第3章 古典密碼學(xué)

1、1第第2 2章章 古典密碼技術(shù)古典密碼技術(shù) 古典密碼技術(shù)古典密碼技術(shù) 古典密碼體制古典密碼體制 定義和分類定義和分類 代換密碼代換密碼 置換密碼置換密碼 古典密碼的統(tǒng)計分析古典密碼的統(tǒng)計分析 單表替代密碼分析單表替代密碼分析 對對HillHill密碼的已知明文分析密碼的已知明文分析 2隱寫術(shù)隱寫術(shù) 我畫藍(lán)江水悠悠，我畫藍(lán)江水悠悠，愛晚亭上楓葉愁。愛晚亭上楓葉愁。秋月溶溶照佛寺，秋月溶溶照佛寺，香煙裊裊繞經(jīng)樓香煙裊裊繞經(jīng)樓 3第第2 2章章 古典密碼技術(shù)古典密碼技術(shù)2.1.1 2.1.1 定義和分類定義和分類4密碼體制的要素密碼體制的要素 明文：發(fā)送方將要發(fā)送的消息明文：發(fā)送方將要發(fā)送的消息 密

2、文：明文被變換成看似無意義的隨機消息密文：明文被變換成看似無意義的隨機消息 加密：明文變換成密文的過程稱為加密加密：明文變換成密文的過程稱為加密 解密：密文恢復(fù)出原明文的過程稱為解密解密：密文恢復(fù)出原明文的過程稱為解密 加密算法：對明文進行加密時所采用的一組加密算法：對明文進行加密時所采用的一組規(guī)則規(guī)則 解密算法解密算法：對密文進行解密時所采用的一組：對密文進行解密時所采用的一組規(guī)則規(guī)則 加密和解密算法的操作通常都是在一組密鑰加密和解密算法的操作通常都是在一組密鑰控制下進行的，分別稱為控制下進行的，分別稱為加密密鑰和解密密加密密鑰和解密密鑰鑰5第第2 2章章 古典密碼技術(shù)古典密碼技術(shù)定義定義2

3、.1 一個密碼系統(tǒng)（一個密碼系統(tǒng)（Cryptosystem）是一個五元是一個五元組（組（P, C, K, E, D）滿足條件：滿足條件： （1）P是可能明文的有限集；（明文空間）是可能明文的有限集；（明文空間） （2）C是可能密文的有限集；（密文空間）是可能密文的有限集；（密文空間） （3）K是一切可能密鑰組成的有限集；是一切可能密鑰組成的有限集；(密鑰空間密鑰空間) （4）對于）對于kK，有一個加密算法有一個加密算法 ekE 和相應(yīng)的和相應(yīng)的解密算法解密算法dkD ,使得使得 ek:PC 和和 dk:C P 分別為加密、解密函數(shù)，滿足分別為加密、解密函數(shù)，滿足dk(ek(x)=x，這里，這里

4、xP6第第2 2章章 古典密碼技古典密碼技術(shù)術(shù) 對稱密碼是一種加解密使用相同密鑰的密碼體對稱密碼是一種加解密使用相同密鑰的密碼體制制 應(yīng)用密碼體系應(yīng)滿足的特性應(yīng)用密碼體系應(yīng)滿足的特性 每個加密函數(shù)和每個解密函數(shù)都應(yīng)當(dāng)能有效的被每個加密函數(shù)和每個解密函數(shù)都應(yīng)當(dāng)能有效的被計算（密碼的易用性）計算（密碼的易用性） 即使看到密文串即使看到密文串y，竊聽者竊聽者Oscar確定所用的密鑰確定所用的密鑰k或明文串或明文串x是計算上不可行的（安全性）是計算上不可行的（安全性） 已知密文串已知密文串y的情況下試圖計算密鑰的情況下試圖計算密鑰k或或x的過程的過程稱為密碼分析（稱為密碼分析（Cryptanalysi

5、s） 密碼分析包含基于算法性質(zhì)的分析和窮舉密鑰密碼分析包含基于算法性質(zhì)的分析和窮舉密鑰分析分析7第第2 2章章 古典密碼技古典密碼技術(shù)術(shù) 古典密碼的分類古典密碼的分類 代換密碼（代換密碼（Substitution） 置換密碼（置換密碼（Permutation） 代換密碼：將明文元素（字符、比特）代換密碼：將明文元素（字符、比特）映射成密文的元素映射成密文的元素 置換密碼：將明文元素的位置進行系統(tǒng)置換密碼：將明文元素的位置進行系統(tǒng)的置換的置換8代換密碼（替代密碼）代換密碼（替代密碼） 代換是古典密碼中用到的最基本的處理技巧之一；代換是古典密碼中用到的最基本的處理技巧之一；將明文字母表抽象的表示為

6、一個整數(shù)集將明文字母表抽象的表示為一個整數(shù)集Zq=0, 1, q-1。 代換密碼就是用代換密碼就是用密文位串代替明文位串密文位串代替明文位串 代換密碼是指先建立一個代換表，加密時將需要加代換密碼是指先建立一個代換表，加密時將需要加密的明文依次通過查表，替換為相應(yīng)的字符，明文密的明文依次通過查表，替換為相應(yīng)的字符，明文字符被逐個替換后，生成無任何意義的字符串，即字符被逐個替換后，生成無任何意義的字符串，即密文，代換密碼的密鑰就是其替換表；密文，代換密碼的密鑰就是其替換表； 根據(jù)密碼算法加解密時使用代換表多少的不同，代根據(jù)密碼算法加解密時使用代換表多少的不同，代換密碼又可分為換密碼又可分為單表代換

7、密碼和多表代換密碼單表代換密碼和多表代換密碼。 多表替代密碼的密碼算法加解密時使用多個替換表多表替代密碼的密碼算法加解密時使用多個替換表9單表代換密碼單表代換密碼 密碼算法加解密時使用一個固定的代換表；密碼算法加解密時使用一個固定的代換表；加密變加密變換過程就是將明文中的每一個字母替換為密文字母換過程就是將明文中的每一個字母替換為密文字母表的一個字母表的一個字母 Caesar密碼：密碼：26個英文字母與整數(shù)個英文字母與整數(shù)0, 1, , 25一一一對應(yīng)：一對應(yīng)： 加密變換加密變換: c=E(3,p)=(p + 3) (mod 26) 解密變換解密變換: p=D(3,c)=(c - 3) (mo

8、d 26) 將將Caesar密碼一般化，取任意的整數(shù)密碼一般化，取任意的整數(shù)k作為密鑰作為密鑰: 加密變換加密變換: c=E(k,p)=(p + k) (mod 26) 解密變換解密變換: p=D(k,c)=(c k) (mod 26)10一般單表代換密碼一般單表代換密碼 Caesar密碼密鑰數(shù)量過少；密碼密鑰數(shù)量過少； 一般單表替代密碼的原理是以一般單表替代密碼的原理是以26個英文字母集合上個英文字母集合上的一個置換的一個置換為密鑰構(gòu)造代換表，對明文消息中的每為密鑰構(gòu)造代換表，對明文消息中的每個字母依次進行變換。個字母依次進行變換。 例：設(shè)置換例：設(shè)置換的對應(yīng)關(guān)系如下：的對應(yīng)關(guān)系如下： a

9、b c d e f g h i j k l m n o p q r s t u v w x y z q w e r t y u i o p a s d f g h j k l z x c v b n m 試用單表替代密碼以試用單表替代密碼以為密鑰對明文消息為密鑰對明文消息message加密，然后寫出逆置換加密，然后寫出逆置換 ，并對密文解密。，并對密文解密。解：解：密文消息為：密文消息為： (m)(e)(s)(s)(a)(g)(e)=dtllqut11一般單表代換密碼一般單表代換密碼一般單表替代密碼算法特點：一般單表替代密碼算法特點：密鑰空間密鑰空間K很大，很大，|K|=26!=41026 ，

10、破譯者窮，破譯者窮舉搜索計算不可行，舉搜索計算不可行，1微秒試一個密鑰，遍歷全部微秒試一個密鑰，遍歷全部密鑰需要密鑰需要1013 年。年。移位密碼體制是替換密碼體制的一個特例，它僅含移位密碼體制是替換密碼體制的一個特例，它僅含26個置換做為密鑰空間。個置換做為密鑰空間。密鑰密鑰不便記憶，通常會采用不便記憶，通常會采用密鑰短語密碼：密鑰短語密碼：選用選用一個英文短語或單詞串作為密鑰，去掉其中重復(fù)的一個英文短語或單詞串作為密鑰，去掉其中重復(fù)的字母得到一個無重復(fù)字母的字符串，然后再將字母字母得到一個無重復(fù)字母的字符串，然后再將字母表中的其它字母依次寫于此字母串后，就可構(gòu)造出表中的其它字母依次寫于此字

11、母串后，就可構(gòu)造出一個字母替代表。一個字母替代表。 12多表代換密碼多表代換密碼 單表替代密碼表現(xiàn)出明文中單字母出現(xiàn)的頻單表替代密碼表現(xiàn)出明文中單字母出現(xiàn)的頻率分布與密文中相同率分布與密文中相同 多表代換密碼是以一系列（兩個以上）代換多表代換密碼是以一系列（兩個以上）代換表依次對明文消息的字母進行代換的加密方表依次對明文消息的字母進行代換的加密方法法 多表替代密碼使用從明文字母到密文字母的多表替代密碼使用從明文字母到密文字母的多個映射來隱藏單字母出現(xiàn)的頻率分布多個映射來隱藏單字母出現(xiàn)的頻率分布131. 希爾（希爾（Hill）密碼）密碼 Hill密碼算法的基本思想是將密碼算法的基本思想是將n個明

12、文字母通個明文字母通過線性變換，將它們轉(zhuǎn)換為過線性變換，將它們轉(zhuǎn)換為n個密文字母。解密個密文字母。解密只需做一次逆變換即可。只需做一次逆變換即可。 算法的密鑰算法的密鑰K=Z26上的上的n*n可逆矩陣可逆矩陣，明，明文文M與密文與密文C 均為均為n維向量，加密和解密變換分維向量，加密和解密變換分別為：別為： C=K*M(mod 26); M=K-1*C(mod 26) 其中，其中，K 1為為K在模在模26上的逆矩陣：上的逆矩陣：KK 1 =K1K=I (mod 26) 這里這里 I 為單位矩陣。為單位矩陣。 定理定理2.1：假設(shè)假設(shè)A= 是一個是一個Z26上的上的22矩陣，它的行列式：矩陣，它

13、的行列式： 是可是可逆的，那么：逆的，那么：多表代換密碼多表代換密碼1,11,22,12,2aaaa1,1 2,21,2 2,1detA a aa a2,21,2112,11,1(det )mod26aaAAaa14HillHill密碼密碼 K的逆矩陣為：的逆矩陣為：【例例2.5】設(shè)明文消息為設(shè)明文消息為good，試用，試用n2，密鑰，密鑰 的的Hill密碼對其進密碼對其進 行加密，然后再進行解密。行加密，然后再進行解密。解：對明文劃分：解：對明文劃分：(g，o) 和和 (o，d)，即，即(6, 14)和和(14, 3)。加。加密過程：密過程： 因此，因此，good的加密結(jié)果是的加密結(jié)果是wm

14、wl。顯然，明文不同位置的字。顯然，明文不同位置的字母母“o”加密成的密文字母不同。加密成的密文字母不同。111118787181mod 26373112311K11837K1122118617822(mod26)371411612cmwKcmm33441181417822(mod26)3736311cmwKcml15HillHill密碼密碼 因此，解密得到正確的明文因此，解密得到正確的明文“good”good”。 HillHill密碼特點：密碼特點：u可以較好地抑制自然語言的統(tǒng)計特性，不再有單可以較好地抑制自然語言的統(tǒng)計特性，不再有單字母替換的一一對應(yīng)關(guān)系，對抗字母替換的一一對應(yīng)關(guān)系，對抗“

15、惟密文攻擊惟密文攻擊”有較高安全強度。有較高安全強度。u密鑰空間較大，在忽略密鑰矩陣密鑰空間較大，在忽略密鑰矩陣K可逆限制條件可逆限制條件下，下，|K|=26nn u易受已知明文攻擊及選擇明文攻擊。易受已知明文攻擊及選擇明文攻擊。11221718223706(mod 26)23111263814mcgKmco334417182235214mod 262311116273mcoKmcd16多表代換密碼多表代換密碼2. 維吉尼亞密碼：維吉尼亞密碼：最古老而且最著名的多表代換密碼最古老而且最著名的多表代換密碼體制之一，與位移密碼體制相似，但體制之一，與位移密碼體制相似，但維吉尼亞密碼的維吉尼亞密碼的

16、密鑰是動態(tài)周期變化的密鑰是動態(tài)周期變化的。 該密碼體制有一個參數(shù)該密碼體制有一個參數(shù)n。在加解密時，按。在加解密時，按n個字個字母一組進行變換。母一組進行變換。加密變換定義如下：加密變換定義如下：設(shè)密鑰設(shè)密鑰 k=(k1,k2,kn), 明文明文m=(m1,m2,mn): e(k, m)=(c1,c2,cn), 其中其中ci=(mi + ki)(mod26)，i =1,2,n對密文對密文 c=(c1,c2,cn), 解密變換為：解密變換為： d(k, c)=(m1,m2,mn), 其中其中 mi=(ci ki)(mod26)，i =1,2,n17維吉尼亞密碼維吉尼亞密碼例：設(shè)密鑰例：設(shè)密鑰k

17、=cipher，明文消息，明文消息appliedcryptosystem，試用維吉尼亞密碼對，試用維吉尼亞密碼對其進行加密，然后再進行解密。其進行加密，然后再進行解密。解：由密鑰解：由密鑰k=cipher，得，得n=6，密鑰對應(yīng)的數(shù)，密鑰對應(yīng)的數(shù)字序列為字序列為 (2，8，15，7，4，17)。然后將明。然后將明文按每文按每6個字母進行分組，并轉(zhuǎn)換這些明文字母個字母進行分組，并轉(zhuǎn)換這些明文字母為相應(yīng)的數(shù)字，再用模為相應(yīng)的數(shù)字，再用模26加上對應(yīng)密鑰數(shù)字，加上對應(yīng)密鑰數(shù)字，其加密過程如表其加密過程如表2.3所示。所示。 表表2.3 密鑰為密鑰為cipher的維吉尼亞密碼加密過程的維吉尼亞密碼加密

18、過程 密文為：密文為：cxtsmvfkgftkqanzxvo。 解密使用相同的密鑰，但用模解密使用相同的密鑰，但用模26的減法代替的減法代替模模26加法，這里不再贅述。加法，這里不再贅述。18多表代換密碼多表代換密碼3一次一密密碼（一次一密密碼（One Time Pad） 若替代碼的密鑰是一個隨機且不重復(fù)的字符序列，這種密碼若替代碼的密鑰是一個隨機且不重復(fù)的字符序列，這種密碼則稱為一次一密密碼，因為它的密鑰只使用一次。則稱為一次一密密碼，因為它的密鑰只使用一次。 該密碼體制是美國電話電報公司的該密碼體制是美國電話電報公司的Gilbert Vernam在在1917年為電報通信設(shè)計的一種密碼，所以

19、又稱為年為電報通信設(shè)計的一種密碼，所以又稱為Vernam密碼。后來被陸軍情報軍官密碼。后來被陸軍情報軍官Joseph Mauborgne改進。改進。Vernam密碼在對明文加密前首先將明文編碼為（密碼在對明文加密前首先將明文編碼為（0，1）序）序列，然后再進行加密變換。列，然后再進行加密變換。 設(shè)設(shè)m=(m1 m2 m3 mn)為明文為明文,k=(k1 k2 k3 kn )為密鑰為密鑰,其中其中mi,ki (0,1), i1, 則加密和解密變換為，這里為模則加密和解密變換為，這里為模2加法（或異或運算）：加法（或異或運算）： c=(c1 c2 c3 cn) , 其中其中ci mi ki , i

20、1 m=(m1 m2 m3 mn) , 其中其中mi ci ki , i1, 19一次一密密碼一次一密密碼 由于每一密鑰序列都是等概率隨機產(chǎn)生的，敵由于每一密鑰序列都是等概率隨機產(chǎn)生的，敵手沒有任何信息用來對密文進行密碼分析。香手沒有任何信息用來對密文進行密碼分析。香農(nóng)從信息論的角度證明了這種密碼體制在理論農(nóng)從信息論的角度證明了這種密碼體制在理論上是不可破譯的。上是不可破譯的。 若敵手獲得了一個密文若敵手獲得了一個密文c=(c1 c2 c3 cn) 和對和對應(yīng)明文應(yīng)明文m=(m1m2 mn)時，就很容易得出時，就很容易得出密鑰密鑰 k=(k1k2 kn)，其中，其中ki ci mi ，i1。故

21、若重復(fù)使用密鑰，該密碼體制就很不。故若重復(fù)使用密鑰，該密碼體制就很不安全。安全。 Vernam密碼軟硬件實現(xiàn)非常簡單理論上是不密碼軟硬件實現(xiàn)非常簡單理論上是不可破譯的，然而在實際應(yīng)用中，卻受到很大的可破譯的，然而在實際應(yīng)用中，卻受到很大的限制：限制： 密鑰是真正的隨機序列；密鑰是真正的隨機序列； 密鑰長度大于等于明文長度；密鑰長度大于等于明文長度； 每個密鑰只用一次（一次一密）。每個密鑰只用一次（一次一密）。 這樣，分發(fā)和存儲這樣的隨機密鑰序列，并確這樣，分發(fā)和存儲這樣的隨機密鑰序列，并確保密鑰的安全都是很因難的；而如何生成真正保密鑰的安全都是很因難的；而如何生成真正的隨機序列也是一個現(xiàn)實問題

22、的隨機序列也是一個現(xiàn)實問題20第第2 2章章 古典密碼技古典密碼技術(shù)術(shù) 置換密碼又稱為換位密碼；置換密碼又稱為換位密碼；置換密碼通過改變明文消息各元素的相對位置，置換密碼通過改變明文消息各元素的相對位置，但明文消息元素本身的取值或內(nèi)容形式不變；但明文消息元素本身的取值或內(nèi)容形式不變；在在前面的代換密碼中，則可以認(rèn)為是保持明文的符前面的代換密碼中，則可以認(rèn)為是保持明文的符號順序，但是將它們用其它符號來替代；號順序，但是將它們用其它符號來替代；這種密碼是把明文中各字符的位置次序重新排列這種密碼是把明文中各字符的位置次序重新排列來得到密文的一種密碼體制。例如直接把明文順來得到密文的一種密碼體制。例如

23、直接把明文順序倒過來，然后排成固定長度的字母組作為密文序倒過來，然后排成固定長度的字母組作為密文就是一種置換密碼。就是一種置換密碼。2.2 置換密碼置換密碼 ( Permutation Cipher )21置換密碼置換密碼例：例：給定明文為給定明文為cryptography，試用密鑰，試用密鑰= (3 5 1 6 4 2)的置換密碼對其進行加密，然后再對密文的置換密碼對其進行加密，然后再對密文進行解密。進行解密。 解：解：密鑰長度是密鑰長度是6，所以按周期長度，所以按周期長度6對明文分組，對對明文分組，對每組字母用密鑰每組字母用密鑰 進行重排得到對應(yīng)的加密結(jié)果。進行重排得到對應(yīng)的加密結(jié)果。 明

24、文分組為：明文分組為：crypto|graphy，再利用置換密鑰，再利用置換密鑰進行加密變換，得：進行加密變換，得：E (crypto) = (ytcopr); E (graphy) = (ahgypr) 即密文消息為即密文消息為ytcoprahgypr。 顯然由加密置換可求出逆置換為顯然由加密置換可求出逆置換為(3 6 1 5 2 4)，根，根據(jù)密文和逆置換即可直接明文。據(jù)密文和逆置換即可直接明文。 22密碼分析（或攻擊密碼分析（或攻擊）的分類）的分類攻擊類型攻擊者擁有的資源惟密文攻擊密碼分析者取得一個或多個用同一密鑰加密的密文已知明文攻擊除要破譯的密文外，密碼分析者還取得了一些用同一密鑰加

25、密的明密文對選擇明文攻擊密碼分析者可取得他所選擇的任意明文所對應(yīng)的密文，這些明密文對和要破譯的密文是用同一密鑰加密的選擇密文攻擊密碼分析者可以取得他所選擇的任何密文所對應(yīng)的明文（要破譯的密文除外） Kerckhoff原則：算法細(xì)節(jié)公開，密鑰保密原則：算法細(xì)節(jié)公開，密鑰保密23古典密碼的分析古典密碼的分析 移位密碼、仿射密碼、維吉尼亞密碼、置換密碼等移位密碼、仿射密碼、維吉尼亞密碼、置換密碼等對己知明文攻擊都是非常脆弱的。對己知明文攻擊都是非常脆弱的。 使用惟密文攻擊，大多數(shù)古典密碼體制都容易被攻使用惟密文攻擊，大多數(shù)古典密碼體制都容易被攻破。因為算法破。因為算法不能很好隱藏明文消息的統(tǒng)汁特征。

26、不能很好隱藏明文消息的統(tǒng)汁特征。 2.2.1 單表替代密碼分析單表替代密碼分析 對于單表替代密碼，加法密碼和乘法密碼的密鑰對于單表替代密碼，加法密碼和乘法密碼的密鑰量比較小，可利用窮舉密鑰的方法進行破譯。仿射密量比較小，可利用窮舉密鑰的方法進行破譯。仿射密碼密鑰量也只有成百上千，古代密碼分析者企圖用窮碼密鑰量也只有成百上千，古代密碼分析者企圖用窮舉全部密鑰的方法破譯密碼可能會有一定困難，然而舉全部密鑰的方法破譯密碼可能會有一定困難，然而計算機出現(xiàn)后這就很容易了。計算機出現(xiàn)后這就很容易了。24單表密碼的分析單表密碼的分析 本質(zhì)上，密文字母表是明文字母表的一種排列。本質(zhì)上，密文字母表是明文字母表的

27、一種排列。但企圖使用計算機窮舉一切密鑰來破譯替代密碼計但企圖使用計算機窮舉一切密鑰來破譯替代密碼計算不可行的。算不可行的。 窮舉不是攻擊密碼的惟一方法，密碼分析者可利窮舉不是攻擊密碼的惟一方法，密碼分析者可利用語言的統(tǒng)計特性進行分析。用語言的統(tǒng)計特性進行分析。如果明文語言的這種如果明文語言的這種統(tǒng)計特性在明文中有所反映，密碼分析者便可通過統(tǒng)計特性在明文中有所反映，密碼分析者便可通過分析明文和密文的統(tǒng)計規(guī)律而破譯密碼。分析明文和密文的統(tǒng)計規(guī)律而破譯密碼。 通過對大量英文語言的研究可以發(fā)現(xiàn)，每個字母通過對大量英文語言的研究可以發(fā)現(xiàn)，每個字母出現(xiàn)的頻率不一樣，出現(xiàn)的頻率不一樣，e出現(xiàn)的頻率最高。如果

28、所統(tǒng)計出現(xiàn)的頻率最高。如果所統(tǒng)計的文獻足夠長，便可發(fā)現(xiàn)各字母出現(xiàn)的頻率比較穩(wěn)的文獻足夠長，便可發(fā)現(xiàn)各字母出現(xiàn)的頻率比較穩(wěn)定。如表定。如表2.4所示（表中字母出現(xiàn)頻率為字母出現(xiàn)次所示（表中字母出現(xiàn)頻率為字母出現(xiàn)次數(shù)除以文本字母總數(shù)）。數(shù)除以文本字母總數(shù)）。25密碼分析技術(shù)密碼分析技術(shù) 表表2.4 262.4 26個英文字母出現(xiàn)頻率統(tǒng)計表個英文字母出現(xiàn)頻率統(tǒng)計表 字母出現(xiàn)頻率字母出現(xiàn)頻率a0.0856n0.0707b0.0139o0.0797c0.0279p0.0199d0.0378q0.0012e0.1304r0.0677f0.0289s0.0607g0.0199t0.1045h0.0528u0

29、.0249i0.0627v0.0092j0.0013w0.0149k0.0042x0.0017l0.0339y0.0199m0.0249z0.000826單表代換密碼的分單表代換密碼的分析析 通過對通過對26個英文字母出現(xiàn)頻率的分析，可以有個英文字母出現(xiàn)頻率的分析，可以有以下結(jié)果：以下結(jié)果： （1）e出現(xiàn)的頻率最大，約為出現(xiàn)的頻率最大，約為0.13； （2）t，a，o，i，n，s，h，r出現(xiàn)頻率在出現(xiàn)頻率在0.060.1之間之間 （3）d，l出現(xiàn)的頻率在出現(xiàn)的頻率在0.04附近；附近； （4）c, u, m, w, f, g, y, p, b出現(xiàn)的頻率約在出現(xiàn)的頻率約在0.0150.029 （

30、5）v，k，j，x，q，z出現(xiàn)的頻率小于出現(xiàn)的頻率小于0.01。 在密碼分析中，除了考慮單字母統(tǒng)計特性外在密碼分析中，除了考慮單字母統(tǒng)計特性外，掌握雙字母、三字母的統(tǒng)計特性以及字母，掌握雙字母、三字母的統(tǒng)計特性以及字母之間的連綴關(guān)系等信息也是很有用的。之間的連綴關(guān)系等信息也是很有用的。 (6) 出現(xiàn)頻率最高的出現(xiàn)頻率最高的30個雙字母組合依次是個雙字母組合依次是： th he ineranreedon es st enattonthandou eang asortiisetit ar te se hiof27單表代換密碼的分單表代換密碼的分析析(7) 出現(xiàn)頻率最高的出現(xiàn)頻率最高的20個三字母組

31、合依次是：個三字母組合依次是： the ing and her ere ent tha nth was eth for dth hat she ion int hissth ers ver 特別的，特別的，the出現(xiàn)的頻率幾乎是出現(xiàn)的頻率幾乎是ing的的3倍，倍，這在密碼分析中很有用。此外，統(tǒng)計資料還這在密碼分析中很有用。此外，統(tǒng)計資料還表明：表明：英文單詞以英文單詞以e，s，d，t字母結(jié)尾的超字母結(jié)尾的超過一半。英文單詞以過一半。英文單詞以t，a，s，w為起始字母為起始字母的約占一半。的約占一半。 以上這些統(tǒng)計數(shù)據(jù)是通過非專業(yè)性文獻中的以上這些統(tǒng)計數(shù)據(jù)是通過非專業(yè)性文獻中的字母進行統(tǒng)計得到的

32、。對于密碼分析者來說字母進行統(tǒng)計得到的。對于密碼分析者來說，這些都是十分有用的信息。除此之外，密，這些都是十分有用的信息。除此之外，密碼分析者對明文相關(guān)知識的掌握對破譯密碼碼分析者對明文相關(guān)知識的掌握對破譯密碼也是十分重要的。也是十分重要的。 28單表代換密碼的分單表代換密碼的分析析字母和字母組的統(tǒng)計數(shù)據(jù)對于密碼分析者是十分重要字母和字母組的統(tǒng)計數(shù)據(jù)對于密碼分析者是十分重要的。因為它們可以提供有關(guān)密鑰的許多信息。的。因為它們可以提供有關(guān)密鑰的許多信息。對于字母對于字母e比其它字母的頻率都高得多，如果是單表比其它字母的頻率都高得多，如果是單表替代密碼，可以預(yù)計大多數(shù)密文都將包含一個頻率比替代密碼

33、，可以預(yù)計大多數(shù)密文都將包含一個頻率比其它字母都高的字母。其它字母都高的字母。當(dāng)出現(xiàn)這種情況時，猜測這個當(dāng)出現(xiàn)這種情況時，猜測這個字母所對應(yīng)的明文字母為字母所對應(yīng)的明文字母為e，進一步比較密文和明文，進一步比較密文和明文的各種統(tǒng)計數(shù)據(jù)及其分布，便可確定出密鑰，從而破的各種統(tǒng)計數(shù)據(jù)及其分布，便可確定出密鑰，從而破譯單表替代密碼。譯單表替代密碼?！纠吭O(shè)某一段明文經(jīng)仿射密碼加密后的密文如下，設(shè)某一段明文經(jīng)仿射密碼加密后的密文如下， FMXVEDKAPHFERBNDKRXRSREFMORUDSDKDVSHVUFEDKAPRKDLYEVLRHHRH 試分析出對應(yīng)明密文。試分析出對應(yīng)明密文。29單表代

34、換密碼的分單表代換密碼的分析析 又經(jīng)過統(tǒng)計，上邊的密文中，最高頻的英文字又經(jīng)過統(tǒng)計，上邊的密文中，最高頻的英文字母是：母是：R(8), D(7), E,H,K(5), F,S,V(4).假設(shè)：假設(shè)：1. R-e； D-t 錯錯 2. R-e； E-t 錯錯 3. R-e； K-t 可以可以 破譯單表替代密碼的大致過程是：破譯單表替代密碼的大致過程是： 1. 統(tǒng)計密文的各種統(tǒng)計特征，如果密文量比較多，統(tǒng)計密文的各種統(tǒng)計特征，如果密文量比較多，則完成這步后便可確定出大部分密文字母；則完成這步后便可確定出大部分密文字母； 2. 分析雙字母、三字母密文組，以區(qū)分元音和輔音分析雙字母、三字母密文組，以區(qū)

35、分元音和輔音字母；字母； 3. 分析字母較多的密文，在這一過程中大膽使用猜分析字母較多的密文，在這一過程中大膽使用猜測的方法，如果猜對一個或幾個詞，就會大大加快測的方法，如果猜對一個或幾個詞，就會大大加快破譯過程。破譯過程。30對對HillHill密碼的已知明密碼的已知明文分析文分析 Hill密碼能較好地抵抗字母頻率的統(tǒng)計分析，密碼能較好地抵抗字母頻率的統(tǒng)計分析，采用惟密文攻擊是較難攻破，但采用已知明采用惟密文攻擊是較難攻破，但采用已知明文攻擊就容易破譯。文攻擊就容易破譯。 假定密碼分析者知道加密分組長度假定密碼分析者知道加密分組長度n值，且有值，且有至少至少N(Nn)個不同的明文個不同的明文

36、/密文分組對密文分組對(M1,C1), , (M N,C N ) 滿足：滿足： C 1= K M1(mod26) ,., C N = K M N(mod26) 記為：記為：(C1 C2 C N )=(M1 M2 M N )K (mod26) 其中其中M I,C I(i=1,N)均為均為n維列向量，維列向量，K為為未知密鑰方陣。未知密鑰方陣。 利用利用n個已知的明文個已知的明文/密文分組對定義兩個密文分組對定義兩個nn方陣：方陣： M=(M1 Mn), C=(C1 Cn), 有方程有方程:C=K*M(mod26)若矩陣若矩陣M是可逆的，則能計算出是可逆的，則能計算出K=C*M1(mod26)，從而破譯該密碼體制。，從而破譯該密碼體制。若方陣若方陣M關(guān)于模關(guān)于模26不可逆，攻擊者可通過嘗不可逆，攻擊者可通過嘗試其它明文試其它明文/密文對來產(chǎn)生新的方陣密文對來產(chǎn)生新的方陣M ，直到，直到找到一個可逆的明文矩陣找到一個可逆的明文矩陣M就可破譯就可破譯Hill密碼密碼。31HillHill密碼的分析密碼的分析例：例：設(shè)明文設(shè)明文worker利用利用n=2的的Hill密碼加密，密文為密碼加密，密文為qihryb，求，求密鑰密鑰K 解：將明密文劃分為三組：解：將明密文劃分為三組：(w, o), (r, k), (e,