傳統(tǒng)密碼(二)教材

1

在此之前，我們所涉及的密碼都具有一個共同的特點：每個明文字母對應的密文字母是確定的，因此頻率分析對這些密碼體制的攻擊是有效的。這些密碼體制稱之為單表置換。2多表置換特點:以一系列(兩個以上)的置換表對明文 消息的字符進行置換加密。令ZN為明文字符表——置換序列明文字符序列密文字符序列3注:若f是非周期的無限序列，則相應的密碼稱之為非周期多表置換密碼，即對每個明文字符都采用不同的置換表，即一次一密密碼。這是一種在理論上唯一不可破的密碼，這種密碼完全隱蔽明文的特點，但密鑰長度與明文長度相同，難于廣泛應用。4周期多表置換密碼置換序列:明文序列：密文序列：52.有名的多表置換密碼有很多，如

Vigenere密碼、Beaufort密碼、Running-key密碼、Vernam密碼等等。注：1.當時，周期多表置換就退化為 單表置換。66.Vigenere密碼

Vigenere密碼是由法國密碼學家BlaisedeVigenere于1858年提出的一種密碼，它是一種以移位置換為基礎的周期置換密碼。7Vigenere密碼加密方法置換序列（密鑰）：明文序列：密文序列：其中8abcdefghijklm0123456789101112nopqrstuvwxyz13141516171819202122232425例：對明文m:datasecurity作Vigenere加密，密鑰k:best首先根據(jù)字母數(shù)字對將明文及密鑰化為數(shù)字串m=(3,0,19,0,18,4,2,20,17,8,19,24)k=(1,4,18,19)9對m用k加密m:301901842201781924k:141819141819141819c:441119198201318121117再對應字母數(shù)字對得密文c:441119198201318121117c:EELTTIUNSMLR10Vigenere密碼解密方法置換序列（密鑰）：明文序列：密文序列：其中11對多表置換密碼的攻擊簡單的單表置換密碼，如移位密碼極易破譯。僅統(tǒng)計標出最高頻度率字母再與明文字母表字母對應決定出移位量，就差不多可以得到正確解了。另外，單表置換密碼如移位密碼也很容易用窮舉法來搜索密鑰，因為它的密鑰量僅為N。12多表置換密碼的破譯要比單表置換密碼難得多。因為在單表置換下，字母的頻率、重復字母模式、字母結(jié)合方式等統(tǒng)計特性除字母名稱改變之外，都未發(fā)生變化，依靠這些不變的統(tǒng)計特性就能破譯單表置換密碼，而在多表置換下，原來明文中的這些特性通過多個表的平均作用被隱蔽了起來，因此簡單的頻率分析方法此時失效。13對Vigenere密碼的攻擊方法：Ⅰ.

求密鑰長Ⅱ.

求平移差Ⅲ.

恢復明文

下面以Vigenere密碼為例來說明對多表置換密碼的攻擊方法14Ⅰ.

求密鑰長1.

重合指數(shù)法(indexofcoincidence)隨機取字母排成兩列,對應位置上出現(xiàn)相同字母的概率為15任取兩段英文并列,在對應位置上出現(xiàn)相同字母的概率為其中為所對應的字母在英文中出現(xiàn)的概率abcdefg0.08560.01390.02790.03780.13040.02890.0199hijklmn0.05280.06270.00130.00420.03390.02490.0707opqrstu0.07970.01990.00120.06770.06070.10450.0249vwxyz0.00920.01490.00170.01990.000816設一段字母序列長為,有個, 個…，個，在兩個位置上出現(xiàn)相同字母的概率為，稱為重合指數(shù)：計算重合指數(shù)：A構成的字母對數(shù)目：B構成的字母對數(shù)目：Z構成的字母對數(shù)目：……………17所以這段文字中相同字母構成的字母對數(shù)目：因此這段文字中兩個位置上出現(xiàn)相同字母的概率：18下面確定密鑰的長度由Vigenere密碼產(chǎn)生的密文序列（n充分大）假設密鑰長度為l，將c分為l個子序列相應的明文19考察密文c中相同字母對的個數(shù)N，假定重合指數(shù)為IC，那么

現(xiàn)從密文c中任取兩字母，再次計算這兩字母相同的概率：(a)若這兩字母屬于同一個由于是由平移而得到的而的重合指數(shù)為0.0687的重合指數(shù)也為0.0687，即此時這兩字母相同的概率為0.068720(b)若這兩字母分別屬于不同的子序列則這兩字母是由某兩個字母隨機平移而來的隨機字母相同的概率為0.0385此時，這兩字母相同的概率為0.0385由(a)和(b)可得21又因而1.從密文c，可求得IC，進而由(*)式可求得l的估計值。注:2.由(*)式求出的l的估計值僅具有參考意義，因為密文c未必夠長。222.

卡西斯基(Kasiski)

實驗法

Kasiski實驗法是由普魯士軍官Kasiski在1863年提出的一種重碼分析法?；驹恚喝粲媒o定的d個密鑰表周期地對明文字母加密，則當明文中有兩個相同字母在明文序列中間隔的字母數(shù)為d的倍數(shù)時，這兩個明文字母對應的密文字母必相同。反過來，若密文中出現(xiàn)兩個相同的字母，它們所對應的明文字母未必相同，但相同的可能性很大。23

因此，如果我們將密文中相同字母找出來，并找出它們相隔間字母數(shù)的最大公因子，就可能得到關于密鑰長度d的信息。24卡西斯基(Kasiski)

實驗法步驟：(ⅰ)若密文中相鄰兩字母、三字母……超過一次，則記下它們的位置，并將位置差進行因數(shù)分析；(ⅱ)統(tǒng)計各因子出現(xiàn)的次數(shù)，在次數(shù)較多者中，取一個作為猜測的密鑰長l；分別求他們的IC，若各組的IC值接近0.0687，則可接受密鑰長為l。(ⅲ)

將分為l個子序列，對25Ⅱ.

求平移差——確定密鑰字設第i組有

個字符，其中有個A，

個B…，且設第j組有

個字符，其中有個A，

個B…，且26這兩行的重合指數(shù)：27將第i

行的每一元素作的運算，，求使得IC達到最大值的將第i

行與第j

行配對：上式中和是常量，即只需求28例：見《計算機密碼學》p20(i,j)(1,2)(1,3)(1,4)(1,5)(2,3)k*9121623(i,j)(2,4)(2,5)(3,4)(3,5)(4,5)k*71941612k5-k4=12k5-k3=16k4-k3=4k5-k2=19k4-k2=7k3-k2=3k5-k1=2k4-k1=16k3-k1=12k2-k1=9即：29求出密鑰字的相對位移差為0,9,12,16,2用窮舉法找出可能的密鑰0,9,12,16,21,10,13,17,32,11,14,18,43,12,15,19,54,13,16,20,65,14,17,21,76,15,18,22,87,16,19,23,98,17,20,24,109,18,21,25,1110,19,22,0,1211,20,23,1,1312,21,24,2,1413,22,25,3,1514,23,0,4,1615,24,1,5,1716,25,2,6,1817,0,3,7,1918,1,4,8,2019,2,5,9,2120,3,6,10,2221,4,7,11,2322,5,8,12,2423,6,9,13,2524,7,10,14,025,8,11,15,130AJMQCBKNRDCLOSEDMPTEENQUCFORVHGPSWIHQTXJIRUYKJSVZLKTWAMLUXBNMVYCONWZDPOXAEQPYBFRQZCGSRADHTSBEIUTHKOAUDGKWVEHLXWFIMYXGJNZYHKOAZILPBabcdefghijklm0123456789101112nopqrstuvwxyz1314151617181920212223242531

前面我們介紹的密碼都是以單個字母作為置換對象的，下面我們介紹一種多字母置換密碼，即每次對多個字母進行置換。7.Hill密碼

Hill密碼的基本思想是將l個明文字母通過線性變換，將它們轉(zhuǎn)換成l個密文字母。我們將明文與密文表示成向量，密鑰表示成矩陣。32記加密算法：顯然，若K為可逆陣，那么c與m一一對應。解密算法：33例：在Z26中，對明文july用Hill密碼加密，其中明文、密文長度密鑰解：將明文july分組為ju,

ly，并根據(jù)字母數(shù)字對將ju,ly轉(zhuǎn)換成數(shù)字向量abcdefghijklm0123456789101112nopqrstuvwxyz1314151617181920212223242534計算因此密文為：ZMBT35其中明文、密文長度密鑰例：上例中，若已知密文為ZMBT，試解密解：將密文ZMBT分組并轉(zhuǎn)換為數(shù)字向量36在Z26中求37計算因此明文為：july38

已有事實表明，用唯密文攻擊法分析Hill密碼是比較困難的，分析Hill密碼多用已知明文攻擊法。39例：已知Hill密碼的3個明文ab,bc,de對應的密文是BC,EF,KL