第2章3-密碼分析

密碼分析密碼學(xué)包括密碼編碼學(xué)和密碼分析學(xué)兩部分。密碼編碼學(xué)研究如何構(gòu)造一個符合規(guī)定安全要求的密碼系統(tǒng)，即如何設(shè)計相應(yīng)的加密和解密算法、密鑰和安全協(xié)議，使得密碼系統(tǒng)能夠達到所需要的安全性。

密碼分析學(xué)是研究在不知道解密密鑰和密碼體制的情況下如何恢復(fù)明文的科學(xué)。這兩部分既對立又統(tǒng)一，正是這兩者的對立和統(tǒng)一推動了密碼學(xué)的發(fā)展。密碼分析目標(biāo)密碼分析的目的是尋找密碼算法的弱點，并根據(jù)這些弱點對密碼進行破譯。攻擊密碼的目標(biāo)有：1.完全攻破（TotalBreak）

發(fā)現(xiàn)密碼系統(tǒng)所用的密鑰，因此，所有密文均可破譯，并且攻擊者可以按照自己的需要產(chǎn)生假冒的密文；2.全局演繹（GlobalDeduction）

攻擊者找到了解密算法的一個等價算法，無須密鑰便可進行解密；3.局部演繹（LocalDeduction）發(fā)現(xiàn)一個或多個密文對應(yīng)的明文，這將為發(fā)現(xiàn)實際使用的密鑰提供線索；密碼分析目標(biāo)4.信息演繹（InformationDeduction）發(fā)現(xiàn)與實際使用的密鑰或明文有關(guān)的信息，例如密鑰的一部分，或明文的格式等。這些信息將有助于進行密鑰分析。

5.算法辨別（algorithmdistinguishing）發(fā)現(xiàn)正在使用的密碼的輸出與隨機置換的輸出不同，它與密碼偵察（cipherdetection）有密切關(guān)系。在密碼偵察中可以區(qū)分出正在使用的是哪一種密碼算法，這通常是進行其他密碼分析的基礎(chǔ)。密碼分析的手段根據(jù)攻擊者掌握的密碼系統(tǒng)的信息，可以將對密碼系統(tǒng)的攻擊手段分成以下幾種類型：1.唯密文攻擊（CiphertextOnlyAttack）

攻擊者只有一些用同一算法和同一密鑰加密的密文，密碼分析的任務(wù)是從這些密文盡可能多地恢復(fù)出明文，或者推導(dǎo)出密鑰，即：已知：c1=Ek(m1)，c2=Ek(m2)，…，ci=Ek(mi)求：m1，m2，…，mi或k。2.已知明文攻擊（KnownPlaintextAttack）

攻擊者不僅能得到一些密文，而且能得到這些密文對應(yīng)的明文。密碼分析的任務(wù)是由此推導(dǎo)出密鑰，或一個能解密任何新消息的算法，即：已知：m1，c1=Ek(m1)，m2，c2=Ek(m2),…,mi，ci=Ek(mi)；求：k或一個能由ci+1=Ek(mi+1)推出mi+1的算法。密碼分析的手段3.選擇明文攻擊（ChosenPlaintextAttack）攻擊者不僅能得到一些密文和對應(yīng)的明文，而且能選擇用于加密的明文。這種攻擊比已知明文攻擊更有力，因為攻擊者可以選擇一些特殊的明文進行加密，這些明文可以暴露出更多與密鑰有關(guān)的信息。在這種條件下，密碼分析的任務(wù)是推導(dǎo)出用于加密這些信息所用的密鑰，或一個能將加密的新消息進行解密的算法，即：

已知：m1，c1=Ek(m1)，m2，c2=Ek(m2),…,mi，ci=Ek(mi)；其中，m1，m2，…，mi由攻擊者選擇；求：k或一個能由c推出m的算法D，使m=D(c)。

密碼分析的手段4.選擇密文攻擊（ChosenCiphertextAttack)

攻擊者可以選擇不同的密文來解密，并能得到解密后的明文。例如，攻擊者可以訪問一臺該密碼系統(tǒng)的自動解密裝置，產(chǎn)生任何密文對應(yīng)的明文。攻擊者的任務(wù)是推導(dǎo)出密鑰，即：已知：c1，m1=Dk(c1)，c2，m2=Dk(c2)，

…，ci，mi=Dk(ci)；其中，c1，c2，…，ci由攻擊者選擇；求：k。密碼分析的手段5.自適應(yīng)選擇明文攻擊（AdaptiveChosenPlaintextAttack）這是選擇明文攻擊的特殊情況，密碼分析者不僅能選擇要加密的明文，而且還可以根據(jù)加密的結(jié)果對所選擇的明文進行修正。即，攻擊者選擇明文m1并得到相應(yīng)密文c1，然后根據(jù)c1選擇明文m2并得到相應(yīng)密文c2，…，根據(jù)cn-1選擇mn并得到相應(yīng)密文cn。這樣交互得到的明文m1,m2,…,mn及其相應(yīng)密文c1,c2,…,cn就是自適應(yīng)選擇明文，利用自適應(yīng)選擇明文對密碼進行攻擊就叫做自適應(yīng)選擇明文攻擊。

密碼分析的方法

1.窮舉法（ExhaustiveAttackMethod）

窮舉法又稱作強力攻擊(Brute-forceattack)，是對截獲的密文依次用各種可能的密鑰去解密，直到得到有意義的明文為止。窮舉攻擊所花費的時間等于嘗試次數(shù)乘以一次解密所需的時間。設(shè)可能的密鑰數(shù)為n，嘗試一個密鑰去解密需要的時間為t，則窮舉法平均需要(n×t)/2的時間攻破一個密碼系統(tǒng)。因此，只要有足夠多的計算資源（計算時間和存儲容量），理論上窮舉法總是可以成功的。但實際上，如果破譯的代價大于可能獲得的利益，或破譯的時間超過該信息的有用期限，那么這樣的破譯是毫無意義的。因此，可以通過增大密鑰量或加大加密算法的復(fù)雜性來對抗窮舉攻擊。密碼分析的方法

2.分析法（AnalyticalAttackMethod）分析法分為確定性分析法和統(tǒng)計性分析法兩種。確定性分析法是通過數(shù)學(xué)求解的方法，用數(shù)學(xué)關(guān)系式表示出所求的未知量（如密鑰）與已知量（如密文或明文/密文對）的關(guān)系。已知量和未知量的關(guān)系由加密和解密算法決定，因此為了對抗確定性分析法的攻擊，應(yīng)選用具有堅實數(shù)學(xué)基礎(chǔ)和足夠復(fù)雜度的加解密算法。密碼分析的方法

2.分析法（AnalyticalAttackMethod）

統(tǒng)計分析法是利用明文的已知統(tǒng)計特性來進行破譯的方法。密碼分析者對截獲的密文進行統(tǒng)計分析，總結(jié)出它的統(tǒng)計規(guī)律，并與明文的統(tǒng)計規(guī)律進行對照比較，從中得到明文和密文的對應(yīng)關(guān)系或變換信息。因此，為了對抗統(tǒng)計分析法的攻擊，應(yīng)設(shè)法使明文的統(tǒng)計特性不帶入密文，這樣密文中就沒有明文的痕跡，從而不可能使用統(tǒng)計攻擊方法。

古典密碼分析系統(tǒng)的安全性和Kerckhoff

假設(shè)

安全性有兩種標(biāo)準(zhǔn)：一種稱為理論安全性或無條件安全性，另一種稱為實際安全性。若具有無限的計算資源（例如時間、空間、設(shè)備和資金等）也無法破譯某密碼系統(tǒng)，則稱該系統(tǒng)是理論上安全的。

例如，一次一密密碼是理論上安全的。因為已經(jīng)證明，無論具有多少資源一次一密密碼都是不可破譯的。實際安全性又分為計算安全性和可證明安全性兩種。如果破譯一個系統(tǒng)在原理上是可能的，但使用所有已知的算法和現(xiàn)有的計算工具不可能在適當(dāng)?shù)臅r間內(nèi)完成破譯所要求的計算量，則稱該系統(tǒng)是計算上安全的；如果可以證明破譯某系統(tǒng)的難度與解某數(shù)學(xué)難題等價，則稱該系統(tǒng)是可證明安全的。

Kerckhoff基本條件1883年Kerckhoff提出系統(tǒng)應(yīng)滿足的6條基本條件：(1)系統(tǒng)即使不是理論上不可破的，至少也應(yīng)該是實際上不可破的；(2)系統(tǒng)的保密性不依賴于對加密體制或算法的保密，而僅僅依賴于密鑰的保密；(3)密鑰應(yīng)便于記憶、易于修改；(4)密文可用電報傳送；(5)加密裝置小巧、可由單人操作；(6)掌握系統(tǒng)既不需要了解繁復(fù)的規(guī)則，也不要求超人的智慧。這些規(guī)則是一個多世紀(jì)前提出的，但其中大部分原則至今仍然有用。特別是第二條是當(dāng)今密碼系統(tǒng)安全性的前提，通常稱為Kerckhoff假設(shè)。Kerckhoff假設(shè)的重要性如果密碼系統(tǒng)的安全性依賴于加密算法的保密，那么就很難開發(fā)通用的加密硬件和軟件模塊，不利于加密算法的優(yōu)化、標(biāo)準(zhǔn)化和推廣；

如果密碼系統(tǒng)的安全性依賴于攻擊者不知道系統(tǒng)的密碼體制，那么這種假設(shè)早晚會失敗。因為密碼分析者會不斷地對你的系統(tǒng)進行攻擊、反匯編你的代碼、逆向設(shè)計你的算法等等，破譯算法只是時間和金錢問題，密碼發(fā)展史上這樣的例子屢見不鮮；(3)如果系統(tǒng)的安全取決于算法的保密，那么一旦有機構(gòu)退出所建立的保密系統(tǒng)（這種情況總是會發(fā)生的），整個系統(tǒng)就徹底崩潰了。這時必須更換整個系統(tǒng)的軟件和硬件，重新建立新的安全保密體制，不但增加了不必要的開銷，而且使人對系統(tǒng)安全性的基礎(chǔ)缺乏信心。反之，如果系統(tǒng)的安全僅取決于密鑰的保密，那么在這種情況下只需更換密鑰，而不需要修改系統(tǒng)的任何硬件和軟件；實踐證明，最好的算法是那些已經(jīng)公開、并經(jīng)過世界上最好的密碼分析家們多年攻擊仍無法攻破的算法。因此，在進行密碼分析時，總是假定Kerckhoff假設(shè)成立，即密碼算法是公開的，所謂破譯密碼就是破譯它的密文或求出它的密鑰。單表替代密碼的分析

在單表替代密碼中，各種密鑰字的使用都是可能的，因此，26種不同排列的字符變換表作為密表都是可能的。

26！～4×1026即使使用計算機用窮舉法來破譯單表替代密碼也是不可能的。但事實上，有許多方法可以不必窮盡各種可能的密鑰即可破譯單表替代密碼。猜測法在單表替代密碼中，明文字母與密文字母一一對應(yīng)，因此，變換后詞的長度不會變化，詞中的重復(fù)模式也不會發(fā)生改變。這樣一來，短詞、有重復(fù)模式的單詞、以及常用的起始和結(jié)尾字母都會給出字符替代的線索。例如，英語中字母少的詞是相當(dāng)少的：二個字母組成的常用單詞只有am,is,to,be,we,of等；三個字母組成的常用單詞也只有and,you,she，any等。一種猜測方法就是在密文相應(yīng)的地方用已知的少字母的詞來替代，然后試圖在密文其它地方進行相同的替代。另一種常用的猜測方法是查看密文中的重復(fù)模式，具有某些重復(fù)模式的詞是很少的，一旦發(fā)現(xiàn)這種模式，將使得猜測的范圍大為縮小。最后，常見的詞的起始和結(jié)尾字母也給猜測提供很多線索。用猜測法破譯下面的密文消息WKLVPHVVDJHLVQRWKDUGWREUHDN具有xyy模式的最普通的詞是“see”和“too”，其它可能性較小的是“add”，“odd”，和“off”。若WRR是see，那么密文中的另一個詞WR就是se。因為不存在se這個詞，所以這種猜測不正確。但若WRR是too，那么WR就是to，這看來十分合理。于是用t替代W，o替代R。WRRWR用猜測法破譯下面的密文消息WKLVPHVVDJHLVQRWWRRKDUGWREUHDNt--------------ottoo----to-----

“-ot”，它可能是“cot”，“dot”，“got”，“hot”,“l(fā)ot”,“not”,“pot”,“rot”或“tot”。聯(lián)系到它后面的一個單詞是“too”，理想的選擇應(yīng)該是“not”，于是用n替代Q。這一替代并沒有給出更多的線索，因為密文中Q只出現(xiàn)了一次。WKLVPHVVDJHLVQRWWRRKDUGWREUHDNt-------------nottoo----to-----

用猜測法破譯下面的密文消息WKLVPHVVDJHLVQRWWRRKDUGWREUHDNt-------------nottoo----to-----

短詞“LV”，它也是“WKLV”這個詞的末尾?？梢杂米鲉卧~，又可以是一般詞的末尾的兩個字母最可能的是“so”,”is”,”in”等。so不可能，因為“t-so”這種形式不象是什么詞。由于前面假設(shè)Q是n，所以“in”也被排除。于是在所有的地方都用“is”替代“LV”，得到：WKLVPHVVDJHLVQRWWRRKDUGWREUHDNt-is-------isnottoo----to-----

用猜測法破譯下面的密文消息WKLVPHVVDJHLVQRWWRRKDUGWREUHDNt-is-------isnottoo----to-----

密文字母正好距離其明文字母三個位置！該密碼系統(tǒng)可能是k=3的凱撒密碼。推理得明文為：thismessageisnottoohardtobreak（“該消息不難破譯”）這是一個有意義的英語句子，可以認(rèn)為這就是該密文所代表的明文。因此，密碼已被破譯。這里描述的密碼分析是特設(shè)的，用的是基于猜測的演繹法，而不是固定的原理和規(guī)則，但這種基于猜測的演繹法也可以用于其它密文的破譯。如果預(yù)先建立一個常用短詞、詞頭、詞尾和特殊模式的表，并用計算機進行各種匹配，則可以大大提高破譯的速度。單表古典密碼的統(tǒng)計分析原理：明文的統(tǒng)計規(guī)律在密文中能夠反映出來，故信息泄露大。多表古典密碼的統(tǒng)計分析原理：密鑰相同時，相同的明文對應(yīng)相同的密文。統(tǒ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%明文的統(tǒng)計規(guī)律

雙字母集的統(tǒng)計特性頻率高的前30個雙字母組，按其出現(xiàn)頻率的高低順序排列如下：

thheineranreedones

stenattonthand

oueangasortiisetitar

tesehiof明文的統(tǒng)計規(guī)律

三字母集的統(tǒng)計特性。

頻率高的前20個三字母組，按其出現(xiàn)頻率高低順序排列如下：

theingandherereent

thanthwasethfordthhatsheioninthissth

ers

ver

明文的統(tǒng)計規(guī)律

高維字母集的統(tǒng)計特性。有超過50%的英語單詞以e,s,d,t

為結(jié)尾字母；有約50%的單詞以t,a,s,w

為起始字母。對于單表替代密碼，由于明文字母和密文字母一一對應(yīng)，因此，利用自然語言中的字母頻率特征，將密文中和自然語言中頻率相近的字符對應(yīng)起來就有可能打開破譯密碼的缺口。字符出現(xiàn)的頻率越不均勻，密文的保密性就越低。

漢字中單音節(jié)出現(xiàn)頻率最常用，出現(xiàn)頻率在百分之一以上的有14個音節(jié)，它們是：deshiyi

buyouzhileji

zhe

woyenli

ta

dao的是一不有之了機這我們里他到次常用音節(jié)有33個，它們是：zhong

zi

guo

shang

gemenheweiyedagongjian

jiu

xiang

zhu

lai

sheng

di

zai

ni

xiao

ke

yao

wu

yu

jie

jin

chan

zuo

jia

xian

quan

shuo

從三億漢字的母體材料中，抽樣二千五百萬字進行雙音節(jié)詞詞頻統(tǒng)計，結(jié)果是：頻率在一萬次以上的雙音節(jié)詞有33個：我們?nèi)f次以上可以他們二萬次以上進行沒有工作人民生產(chǎn)這個發(fā)展就是問題國家中國這樣革命自己不能由于這些所以因此作用一般什么如果情況必須方法因為主要要求社會漢字中雙音節(jié)詞出現(xiàn)頻率代換密碼分析舉例頻度分析W->e模式分析X->tB->h猜猜猜tS->?t_->?猜猜猜猜猜猜猜猜猜利用英語單字母頻率表

破譯密文：HQFUBSWLRQLVDPHDQVRIDWWDLQLQJVHFXUHFRPSXWDWLRQRYHULQVHFXUHFKDQQHOVEBXVLQJHQFUBSWLRQZHGLVJXLVHWKHPHVVDJHVRWKDWHYHGLIWKHWNDQVPLVVLRQLVGLYHUWHGHKHPHVVDJHZLOOQRWEHUHYHDOHG可以認(rèn)定這種加密用的是k=3的凱撒密碼。按此推測可得明文為：encryptionisameansofattainingsecurecomputationoverinsecurechannelsbyusingencryptionwedisguisethemessagesothatevenifthetransmissionisdivertedthemessagewillnotberevealed有意義的明文消息，因此，猜測是正確的。

多表古典密碼的統(tǒng)計分析步驟1：首先確定密鑰的長度：利用Kasiski測試法和重合指數(shù)法(indexofcoincidence)步驟2：確定具體的密鑰內(nèi)容：交互重合指數(shù)法卡西斯基法的基本思想是：若明文消息用n個密表循環(huán)加密，那么兩個相同的字母組合在明文序列中間隔的字母數(shù)為n的倍數(shù)時，這兩個明文字母組對應(yīng)的密文字母組必然相同。反之，密文中兩個相同的字母組對應(yīng)的明文字母組不一定相同，只有2個字符的密文字母組的重復(fù)可能是偶然的，但字母組的字符數(shù)超過2個時，它們對應(yīng)的明文相同可以說是肯定無疑的。

Kasiski測試法：Kasiski（卡西斯基法

）于1863年提出在英語中，詞尾-th、-ing、-ion、-tion、-ation；詞頭im-、in-、un-、re-；模式-eek-、-oot-、-our-以及象of、and、to、with、are等詞經(jīng)常不成比例的頻繁出現(xiàn)，所以在密文中重復(fù)的字母組是容易找到的。如果把密文中重復(fù)的字母組找出來，分析相同字母組之間的字符數(shù)，求出它們的公因子，就有可能提取多表替代密碼所用的密表數(shù)（密鑰長度）的信息。

Kasiski測試法尋找密文中相同的片段對，計算每對相同密文片段對之間的距離，不妨記為d1,d2,…,di，若令密鑰字的長度為m，則m=gcd(d1,d2,…,di)。定理1若兩個相同的明文片段之間的距離是密鑰長度的倍數(shù)，則這兩個明文段對應(yīng)的密文一定相同。反之則不然。若密文中出現(xiàn)兩個相同的密文段(密文段的長度m>2)，則它們對應(yīng)的明文（及密鑰）將以很大的概率相同。Kasiski測試法設(shè)下列密文是用Vigenere密碼加密得到的，求加密的密表數(shù)：CHREEVOAHMAERATBIAXXWTNXBEEOPHBSBQMQEQERBWRVXUOAKXAOSXXWEAHBWGJMMQMNKGRFVGXWTRZXWIAKLXFPSKAUTEMNDCMGTSXMXBTUIADNGMGPSRELXNJELXVRVPRTULHDNQWTWDTYGBPHXTFALJHASVBFXNGLLCHRZBWELEKMSJIKNBHWRJGNMGJSGLXFEYPHAGNRBIEQJTAMRVLCRREMNDGLXRRIMGNSNRWCHRQHAEYEVTAQEBBIPEEWEVKAKOEWADREMXMTBHHCHRTKDNVRZCHRCLQOHPWQAIIWXNRMGWOIIFKEE

Kasiski測試法CHR出現(xiàn)在5次，MND出現(xiàn)在2個地方Kasiski測試法于是密表數(shù)最可能是5個卡西斯基法確定密鑰長度的步驟總結(jié)如下：（1）找出三個或更多字符的重復(fù)模式；（2）記錄每個具體模式每次出現(xiàn)的開始位置；（3）計算連續(xù)兩次具體模式起點之間的差數(shù)；（4）確定每種差數(shù)的所有因子；（5）若用的是多表替代密碼。那么密鑰長度將可能是（4）中因子計算中出現(xiàn)最多的那個因子的值。思考：以多大的概率成立？

P(X1=X2|Y1=Y2)=1-P(X1!=X2;K1!=K2|Y1=Y2)由于密鑰是等概獨立的，每個密鑰出現(xiàn)的概率為1/26，這相當(dāng)于求滿足X1+K1=X2+K2(mod26)的K1和K2出現(xiàn)的概率。若K1和K2中均有m個字母，且m>=3，則P(X1=X2|Y1=Y2)重合指數(shù)法(indexofcoincidence)：Wolfefriendman于1920年提出用多密表加密時，用的密表越多密文字母出現(xiàn)的頻率越平均。因此，計算密文字母的分布與平均分布的方差，可以得到有關(guān)密表數(shù)的信息。重合指數(shù)法(indexofcoincidence)1.粗糙度（roughness）設(shè)proba是消息中字母a出現(xiàn)的概率，probb是b出現(xiàn)的概率，…，probz是z出現(xiàn)的概率。由于可能出現(xiàn)的字母只有a,b,…,z，故有：proba

+probb+…+probz

=1。

如果在消息集合S中，各個字母出現(xiàn)的概率相等，即消息中字母的分布是完全均勻的分布，那么有：proba+probb+…+probz=1/26≈0.0384。重合指數(shù)法(indexofcoincidence)1.粗糙度（roughness）定義

設(shè)消息集合S中，proba是消息中字母a出現(xiàn)的概率，probb是b出現(xiàn)的概率，…，probz是z出現(xiàn)的概率,令：變量Var

稱為集合S的粗糙度。Var反映了消息集合中字母出現(xiàn)頻率的分布與均勻分布的不一致性。正常英語字母的出現(xiàn)頻率作為概率,則可求出正常英語的粗糙度Var=0.0296。由此可知，如果求得一個密文字母集的粗糙度接近0.0296，則該密文集可能是用一個密表加密而得到的。反之，如果求得的粗糙度明顯比0.0296小，則該密文集可能是用多個密表加密而得到的。加密的密表數(shù)越多，密文集的粗糙度越小。因此，可以用粗糙度來判斷一個密文集是否是用一個密表加密得到的。如果注意到粗糙度的后一項是一常數(shù)，那么計算也可以判斷一個密文集是否是用一個密表加密得到的：若=0.0384+0.0296=0.068,則是用一個密表加密的；反之，則不是用一個密表加密的。

的物理意義是從密文中任意取出二個字符是相同字母的概率。通常密文的長度有限，無法求出各字母出現(xiàn)的概率，只能計算它們出現(xiàn)的頻率，為此引入重合指數(shù)的概念。進一步判斷密鑰字的長度是否為

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

定義1設(shè)X=x1x2…xn是一個長度為n的英文字母串，則x中任意選取兩個字母相同的概率定義為重合指數(shù)，用表示。重合指數(shù)法(indexofcoincidence)定理1設(shè)英文字母A，B,…，Z在X中出現(xiàn)的次數(shù)分別為：f0,f1,…,f25則從X中任意選取兩個字母相同的概率為證明在X中任意選取兩個字母共有種選取的可能；在X中的每個相同的字母中選取兩個元素共有種選取的可能。故易證。證畢。注意：（1）當(dāng)密表數(shù)在1-3時，隨著密表的增加IC值迅速下降，但是它的變化幅度在密表更多時逐漸變小。因此，從平均密文字母的分布來說，用三個密表就足夠了。（2）當(dāng)用的密表數(shù)很少時，重合指數(shù)能很好地預(yù)測密表的多少,但對大量的密表就不能直接利用多密表時的IC值來判別密表數(shù)，但可以利用重合指數(shù)法來判別所作的猜測是否能夠成立。已知每個英文字母出現(xiàn)的期望概率，分別記為p0,p1,…,p25，那么X中兩個元素相同的概率為：

=0.065

對于英文的一個隨機字母串，每個英文字母出現(xiàn)的期望概率均為1/26，則在X中任意選取兩個元素相同的概率為=0.038.根據(jù)Kasiski測試法得到的m，可以將密文Y按照下列形式排列：表1將Y排列成m行n/m列的形式，設(shè)m=0(modn)若m確實是密鑰的長度，則上述矩陣中的每一行都是由同一個密鑰ki加密得到，這說明每一行即是一個單表代替，這時計算每一行的重合指數(shù)，應(yīng)該更接近0.065；若m不是密鑰的長度，則上述矩陣中的每一行不是由同一個密鑰ki加密得到，這說明每一行是一個等概隨機的字母串（對密文的要求），這時計算每一行的重合指數(shù)，應(yīng)該更接近0.038。驗證剛才的例子于是密表數(shù)最可能是5個例用重合指數(shù)法來進一步核實該例

中的密文是用5個密表加密而成的。重復(fù)模式卡西斯基法已經(jīng)推測該密文是由5個密表加密而成的,為了證實這一猜測,可將上述密文按下列方式分成5組判斷每個組是否都是用一個密表加密的。如果每一組都是用一個密表加密而成的，那么每一組的重合指數(shù)都應(yīng)該接近0.068。分別計算它們的IC得：IC(S1)=0.063,IC(S2)=0.068,IC(S3)=0.069,IC(S4)=0.061和IC(S5)=0.072。這些值都與0.068很接近，因此，間接地證明了該維吉尼亞密碼的密鑰長度為5。單字符多表替代密碼的分析步驟從以上例子可以歸納多表替代密碼的分析過程如下：（1）用卡西斯基法預(yù)測加密密表的可能數(shù)目，如果沒有出現(xiàn)比較有規(guī)律的數(shù)，那么該密碼可能不是簡單的多表替代密碼；（2）計算整個密文的重合指數(shù)確認(rèn)第一步的預(yù)測；（3）通過（1）和（2）得到了有希望的密表數(shù)，因而可以把密文分成適當(dāng)?shù)淖蛹?，分別計算每個子集的重合指數(shù)，以確定每個子集確實是單表密碼；（4）用猜測法或統(tǒng)計法分析每個子集，求出明文。若明文有意義，則該多表替代密碼的密文已被破譯。用交互重合指數(shù)確定密鑰的具體內(nèi)容定義設(shè)X=x1x2…xn和Y=y1y2…yn，是兩個長度分別為n和n’的字母串。X和Y的交互重合指數(shù)(mutualindexofcoincidence)定義為X中的一個隨機元素與Y中的一個隨機元素相同的概率，記為

fi和f‘i為字母出現(xiàn)頻率計算表1中的任意兩行之間的交互重合指數(shù)中的一個隨機元素與中的一個隨機元素同為字母h(0<=h<26)的概率為

則稱為和之間的相對位移(relativeshift)，用表示。由于計算具體密鑰內(nèi)容當(dāng)相對位移不為0時，重合指數(shù)的取值范圍[0.031,0.045]當(dāng)相對位移為0時，重合指數(shù)取值為0.065?？梢越y(tǒng)計每兩行中英文字母出現(xiàn)的概率f0,f1,…,f25

和f’0,f’1,…,f’25記為以g作密鑰進行加法加密得到的密文，并窮舉計算得到若

，則應(yīng)該接近0.065；若不然，應(yīng)該接近[0.031,0.045]中的某個值。K1+i,i=0,……,25K1-k2=5計算具體密鑰內(nèi)容的復(fù)雜度分析

這樣可以得到任意兩行之間的相對位移。給定某一行，猜測其密鑰值(只有26種可能),其它行的密鑰由相對位移唯一確定,這時用窮舉法只有26種可能,可得到密鑰值。剛才的例子繼續(xù)的值共有260個，計算結(jié)果列于下表，找出的值接近0.068的（i,j）對，如果對于給定的（i，j）只有一個值接近0.068，則g就是i和j對應(yīng)的相對位移，即：ki?kj=g在表中共有6個滿足該條件的值，這些值說明y1和y2的相對位移是9；y1和y5的相對位移是16；y2和y3的相對位移是13；y2和y5的相對位移是7；y3和y5的相對位移是20以及y4和y5的相對位移是11。這樣就得到了未知數(shù)k1,k2,k3,k4,和k的6個方程：密鑰形式為：經(jīng)過對密鑰的窮盡搜索（最多26次,），確定密鑰為：JANET用密鑰JANET解密Thealmondtreewasintentativeblossom.Thedayswerelonger,oftenendingwithmagnificenteveningsofcorrugat