第3講-古典密碼的統(tǒng)計分

古典密碼的統(tǒng)計分析

鄭洪英

zhenghongy@上次課內(nèi)容回顧幾個典型的古典密碼體制卡撒密碼維吉尼亞密碼維福特密碼單表古典密碼的統(tǒng)計分析原理：明文的統(tǒng)計規(guī)律在密文中能夠反映出來，故信息泄露大。多表古典密碼的統(tǒng)計分析原理：密鑰相同時，相同的明文對應(yīng)相同的密文。明文的統(tǒng)計規(guī)律26個英文字母：e

12%t---a---o---i---n---s---h---r

6%--9%d---l

4%c---u---m---w---f---g---y---p---b

1.5%--2.8%v—k---j---x---q---z

<1%出現(xiàn)頻率最高的30個雙字母（按頻率從大到小）：thheineranreedonesstenattonthandoueangasortiisetitartesehiof出現(xiàn)頻率最高的20個三字母（按頻率從大到?。簍heingandherereentthanthwasethfordthhatsheioninthissthersver漢字中單音節(jié)出現(xiàn)頻率最常用，出現(xiàn)頻率在百分之一以上的有14個音節(jié)，它們是：deshiyibuyouzhilejizhewoyenlitadao的是一不有之了機這我們里他到次常用音節(jié)有33個，它們是：zhongziguoshanggemenheweiyedagongjianjiuxiangzhulaishengdizainixiaokeyaowuyujiejinchanzuojiaxianquanshuo從三億漢字的母體材料中，抽樣二千五百萬字進行雙音節(jié)詞詞頻統(tǒng)計，結(jié)果是：我們?nèi)f次以上可以他們二萬次以上頻率在一萬次以上的雙音節(jié)詞有33個：進行沒有工作人民生產(chǎn)這個發(fā)展就是問題國家中國這樣革命自己不能由于這些所以因此作用一般什么如果情況必須方法因為主要要求社會漢字中雙音節(jié)詞出現(xiàn)頻率移位密碼分析給定加密的消息：PHHWPHDIWHUWKHWRJDSDUWB由于（1）加解密算法已知；（2）可能嘗試的密鑰只有26個通過強力攻擊得到明文：Meetmeafterthetogaparty.移位密碼很容易受到唯密文攻擊仿射密碼分析加密函數(shù)

c=Ek(m)=(k1+k2m)modq

要求有唯一解的充要條件是gcd(k2,q)=1當(dāng)q=26時，k2的選擇有12中：1，3，5，7，9，11，15，17，19，21，23，25因此，可能的密鑰是26*12-1=311(去掉k1=0并且k2=1這種情況)仿射密碼分析例：利用仿射密碼獲得如下密文：FMXVEDKAPHFERBNDKRXRSREFMORUDSDKDVSHVUFEDKAPRKDLYEVLRHHRH仿射密碼分析最大頻數(shù)的密文字母是：R(8次)，D(7次），E、H、K（各5次），S、F、V(各4次）猜想R是e的加密，D是t的加密Ek(4)=17,Ek(19)=3Ek(m)=am+b4a+b=1719a+b=3唯一解a=6,b=19(不合法密鑰，因為gcd(6,26）=2)仿射密碼分析再猜想R是e的加密，E是t的加密Ek(4)=17,Ek(19)=4,則a=13

再猜想：R是e的加密，H是t的加密,則a=8繼續(xù)猜想：R是e的加密，K是t的加密,這樣可得a=3,b=5.這是一個合法的密鑰。下一步就是驗證這個合法密鑰的正確性，解密Dk(m)=9y-19,解密后的明文：Algorithmsarequitegeneraldefinitionsofarithmeticprocesses至此，我們得到了正確的密鑰。Hill密碼的已知明文分析

例明文friday是用Hill密碼加密的，m=2，得到密文POCFKU。則有，，。從最初兩個明文對，我們得到矩陣方程，容易計算，所以?？捎玫谌齻€明密文對驗證。

單表古典密碼的分析通常，攻擊步驟如下：（1）做出密文中字母的頻次統(tǒng)計表，算出密文字母出現(xiàn)的概率，并與明文字母集的概率分布進行對照，區(qū)分高概率字母和低概率字母。（還不能具體識別它確切地對應(yīng)哪個明文字母）（2）利用上述信息，結(jié)合自然語言的雙字母和三字母的統(tǒng)計特性，推斷出一些可能的明密文對應(yīng)關(guān)系。（3）結(jié)合自然語言的文字規(guī)律進一步推斷出一些新的明密對應(yīng)關(guān)系。一些字母在詞頭頻繁出現(xiàn)(TASOICWPBF)，一些字母在詞尾經(jīng)常出現(xiàn)（ESDNTRYFOL)。輔音和元音的結(jié)合規(guī)律（雙字母、三字母和四字母的密文組合，這個的組合中一般必含有一個元音）利用模式字或模式短語，如果猜出一個或幾個詞一個短語，就會大大加速攻擊速度，這常常是攻擊的關(guān)鍵。

多表古典密碼的統(tǒng)計分析步驟1：首先確定密鑰的長度：利用Kasiski測試法和重合指數(shù)法(indexofcoincidence)步驟2：確定具體的密鑰內(nèi)容

尋找密文中相同的片段對，計算每對相同密文片段對之間的距離，不妨記為d1,d2,…,di，若令密鑰字的長度為m，則m=gcd(d1,d2,…,di)。定理1若兩個相同的明文片段之間的距離是密鑰長度的倍數(shù)，則這兩個明文段對應(yīng)的密文一定相同。反之則不然。若密文中出現(xiàn)兩個相同的密文段(密文段的長度m>2)，則它們對應(yīng)的明文段極有可能是相同的，當(dāng)然也可能不同。但是相同的概率很大。Kasiski測試法：Kasiski于1863年提出進一步判斷密鑰字的長度是否為

m=gcd(d1,d2,…,di).

定義1設(shè)X=x1x2…xn是一個長度為n的英文字母串，則x中任意選取兩個字母相同的概率定義為重合指數(shù)，用表示。重合指數(shù)法(indexofcoincidence)：Wolfefriendman于1920年提出定理1設(shè)英文字母A，B,…，Z在X中出現(xiàn)的次數(shù)分別為：f0,f1,…,f25則從X中任意選取兩個字母相同的概率為已知每個英文字母出現(xiàn)的期望概率，分別記為p0,p1,…,p25，那么X中兩個元素相同的概率為：

=0.065

對于英文的一個隨機字母串，每個英文字母出現(xiàn)的期望概率均為1/26，則在X中任意選取兩個元素相同的概率為=0.038.根據(jù)Kasiski測試法得到的m，可以將密文Y按照下列形式排列：表1將Y排列成m行n/m列的形式，

若m確實是密鑰的長度，則上述矩陣中的每一行都是由同一個密鑰ki加密得到，這說明每一行即是一個單表代替，這時計算每一行的重合指數(shù)，應(yīng)該更接近0.065；若m不是密鑰的長度，則上述矩陣中的每一行不是由同一個密鑰ki加密得到，這說明每一行是一個等概隨機的字母串（對密文的要求），這時計算每一行的重合指數(shù)，應(yīng)該更接近0.038。設(shè)f0,f1,…,f25分別表示串yi中英文字母A，B,…，Z出現(xiàn)的次數(shù)，令n’=n/m表示串yi的長度，則26個英文字母在yi的概率分布為：考慮到Vigenere密碼子串yi是有對應(yīng)的明文子集中的字母移動Ki個位置所得，因此，移動后的概率分布為：確定密鑰的具體內(nèi)容

定義設(shè)數(shù)值如果g=ki，類似與重合指數(shù)法，應(yīng)該有否則，Mg應(yīng)該小于0.065應(yīng)用舉例

明文：wearediscoveredsaveyour