1、1第二章第二章 古典密碼古典密碼n1. 學(xué)習(xí)基本的密碼編制原理;n2.了解早期編制密碼的基本方法;n3. 為進(jìn)一步學(xué)習(xí)現(xiàn)代密碼的編制打下基礎(chǔ)。23我們將重點(diǎn)介紹我們將重點(diǎn)介紹代替密碼代替密碼 4 一、單表代替密碼：一、單表代替密碼： 利用預(yù)先設(shè)計(jì)的利用預(yù)先設(shè)計(jì)的固定固定代替規(guī)則代替規(guī)則, ,對(duì)明對(duì)明文文逐逐字符字符或或逐逐字符組字符組進(jìn)行代替的密碼進(jìn)行代替的密碼. . 字符組稱為一個(gè)代替單位字符組稱為一個(gè)代替單位. . 這里這里代替規(guī)則代替規(guī)則又稱為又稱為代替函數(shù)代替函數(shù)、代替表代替表或或S S盒。盒。它的它的固定性固定性是指這個(gè)代替規(guī)則與是指這個(gè)代替規(guī)則與密密鑰因素鑰因素和被加密的明文字符的

2、和被加密的明文字符的序號(hào)序號(hào)無關(guān)。無關(guān)。 即即相同的相同的明文字符組產(chǎn)生明文字符組產(chǎn)生相同的相同的密文字密文字符組符組. .5 例例1: 1: 漢字和符號(hào)的區(qū)位碼漢字和符號(hào)的區(qū)位碼( (單表代替單表代替) ) 6例例2 2 以十進(jìn)值數(shù)為代替單位的代替函數(shù)則明文則明文晨五點(diǎn)總攻晨五點(diǎn)總攻 先變換為區(qū)位碼先變換為區(qū)位碼 1931 4669 2167 5560 1505 再被加密成密文 4624 1996 8497 0095 4050單表代替的缺點(diǎn):明文字符相同,則密文字符也相同9 , 2 , 1 , 09 , 2 , 1 , 0:S105,4,8,2,1, 0,9,7,3,6S假設(shè)明文 0 1 2

3、 3 4 5 6 7 8 9密文 5 4 8 2 1 0 9 7 3 6即代替表為即代替表為: :7qkmmEckmod)()(加密變換加密變換:1, 2 , 1 , 0qZq 例例3 3 加法密碼加法密碼 選定選定常數(shù)常數(shù) q 和和 k. . 明文空間明文空間= =密文空間密文空間= =qkccDmkmod)()(脫密變換脫密變換： 其中其中 讀作讀作 n 模模q, ,它是它是n n被被q q除后所得的余數(shù)除后所得的余數(shù). . 如如18 18 mod7 = 4 mod7 = 4 上述加法稱為上述加法稱為模模q加加.qn mod890,10mod) 3()(3mmmEc加密變換為加密變換為：

4、特別地特別地,若取若取q =10 和和 k=3, ,則則脫密變換為脫密變換為：90,10mod) 3()(3cccDm 此時(shí)此時(shí), ,明文明文: :晨五點(diǎn)總攻晨五點(diǎn)總攻 變換為區(qū)位碼變換為區(qū)位碼1931 4669 2167 5560 1505后就被加密成密文4264 7992 5490 8893 4838 缺點(diǎn): 密文差 = 明文差10mod)(10mod)3() 3(10mod) 3(10mod) 3(21212121mmmmmmcc9( (凱撒密碼) ) 這是一種對(duì)英文字母的典型逐字母加密的的加法密碼,其密鑰k=3。 英文字母被編碼為該字母的序號(hào) 英文 A B C D X Y Z 數(shù)字 0

5、 1 2 3 23 24 25250,26mod)3()(3mmmEc加密變換為加密變換為：脫密變換為脫密變換為：250,26mod)3()(3cccDm10 這是一種對(duì)英文字母的典型逐字母加密的密碼,它利用一個(gè)密鑰字來構(gòu)造代替表。 如如: : 若選擇cipher作為密鑰字,則對(duì)應(yīng)代替表為:明文明文 A B C D E F G H I J K L M N O P A B C D E F G H I J K L M N O P 密文密文 C I P H E RC I P H E R A B D F G J K L M N A B D F G J K L M N 1110mod)()(kmmEck

6、例例4 4：加密變換為加密變換為: : 二、多表代替密碼二、多表代替密碼 根據(jù)密鑰的指示，來選擇加密時(shí)使用的單根據(jù)密鑰的指示，來選擇加密時(shí)使用的單表的方法，稱為表的方法，稱為多表代替多表代替密碼。密碼。但但 k 不再是固定常數(shù)而是密鑰。不再是固定常數(shù)而是密鑰。加密算法：加密算法： 明明 文：文： 晨晨 五五 點(diǎn)點(diǎn) 總總 攻攻明文序列：明文序列： 1931 4669 2167 5560 1505密鑰序列：密鑰序列： 4321 5378 4322 3109 11074321 5378 4322 3109 1107密文序列：密文序列： 5252 9937 6489 8669 26025252 993

7、7 6489 8669 2602若密鑰序列是隨機(jī)的若密鑰序列是隨機(jī)的, ,該密碼就是該密碼就是絕對(duì)安全絕對(duì)安全的的. .隨機(jī)隨機(jī)就是指序列的信號(hào)相互就是指序列的信號(hào)相互獨(dú)立獨(dú)立且且等概等概分布分布. .1226mod)()(kmmEck將對(duì)英文字母的加密變換改為：將對(duì)英文字母的加密變換改為： 當(dāng)將明、密文空間均改為當(dāng)將明、密文空間均改為25, 2 , 1 , 026Z這個(gè)密碼就是一個(gè)著名的古典密碼體制：這個(gè)密碼就是一個(gè)著名的古典密碼體制：維幾尼亞密碼維幾尼亞密碼（VigenereVigenere密碼體制）密碼體制）,21tmmm若若明文序列明文序列為為: :,21tkkk密鑰序列密鑰序列為：為

8、：,21tccc則則密文序列密文序列為為: :其中：其中：26mod)()(iiikikmmEci這也是序列密碼的一般加密形式這也是序列密碼的一般加密形式將英文字母編碼為它的序號(hào)(0起算)13維維幾幾利利亞亞密密碼碼的的代代替替表表為為明文字母密鑰字母密鑰字母為d,明文字母為b時(shí)查表得密文字母為e1426mod)()(mkmEck將對(duì)英文字母的加密變換改為：將對(duì)英文字母的加密變換改為： 當(dāng)將明、密文空間均設(shè)為當(dāng)將明、密文空間均設(shè)為25, 2 , 1 , 026Z,21tmmm若若明文序列明文序列為為: :,21tkkk密鑰序列密鑰序列為：為：,21tccc則則密文序列密文序列為為: :其中：其

9、中：26mod)()(iiikimkmEci該密碼稱為該密碼稱為維福特密碼維福特密碼（BeaufortBeaufort密碼體制）密碼體制）此時(shí)脫密變換與加密變換完全相同，也是：此時(shí)脫密變換與加密變換完全相同，也是：26mod)()(ckcEmk15 如果將明、密文空間均改為如果將明、密文空間均改為1 , 02Z將加密變換改為：將加密變換改為：kmkmmEck定義2mod)()(,21tmmm若若明文序列明文序列為為：,21tkkk密鑰序列密鑰序列為：為：,21tccc則則密文序列密文序列為：為：其中：其中：iiikikmmEci)(這是眾所周知的完全保密的密碼體制這是眾所周知的完全保密的密碼體

10、制這個(gè)密碼就是著名的這個(gè)密碼就是著名的VernamVernam密碼體制密碼體制16 代替密碼的安全性分析代替密碼的安全性分析 1. 單表代替的優(yōu)缺點(diǎn)單表代替的優(yōu)缺點(diǎn) 優(yōu)點(diǎn)優(yōu)點(diǎn): 明文字符的形態(tài)一般將面目全非明文字符的形態(tài)一般將面目全非 缺點(diǎn)缺點(diǎn): (A) 明文的位置不變明文的位置不變; (B) 明文字符明文字符相同相同,則則密文字符密文字符也相同也相同; 從而導(dǎo)致從而導(dǎo)致: (I) 若明文字符若明文字符e被加密成密文字符被加密成密文字符a,則明文則明文中中e的出現(xiàn)次數(shù)就是密文中字符的出現(xiàn)次數(shù)就是密文中字符a的出現(xiàn)次數(shù)的出現(xiàn)次數(shù); (II) 明文的跟隨關(guān)系反映在密文之中明文的跟隨關(guān)系反映在密文之

11、中. 因此因此,明文字符的統(tǒng)計(jì)規(guī)律就完全暴露在明文字符的統(tǒng)計(jì)規(guī)律就完全暴露在密文字符的統(tǒng)計(jì)規(guī)律之中密文字符的統(tǒng)計(jì)規(guī)律之中.形態(tài)變但位置不變形態(tài)變但位置不變17e：出現(xiàn)的頻率約為0.127t，a，o，i，n，s，h，r：出現(xiàn)的頻率約在0.06到0.09之間d，l：的出現(xiàn)頻率約為0.04c，u，m，w，f，g，y，p，b ：的出現(xiàn)頻率約在0.015到0.028之間v，k，j，x，q，z：出現(xiàn)的頻率小于0.011819 代替密碼的安全性分析代替密碼的安全性分析 2. 多表代替的優(yōu)缺點(diǎn)多表代替的優(yōu)缺點(diǎn) 優(yōu)點(diǎn)優(yōu)點(diǎn): 只要只要 (1) 多表設(shè)計(jì)合理多表設(shè)計(jì)合理,即每行中元互不相同即每行中元互不相同,每列每

12、列中元互不相同中元互不相同.(這樣的表稱為拉丁方表這樣的表稱為拉丁方表) (2) 密鑰序列是隨機(jī)序列密鑰序列是隨機(jī)序列，即具有等概性和，即具有等概性和獨(dú)立性。獨(dú)立性。這個(gè)多表代替就是完全保密的。這個(gè)多表代替就是完全保密的。 等概性等概性:各位置的字符取可能字符的概率相同；各位置的字符取可能字符的概率相同； 獨(dú)立性：獨(dú)立性：在其它所有字符都知道時(shí)，也判斷在其它所有字符都知道時(shí)，也判斷不出未知的字符取哪個(gè)的概率更大。不出未知的字符取哪個(gè)的概率更大。20 代替密碼的安全性分析代替密碼的安全性分析 2. 多表代替的優(yōu)缺點(diǎn)多表代替的優(yōu)缺點(diǎn) 密鑰序列是隨機(jī)序列意味著：密鑰序列是隨機(jī)序列意味著： （1）密鑰

13、序列不能周期重復(fù)；）密鑰序列不能周期重復(fù)； （2）密鑰序列必須與明文序列等長；）密鑰序列必須與明文序列等長； （3）這些序列必須在通信前分配完畢；）這些序列必須在通信前分配完畢； （4）大量通信時(shí)不實(shí)用；）大量通信時(shí)不實(shí)用； （5）分配密鑰和存儲(chǔ)密鑰時(shí)安全隱患大。）分配密鑰和存儲(chǔ)密鑰時(shí)安全隱患大。 缺點(diǎn)：缺點(diǎn)：周期較短時(shí)可以實(shí)現(xiàn)唯密文攻擊。周期較短時(shí)可以實(shí)現(xiàn)唯密文攻擊。 解決方案：解決方案：密鑰序列有少量真隨機(jī)的數(shù)密鑰序列有少量真隨機(jī)的數(shù)按固定的算法生成，只要它很像隨機(jī)序列即可。按固定的算法生成，只要它很像隨機(jī)序列即可。這種序列稱為偽隨機(jī)序列。這種序列稱為偽隨機(jī)序列。 21移移 位位 密密 碼

14、碼 對(duì)明文字符或字符組的進(jìn)行對(duì)明文字符或字符組的進(jìn)行位置移動(dòng)位置移動(dòng)的密碼的密碼 例例：設(shè)：設(shè)明文明文為：為： 北京科技大學(xué)信息工程學(xué)院北京科技大學(xué)信息工程學(xué)院移位方式：移位方式：S9=2,11,5,10,7,3,4,8,9,1,12,6即即:第第 i 個(gè)密文漢字就是第個(gè)密文漢字就是第S i個(gè)明文漢字個(gè)明文漢字.則則密文密文為為京學(xué)大程信科技息工北院學(xué)京學(xué)大程信科技息工北院學(xué)移位也是現(xiàn)代密碼中必用的一種編碼技術(shù)移位也是現(xiàn)代密碼中必用的一種編碼技術(shù) 22 移位密碼的安全性分析移位密碼的安全性分析 1. 移位密碼的優(yōu)缺點(diǎn)移位密碼的優(yōu)缺點(diǎn) 優(yōu)點(diǎn)優(yōu)點(diǎn): 明文字符的位置發(fā)生變化明文字符的位置發(fā)生變化;

15、缺點(diǎn)缺點(diǎn): (A) 明文字符的形態(tài)不變明文字符的形態(tài)不變; 從而導(dǎo)致從而導(dǎo)致: (I) 密文字符密文字符e的出現(xiàn)頻次的出現(xiàn)頻次也是明文字符也是明文字符e的出現(xiàn)次的出現(xiàn)次數(shù)數(shù); 有時(shí)直接可破有時(shí)直接可破! (如密文字母全相同如密文字母全相同) 目前也有現(xiàn)成的破譯方法目前也有現(xiàn)成的破譯方法.移位密碼優(yōu)缺點(diǎn)總結(jié)移位密碼優(yōu)缺點(diǎn)總結(jié): 位置變位置變但但形態(tài)不變形態(tài)不變.代替密碼優(yōu)缺點(diǎn)總結(jié)代替密碼優(yōu)缺點(diǎn)總結(jié): 形態(tài)變形態(tài)變但但位置不變位置不變.23 結(jié)論結(jié)論: : 將代替密碼和移位密碼輪番使用,必然可以發(fā)揮各自的長處,克服對(duì)方的缺點(diǎn)!必然可以設(shè)計(jì)出安全的密碼體制! 這就是現(xiàn)代密碼的設(shè)計(jì)思想!24單表古典密

16、碼的統(tǒng)計(jì)分析單表古典密碼的統(tǒng)計(jì)分析原理原理：明文的統(tǒng)計(jì)規(guī)律在密文中能夠反映出：明文的統(tǒng)計(jì)規(guī)律在密文中能夠反映出 來，故信息泄露大。來，故信息泄露大。多表古典密碼的統(tǒng)計(jì)分析多表古典密碼的統(tǒng)計(jì)分析原理原理：密鑰相同時(shí)，相同的明文對(duì)應(yīng)相同的：密鑰相同時(shí)，相同的明文對(duì)應(yīng)相同的 密文。密文。252627最常用，出現(xiàn)頻率在百分之一以上的有14個(gè)音節(jié)，它們是：de shi yi bu you zhi le ji zhe wo yen li ta dao的是 一 不有之 了機(jī) 這我們 里 他 到次常用音節(jié)有33個(gè)，它們是：zhong zi guo shang ge men he wei ye da gong

17、jian jiu xiang zhu lai sheng di zai ni xiao ke yao wu yu jie jin chan zuo jia xian quan shuo 28從三億漢字的母體材料中，抽樣二千五百萬字進(jìn)行雙音節(jié)詞詞頻統(tǒng)計(jì)，結(jié)果是：頻率在一萬次以上的雙音節(jié)詞有33個(gè)：我們?nèi)f次以上可以 他們 二萬次以上進(jìn)行 沒有 工作 人民 生產(chǎn) 這個(gè) 發(fā)展 就是 問題 國家 中國 這樣 革命 自己 不能 由于 這些 所以 因此 作用 一般 什么 如果 情況 必須 方法 因?yàn)?主要 要求 社會(huì)29多表古典密碼的統(tǒng)計(jì)分析多表古典密碼的統(tǒng)計(jì)分析步驟步驟1：首先確定密鑰的長度：利用：首先

18、確定密鑰的長度：利用Kasiski測(cè)試法測(cè)試法和重合指數(shù)法和重合指數(shù)法(index of coincidence)步驟步驟2：確定具體的密鑰內(nèi)容：交互重合指數(shù)法：確定具體的密鑰內(nèi)容：交互重合指數(shù)法30 尋找密文中相同的片段對(duì)，計(jì)算每對(duì)相同密文片段對(duì)尋找密文中相同的片段對(duì)，計(jì)算每對(duì)相同密文片段對(duì)之間的距離，不妨記為之間的距離，不妨記為d1,d2,di，若令密鑰字的長度為，若令密鑰字的長度為m，則，則m=gcd(d1,d2,di)。 定理定理1 若兩個(gè)相同的明文片段之間的距離是密鑰長度若兩個(gè)相同的明文片段之間的距離是密鑰長度的倍數(shù)，則這兩個(gè)明文段對(duì)應(yīng)的密文一定相同。的倍數(shù)，則這兩個(gè)明文段對(duì)應(yīng)的密文

19、一定相同。 反之則不然。反之則不然。 若密文中出現(xiàn)兩個(gè)相同的密文段若密文中出現(xiàn)兩個(gè)相同的密文段(密文段的長度密文段的長度m2)，則它們對(duì)應(yīng)的明文（及密鑰）將以很大的概率相同。則它們對(duì)應(yīng)的明文（及密鑰）將以很大的概率相同。Kasiski測(cè)試法：測(cè)試法：Kasiski于于1863年提出年提出3130.9999991126 32進(jìn)一步判斷密鑰字的長度是否為 m=gcd(d1,d2,di). 定義1設(shè)X=x1x2xn是一個(gè)長度為n的英文字母串，則x中任意選取兩個(gè)字母相同的概率定義為重合指數(shù)，用 表示。)(xIc33定理1設(shè)英文字母A，B,，Z在X中出現(xiàn)的次數(shù)分別為：f0,f1,f25則從X中任意選取兩

20、個(gè)字母相同的概率為 證明在X中任意選取兩個(gè)字母共有種 選取的可能；在X中的每個(gè)相同的字母中選取兩個(gè)元素共有 種選取的可能。故易證。證畢。) 1() 1()(250nnffXIiiic2) 1(2nnCn2) 1(2iifffCi34已知每個(gè)英文字母出現(xiàn)的期望概率，分別記為已知每個(gè)英文字母出現(xiàn)的期望概率，分別記為p0,p1,p25，那么，那么X中兩個(gè)元素相同的概率中兩個(gè)元素相同的概率為：為： =0.065 2502)(iicpXI35對(duì)于英文的一個(gè)隨機(jī)字母串，每個(gè)英文字對(duì)于英文的一個(gè)隨機(jī)字母串，每個(gè)英文字母出現(xiàn)的期望概率均為母出現(xiàn)的期望概率均為1/26，則在，則在X中任中任意選取兩個(gè)元素相同的概率為意選取兩個(gè)元素相同的概率為=0.038.2250261icI36根據(jù)根據(jù)Kasiski測(cè)試法得到的測(cè)試法得到的m，可以將密文，可以將密文Y按照下列形式排按照下列形式排列：列：表表1將將Y排列成排列成m行行n/m列的形式，設(shè)列的形式，設(shè)m=0(modn)nmmmmnmmnmmn