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

2、和被加密的明文字符的序號序號無關。無關。 即即相同的相同的明文字符組產生明文字符組產生相同的相同的密文字密文字符組符組. .5 例例1: 1: 漢字和符號的區位碼漢字和符號的區位碼( (單表代替單表代替) ) 6例例2 2 以十進值數為代替單位的代替函數則明文則明文晨五點總攻晨五點總攻 先變換為區位碼先變換為區位碼 1931 4669 2167 5560 1505 再被加密成密文 4624 1996 8497 0095 4050單表代替的缺點:明文字符相同,則密文字符也相同9 , 2 , 1 , 09 , 2 , 1 , 0:S105,4,8,2,1, 0,9,7,3,6S假設明文 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 加法密碼加法密碼 選定選定常數常數 q 和和 k. . 明文空間明文空間= =密文空間密文空間= =qkccDmkmod)()(脫密變換脫密變換： 其中其中 讀作讀作 n 模模q, ,它是它是n n被被q q除后所得的余數除后所得的余數. . 如如18 18 mod7 = 4 mod7 = 4 上述加法稱為上述加法稱為模模q加加.qn mod890,10mod) 3()(3mmmEc加密變換為加密變換為：

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

5、 1 2 3 23 24 25250,26mod)3()(3mmmEc加密變換為加密變換為：脫密變換為脫密變換為：250,26mod)3()(3cccDm10 這是一種對英文字母的典型逐字母加密的密碼,它利用一個密鑰字來構造代替表。 如如: : 若選擇cipher作為密鑰字,則對應代替表為:明文明文 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：加密變換為加密變換為: : 二、多表代替密碼二、多表代替密碼 根據密鑰的指示，來選擇加密時使用的單根據密鑰的指示，來選擇加密時使用的單表的方法，稱為表的方法，稱為多表代替多表代替密碼。密碼。但但 k 不再是固定常數而是密鑰。不再是固定常數而是密鑰。加密算法：加密算法： 明明 文：文： 晨晨 五五 點點 總總 攻攻明文序列：明文序列： 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若密鑰序列是隨機的若密鑰序列是隨機的, ,該密碼就是該密碼就是絕對安全絕對安全的的. .隨機隨機就是指序列的信號相互就是指序列的信號相互獨立獨立且且等概等概分布分布. .1226mod)()(kmmEck將對英文字母的加密變換改為：將對英文字母的加密變換改為： 當將明、密文空間均改為當將明、密文空間均改為25, 2 , 1 , 026Z這個密碼就是一個著名的古典密碼體制：這個密碼就是一個著名的古典密碼體制：維幾尼亞密碼維幾尼亞密碼（VigenereVigenere密碼體制）密碼體制）,21tmmm若若明文序列明文序列為為: :,21tkkk密鑰序列密鑰序列為：為

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

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

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

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

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

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

14、碼 對明文字符或字符組的進行對明文字符或字符組的進行位置移動位置移動的密碼的密碼 例例：設：設明文明文為：為： 北京科技大學信息工程學院北京科技大學信息工程學院移位方式：移位方式：S9=2,11,5,10,7,3,4,8,9,1,12,6即即:第第 i 個密文漢字就是第個密文漢字就是第S i個明文漢字個明文漢字.則則密文密文為為京學大程信科技息工北院學京學大程信科技息工北院學移位也是現代密碼中必用的一種編碼技術移位也是現代密碼中必用的一種編碼技術 22 移位密碼的安全性分析移位密碼的安全性分析 1. 移位密碼的優缺點移位密碼的優缺點 優點優點: 明文字符的位置發生變化明文字符的位置發生變化;

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

16、碼的統計分析單表古典密碼的統計分析原理原理：明文的統計規律在密文中能夠反映出：明文的統計規律在密文中能夠反映出 來，故信息泄露大。來，故信息泄露大。多表古典密碼的統計分析多表古典密碼的統計分析原理原理：密鑰相同時，相同的明文對應相同的：密鑰相同時，相同的明文對應相同的 密文。密文。252627最常用，出現頻率在百分之一以上的有14個音節，它們是：de shi yi bu you zhi le ji zhe wo yen li ta dao的是 一 不有之 了機 這我們 里 他 到次常用音節有33個，它們是：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從三億漢字的母體材料中，抽樣二千五百萬字進行雙音節詞詞頻統計，結果是：頻率在一萬次以上的雙音節詞有33個：我們三萬次以上可以 他們 二萬次以上進行 沒有 工作 人民 生產 這個 發展 就是 問題 國家 中國 這樣 革命 自己 不能 由于 這些 所以 因此 作用 一般 什么 如果 情況 必須 方法 因為 主要 要求 社會29多表古典密碼的統計分析多表古典密碼的統計分析步驟步驟1：首先確定密鑰的長度：利用：首先

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

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

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