密碼學(xué)課件(古典密碼)

第一章古典密碼密碼學(xué)的意義密碼學(xué)的歷史、現(xiàn)狀和未來基本術(shù)語和定義古典密碼和相關(guān)基礎(chǔ)數(shù)學(xué)理論如何用精確的數(shù)學(xué)語言定義和分析古典密碼密碼學(xué)的重要性密碼學(xué)是信息安全技術(shù)的核心和基石，在信息安全領(lǐng)域起著基本的、無可替代的作用。這方面的任何重大進展，都會有可能改變信息安全技術(shù)的走向密碼技術(shù)和理論的發(fā)展始終深刻影響著信息安全技術(shù)的發(fā)展和突破密碼學(xué)的地位信息安全大廈安全的密碼算法安全協(xié)議網(wǎng)絡(luò)安全系統(tǒng)安全應(yīng)用安全密碼學(xué)學(xué)習(xí)密碼學(xué)的意義密碼學(xué)相關(guān)理論和技術(shù)，是進一步學(xué)習(xí)和運用安全技術(shù)的基本功數(shù)據(jù)保密身份鑒別數(shù)字簽名數(shù)字水印密碼學(xué)的發(fā)展歷史起源(4000年以前)有意識地隱藏信息古代密碼(1900年以前)純手工或采用簡單機械古典密碼(1900-1949)采用復(fù)雜機械或機電設(shè)備也有學(xué)者將1949年以前統(tǒng)稱為古典密碼傳統(tǒng)密碼(1950-1975)采用計算機技術(shù)安全基于密鑰現(xiàn)代密碼(1976以后)出現(xiàn)公鑰密碼密碼學(xué)的起源密碼學(xué)(Cryptology)一詞來源于兩個希臘語單詞——隱藏(Kryptos)和書寫(Graphen)隱寫術(shù)(Steganography)：通過隱藏消息的存在來保護消息。常用的手段包括：隱形墨水、字符格式的變化、圖形圖像(水印)。AB

Apparentlyneutral'sprotestisthoroughlydiscountedandignored.Ismanhardhit.Blockadeissueaffectspretextforembargoonbyproducts,ejectingsuetsandvegetableoils.

:^;@b(]Y(m=4$1m=dQg&_;c?VdSt<C![VKYo]

藏頭詩平湖一色萬頃秋，湖光渺渺水長流。秋月圓圓世間少，月好四時最宜秋。蘆花叢中一扁舟，俊杰俄從此地游，

義士若能知此理，反躬難逃可無憂樂譜古典密碼的特點密碼學(xué)還不是科學(xué)，而是藝術(shù)出現(xiàn)一些密碼算法和加密設(shè)備密碼算法的基本手段(代替&置換)出現(xiàn)，針對的是字符簡單的密碼分析手段出現(xiàn)基于字符的密碼古典密碼象形文字的修改(ModifiedHieroglyphics)：密碼學(xué)的第一個例子是對標準書寫符號的修改，例如古埃及法老墳?zāi)股系奈淖郑?200-1100B.C.），核心思想是代替(Substitution)古典密碼400B.C.，希臘人艾奈阿斯《城市防衛(wèi)論》艾奈阿斯繩結(jié)密碼不同的繩結(jié)距離代表不同的字母妻子給丈夫的保密家書古典密碼古典密碼205-123B.C.，棋盤密碼HELLO

2315313134古典密碼50B.C.，愷撒密碼明文：thequickbrownfoxjumpsoverthelazydog密文：WKHTXLFNEURZQIRAMXPSVRYHUWKHODCBGRJ曾公亮《武經(jīng)總要》(北宋)將常用軍事情報編為40種1請弓、2請箭、3請刀、4請甲、5請槍旗6請鍋幕、7請馬、8請衣賜、9請糧料、10請草料11請車牛、12請船、13請攻城守具、14請?zhí)肀?5請移營16請進軍、17請退軍、18請固守、19未見賊、20見賊訖21賊多、22賊少、23賊相敵、24賊添兵、25賊移營26賊進兵、27賊退兵、28賊固守、29圍得賊城、30解圍城31被賊圍、32賊圍解、33戰(zhàn)不勝、34戰(zhàn)大勝、35戰(zhàn)大捷36將士投降、37將士叛、38士卒病、39都將病、40戰(zhàn)小勝古典密碼曾公密碼選擇一首五言律詩作為密碼本國破山河在，城春草木深感時花濺淚，恨別鳥驚心烽火連三月，家書抵萬金白頭搔更短，渾欲不勝簪——杜甫《春望》加密過程：找到軍情對應(yīng)的字，做標記后放在普通公文中發(fā)送解密過程：字驗古典密碼古典密碼500B.C.，斯巴達人在軍事上用于加解密發(fā)送者把一條羊皮紙螺旋形地纏在一個圓柱形木棒上，核心思想是置換（Permutation）以一種形式寫下消息，以另一種形式讀取消息

IcameIsawIconquered幾何圖形密碼王先生：來信收到，你的盛情真是難以報答。我已在昨天抵答廣州。秋雨連綿，每天需備雨傘一把方能上街，苦矣！大約本月中旬我才能返回，屆時再見。弟李明卡爾達諾漏格法16世紀，意大利數(shù)學(xué)家卡爾達諾發(fā)明情報加密古典密碼卡爾達諾漏格法古典密碼卡爾達諾漏格法古典密碼王先生：來信收到，你的盛情真是難以報答。我已在昨天抵答廣州。秋雨連綿，每天需備雨傘一把方能上街，苦矣！大約本月中旬我才能返回，屆時再見。弟李明Enigma密碼機宣告了手工編碼技術(shù)的結(jié)束發(fā)明人，亞瑟.謝爾比烏斯(ArthurScherbius)(德國)初步破解人，馬里安.雷杰夫斯基(MarianRejewski)(波蘭)最終破解人，阿蘭.圖靈(AlanTuring)(英國)古典密碼Enigma密碼機基本原理利用不斷變化的轉(zhuǎn)子改變字母的代替規(guī)則古典密碼Enigma密碼機基本結(jié)構(gòu)模擬程序古典密碼傳統(tǒng)密碼1949～1975年傳統(tǒng)密碼計算機使得基于復(fù)雜計算的密碼成為可能Shannon,TheCommTheoryofSecretSystems,1949DavidKahn,TheCodebreakers,1967J.L.Smith,ACryptographicDeviceforDataComm,1971H.Feistel,CryptographyandComputerPrivacy,1973數(shù)據(jù)的安全基于密鑰而不是算法的保密傳統(tǒng)密碼加密通信模型HelloHelloHello傳統(tǒng)密碼加密通信模型HelloHello加密機解密機@#^$&@#^$&@#^$&密鑰源安全信道現(xiàn)代密碼1976年以后現(xiàn)代密碼Diffie,Hellman.NewDirectionsinCryptography,19761977年Rivest,Shamir&Adleman提出了RSA公鑰算法90年代逐步出現(xiàn)橢圓曲線等其他非對稱算法基于身份標識的密碼(IBE)非對稱密碼使得無密鑰傳輸?shù)谋Ｃ芡ㄐ懦蔀榭赡埽ΨQ密鑰密碼算法進一步發(fā)展1977年DES加密算法正式成為標準90年代RC6,MARS,Twofish,Serpent等加密算法出現(xiàn)2001年Rijndael算法成為DES的替代者量子密碼(QuantumCryptography)B的公開密鑰現(xiàn)代密碼非對稱密碼加密通信模型HelloHello加密機解密機@#^$&@#^$&@#^$&公開密鑰庫B的私人密鑰基本術(shù)語和概念問題的描述發(fā)送者(Sender)把消息(Message)傳遞給接收者(Receiver)，他想確保除接收者以外的任何人都不能閱讀發(fā)送的消息。消息的內(nèi)容被稱為明文(Plaintext)，用某種方法偽裝消息以隱藏其內(nèi)容的過程成為加密(Encrypt)或譯成密碼(Encipher)被加密的消息成為密文(Ciphertext)，而把密文還原為明文的過程稱為解密(Decrypt)或解譯密碼(Decipher)。基本術(shù)語和概念密碼學(xué)(Cryptology)是研究信息系統(tǒng)安全保密的科學(xué)。是數(shù)學(xué)的一個分支，包括密碼編碼學(xué)和密碼分析學(xué)。密碼編碼學(xué)(Cryptography)主要研究對信息進行編碼，實現(xiàn)對信息的隱蔽。密碼分析學(xué)(Cryptanalytics)主要研究加密消息的破譯或消息的偽造?；拘g(shù)語和概念密碼算法(CryptographyAlgorithm)是用于加密和解密的數(shù)學(xué)函數(shù)。密碼員對明文進行加密操作時所采用的一組規(guī)則稱作加密算法(EncryptionAlgorithm)。接收者對密文解密所采用的一組規(guī)則稱為解密算法(DecryptionAlgorithm)?；拘g(shù)語和概念密碼算法的數(shù)學(xué)表達明文用M或P表示，密文用C表示，加密函數(shù)E作用于M得到C，數(shù)學(xué)公式表示為：

E(P)=C相反地，解密函數(shù)D作用于C產(chǎn)生M

D(C)=P如果使用了密鑰k，則可表示為：

Ek(P)=C;Dk(C)=P基本術(shù)語和概念密碼體制（密碼系統(tǒng)）的數(shù)學(xué)描述它是一個五元組（P,C,K,E,D）滿足條件：（1）P是可能明文的有限集；（明文空間）（2）C是可能密文的有限集；（密文空間）（3）K是一切可能密鑰構(gòu)成的有限集；（密鑰空間）（4）E是加密算法的有限集，D是解密算法的有限集（5）對任意的k∈K，有一個加密規(guī)則(算法)ek∈E和相應(yīng)的解密規(guī)則(算法)dk∈D，使得ek:P->C和dk:C->P分別為加密解密函數(shù)，滿足dk(ek(x))=x，這里x∈P。*加密函數(shù)必須是單射函數(shù)密碼算法的分類按照明文的處理方法可分為分組密碼(blockcipher)和流密碼(streamcipher)分組密碼將明文分成固定長度的組塊，用同一密鑰和算法對每一塊加密，每塊輸出也是固定長度的密文。流密碼又稱序列密碼。序列密碼每次加密一位或一字節(jié)的明文，是手工和機械密碼時代的主流。密碼算法的分類

按照保密的條件可分為受限制的（Restricted）算法和基于密鑰（key-based）的算法如果加脫密的保密性是基于保持算法的秘密，這種算法稱為受限制的算法。缺陷：無法用于大的或經(jīng)常變換的用戶組織。如果加脫密的保密性是基于保持密鑰的秘密，而算法本身可以完全公開，則稱為基于密鑰的算法?；诿荑€的算法通常有兩類：對稱算法和公開密鑰算法。密碼算法的分類對稱算法(SymmetricAlgorithm)就是加密密鑰和解密密鑰相同或能相互推導(dǎo)的密碼算法。秘密密鑰算法或單密鑰算法，要求發(fā)送者和接收者在安全通信之前，商定一個密鑰。對稱算法的安全性完全依賴于密鑰，加密和解密表示為：

EK(M)=C DK(C)=M密碼算法的分類公開密鑰算法(PublicKeyAlgorithm)就是加密密鑰和解密密鑰無法相互推導(dǎo)（至少在假定的長時間內(nèi)）的密碼算法。加密密鑰可以公開，任何人能用加密密鑰加密信息，但只有相應(yīng)的解密密鑰才能解密信息。這里，加密密鑰叫做公開密鑰(PublicKey)，用PuK表示

EPuK(M)=C解密密鑰不可公開，只為解密者(接收方)個人所持有，因此叫做私人密鑰(PrivateKey)或秘密密鑰，用PrK表示

DPrK(C)=M密碼算法的分類有些算法用私人密鑰加密而用公開密鑰解密，這種算法通常叫數(shù)字簽名算法，可以表示為：

EPrK(M)=C DPuK(C)=M移位密碼基本思路將字母表中的每個字母向后移動若干位代替明文字母直觀方便，操作簡單移位密碼移位密碼體制的數(shù)學(xué)描述對于密碼體制的五元組（P,C,K,E,D）有P=C=K=Z26對k,x,y∈Z26，定義ek(x)=(x+k)mod26dk(y)=(y-k)mod26mod稱為“模運算”如果k=3，則此密碼體制為凱撒密碼模運算生活中的求模運算現(xiàn)在是3點鐘，25小時以后是幾點鐘？52小時以后呢？(52+3)÷24余7，52小時后應(yīng)該是7點鐘今天是星期二，9天以后是星期幾？90天以后呢？(90+2)÷7余1，90天以后應(yīng)該是星期一模運算的作用為什么引入模運算模運算可將很大的數(shù)變成較小的數(shù)，同時保持數(shù)的某些周期性的性質(zhì)不變比如1和32085在26下同余，都可以表示字母B從某種意義上看，1=32085可稱32085被模26約化為1密碼運算涉及指數(shù)、對數(shù)等大數(shù)的運算，模運算將運算的數(shù)值始終限定在一定范圍內(nèi)，利于計算機快速處理模運算和同余給定任意整數(shù)a和q，以q除a，余數(shù)是r，則可以表示為a=sq+r,0≦r<q稱q為模數(shù)，r為a模q的剩余，記為

r≡a

modq若整數(shù)a和b有(amodq)=(bmodq)，則稱a與b在模q下同余。(即a和b的差是q的倍數(shù))例如11和19在模4下同余(3)。模運算舉例14＝3×4＋2,2是14模4的余，2≡14mod4（2也是14模3的余）通常對r<q的條件并不嚴格要求，如

19＝3×4＋7，7≡19mod4負數(shù)亦可參與求模（保證余數(shù)大于零即可)(-13)＝(-4)×4＋3，3≡(-13)mod4

7＝(-3)×4＋19，19≡7mod41＝(-1)×11＋12，12≡1mod11模運算的性質(zhì)模運算的基本性質(zhì)：①若q|(a-b)，則b≡amodq。如11－3能被4整除，則3是11模4的余；②(amodq)=(bmodq)意味著a≡bmodq。如3mod4=11mod4，則3是11模4的余；③a≡bmodq等價于b≡amodq。如3是11模4的余，同時4是11模3的余；④若a≡bmodq且b≡cmodq，則a≡cmodq。如3≡7mod4且7≡11mod4，則3≡11mod4模運算的性質(zhì)模算術(shù)（不要求r<q）加法：((amodq)＋(bmodq))=(a＋b)modq例：(3mod4)＋(7mod4)=6=10mod4乘法：((amodq)×(bmodq))=(a×b)modq例：(3mod4)×(7mod4)=9=21mod4指數(shù)：anmodq=an-1modq×amodqam×nmodq=(ammodq)n模運算的性質(zhì)模算數(shù)運算滿足交換律、分配律、結(jié)合律模的加和乘存在單位元和逆元加法的單位元是0，乘法的單位元是1a關(guān)于模m的加法逆元是m-aa關(guān)于模m的乘法逆元是?能在有限的整數(shù)范圍內(nèi)構(gòu)造群、環(huán)和域等重要的代數(shù)結(jié)構(gòu)利用模運算實現(xiàn)移位密碼字母編碼表，將字母A－Z對應(yīng)于數(shù)字0－25移位密碼加密應(yīng)用假設(shè)移位密碼的密鑰為K=11，明文為wewillmeetatmidnight首先根據(jù)編碼表將明文轉(zhuǎn)換成整數(shù)串

224228111112441901912831386719然后將每個數(shù)與11相加，結(jié)果模26，得到

71571922222315154114231914241917184最后根據(jù)編碼表將數(shù)字串轉(zhuǎn)換成字母串，得到

HPHTWWXPPELEXTOYTRSE移位密碼的分析設(shè)有如下密文串

JBCRCLQRWCRVNBJENBWRWN取k=1,2,3...依次嘗試，得到如下不同字母串 iabqbkpqvbpumaidmavqvm(k=1) hzapajopuaptlzhclzupul(k=2) gyzozinotzoskygbkytotk(k=3) fxynyhmnsynrjxfajxsnsj(k=4) ewxmxglmrxmqiweziwrmri(k=5) dvwlwfklqwlphvdyhvqlqh(k=6) cuvkvejkpvkogucxgupkpg(k=7) btujudijoujnftbwftojof(k=8)

astitchintimesavesnine(k=9)移位密碼的安全性分析密鑰空間過小最多嘗試25次，最少嘗試1次，平均嘗試13次代換密碼代換密碼體制的數(shù)學(xué)描述對于密碼體制的五元組（P,C,K,E,D）有P=C=Z26K是由26個數(shù)字0,1,2,...,25的所有可能的置換組成對任意的置換π∈K，定義 eπ(x)=π(x) dπ(y)=π-1(y)π-1表示置換π的逆置換代換密碼加密任取一個置換π，可以得到一個加密函數(shù)，例如下表所示的置換規(guī)則：按照此表可知eπ(a)=X，eπ(b)=N，...abcdefghijklmXNYAHPOGZQWBTnopqrstuvwxyzSFLRCVMUEKJDI代換密碼解密解密函數(shù)是相應(yīng)的逆置換，前例的逆置換可以表示為：可知dπ(A)=d，dπ(B)=l，...試解密MGZVYZLGHCMHJMYXSSFMNHAHYCDLMHAABCDEFGHIJKLMdlryvohezxwptNOPQRSTUVWXYZbgfjqnmuskaci代換密碼的安全性分析密鑰是26個字母的置換，所有可能的置換有26!=403291461126605635584000000種采用窮舉法，假設(shè)每秒可以嘗試1000萬次，需要1012年以上(已經(jīng)超過宇宙的理論壽命)果真如此安全？仿射密碼仿射密碼體制的數(shù)學(xué)描述對于密碼體制的五元組（P,C,K,E,D）有P=C=Z26K={(a,b)∈Z26×Z26:gcd(a,26)=1}對任意的k=(a,b)∈K,x,y∈Z26，定義 ek(x)=(ax+b)mod26 dk(y)=a-1(y-b)mod26gcd(a,26)=1意味著a和26互質(zhì)a-1是a關(guān)于模26乘法的逆仿射密碼a和26互質(zhì)是保證加密函數(shù)為單射函數(shù)的充要條件，否則不同的明文可能被加密成相同的密文例如a=4，b=3則加密函數(shù)為(4x+3)mod26明文字母c對應(yīng)的值為2，加密后為11，對應(yīng)密文字母是L；明文字母p對應(yīng)的值為15，加密后的密文也是L根據(jù)該條件，a可能的取值范圍是12個數(shù) 1,3,5,7,9,11,15,17,19,21,23,25模乘法的逆模乘法的逆求a對于模b乘法的逆，即求x滿足axmodb

＝1，可記做

x＝a-1modb

或x＝a-1

如：3×9＝1×26＋1，則稱9和3對于模26互逆，記做9-1mod26=3或3-1mod26=9將模數(shù)的倍數(shù)加1后分解為兩個數(shù)的乘法，即可得到兩個關(guān)于模數(shù)互逆的數(shù)。仿射密碼當a=1時，仿射密碼即為移位密碼仿射密碼中不同a值對應(yīng)的逆(模26)1-1=1 3-1=9 5-1=21 7-1=1511-1=19 17-1=23 25-1=25簡單的驗證(7×15)mod26=105mod26=17和15在模26下互逆仿射密碼舉例設(shè)仿射密碼的密鑰k=(7,3)，試給出明文hot的加解密過程加密函數(shù)為ek(x)=7x+3解密函數(shù)為dk(y)=7-1(y-3)=15(y-3)=15y-19驗證dk(ek(x))=dk(7x+3)=15(7x+3)-19

=x+45-19=x仿射密碼舉例字母hot對應(yīng)的明文數(shù)值為7,14,19，分別加密如下：(7×7+3)mod26=52mod26=0(7×14+3)mod26=101mod26=23(7×19+3)mod26=136mod26=6三個密文值分別為0,23,6，相應(yīng)的密文為AXG解密過程略仿射密碼安全性分析a可能的取值是12，b有效的取值是26，密鑰空間大小為12×26=312如果將模數(shù)m推廣到一般，則仿射密碼的密鑰空間為mΦ(m)，其中Φ(m)表示m以內(nèi)與m互質(zhì)的數(shù)的個數(shù)，稱為歐拉函數(shù)例如：Φ(26)=12；Φ(60)=16取模數(shù)m=60，則仿射密碼的密鑰空間大小為16×60=960歐拉函數(shù)假定這里pi均為素數(shù)且互不相同，ei是大于0的整數(shù)，則例如60=22×3×5，則Φ(60)=(22-21)×(31-30)×(51-50)=2×2×4=16如果m=p×q(p和q均為素數(shù))則Φ(m)=(p-1)×(q-1)課堂練習(xí)已知仿射密碼的密鑰為k=(3,10)試解密XICFP維吉尼亞密碼16世紀晚期，法國外交官維吉尼亞(Vigenere)發(fā)明，引入了“密鑰”的概念維吉尼亞密碼維吉尼亞密碼體制的數(shù)學(xué)描述對于密碼體制的五元組（P,C,K,E,D）有P=C=K=(Z26)m，m是一個正整數(shù)對任意的k=(k1,k2,...,km)∈K,x=(x1,x2,...,xm)∈P,y=(y1,y2,...,ym)∈C，定義 ek(x)=(x1+k1,x2+k2,...,xm+km) dk(y)=(y1-k1,y2-k2,...,ym-km)以上運算均在Z26上運行(模26)維吉尼亞密碼舉例假設(shè)m=6，密鑰字為CIPHER，加密明文

thiscryptosystemisnotsecure密鑰字對應(yīng)的數(shù)字串為k=(2,8,15,7,4,17)將明文轉(zhuǎn)化為對應(yīng)的數(shù)字，每6個為一組1978182172415191418241819412818131419184220174維吉尼亞密碼舉例使用密鑰字進行模26下的加法運算1978182172415191418242815741728157417+(mod26)21152325680238212215181941281813141918422815741728157417+(mod26)20119191291522825819201742815+(mod26)222519得到相應(yīng)的密文為VPXZGIAXIVWPUBTTMJPWIZITWZT維吉尼亞密碼的安全性密鑰空間大小為26m當m=5時，密鑰空間大小超過1.1×107，已經(jīng)不可能采用手工方法窮舉搜索采用計算機窮舉搜索可能不到1秒鐘希爾(Hill)密碼希爾密碼體制的數(shù)學(xué)描述對于密碼體制的五元組（P,C,K,E,D）有P=C=(Z26)m，m是一個不小于2的正整數(shù)K是定義在Z26上的m×m可逆矩陣的集合取密鑰k∈K，k為一個m×m矩陣，記為(kij)，對x=(x1,x2,...,xm)∈P,y=(y1,y2,...,ym)∈C，定義 ek(x)=xk dk(y)=yk-1k-1表示k的逆矩陣以上運算均在Z26上運行(模26)希爾密碼舉例設(shè)m=2，取密鑰k=每個明文單元使用x=(x1,x2)來表示，對應(yīng)的密文單元用y=(y1,y2)表示，則有 y=xk，即(y1,y2)=(x1,x2)

即 y1=(11x1+3x2)mod26 y2=(8x1+7x2)mod26希爾密碼加密假設(shè)需要加密明文july，則可將明文劃分為如下兩個加密單元(9,20)和(11,24)，分別進行加密變換如下(9,20)=(99+60,72+140)=(3,4)(11,24)=(121+72,88+168)=(11,22)因此密文為DELW希爾密碼解密k的逆矩陣k-1=有x=yk-1，即(x1,x2)=(y1,y2)即x1=(7y1+23y2)mod26x2=(18y1+11y2)mod26希爾密碼解密對密文DELW進行解密即做如下運算(3,4)=(21+92,54+44)=(9,20)(11,22)=(77+506,198+242)=(11,24)如何計算逆矩陣？矩陣運算矩陣的乘法設(shè)A=(ai,j)是一個l×m矩陣，B=(bj,k)是一個m×n矩陣，則定義矩陣的乘法AB=C=(ci,k)C是一個l×n矩陣矩陣乘法不滿足交換律但滿足結(jié)合律矩陣運算單位矩陣m×m的矩陣中，主對角線上的元素均為1，其余元素均為0的矩陣稱為單位矩陣，記為Im對任意l×m矩陣A，有AIm=A；對任意m×n矩陣B，有ImB=B逆矩陣m×m矩陣A的逆矩陣記為A-1，滿足AA-1=A-1A=Im逆矩陣具有唯一性(但不一定存在)矩陣運算m×m階矩陣A=(ai,j)的行列式記為|A|或detA如果A為2×2階矩陣，則 detA=a1,1a2,2-a1,2a2,1如果A為3×3階矩陣，則 detA=a1,1a2,2a3,3+a1,2a2,3a3,1+a1,3a2,1a3,2 -(a1,1a2,3a3,2+a1,2a2,1a3,3+a1,3a2,2a3,1)矩陣運算推廣到一般情況如果A為m×m階矩陣，則其中i1i2...im是整數(shù)1到m的一個排列τ[i1i2...im]表示這個排列的逆序數(shù)遞歸法計算，定義Ai,j表示從A中刪除第i行第j列所得的(m-1)×(m-1)階矩陣，則矩陣求逆矩陣K的逆矩陣存在的充要條件是|K|非零；在模26下，逆矩陣存在的充要條件是|K|與26互素，即gcd(detK,26)=1矩陣求逆方法一：利用矩陣的初等行變換求逆矩陣如矩陣求逆矩陣求逆方法二：K-1=(detK)-1K*K*表示K的伴隨矩陣K*的第i行第j列取值為(-1)i+jdetKji，Kji是刪除K的第j行第i列后形成的矩陣對二階矩陣有矩陣求逆舉例設(shè)矩陣是定義在Z26上的矩陣，可計算detK=7，且(detK)-1=15K的伴隨矩陣為因此K-1存在且為*利用matlab進行矩陣運算定義矩陣，命令行輸入：A=[10,5,12;3,14,21;8,9,11]求矩陣的行列式值，命令行輸入：det(A)求矩陣的逆(非模運算)，命令行輸入：inv(A)求伴隨矩陣，命令行輸入：det(A)*inv(A)mod(det(A)*inv(A),26)課堂練習(xí)已知希爾密碼的解密函數(shù)為試加密明文X=text置換密碼置換密碼體制密碼體制的數(shù)學(xué)描述對于密碼體制的五元組（P,C,K,E,D）有P=C=(Z26)m，m是一個正整數(shù)K是由所有定義在集合{1,2,...,m}上的置換組成對任意的密鑰(即置換)π，定義其中π-1為置換π的逆置換置換密碼置換和逆置換的定義置換是定義在有限集X上的雙射函數(shù)π:X→X,對任意的x∈X，存在唯一的x’∈X，使得π(x’)=x置換π的逆置換定義為π-1:X→X π-1(x)=x’當且僅當π(x’)=x π-1也是X上的一個置換置換密碼舉例設(shè)m=6，密鑰為如下的置換π將兩行對調(diào)并重新排序可得逆置換π-1如下即x123456π(x)351642y123456π-1(y)361524置換密碼舉例使用該密碼加密明文shesellsseashellsbytheseashore首先將明文字母每六個分為一組：shesel|lsseas|hellsb|ythese|ashore對每組字母使用加密變換可得EESLSH|SALSES|LSHBLE|HSYEET|HRAEOS即密文為EESLSHSALSESLSHBLEHSYEETHRAEOS置換密碼的特性置換密碼實際上是希爾密碼的特殊形式給定集合{1,2,...,m}的一個置換π，定義置換π的關(guān)聯(lián)置換矩陣Kπ=(Ki,j)m×m，其元素值為使用矩陣Kπ為密鑰的希爾密碼等價于使用置換π為密鑰的置換密碼，且置換密碼的特性前面置換密碼的例子中，等價的希爾密碼加密密鑰為加密函數(shù)為eπ(x)=xKπ =(x1,x2,x3,x4,x5,x6) =(x3,x5,x1,x6,x4,x2)置換密碼的特性解密密鑰為解密函數(shù)為dπ(y)=yKπ-1 =(y1,y2,y3,y4,y5,y6) =(y3,y6,y1,y5,y2,y4)流密碼前面的密碼體制中，連續(xù)的明文元素使用相同的密鑰K來加密y=y1y2...=ek(x1)ek(x2)...這種類型的密碼體制稱為分組密碼分組密碼的不足需要設(shè)計復(fù)雜的加密函數(shù)以提高安全性經(jīng)常需要對明文進行填充(padding)操作以確保分組長度完整如果k較短，則容易遭到窮舉攻擊流密碼設(shè)計思路將明文看作字符串或比特串，并逐字符或者逐位進行加密為了防止密鑰窮舉，使用和明文信息一樣長的密鑰(無限)流z=z1,z2...進行加密這種密碼體制稱為流密碼(或序列密碼)可以使用非常簡單的加密算法(如簡單的異或運算)關(guān)鍵是如何生成密鑰流流密碼的代表弗納姆(Vernam)密碼1918年，GillbertVernam建議密鑰與明文一樣長并且沒有統(tǒng)計關(guān)系的密鑰內(nèi)容，他采用的是二進制數(shù)據(jù)：加密：Ci=Pi⊕Ki

解密：Pi=Ci⊕Ki關(guān)鍵：構(gòu)造和消息一樣長的隨機密鑰異或運算位的異或運算0⊕0=0,0⊕1=1,1⊕0＝1,1⊕1=0異或運算等價模2加法運算特性：兩次異或運算以后還原，可設(shè)計加密和脫密完全相同的函數(shù)。流密碼特點運算簡單實時性強安全性依賴與密鑰流的產(chǎn)生方法流密碼的分類按密鑰的周期性分類周期流密碼；存在某個固定的正整數(shù)r，使得密鑰流每隔r個字符（或者比特）以后重復(fù)非周期流密碼對任何正整數(shù)密鑰流都不重復(fù)如一次一密亂碼本流密碼的分類按密鑰的產(chǎn)生方式分類同步流密碼密鑰流的產(chǎn)生獨立于消息流;例如分組密碼的OFB(輸出反饋)模式異步流密碼每一個密鑰字符是由前面n個明文或密文字符推導(dǎo)出來的，其中n為定值。例如分組密碼的CFB(密碼反饋)模式同步流密碼使用某種算法，由一個初始密鑰變換出和明文串相互獨立的密鑰流。定義如下：同步流密碼是一個六元組(P,C,K,L,E,D)和一個函數(shù)g，且滿足如下條件1P,C,K分別是明文、密文、密鑰的有限集2L是密鑰流字母表有限集3g是密鑰流生成器，g使用密鑰k∈K作為輸入，產(chǎn)生無限長的密鑰流Z=z1z2...，其中zi∈L4對任意的z∈L，都有一個加密規(guī)則(函數(shù))ez:P→C∈E和相應(yīng)的解密規(guī)則(函數(shù))dz:C→P∈D，并且對每個明文x∈P滿足 dz(ez(x))=x流密碼和分組密碼的關(guān)系分組密碼可以看做流密碼的特殊情況如維吉尼亞密碼，可以看做是一種短周期的同步流密碼 ek(x)=(x1+k1,x2+k2,...,xm+km) dk(y)=(y1-k1,y2-k2,...,ym-km)密鑰流定義為即密鑰流是周期為m的密鑰序列k1k2...kmk1k2...kmk1k2...km...分組密碼可以用于生成密鑰序列密鑰流的產(chǎn)生理想的密鑰流是隨機不重復(fù)的真隨機拋硬幣、擲骰子、噪聲發(fā)生器收發(fā)雙方難以同步無周期性密鑰和密文等長一次一密亂碼本難以在高帶寬的信道上使用密鑰流的產(chǎn)生真正的隨機序列往往難以實用，實際多用線性遞歸關(guān)系產(chǎn)生偽隨機序列例如設(shè)m=4，(a1,a2,a3,a4)為(0,0,0,1)密鑰流按如下線性遞歸關(guān)系產(chǎn)生：ai+4=(ai+ai+3)mod2 (等價于ai+4=ai⊕ai+1)產(chǎn)生的密鑰序列為a1a2a3a4a5....，即00011110101100100011110101...周期為24-1=15(a1,a2,a3,a4)通常被稱為初始向量密鑰流的產(chǎn)生這種方式可以使用硬件輕易實現(xiàn)，此硬件稱為線性反饋移位寄存器(LFSR,LinearFeedbackShiftRegister)anan-1a2a1......⊕⊕⊕=1c0=1輸出{ak}（a1，

a2，...

，an）輸出序列為{ak}＝a1a2...

an...ai(t+1)=ai+1(t)an(t+1)=cna1(t)⊕cn-1a2(t)⊕...⊕c1an(t)ai(t+1)=ai+1(t)a4(t+1)=a1(t)⊕a4(t)ta4a3a2a1ta4a3a2a101000901101110010001121110111001311111201004011113001051011140001601011510007101016110081101...............a4a3a2a1⊕輸出{ak}c4=1c1=1返回

LFSR示例說明周期為24－1＝15cn＝1的n級LFSR其輸出序列為周期序列，且周期數(shù)r滿足r≤2n－1若n級LFSR的輸出序列的周期達到最大2n－1，則稱之為m序列f(x)=c0+c1x+c2x2+...+cnxn描述LFSR的反饋連接狀態(tài)，稱為特征多項式可以證明，一個n級LFSR能產(chǎn)生m序列的充要條件是它的特征多項式為一個n次本原多項式本原多項式若一個n次多項式f(x)的階為2n－1，即滿足條件：f(x)為既約多項式f(x)可整除（x2n-1＋1)f(x)不能整除（xp＋1)，其中p<2n－1eg.n=4，周期為24－1＝15，其特征多項式是能整除(x15+1)的4次本原多項式x15+1=(x+1)(x2+x+1)(x4+x+1)(x4+x3+1)(x4+x3+x2+x+1)由于x4+x3+x2+x+1|x5＋1，所以本原多項式為，x4+x+1和x4+x3+1，選擇f(x)＝x4+x+1，即c4＝c1＝c0＝1見前例本原多項式n2n-1λ(n)n2n-1λ(n)1111120471762311240951443721381916304152141638375653161532767180066361665535204871271817131071771082551618262143777695114819524287275941010236020104857524000

可以產(chǎn)生λ(n)×2n-1種密鑰流m序列的特性Golomb提出0-1序列的隨機性公設(shè)（1）若r是奇數(shù)，則0-1序列的一個周期內(nèi)0的個數(shù)比1的個數(shù)多一個或少一個；若r是偶數(shù)，則其個數(shù)相等。（2）在長度為r的周期內(nèi)，1游程的個數(shù)為游程總數(shù)的1/2，2游程的個數(shù)占總數(shù)的1/22，一次，c游程的個數(shù)占總數(shù)的1/2c。而且，對于任意長度，0的游程個數(shù)和1的游程個數(shù)相等。（3）自相關(guān)函數(shù)是一個常數(shù)。m序列的特性偽隨機序列游程

eg.0-1序列00110111，00稱為0的2游程；自相關(guān)函數(shù)

eg.假定s1s2s3...為0-1序列，r為其周期，即r為滿足sm+r＝sm的最小正整數(shù)，若有兩個子序列

s1，s2，s3，...，srs1＋τ，s2＋τ

，s3＋τ

，...，sr＋τ

定義R（τ）＝（nτ－dτ

）/r

其中：nτ為該兩個子序列中相應(yīng)位相同的數(shù)目，不同的位的數(shù)目即為dτ

＝r－nττ=0，有

R（τ）＝1m序列的特性平衡特性

m序列中1的個數(shù)比0的個數(shù)多1游程特性

1的最大游程為n游程，有且僅有1個，因為會出現(xiàn)1個全1狀態(tài)111...1，那么會出現(xiàn)串01......10，則經(jīng)歷狀態(tài)為

1...10

，1...1，01...1

不存在1的n-1游程，會出現(xiàn)1個0的n-1游程，則出現(xiàn)串10...01，經(jīng)歷狀態(tài)0...01

和10...0

當n>2，設(shè)r為不超過n-2的任一正整數(shù)，則任何1的r游程表示存在串01...10（r+2位），其游程數(shù)目為2n-r-2，于是，在每一周期中出現(xiàn)1的游程個數(shù)為

1＋＝2n-2

同樣，出現(xiàn)0的游程個數(shù)為2n-2

，游程總數(shù)為2n-1eg.n=4，000111101011001；m序列的特性位移相加特性

m序列和它的位移序列模2相加后所得序列仍是該m序列的某個位移序列。

設(shè)序列{ak}為m序列，且滿足遞推關(guān)系：

ah+n=cnah

⊕cn-1ah+1

⊕...⊕c1ah+n-1

位移τ位：ah+n+τ

=cnah+τ

⊕cn-1ah+1+τ

⊕...⊕c1ah+n-1+τ

，則ah+n

⊕ah+n+τ

＝cn（ah⊕

ah+τ

）⊕cn-1（ah+1⊕

ah+1+τ

）

⊕...⊕c1（ah+n-1⊕

ah+n-1+τ

）

自相關(guān)特性

設(shè)兩子串為{at}和{at+τ}，則{at}⊕{at+τ}中為0的位的數(shù)目正好是兩個子串中對應(yīng)位相同的位數(shù)，則：

R（τ）＝（nτ－dτ

）/r＝－1/2n－1（τ≠0)

當τ＝0時，R（τ）＝1

利用LFSR設(shè)計加密算法同步序列密碼實現(xiàn)⊕anan-1a2a1......⊕⊕=1c0=1輸出{ak}密鑰流⊕明文密文異步流密碼同步流密碼存在周期問題異步流密碼思路密鑰流z的產(chǎn)生不但與密鑰K有關(guān)，而且還與明文元素(x1,x2,...,xi-1)或密文元素(y1,y2,...,yi-1)有關(guān)自動密鑰密碼通過K和明文產(chǎn)生密鑰流自動密鑰密碼自動密鑰密碼體制的數(shù)學(xué)描述自動密鑰密碼是一個六元組(P,C,K,L,E,D)，滿足以下條件P=C=K=L=Z26密鑰流定義：z1=k∈K，zi=xi-1，i≥2對任意的z∈K，x,y∈Z26，定義 ez(x)=(x+z)mod26 dz(y)=(y-z)mod26自動密鑰密碼舉例假設(shè)k=8，明文為rendezvous加密過程如下：首先將明文轉(zhuǎn)換為整數(shù)序列:17413342521142018根據(jù)z1=k=8，zi=xi-1得到密鑰流為：8174133425211420將對應(yīng)的元素相加并模26得到：2521171673209812字母形式的密文為ZVRQHDUJIM解密過程略

利用LFSR設(shè)計加密算法序列密碼密碼反饋加密⊕anan-1a2a1......⊕⊕=1⊕明文m密文c加密過程：e1＝m1＋，e2＝m2＋＋c1e1

，......ek＝mk＋＋1≤k≤n

en+1＝mn+1＋，en+h＝mn+h＋

利用LFSR設(shè)計加密算法序列密碼密碼反饋解密⊕anan-1a2a1......⊕⊕=1⊕明文m密文c解密密鑰和加密密鑰相同，都是系數(shù)c1，c2，...，cn和初始狀態(tài)(a1，a2，...an）密碼分析前面從窮舉密鑰的角度簡單分析了各類密碼體制的安全性，其前提是分析者知道使用的密碼體制(密碼算法)。如果不知道密碼體制，分析工作將困難得多將安全性建立在保持算法的秘密基礎(chǔ)之上，這類算法稱為受限制的算法缺陷：無法用于大的或經(jīng)常變換用戶的組織。如果加脫密的保密性是基于保持密鑰的秘密，而算法本身可以完全公開，則稱為基于密鑰的算法密碼分析目標密碼分析學(xué)是在不知道密鑰的情況下，恢復(fù)出明文的科學(xué)。分析者是在已知密碼體制（密碼算法及其實現(xiàn)的全部詳細資料）的前提下來破譯使用的密鑰。從分析者掌握的條件區(qū)分，常用的密碼分析攻擊有四類密碼分析方法四類常用的密碼分析攻擊方式唯密文攻擊(Ciphertext-onlyAttack)分析者有一些消息的密文，這些密文都用同一加密算法加密，任務(wù)是盡可能恢復(fù)這些密文，或推算出加密的密鑰。已知明文攻擊(Known-plaintextAttack)分析者不但有一些消息的密文，還知道這些密文對應(yīng)的明文，任務(wù)是推算出加密的密鑰，或推導(dǎo)出可以對新密文進行解密的算法密碼分析方法四類常用的密碼分析攻擊方式選擇明文攻擊(Chosen-plaintextAttack)分析者可獲得對加密機的暫時訪問，因此他能自由選擇明文串并構(gòu)造出相應(yīng)的密文串，任務(wù)是推算出加密的密鑰，或推導(dǎo)出可以對新密文進行解密的算法選擇密文攻擊(Chosen-ciphertextAttack)分析者可獲得對解密機的暫時訪問，因此他能自由選擇密文串并構(gòu)造出相應(yīng)的明文串，任務(wù)是推算出加密的密鑰，或推導(dǎo)出可以對新密文進行解密的算法課堂練習(xí)截獲使用移位密碼加密的密文如下 MQTSVXERXQIWWEKI試分析其對應(yīng)的明文唯密文攻擊分析古典密碼最困難的分析條件在密文片段足夠長的情況下，能分析大多數(shù)古典密碼通常需要用到英文字母的頻率分析和反復(fù)猜測能有效分析單表替代密碼多表替代難度加大只能分析可閱讀的文本數(shù)據(jù)借助計算機能大大提高分析效率英文字母頻率分析利用26個字母在英文文字出現(xiàn)的不同頻率猜測單表替代字母英文字母頻率分析26個字母在英文語言中出現(xiàn)的頻率排序E出現(xiàn)的頻率遠高于其他字母其次為T、A、O、I、N、S、H、R再次為D、L更次為C、U、M、W、F、G、Y、P、B最次為V、K、J、X、Q、Z許多雙字母的固定序列經(jīng)常出現(xiàn)TH、HE、IN、ER、AN、RE、ED、ON、ES、ST、EN、AT、TO、NT、HA、ND、OU、EA、NG、AS、OR、TI、IS、ET、IT、AR、TE、SE、HI、OF英文字母頻率分析還有一些經(jīng)常出現(xiàn)的3字母固定序列THE、ING、AND、HER、ERE、ENT、THA、NTH、WAS、ETH、FOR、DTH根據(jù)經(jīng)驗，有些字母不可能組合出現(xiàn)在一個單詞中，如果出現(xiàn)可作為單詞邊界進行分析簡單代替密碼的分析原理根據(jù)密文字母出現(xiàn)頻率的高低進行猜測和驗證得到的密文越長，越符合統(tǒng)計規(guī)律仿射密碼的密碼分析仿射密碼體制的數(shù)學(xué)描述對于密碼體制的五元組（P,C,K,E,D）有P=C=Z26K={(a,b)∈Z26×Z26:gcd(a,26)=1}對任意的k=(a,b)∈K,x,y∈Z26，定義 ek(x)=(ax+b)mod26 dk(y)=a-1(y-b)mod26gcd(a,26)=1意味著a和26互質(zhì)a-1是a關(guān)于模26乘法的逆分析目標：根據(jù)密文得到a和b的值分析方法：首先分析出現(xiàn)頻率最高的字符，只需要猜中兩個字母的代替，就能解出a和b仿射密碼分析舉例得到仿射密碼的密文如下FMXVEDKAPHEFRBNDKRXRSREFMORUD SDKDVSHVUFEDKAPRKDLYEVLRHHRH分析密文中每個字母的出現(xiàn)頻數(shù)記錄如下字母頻數(shù)字母頻數(shù)字母頻數(shù)字母頻數(shù)字母頻數(shù)A2B1C0D7E5F4G0H5I,J0K5L2M2N1O1P2Q0R8S3T0U2V4W0X2Y1Z0仿射密碼分析舉例以上密文中出現(xiàn)的最大頻數(shù)的幾個密文字母依次是R、D、E、H、K、S、F、V假設(shè)R是e的加密，D是t的加密即ek(4)=17,ek(19)=3，因為ek(x)=ax+b，得到方程組解方程組可知a=6,b=19，因為a不滿足與26互質(zhì)的條件，因此猜測錯誤仿射密碼分析舉例以上密文中出現(xiàn)的最大頻數(shù)的幾個密文字母依次是R、D、E、H、K、S、F、V再假設(shè)R是e的加密，E是t的加密，繼續(xù)使用該方法得到a=13仍不滿足與26互質(zhì)的條件再假設(shè)H是t的加密，得到a=8仍無效再假設(shè)K是t的加密，得到a=3,b=5，使用此密鑰嘗試解密得到可閱讀的明文為algorithmsarequitegeneraldefinitionsofarithmeticprocesses代換密碼的密碼分析代換密碼體制的數(shù)學(xué)描述對于密碼體制的五元組（P,C,K,E,D）有P=C=Z26K是由26個數(shù)字0,1,2,...,25的所有可能的置換組成對任意的置換π∈K，定義 eπ(x)=π(x) dπ(y)=π-1(y)π-1表示置換π的逆置換分析目標：根據(jù)密文得到置換π分析技巧：先分析頻率高的密文，再根據(jù)英文單詞中的字母組合規(guī)律進行分析代換密碼分析舉例得到代換密碼的密文如下YIFQFMZRWQFYVECFMDZPCVMRZWNMDZVEJBTXCDDUMJNDIFEFMDZCDMQZKCEYFCJMYRNCWJCSZREXCHZUNMXZNZUCDRJXYYSMRTMEYIFZWDYVZVYFZUMRZCRWNZDZJJXZWGCHSMRNMDHNCMFQCHZJMXJZWIEJYUCFWDJNZDIR代換密碼分析舉例分析密文中各字母出現(xiàn)的頻數(shù)Z出現(xiàn)頻率最高其次是C,D,F,J,M,R,Y字母頻數(shù)字母頻數(shù)字母頻數(shù)字母頻數(shù)字母頻數(shù)A0B1C15D13E7F11G1H4I5J11K1L0M16N9O0P1Q4R10S3T2U,V5W8X6Y10Z20代換密碼分析舉例Z出現(xiàn)的頻率遠高于其他字母，推測dk(Z)=e以Z開頭的雙字母中，ZW出現(xiàn)的次數(shù)最多，推測dk(W)=d；以W結(jié)尾的雙字母中，RW出現(xiàn)數(shù)次且R也多次出現(xiàn)，推測dk(R)=n；NZ出現(xiàn)多次而ZN未出現(xiàn)，推測dk(N)=h根據(jù)以上猜測得到一些殘缺的明文如ne?ndhe(其密文為RZCRWNZ)，在英語字典中搜索不到匹配的單詞，猜測?為a，即dk(C)=a代換密碼分析舉例nh(對應(yīng)密文為RN)不可能出現(xiàn)在一個單詞中，因此密文中的RNM解密為nh?，其中h是單詞的開頭且后面應(yīng)該是一個元音字母M在密文中出現(xiàn)的頻率很高，因此對應(yīng)i或o；考慮到ai出現(xiàn)的頻率高于ao，推測dk(M)=io是較常出現(xiàn)的字母，對應(yīng)的密文應(yīng)該是D,F,J,Y中的一個，因為密文中出現(xiàn)了CDM/CFM/CJM這樣的組合，推測dk(Y)=o(單詞中不會出現(xiàn)aoi)代換密碼分析舉例剩下的三個高頻密文字母D,F,J，應(yīng)該是明文r,s,t的某種映射密文組合NMD(hi?)多次出現(xiàn)，猜測dk(D)=s密文組合HCMF(hai?)出現(xiàn)，猜測dk(F)=r剩下dk(J)=t密文組合HNCMF(?hair)出現(xiàn)，猜測dk(H)=c代換密碼分析舉例目前猜測出的代替規(guī)則有Z-e，W-d，R-n，N-h，C-a，M-i，Y-o，D-s，F(xiàn)-r，J-t，H-c根據(jù)該規(guī)則部分解密密文如下o-r-riend-ro--arise-a-inedhise--t---ass-itYIFQFMZRWQFYVECFMDZPCVMRZWNMDZVEJBTXCDDUMJhs-r-riseasi-d-a-orationhadta-en--ace-hi-eNDIFEFMDZCDMQZKCEYFCJMYRNCWJCSZREXCHZUNMXZhe-asnt-oo-in-i-o-redso-e-ore-ineandhesettNZUCDRJXYYSMRTMEYIFZWDYVZVYFZUMRZCRWNZDZJJ-ed-ac-inhischair-aceti-ted--to-ardsthes-nXZWGCHSMRNMDHNCMFQCHZJMXJZWIEJYUCFWDJNZDIR代換密碼分析舉例最后從英文單詞、語法等語言規(guī)律猜測其他代替規(guī)則，最終得到明文OurfriendfromParisexaminedhisemptyglasswithsurprise,asifevaporationhadtakenplacewhilehewasn’tlooking.Ipouredsomemorewineandhesettledbackinhischair,facetilteduptowardsthesun維吉尼亞密碼的密碼分析維吉尼亞密碼體制的數(shù)學(xué)描述對于密碼體制的五元組（P,C,K,E,D）有P=C=K=(Z26)m，m是一個正整數(shù)對任意的k=(k1,k2,...,km)∈K,x=(x1,x2,...,xm)∈P,y=(y1,y2,...,ym)∈C，定義 ek(x)=(x1+k1,x2+k2,...,xm+km) dk(y)=(y1-k1,y2-k2,...,ym-km)以上運算均在Z26上運行(模26)分析目標：根據(jù)密文得到k1,k2,...,km維吉尼亞密碼的密碼分析維吉尼亞密碼的分析難點多表替代，使簡單的頻率分析方法失效如果知道密鑰字長度m，可以分解為m個單表替代密碼分析任務(wù)確認密鑰字長度m是關(guān)鍵Kasiski法重合指數(shù)法維吉尼亞密碼的密碼分析Kasiski測試法確定密鑰字長度m19世紀普魯士少校Kasiski提出可粗略猜測m，密文越長越準確基本步驟1.在密文中標出重復(fù)的三個或多個字符結(jié)構(gòu)；2.對每一個字符結(jié)構(gòu)，記下結(jié)構(gòu)的起始位置；3.計算相鄰的起始點的距離；4.對每個距離求出所有因數(shù)；5.密鑰的長度為步驟4中出現(xiàn)的某一因數(shù)維吉尼亞密碼的密碼分析Kasiski測試法舉例明文：wearediscoveredsaveyourself密鑰：deceptive密文：ZICVTWQNGRZGVTWAVZHCQYGLMGJ測試過程：1.在密文中標出重復(fù)的字符結(jié)構(gòu)——VTW；2.兩個字符結(jié)構(gòu)的起始位置分別為4和13；3.兩個起始點的距離是9；4.9的因數(shù)有3和9；5.根據(jù)步驟4出現(xiàn)的因數(shù)，確定密鑰的可能長度是3位或9位。維吉尼亞密碼的密碼分析重合指數(shù)法確定密鑰字長度m重合指數(shù)的定義一個字母串X中隨機取出兩個字母，這兩個字母恰好相同的概率，記為Ic(X)對于完全隨機的字母串，Ic(X)=26*(1/26)2=1/26≈0.038對于英文文本，其中pi是字母表中第i個字母在英文中出現(xiàn)的概率重合指數(shù)的特點單表代替密碼中，密文的重合指數(shù)和明文相同維吉尼亞密碼的密碼分析重合指數(shù)法確定密鑰字長度m密文重合指數(shù)的計算方法對于長度為n的密文串X，首先統(tǒng)計密文字母A,B,C,...,Z出現(xiàn)的頻數(shù)(次數(shù))，記為f0,f1,f2,...,f25計算維吉尼亞密碼的密碼分析重合指數(shù)法確定密鑰字長度m分析原理假設(shè)密文串為Y=y1y2...yn，m是密鑰字長度將Y分割成m個子串Y1=y1y1+my1+2m...Y2=y2y2+my2+2m......Ym=ymy2my3m...對于每個Yi，其密文采用的是單表代替方法(相同的密文對應(yīng)相同的明文)，其重合指數(shù)Ic(Yi)應(yīng)接近0.065通過嘗試不同的m，找到重合指數(shù)最接近0.065的那個維吉尼亞密碼分析舉例得到維吉尼亞密碼加密的密文如下CHREEVOAHMAERATBIAXXWTNXBEEOPHBSBQMQEQERBWRVXUOAKXAOSXXWEAHBWGJMMQMNKGRFVGXWTRZXWIAKLXFPSKAUTEMNDCMGTSXMXBTUIADNGMGPSRELXNJELXVRVPRTULHDNQWTWDTYGBPHXTFALJHASVBFXNGLLCHRZBWELEKMSJIKNBHWRJGNMGJSGLXFEYPHAGNRBIEQJTAMRVLCRREMNDGLXRRIMGNSNRWCHRQHAEYEVTAQEBBIPEEWEVKAKOEWADREMXMTBHHCHRTKDNVRZCHRCLQOHPWQAIIWXNRMGWOIIFKEE維吉尼亞密碼分析舉例Kasiski測試法分析密文串CHR出現(xiàn)在1,166,236,276,286這幾個位置，到第一個位置的距離分別是165,235,275,285，他們只有一個公因子5，故猜測密鑰字長度為5維吉尼亞密碼分析舉例重合指數(shù)法分析嘗試不同的密鑰字長度，計算密文的重合指數(shù)mIc(Y1)Ic(Y2)Ic(Y3)Ic(Y4)IcY510.04520.0460.04130.0430.0500.04740.0420.03900450.04050.0630.0680.0690.0610.072維吉尼亞密碼分析舉例分析密鑰字確定密鑰字長度后，可以使用頻率分析方法分別解密Y1,Y2,...,YmY1=CVABWEBQBUAWWQRWWXANTBDPXXRDWBFAX CWMNJJFAIACNRNCATBWKDMCDCQQXWKY2=HOEITESEWOOEGMFTIFUDSTNSNVTNDPASNHES BGSEGEMRDRSHEAIEORTHNHOANOEY3=RARANOBQRASAJNVRAPTCXUGRJRUQTHLVGRLJH NGYNQRRGINRYQPVEEBRVRHIRIEY4=EHAXXPQEVKXHMKGZKSEMMIMEEVLWYXJBLZEI WMLPRJVELMRQEEEKWMHTRCPIMIY5=EMTXBHMR