5保障與安全密碼學06

1、第三章 密碼學（2） 傳統(tǒng)密碼技術 一、 數據表示方法數據的表示有多種形式，使用最多的是文字，還有圖形、聲音、圖像等。這些信息在計算機系統(tǒng)中都是以某種編碼的方式來存儲的。 傳統(tǒng)加密方法的主要應用對象是對文字信息進行加密解密。 古典加密技術兩個基本組成部分：代替與變換 二、 代替密碼代替密碼（Substitution Cipher）在代替密碼中,用一組密文字母來代替一組明文字母以隱藏明文,但保持明文字母的位置不變。 傳統(tǒng)密碼技術代替密碼就是將明文字母表P中的每個字母用密文字母表C中的相應字母來代替這一類密碼，包括移位密碼、替換密碼、仿射密碼、乘數密碼、多項式代替密碼、密鑰短語密碼等。接收者對密文

2、進行逆替換就恢復出明文來。在經典密碼學中，有四種類型的代替密碼。簡單代替密碼（Simple Substitution Cipher) Caesar 多名碼代替密碼 多字母代替密碼 多表代替密碼Vigenre 。傳統(tǒng)密碼技術1單表代替密碼 單表代替密碼的一種典型方法是凱撒（Caesar）密碼，又叫循環(huán)移位密碼。它的加密方法就是把明文中所有字母都用它右邊的第k個字母代替，并認為Z后邊又是A。這種映射關系表示為如下函數：F(a)=(a+k) mod n其中：a表示明文字母；n為字符集中字母個數；k為密鑰。 傳統(tǒng)密碼技術映射表中，明文字母中在字母表中的相應位置數為如A=0，B=1，具體形式如下：設k3

3、；對于明文PCOMPUTE SYSTEMS則f（C）=（2+3） mod 26=5=Ff（O）=（14+3）mod 26=17=Rf（M）=（12+3）mod 26=15=Pf（S）=（18+3） mod 26=21=V所以，密文C= Ek（P）=FRPSXRWHUVBVWHPV。 愷撒密碼的特點單字母密碼（簡單替換技術）簡單，便于記憶令26個字母分別對應于025，a=0，b=1y=24，z=25。缺點：結構過于簡單，密碼分析員只使用很少的信息就可預言加密的整個結構。已知加密與解密算法C=E(p)=(p+k)mod(26)p=D(C)=(C-k)mod(26)25個可能的密鑰k,適用Brute

4、-Force Cryptanalysis明文所用的語言是已知的，且其意義易于識別 Caesar CipherCaesar 密碼的數學表示 設：A the value 0, B 1, C 2, . Y 24, Z 25; 加密算法：Ek: i - i + k (mod 26) 解密算法： Dk: i - i - k (mod 26) 例1: plain: meet me after the toga partycipher: PHHW PH DIWHU WKH WRJD SDUWB1oggv og chvgt vjg vqic rctva2nffu nf bgufs uif uphb qbsuz

5、3meet me after the toga party4ldds ld zesdq sgd snfz ozqsx56789qiix qi ejxiv xli xske tevxcBrute-force cryptanalysis is easily performed:simply try all the 25possible keys.作業(yè)1：用C編制上述程序2多表代替密碼 多表代替密碼使用從明文字母到密文字母的多個映射來隱藏單字母出現的頻率分布，每個映射是簡單代替密碼中的一對一映射。維吉尼亞Vigenere 密碼和博福特Beaufort 密碼均是多表代替密碼的例子。多表代替密碼有多個單

6、字母密鑰，每一個密鑰被用來加密一個明文字母。第一個密鑰加密明文的第一個字母，第二個密鑰加密明文的第二個字母等，所有密鑰使用完后密鑰又再循環(huán)使用。密鑰k可以通過周期性地延長反復進行以至無窮。Vigenere Cipher Table 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 u v w x y z ac c d e f g h i j k l m n o

7、 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 q r s t u v w x y z a b c d e f g i i j

8、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 k l n n o p q r s t u v w x y z a b c d

9、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 e f g h i j k l m n o p q r t t u v w x

10、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 y z a b c d e f g h i j k l m n o p q r

11、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 The table lists the keycharacters ontop and theplaintextcharacters onthe side 這種加密的加密表是以字母表移位為基礎把26個英文字母進行循環(huán)移位，排列在一起，形成2626的方陣。該方陣被稱為維吉尼亞表。采用的算法為f（a）=（a+Bi） mod n（i=（1，2，n）即一個明文字母可表示為多個密文字母。：例如：明文為System，密鑰為dog，加密過程如下：明文：S y s t e m密鑰

12、：d o g d o g密文：V my s在這個例子中，每三個字母中的第一、第二、第三個字母分別移動（mod 26）3個，14個和6個位置。第四章 傳統(tǒng)密碼學設密鑰k=k1k2kn，明文M=m1m2mn，加密變換Ek(M)=c1c2cn。其中ci( mi + ki) mod 26，i=1,2n。優(yōu)點：能抵抗簡單的字母頻率分析攻擊。多表密碼加密算法結果將使得對單表置換用的簡單頻率分析方法失效。例 設密鑰k =cipher，明文消息appliedcryptosystem， 試用維吉尼亞密碼對其進行加密，然后再進行解密。解：由密鑰k=cipher，得n=6，密鑰對應的數字序列為 (2，8，15，7，

13、4，17)。然后將明文按每6個字母進行分組，并轉換這些明文字母為相應的數字，再用模26加上對應密鑰數字，其加密過程如下表 解密使用相同的密鑰，但用模26的減法代替模26加法 密鑰為cipher的維吉尼亞密碼加密過程 密文為：cxesmvfkgftkqanzxvo。作業(yè)2：用C編制上述程序 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 u v w x y z

14、 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 q r s t u v

15、 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 k l n n o p

16、 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 e f g h i j

17、 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 y z a b c d

18、 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 OperationA keyword is selected and it is repeatedly written above the plaintextEXAMPLE: using the keyword “hold”HOLDHOLDHOLDHOLDHOKEYplaintextI STHELPIATNXETSTHI a b c d e f g h i . . .a a b c d e f g h ib

19、 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 . . .

20、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 . . .ACiphertextVTVHKEGQHEBQDWDLESelect Vigenere from the Ciphers MenuEnter akeyword傳統(tǒng)密碼技術3多名碼代替密碼（Homoph

21、onic Substitution）：它與簡單代替密碼相似，只是映射是一對多的，每個明文字母可以加密成多個密文字母。 例如， A可能對應于5、13、25 B可能對應于7、9、31、42當對字母的賦值個數與字母出現頻率成比例時，安全性將有所提高。這是因為密文符號的相關分布會近似于平的，可以挫敗頻率分析。1401年Duchy Mantua公司就開始使用多名碼代替密碼，比簡單代替密碼難破譯，但仍不能掩蓋明文語言的所有統(tǒng)計特性，用已知明文攻擊，較容易破解，但用唯密文攻擊要困難一些。第四章 傳統(tǒng)密碼學多字母或多碼代替密碼 不同于前面介紹的代替密碼都是每次加密一個明文字母，多字母代替密碼將明文字符劃分為長

22、度相同的消息單元，稱為明文組，對字符塊成組進行代替，這樣一來使密碼分析更加困難。多字母代替的優(yōu)點是容易將字母的自然頻度隱蔽或均勻化，從而有利于抗擊統(tǒng)計分析。Playfair密碼，Hill密碼都是這一類型的密碼4 多字母代替密碼-Playfair （英國一戰(zhàn)期間曾用）第四章 傳統(tǒng)密碼學密鑰由25個英文字母（J與I相同）組成的5階方陣。 每一對明文字母 m1和m2，都根據下面的6條規(guī)則進行加密。（1）明文字母 m1和m2同行。密文是其右邊字母。（2）明文字母 m1和m2同列。密文是其下邊字母。（3）明文字母 m1和m2不同行、不同列。密文是長方形的另兩個頂點。（4）明文字母 m1和m2相同。在m1

23、和m2之間加一個無效字母。（5）明文有奇數個字母，末尾加一個無效字母。（6）I、J看成是相同字母。4 多字母或多碼代替密碼-Playfair （英國一戰(zhàn)期間曾用）4 多字母代替密碼-Playfair Playfair:將明文中的雙字母組合作為一個單元對待，并將這些單元轉換為密文的雙字母組合。 密鑰是55變換矩陣: I與J視為同一字符C I P H ER A B D FG K L M NO Q S T UV W X Y Z加密規(guī)則:按成對字母加密 相同對中的字母加分隔符(如x) balloon ba lx lo on 同行取右邊: he EC 同列取下邊: dm MT 其他取交叉: kt MQ

24、OD TRPlayfair舉例以前面的55變換矩陣(cipher)為例 C I P H ER A B D FG K L M NO Q S T UV W X Y Z(1)balloon ba lx lo on(2)book bo ok(3)fill fi lx lxdb sp gs ugrs qgae sp spPlayfair密碼分析Playfair有2626=676種字母對組合字符出現幾率一定程度上被均勻化基于字母頻率的攻擊比較困難依然保留了相當的結構信息5 .仿射密碼（affine cipher）體制仿射密碼是代替密碼的一個特例。在仿射密碼中： 加密函數形式為 要求唯一解的充要條件是gcd

25、( a,26)=1 該體制描述為： 設P=C=Z/(26) 對 定義 ek(x)=ax+b (mod 26) 和dk(y)=a-1(y-b)(mod 26) 與26互素的數為1，3，5，7，9，11，15，17，19，21，23，25（12個）因此，模為26的仿射密碼的密鑰空間為1226=312在Z/(26)的情形下，與26互素的數的元的乘法逆為1-1=13-1 =9(39=27=26+1)5-1 =21(521=105=264+1)7-1 =15(715=105=264+1)11-1 =19(1119=209=268+1)17-1 =23(1723=391=2615+1)25-1 =25（6

26、25=2525=2624+1）例子 設k（7，3），注意到7-1(mod 26)=15,加密函數是ek(x)=7x+3,相應的解密函數是dk(y)=15(y-3)=15y-19 , 易見 dk(ek(x)=dk(7x+3)=15(7x+3)-19 =x+45-19 =x (mod 26) 若加密明文：hot ，首先轉換字母h,o,t成為數字7,14,19,然后加密：解密：作業(yè)3:編程實現上述加解密過程。6 Hill密碼（1929）Hill cipher was developed by the mathematician Lester Hill in 1929.基于矩陣的線性變換: K是一個m

27、m矩陣,在Z/(26)上可逆,即存在K-1使得:KK-1 = I (在Z/(26) 對每一個k K,定義ek(x)=xK (mod 26) 和 dk(y)=yK-1 (mod 26)注：明文與密文都是 m元的向量（x1, x2 , xm ); (y1, y2,ym)，定理 設K=(k i,j)為一個定義在zn上的mm矩陣。若K在zn上可逆，則有K-1 = (detK)-1 k*，這里k*為K矩陣的伴隨矩陣。推論 設矩陣為一個定義在zn上的矩陣。Hill密碼的例子-i例子：當 m=2時，明文元素x=(x1,x2),密文元素y=(y1,y2) K= 若對明文july加密，它分成2個元素（j,u),

28、(l,y),分別對應于（9,20）,（11,24）,有（9,20） (mod 26)=(9960,72140）(mod 26)=（3,4） 且（11,24 ） (12172,88168) （11,22）于是對 july加密的結果為DELW。(y1,y2)=(x1,x2)K這是因為 = mod26=Detk=53mod26=11-1=1Hill密碼的例子-ii為了解密，計算 且 因此，得到了正確的明文“july”Hill密碼分析完全隱藏了字符(對)的頻率信息線性變換的安全性很脆弱，易被已知明文攻擊擊破。對于一個m m的hill密碼，假定有m個明文-密文對，明文和密文的長度都是m.可以把明文和密文

29、對記為：Pj=(p1j,p2j,.pmj)和Cj=(C1j,C2j,Cmj), 對任意,1j m 定義m m的方陣X=（Pij) Y=(Cij),得到Y=XK，K=X-1Y例子：friday PQCFKU (5 17)K =(15 16) (8 3)K =(2 5) (0 24)K =(10 20)這個結果可對第三個明文對進行驗證練習假設明文worker利用n=2的Hill密碼加密，得到密文qihryb，求密鑰K。 解：將明文、密文劃分為三組： 明文 （w, o）、（r, k）、（e, r） （22,14）、 (17,10 ) 、 (4,17 ) 密文 （q, i） 、（h, r） 、（y,

30、b） （16, 8）、 (7,17 ) 、 (24,1 )作業(yè)4 通過編程求出密鑰 對Hill密碼的已知明文分析練習假設明文worker利用n=2的Hill密碼加密，得到密文qihryb，求密鑰K。 解： 利用前兩個明文密文對，構造矩陣方程： 計算明文方陣行列式， 由于（18,26）1，即該矩陣沒有逆元，于是考慮第二、第三組明文密文對，得到矩陣方程： 對Hill密碼的已知明文分析 249mod26=15 ，15-1=7顯然，通過對比第一個明文密文對很容易驗證該密鑰。 如果密碼分析者不知道加密分組長度l的值，那么可以通過逐一嘗試不同的l值來得到密鑰。 Hill密碼體制的重要性在于它無可辯駁地表明

31、數學方法在密碼學中的地位是不容置疑的。對Hill密碼的已知明文分析 顯然，通過對比第一個明文密文對很容易驗證該密鑰。 如果密碼分析者不知道加密分組長度l的值，那么可以通過逐一嘗試不同的l值來得到密鑰。 Hill密碼體制的重要性在于它無可辯駁地表明數學方法在密碼學中的地位是不容置疑的。對Hill密碼的已知明文分析Hill ProcessEach character is assigned a numerical value a = 0, b = 1, . . ., z = 25for m = 3 the transformation of p1p2p3 to c1c2c3 is given by

32、 3 equations: c1 = (k11p1 + k12p2 + k13p3) mod 26 c2 = (k21p1 + k22p2 + k23p3) mod 26c3 = (k31p1 + k32p2 + k33p3) mod 26KEYHill MatrixThe Hill cipher is really a matrix multiplication systemThe enciphering key is an n x n matrix, MThe deciphering key is M-1For example, if n = 3 one possible key is:1

33、7 17 521 18 21 2 2 19M = ( ) 4 9 1515 17 624 0 17M-1 = ( )Encrypt n o w 13 14 22 (17 17 521 18 21 2 2 19() = ( ) mod 26 u eFirst, enter the group size which is the same as the matrix size轉輪機 上個世紀20年代，出現了轉輪密碼，而由德國發(fā)明家亞瑟謝爾比烏斯發(fā)明的Enigma 密碼機最為著名。它主要由經電線相連的鍵盤、轉子和顯示器組成，轉子本身也集成了26條線路（在下圖中顯示了6條），

34、把鍵盤的信號對應到顯示器不同的小燈上去。在圖中可以看到，如果按下a鍵，那么燈B就會亮，這意味著a被加密成了B。同樣地我們看到，b被加密成了A，c被加密成了D，d被加密成了F，e被加密成了E，f被加密成了C。于是如果我們在鍵盤上依次鍵入cafe（咖啡），顯示器上就會依次顯示DBCE，這是最簡單的加密方法之一簡單代替密碼。轉輪機轉輪機不僅僅如此，因為當鍵盤上一個鍵被按下時，相應的密文在顯示器上顯示，然后轉子的方向就自動地轉動一個字母的位置（在圖中就是轉動1/6圈，而在實際中轉動1/26圈）。右圖表示了連續(xù)鍵入3個b的情況。轉輪機當第一次鍵入b時，信號通過轉子中的連線，燈A亮起來，放開鍵后，轉子轉動

35、一格，各字母所對應的密碼就改變了；第二次鍵入b時，它所對應的字母就變成了C；同樣地，第三次鍵入b時，燈E閃亮。為使機器更安全，可以把幾種轉輪和移動的齒輪結合起來。因為所有轉輪以不同的速度移動，n個轉輪的機器的周期是26n。為進一步阻止密碼分析，有些轉輪機在每個轉輪上還有不同的位置號。轉輪機德國人為了戰(zhàn)時使用，大大加強了其基本設計，軍用的Enigma由3個轉輪，從5個轉輪中選取。轉輪機中還有一塊稍微改名明文序列的插板，有一個反射器導致每個轉輪對每一個明文字母操作兩次，結構如圖所示。轉輪機 于是轉子自身的初始方向，轉子之間的相互位置，以及連接板連線的狀況就組成了所有可能的密鑰：三個轉子不同的方向組

36、成了26*26*26=17576種不同可能性；三個轉子間不同的相對位置為6種可能性；連接板上兩兩交換6對字母的可能性數目非常巨大，有1種；于是一共有17576*6*1，大約為100000，即一億億種可能性。 但如此復雜的密碼機在第二次世界大戰(zhàn)中被破解了，首先是波蘭人利用德軍電報中前幾個字母的重復出現，破解了早期的Enigma密碼機，而后又將破譯的方法告訴了法國人和英國人。英國人在計算機理論之父圖靈的帶領下，通過尋找德國人在密鑰選擇上的失誤，并成功奪取德軍的部分密碼本，獲得密鑰，以及進行選擇明文攻擊等等手段，破解出相當多非常重要的德軍情報。一次一密亂碼本 如上所述的所有密碼算法均被破解，那么是否

37、存在無法破解的理想加密方案呢？香農證明了一種密碼屬于這種情況，它就是一次一密亂碼本（one-time pad）。一般說來，一次一密亂碼本就是一個大的不重復的真隨機密鑰字母集，發(fā)送者用亂碼本中的每一個密鑰準確地加密一個明文字符，加密是明文字符和密鑰字符進行模26加法。比如：明文：onetimepad密鑰：TBFRGFARFM密文：IPKLPSFHGQ因為：O+Tmod26=I，N+Bmod26=P，E+Fmod26=K，如果竊聽者不能得到用來加密的一次一密亂碼本，這個方案就是完全保密的。給出的密文消息相當于同樣長度的任何可能的明文消息。代替密碼的特點單字母代替密碼（Monoalphabetic Cipher) ：明文中字母的出現頻度、重復字母的模式和字母相互之間的結合模式等統(tǒng)計特性不變，安全性差。多碼代替密碼 ：沒有隱藏明文中不同字母的統(tǒng)計特性 ，但安全性有所提高。多字母代替密碼 ：字符塊被成組加密 ，有利于抗擊統(tǒng)計分析。多表代替密碼 ：有多個映射表，可隱藏單字母出現的頻率分布。傳統(tǒng)