古典密碼體制

1、1第第2章章 古典密碼體制古典密碼體制22.1 替代密碼替代密碼 替代密碼又可分為替代密碼又可分為單一字母替代密碼單一字母替代密碼和和多字母替代密碼多字母替代密碼。 替代密碼可以用字母來替代字母，也可以用圖形符號來替替代密碼可以用字母來替代字母，也可以用圖形符號來替代字母，或者用字母來替代圖形符號。每個符號都用其他符號代字母，或者用字母來替代圖形符號。每個符號都用其他符號替換，并且替換，并且替換始終不變的密碼被稱為單一字母替代密碼替換始終不變的密碼被稱為單一字母替代密碼。 一般的單一字母替代密碼以一般的單一字母替代密碼以26個英文字母的集合上的一個個英文字母的集合上的一個代換代換 為密鑰對明文

2、消息中的每個字母依次進行變換，如為密鑰對明文消息中的每個字母依次進行變換，如K= : Z26Z26| 是代換是代換，變換的方法是把明文中的每個字母用它，變換的方法是把明文中的每個字母用它在在 下的像去替換。解密時用下的像去替換。解密時用 的逆代換的逆代換 -1進行替換。進行替換。2.1.1 單一字母替代密碼單一字母替代密碼3【例例2-1】設(shè)代換設(shè)代換 的對應(yīng)關(guān)系如下：的對應(yīng)關(guān)系如下：a b c d e f g h i j k l m n o p q r s t u v w x y zi d m e f z o a p h x b s c q r l t u y j v n w g k從代換從代

3、換 的對應(yīng)關(guān)系可知的對應(yīng)關(guān)系可知su，ef，yg因此以代換因此以代換 為密鑰對為密鑰對security加密得到密文加密得到密文ufmjtpyg4棋盤密碼棋盤密碼abcdefghijklmnopqrstuvwxyz12345123455 1. Caesar1. Caesar密碼密碼 Caesar Caesar密碼是由密碼是由Julins CaesarJulins Caesar發(fā)明的，它非常簡單，發(fā)明的，它非常簡單，就是對字母表中的每個字母，用它之后的第就是對字母表中的每個字母，用它之后的第3 3個字母來代換個字母來代換成密文，這里的密鑰成密文，這里的密鑰k k=3=3。如果密鑰空間。如果密鑰空間

4、K K=0,1,2,25=0,1,2,25，即即k kZZ2626，就成為移位密碼，就成為移位密碼，CaesarCaesar密碼是移位密碼的一個密碼是移位密碼的一個特例。特例。移位密碼的加密和解密算法如下：移位密碼的加密和解密算法如下：加密算法加密算法E Ek k ( (m m) ) m m + + k k(mod26)(mod26)解密算法解密算法D Dk k( (c c) ) c c - - k k (mod26) (mod26)6 【例例2-22-2】設(shè)明文為：設(shè)明文為：securitysecurity，試用，試用CaesarCaesar密碼對其進密碼對其進行加密，然后再進行解密。行加密

5、，然后再進行解密。(1)(1)加密過程加密過程如字母如字母s s對應(yīng)的數(shù)字為對應(yīng)的數(shù)字為1818，將，將1818使用加密算法進行加密使用加密算法進行加密E E3 3(18) 18+ 3 (mod26) 21(18) 18+ 3 (mod26) 21數(shù)字?jǐn)?shù)字2121對應(yīng)的字母為對應(yīng)的字母為v v，所以，所以securitysecurity的密文為的密文為vhfxulwbvhfxulwb(2) (2) 解密過程解密過程D D3 3(21) 21- 3 (mod26) 18(21) 21- 3 (mod26) 187CAP will encipher/decipher using a simple

6、shift systemEnter the plaintextSelect Simple Shift under the Ciphers MenuEnter shift valueSelect EncipherThis is a sampleymnxnxfxfruqj 8 2. 2. 仿射密碼仿射密碼仿射密碼就是將加法密碼和乘法密碼組合而成的一種密碼。仿射密碼就是將加法密碼和乘法密碼組合而成的一種密碼。它的密鑰空間為它的密鑰空間為K K=(=(k k1 1, , k k2 2)|)| k k1 1, , k k2 2 Z Z2626 加密算法加密算法c ck k1 1m m+ +k k2 2(

7、mod26)(mod26)解密算法解密算法m m(c c- -k2) ) k k1 1-1-1(mod26)(mod26)其中：其中：k k1 1k1-11 (mod26)1 (mod26)9 【例例2-32-3】假設(shè)假設(shè)k k1 1 9,9, k k2 2 2 2，明文字母為，明文字母為w w，用仿射密碼，用仿射密碼對其加密和解密。對其加密和解密。加密時，先把明文字母加密時，先把明文字母w w轉(zhuǎn)換為數(shù)字轉(zhuǎn)換為數(shù)字2222，由加密算法得，由加密算法得c c k k1 1m m+ +k k2 2(mod26) (mod26) (9(922222) (mod26) 2) (mod26) 1818再

8、把數(shù)字再把數(shù)字1818轉(zhuǎn)換為字母得到密文轉(zhuǎn)換為字母得到密文s s。解密時，先計算解密時，先計算k k1 1-1-1。有。有9 931(mod26)31(mod26)可以得出可以得出k k1 1-1-13(mod26)3(mod26)。再由解密算法得再由解密算法得m m ( (c c- -k k2 2) ) k k1 1-1-1(mod26) (mod26) (18-2) (18-2) 3 (mod26) 3 (mod26) 22 22數(shù)字?jǐn)?shù)字2222對應(yīng)的明文字母為對應(yīng)的明文字母為w w。10補充例子補充例子 加密：加密： “China”“China”經(jīng)仿射加密變換成經(jīng)仿射加密變換成“RAHQ

9、D” RAHQD” DQHAR316701726mod39459521733333013872711解密：解密： 原始消息原始消息“China”China”得到恢復(fù)得到恢復(fù) ANIHC01387226mod262218619236191919191931670171512 3.3.PlayfairPlayfair密碼密碼 Playfair Playfair密碼密碼基于一個基于一個5 55 5的字母矩陣的字母矩陣。字母矩陣構(gòu)。字母矩陣構(gòu)造方法：造方法： 選用一個英文短語或單詞串作為密鑰，去掉其中重復(fù)選用一個英文短語或單詞串作為密鑰，去掉其中重復(fù)的字母得到一個無重復(fù)字母的字符串，然后再將字母表中的

10、字母得到一個無重復(fù)字母的字符串，然后再將字母表中剩下的字母依次從左到右、從上往下填入矩陣中，字母剩下的字母依次從左到右、從上往下填入矩陣中，字母i i，j j占同一個位置。占同一個位置?！纠?-42-4】設(shè)密鑰設(shè)密鑰K K= information security= information security，去除重復(fù)字，去除重復(fù)字母后母后K K=informatsecuy=informatsecuy13 i/jnformatsecuybdghklpqvwxz圖圖2-1 Playfair2-1 Playfair密碼字母矩陣示例密碼字母矩陣示例14 對每一明文字母對對每一明文字母對m m1 1

11、、m m2 2的加密方法如下：的加密方法如下： m m1 1和和m m2 2在同一行，則密文在同一行，則密文c c1 1和和c c2 2分別緊靠分別緊靠m m1 1、m m2 2右端的字右端的字母，其中第一列看做是最后一列的右方。母，其中第一列看做是最后一列的右方。 若若m m1 1和和m2在同一列，則密文在同一列，則密文c c1 1和和c c2 2分別緊靠分別緊靠m m1 1、m m2 2下方的下方的字母，其中第一行看做是最后一行的下方。字母，其中第一行看做是最后一行的下方。 若若m m1 1和和m m2 2不在同一行，也不在同一列，則密文不在同一行，也不在同一列，則密文c c1 1和和c

12、c2 2是由是由m m1 1、m m2 2確定的矩形的其他兩角的字母，并且確定的矩形的其他兩角的字母，并且c c1 1和和m m1 1 ，c c2 2和和m m2 2同行。同行。 若若m m1 1m m2 2，則插入空字母于重復(fù)字母之間。，則插入空字母于重復(fù)字母之間。 明文字母數(shù)為奇數(shù)，將空字母加在明文的末端。明文字母數(shù)為奇數(shù)，將空字母加在明文的末端。15Rule OneUsing the keyword array formed from “software” TFOSWBERACIHGDKPNMLQYXVUZQERLEBLM16Rule TwoAgain using the keyword

13、 array formed from “software”TFOSWBERACIHGDKPNMLQYXVUZALTUDYBT17Rule ThreeUsing the keyword array formed from “software”TFOSWBERACIHGDKPNMLQYXVUZPOTM18 【例例2-52-5】用圖用圖2-12-1所示的所示的PlayfairPlayfair密碼字母矩陣加密明文密碼字母矩陣加密明文computercomputer。先將先將computercomputer中的字母兩兩分組為中的字母兩兩分組為co mp ut erco mp ut er再按照再按照Pla

14、yfairPlayfair密碼的加密規(guī)則，得到的密文為密碼的加密規(guī)則，得到的密文為bi eg ya debi eg ya de19 多字母替代密碼在加解密時，所使用的多字母替代密碼在加解密時，所使用的密鑰是是明文密鑰是是明文字母到密文字母的多個映射字母到密文字母的多個映射，每個映射又是一對一的簡單，每個映射又是一對一的簡單替換。替換。 多表替代密碼將明文字母劃分為長度相同的消息單元多表替代密碼將明文字母劃分為長度相同的消息單元，稱為，稱為明文分組明文分組，對明文成組地進行替代，同一個字母有，對明文成組地進行替代，同一個字母有不同的密文，不同的密文， 2.1.2 多字母替代密碼多字母替代密碼20

15、 1. Vigenere1. Vigenere密碼密碼 該密碼體制有一個參數(shù)該密碼體制有一個參數(shù)n n。在加解密時，把英文字母映射。在加解密時，把英文字母映射為為0 02525的數(shù)字再進行運算，并按的數(shù)字再進行運算，并按n n個字母一組進行變換。明文個字母一組進行變換。明文空間、密文空間及密鑰空間都是長度為空間、密文空間及密鑰空間都是長度為n n的英文字母串的集合。的英文字母串的集合。設(shè)密鑰設(shè)密鑰 k=(k1,k2,kn)，明文，明文m=(m1,m2,mn)，則，則加密算法為加密算法為Ek(m)=(c1,c2,cn)其中：其中：ci (mi + ki)(mod26)，i =1,2,n對密文對密

16、文 c=(c1,c2,cn)，解密算法為解密算法為Dk(c)= (m1,m2,mn)其中：其中：mi(ci - ki)(mod26)，i =1,2,n21 【例例2-62-6】設(shè)密鑰設(shè)密鑰KEYSKEYS，明文消息為，明文消息為GOODCRYPTOSYSTEMGOODCRYPTOSYSTEM，試用，試用VigenereVigenere密碼對其進行加密，然后再進行解密。密碼對其進行加密，然后再進行解密。 由密鑰由密鑰KEYSKEYS，得，得n n = 4= 4，密鑰對應(yīng)的數(shù)字序列為，密鑰對應(yīng)的數(shù)字序列為 (10,4,24,18)(10,4,24,18)。然后將明文按每。然后將明文按每4 4個字母

17、進行分組，并轉(zhuǎn)換這個字母進行分組，并轉(zhuǎn)換這些明文字母為相應(yīng)的數(shù)字，再用模些明文字母為相應(yīng)的數(shù)字，再用模2626加上對應(yīng)密鑰數(shù)字，其加加上對應(yīng)密鑰數(shù)字，其加密過程如表密過程如表2-22-2所示。所示。得到的密文為：得到的密文為：qsmvmvwhdsqqcxceqsmvmvwhdsqqcxce。22明明文文GOODCRYPTOSYSTE M614 143217 24 15 19 14 18 24 18 194 12密密鑰鑰KEYSKEYSKEYSKEYS10424 18 10424 18 10424 18 10424 18密密文文16 18 12 21 12 21 227318 16 162232

18、4qsmvmvwhdsqqcxce表表2-2 Vigenere2-2 Vigenere密碼加密示例密碼加密示例23Vigenere Cipher TableThe table lists the keycharacters ontop and theplaintextcharacters onthe side a b c d e f g h i j k l m n o p q r s t u v w x y za a b c d e f g h i j k l m n o p q r s t u v w x y zb b c d e f g h i j k l m n o p q r s t

19、u v w x y z ac c d e f g h i j k l m n o p q r s t u v w x y z a bd d e f g h i j k l m n o p q r s t u v w x y z a b ce e f g h i j k l m n o p q r s t u v w x y z a b c df f g h i j k l m n o p q r s t u v w x y z a b c d e g g h i j k l m n o p q r s t u v w x y z a b c d e f h h i j k l m n o p

20、q r s t u v w x y z a b c d e f g i i j k l m n o p q r s t u v w x y z a b c d e f g h j j k l m n o p q r s t u v w x y z a b c d e f g h i k k l m n o p q r s t u v w x y z a b c d e f g h i j l l m n o p q r s t u v w x y z a b c d e f g h i j k m m n o p q r s t u v w x y z a b c d e f g h i j

21、k l n n o p q r s t u v w x y z a b c d e f g h i j k l m o o p q r s t u v w x y z a b c d e f g h i j k l m n p p q r s t u v w x y z a b c d e f g h i j k l m n o q q r s t u v w x y z a b c d e f g h i j k l m n o p r r s t u v w x y z a b c d e f g h i j k l m n o p q s s t u v w x y z a b c d

22、e f g h i j k l m n o p q r t t u v w x y z a b c d e f g h i j k l m n o p q r s u u v w x y z a b c d e f g h i j k l m n o p q r s t v v w x y z a b c d e f g h i j k l m n o p q r s t u w w x y z a b c d e f g h i j k l m n o p q r s t u v x x y z a b c d e f g h i j k l m n o p q r s t u v w y

23、y z a b c d e f g h i j k l m n o p q r s t u v w x z z a b c d e f g h i j k l m n o p q r s t u v w x y 24OperationA keyword is selected and it is repeatedly written above the plaintextEXAMPLE: using the keyword “hold”HOLDHOLDHOLDHOLDHOI STHELPIATNXETSTHI a b c d e f g h i . . .a a b c d e f g h i

24、b b c d e f g h i j . . .n c d e f g h i j k . . .d d e f g h i j k l . . .e e f g h i j k l m . . .f f g h i j k l m n . . .g g h i j k l m n o . . .h h i j k l m n o p . . .i i j k l m n o p q . . .j j k l m n o p q r . . . k k l m n o p q r s . . .l l m n o p q r s t . . .m m n o p q r s t u . .

25、.n n o p q r s t u v . . .o o p q r s t u v w . . .p p q r s t u v w x . . .q q r s t u v w x y . . .r r s t u v w x y z . . .s s t u v w x y z a . . .t t u v w x y z a b . . .u u v w x y z a b c . . .AVTVHKEGQHEBQDWDLE252. Hill2. Hill密碼密碼 Hill Hill密碼算法的基本思想是將明文字母通過線性變換，將密碼算法的基本思想是將明文字母通過線性變換，將它們轉(zhuǎn)換為

26、個數(shù)相同的密文字母。它們轉(zhuǎn)換為個數(shù)相同的密文字母。 給定一個具有給定一個具有m m個字母的明文，選定一個個字母的明文，選定一個n n值，值，n n m m，將密鑰，將密鑰K K構(gòu)造為一個構(gòu)造為一個n nn n的矩陣。將的矩陣。將m m個字母的明文劃分為個字母的明文劃分為n n個字母的個字母的多個組，多個組，n n個字母轉(zhuǎn)換為整數(shù)列向量個字母轉(zhuǎn)換為整數(shù)列向量M M，通過矩陣乘法，通過矩陣乘法C CK KM Mmodmodp p得到向量得到向量C C，隨后將向量，隨后將向量C C中的整數(shù)轉(zhuǎn)換為密文。中的整數(shù)轉(zhuǎn)換為密文。 Hill Hill密碼使用的密鑰是一個密碼使用的密鑰是一個n nn n的整數(shù)矩

27、陣，的整數(shù)矩陣，加密算法加密算法是是C CK KM Mmod mod p p，解密時只需做一次逆變換即可。，解密時只需做一次逆變換即可。 26 【例例2-72-7】設(shè)明文消息為設(shè)明文消息為seedseed，試用，試用n n2 2，密鑰為，密鑰為的的HillHill密碼對其進行加密，然后再進行解密。密碼對其進行加密，然后再進行解密。加密過程如下：加密過程如下：執(zhí)行矩陣運算執(zhí)行矩陣運算MK-1Cmod p可以完成解密操作，本例中可以完成解密操作，本例中K K的的逆矩陣解密過程如下：逆矩陣解密過程如下：52109K231426mod34,42026mod41852109K3426mod2314,41

28、826mod42017210211K27 HillHill密碼的安全性密碼的安全性在于：在于： 可以較好地抑制自然語言的統(tǒng)計特性，不再有單字母替換的可以較好地抑制自然語言的統(tǒng)計特性，不再有單字母替換的一一對應(yīng)關(guān)系，對抗一一對應(yīng)關(guān)系，對抗“唯密文攻擊唯密文攻擊”有較高安全強度。有較高安全強度。密鑰空間較大，在忽略密鑰矩陣密鑰空間較大，在忽略密鑰矩陣K K可逆限制條件下，可逆限制條件下，| |K K| = | = 2626n nn n。HillHill密碼的脆弱性密碼的脆弱性在于：在于： 若提供的矩陣若提供的矩陣M M是可逆的，則能計算出是可逆的，則能計算出K KM-1Cmod p,從而從而破譯該

29、密碼體制。破譯該密碼體制。 若方陣若方陣M M關(guān)于模關(guān)于模2626不可逆，攻擊者可通過嘗試其它明文不可逆，攻擊者可通過嘗試其它明文/ /密文密文對來產(chǎn)生新的方陣對來產(chǎn)生新的方陣M M ，直到找到一個可逆的明文矩陣，直到找到一個可逆的明文矩陣M M就可破就可破譯譯HillHill密碼。密碼。283. 3. 一次一密密碼一次一密密碼 若多字母替代密碼的密鑰是一個隨機且不重復(fù)的字符序列，若多字母替代密碼的密鑰是一個隨機且不重復(fù)的字符序列，這種密碼則稱為一次一密密碼，因為它的密鑰只使用一次。該這種密碼則稱為一次一密密碼，因為它的密鑰只使用一次。該密碼體制是美國電話電報公司的密碼體制是美國電話電報公司的

30、Joseph MauborgneJoseph Mauborgne在在19171917年為年為電報通信設(shè)計的一種密碼，又稱為電報通信設(shè)計的一種密碼，又稱為VernamVernam密碼。密碼。 設(shè)設(shè)m=(m1 m2 m3 mi )為明文，為明文，k=(k1 k2 k3 ki )為密鑰，為密鑰，其中：其中：mi,ki(0,1), i1,則加密變換為：則加密變換為：c=(c1 c2 c3 ci)，其中，其中ci mi ki , i 1。解密變換為：解密變換為：m=(m1 m2 m3 mi)，其中，其中mi ci ki , i 1。29 【例例2-82-8】設(shè)明文消息是設(shè)明文消息是10111001101

31、11001，密鑰（隨機序列中的一段），密鑰（隨機序列中的一段）是是0010101100101011，那么加密過程如下：，那么加密過程如下： 10111001 10111001（明文）（明文） 0010101100101011（密鑰）（密鑰） = 10010010 = 10010010（密文）（密文） 實際上一次一密體制屬于流密碼，加密解密方法都使用異實際上一次一密體制屬于流密碼，加密解密方法都使用異或，這使軟硬件實現(xiàn)都非常簡單。雖然這種密碼體制或，這使軟硬件實現(xiàn)都非常簡單。雖然這種密碼體制理論上是理論上是不可破譯的不可破譯的，然而在實際應(yīng)用中，一般情況下，選擇一個短的，然而在實際應(yīng)用中，一般情

32、況下，選擇一個短的隨機輸入產(chǎn)生隨機輸入產(chǎn)生一個偽隨機序列作為密鑰序列一個偽隨機序列作為密鑰序列，稱為，稱為“近似近似”的的一次一密亂碼本。一次一密亂碼本。30 例：設(shè)明文消息是：例：設(shè)明文消息是：datasecurity,取自亂碼本取自亂碼本的密鑰序列是：的密鑰序列是：tbfqlpdzsdye,求密文。求密文。 加密時要依次對加密時要依次對datasecurity中的各字母移位中的各字母移位19、1、5、16、11、15、3、25、18、3、24、4 得到的密文為得到的密文為wbyqdtftjlrc31 在替代密碼中，明文中的每個字母都被替換成另外的字母。在替代密碼中，明文中的每個字母都被替換

33、成另外的字母。置換密碼只改變明文消息各元素的相對位置置換密碼只改變明文消息各元素的相對位置，而明文消息元素，而明文消息元素本身的取值或內(nèi)容形式不變。置換密碼又稱為換位密碼。本身的取值或內(nèi)容形式不變。置換密碼又稱為換位密碼。2.2 置換密碼置換密碼2.2.1 列置換密碼列置換密碼 列置換密碼的加密方法就是將明文按行填寫到一個列寬列置換密碼的加密方法就是將明文按行填寫到一個列寬固定（設(shè)為固定（設(shè)為n n）的表格或長方形中；然后按（）的表格或長方形中；然后按（1 1，2 2，n n）的一個的一個置換置換 交換列的位置次序交換列的位置次序，再按列讀出即得密文。，再按列讀出即得密文。 解密時，將密文按列

34、填寫到一個行數(shù)固定（也為解密時，將密文按列填寫到一個行數(shù)固定（也為n n）的）的表格或長方形中，按置換表格或長方形中，按置換 的逆置換交換列的位置次序，然后的逆置換交換列的位置次序，然后按行讀出即得到明文。按行讀出即得到明文。置換置換 可看成是算法的密鑰。可看成是算法的密鑰。32 【例例2-92-9】設(shè)明文設(shè)明文Alice is a murdererAlice is a murderer，列寬，列寬n n=4=4，密鑰，密鑰 是按是按3 3，4 4，2 2，1 1列的次序讀出得到密文，試寫出加解密的過程列的次序讀出得到密文，試寫出加解密的過程和結(jié)果。和結(jié)果。 明文為明文為Alice is a

35、murdererAlice is a murderer，加密過程中，將明文按，加密過程中，將明文按4 4個個字母一行寫出：字母一行寫出：1 2 3 41 2 3 4a l i ca l i ce i s ae i s am u r dm u r de r e re r e r按列按列3 3，4 4，2 2，1 1寫出密文：寫出密文：isrecadrliuraemeisrecadrliuraeme。 解密過程：將密文解密過程：將密文isrecadrliuraemeisrecadrliuraeme按按4 4個字母一列寫出，個字母一列寫出，按列按列4 4，3 3，1 1，2 2一行一行的書寫，得出明

36、文為：一行一行的書寫，得出明文為：alice is a alice is a murderermurderer。33 柱狀列置換密碼柱狀列置換密碼 柱狀列置換密碼沒有直接指定置換柱狀列置換密碼沒有直接指定置換 ，而是先選取一個密鑰，而是先選取一個密鑰短語，再生成一個數(shù)字序列，根據(jù)數(shù)字序列來交換列，重排字短語，再生成一個數(shù)字序列，根據(jù)數(shù)字序列來交換列，重排字母得到密文。母得到密文。 如密鑰短語為如密鑰短語為“good cryptosystem”good cryptosystem”，選的密鑰為，選的密鑰為“goodcryp”goodcryp”。對所有字母編號的結(jié)果是：。對所有字母編號的結(jié)果是：g

37、o o d c r y pg o o d c r y p3 4 5 2 1 7 8 63 4 5 2 1 7 8 634 【例例2-102-10】 已知明文消息為已知明文消息為This should be encrypted This should be encrypted with cautionwith caution，試用密鑰為，試用密鑰為goodcrypgoodcryp的柱狀列置換密碼對其進的柱狀列置換密碼對其進行加密。行加密。 密鑰密鑰“goodcryp”goodcryp”指定了一個數(shù)字序列指定了一個數(shù)字序列“3 3，4 4，5 5，2 2，1 1，7 7，8 8，6”6”，將明文被

38、排列成一個具有，將明文被排列成一個具有8 8列和列和4 4行的長方形。行的長方形。g o o d c r y pg o o d c r y p3 4 5 2 1 7 8 63 4 5 2 1 7 8 6t h i s s h o ut h i s s h o ul d b e e n c rl d b e e n c ry p t e d w i ty p t e d w i th c a u t i o nh c a u t i o n 將每一列根據(jù)列號由小到大進行排序，逐列讀取將每一列根據(jù)列號由小到大進行排序，逐列讀取4 4個字母為個字母為一組，生成的密文為：一組，生成的密文為：sedt

39、seeu tlyh hdpc ibta urtn hnwi ociosedt seeu tlyh hdpc ibta urtn hnwi ocio。35 周期置換密碼是將明文字符按一定長度周期置換密碼是將明文字符按一定長度n n分組，把每組中的分組，把每組中的字符按字符按1,2,1,2,n n的一個置換的一個置換 重排位置次序來得到密文的一種重排位置次序來得到密文的一種加密方法。其中的加密方法。其中的密鑰就是置換密鑰就是置換 ，在，在 的描述中包含了分組長的描述中包含了分組長度的信息。度的信息。2.2.2 周期置換密碼周期置換密碼 解密時，對密文字符按長度解密時，對密文字符按長度n n分組，并

40、按分組，并按 的逆置換的逆置換把每組把每組字符重排位置次序來得到明文。字符重排位置次序來得到明文。36 【例例2-112-11】給定明文為給定明文為cryptographycryptography，試用密鑰，試用密鑰的置換密碼對其進行加密，然后再對密文進行解密。的置換密碼對其進行加密，然后再對密文進行解密。 明文分組為：明文分組為：cryp togr aphycryp togr aphy，再利用置換密鑰，再利用置換密鑰進行進行加密變換，得：加密變換，得：E (cryp) = (yprc)(cryp) = (yprc)；E (togr) = (grot)(togr) = (grot)；E (ap

41、hy) = (hypa)(aphy) = (hypa)即密文消息是：即密文消息是：yprcgrothypayprcgrothypa。 解密時，先由加密變換可求出逆置換，解密時，先由加密變換可求出逆置換， 對每組字母用逆置換對每組字母用逆置換 進行重排進行重排 , ,解密得到明文：解密得到明文：cryptography cryptography 32412134432142311137 在對密碼體制進行破譯時，一般假設(shè)攻擊者已知道通信雙方在對密碼體制進行破譯時，一般假設(shè)攻擊者已知道通信雙方使用的密碼算法，這就是使用的密碼算法，這就是KerckhoffsKerckhoffs假設(shè)，密碼破譯的重點在假

42、設(shè)，密碼破譯的重點在于如何獲取加密過程中所使用的密鑰。于如何獲取加密過程中所使用的密鑰。2.3 古典密碼的破譯古典密碼的破譯 通過對大量英文語言的研究可以發(fā)現(xiàn)，每個字母出現(xiàn)的頻通過對大量英文語言的研究可以發(fā)現(xiàn)，每個字母出現(xiàn)的頻率不一樣，率不一樣，e e出現(xiàn)的頻率最高出現(xiàn)的頻率最高。如果所統(tǒng)計的文獻足夠長，便。如果所統(tǒng)計的文獻足夠長，便可發(fā)現(xiàn)各字母出現(xiàn)的頻率比較穩(wěn)定?？砂l(fā)現(xiàn)各字母出現(xiàn)的頻率比較穩(wěn)定。 如表如表2-52-5所示所示 . .2.3.1 單一字母替代密碼的破譯38abcdef0.08560.01390.02790.03780.13040.0289ghijkl0.01990.05180.

43、06270.00130.00420.0339mnopqr0.02490.07070.07970.01990.00120.0677stuvwx0.06070.10450.02490.00920.01490.0017yz0.01990.0008表表2-5 2-5 英文字母出現(xiàn)頻率統(tǒng)計表英文字母出現(xiàn)頻率統(tǒng)計表39 單一字母替代密碼的破譯中，除了考慮單字母統(tǒng)計特單一字母替代密碼的破譯中，除了考慮單字母統(tǒng)計特性外，掌握雙字母、三字母的統(tǒng)計特性以及字母之間的連性外，掌握雙字母、三字母的統(tǒng)計特性以及字母之間的連綴關(guān)系等信息也是很有用的，如綴關(guān)系等信息也是很有用的，如出現(xiàn)頻率較高的雙字母組出現(xiàn)頻率較高的雙字母

44、組合有合有ththheheininereranan等，英語中等，英語中最常用的最常用的三字母組合三字母組合是是the, ingthe, ing等，特別地，等，特別地，thethe出現(xiàn)的頻率幾乎出現(xiàn)的頻率幾乎是是inging的的3 3倍。此外，統(tǒng)計資料還表明：英文單詞以倍。此外，統(tǒng)計資料還表明：英文單詞以e e，s s，d d，t t字母結(jié)尾的超過一半。英文單詞以字母結(jié)尾的超過一半。英文單詞以t t，a a，s s，w w為起始為起始字母的約占一半。字母的約占一半。40【例例2-12】設(shè)某一段明文經(jīng)移位密碼加密后的密文如下：設(shè)某一段明文經(jīng)移位密碼加密后的密文如下：rjjy rjzs ijwy m

45、jtq najy wjjs jcyb jjpj sibj bnqq inxh zxym juqf s試破譯該密文。為了表述更加清楚，本例的密文用小寫字試破譯該密文。為了表述更加清楚，本例的密文用小寫字母，明文用大寫字母。母，明文用大寫字母。首先統(tǒng)計密文中各個字母的出現(xiàn)次數(shù)，如表首先統(tǒng)計密文中各個字母的出現(xiàn)次數(shù)，如表2-7所示。所示。 從表從表2-72-7可以看出，密文字母可以看出，密文字母j j出現(xiàn)的次數(shù)為出現(xiàn)的次數(shù)為1414，猜測，猜測j j對對應(yīng)的明文字母可能為應(yīng)的明文字母可能為E E。y y出現(xiàn)的次數(shù)為出現(xiàn)的次數(shù)為5 5，猜測，猜測y y它對應(yīng)的明文它對應(yīng)的明文字母可能為字母可能為T T

46、。j j和和E E之間的距離為之間的距離為5 5，y y和和T T之間的距離也為之間的距離也為5 5。41字母字母a b c d e f g h i j k l m n o p q r s t u v w x y z次數(shù)次數(shù)1 3 1 0 0 1 0 1 3 14 0 0 2 3 0 1 4 2 4 1 1 0 2 2 5 2表表2-7 2-7 各個密文字母的出現(xiàn)次數(shù)各個密文字母的出現(xiàn)次數(shù) 將移位密碼中的密鑰將移位密碼中的密鑰k k定為定為5 5，使用解密算法：，使用解密算法：D5( (c c) = ) = c c - 5(mod26) - 5(mod26)， 將每個密文字母還原為明文，如，密

47、文將每個密文字母還原為明文，如，密文r r的明文為的明文為M M。最終得到完整的明文為：最終得到完整的明文為：MEET ME UNDER THE OLIVE TREE NEXT WEEKEND, WE WILL MEET ME UNDER THE OLIVE TREE NEXT WEEKEND, WE WILL DISCUSS THE PLAN.DISCUSS THE PLAN.42例如，明文如下所示：例如，明文如下所示：TO ALL UNITS. TODAYS WEATHER OVERCAST, TO ALL UNITS. TODAYS WEATHER OVERCAST, FREEZING,

48、WIND GUSTING. CHANCE OF NIGHT FOG.FREEZING,WIND GUSTING. CHANCE OF NIGHT FOG.假定加密使用假定加密使用8 8個字母的密鑰個字母的密鑰”TOASTING”,”TOASTING”,將明文置入一個將明文置入一個列數(shù)為列數(shù)為8 8的長方形，然后根據(jù)密鑰逐列讀取這些字母。在最的長方形，然后根據(jù)密鑰逐列讀取這些字母。在最后添加四個字母后添加四個字母“X X”, ,使消息的總長度能夠被使消息的總長度能夠被5 5整除。整除。2.3.2 柱狀列置換密碼的破譯柱狀列置換密碼的破譯43T O A S T I N G7 5 1 6 8 3 4 2T O A L L U N IT O A L L U N IT S T O D A Y ST S T O D A Y SW E A T H E R OW E A T H E R OV E R C A S T F V E R C A S T F R E E Z I N G WR E E Z I N G WI N D G U