新編密碼學(xué) 課件 第3章 古典密碼

3.1古典密碼體制

3.2密碼分析技術(shù)古典密碼(ClassicalCipher)是密碼學(xué)的淵源。雖然古典密碼比較簡(jiǎn)單而且容易破譯,但研究古典密碼的設(shè)計(jì)原理和分析方法對(duì)理解、分析、設(shè)計(jì)現(xiàn)代密碼是十分有益的。古典密碼大多是以單個(gè)字母為作用對(duì)象的加密法,本章簡(jiǎn)要介紹一些典型的古典密碼體制(ClassicalCipherSystem),并在此基礎(chǔ)上對(duì)古典密碼學(xué)進(jìn)行分析,給出密碼分析學(xué)的基本概念和原理。3.1古典密碼體制3.1.1棋盤密碼棋盤密碼是公元前2世紀(jì)前后由希臘作家Polybius提出來的,在當(dāng)時(shí)得到了廣泛的應(yīng)用。棋盤密碼通過將26個(gè)英文字母加密成兩位整數(shù)來達(dá)到加密目的的,棋盤密碼的密鑰是一個(gè)5×5的棋盤,將26個(gè)英文字母放置在里面,其中字母i和j被放在同一個(gè)方格中。將字母i和j放在同一個(gè)方格的原因是j是一個(gè)低頻率字母,在明文中出現(xiàn)得很少,它可用i來替代而不影響文字的可讀性。棋盤密碼的密鑰如圖3-1所示。在給定了字母排列結(jié)果的基礎(chǔ)上,每一個(gè)字母都會(huì)對(duì)應(yīng)一個(gè)整數(shù)αβ,其中α是該字母所在行的標(biāo)號(hào),β是該字母所在列的標(biāo)號(hào)。通過設(shè)計(jì)的棋盤可以對(duì)英文消息進(jìn)行加密,例如,u對(duì)應(yīng)的是22,f對(duì)應(yīng)的是34。3.1.2移位密碼移位密碼的加密對(duì)象為英文字母。移位密碼采用對(duì)明文消息的每一個(gè)英文字母向前推移固定key位的方式來實(shí)現(xiàn)加密。換句話說,移位密碼實(shí)現(xiàn)了26個(gè)英文字母的循環(huán)移位。由于英文共有26個(gè)字母,我們可以在英文字母表和?26={0,1,…,25}之間建立一一對(duì)應(yīng)的映射關(guān)系,因此,可以在?26中定義相應(yīng)的加法運(yùn)算來表示加密過程。移位密碼中,當(dāng)取密鑰key=3時(shí),得到的移位密碼稱為凱撒密碼,這是因?yàn)樵撁艽a體制首先被JuliusCaesar所使用。移位密碼的密碼體制定義如下:令M=C=K=?26,對(duì)任意的key∈?26,x∈M,y∈C,定義在使用移位密碼體制對(duì)英文字母進(jìn)行加密之前,首先需要26個(gè)英文字母與?26中的元素建立一一對(duì)應(yīng)關(guān)系,然后應(yīng)用以上密碼體制進(jìn)行相應(yīng)的加密計(jì)算和解密計(jì)算。3.1.3仿射密碼仿射密碼是移位密碼的一個(gè)推廣,其加密過程中不僅包含移位操作,而且使用了乘法運(yùn)算。與移位密碼相同,仿射密碼的明文空間M和密文空間C均為?26,因此,在使用仿射密碼體制對(duì)英文消息進(jìn)行加密之前,需要26個(gè)英文字母與?26中的元素建立一一對(duì)應(yīng)關(guān)系,然后才能應(yīng)用仿射密碼體制進(jìn)行相應(yīng)的加密計(jì)算和解密計(jì)算。仿射密碼的密碼體制定義如下:令M=C=?26,密鑰空間

。對(duì)任意的密鑰定義其中,k1-1

表示k1

在?26中的乘法逆,gcd(k1,26)=1表示k1

與26互素。

根據(jù)數(shù)論中的

相

關(guān)

結(jié)

論,同

余

方

程y≡(k1x+k2)mod26有

唯

一

解x,當(dāng)

且

僅

當(dāng)gcd(k1,26)=1。當(dāng)k1=1時(shí),仿射密碼就是移位密碼,因此,移位密碼是仿射密碼的特例。仿射密碼相當(dāng)于在使用移位密碼之前對(duì)明文做了一個(gè)一一變換。

3.1.4代換密碼移位密碼可看成是對(duì)26個(gè)英文字母的一個(gè)簡(jiǎn)單置換,比移位密碼稍微復(fù)雜一點(diǎn)的仿射密碼是對(duì)26個(gè)英文字母的一個(gè)較為復(fù)雜的置換,因此我們可以考慮26個(gè)英文字母集合上的一般置換操作。鑒于26個(gè)英文字母和?26中的元素可以建立一一對(duì)應(yīng)關(guān)系,于是?26中元素的任一個(gè)置換也就對(duì)應(yīng)了26個(gè)英文字母表上的一個(gè)置換。我們可以借助?26中元素的置換來改變英文字母表中英文字符的原有位置,即用新的字符代替明文消息中的原有字符,以達(dá)到加密明文消息的目的。?26上的置換被當(dāng)作加密所需的密鑰,由于該置換對(duì)應(yīng)26個(gè)英文字母表上的一個(gè)置換,因此我們可以將代換密碼的加密和解密過程看作是應(yīng)用英文字母表的置換變換進(jìn)行的代換操作。代換密碼的密碼體制定義如下:令M=C=?26,K是?26上所有可能置換構(gòu)成的集合。對(duì)任意的置換π∈K,x∈M,y∈C,定義3.1.5維吉尼亞密碼前面介紹的移位密碼體制、仿射密碼體制,以及更為一般的代換密碼體制,一旦加密密鑰被選定,則英文字母表中每一個(gè)字母對(duì)應(yīng)的數(shù)字都會(huì)被加密成唯一的一個(gè)密文,這種密碼體制被稱為單表代換密碼?？紤]到頻率分析法破解單表代換密碼的高成功率,人們開始考慮多表代換密碼,通過用多個(gè)密文字母替換同一個(gè)明文字母的方式消除字符的特性,即一個(gè)明文字母可以映射為多個(gè)密文字母。本節(jié)介紹多表代換密碼的一個(gè)基本范例———維吉尼亞密碼(VigenèreCipher),它是由法國(guó)人BlaisedeVigenère在16世紀(jì)提出的。維吉尼亞密碼的密碼體制定義如下:令m是一個(gè)正整數(shù),M=C=K=(?26)m。對(duì)任意的密鑰key=(k1,k2,…,km)∈K,(x1,x2,…,xm)∈M,(y1,y2,…,ym)∈C,定義如果已經(jīng)在26個(gè)英文字母和?26之間建立了一一對(duì)應(yīng)的關(guān)系,則每一個(gè)密鑰key∈K都相當(dāng)于一個(gè)長(zhǎng)度為m的字母串,被稱為密鑰字。當(dāng)m=1時(shí),維吉尼亞密碼退化為移位密碼。因此,維吉尼亞密碼可看成是移位密碼的高維化,強(qiáng)化了移位密碼的安全性。維吉尼亞密碼通過將“單字目加密”改為“字母組加密”,體現(xiàn)出了“分組”加密的思想。3.1.6置換密碼前面幾小節(jié)介紹的加密方式的共同特點(diǎn)是通過將英文字母改寫成另一個(gè)表達(dá)形式來達(dá)到加密的效果。本節(jié)介紹另一種加密方式,通過重新排列消息中元素的位置而不改變?cè)乇旧淼姆绞綄?duì)一個(gè)消息進(jìn)行變換,這種加密機(jī)制稱為置換密碼(也稱為換位密碼)。置換密碼是古典密碼中除代換密碼外的重要一類,它被廣泛應(yīng)用于現(xiàn)代分組密碼的構(gòu)造。與維吉尼亞密碼一樣,置換密碼也體現(xiàn)出了“分組”加密的思想。置換密碼的密碼體制定義如下:令m是一個(gè)正整數(shù),且m≥2,M=C=(?26)m,K是?m={1,2,…,m}上所有可能置換構(gòu)成的集合。對(duì)任意的(x1,x2,…,xm)∈M,π∈K,(y1,y2,…,ym)∈C,定義其中,π和π-1互為?m

上的逆置換,m為分組長(zhǎng)度。對(duì)于長(zhǎng)度大于分組長(zhǎng)度m的明文消息,可對(duì)明文消息先按照長(zhǎng)度m進(jìn)行分組,然后對(duì)每一個(gè)分組消息重復(fù)進(jìn)行同樣的置換加密過程,最終實(shí)現(xiàn)對(duì)明文消息的加密。3.1.7Hill密碼置換密碼的主要思想體現(xiàn)在“分組

置換”上,置換方式的過于簡(jiǎn)單使其安全性不高。為了進(jìn)一步增加安全性,1929年Hill提出了一種多表代換密碼———Hill密碼。該算法保留了置換密碼的加密框架,所不同的是將分組后的每個(gè)部分采用線性變換的方式得到密文,即將明文消息按照步長(zhǎng)m進(jìn)行分組,對(duì)每一組的m個(gè)明文字母通過線性變換將其轉(zhuǎn)換成m個(gè)相應(yīng)的密文字母。這樣密鑰由一個(gè)較為簡(jiǎn)單的排列問題改變成較為復(fù)雜的m×m階可逆矩陣。在使用Hill密碼前,先將英文的26個(gè)字母和數(shù)字1~26按自然順序進(jìn)行一一對(duì)應(yīng)。Hill密碼的密碼體制定義如下:令m是一個(gè)正整數(shù),且m≥2,M=C=(?26)m,K是定義在?26上的所有大小為m×m的可逆矩陣的集合。對(duì)任意的A∈K,定義3.2密碼分析技術(shù)自從有了加密算法,對(duì)加密信息的破解技術(shù)應(yīng)運(yùn)而生。加密算法的對(duì)立面稱作密碼分析,也就是研究密碼算法的破譯技術(shù)。加密和破譯構(gòu)成了一對(duì)矛盾體,密碼學(xué)的主要目的是保護(hù)通信消息的秘密以防止被攻擊。由于古典密碼是為了對(duì)英文字符進(jìn)行加密而設(shè)計(jì)的,所以許多對(duì)古典密碼的密碼分析方法都利用了英文語(yǔ)言的統(tǒng)計(jì)特性。在對(duì)大量的英文文章、報(bào)紙、小說和雜志進(jìn)行統(tǒng)計(jì)分析的基礎(chǔ)上,Beker和Piper給出了26個(gè)英文字符出現(xiàn)頻率的統(tǒng)計(jì)結(jié)果(見表3-5)在表35的基礎(chǔ)上,我們可以將26個(gè)英文字符劃分成如下5個(gè)部分:(1)字符E的概率大約為0.12。(2)字符A,H,I,N,O,R,S,T的概率大約為0.06~0.09。(3)字符D,L的概率大約為0.04。(4)字符B,C,F,G,M,P,U,W,Y的概率大約為0.015~0.028。(5)字符J,K,Q,V,X,Z的概率小于0.01。當(dāng)然,除了26個(gè)英文字符呈現(xiàn)出的統(tǒng)計(jì)規(guī)律性,還有一些常見的字母組合,如TH,HE,IN,RE,DE,ST,EN,AT,OR,IS,ET,IT,AR,TE,HI,OF,THE,ING,ERE,ENT,FOR等,這些規(guī)律都為密碼分析提供了很好的依據(jù)。根據(jù)以上英文字母的統(tǒng)計(jì)規(guī)律性,可以實(shí)現(xiàn)對(duì)古典密碼體制的破譯。先以仿射密碼為例來說明應(yīng)用以上統(tǒng)計(jì)結(jié)果對(duì)其進(jìn)行唯密文攻擊的密碼分析過程。假設(shè)攻擊者Oscar截獲到的密文為FMXVEDKAPHFERBNDKRXRSREFMORUDSDKDVSHVUFEDKAPRKDLYEVLRHHRH對(duì)以上密文消息中的英文字符進(jìn)行統(tǒng)計(jì),相應(yīng)的結(jié)果見表3-6。通過以上統(tǒng)計(jì)可知,在密文消息中按照出現(xiàn)頻率排序,頻率最高的英文字符依次是R,D,E,H,K,S,F,V。通過與表3-5對(duì)照,我們可以假設(shè)密文字符R對(duì)應(yīng)的明文字符是e,密文字符D對(duì)應(yīng)的明文字符是t。用仿射密碼體制來表示,就是ekey(4)=17,ekey(19)=3。仿射密碼體制中,ekey(x)≡(k1x+k2)mod26,這里k1,k2

是未知的加密密鑰。根據(jù)假設(shè)我們可以得到關(guān)于密鑰k1,k2

的線性方程組解以上方程組,得到唯一的解k1=6,k2=19。因?yàn)間cd(k1,26)=2≠1,顯然得到的密鑰是不合法的。說明以上假設(shè)密文字符R對(duì)應(yīng)明文字符e,密文字符D對(duì)應(yīng)明文字符t是錯(cuò)誤的。根據(jù)表3-5,我們?cè)偌僭O(shè)密文字符R對(duì)應(yīng)的明文字符是e,密文字符E對(duì)應(yīng)的明文字符是t。同樣用仿射密碼體制來表示,就是ekey(4)=17,ekey(19)=4。采用相同的方法建立線性方程組解方程組可得k1=13。得到的密鑰也是不合法的。再假設(shè)密文字符R對(duì)應(yīng)的明文字符是e,密文字符H對(duì)應(yīng)的明文字符是t。同樣用仿射密碼體制來表示,就是ekey(4)=17,ekey(19)=7。采用相同的方法建立線性方程組解方程組可得k1=8。得到的密鑰仍然是不合法的。再假設(shè)密文字符R對(duì)應(yīng)的明文字符是e,密文字符K對(duì)應(yīng)的明文字符是t。同樣用仿射密碼體制來表示,就是ekey(4)=17,ekey(19)=10。采用相同的方法建立線性方程組解方程組得到唯一的解k1=3,k2=5?？梢灾赖玫降拿荑€是一組合法密鑰。接下來我們應(yīng)用得到的密鑰對(duì)密文消息進(jìn)行解密,進(jìn)一步驗(yàn)證密鑰的正確性。由于3-1mod26≡9,所以解密過程為dkey(y)=9y-19。得到解密密文Algorithmsarequitegeneraldefinitionsofarithmeticprocesses通過解密出的明文消息可知,所得到的密鑰是正確的。再以代換密碼為例來說明應(yīng)用表35的統(tǒng)計(jì)結(jié)果對(duì)其進(jìn)行唯密文攻擊的密碼分析過程。假設(shè)攻擊者Oscar截獲到的密文為YIFQFMZRWQFYVECFMDZPCVMRZWNMDZVEJBTXCDDUMJNDIFEFMDZCDMQZKCEYFCJMYRNCWJCSZREXCHZUNMXZNZUCDRJXYYSMRTMEYIFZWDYVZVYFZUMRZCRWNZDZJJXZWGCHSMRNMDHNCMFQCHZJMXJZWIEJYUCFWDJNZDIR對(duì)以上密文消息中的英文字符進(jìn)行統(tǒng)計(jì),相應(yīng)的結(jié)果如表3-7所示。通過以上統(tǒng)計(jì)可知,在密文消息中按照出現(xiàn)頻率排序,頻率最高的英文字符依次是Z,M,C,D,F,J,R,Y。通過與表3-5對(duì)照,我們可以假設(shè)密文字符Z對(duì)應(yīng)的明文字符是e,密文字符集合{M,C,D,F,J,R,Y}對(duì)應(yīng)的明文字符集合是{a,h,i,o,r,s,t}。但是僅依據(jù)表3-5與以上的統(tǒng)計(jì)結(jié)果之間的關(guān)系難以確定兩個(gè)字符集合之間的具體對(duì)應(yīng)關(guān)系。接下來我們?cè)倮糜⑽淖址M合的統(tǒng)計(jì)規(guī)律性來進(jìn)行分析。由于已經(jīng)假設(shè)密文字符Z對(duì)應(yīng)的明文字符是e,在密文消息中,與字符Z有關(guān)的長(zhǎng)度為2的組合中出現(xiàn)較多的分別是DZ和ZW(分別出現(xiàn)4次);NZ和ZU(分別出現(xiàn)3次);RZ,HZ,XZ,FZ,ZR,ZV,ZC和ZD(分別出現(xiàn)2次)。在以上統(tǒng)計(jì)結(jié)果中,ZW出現(xiàn)了4次,而WZ沒有出現(xiàn),同時(shí)字符W本身單獨(dú)出現(xiàn)的次數(shù)也較少,所以我們假設(shè)密文字符W對(duì)應(yīng)的明文字符是d。由于DZ出現(xiàn)4次,而ZD也出現(xiàn)了2次,我們可以假設(shè)密文字符D可能對(duì)應(yīng)明文字符r,s,t中的某一個(gè)。在密文的開始部分出現(xiàn)ZRW和RZW字符組合,字符組合RW在密文消息中也出現(xiàn)過,而且密文字符R在密文消息中也頻繁出現(xiàn)。所以我們假設(shè)密文字符R對(duì)應(yīng)的明文字符是n。根據(jù)已經(jīng)做出的假設(shè),我們可以給出密文的部分破譯結(jié)果如下:由于密文字符組合NZ出現(xiàn)的頻率較高,而組合ZN出現(xiàn)次數(shù)很少。所以接下來我們假設(shè)密文字符N對(duì)應(yīng)的明文字符是h。如果該假設(shè)是正確的,則在密文消息第三行中出現(xiàn)的RZCRWNZ對(duì)應(yīng)的明文字符序列是ne?ndhe,據(jù)此可以假設(shè)密文字符C對(duì)應(yīng)的明文字符是a。根據(jù)以上假設(shè),我們可以得到進(jìn)一步的破譯結(jié)果如下:接下來我們確定在密文中出現(xiàn)次數(shù)較多的字符M,由于已經(jīng)確定密文RNM解密成nh?,說明h很可能是一個(gè)單詞的第一個(gè)字符,所以M對(duì)應(yīng)的明文字符應(yīng)該是一個(gè)元音字符?？紤]到我們已經(jīng)使用了元音字符a和e,同時(shí)考慮到字符組合ao出現(xiàn)概率較低,我們假設(shè)密文字符M對(duì)應(yīng)的明文字符是i。從而進(jìn)一步得到破譯結(jié)果如下:在剩余的{D,F,J,Y}與{r,s,t,o}的對(duì)應(yīng)關(guān)系中,根據(jù)密文消息第一行的組合CFM對(duì)應(yīng)a?i,可以猜測(cè)密文字符F不可能對(duì)應(yīng)明文字符o。根據(jù)密文消息第二行的組合CJM對(duì)應(yīng)a?i,可以猜測(cè)密文字符J也不可能對(duì)應(yīng)明文字符o。因此我們假設(shè)密文字符Y對(duì)應(yīng)的明文字符是o。剩余的對(duì)應(yīng)關(guān)系中,由于NMD出現(xiàn)了2次,所以假設(shè)密文字符D對(duì)應(yīng)的明文字符是s,而根據(jù)密文消息第四行的組合HNCMF對(duì)應(yīng)chai?,可以假設(shè)密文字符F對(duì)應(yīng)的明文字符是r,密文字符H對(duì)應(yīng)的明文字符是c。從而假設(shè)密文字符J對(duì)應(yīng)的明文字符是t。在此基礎(chǔ)上,進(jìn)一步得到破譯結(jié)果如下:在此基礎(chǔ)上,我們可以得到解密的明文消息為:理論上講,一次一密的密碼體制是不可破譯的,但考慮到加密算法的密鑰傳輸代價(jià),它又是不實(shí)用的,所以實(shí)際上不存在不可破譯的密碼(除了后面將要介紹的序列密碼,但考慮到算法的實(shí)用性,序列密碼算法也是有可能被破譯的)。對(duì)于加密法的評(píng)估,20世紀(jì)40年代,Shannon提出了一個(gè)常用的評(píng)估概念,他認(rèn)為一個(gè)好的加密法應(yīng)具有混淆性(Confusion)和擴(kuò)散性(Diffusion)。混淆性意味著加密法應(yīng)隱藏所有的局部模式,即隱藏那些可能導(dǎo)致破解密鑰的提示性信息的特征;擴(kuò)散性要求加密法將密文的不同部分進(jìn)行混合,使得任何字符都不在原來的位置。前面介紹的幾個(gè)古典密碼中,由于未能滿足Shannon提出的兩個(gè)條件,所以它們能被破解。此