《現(xiàn)代密碼學(xué)原理與實(shí)踐》課件第1章

第1章傳統(tǒng)密碼1.1基本概念1.2傳統(tǒng)密碼舉例

1.3密碼分析舉例

習(xí)題1

實(shí)踐練習(xí)1

為了經(jīng)濟(jì)或軍事的需要，古代就出現(xiàn)了各種各樣的加密方法。經(jīng)過人類多年的研究和改進(jìn)，已經(jīng)取得了大量的成果?，F(xiàn)代密碼學(xué)是在借鑒與發(fā)展傳統(tǒng)密碼學(xué)的基礎(chǔ)上誕生的。在學(xué)習(xí)現(xiàn)代密碼學(xué)之前，了解傳統(tǒng)密碼學(xué)的基本概念和成功經(jīng)驗(yàn)是十分必要的。本章將介紹最典型的幾種傳統(tǒng)密碼算法及其破譯方法。1.1基本概念1.1.1密碼與密碼學(xué)密碼是為解決信息安全而進(jìn)行的編碼。安全指通信系統(tǒng)抗御外來攻擊的能力。外來攻擊主要有兩大類：一類是以截獲或竊聽通信內(nèi)容為目標(biāo)的被動(dòng)攻擊，攻擊者截獲他人信息、竊取密碼、打探隱私、偷盜機(jī)密、危害民眾；另一類是以纂改或偽造信息為手段的主動(dòng)攻擊，攻擊者冒充合法發(fā)信人，發(fā)布信息，安置黑客，散布病毒，甚至破壞通信系統(tǒng)。針對被動(dòng)攻擊，密碼可以使所傳輸信息具有保密功能，竊聽者即使截獲了一些信息，也會(huì)因不懂密文而不知所云。針對主動(dòng)進(jìn)攻，密碼應(yīng)具備“認(rèn)證”功能，對發(fā)信人身份、消息來源以及消息完整性等加以認(rèn)證，使非法發(fā)信人不得進(jìn)入系統(tǒng)，使虛假消息能被識(shí)別，使篡改行為得以被發(fā)現(xiàn)。保密和認(rèn)證是密碼的兩大基本功能。為了軍事、政治、司法等方面的需求，有時(shí)也需要破譯對方的密碼或者賺取對方的認(rèn)證，由此便出現(xiàn)了與“密碼編碼學(xué)”原理相同但目的相反的另一分支，叫做“密碼分析學(xué)”。這種保密與破譯的斗爭如同矛與盾的關(guān)系一樣，魔高一尺，道高一丈，相依相存，相克相長，促進(jìn)了二者共同的發(fā)展。近年來曾多次聽到某種保密系統(tǒng)懸賞破譯，某個(gè)防火墻產(chǎn)品歡迎投訴，其目的就是通過不斷發(fā)現(xiàn)問題與解決問題，增強(qiáng)自己的抗攻擊性能。為了設(shè)計(jì)出更加安全可靠的密碼系統(tǒng)，設(shè)計(jì)者不僅要研究出更新更強(qiáng)的密碼技術(shù)，還要研究對手有哪些可能的攻擊手段。設(shè)計(jì)以分解大數(shù)復(fù)雜性為基礎(chǔ)的RSA密碼體制時(shí)，必定要討論分解大數(shù)的技巧；設(shè)計(jì)以離散對數(shù)復(fù)雜性為基礎(chǔ)的密碼體制時(shí)，難免要討論離散對數(shù)的計(jì)算方法，因此，聰明的密碼設(shè)計(jì)者同時(shí)也應(yīng)該是高明的密碼分析者，二者統(tǒng)一于同一個(gè)目標(biāo)?！懊艽a學(xué)”則是“密碼編碼學(xué)”與“密碼分析學(xué)”的總稱。1.1.2傳統(tǒng)密碼學(xué)與現(xiàn)代密碼學(xué)

密碼技術(shù)的歷史源遠(yuǎn)流長。很久以前，人們?yōu)榱吮４婊騻鬟f經(jīng)濟(jì)、軍事、外交上的重要信息，就已經(jīng)開始使用密碼或類似的保密技術(shù)，發(fā)明了多種多樣的加密和解密方法，其手段由手工加密發(fā)展到機(jī)械加密，直到近代的電子加密。密碼技術(shù)的發(fā)展歷史上，記載著不少精辟的成就，書寫了豐富的經(jīng)驗(yàn)，密碼技術(shù)的成果也曾在二戰(zhàn)中發(fā)揮了巨大作用。然而直到20世紀(jì)40年代以前，密碼技術(shù)卻一直是純經(jīng)驗(yàn)性的學(xué)問。1949年，Shannon發(fā)表了“保密系統(tǒng)的通信理論［1］”，用信息論的觀點(diǎn)對密源、密鑰、密文等概念進(jìn)行了數(shù)學(xué)描述，對保密系統(tǒng)進(jìn)行了定量化的分析，才使保密學(xué)建立在科學(xué)的理論基礎(chǔ)之上。我們把20世紀(jì)70年代以前的密碼研究與應(yīng)用稱為傳統(tǒng)密碼學(xué)。那時(shí)，互聯(lián)網(wǎng)、智能卡以及很多現(xiàn)代交互方式都還沒有出現(xiàn)，傳統(tǒng)密碼學(xué)以研究秘密通信為目的，它關(guān)注的是怎樣使所傳輸?shù)男畔⒉槐坏谌咚`取，發(fā)信人身份的認(rèn)證問題并未引起足夠的重視。

隨著計(jì)算機(jī)互聯(lián)網(wǎng)的出現(xiàn)與普及，一方面通信網(wǎng)絡(luò)極大地方便了人們對信息的交換和共享，另一方面也同時(shí)給攻擊者提供了更多的機(jī)會(huì)。如何更好地解決信息安全問題，已成為刻不容緩的任務(wù)。社會(huì)需求的推動(dòng)與科研成果的積累，終于迎來了20世紀(jì)70年代以公開密鑰體制為標(biāo)志的密碼學(xué)大發(fā)展階段。古老的密碼學(xué)重新煥發(fā)出蓬勃的生機(jī)，成為新的熱門學(xué)科。密碼學(xué)作為信息安全的衛(wèi)士，已走出密碼學(xué)家神秘的殿堂，成為廣大民眾和商界關(guān)注的學(xué)科。一般認(rèn)為現(xiàn)代密碼學(xué)誕生于20世紀(jì)70年代，標(biāo)志性的大事有兩件［2］：一是1977年美國國家標(biāo)準(zhǔn)局正式公布實(shí)施了美國數(shù)據(jù)加密標(biāo)準(zhǔn)(DES)，并批準(zhǔn)用于非機(jī)要部門和商業(yè)用途，傳統(tǒng)密碼學(xué)的神秘面紗被揭開；二是1976年11月，美國斯坦福大學(xué)電氣工程系研究生W.Diffie和副教授Helman在IEEE上發(fā)表了題為“密碼學(xué)新方向”的學(xué)術(shù)論文，公鑰密碼研究的序幕就此拉開。從此密碼學(xué)以一種全新的理念和姿態(tài)迅速崛起，理論研究成果頻出的同時(shí)，實(shí)際應(yīng)用也大踏步地走進(jìn)了人們的生活。傳統(tǒng)密碼學(xué)只重視保密功能，而現(xiàn)代密碼學(xué)除了重視保密功能之外，還對認(rèn)證功能提出了多方面的要求，如發(fā)信人身份認(rèn)證、信息完整性認(rèn)證、不可抵賴性認(rèn)證等，對于抵御主動(dòng)攻擊發(fā)揮了巨大的作用。數(shù)字簽名是一種常見的認(rèn)證手段?，F(xiàn)代密碼學(xué)還提出了公開算法的思想，開創(chuàng)了公開密鑰體制的新思路，從而在安全觀念與設(shè)計(jì)理念上明顯地區(qū)別于傳統(tǒng)密碼學(xué)，獨(dú)樹一幟，成為當(dāng)代信息安全的重要技術(shù)支柱。由于現(xiàn)代密碼學(xué)的需要，過去某些純數(shù)學(xué)理論的領(lǐng)域，如經(jīng)典數(shù)論、橢圓曲線等，一下子找到了用武之地，變得火爆起來。1.1.3對稱密鑰與非對稱密鑰

就系統(tǒng)使用的密鑰來分類，有兩大類密鑰體制。一類是對稱密鑰體制，加密與解密的密鑰相同，掌握加密密鑰的人，必然也能解密，這種密碼體制也叫做單密鑰體制。另一類是非對稱密鑰體制，加密密鑰與解密密鑰是不相同的，因而可以將其中一把密鑰公開，只需秘密保管另一把，這種密碼體制也叫做公開密鑰體制或雙鑰體制。傳統(tǒng)密碼系統(tǒng)全都屬于對稱密鑰體制,而現(xiàn)代密碼系統(tǒng)中兩類密鑰體制都存在。比如DES屬于對稱密鑰體制，RSA則屬于非對稱密鑰體制。1.1.4分組密碼與序列密碼

就系統(tǒng)加密與解密方式來分類，有分組密碼與序列密碼兩類。分組密碼是把欲加密的文本分成一些較短的段落，每次使用相同的密鑰與算法處理一段，然后將處理后的各個(gè)小段連接起來。解密過程也是按原來的分段一段段解譯，然后再連接起來。序列密碼方式則不進(jìn)行分段，直接把整個(gè)文章順序送入加密器，密鑰也應(yīng)當(dāng)源源不斷地輸入加密器，加密器通常只是完成某種很簡單的算法，比如模二加法。這種看似簡單的一字一密加密方式已被Shannon從理論上證明是無法破譯的，當(dāng)然它要求的密鑰是無限長的隨機(jī)序列。1.1.5密碼學(xué)基本術(shù)語［3］

保密通信過程的流程圖如圖1.1所示。保密通信的一些基本術(shù)語對于傳統(tǒng)密碼學(xué)與現(xiàn)代密碼學(xué)都同樣有用。如：

·明文(plaintext)：發(fā)送方(sender)未經(jīng)過加密處理的信息，其內(nèi)容是容易理解的。

·密文(ciphertext)：發(fā)送方經(jīng)過加密處理后的信息，文字被改變，其內(nèi)容是難以理解的。

·密鑰(key)：發(fā)送方加密處理時(shí)所用的秘密信息。在傳統(tǒng)密碼學(xué)中，解密也使用同樣的密鑰。

·加密(encryption,encipher)：發(fā)送方把明文加工成密文的變換，即

c=Ek(m)

(1-1)

·

解密(decryption,decipher)：接收方(receiver)把密文解譯成明文的變換，即

m=Dk(c)(1-2)

為了順利進(jìn)行上述保密通信過程，通信之前還必須完成以下準(zhǔn)備工作：

(1)協(xié)議(protocol)：約定通信雙方的通信步驟和各個(gè)技術(shù)細(xì)節(jié)。

(2)密鑰交換(keyexchange)：通信雙方必須設(shè)法取得所約定的密鑰(指對稱密鑰)。用公共信道傳輸密鑰是不安全的，除非利用某種專門用于傳送密鑰的秘密信道來傳輸，然而其代價(jià)可能是昂貴的，或是很不方便的?？梢?，密鑰交換問題是傳統(tǒng)密碼體制的一大難題。圖1.1保密通信的流程示意1.2傳統(tǒng)密碼舉例［2］

1.2.1逆序密碼

設(shè)：明文為

m=Thousandsofyearsago,cryptographyhadbeenusedtokeepsecretsofmilitaryoperationsortreasure.加密算法Ek為將原文忽略空格并不計(jì)字母大小寫，每5字符一組，各組取逆序，連接后得到密文：

c=suohtosdnaraeyfcogasotpyrhpargbdahysuneekotdeespeesterclimfoyratiareposnoitertroerusa

這里，k=5是密鑰。1.2.2棋盤密碼將26個(gè)字母寫入5×5方陣中，i和j占同一格，使每個(gè)字符都由一對行、列腳標(biāo)表示之，如表1.1所示。例如,明文為

m=Thereareallkindsofencryptionschemesinclassiccryptography.

則將原文忽略空格，用表1.1的行、列腳標(biāo)編碼，可寫出如表1.2所示的密文。表1.1棋盤密碼的字母排列表1.2棋盤密碼對明文的加密結(jié)果1.2.3凱撒密碼將26個(gè)英文字母按字母表序號(hào)0~25編號(hào)(有時(shí)也可以按1~26編號(hào))，如表1.3所示。加密編碼的方法是把明文的每個(gè)字母用向后循環(huán)移動(dòng)k位后的字符代替：

c=Ek(m)=m+kmod26(1-3)移位距離k(0<k<26)是密鑰。例如明文是：

m=JuliusCaesar(朱麗葉斯·凱撒)則不計(jì)空格與大小寫，明文各字符的序號(hào)為920118201820418017

假設(shè)平移k=11，則變?yōu)?03122193129131115291128表1.3英文字母按字母表序號(hào)0～25編號(hào)循環(huán)位移意味著：31=5mod26，29=3mod26，28=2mod26于是，得到平移后的序號(hào)：2052219531311153112再按字母表寫出，則密文為

c=UFWTFDNLPDLC更一般的方法是不僅平移而且作“仿射變換”：

c=k1m+k2mod26(1-4)式中，k1和k2是兩個(gè)密鑰，k1要求與26互素。例如，m=information對應(yīng)的字母序號(hào)是：813514171201981413

若選k1=7，k2=10，則變換后的數(shù)字是：14231942516101314423對應(yīng)的密文是

c=OXTEZQKNOEX1.2.4單表置換密碼

實(shí)際上，除了移位，還可以置換，甚至任意調(diào)換，26個(gè)字母的各種排列共26!種，每指定一種調(diào)換方式，都可以寫出一張與原字母表對應(yīng)的置換對照表，稱為單表置換。在置換表中引入密鑰的方法有許多種。例如可按下述方式編制置換對照表：設(shè)密鑰為UniversityofScienceandTechnology，略去重復(fù)字符，得到UNIVERSTYOFCADHLG，排在置換對照表的最前面，后面順序接上字母表中尚未出現(xiàn)過的字符，就構(gòu)成了下面的列置換表：1.2.5多表置換——維吉利亞(Vigenere)密碼單表置換雖然改變了明文的模樣，但密文中同一個(gè)字符總來自明文的同一字母，這樣就很容易從概率分析上破譯(找到概率最大的字母，就可能是e變來的)。為此引入多表變換，原文中的同一字母出現(xiàn)在不同位置時(shí)，會(huì)變換成密文的不同字符。設(shè)密鑰k是長度為n的字符串(k1k2…kn)，這里kj是密碼的第j個(gè)字符在字母表的序號(hào)。明文m也被分成許多長為n的小段，第i段Mi=m1m2…mn；那么該段明文對應(yīng)的密文Ci=c1c2…cn。則有

cj=(mj+kj)mod26j=1，2，…，n(1-5)

例如：密鑰k=shift，其字母序號(hào)為18，7，8，5，19；密鑰長度n=5。將明文m=encodealgorithm忽略空格，按n=5分段后，其字母序號(hào)是：4,13,2,14,3；4,0,11,6,14；17,8,19,7,12；則第1段5個(gè)字符分別移位18，7，8，5，19后序號(hào)變?yōu)?2,20,10,19,22，即WUKTW；第2段5個(gè)字符再分別移位18，7，8，5，19后序號(hào)變?yōu)?2,7,19,11,7，即WHTLH；第3段5個(gè)字符又分別移位18，7，8，5，19后序號(hào)變?yōu)?,15,1,12,5，即JPBMF。最終的密文是c=WUKTWWHTLHJPBMF。為了容易地查到不同密鑰字符的變換結(jié)果，可以列出一張“維吉利亞”方陣表，第一行26個(gè)字母按序排列。第二行是第一行左移一位的結(jié)果，B開頭，字母順序不變，直到Z，最后是A作結(jié)尾。第三行是循環(huán)左移二位……直到第26行以Z開頭，后接AB……XY。當(dāng)密鑰字符為a時(shí)，就查第一行；當(dāng)密鑰字符為b時(shí)，就查第二行……當(dāng)密鑰字符為z時(shí)，就查最后一行。表中的列用來查詢每個(gè)明文字母應(yīng)當(dāng)對應(yīng)什么密文字母。這種方式稱為多表置換。后來，比歐福特(Beaufort)將“維吉利亞”方陣表的各行按逆序排列得到了“比歐福特方陣”，使破譯更加困難。1.2.6維爾南(Vernam)加密算法當(dāng)明文、密文、密鑰均為二元代碼(0，1)時(shí)，維吉利亞密碼就成了維爾南密碼。維爾南密鑰在計(jì)算機(jī)代碼中得到廣泛應(yīng)用，其計(jì)算公式是：

ci=(mi+ki)mod2i=1，2，3，…(1-6)式中，mi、ki、ci都是0或1。密鑰一般是取一個(gè)周期很長的偽隨機(jī)二元碼序列。加密后，密鑰的隨機(jī)性掩蓋了明文的可讀性，使密文變的不可理解。為了得到較長的密鑰，可以找兩個(gè)不太長的密鑰，各自循環(huán)著使其中一個(gè)對另一個(gè)加密，當(dāng)兩密鑰長度互素時(shí)，可得到長度為二者之積的密鑰。1.2.7普萊費(fèi)厄(Playfair)加密算法普萊費(fèi)厄加密算法把引入密鑰詞組的單表密碼與棋盤密碼結(jié)合。例如密鑰是fivestars，按單表方式排序后寫成5×5方陣：若明文為M=Playfaircipherwasactuallyinventedbywheatstone則先將明文兩兩分組：pl,ay,fa,Ir,ci,ph,wa,sa,ct,ua,lq,ly,in,ve,nt,ed,by,wh,ea,ts,to,ne

分組時(shí)注意：

(1)若分組出現(xiàn)兩字母相同時(shí)，則在兩字母之間插入一個(gè)q。(2)若總字符個(gè)數(shù)為單數(shù)，則在最后那個(gè)不配對的字母后添一個(gè)q。加密方法如下：

(1)若分組m1m2在方陣同行時(shí)，密文c1c2分別是m1和m2右面的字母，其中第一列可視為第五列的右面。

(2)若分組m1m2處在方陣同一列時(shí)，密文c1和c2分別是m1和m2下面的字母，第一行可視為第五行的下面。(3)若m1m2不同行也不同列時(shí)，c1和c2是m1m2為對角的矩陣塊的另兩個(gè)角，并且c1與m1同行，c2與m2同行。按此加密方法，上例中分組被加密為

QK,BW,IT,VA,AS,OK,IG,IC,TA,WT,QZ,KZ,AW,ES,MA,FK,KE,XG,IB,CF,RM,PI1.2.8希爾(Hill)加密算法將明文中長為L的字符分組m通過線性變換k，變?yōu)槊芪闹虚L為L的字符分組c。字符分組以列矢量表示：

c=k·mmod26 (1-7)有時(shí)，字符分組以行矢量表示，此時(shí)應(yīng)采用的變換式為

c=m·kmod26(1-8)例如,m=Hill，四個(gè)字母序號(hào)為7，8，11，11若則c=k·m=

即c=YTIX解密可由反變換：

m=k-1cmod26(1-9)來計(jì)算，k-1是k的逆矩陣,且作模26處理。掌握密鑰的用戶不難求出k-1。本例中：1.3密碼分析舉例

以破譯密碼為目的的學(xué)問叫密碼分析學(xué)。越來越多的事實(shí)告訴我們，密碼分析是密碼學(xué)不可分割的組成部分。每研制出一種新密碼的同時(shí)，就應(yīng)當(dāng)討論它的抗攻擊性能；每當(dāng)某種密碼被破譯的同時(shí)，也就啟示密碼學(xué)家發(fā)現(xiàn)原先密碼系統(tǒng)的漏洞和改進(jìn)方法。根據(jù)掌握數(shù)據(jù)的多少，密碼分析可以分為以下幾種：

(1)唯密文攻擊：僅掌握若干被同一密鑰和同一加密算法得到的密文，想導(dǎo)出明文。

(2)已知明文攻擊：不僅掌握若干密文，還知道相應(yīng)的明文，想從中找到密鑰,從而對任何其他同類加密的密文都能破解。(3)選擇明文攻擊：不僅掌握密文，還有多個(gè)可供選擇的明文。顯然攻擊力度更強(qiáng)了，或破譯更容易了。下面舉幾個(gè)破譯傳統(tǒng)密碼的例子。1.3.1對單表置換密碼的分析

單表密碼系統(tǒng)的漏洞在于明文中相同的字符一定對應(yīng)密文中同樣的字符，明文中出現(xiàn)概率最高的字符，必然對應(yīng)于密文中出現(xiàn)最多的字符，因此利用自然語言文字的概率統(tǒng)計(jì)性質(zhì)容易找到明、密文字符的對應(yīng)關(guān)系。下面以兩個(gè)實(shí)例來展示分析過程。對大量英語文章的統(tǒng)計(jì)發(fā)現(xiàn)，各個(gè)字母出現(xiàn)的概率是不相同的。對單個(gè)字母的統(tǒng)計(jì)結(jié)果列于表1.4中(概率值為x%)。表1.4英文文章中各個(gè)字母出現(xiàn)的概率【例1】已知仿射密碼的密文為［4］

FMXVEDRAPHFERBNDKRXRSREFMORUDSDKDVSHVUFEDKAPRKDLYEVLRHHRH共57字。對應(yīng)的明文是什么？解：先統(tǒng)計(jì)各字符(特別是高頻字符)出現(xiàn)的頻度：R(8)，D(7)，E、H、K(各5),F、S、V(各4)(1)根據(jù)出現(xiàn)頻率大小，不妨設(shè)R→e，D→t，R序號(hào)為17，D序號(hào)為3，e為4，t為19。將之代入加密的仿射方程：

y=ek(x)=ax+bmod26

(1-10)得解得由于gcd(a,26)=2，表明此密碼不正確(正確的a應(yīng)當(dāng)與26互素)。(2)重新假設(shè)R→e，E→t，E的序號(hào)為4，從而得解得由于gcd(a,26)=1，因此有可能是正確的結(jié)果。(4)由加密算法：

y=3x+5mod26得到解密算法

式中：3-1=9mod26(3的模逆元是9)。

(5)用這個(gè)結(jié)果解譯密文，看能否得到有意義的明文。結(jié)果是：

algorithmsarequitegeneraldefinitionsofarithmeticprocesses得到了有意義的明文，表明破譯正確。【例2】已知單表加密的280字密文為［2］

GJXXNGGOTZNUCOTWMOHYJTKTAMTXOBYNFGOGINUGJFNZVQHYNGNEAJFHYOTWGOTHYNAFZNFTUINZBNEGNLNFUTXNXUFNEJCINHYAZGAEUTUCQGOGOTHJOHOATCJXKHYNUVOCOHOUHCNUGHHAFNUZHYNCUTWJUWNAEHYNAFOWOTUCHNPHOGLNFQZNGFOUVCNVJHTAHNGGNTHOUCGJXYOGHYNABNTOTWGNTHNTXNAEBUFKNFYOHHGIUTJUCEAFHYNGACJHOATAEIOCOHUFQXOBYNFG如何解密以恢復(fù)明文？

解：(1)先統(tǒng)計(jì)密文中各字母出現(xiàn)的次數(shù)：(由大到小排列)N(36),H(26),O(25),G(23),T(22),U(20),F(17),A(16),Y(14),C(13),J(12),X(9),E(7),Z(7),W(6),B(5),I(5),Q(5),V(4),K(3),L(2),M(2),P(1)英文文章中的高概率字母e、t、a、o、n、i、r、s、h和中概率字母d、l、u、c、m之間的概率值有一明顯的間斷。由此我們大體可確定密文中出現(xiàn)頻度較高的9個(gè)字符N、H、O、G、T、U、F、A、Y的對應(yīng)范圍，并且大體能肯定N就是e。

(2)再來統(tǒng)計(jì)密文中各字符的前綴與后綴的出現(xiàn)頻度。下表列出了密文中出現(xiàn)頻度較高的9個(gè)字符的前后連綴關(guān)系。表格中的每組數(shù)分別表示該行、該列兩字符的兩種不同排序方式所出現(xiàn)的次數(shù)。比如N行G列交叉處的(5,4)表示NG出現(xiàn)5次，GN出現(xiàn)4次。①由這些數(shù)據(jù)推測，O、U、A可能是元音i、a、o，這是因?yàn)樗鼈兓ミB的可能很小；OA出現(xiàn)兩次，OU出現(xiàn)一次，其他UO、UA、AO、AU均無出現(xiàn)，所以O(shè)→i,A→O；又由OU出現(xiàn)一次，NU出現(xiàn)5次，UN不出現(xiàn)，可猜到U→a(因ea常見ae極少，ia也是存在的)。②根據(jù)n是高頻輔音,且n的前面是元音的概率高達(dá)80%，現(xiàn)在T頻度為22，前面是O.U.A的占17次，由此可判定T→n。③YN出現(xiàn)9次,NY不出現(xiàn)，已經(jīng)判知N→e,于是可判Y→h。根據(jù)th常見而ht罕見，及HY出現(xiàn)10次，YH一次也沒有，知H→t。④高概率集中只剩下r和s尚看不出與密文前9位中剩余的F和G有何對應(yīng)關(guān)系。(3)接下來就把280個(gè)字母中已找到的159個(gè)先寫出來，空出尚未找到對應(yīng)關(guān)系的字母，待猜測填空(注意：大寫表示密文字符，小寫表示已經(jīng)找到的明文字符)。①由Mith猜出M→w,于是由nKnown→nknown知K→k；由intJition知J→u。②將已判定的字母填入置換對照表中就有：之后的HJ_M已呈現(xiàn)出字母表的順序，于是可猜到中間空的是L→v；而前面的rs應(yīng)當(dāng)是FG,后面的xy則是PQ；最前面既然U→a，可猜到V→b。③再次將猜到的字母代入密文，就得到：

由suXXess可猜出X→c，于是由XiBhers知B→p，得ciphers；還可由Eour猜E→f得four；thinW猜W→g，得thing。④再次回到單表對照關(guān)系上，就知密鑰詞組是：NEWYORKCITY。去掉重復(fù)的Y，后面按順序接字母表中尚未出現(xiàn)的字符，就是：NEWYORKCITABDFGHJLMPQS。最后將UVXZ循環(huán)移位到前面去，得到與字母表對應(yīng)的置換密鑰是UVXZNEWYORKCITABDFGHJLMPQS。(4)按此對照表，可將密文全文譯出為

Successindealingwithunknownciphersismeasuredbythesefourthingsintheordernamed,perseverance,carefulmethodsofanalysis,intuition,luck.Theabilityatleasttoreadthelanguageoftheoriginaltextisverydesirablebutnotessential.SuchistheopeningsentenceofParkerHitt’sManualfortheSolutionofMilitaryCiphers.

意思是：破譯一未知密碼是否成功，可由以下四個(gè)因素來衡量，按順序?yàn)椋阂懔?、審慎的分析方法、直觀和運(yùn)氣。閱讀原文文字的起碼能力是需要的，然而不是必不可少的。這是ParkerHitt的“軍事密碼破譯指南”一書的開場白。1.3.2對維吉利亞密碼的分析［2，5］

維吉利亞密碼屬多表密碼，明文相同的字符變換到密文中未必是相同的字符，只有當(dāng)這兩個(gè)相同字符距離等于密鑰長度時(shí)，它們對應(yīng)的密文字符才會(huì)相同。因此分析密文中兩個(gè)相同字符出現(xiàn)的位置,就是尋找密鑰長度的關(guān)鍵。

1.密鑰長度的初步判斷首先統(tǒng)計(jì)密文中不同距離處出現(xiàn)相同字符的次數(shù)。例如密文是如下的280個(gè)字符：UFQUIUDWFHGLZARIHWLLWYYFSYYQATJPFKMUXSSWWCSVFAEVWWGQCMVVSWFKUTBLLGZFVITYOEIPASJWGGSJEPNSUETPTMPOPHZSFDCXEPLZQWKDWFXWTHASPWIUOVSSSFKWWLCCEZWEUEHGVGLR

LGWOFKWLUWSHEVWSWTTUARCWHWBVTGNITJRWWKCOYFGMILRQESKWGYHAQENDIULKDHZIQASFMPRGWRVPBUIQQDSVMPFZMVEGEEPFODJQCHZIUZZMXKZBGJOTZAXCCMUMRSSJW從頭到尾考察密文中所有的符號(hào)。統(tǒng)計(jì)距離為1的兩個(gè)相同符號(hào)出現(xiàn)的次數(shù)，就是數(shù)出相鄰兩字符相同的次數(shù)，結(jié)果是20次；統(tǒng)計(jì)距離為2的兩個(gè)相同符號(hào)出現(xiàn)的次數(shù)，也就是中間只隔一個(gè)符號(hào)的兩相同符號(hào)的次數(shù)，結(jié)果共出現(xiàn)52次。再統(tǒng)計(jì)距離為3的兩個(gè)相同符號(hào)出現(xiàn)的次數(shù)，得到是32次。下表列出了兩個(gè)相同字符出現(xiàn)在距離20以內(nèi)的各種情況的次數(shù)：

可以看到，距離為2和5時(shí)，兩相同符號(hào)出現(xiàn)的次數(shù)最多，由此可以推測，密鑰長度可能為2或5。但是長度為2的密鑰極少有人取，于是初步判定密鑰長度為5。

2.密鑰長度的確認(rèn)

根據(jù)初步判斷，可以把密文依次按列排序，每列5個(gè)字符，構(gòu)成m=5行的陣列。也就是說，把原來的序列像發(fā)撲克牌似地依次分配到5行中：UUGIWYJUWAGVUGTFGPTOFPKWPVKCUGGWHTCVTKGQGNKQPVQMVPQUKOCRFDLHYYPXCEQSTZYAGNPPDLDTWSWRELWLETWTJCMEYDDARPQPEFCZZTCSQWZWYQFSSVCWBFOSSSTHCZWHISWZHROUVUHGROISHIHSGBDFGOHZBZMSUFALFAKSVWMFLVEIJUMZXQFAUSLWGLFWWAWNWTLKAUZFWUSZEDZMGAUJIHRLSTMWFWVKLIIWEEPSEWXSOFCEVLKSSRBIWPRWELIMRIVMEJIXJXMW

如果密鑰長度確實(shí)是5，則若設(shè)密鑰為k=k1k2k3k4k5，那么陣列的第1行應(yīng)當(dāng)是明文中序號(hào)為1,6,11,16……的相應(yīng)字符用第1位密鑰k1移位加密的結(jié)果，第2行是明文中序號(hào)為2,7,12,17……的相應(yīng)字符用第2位密鑰k2移位加密的結(jié)果……

由于同一行的各個(gè)元素都是由明文字符通過相同距離的移位產(chǎn)生的，而這種單表加密方式的字符替換不改變原來的概率分布，因此每行仍然應(yīng)當(dāng)呈現(xiàn)出與明文英語相同的統(tǒng)計(jì)規(guī)律。然而，如果密鑰長度本不是5，卻按照上述方式排成了5行的陣列，則它的同一行各個(gè)元素是由不同的移位規(guī)律的多表加密方式產(chǎn)生，就不具備明文英語字符的統(tǒng)計(jì)規(guī)律，而呈現(xiàn)完全隨機(jī)的統(tǒng)計(jì)特征。完全隨機(jī)排列的字符序列中，任一位置出現(xiàn)指定字符(比如A)的概率是在兩位置都出現(xiàn)該指定字符的概率是，所以兩位置出現(xiàn)相同字符(不論什么字符)的概率是

而如果是英語明文序列，不同字母出現(xiàn)的概率是不相同的，比如A是0.0856，兩指定位置同時(shí)出現(xiàn)A的概率(假設(shè)為無記憶信源)是(0.0856)2，B是0.0139，兩指定位置同時(shí)出現(xiàn)B的概率(假設(shè)為無記憶信源)是(0.0139)2……于是兩指定位置出現(xiàn)任意相同字母的概率是設(shè)明文(密文)的長度為n，維吉利亞密鑰長度為m。再設(shè)已統(tǒng)計(jì)出密文中字母A的數(shù)目為nA個(gè)，B的數(shù)目為nB個(gè)……，Z的數(shù)目為nZ個(gè)，那么字母A構(gòu)成的重復(fù)雙A對(不論間隔多遠(yuǎn))的數(shù)目是，同理B構(gòu)成的重復(fù)雙B對的數(shù)目是……Z構(gòu)成的重復(fù)雙Z對的數(shù)目是。所有相同字母對的數(shù)目為。而長為n的密文中，任取兩字符組成的對子的數(shù)目為，可見兩位置上字母相同的概率為(1-11)IC稱為重合指數(shù)，表示指定序列中任意兩位置上有相同字符的頻度。對上述陣列每行分別計(jì)算重合指數(shù)：第一行為0.0623，第二行為0.0506，第三行為0.0649，第四行為0.0617，第五行為0.0617；它們都很接近英文明文序列的統(tǒng)計(jì)結(jié)果0.0687，而明顯不同于完全隨機(jī)序列的理論值0.0385。這就表明了各行都是單表置換所得，也就是說，m=5的判斷是正確的。3.密文的破譯

我們不妨把一、二兩行合起來作為一個(gè)整體來計(jì)算重合指數(shù)：式中，上角標(biāo)(1)、(2)分別代表第一行和第二行，n(1)+n(2)則是兩行總字符數(shù)。因?yàn)槭街?，除?xiàng)外，其他都是常量，所以相關(guān)系數(shù)最大，則IC最大。

設(shè)第一行的密鑰為k1,第二行為k2，一般k1≠k2。我們首先計(jì)算密文一、二兩行的相關(guān)系數(shù)X12=的值，之后將第一行各字符按字母表順序右移一位后再計(jì)算第一行與第二行的相關(guān)系數(shù)X12，再將第一行各字符按字母表順序右移二位再計(jì)算第一行與第二行的相關(guān)系數(shù)X12……如此作下去，這些X12中最大的一個(gè)必定是右移σ12位，使σ12+k1=k2的那個(gè)，因?yàn)樗沟靡弧⒍尚卸甲兂闪讼嗤荑€k2產(chǎn)生的密文。

換言之，我們由X12的最大，找到了一、二兩行密鑰序號(hào)之差σ12=k2-k1。同理，由計(jì)算一、三兩行的X13的最大值可找到一、三兩行密鑰序號(hào)之差σ13。同樣還可找到σ14和σ15。本例的結(jié)果是σ12=9，σ13=12，σ14=16，σ15=2。進(jìn)行到這一步，其實(shí)已經(jīng)有了解譯密文的方法：把第二行各字符按字母順序左移9位，把第三行各字符左移12位，第四行左移16位，第五行左移2位，于是所有密鑰都變得與密鑰一樣了。之后把這樣移位處理后的5段密文重新按原來的順序連接起來，得到：

此文中所有的字符都來自同樣的循環(huán)移位，只需找到這個(gè)位移值k1,問題就得到解決。對此單表密碼問題，已有成熟的破譯方法：統(tǒng)計(jì)各個(gè)字符出現(xiàn)的頻度，不難得到，文中G(序號(hào)為6)出現(xiàn)最多，為36次，可以大體判定它就是e(序號(hào)為4)，因此位移值k1=6-4=2。將所有字符均按字母表順序，移回2個(gè)字符，就得到與［例1］內(nèi)容完全相同的譯文。既然k1=2，那么就有k2=11，k3=14，k4=18和k5=4，表明密鑰是“close”