新編密碼學 課件 第3章 古典密碼

3.1古典密碼體制

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

。對任意的密鑰定義其中,k1-1

表示k1

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

與26互素。

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

相

關

結

論,同

余

方

程y≡(k1x+k2)mod26有

唯

一

解x,當

且

僅

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

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

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

置換”上,置換方式的過于簡單使其安全性不高。為了進一步增加安全性,1929年Hill提出了一種多表代換密碼———Hill密碼。該算法保留了置換密碼的加密框架,所不同的是將分組后的每個部分采用線性變換的方式得到密文,即將明文消息按照步長m進行分組,對每一組的m個明文字母通過線性變換將其轉換成m個相應的密文字母。這樣密鑰由一個較為簡單的排列問題改變成較為復雜的m×m階可逆矩陣。在使用Hill密碼前,先將英文的26個字母和數(shù)字1~26按自然順序進行一一對應。Hill密碼的密碼體制定義如下:令m是一個正整數(shù),且m≥2,M=C=(?26)m,K是定義在?26上的所有大小為m×m的可逆矩陣的集合。對任意的A∈K,定義3.2密碼分析技術自從有了加密算法,對加密信息的破解技術應運而生。加密算法的對立面稱作密碼分析,也就是研究密碼算法的破譯技術。加密和破譯構成了一對矛盾體,密碼學的主要目的是保護通信消息的秘密以防止被攻擊。由于古典密碼是為了對英文字符進行加密而設計的,所以許多對古典密碼的密碼分析方法都利用了英文語言的統(tǒng)計特性。在對大量的英文文章、報紙、小說和雜志進行統(tǒng)計分析的基礎上,Beker和Piper給出了26個英文字符出現(xiàn)頻率的統(tǒng)計結果(見表3-5)在表35的基礎上,我們可以將26個英文字符劃分成如下5個部分:(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。當然,除了26個英文字符呈現(xiàn)出的統(tǒng)計規(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)計規(guī)律性,可以實現(xiàn)對古典密碼體制的破譯。先以仿射密碼為例來說明應用以上統(tǒng)計結果對其進行唯密文攻擊的密碼分析過程。假設攻擊者Oscar截獲到的密文為FMXVEDKAPHFERBNDKRXRSREFMORUDSDKDVSHVUFEDKAPRKDLYEVLRHHRH對以上密文消息中的英文字符進行統(tǒng)計,相應的結果見表3-6。通過以上統(tǒng)計可知,在密文消息中按照出現(xiàn)頻率排序,頻率最高的英文字符依次是R,D,E,H,K,S,F,V。通過與表3-5對照,我們可以假設密文字符R對應的明文字符是e,密文字符D對應的明文字符是t。用仿射密碼體制來表示,就是ekey(4)=17,ekey(19)=3。仿射密碼體制中,ekey(x)≡(k1x+k2)mod26,這里k1,k2

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

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