應用密碼學：第二章 古典密碼體制及其破譯

1、 密 碼 學第二章 古典密碼體制及其破譯內(nèi)容：1、 密碼體制定義和分類2、古典密碼體制與破譯 2、古典密碼體制與破譯 2.1 替代和換位 2.2 單表古典密碼 2.3 多表古典密碼 2.4 古典密碼的統(tǒng)計分析與破譯2.1 替代和換位對稱鑰密碼 分組密碼 block cipher 序列密碼 stream cipher替代密碼 substitution cipher換位密碼 transposition cipher乘積密碼 product cipher古典密碼1、置換的概念：permutation 一般加密函數(shù)或變換應當是雙射，這樣保證解密是 唯一的。古典密碼一般是字母到字母的變換，所以 雙射是一

2、個集合映射到自身時，就稱為置換。 設(shè) S 是一個有限集合，置換p 是從 S 到 S 的一 個雙射。 如果p是（1,2, ,n）到（1,2, ,n）的一個置換，則記為 例： S（1，2，3，4，5）， 一個置換 p：S S 定義為： p(1)=3, p(2)=5, P(3)=4, p(4)2, p(5)1，從位置上說：第一行表示原位置 第二行表示置換后的元素的位置例：英語字母表上的置換。（共有26！種） 將英文字母表26個字母反序。 a b c d e f g h i j k l m n o p q r s t u v w x y zz y x w v u t s r q p o n m l k

3、 j i h g f e d c b a 如果我們利用上述置換表，對cyptography進行字母代換，（為了清楚，我們四個字母一組），就得到一種密碼c r y p t o g r a p h yXI BK GLT I ZKSB這就是一種替代密碼。例：n長的英文字母串上的置換。（共有n！種） 將crptography的第一位字母和最后一個字母對調(diào)， 將第二位字母和導數(shù)第二位字母對調(diào)，依次類推， 產(chǎn)生一個置換。 cryptography yhpargotpyrc這就是一種換位密碼。 2、替代密碼 (substitution cipher): 用其它的字母替代明文中的字母，而保持明文字母 順序關(guān)系

4、。 又分為單表替代和多表替代。A是含有 q 個符號的字母表K 是 A 上的所有置換的集合（每種置換對應一個表）對明文消息 ， ，單表替代加密變換為單表替代是用一個固定的置換 e。對 c 解密時，計算，例如明文字母為Y，即 ，則因此密文為B。這里密鑰就是3。 愷撒密碼就是單表替代密碼，如果我們用數(shù)字 0，1，2，24，25分別表示字母A，B，C，Y，Z，則密文字母可用明文字母 表示為： 因為置換限制為移位，所以這類密碼又稱為移位密碼。(shift cipher)利用密鑰 對消息 加密時， A是含有 q 個符號的字母表 M是 A 上的長度為 n 的所有符號串的集合 密鑰空間 K 包含所有有序的 n

5、 個置換 的集合， 每個置換都定義在A上。 多表替代密碼就是用一系列的不同置換替代明文中的字母。 也就是在不同字母位置使用不同的替換規(guī)則。 解密時利用逆置換例如：有兩個字母表的置換如下 （1） 向前移一位，k1=1a b c d e f g h i j k l m n o p q r s t u v w x y zb c d e f g h i j k l m n o p q r s t u v w x y z a （2） 向前移兩位，k2=2a b c d e f g h i j k l m n o p q r s t u v w x y zc d e f g h i j k l m n o

6、 p q r s t u v w x y z a b則對cryptography的二表替代密碼為： cr yp to gr ap hy dt zr uq ht br ia 轉(zhuǎn)輪機替代密碼實例上個世紀20年代，出現(xiàn)了轉(zhuǎn)輪密碼，而由德國發(fā)明家亞瑟謝爾比烏斯發(fā)明的Enigma 密碼機最為著名。它主要由經(jīng)電線相連的鍵盤、轉(zhuǎn)子和顯示器組成，轉(zhuǎn)子本身也集成了26條線路（在圖2-5中顯示了6條），把鍵盤的信號對應到顯示器不同的小燈上去。在圖2-5中可以看到，如果按下a鍵，那么燈B就會亮，這意味著a被加密成了B。同樣地我們看到，b被加密成了A，c被加密成了D，d被加密成了F，e被加密成了E，f被加密成了C。于

7、是如果我們在鍵盤上依次鍵入cafe（咖啡），顯示器上就會依次顯示DBCE，這是最簡單的加密方法之一簡單替代密碼。多輪替代多輪替代(省)不僅僅如此，因為當鍵盤上一個鍵被按下時，相應的密文在顯示器上顯示，然后轉(zhuǎn)子的方向就自動地轉(zhuǎn)動一個字母的位置（在圖中就是轉(zhuǎn)動1/6圈，而在實際中轉(zhuǎn)動1/26圈）。圖2-6表示了連續(xù)鍵入3個b的情況。(省)當?shù)谝淮捂I入b時，信號通過轉(zhuǎn)子中的連線，燈A亮起來，放開鍵后，轉(zhuǎn)子轉(zhuǎn)動一格，各字母所對應的密碼就改變了；第二次鍵入b時，它所對應的字母就變成了C；同樣地，第三次鍵入b時，燈E閃亮。為使機器更安全，可以把幾種轉(zhuǎn)輪和移動的齒輪結(jié)合起來。因為所有轉(zhuǎn)輪以不同的速度移動，n

8、個轉(zhuǎn)輪的機器的周期是26n。為進一步阻止密碼分析，有些轉(zhuǎn)輪機在每個轉(zhuǎn)輪上還有不同的位置號。(省)德國人為了戰(zhàn)時使用，大大加強了其基本設(shè)計，軍用的Enigma由3個轉(zhuǎn)輪，從5個轉(zhuǎn)輪中選取。轉(zhuǎn)輪機中還有一塊稍微改名明文序列的插板，有一個反射器導致每個轉(zhuǎn)輪對每一個明文字母操作兩次，結(jié)構(gòu)如圖2-7所示。(省)于是轉(zhuǎn)子自身的初始方向，轉(zhuǎn)子之間的相互位置，以及連接板連線的狀況就組成了所有可能的密鑰：三個轉(zhuǎn)子不同的方向組成了26*26*26=17576種不同可能性；三個轉(zhuǎn)子間不同的相對位置為6種可能性；連接板上兩兩交換6對字母的可能性數(shù)目非常巨大，有100391791500種；于是一共有17576*6*10

9、0391791500，大約為10000000000000000，即一億億種可能性。(省)但如此復雜的密碼機在第二次世界大戰(zhàn)中被破解了，首先是波蘭人利用德軍電報中前幾個字母的重復出現(xiàn)，破解了早期的Enigma密碼機，而后又將破譯的方法告訴了法國人和英國人。英國人在計算機理論之父圖靈的帶領(lǐng)下，通過尋找德國人在密鑰選擇上的失誤，并成功奪取德軍的部分密碼本，獲得密鑰，以及進行選擇明文攻擊等等手段，破解出相當多非常重要的德軍情報。EnigmaEnigmaEnigmaEnigmaEnigma3、換位密碼（transposition cipher） 替代保持明文字母序列的順序，但變換明文字母。換位則相反，它

10、重新排列字母，并不變換明文字母表。 分組長度為n密鑰空間K是1,2, , , ,n 上的所有置換的集合對于消息 ，密鑰 ，加密函數(shù)為（各個序號表示位置）。解密時利用密鑰，即逆置換 ，對于密文。 例如： 簡單換位密碼的分組長度為n6，密鑰為 e =(6 4 1 3 5 2)， 則消息 m =(CAESAR)加密為 c =(RSCEAA)。 解密的密鑰為d=(3 6 4 2 5 1)，得到明文。 注： “transpositon”常用“permutation”替換，特別是在 DES的substitutionpermutation網(wǎng)絡(luò)中，就是用 “置換”表示“換位”。 第一行是原位置，第二行是置換后

11、的位置。置換的結(jié)果！例如：假如有一個密鑰是type（不能重復字母） 的列置換密碼，我們把明文can you understand 首先按行排列 密鑰 t y p e 順序 3 4 2 1 c a n y o u u n d e r s t a n d 按列寫出密文：YNSDNURNCODTAUEA。 替代和換位的區(qū)別： 1、替代保持明文字母順序； 而換位打亂明文字母順序。 2、換位密鑰量為n！，取決于字母串的個數(shù)n， 如果n較小則很容易通過遍歷找到密鑰。 單表替代的密鑰量是q！ 多表替代有多種情況。 3、換位密鑰不會出現(xiàn)字母串以外的字母； 而替代可能出現(xiàn)字母串以外的字母。 2.2 單表古典密碼

12、以下設(shè) X 是明文空間的字母表， Y是密文空間的字母表。我們僅考慮XY的情況。設(shè) q 是一個正整數(shù)， 是在模q加法和模q乘法下的交換環(huán)。對于英文字母表，q26。 是在模q下的乘法群。 一、基本加密方法乘積密碼的密鑰量為 加密密碼的密鑰量為q。1、加法密碼2、 乘法密碼仿射密碼是置換 密碼的特例，置換 密碼的密鑰量為K為 上的全體置換的集合，對任意3、仿射密碼（因仿射變換而得名） 加法和乘法密碼是仿射密碼的特例，密鑰量為 4、置換密碼（此應為前面的一般單表替代。）二、單表替代密碼的例子1愷撒密碼體制 已經(jīng)介紹過這種密碼，它是一種加法密碼，k3。 2標準字頭密碼體制 這是一種置換（一般替代）密碼，

13、利用一個密鑰字 構(gòu)造置換。 例如 選擇cipher作為密鑰字， 則明密文字母對應關(guān)系為： abcdefghijklmnopqrstuvwxycipherabdfgjklmnoqstuvwxyzZ2.3 多表古典密碼1、簡單加法密碼 一、基本加密方法其中的加法都是模 q 加法，密鑰量 表示 n 個字母。2、簡單乘積密碼其中乘法都是模q的乘法，密鑰量 3、簡單仿射密碼 運算都是模q運算，密鑰量 4、 簡單置換 密碼 （應為前面的一般多表替代密碼 ） 密鑰量為 5、換位密碼 （這里換位被看作一種多表替代密碼?。?密鑰量為 n！ 注意： 替代中的置換（密鑰）是明文字母表上的置換； 換位中的置換（密鑰）

14、是分組的位置上的置換！6、廣義置換密碼 （應稱為向量置換替代密碼。） 密鑰量為 7、廣義仿射密碼 （同樣可以看作向量運算） 密鑰量為 是 上的不同的n階可逆方陣的個數(shù)。 二、多表替代密碼的實例1、Playfair密碼體制：一般多表替代 2、Vigenere密碼體制：簡單加法密碼 3、Beaufort密碼體制：簡單加法密碼 注意： Beaufort方陣不是對稱的， 而Vigenera方陣是斜對稱的，行和列可互換。 4、Vernam密碼體制： 5、Hill密碼體制 ：廣義仿射密碼Playfair密碼體制Playfair密碼體制Vigenere密碼體制Vigenre 密碼的代替規(guī)則是用明文字母在Vi

15、genre方陣中的列和密鑰字母在Vigenre 方陣中的行的交點處的字母來代替該明文字母。例如，設(shè)明文字母為P ，密鑰字母為Y ，則用字母N 來代替密文字母P 。明文：MING MINGCHEN CHENWU WU DIAN FA DONG FAN GONG密鑰：XING XINGCHUI CHUI PING YE KUO YUE YONG DAJIANG LIU密文：JQAME JQAMEOYVLC OYVLC QOYRP QOYRPURMHK URMHK DOAMR NP解密就是利用Vigenre 方陣進行反代替。Vernam 密碼Vernam 密碼、密鑰都表示為二進制位：明文、密文M=m

16、1,m2, mn K=k =k1,k2, kn C =c1,c2,cn加密： c1= mi ki ,i=1,2, ,n 解密：m1= ci ki ,i=1,2, ,n因為加解密算法是模2加，所以稱為代數(shù)密碼。對合運算：f=f -1， 模2 加運算是對合運算。密碼算法是對和運算，則加密算法解密算法，工程實現(xiàn)工作量減半。Vernam 密碼經(jīng)不起已知明文攻擊。2.4 古典密碼的統(tǒng)計分析一、單表密碼的統(tǒng)計分析單表密碼保持明文的統(tǒng)計特性，因此易于被攻破。例如：愷撒密碼將 a，b，c 映射位為 D，E，F(xiàn)統(tǒng)計概率：在大量的有意義文字上的統(tǒng)計值。 統(tǒng)計 概率計算概率計算概率：在固定長度的字母串上的統(tǒng)計值。英

17、文中最常出現(xiàn)的字母e、o、a、n、i，所以密文中最常出現(xiàn)的單字母Xe，其它依次判斷；連接字母頻率中，三字母最常出現(xiàn)的the, ing, and，則密文中三連字母最常出現(xiàn)的為the ，等等。例題：見書中2. 5，為一般的單表替代密碼。如果已知所用的密碼體制，則更容易分析。書中統(tǒng)計概率表！單表密文的統(tǒng)計分析 單表古典密碼體制的密文字母表實際上是明文字母表的一個排列.因此,明文字母的統(tǒng)計特性在密文中能夠反映出來.當截獲的密文足夠多時,就可以通過統(tǒng)計密文字母的出現(xiàn)頻率,來確定明文字母和密文字母的對應關(guān)系.26個字母出現(xiàn)的頻率字母頻率字母頻率字母頻率A0.082K0.008U0.028B0.015L0.

18、040V0.010C0.028M0.024W0.023D0.043N0.067X0.001E0.127O0.075Y0.020F0.022P0.019z0.001G0.020Q0.001H0.061R0.060I0.070S0.063j0.002T0.091 26個英文字母按出現(xiàn)頻率的大小可以分為五類：1. e: 0.1202.t,a,o,I,n,s,h,r 0.060.093.d,l 0.044,c,u,m,w,f,g,y,p,b 0.015-0.0285,v,k,j,x,q,z 小于0.01 這樣，我們可以統(tǒng)計密文中字母的頻率。和上表對應,得出相應的對應方式，推測出明文。注：前提是我們知道

19、明文和密文所使用的字母表。這和古代文字的破譯 是一樣的。 英語中有一些習慣,比方說一些兩個字母或三個字母的的組合出現(xiàn)的頻率很高.例如ea, ed, ing等,我們也可以按照上面的辦法計算出這些雙字母組合和三個字母的組合的頻率,進行對應.這樣基本上單表密碼就可以破譯了. 當然,剩下的就需要根據(jù)對英語和創(chuàng)建以及使用此密碼的人的習慣的了解去猜測.舉例密文為 YIFQFMZRWQFYVECFMDZPCVMRZWNMDZVEJBTXCDDUMJNDIFEFMDZCDMQZKCEYFCJMYRNCWJCSZREXCHZUNMXZNZUCDRJCYYSMRTMRTMEYIFZWDYVZVYFZUMRZCRW

20、NZDZJJXZWGCHSMRNMRNMDHNMDHNCMFQCHZJMXJZWJZWIEJYUCFWDJNZDIR共 168個字母各個密文字母出現(xiàn)次數(shù)和出現(xiàn)頻率：字母次數(shù)頻率字母次數(shù) 頻率A00.000N90.054B10.006O00.000C150.089P10.006D130.077Q40.024E70.042R100.060F110.065S30.018G10.006T20.012H40.024U50.030I50.030V50.030J110.065W80.048K10.006X60.036L00.000Y100.060M160.095Z200.119 由上表可以看出，密文字母Z的

21、出現(xiàn)次數(shù)明顯比其他密文字母的出現(xiàn)次數(shù)多，出現(xiàn)頻率約為0.12。因此，可以猜測ZE. 出現(xiàn)至少十次的字C,D,J,F,M,R,Y,出現(xiàn)頻率在0.06到0.095之間,因此可以猜測C,D,F,J,M,R,Y-T,A,O,I,N,S,H,R 再計算密文字母中包含Z的雙字母和三個字母的重復出現(xiàn)次數(shù),與標準表進行對比,即可得出明文為: Our friend from Paris examined his empty glass with surprise ,as if evaporation has taken place while he was not looking. I poured some

22、more wine and he settled back in his chair ,face tilted up towards the sun. 二、多表密碼的統(tǒng)計分析與破譯多表密碼比單表密碼復雜一些，但仍然不能抵御稍復雜的統(tǒng)計攻擊。我們以Vigenere密碼為例。分析分為兩步： 首先確定密鑰長度，也就是表長度。 其次確定密鑰。 1、確定密鑰長度 m Kasiski測試法重合指數(shù)法Kasiski測試法： 如果相同的兩個明文片段之間的距離為m的倍數(shù)， 則所對應的密文片段一定相同。我們可以在密文中尋找相同的片段，計算相同片段之間的距離，d1,d2,，我們可以猜測m為這些距離的最大公因子（或最

23、常出現(xiàn)的因子）。反之，密文中相同的片段所對應的明文也可能相同。重合指數(shù)法： 單表加密的字母串的重合指數(shù)和多表加密的字母串 的重合指數(shù)有明顯差別，因此通過比較重合指數(shù)， 就可以判斷表的個數(shù)也就是密鑰字長度。 重合指數(shù)：設(shè) 是一個長度為n的英文字 母串，x中任意兩個隨機元素相同的概率。為字母在 x 中出現(xiàn)的次數(shù)。X中取兩個元素的次數(shù)；兩個元素同時為i的次數(shù)。對于任意字母串，可以計算重合指數(shù)這一指標，而這一指標，對于有意義文本和完全隨機值是明顯不同的:對明文 x，兩個隨機元素同為 i 的概率為 如果經(jīng)過單表加密得到密文x，總體統(tǒng)計特性不變：但如果經(jīng)過不同表加密得到得密文，則隨機性強一些：為此，將長為

24、 n 的密文字母 按列排成 m 行，n/m列的矩形陣列。如果 m 是密鑰字長度，則每一行都是單表變換，每一行的重合指數(shù)應約為 0.065; 如果 m 不是密鑰字長度，則每一行都是多表變換，每一行的重合指數(shù)都應約為0.038.m個n/m個2、確定具體密鑰-移位密碼 思路是通過計算交互重合指數(shù)，找到各密鑰字母的關(guān)系（相對位移），密鑰字母都歸結(jié)為一個密鑰字母的關(guān)系式，之后利用窮舉搜索找到這個密鑰字母，也就找到了所有密鑰字母。 交互重合指數(shù) mutual index of coincidence： 兩個長度分別為n和 的字母串 x 中一個隨機元素與y 中的一個隨機元素 相同 的概率 中的一個隨機元素和 中的一個隨機元素同時為第 h 個英文字母的概率（統(tǒng)計值）為 現(xiàn)假定已經(jīng)確定密鑰字的長度 m，密文子串 （陣列的一行）中各密文字母都是由同一單表加密得來。 設(shè)密鑰為：abcdefghijklmnopqrstuvwxyDEFGHIJKLMNOPQRSTUVWXYZAB例如：a 經(jīng)過 k1=3，變?yōu)?DzCa 經(jīng)過 k2=5，變?yōu)?FabcdefghijklmnopqrstuvwxyFGHIJKLMNOPQRSTUVWXYZABCDzE那么兩段密文中同時為 D的概率為：同時為 F的概率為：同時為 A的概率為： 額外移 2明文例題見書中例 2. 6。相對位移：由交互重合指數(shù)的估計表可