第3章 古典密碼技術(shù)

1、第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)1第第3 3章古典密碼技術(shù)章古典密碼技術(shù)本章內(nèi)容本章內(nèi)容 代換密碼技術(shù)代換密碼技術(shù) 置亂密碼技術(shù)置亂密碼技術(shù) 密碼分析技術(shù)密碼分析技術(shù)第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)2第第3 3章古典密碼技術(shù)章古典密碼技術(shù)教學(xué)要求教學(xué)要求 掌握單表和多表代換密碼技術(shù)掌握單表和多表代換密碼技術(shù) 了解置亂密碼技術(shù)和典型的古典密碼了解置亂密碼技術(shù)和典型的古典密碼 了解密碼分析的基本概念了解密碼分析的基本概念 掌握移位密碼和仿射密碼的破譯方法掌握移位密碼和仿射密碼的破譯方法第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)3英文字母與數(shù)字的對應(yīng)關(guān)系英文字母與數(shù)字的對應(yīng)關(guān)系 明文明

2、文小寫字母小寫字母密文密文大寫字母大寫字母第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)43.1 3.1 代換密碼技術(shù)代換密碼技術(shù)（substitution ciphersubstitution cipher）原理原理使用代換技術(shù)實(shí)現(xiàn)保密使用代換技術(shù)實(shí)現(xiàn)保密明文中的字母由其他字母、數(shù)字或明文中的字母由其他字母、數(shù)字或符號所取代符號所取代具體的代換方案稱為密鑰具體的代換方案稱為密鑰類型類型單表代換單表代換多表代換多表代換第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)5一、單表代換密碼一、單表代換密碼特點(diǎn)特點(diǎn)只有一張代換表只有一張代換表相同的明文加密為相同的密文相同的明文加密為相同的密文種類種類一般代換密碼一

3、般代換密碼特殊代換密碼特殊代換密碼移位密碼移位密碼仿射密碼仿射密碼第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)6一、單表代換密碼一、單表代換密碼1 1、一般代換密碼、一般代換密碼任意指定字符間的代換關(guān)系任意指定字符間的代換關(guān)系2626個(gè)英文字母的任意代換有個(gè)英文字母的任意代換有26！ 41026種種一種代換方案一種代換方案明文：明文：s su ub bs st ti it tu ut ti ionconci ipherpher密文：密文：L LP PH HL LA AE EA AP PA AE EDIKDIKE EONQV ONQV 相同的明文加密相同的明文加密為相同的密文！為相同的密文！密鑰量大

4、，但不便記憶和使用。密鑰量大，但不便記憶和使用。第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)7一、單表代換密碼一、單表代換密碼1 1、一般代換密碼、一般代換密碼一種使用密鑰字一種使用密鑰字communicationcommunication 的代換方案的代換方案明文：明文：substitutionciphersubstitutioncipher密文：密文：QSOQRBRSRBJHMBKTNPQSOQRBRSRBJHMBKTNP 剔除后來重復(fù)的字母后，剔除后來重復(fù)的字母后，真正的密鑰為：真正的密鑰為：comuniat comuniat 便于記憶和使用，但便于記憶和使用，但密鑰量大大減少！密鑰量大大減

5、少！第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)82 2、移位密碼、移位密碼（shift cipher） 符號：明文符號：明文p，密文，密文c，密鑰，密鑰k 加密：加密： 解密：解密： 密鑰量密鑰量 kq=26( )(mod26)kceppk( )(mod26)kpdcckk=3k=3時(shí)為時(shí)為愷撒密碼愷撒密碼CaesarCaesar。密文字母是明文字母的移位密文字母是明文字母的移位-代換的特例代換的特例第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)9CaesarCaesar密碼密碼(k=3)(k=3)舉例舉例( )3 (mod26)kcepp( )3 (mod26)kpdcc第第3 3章章 古典密碼技術(shù)

6、古典密碼技術(shù)103 3、仿射密碼、仿射密碼 ( (affine cipheraffine cipher) ) 加密：加密： 解密：解密：12()(mod 26)kcepk pk112( )() (mod 26)kpdckck1111111 (mod26)kkk k為 的乘法逆，滿足：1)26,gcd(1k12(k ,k )k 密鑰第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)11仿射密碼的密鑰量與乘法逆元仿射密碼的密鑰量與乘法逆元k1-11)26,gcd(1k12 26312qk 密鑰量密鑰量 k k1 1：1 1，3 3，5 5，7 7，9 9，1111，1515，1717，1919，2121，2

7、323，2525 k k2 2：0 02525k k1 1的乘法逆（的乘法逆（mod 26mod 26）1-1=1, 3-1=9, 5-1=21, 7-1=15, 9-1=3, 11-1=19, 15-1=7, 17-1=23, 19-1=11, 21-1=5, 23-1=17, 25-1=25第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)12仿射密碼加密實(shí)例仿射密碼加密實(shí)例 密鑰：密鑰： 加密函數(shù)：加密函數(shù)： 解密函數(shù)：解密函數(shù)： 明文：明文：cryptography 加密、解密過程加密、解密過程 )7,3(k()73 (mod 26)kcepp( )15(3) (mod 26)kpdcc1117

8、(mod 26)15k第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)13()73 (mod 26)kcepp( )15(3) (mod 26)kpdcc明文字符明文字符y y（2424）的加密、解密過程：）的加密、解密過程： 加密：加密：7 724+3=17115=P 24+3=17115=P （mod 26mod 26） 解密：解密：1515（15-315-3）=15=1512=18024=y 12=18024=y （mod 26mod 26） 第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)14試一試 假設(shè)k1=7，k2=3，明文為secret，利用仿射密碼算法給出對應(yīng)的密文 （18,4,2,17,4,

9、19）第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)15單表代換密碼的缺點(diǎn)單表代換密碼的缺點(diǎn) 密鑰量一般比較小，難以抵抗窮盡搜索攻擊密鑰量一般比較小，難以抵抗窮盡搜索攻擊 即使密鑰量很大，但因?yàn)闆]有將明文字母出現(xiàn)的頻即使密鑰量很大，但因?yàn)闆]有將明文字母出現(xiàn)的頻率掩藏起來，所以也很容易受到率掩藏起來，所以也很容易受到頻數(shù)分析法頻數(shù)分析法的攻擊的攻擊明、密文字母的頻數(shù)再現(xiàn)明、密文字母的頻數(shù)再現(xiàn)第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)16二、多表代換密碼二、多表代換密碼特點(diǎn)特點(diǎn)有多張代換表有多張代換表相同的明文可以加密為不同的密文相同的明文可以加密為不同的密文保密性能較好保密性能較好典型密碼典型密碼維吉尼

10、亞密碼維吉尼亞密碼希爾密碼希爾密碼第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)171 1、維吉尼亞密碼、維吉尼亞密碼（Vigenere cipherVigenere cipher） 二、多表代換密碼二、多表代換密碼密鑰密鑰K=（k1,k2,kn）明文明文P=（p1,p2,pn）密文密文C=（c1,c2,cn）加密：加密： ci=pi+ki （mod 26）解密：解密： pi=ci-ki (mod 26)本質(zhì)：本質(zhì)： 多個(gè)移位密碼多個(gè)移位密碼密鑰量：密鑰量：n n位密鑰位密鑰密鑰一般是一個(gè)密鑰一般是一個(gè)單詞或一句話去單詞或一句話去除后面的重復(fù)字除后面的重復(fù)字母后構(gòu)成母后構(gòu)成)!26(!26nkq第第

11、3 3章章 古典密碼技術(shù)古典密碼技術(shù)18維吉尼亞密表維吉尼亞密表第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)19維吉尼亞密碼舉例維吉尼亞密碼舉例密鑰字：密鑰字：common明文：明文：cryptography真正密鑰：真正密鑰：comn（4位分組）位分組）相同的明相同的明文有了不文有了不同的密文同的密文第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)202 2、希爾密碼、希爾密碼 （Hill cipherHill cipher） 明文：明文： 密文：密文： 密鑰：密鑰：由數(shù)學(xué)家由數(shù)學(xué)家Lester HillLester Hill于于19291929年發(fā)明年發(fā)明二、多表代換密碼二、多表代換密碼dpppp,2

12、1dcccc,21ddddddkkkkkkkkkk212221212111k k必須滿足的條件必須滿足的條件 非奇異矩陣，即非奇異矩陣，即|K|K| 0 0； gcd(|K|,26)=1 mod 26gcd(|K|,26)=1 mod 26。第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)212 2、希爾密碼、希爾密碼 加密：加密：mod 26cp k1121121222121212,(mod 26)ddddddddkkkkkkc ccp ppkkk1122mod 26jjjdjdcpkpkpk第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)222 2、希爾密碼、希爾密碼 解密：解密：111211212221

13、21212,(mod 26)ddddddddkkkkkkp ppc cckkk1mod 26pck)26(mod11Ikkkk)26(mod| /*1*1kkkkk*( 1)|(mod 26)ijjiijkk 1*|ijjiijjiIkkkkkkkkkk： 主對角線單位矩陣：的逆矩陣| |：的行列式值：去掉第 行第 列元素后的行列式值：的伴隨矩陣： 中第 行第 列的元素第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)23希爾密碼舉例希爾密碼舉例192221182151717kphot（1 1）確定解密密鑰矩陣）確定解密密鑰矩陣k k-1-1 ：192221182151717k17 18 1921 2

14、52 17 21 5 18 221 2 17 19 17 215814210714 18071467839393 (mod 26)23 (mod 26) 1726mod2311k)26(mod10681772514182117172217172218212121517192517192212121185171925171922118*k11*14257238425119491517 7181191713615176(mod 26)60110201724017kkk第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)24希爾密碼舉例希爾密碼舉例192221182151717kphot（2 2）加密）加密 ：

15、將明文字符將明文字符h h、o o、t t變換為數(shù)字，分別為變換為數(shù)字，分別為7 7、1414、19 19 。171757141921 1821(451409690)2219(91914) (mod 26)()cp kJTO第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)25希爾密碼舉例希爾密碼舉例192221182151717kphot（3 3）解密）解密149151517624017k()(91914)cJTO149159191415176(657404487)24017(71419)(mod 26)()pc khot第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)26希爾密碼的特點(diǎn)希爾密碼的特點(diǎn) 完全隱

16、藏了單字母的頻數(shù)完全隱藏了單字母的頻數(shù) 字母和數(shù)字的對應(yīng)可以改成其它方案，字母和數(shù)字的對應(yīng)可以改成其它方案，使得更不容易攻擊成功使得更不容易攻擊成功 能比較好地抵抗頻數(shù)法的分析，對抗能比較好地抵抗頻數(shù)法的分析，對抗唯密文的攻擊強(qiáng)度較高唯密文的攻擊強(qiáng)度較高 易受已知明文攻擊易受已知明文攻擊第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)273.2 3.2 置亂密碼技術(shù)置亂密碼技術(shù) 置亂（置亂（permutation）也叫換位（）也叫換位（transposition），它通過），它通過打亂明文字符的順序?qū)崿F(xiàn)信息的保密。打亂明文字符的順序?qū)崿F(xiàn)信息的保密。 由此得到的密碼稱為由此得到的密碼稱為置亂密碼置亂密碼

17、（permutation cipher）或）或換換位密碼位密碼（transposition caipher）。）。 由于重新排列了消息中的字符，所以打破了明文的結(jié)構(gòu)特性由于重新排列了消息中的字符，所以打破了明文的結(jié)構(gòu)特性 n個(gè)明文字符任意置亂的密鑰量：個(gè)明文字符任意置亂的密鑰量：kq=n! 典型處理方法：將明文按行寫在一張格紙上，然后再按列的典型處理方法：將明文按行寫在一張格紙上，然后再按列的方式讀出結(jié)果方式讀出結(jié)果 為了增加變換的復(fù)雜性，可以設(shè)定讀出列的不同次序（即密為了增加變換的復(fù)雜性，可以設(shè)定讀出列的不同次序（即密鑰）鑰） 第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)28置亂密碼加密例子置亂

18、密碼加密例子 明文明文 The process of transforming plaintext into ciphertext is called encipherment or encryption; the reverse process of transforming ciphertext into plaintext is called decipherment or decryption 按列讀出按列讀出時(shí)，順序時(shí)，順序大亂！大亂！列越多，列越多，越亂。越亂。第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)29更簡單的一個(gè)例子更簡單的一個(gè)例子 明文：明文：cryptography is

19、an applied science 密鑰：密鑰：encry（字母順序：（字母順序：23145）（即讀出列順序）（即讀出列順序） 密文：密文： yripdn cohnii rgyaee paspsc tpalce 第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)303.3 3.3 密碼分析密碼分析一、密碼分析的基本概念一、密碼分析的基本概念密碼分析：密碼分析：破譯破譯（breakbreak）、）、攻擊攻擊( (attackattack) ) 竊密者在不知道解密密鑰和通信者所采竊密者在不知道解密密鑰和通信者所采用的加密體制的細(xì)節(jié)的條件下，對截獲的密用的加密體制的細(xì)節(jié)的條件下，對截獲的密文進(jìn)行分析，以獲取

20、解密信息（明文或密文進(jìn)行分析，以獲取解密信息（明文或密鑰）。鑰）。1 1、密碼分析的基本過程、密碼分析的基本過程分析分析假設(shè)假設(shè)推斷推斷證實(shí)證實(shí)第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)312 2、密碼分析的基本類型、密碼分析的基本類型唯密文攻擊唯密文攻擊（Ciphertext onlyCiphertext only） 破譯者已知：加密算法、待破譯的密文破譯者已知：加密算法、待破譯的密文 已知明文攻擊已知明文攻擊（Known plaintextKnown plaintext） 破譯者已知：加密算法、一定數(shù)量的密文和對應(yīng)的明文破譯者已知：加密算法、一定數(shù)量的密文和對應(yīng)的明文 選擇明文攻擊選擇明文攻

21、擊（Chosen plaintextChosen plaintext） 破譯者已知：加密算法、選定的明文和對應(yīng)的密文破譯者已知：加密算法、選定的明文和對應(yīng)的密文選擇密文攻擊選擇密文攻擊（Chosen ciphertextChosen ciphertext） 破譯者已知：加密算法、選定的密文和對應(yīng)的明文破譯者已知：加密算法、選定的密文和對應(yīng)的明文選擇文本攻擊選擇文本攻擊（Chosen textChosen text） 破譯者已知：加密算法、選定的明文和對應(yīng)的密文、選破譯者已知：加密算法、選定的明文和對應(yīng)的密文、選定的密文和對應(yīng)的明文定的密文和對應(yīng)的明文 第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)3

22、23 3、密碼分析的基本方法、密碼分析的基本方法（1 1）窮舉破譯法：蠻力攻擊法）窮舉破譯法：蠻力攻擊法對截獲的密文依次用可解的密鑰試譯，直到得到有對截獲的密文依次用可解的密鑰試譯，直到得到有意義的明文；意義的明文；或在不變密鑰下，對所有可能的明文加密，直到得或在不變密鑰下，對所有可能的明文加密，直到得到與截獲密文一致為止。到與截獲密文一致為止。任何一種實(shí)用的能保障安全的密碼，都必須設(shè)計(jì)得任何一種實(shí)用的能保障安全的密碼，都必須設(shè)計(jì)得能夠使該方法不可行。途徑就是使密鑰量極大。能夠使該方法不可行。途徑就是使密鑰量極大。第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)33窮舉法平均破譯時(shí)間窮舉法平均破譯時(shí)間

23、宇宙年齡：大約宇宙年齡：大約10101111年！年！第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)34（2 2）分析破譯法）分析破譯法確定性分析法確定性分析法 利用一個(gè)或幾個(gè)已知量（例如明利用一個(gè)或幾個(gè)已知量（例如明- -密對），密對），用數(shù)學(xué)關(guān)系式表示所求未知數(shù)（例如密鑰）。用數(shù)學(xué)關(guān)系式表示所求未知數(shù)（例如密鑰）。統(tǒng)計(jì)分析法統(tǒng)計(jì)分析法 利用明文的某些已知的統(tǒng)計(jì)特性破譯。利用明文的某些已知的統(tǒng)計(jì)特性破譯。例如，利用英文字母的頻數(shù)特性，可以破譯例如，利用英文字母的頻數(shù)特性，可以破譯任何單表代換密碼。任何單表代換密碼。第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)35英文字母的頻數(shù)特性英文字母的頻數(shù)特性頻數(shù)比

24、較高的幾個(gè)英文字母頻數(shù)比較高的幾個(gè)英文字母e e、t t、a a、o o、i i、n n、s s、h h、r r第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)36二、密碼分析舉例二、密碼分析舉例解：解：解密公式為解密公式為 例例3-5 用窮舉法破譯下面的一段移位密碼密文：用窮舉法破譯下面的一段移位密碼密文：UJTUQJQNPJXUWNSLUJTUQJQNPJXUWNSL 1 1、窮舉法破譯移位密碼、窮舉法破譯移位密碼)26(modkcp密文密文 UJTUQJQNPJXUWNSLUJTUQJQNPJXUWNSLk=1 tistpipmoiwtvmrkk=1 tistpipmoiwtvmrkk=2 sh

25、rsoholnhvsulqjk=2 shrsoholnhvsulqjk=3 rgqrngnkmgurtkpik=3 rgqrngnkmgurtkpik=4 qfpqmfmjlftqsjohk=4 qfpqmfmjlftqsjohk=5 peoplelikespringk=5 peoplelikespring密鑰密鑰 f f（5 5）明文明文people like springpeople like spring 第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)37基本過程基本過程 統(tǒng)計(jì)密文中各個(gè)字母出現(xiàn)的頻數(shù)統(tǒng)計(jì)密文中各個(gè)字母出現(xiàn)的頻數(shù) 根據(jù)密文中出現(xiàn)的各個(gè)字母的頻數(shù)，根據(jù)密文中出現(xiàn)的各個(gè)字母的頻數(shù)，

26、和英語字母標(biāo)準(zhǔn)頻數(shù)進(jìn)行對比分析，和英語字母標(biāo)準(zhǔn)頻數(shù)進(jìn)行對比分析，做出假設(shè)，推論加密所用的公式做出假設(shè)，推論加密所用的公式 證實(shí)上述假設(shè)或繼續(xù)作其他假設(shè)證實(shí)上述假設(shè)或繼續(xù)作其他假設(shè)2 2、頻數(shù)法破譯仿射密碼、頻數(shù)法破譯仿射密碼第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)38例例3-6 用頻數(shù)法破譯下面的一段仿射密碼密文：用頻數(shù)法破譯下面的一段仿射密碼密文： PWUFFOGWCHFDWIWEJOUUNJORSMDWRHVCMWJUPVCCG 破譯舉例破譯舉例解解 （1 1）密文字母頻數(shù)統(tǒng)計(jì)：）密文字母頻數(shù)統(tǒng)計(jì)：4141個(gè)字符個(gè)字符頻數(shù)較高的密文字母：頻數(shù)較高的密文字母：W，C，U，F(xiàn)，J，O第第3 3

27、章章 古典密碼技術(shù)古典密碼技術(shù)39（2 2）假設(shè)與推論、證實(shí)）假設(shè)與推論、證實(shí)頻數(shù)較高的密文字母：頻數(shù)較高的密文字母：W，C，U，F(xiàn)，J，O頻數(shù)較高的明文字母：頻數(shù)較高的明文字母：e e、t t、a a、o o、i i、n n、s s、h h、r r加密公式：加密公式：解密公式：解密公式： )26(mod)(21kpkpeck)26(mod)()(211kckcdpk1)26,gcd(1k第一次假設(shè)：第一次假設(shè)： W(22)e(4), C(2)t(19)W(22)e(4), C(2)t(19) )26(mod42221kk )26(mod19221kk 115206 (mod 26)k 111

28、567 64216 (mod 26)k2)26,16gcd()26,gcd(1k 錯(cuò)誤錯(cuò)誤第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)40（2 2）假設(shè)與推論、證實(shí)）假設(shè)與推論、證實(shí)頻數(shù)較高的密文字母：頻數(shù)較高的密文字母：W，C，U，F(xiàn)，J，O頻數(shù)較高的明文字母：頻數(shù)較高的明文字母：e e、t t、a a、o o、i i、n n、s s、h h、r r加密公式：加密公式：解密公式：解密公式： )26(mod)(21kpkpeck)26(mod)()(211kckcdpk1)26,gcd(1k第二次假設(shè)：第二次假設(shè)： W(22)e(4), U(22)t(19)W(22)e(4), U(22)t(19) )26(mod42221kk 122019(mod 26)kk115224 (mod 26)k 1115247 2416812 (mod 26)k1gcd( ,26)gcd(12,26)2k 錯(cuò)誤錯(cuò)誤第第3 3章章 古典密碼技術(shù)古典密碼技術(shù)41（2 2）