1

信息安全原理與應(yīng)用第二章密碼學(xué)基礎(chǔ)本章由王昭主寫1信息安全原理與應(yīng)用12內(nèi)容提要基本概念和術(shù)語(yǔ)密碼學(xué)的歷史古典密碼2內(nèi)容提要基本概念和術(shù)語(yǔ)23基本概念密碼學(xué)(Cryptology)：是研究信息系統(tǒng)安全保密的科學(xué)。密碼編碼學(xué)(Cryptography)：主要研究對(duì)信息進(jìn)行編碼，實(shí)現(xiàn)對(duì)信息的隱蔽。密碼分析學(xué)(Cryptanalytics)：主要研究加密消息的破譯或消息的偽造。3基本概念密碼學(xué)(Cryptology)：是研究信息系統(tǒng)安全34基本術(shù)語(yǔ)消息被稱為明文(Plaintext)。用某種方法偽裝消息以隱藏它的內(nèi)容的過(guò)程稱為加密(Encrtption)，被加密的消息稱為密文(Ciphertext)，而把密文轉(zhuǎn)變?yōu)槊魑牡倪^(guò)程稱為解密(Decryption)。對(duì)明文進(jìn)行加密操作的人員稱作加密員或密碼員(Cryptographer)。密碼算法(CryptographyAlgorithm):是用于加密和解密的數(shù)學(xué)函數(shù)。密碼員對(duì)明文進(jìn)行加密操作時(shí)所采用的一組規(guī)則稱作加密算法(EncryptionAlgorithm)。所傳送消息的預(yù)定對(duì)象稱為接收者(Receiver)。接收者對(duì)密文解密所采用的一組規(guī)則稱為解密算法(DecryptionAlgorithm)。4基本術(shù)語(yǔ)消息被稱為明文(Plaintext)。用某種方法偽45凱撒密表公元前54年，古羅馬長(zhǎng)官凱撒明文字母abcdefghijklmnopqrstuvwxyz密文字母DEFGHIJKLMNOPQRSTUVWXYZABC有一個(gè)拉丁文句子omniagalliaestdivisainpartestres(高盧全境分為三個(gè)部分）RPQLDJDOOLDHVWGLYLVDLQSDUWHVWUHV把明文的拉丁字母逐個(gè)代之以相應(yīng)的希臘字母5凱撒密表公元前54年，古羅馬長(zhǎng)官凱撒56

加解密過(guò)程示意圖加密和解密算法的操作通常都是在一組密鑰的控制下進(jìn)行的，分別稱為加密密鑰(EncryptionKey)和解密密鑰(DecryptionKey)。667

密碼學(xué)的目的：A和B兩個(gè)人在不安全的信道上進(jìn)行通信，而攻擊者O不能理解他們通信的內(nèi)容。加密通信的模型

7加密通信的模型

78密碼體制密碼體制：它是一個(gè)五元組（P,C,K,E,D)滿足條件：（1）P是可能明文的有限集；（明文空間）（2）C是可能密文的有限集；（密文空間）（3）K是一切可能密鑰構(gòu)成的有限集；（密鑰空間）（4）任意k∈K，有一個(gè)加密算法和相應(yīng)的解密算法，使得和分別為加密解密函數(shù)，滿足dk(ek(x))=x，這里x∈P。8密碼體制密碼體制：它是一個(gè)五元組（P,C,K,E,D)滿足89密碼算法分類-i按照保密的內(nèi)容分:受限制的（restricted）算法：算法的保密性基于保持算法的秘密。

基于密鑰（key-based）的算法：算法的保密性基于對(duì)密鑰的保密。9密碼算法分類-i按照保密的內(nèi)容分:910密碼算法分類-ii基于密鑰的算法，按照密鑰的特點(diǎn)分類：對(duì)稱密碼算法（symmetriccipher)：又稱傳統(tǒng)密碼算法（conventionalcipher)，就是加密密鑰和解密密鑰相同，或?qū)嵸|(zhì)上等同，即從一個(gè)易于推出另一個(gè)。又稱秘密密鑰算法或單密鑰算法。非對(duì)稱密鑰算法（asymmetriccipher）:加密密鑰和解密密鑰不相同，從一個(gè)很難推出另一個(gè)。又稱公開(kāi)密鑰算法（public-keycipher）

。公開(kāi)密鑰算法用一個(gè)密鑰進(jìn)行加密,而用另一個(gè)進(jìn)行解密.其中的加密密鑰可以公開(kāi)，又稱公開(kāi)密鑰（publickey)，簡(jiǎn)稱公鑰。解密密鑰必須保密，又稱私人密鑰（privatekey）私鑰，簡(jiǎn)稱私鑰。10密碼算法分類-ii基于密鑰的算法，按照密鑰的特點(diǎn)分類：1011密碼算法分類-iii按照明文的處理方法：分組密碼（blockcipher）:將明文分成固定長(zhǎng)度的組，用同一密鑰和算法對(duì)每一塊加密，輸出也是固定長(zhǎng)度的密文。流密碼（streamcipher）:又稱序列密碼。序列密碼每次加密一位或一字節(jié)的明文，也可以稱為流密碼。序列密碼是手工和機(jī)械密碼時(shí)代的主流11密碼算法分類-iii按照明文的處理方法：1112密碼算法分類-iv對(duì)稱密鑰密碼又可分為：分組密碼

每次對(duì)一塊數(shù)據(jù)加密多數(shù)網(wǎng)絡(luò)加密應(yīng)用

DES、IDEA、RC6、Rijndael流密碼每次對(duì)一位或一字節(jié)加密手機(jī)

One-timepadding、Vigenére、Vernam12密碼算法分類-iv對(duì)稱密鑰密碼又可分為：1213密碼算法分類-v公開(kāi)密鑰密碼：大部分是分組密碼，只有概率密碼體制屬于流密碼每次對(duì)一塊數(shù)據(jù)加密數(shù)字簽名,身份鑒別

RSA、ECC、ElGamal

加密解密速度慢13密碼算法分類-v公開(kāi)密鑰密碼：1314Kerckhoff原則1883年Kerchoffs第一次明確提出了編碼的原則：加密算法應(yīng)建立在算法的公開(kāi)不影響明文和密鑰的安全的基礎(chǔ)上。這一原則已得到普遍承認(rèn)，成為判定密碼強(qiáng)度的衡量標(biāo)準(zhǔn)，實(shí)際上也成為古典密碼和現(xiàn)代密碼的分界線。14Kerckhoff原則1883年Kerchoffs第一次1415密碼分析假設(shè)破譯者O是在已知密碼體制的前提下來(lái)破譯正在使用的密鑰，這個(gè)假設(shè)稱為Kerckhoff原則。最常見(jiàn)的破解類型如下：唯密文攻擊：O具有密文串y。已知明文攻擊:O具有明文串x和相應(yīng)的密文y。選擇明文攻擊：O可獲得對(duì)加密機(jī)的暫時(shí)訪問(wèn)，因此他能選擇明文串x并構(gòu)造出相應(yīng)的密文串y。選擇密文攻擊：O可暫時(shí)接近密碼機(jī)，可選擇密文串y，并構(gòu)造出相應(yīng)的明文x。

這一切的目的在于破譯出密鑰或密文15密碼分析假設(shè)破譯者O是在已知密碼體制的前提下來(lái)破譯正在使1516

內(nèi)容提要基本概念和術(shù)語(yǔ)密碼學(xué)的歷史古典密碼16內(nèi)容提要基本概念和術(shù)語(yǔ)1617密碼學(xué)的起源和發(fā)展-i三個(gè)階段：1949年之前密碼學(xué)是一門藝術(shù)1949～1975年密碼學(xué)成為科學(xué)1976年以后密碼學(xué)的新方向——公鑰密碼學(xué)17密碼學(xué)的起源和發(fā)展-i三個(gè)階段：1718密碼學(xué)的起源和發(fā)展-ii1949年之前:

古典密碼（classicalcryptography)

密碼學(xué)還不是科學(xué)，而是藝術(shù)出現(xiàn)一些密碼算法和加密設(shè)備密碼算法的基本手段代替&置換（substitution&permutation）出現(xiàn)，針對(duì)的是字符簡(jiǎn)單的密碼分析手段出現(xiàn)18密碼學(xué)的起源和發(fā)展-ii1949年之前:1819密碼學(xué)的起源和發(fā)展-iii1949～1975年:計(jì)算機(jī)使得基于復(fù)雜計(jì)算的密碼成為可能1949年Shannon的“TheCommunicationTheoryofSecretSystems”1967年DavidKahn的《TheCodebreakers》1971-73年IBMWatson實(shí)驗(yàn)室的HorstFeistel等的幾篇技術(shù)報(bào)告數(shù)據(jù)的安全基于密鑰而不是算法的保密19密碼學(xué)的起源和發(fā)展-iii1949～1975年:1920密碼學(xué)的起源和發(fā)展-iv1976年以后:

1976年Diffie&Hellman的“NewDirectionsinCryptography”提出了不對(duì)稱密鑰密碼1977年Rivest，Shamir&Adleman提出了RSA公鑰算法90年代逐步出現(xiàn)橢圓曲線等其他公鑰算法

公鑰密碼使得發(fā)送端和接收端無(wú)密鑰傳輸?shù)谋Ｃ芡ㄐ懦蔀榭赡埽?0密碼學(xué)的起源和發(fā)展-iv1976年以后:2021密碼學(xué)的起源和發(fā)展-v1976年以后:

對(duì)稱密鑰密碼算法進(jìn)一步發(fā)展1977年DES正式成為標(biāo)準(zhǔn)80年代出現(xiàn)“過(guò)渡性”的“postDES”算法，如IDEA,RCx,CAST等90年代對(duì)稱密鑰密碼進(jìn)一步成熟Rijndael,RC6,MARS,Twofish,Serpent等出現(xiàn)2001年Rijndael成為DES的替代者21密碼學(xué)的起源和發(fā)展-v1976年以后:2122

內(nèi)容提要基本概念和術(shù)語(yǔ)密碼學(xué)的歷史古典密碼22內(nèi)容提要基本概念和術(shù)語(yǔ)2223密碼算法的安全性無(wú)條件安全（Unconditionallysecure）無(wú)論破譯者有多少密文，他也無(wú)法解出對(duì)應(yīng)的明文，即使他解出了，他也無(wú)法驗(yàn)證結(jié)果的正確性。One-timepad計(jì)算上安全（Computationallysecure）破譯的代價(jià)超出信息本身的價(jià)值。破譯的時(shí)間超出了信息的有效期。23密碼算法的安全性無(wú)條件安全（Unconditionall2324古典密碼基于字符的密碼代替密碼（substitutioncipher)：就是明文中的每一個(gè)字符被替換成密文中的另一個(gè)字符。接收者對(duì)密文做反向替換就可以恢復(fù)出明文。

（代替規(guī)則、密文所用字符、明文中被代替的基本單位）置換密碼（permutationcipher），又稱換位密碼（transpositioncipher）：明文的字母保持相同，但順序被打亂了。24古典密碼基于字符的密碼24古典密碼代替密碼置換密碼25古典密碼代替密碼252526代替密碼簡(jiǎn)單代替密碼（simplesubstitutioncipher），又稱單字母密碼（monoalphabeticcipher）：明文的一個(gè)字符用相應(yīng)的一個(gè)密文字符代替，而且密文所用的字符與一般的明文所用字符屬同一語(yǔ)言系統(tǒng)。多字母密碼（ployalphabeticcipher）：明文中的字符映射到密文空間的字符還依賴于它在上下文中的位置。26代替密碼簡(jiǎn)單代替密碼（simplesubstituti2627單字母密碼單表代換密碼移位（shift）密碼、乘數(shù)（multiplicative）密碼仿射（affine)密碼、多項(xiàng)式（Polynomial）密碼密鑰短語(yǔ)（KeyWord）密碼多表代換密碼維吉尼亞（Vigenere）密碼博福特（Beaufort）密碼滾動(dòng)密鑰（running-key）密碼弗納姆（Vernam）密碼轉(zhuǎn)輪密碼機(jī)（rotormachine）27單字母密碼單表代換密碼2728多字母代換密碼可以用矩陣變換方便地描述多字母代換密碼，有時(shí)又稱起為矩陣變換密碼。

HillcipherPlayfaircipher28多字母代換密碼可以用矩陣變換方便地描述多字母代換密碼，有2829模運(yùn)算-i定義集合為Zq為小于q的所有非負(fù)整數(shù)集合：Zq={0，1，2，…,q-1}，該集合也可看作模q的余數(shù)集合。在該集合上可以進(jìn)行算術(shù)運(yùn)算，就是所謂的模運(yùn)算。定義加法和乘法運(yùn)算如下:

加法:[(amodq)+(bmodq)]modq=(a+b)modq

減法：[(amodq)-(bmodq)]modq=(a-b)modq

乘法:[(amodq)(bmodq)]modq=(ab)modq模運(yùn)算有下述性質(zhì)：（1）若q|(a-b)，則ab(modq)（2）(amodq)=(bmodq)意味abmodq（3）對(duì)稱性，abmodq等價(jià)于bamodq（4）傳遞性，若abmodq且bcmodq

，則acmodq29模運(yùn)算-i定義集合為Zq為小于q的所有非負(fù)整數(shù)集合：Zq2930模運(yùn)算-ii類似普通的加法，在模運(yùn)算中的每個(gè)數(shù)也存在加法逆元，或者稱為相反數(shù)。一個(gè)數(shù)x的加法逆元y是滿足x+y

0modq的數(shù)。對(duì)每一個(gè)，存在z，使得w+z0modq。在通常的乘法中，每個(gè)數(shù)存在乘法逆元，或稱為倒數(shù)。在模q的運(yùn)算中，一個(gè)數(shù)x的乘法逆元y是滿足x

y

1modq的數(shù)。但是并不是所有的數(shù)在模q下都存在乘法逆元。如果(ab)modq=(ac)modq，b

cmodq，如果a與q互素。如果q是一個(gè)素?cái)?shù)，對(duì)每一個(gè),都存在z，使得w

z

1modq，z稱作w的乘法逆元w-1。30模運(yùn)算-ii類似普通的加法，在模運(yùn)算中的每個(gè)數(shù)也存在加法3031模運(yùn)算-iii模26的最小非負(fù)完全剩余系，即模26的余數(shù)集合為{0,1,2,…,25}。可以把字母表與模26的余數(shù)集合等同，26個(gè)英文字母與模26余數(shù)集合{0,….,25}建立一一對(duì)應(yīng)，在此基礎(chǔ)上對(duì)字符進(jìn)行運(yùn)算。31模運(yùn)算-iii模26的最小非負(fù)完全剩余系，即模26的余數(shù)3132單字母密碼單表代換密碼移位（shift）密碼乘數(shù)（multiplicative)密碼仿射（affine)密碼密鑰短語(yǔ)（KeyWord）密碼任意的單表代替密碼32單字母密碼單表代換密碼3233移位密碼算法

設(shè)P=C=K=Z26，對(duì)k∈K,定義ek(x)=x+k(mod26)=y∈C

同時(shí)dk(y)=y-k(mod26)當(dāng)k=3時(shí)，為Caesar密碼

abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABC

例子:cipher=>FLSKHU

實(shí)際算法為：有

同時(shí)有，d3(y)=y-3(mod26)33移位密碼算法

設(shè)P=C=K=Z26，對(duì)k∈K,3334移位密碼分析給定加密的消息:PHHWPHDIWHUWKHWRJDSDUWB由于（1）加解密算法已知（2）可能嘗試的密鑰只有25個(gè)（不包括0）通過(guò)強(qiáng)力攻擊得到明文：

meetmeafterthetogaparty.

移位密碼很容易受到唯密文攻擊。34移位密碼分析給定加密的消息:3435單字母密碼單表代換密碼移位（shift）密碼乘數(shù)（multiplicative)密碼仿射（affine)密碼密鑰短語(yǔ)（KeyWord)密碼任意的單表代替密碼35單字母密碼單表代換密碼3536乘數(shù)密碼算法加密函數(shù)取形式為

e(x)=ax(mod26)，a∈Z26

要求唯一解的充要條件是gcd(a,26)=1

該算法描述為：

設(shè)P=C=Z26，K={a∈Z26|gcd(a,26)=1},

對(duì)k=a∈K,

定義ek(x)=ax(mod26)和dk(y)=a-1(y)(mod26)

x,y∈Z26例子:a=9,ABCDEFGHIJKLMNOPQRSTUVWXYZAJSBKTCLUDMVENWFOXGPYHQZIR

明文密文

cipher=>SUFLKX36乘數(shù)密碼算法加密函數(shù)取形式為3637乘數(shù)密碼分析對(duì)于乘數(shù)密碼，當(dāng)且僅當(dāng)a與26互素時(shí)，加密變換才是一一映射的，因此a的選擇有11種：

a=3,5,7,9,11,15,17,19,21,23,25

可能嘗試的密鑰只有1１個(gè)37乘數(shù)密碼分析對(duì)于乘數(shù)密碼，當(dāng)且僅當(dāng)a與26互素時(shí)，加密變3738單字母密碼單表代換密碼移位（shift）密碼乘數(shù)（multiplicative)密碼仿射（affine)密碼密鑰短語(yǔ)（KeyWord)密碼任意的單表代替密碼38單字母密碼單表代換密碼3839仿射密碼算法-i加密函數(shù)取形式為

e(x)=ax+b(mod26),a,b∈Z26

要求唯一解的充要條件是gcd(a,26)=1

該算法描述為：

設(shè)P=C=Z26

K={(a,b)∈Z26×Z26|gcd(a,26)=1},

對(duì)k=(a,b)∈K，

定義ek(x)=ax+b(mod26)和dk(y)=a-1(y-b)(mod26)

x,y∈Z26q=26時(shí)，可能的密鑰是26×12-1=311個(gè)39仿射密碼算法-i加密函數(shù)取形式為3940單字母密碼單表代換密碼移位（shift）密碼乘數(shù)（multiplicative)密碼仿射（affine)密碼密鑰短語(yǔ)（KeyWord)密碼任意的單表代替密碼40單字母密碼單表代換密碼4041密鑰短語(yǔ)密碼以西文單詞為密鑰的換字表例如：取university為密鑰，首先找出其中發(fā)生重復(fù)的字母，去掉重復(fù)字母i，成為universty.其次，字母一共10個(gè)，從第11個(gè)字母開(kāi)始，用universty按順序進(jìn)行代替配置。然后把其余17個(gè)字母按自然順序接在后面。以u(píng)niversity為密鑰的換字表明文字母abcdefghijklmnopqrstuvwxyz密文字母JKLMOPQWXZUNIVERSTYABCDFGH41密鑰短語(yǔ)密碼以西文單詞為密鑰的換字表4142非自然續(xù)序配置的換字表明文字母與代替他的密文字母豪無(wú)關(guān)聯(lián)那么整個(gè)換字表就是他的密鑰明文字母abcdefghijklmnopqrstuvwxyz密文字母IGVRFHPJYBNKAXLTSMCWDUEOZQ42非自然續(xù)序配置的換字表明文字母與代替他的密文字母豪無(wú)關(guān)聯(lián)4243單字母密碼單表代換密碼移位（shift）密碼乘數(shù)（multiplicative)密碼仿射（affine)密碼密鑰短語(yǔ)（KeyWord)密碼任意的單表代替密碼43單字母密碼單表代換密碼4344任意的單表代替密碼算法設(shè)P=C=Z26，K是由26個(gè)符號(hào)0，1，...，5的所有可能置換組成。任意π∈K，定義eπ(x)=π(x)=y

且dπ(y)=-1(y)=x,π-1是π的逆置換。注：1*.置換π的表示：

π＝

2*密鑰空間K很大，|k|=26!≈4×1026，破譯者窮舉搜索是不行的，然而，可由統(tǒng)計(jì)的方式破譯它。3*移位密碼、乘數(shù)密碼、仿射密碼算法都是替換密碼的特例0123..2324250'1'2'3'..23'24'25')(44任意的單表代替密碼算法設(shè)P=C=Z26，K是由26個(gè)符號(hào)4445單表替換密碼的破譯語(yǔ)言的統(tǒng)計(jì)特性：語(yǔ)言的頻率特征連接特征重復(fù)特征45單表替換密碼的破譯語(yǔ)言的統(tǒng)計(jì)特性：4546頻率特征在各種語(yǔ)言中，各個(gè)字母的使用次數(shù)是不一樣的，有的偏高，有的偏低，這種現(xiàn)象叫偏用現(xiàn)象。對(duì)英文的任何一篇文章，一個(gè)字母在該文章中出現(xiàn)的次數(shù)稱作這個(gè)字母（在這篇文章中）的頻數(shù)。一個(gè)字母的頻數(shù)除以文章的字母總數(shù)，就得到字母的使用頻率。46頻率特征在各種語(yǔ)言中，各個(gè)字母的使用次數(shù)是不一樣的，有的4647英文字母的普遍使用頻率美國(guó)密碼學(xué)家W.F.Friedman在調(diào)查了大量英文資料后,得出英文字母的普遍使用規(guī)律.47英文字母的普遍使用頻率美國(guó)密碼學(xué)家W.F.Friedma4748英文單字母使用頻率分類48英文單字母使用頻率分類4849特殊的特征開(kāi)頭結(jié)尾特征:有些文章的開(kāi)頭和結(jié)尾受到固定格式的限制有時(shí)文章中間的某些特定部位，某些字母也會(huì)出現(xiàn)較高的使用頻率。49特殊的特征開(kāi)頭結(jié)尾特征:4950頻度最高的前30個(gè)雙字母

50頻度最高的前30個(gè)雙字母5051頻度最高的前20個(gè)三字母

51頻度最高的前20個(gè)三字母5152其它頻率特征the的使用頻率最高，是ING的三倍，若把the去掉，t在第II類中排在最后，h會(huì)降為第III類，th和he也不是常出現(xiàn)的字母組了一半的單詞以esdt結(jié)尾一半的單詞以tasw開(kāi)頭Y的使用頻率90%都集中在單詞的結(jié)尾52其它頻率特征the的使用頻率最高，是ING的三倍，若把5253連接特征后連接：q…u前連接：x的前面總是i，e很少是o和a間斷連接：在e和e之間，r的出現(xiàn)頻率最高53連接特征后連接：q…u5354重復(fù)特征兩個(gè)字符以上的字符串重復(fù)出現(xiàn)的現(xiàn)象，叫做語(yǔ)言的重復(fù)特征。thtiontious54重復(fù)特征兩個(gè)字符以上的字符串重復(fù)出現(xiàn)的現(xiàn)象，叫做語(yǔ)言的重54例子-密文QRLLIQQPFVICXPFMTPZWRFNFOTFLPYWIGQPQHICQRGIVAKZWIQIBORGZWPFMQPFZWIOGVIGFCHIVYIGQIJIGCFLILCGIBRXHIZWOVQOBCFCXKQPQPFZRPZPOFXRLNZWICAPXPZKCZXICQZZOGICVZWIXCFMRCMIOBZWIOGPMPFCXZISZPQJIGKVIQPGCAXIARZFOZIQQIFZPCX55例子-密文QRLLIQQPFVICXPFMTPZWRFNFO55確定字母的相對(duì)頻率I可能相當(dāng)于明文中的e56確定字母的相對(duì)頻率5656雙字母頻率57最常見(jiàn)的雙字母組合ZW，Z猜測(cè)其為T，W對(duì)應(yīng)為HWI

HEPFIN雙字母頻率57最常見(jiàn)的雙字母組合ZW，Z猜測(cè)其為T，W對(duì)應(yīng)57進(jìn)一步分析-1ZWIQI與these相似，Q

STPZW與with類似，TWIQQIFZPCX與essential相似，CA，XLCFCXKQPQ與analysis類似，KYCAPXPZK與ability類似，AB58進(jìn)一步分析-15858進(jìn)一步分析-2ZWPFM與things類似，MGXCFMRCMI與language類似，RUVICXPFM與dealing類似，VDQRLLIQQ與success類似，LCGICV與read類似，GR59進(jìn)一步分析-25959進(jìn)一步分析-3LCGIBRX與careful類似，BFHICQRGIV與measured類似，HMHIZWOVQ與methods類似，OOJIGK猜測(cè)為veryYIGQIJIGCFLI猜測(cè)為perseveranceRFNFOTF猜測(cè)為unknown，把ZISZ猜測(cè)為text60進(jìn)一步分析-36060密鑰61密鑰6161完整明文Successindealingwithunknownciphersismeasuredbythesefourthingsintheordernamed：perseverance，carefulmethodsofanalysis，intuition，luck.Theabilityatleasttoreadthelanguageoftheoriginaltextisverydesirablebutnotessential.62完整明文Successindealingwithun6263對(duì)抗頻率分析的辦法多名或同音代替密碼多表代替密碼多字母代替密碼

63對(duì)抗頻率分析的辦法多名或同音代替密碼6364多名代替密碼

與簡(jiǎn)單代替密碼類似，只是映射是一對(duì)多的，每個(gè)明文字母可以加密成多個(gè)密文字母。例如，A可能對(duì)應(yīng)于5、13、25B可能對(duì)應(yīng)于7、9、31、4264多名代替密碼

與簡(jiǎn)單代替密碼類似，只是映射是一對(duì)多的，6465多表代替密碼多表代替密碼：是以一系列（兩個(gè)以上）代換表依此對(duì)明文消息的字母進(jìn)行代換的方法。非周期多表代替密碼：代換表是非周期的無(wú)限序列一次一密密碼（one-timepadding)：對(duì)每個(gè)明文每次采用不同的代換表。周期多表代替密碼：代換表個(gè)數(shù)有限，重復(fù)使用。65多表代替密碼多表代替密碼：是以一系列（兩個(gè)以上）代換表6566多表代替密碼多表代替密碼維吉尼亞（Vigenere)密碼滾動(dòng)密鑰（running-key）密碼弗納姆（Vernam）密碼轉(zhuǎn)輪密碼機(jī)（rotormachine）66多表代替密碼多表代替密碼6667Vigenérecipher(1858)是一種多表移位代替密碼設(shè)d為一固定的正整數(shù)，d個(gè)移位代換表=（1，2,…d)由密鑰序列K＝（k1,k2,…,kd)給定，第i+td個(gè)明文字母由表i決定，即密鑰ki決定

ek(xi+td)=(xi+td+ki)modq=y

dk(yi+td)=(xi+td-ki)modq=x例子：q=26,x=polyalphabeticcipher,K=RADIO67Vigenérecipher(1858)是一種多表移6768Vigenérecipher-破譯密鑰空間大小為26m，m=5，265=1.1107依然保留了字符頻率某些統(tǒng)計(jì)信息分析的第一步是確定密鑰字的長(zhǎng)度d，確定d的方法最常用的有兩種Kasiski測(cè)試法1863年，普魯士軍官Kasiski提出的一種重碼分析法重合指數(shù)法（indexofcoincidence)

68Vigenérecipher-破譯密鑰空間大小為26m6869Kasiski測(cè)試法重碼分析法：間距是密鑰長(zhǎng)度整數(shù)倍的相同子串有相同密文，反過(guò)來(lái)，密文中兩個(gè)相同的子串對(duì)應(yīng)的密文相同的可能性很大偶然重復(fù)和真重復(fù)他們之間的距離的因數(shù)可能就是密鑰長(zhǎng)度。Kasiski實(shí)驗(yàn)：對(duì)一份用周期性多表密碼加密的密文，確定其中所有的重復(fù)出現(xiàn)的字母串，計(jì)算他們之間的距離，并對(duì)這些距離進(jìn)行因子分解，出現(xiàn)頻率較高的因子很可能是密鑰的長(zhǎng)度。69Kasiski測(cè)試法重碼分析法：間距是密鑰長(zhǎng)度整數(shù)倍的相6970重合指數(shù)設(shè)y是一個(gè)長(zhǎng)度為n密文，即y=y=y1y2y3…ym，其中yi是密文字母，同樣來(lái)求從中抽到兩個(gè)相同字母的概率是多少？為此，設(shè)NA為字母A在這份密文中的頻數(shù)，設(shè)NB為字母B在這份密文中的頻數(shù)，依此類推。從n個(gè)密文字母中抽取兩個(gè)字母的方式有Cn2=n(n-1)/2，而其中NA個(gè)A組成一對(duì)A的方式有CNA2=NA(NA-1)/2，于是從y中抽到兩個(gè)字母都為A的概率為[NA(NA-1)]/[n(n-1)]，…因此，從y中抽到兩個(gè)相同字母的概率為這個(gè)數(shù)據(jù)稱為這份密文的重合指數(shù)。記為IC70重合指數(shù)設(shè)y是一個(gè)長(zhǎng)度為n密文，即y=y=y1y2y37071一個(gè)判斷準(zhǔn)則根據(jù)概率論中的大數(shù)定律，如果y是用單表加密的，那么當(dāng)n較大時(shí)，IC很可能接近于0.068771一個(gè)判斷準(zhǔn)則根據(jù)概率論中的大數(shù)定律，如果y是用單表加密的7172多表代替密碼多表代替密碼維吉尼亞（Vigenere)密碼滾動(dòng)密鑰（running-key）密碼弗納姆（Vernam）密碼轉(zhuǎn)輪密碼機(jī)（rotormachine）72多表代替密碼多表代替密碼7273滾動(dòng)密鑰密碼對(duì)于周期代換密碼，當(dāng)密鑰的長(zhǎng)度d和明文一樣長(zhǎng)時(shí)，就成為滾動(dòng)密鑰密碼。

Vigenére本人建議密鑰與明文一樣長(zhǎng)73滾動(dòng)密鑰密碼對(duì)于周期代換密碼，當(dāng)密鑰的長(zhǎng)度d和明文一樣長(zhǎng)7374多表代替密碼多表代替密碼維吉尼亞（Vigenere)密碼滾動(dòng)密鑰（running-key）密碼弗納姆（Vernam）密碼轉(zhuǎn)輪密碼機(jī)（rotormachine）74多表代替密碼多表代替密碼7475Vernam密碼1918年，GillbertVernam建議密鑰與明文一樣長(zhǎng)并且沒(méi)有統(tǒng)計(jì)關(guān)系的密鑰內(nèi)容，他采用的是二進(jìn)制數(shù)據(jù): 加密：Ci=Pi

Ki

解密Pi=Ci

Ki

核心：構(gòu)造和消息一樣長(zhǎng)的隨機(jī)密鑰

75Vernam密碼1918年，GillbertVerna7576多表代替密碼多表代替密碼維吉尼亞（Vigenere)密碼滾動(dòng)密鑰（running-key）密碼弗納姆（Vernam）密碼轉(zhuǎn)輪密碼機(jī)（rotormachine）76多表代替密碼多表代替密碼7677轉(zhuǎn)輪密碼機(jī)三個(gè)轉(zhuǎn)輪的代替表數(shù)量26×26×26=1757677轉(zhuǎn)輪密碼機(jī)7778對(duì)抗頻率分析的辦法多名或同音代替密碼多表代替密碼多字母代替密碼Playfair密碼Hill密碼78對(duì)抗頻率分析的辦法多名或同音代替密碼7879多字母代替密碼-PlayfairPlayfair:將明文中的雙字母組合作為一個(gè)單元對(duì)待，并將這些單元轉(zhuǎn)換為密文的雙字母組合。5×5變換矩陣:I與J視為同一字符

CIPHE RABDF GKLMN(cipher) OQSTU VWXYZ加密規(guī)則:按成對(duì)字母加密相同對(duì)中的字母加分隔符(如x)balloonbalxloon

同行取右邊:heEC

同列取下邊:dmMT

其他取交叉:ktMQODTR79多字母代替密碼-PlayfairPlayfair:將明文7980Playfair密碼分析Playfair有26×26=676種字母對(duì)組合字符出現(xiàn)幾率一定程度上被均勻化基于字母頻率的攻擊比較困難依然保留了相當(dāng)?shù)慕Y(jié)構(gòu)信息80Playfair密碼分析Playfair有26×26=68081多字母代替密碼多字母代替密碼Playfair密碼Hill密碼81多字母代替密碼多字母代替密碼8182Hill密碼（1929）基于矩陣的線性變換:假設(shè)K是一個(gè)m*m矩陣，在Z26上可逆，即存在K-1使得：KK-1=I（在Z26上），對(duì)每一個(gè)k∈K，定義ek(x)=xK(mod26)和

dk(y)=yK-1(mod26)明文與密文都是m元的向量

（x1,x2,

…,xm），（y1,y2,…,ym）82Hill密碼（1929）基于矩陣的線性變換:8283Hill密碼分析完全隱藏了字符（對(duì)）的頻率信息采用唯密文攻擊希爾密碼是很難攻破的.線性變換的安全性很脆弱，易被已知明文攻擊擊破。83Hill密碼分析完全隱藏了字符（對(duì)）的頻率信息83古典密碼代替密碼置換密碼84古典密碼代替密碼848485置換密碼在換位密碼中，明文的字母保持相同，但順序被打亂了。一種換位密碼把明文按行寫入,按列讀出密鑰包含3方面信息:行寬、列高、讀出順序完全保留字符的統(tǒng)計(jì)信息使用多輪加密可提高安全性85置換密碼在換位密碼中，明文的字母保持相同，但順序被打亂了8586

古典密碼小結(jié)模運(yùn)算：加法、減法、乘法性質(zhì)：對(duì)稱、傳遞、交換、結(jié)合、分配加法逆元、乘法逆元對(duì)稱密碼的兩個(gè)基本運(yùn)算代替和置換（Substitution&permutation）密碼分析與Kerckhoff原則多輪加密數(shù)據(jù)安全基于算法的保密

86古典密碼小結(jié)模運(yùn)算：8687古典密碼小結(jié)87古典密碼小結(jié)8788參考文獻(xiàn)王昭，袁春編著，信息安全原理與應(yīng)用，電子工業(yè)出版社，北京，2010，1WilliamStallings,Cryptographyandnetworksecurity:principlesandpractice,SecondEdition.BruceShneier,Appliedcryptography:protocols,algorithms,andsourcecodeinC,SecondEdition.ThomasH.Barr,InvitationtoCryptology,PrenticeHall,2002李克洪主編，實(shí)用密碼學(xué)與計(jì)算機(jī)安全，東北大學(xué)出版社，1997，10王育民劉建偉編著，通信網(wǎng)的安全----理論與技術(shù)，2000，5/Security2e.html……88參考文獻(xiàn)王昭，袁春編著，信息安全原理與應(yīng)用，電子工業(yè)出版8889

Q&A?89Q&A?8990

信息安全原理與應(yīng)用第二章密碼學(xué)基礎(chǔ)本章由王昭主寫1信息安全原理與應(yīng)用9091內(nèi)容提要基本概念和術(shù)語(yǔ)密碼學(xué)的歷史古典密碼2內(nèi)容提要基本概念和術(shù)語(yǔ)9192基本概念密碼學(xué)(Cryptology)：是研究信息系統(tǒng)安全保密的科學(xué)。密碼編碼學(xué)(Cryptography)：主要研究對(duì)信息進(jìn)行編碼，實(shí)現(xiàn)對(duì)信息的隱蔽。密碼分析學(xué)(Cryptanalytics)：主要研究加密消息的破譯或消息的偽造。3基本概念密碼學(xué)(Cryptology)：是研究信息系統(tǒng)安全9293基本術(shù)語(yǔ)消息被稱為明文(Plaintext)。用某種方法偽裝消息以隱藏它的內(nèi)容的過(guò)程稱為加密(Encrtption)，被加密的消息稱為密文(Ciphertext)，而把密文轉(zhuǎn)變?yōu)槊魑牡倪^(guò)程稱為解密(Decryption)。對(duì)明文進(jìn)行加密操作的人員稱作加密員或密碼員(Cryptographer)。密碼算法(CryptographyAlgorithm):是用于加密和解密的數(shù)學(xué)函數(shù)。密碼員對(duì)明文進(jìn)行加密操作時(shí)所采用的一組規(guī)則稱作加密算法(EncryptionAlgorithm)。所傳送消息的預(yù)定對(duì)象稱為接收者(Receiver)。接收者對(duì)密文解密所采用的一組規(guī)則稱為解密算法(DecryptionAlgorithm)。4基本術(shù)語(yǔ)消息被稱為明文(Plaintext)。用某種方法偽9394凱撒密表公元前54年，古羅馬長(zhǎng)官凱撒明文字母abcdefghijklmnopqrstuvwxyz密文字母DEFGHIJKLMNOPQRSTUVWXYZABC有一個(gè)拉丁文句子omniagalliaestdivisainpartestres(高盧全境分為三個(gè)部分）RPQLDJDOOLDHVWGLYLVDLQSDUWHVWUHV把明文的拉丁字母逐個(gè)代之以相應(yīng)的希臘字母5凱撒密表公元前54年，古羅馬長(zhǎng)官凱撒9495

加解密過(guò)程示意圖加密和解密算法的操作通常都是在一組密鑰的控制下進(jìn)行的，分別稱為加密密鑰(EncryptionKey)和解密密鑰(DecryptionKey)。69596

密碼學(xué)的目的：A和B兩個(gè)人在不安全的信道上進(jìn)行通信，而攻擊者O不能理解他們通信的內(nèi)容。加密通信的模型

7加密通信的模型

9697密碼體制密碼體制：它是一個(gè)五元組（P,C,K,E,D)滿足條件：（1）P是可能明文的有限集；（明文空間）（2）C是可能密文的有限集；（密文空間）（3）K是一切可能密鑰構(gòu)成的有限集；（密鑰空間）（4）任意k∈K，有一個(gè)加密算法和相應(yīng)的解密算法，使得和分別為加密解密函數(shù)，滿足dk(ek(x))=x，這里x∈P。8密碼體制密碼體制：它是一個(gè)五元組（P,C,K,E,D)滿足9798密碼算法分類-i按照保密的內(nèi)容分:受限制的（restricted）算法：算法的保密性基于保持算法的秘密。

基于密鑰（key-based）的算法：算法的保密性基于對(duì)密鑰的保密。9密碼算法分類-i按照保密的內(nèi)容分:9899密碼算法分類-ii基于密鑰的算法，按照密鑰的特點(diǎn)分類：對(duì)稱密碼算法（symmetriccipher)：又稱傳統(tǒng)密碼算法（conventionalcipher)，就是加密密鑰和解密密鑰相同，或?qū)嵸|(zhì)上等同，即從一個(gè)易于推出另一個(gè)。又稱秘密密鑰算法或單密鑰算法。非對(duì)稱密鑰算法（asymmetriccipher）:加密密鑰和解密密鑰不相同，從一個(gè)很難推出另一個(gè)。又稱公開(kāi)密鑰算法（public-keycipher）

。公開(kāi)密鑰算法用一個(gè)密鑰進(jìn)行加密,而用另一個(gè)進(jìn)行解密.其中的加密密鑰可以公開(kāi)，又稱公開(kāi)密鑰（publickey)，簡(jiǎn)稱公鑰。解密密鑰必須保密，又稱私人密鑰（privatekey）私鑰，簡(jiǎn)稱私鑰。10密碼算法分類-ii基于密鑰的算法，按照密鑰的特點(diǎn)分類：99100密碼算法分類-iii按照明文的處理方法：分組密碼（blockcipher）:將明文分成固定長(zhǎng)度的組，用同一密鑰和算法對(duì)每一塊加密，輸出也是固定長(zhǎng)度的密文。流密碼（streamcipher）:又稱序列密碼。序列密碼每次加密一位或一字節(jié)的明文，也可以稱為流密碼。序列密碼是手工和機(jī)械密碼時(shí)代的主流11密碼算法分類-iii按照明文的處理方法：100101密碼算法分類-iv對(duì)稱密鑰密碼又可分為：分組密碼

每次對(duì)一塊數(shù)據(jù)加密多數(shù)網(wǎng)絡(luò)加密應(yīng)用

DES、IDEA、RC6、Rijndael流密碼每次對(duì)一位或一字節(jié)加密手機(jī)

One-timepadding、Vigenére、Vernam12密碼算法分類-iv對(duì)稱密鑰密碼又可分為：101102密碼算法分類-v公開(kāi)密鑰密碼：大部分是分組密碼，只有概率密碼體制屬于流密碼每次對(duì)一塊數(shù)據(jù)加密數(shù)字簽名,身份鑒別

RSA、ECC、ElGamal

加密解密速度慢13密碼算法分類-v公開(kāi)密鑰密碼：102103Kerckhoff原則1883年Kerchoffs第一次明確提出了編碼的原則：加密算法應(yīng)建立在算法的公開(kāi)不影響明文和密鑰的安全的基礎(chǔ)上。這一原則已得到普遍承認(rèn)，成為判定密碼強(qiáng)度的衡量標(biāo)準(zhǔn)，實(shí)際上也成為古典密碼和現(xiàn)代密碼的分界線。14Kerckhoff原則1883年Kerchoffs第一次103104密碼分析假設(shè)破譯者O是在已知密碼體制的前提下來(lái)破譯正在使用的密鑰，這個(gè)假設(shè)稱為Kerckhoff原則。最常見(jiàn)的破解類型如下：唯密文攻擊：O具有密文串y。已知明文攻擊:O具有明文串x和相應(yīng)的密文y。選擇明文攻擊：O可獲得對(duì)加密機(jī)的暫時(shí)訪問(wèn)，因此他能選擇明文串x并構(gòu)造出相應(yīng)的密文串y。選擇密文攻擊：O可暫時(shí)接近密碼機(jī)，可選擇密文串y，并構(gòu)造出相應(yīng)的明文x。

這一切的目的在于破譯出密鑰或密文15密碼分析假設(shè)破譯者O是在已知密碼體制的前提下來(lái)破譯正在使104105

內(nèi)容提要基本概念和術(shù)語(yǔ)密碼學(xué)的歷史古典密碼16內(nèi)容提要基本概念和術(shù)語(yǔ)105106密碼學(xué)的起源和發(fā)展-i三個(gè)階段：1949年之前密碼學(xué)是一門藝術(shù)1949～1975年密碼學(xué)成為科學(xué)1976年以后密碼學(xué)的新方向——公鑰密碼學(xué)17密碼學(xué)的起源和發(fā)展-i三個(gè)階段：106107密碼學(xué)的起源和發(fā)展-ii1949年之前:

古典密碼（classicalcryptography)

密碼學(xué)還不是科學(xué)，而是藝術(shù)出現(xiàn)一些密碼算法和加密設(shè)備密碼算法的基本手段代替&置換（substitution&permutation）出現(xiàn)，針對(duì)的是字符簡(jiǎn)單的密碼分析手段出現(xiàn)18密碼學(xué)的起源和發(fā)展-ii1949年之前:107108密碼學(xué)的起源和發(fā)展-iii1949～1975年:計(jì)算機(jī)使得基于復(fù)雜計(jì)算的密碼成為可能1949年Shannon的“TheCommunicationTheoryofSecretSystems”1967年DavidKahn的《TheCodebreakers》1971-73年IBMWatson實(shí)驗(yàn)室的HorstFeistel等的幾篇技術(shù)報(bào)告數(shù)據(jù)的安全基于密鑰而不是算法的保密19密碼學(xué)的起源和發(fā)展-iii1949～1975年:108109密碼學(xué)的起源和發(fā)展-iv1976年以后:

1976年Diffie&Hellman的“NewDirectionsinCryptography”提出了不對(duì)稱密鑰密碼1977年Rivest，Shamir&Adleman提出了RSA公鑰算法90年代逐步出現(xiàn)橢圓曲線等其他公鑰算法

公鑰密碼使得發(fā)送端和接收端無(wú)密鑰傳輸?shù)谋Ｃ芡ㄐ懦蔀榭赡埽?0密碼學(xué)的起源和發(fā)展-iv1976年以后:109110密碼學(xué)的起源和發(fā)展-v1976年以后:

對(duì)稱密鑰密碼算法進(jìn)一步發(fā)展1977年DES正式成為標(biāo)準(zhǔn)80年代出現(xiàn)“過(guò)渡性”的“postDES”算法，如IDEA,RCx,CAST等90年代對(duì)稱密鑰密碼進(jìn)一步成熟Rijndael,RC6,MARS,Twofish,Serpent等出現(xiàn)2001年Rijndael成為DES的替代者21密碼學(xué)的起源和發(fā)展-v1976年以后:110111

內(nèi)容提要基本概念和術(shù)語(yǔ)密碼學(xué)的歷史古典密碼22內(nèi)容提要基本概念和術(shù)語(yǔ)111112密碼算法的安全性無(wú)條件安全（Unconditionallysecure）無(wú)論破譯者有多少密文，他也無(wú)法解出對(duì)應(yīng)的明文，即使他解出了，他也無(wú)法驗(yàn)證結(jié)果的正確性。One-timepad計(jì)算上安全（Computationallysecure）破譯的代價(jià)超出信息本身的價(jià)值。破譯的時(shí)間超出了信息的有效期。23密碼算法的安全性無(wú)條件安全（Unconditionall112113古典密碼基于字符的密碼代替密碼（substitutioncipher)：就是明文中的每一個(gè)字符被替換成密文中的另一個(gè)字符。接收者對(duì)密文做反向替換就可以恢復(fù)出明文。

（代替規(guī)則、密文所用字符、明文中被代替的基本單位）置換密碼（permutationcipher），又稱換位密碼（transpositioncipher）：明文的字母保持相同，但順序被打亂了。24古典密碼基于字符的密碼113古典密碼代替密碼置換密碼114古典密碼代替密碼25114115代替密碼簡(jiǎn)單代替密碼（simplesubstitutioncipher），又稱單字母密碼（monoalphabeticcipher）：明文的一個(gè)字符用相應(yīng)的一個(gè)密文字符代替，而且密文所用的字符與一般的明文所用字符屬同一語(yǔ)言系統(tǒng)。多字母密碼（ployalphabeticcipher）：明文中的字符映射到密文空間的字符還依賴于它在上下文中的位置。26代替密碼簡(jiǎn)單代替密碼（simplesubstituti115116單字母密碼單表代換密碼移位（shift）密碼、乘數(shù)（multiplicative）密碼仿射（affine)密碼、多項(xiàng)式（Polynomial）密碼密鑰短語(yǔ)（KeyWord）密碼多表代換密碼維吉尼亞（Vigenere）密碼博福特（Beaufort）密碼滾動(dòng)密鑰（running-key）密碼弗納姆（Vernam）密碼轉(zhuǎn)輪密碼機(jī)（rotormachine）27單字母密碼單表代換密碼116117多字母代換密碼可以用矩陣變換方便地描述多字母代換密碼，有時(shí)又稱起為矩陣變換密碼。

HillcipherPlayfaircipher28多字母代換密碼可以用矩陣變換方便地描述多字母代換密碼，有117118模運(yùn)算-i定義集合為Zq為小于q的所有非負(fù)整數(shù)集合：Zq={0，1，2，…,q-1}，該集合也可看作模q的余數(shù)集合。在該集合上可以進(jìn)行算術(shù)運(yùn)算，就是所謂的模運(yùn)算。定義加法和乘法運(yùn)算如下:

加法:[(amodq)+(bmodq)]modq=(a+b)modq

減法：[(amodq)-(bmodq)]modq=(a-b)modq

乘法:[(amodq)(bmodq)]modq=(ab)modq模運(yùn)算有下述性質(zhì)：（1）若q|(a-b)，則ab(modq)（2）(amodq)=(bmodq)意味abmodq（3）對(duì)稱性，abmodq等價(jià)于bamodq（4）傳遞性，若abmodq且bcmodq

，則acmodq29模運(yùn)算-i定義集合為Zq為小于q的所有非負(fù)整數(shù)集合：Zq118119模運(yùn)算-ii類似普通的加法，在模運(yùn)算中的每個(gè)數(shù)也存在加法逆元，或者稱為相反數(shù)。一個(gè)數(shù)x的加法逆元y是滿足x+y

0modq的數(shù)。對(duì)每一個(gè)，存在z，使得w+z0modq。在通常的乘法中，每個(gè)數(shù)存在乘法逆元，或稱為倒數(shù)。在模q的運(yùn)算中，一個(gè)數(shù)x的乘法逆元y是滿足x

y

1modq的數(shù)。但是并不是所有的數(shù)在模q下都存在乘法逆元。如果(ab)modq=(ac)modq，b

cmodq，如果a與q互素。如果q是一個(gè)素?cái)?shù)，對(duì)每一個(gè),都存在z，使得w

z

1modq，z稱作w的乘法逆元w-1。30模運(yùn)算-ii類似普通的加法，在模運(yùn)算中的每個(gè)數(shù)也存在加法119120模運(yùn)算-iii模26的最小非負(fù)完全剩余系，即模26的余數(shù)集合為{0,1,2,…,25}?？梢园炎帜副砼c模26的余數(shù)集合等同，26個(gè)英文字母與模26余數(shù)集合{0,….,25}建立一一對(duì)應(yīng)，在此基礎(chǔ)上對(duì)字符進(jìn)行運(yùn)算。31模運(yùn)算-iii模26的最小非負(fù)完全剩余系，即模26的余數(shù)120121單字母密碼單表代換密碼移位（shift）密碼乘數(shù)（multiplicative)密碼仿射（affine)密碼密鑰短語(yǔ)（KeyWord）密碼任意的單表代替密碼32單字母密碼單表代換密碼121122移位密碼算法

設(shè)P=C=K=Z26，對(duì)k∈K,定義ek(x)=x+k(mod26)=y∈C

同時(shí)dk(y)=y-k(mod26)當(dāng)k=3時(shí)，為Caesar密碼

abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABC

例子:cipher=>FLSKHU

實(shí)際算法為：有

同時(shí)有，d3(y)=y-3(mod26)33移位密碼算法

設(shè)P=C=K=Z26，對(duì)k∈K,122123移位密碼分析給定加密的消息:PHHWPHDIWHUWKHWRJDSDUWB由于（1）加解密算法已知（2）可能嘗試的密鑰只有25個(gè)（不包括0）通過(guò)強(qiáng)力攻擊得到明文：

meetmeafterthetogaparty.

移位密碼很容易受到唯密文攻擊。34移位密碼分析給定加密的消息:123124單字母密碼單表代換密碼移位（shift）密碼乘數(shù)（multiplicative)密碼仿射（affine)密碼密鑰短語(yǔ)（KeyWord)密碼任意的單表代替密碼35單字母密碼單表代換密碼124125乘數(shù)密碼算法加密函數(shù)取形式為

e(x)=ax(mod26)，a∈Z26

要求唯一解的充要條件是gcd(a,26)=1

該算法描述為：

設(shè)P=C=Z26，K={a∈Z26|gcd(a,26)=1},

對(duì)k=a∈K,

定義ek(x)=ax(mod26)和dk(y)=a-1(y)(mod26)

x,y∈Z26例子:a=9,ABCDEFGHIJKLMNOPQRSTUVWXYZAJSBKTCLUDMVENWFOXGPYHQZIR

明文密文

cipher=>SUFLKX36乘數(shù)密碼算法加密函數(shù)取形式為125126乘數(shù)密碼分析對(duì)于乘數(shù)密碼，當(dāng)且僅當(dāng)a與26互素時(shí)，加密變換才是一一映射的，因此a的選擇有11種：

a=3,5,7,9,11,15,17,19,21,23,25

可能嘗試的密鑰只有1１個(gè)37乘數(shù)密碼分析對(duì)于乘數(shù)密碼，當(dāng)且僅當(dāng)a與26互素時(shí)，加密變126127單字母密碼單表代換密碼移位（shift）密碼乘數(shù)（multiplicative)密碼仿射（affine)密碼密鑰短語(yǔ)（KeyWord)密碼任意的單表代替密碼38單字母密碼單表代換密碼127128仿射密碼算法-i加密函數(shù)取形式為

e(x)=ax+b(mod26),a,b∈Z26

要求唯一解的充要條件是gcd(a,26)=1

該算法描述為：

設(shè)P=C=Z26

K={(a,b)∈Z26×Z26|gcd(a,26)=1},

對(duì)k=(a,b)∈K，

定義ek(x)=ax+b(mod26)和dk(y)=a-1(y-b)(mod26)

x,y∈Z26q=26時(shí)，可能的密鑰是26×12-1=311個(gè)39仿射密碼算法-i加密函數(shù)取形式為128129單字母密碼單表代換密碼移位（shift）密碼乘數(shù)（multiplicative)密碼仿射（affine)密碼密鑰短語(yǔ)（KeyWord)密碼任意的單表代替密碼40單字母密碼單表代換密碼129130密鑰短語(yǔ)密碼以西文單詞為密鑰的換字表例如：取university為密鑰，首先找出其中發(fā)生重復(fù)的字母，去掉重復(fù)字母i，成為universty.其次，字母一共10個(gè)，從第11個(gè)字母開(kāi)始，用universty按順序進(jìn)行代替配置。然后把其余17個(gè)字母按自然順序接在后面。以u(píng)niversity為密鑰的換字表明文字母abcdefghijklmnopqrstuvwxyz密文字母JKLMOPQWXZUNIVERSTYABCDFGH41密鑰短語(yǔ)密碼以西文單詞為密鑰的換字表130131非自然續(xù)序配置的換字表明文字母與代替他的密文字母豪無(wú)關(guān)聯(lián)那么整個(gè)換字表就是他的密鑰明文字母abcdefghijklmnopqrstuvwxyz密文字母IGVRFHPJYBNKAXLTSMCWDUEOZQ42非自然續(xù)序配置的換字表明文字母與代替他的密文字母豪無(wú)關(guān)聯(lián)131132單字母密碼單表代換密碼移位（shift）密碼乘數(shù)（multiplicative)密碼仿射（affine)密碼密鑰短語(yǔ)（KeyWord)密碼任意的單表代替密碼43單字母密碼單表代換密碼132133任意的單表代替密碼算法設(shè)P=C=Z26，K是由26個(gè)符號(hào)0，1，...，5的所有可能置換組成。任意π∈K，定義eπ(x)=π(x)=y

且dπ(y)=-1(y)=x,π-1是π的逆置換。注：1*.置換π的表示：

π＝

2*密鑰空間K很大，|k|=26!≈4×1026，破譯者窮舉搜索是不行的，然而，可由統(tǒng)計(jì)的方式破譯它。3*移位密碼、乘數(shù)密碼、仿射密碼算法都是替換密碼的特例0123..2324250'1'2'3'..23'24'25')(44任意的單表代替密碼算法設(shè)P=C=Z26，K是由26個(gè)符號(hào)133134單表替換密碼的破譯語(yǔ)言的統(tǒng)計(jì)特性：語(yǔ)言的頻率特征連接特征重復(fù)特征45單表替換密碼的破譯語(yǔ)言的統(tǒng)計(jì)特性：134135頻率特征在各種語(yǔ)言中，各個(gè)字母的使用次數(shù)是不一樣的，有的偏高，有的偏低，這種現(xiàn)象叫偏用現(xiàn)象。對(duì)英文的任何一篇文章，一個(gè)字母在該文章中出現(xiàn)的次數(shù)稱作這個(gè)字母（在這篇文章中）的頻數(shù)。一個(gè)字母的頻數(shù)除以文章的字母總數(shù)，就得到字母的使用頻率。46頻率特征在各種語(yǔ)言中，各個(gè)字母的使用次數(shù)是不一樣的，有的135136英文字母的普遍使用頻率美國(guó)密碼學(xué)家W.F.Friedman在調(diào)查了大量英文資料后,得出英文字母的普遍使用規(guī)律.47英文字母的普遍使用頻率美國(guó)密碼學(xué)家W.F.Friedma136137英文單字母使用頻率分類48英文單字母使用頻率分類137138特殊的特征開(kāi)頭結(jié)尾特征:有些文章的開(kāi)頭和結(jié)尾受到固定格式的限制有時(shí)文章中間的某些特定部位，某些字母也會(huì)出現(xiàn)較高的使用頻率。49特殊的特征開(kāi)頭結(jié)尾特征:138139頻度最高的前30個(gè)雙字母

50頻度最高的前30個(gè)雙字母139140頻度最高的前20個(gè)三字母

51頻度最高的前20個(gè)三字母140141其它頻率特征the的使用頻率最高，是ING的三倍，若把the去掉，t在第II類中排在最后，h會(huì)降為第III類，th和he也不是常出現(xiàn)的字母組了一半的單詞以esdt結(jié)尾一半的單詞以tasw開(kāi)頭Y的使用頻率90%都集中在單詞的結(jié)尾52其它頻率特征the的使用頻率最高，是ING的三倍，若把141142連接特征后連接：q…u前連接：x的前面總是i，e很少是o和a間斷連接：在e和e之間，r的出現(xiàn)頻率最高53連接特征后連接：q…u142143重復(fù)特征兩個(gè)字符以上的字符串重復(fù)出現(xiàn)的現(xiàn)象，叫做語(yǔ)言的重復(fù)特征。thtiontious54重復(fù)特征兩個(gè)字符以上的字符串重復(fù)出現(xiàn)的現(xiàn)象，叫做語(yǔ)言的重143例子-密文QRLLIQQPFVICXPFMTPZWRFNFOTFLPYWIGQPQHICQRGIVAKZWIQIBORGZWPFMQPFZWIOGVIGFCHIVYIGQIJIGCFLILCGIBRXHIZWOVQOBCFCXKQPQPFZRPZPOFXRLNZWICAPXPZKCZXICQZZOGICVZWIXCFMRCMIOBZWIOGPMPFCXZISZPQJIGKVIQPGCAXIARZFOZIQQIFZPCX144例子-密文QRLLIQQPFVICXPFMTPZWRFNFO144確定字母的相對(duì)頻率I可能相當(dāng)于明文中的e145確定字母的相對(duì)頻率56145雙字母頻率146最常見(jiàn)的雙字母組合ZW，Z猜測(cè)其為T，W對(duì)應(yīng)為HWI

HEPFIN雙字母頻率57最常見(jiàn)的雙字母組合ZW，Z猜測(cè)其為T，W對(duì)應(yīng)146進(jìn)一步分析-1ZWIQI與these相似，Q

STPZW與with類似，TWIQQIFZPCX與essential相似，CA，XLCFCXKQPQ與analysis類似，KYCAPXPZK與ability類似，AB147進(jìn)一步分析-158147進(jìn)一步分析-2ZWPFM與things類似，MGXCFMRCMI與language類似，RUVICXPFM與dealing類似，VDQRLLIQQ與success類似，LCGICV與read類似，GR148進(jìn)一步分析-259148進(jìn)一步分析-3LCGIBRX與careful類似，BFHICQRGIV與measured類似，HMHIZWOVQ與methods類似，OOJIGK猜測(cè)為veryYIGQIJIGCFLI猜測(cè)為perseveranceRFNFOTF猜測(cè)為unknown，把ZISZ猜測(cè)為text149進(jìn)一步分析-360149密鑰150密鑰61150完整明文Successindealingwithunknownciphersismeasuredbythesefourthingsintheordernamed：perseverance，carefulmethodsofanalysis，intuition，luck.Theabilityatleasttoreadthelanguageoftheoriginaltextisverydesirablebutnotessential.151完整明文Successindealingwithun151152對(duì)抗頻率分析的辦法多名或同音代替密碼多表代替密碼多字母代替密碼

63對(duì)抗頻率分析的辦法多名或同音代替密碼152153多名代替密碼

與簡(jiǎn)單代替密碼類似，只是映射是一對(duì)多的，每個(gè)明文字母可以加密成多個(gè)密文字母。例如，A可能對(duì)應(yīng)于5、13、25B可能對(duì)應(yīng)于7、9、31、4264多名代替密碼

與簡(jiǎn)單代替密碼類似，只是映射是一對(duì)多的，153154多表代替密碼多表代替密碼：是以一系列（兩個(gè)以上）代換表依此對(duì)明文消息的字母進(jìn)行代換的方法。非周期多表代替密碼：代換表是非周期的無(wú)限序列一次一密密碼（one-timepadding)：對(duì)每個(gè)明文每次采用不同的代換表。周期多表代替密碼：代換表