第2講：古典密碼學(xué)

1、古典密碼學(xué)1現(xiàn)代密碼學(xué)現(xiàn)代密碼學(xué)第二講第二講 密碼學(xué)密碼學(xué)(Cryptology)：研究信息系統(tǒng)安全保密的科學(xué)。它包含兩個分支密碼編碼學(xué)密碼編碼學(xué)(Cryptography)(Cryptography)：對信息進(jìn)行編碼實現(xiàn)隱蔽信息的一門學(xué)問：對信息進(jìn)行編碼實現(xiàn)隱蔽信息的一門學(xué)問( (明文明文-密文密文) )密碼分析學(xué)密碼分析學(xué)(Cryptanalytics)(Cryptanalytics)：研究分析破譯密碼的學(xué)問（密文：研究分析破譯密碼的學(xué)問（密文-明文）明文）密碼學(xué)的基本概念(2) 明文明文(消息)(Plaintext) ：被隱蔽消息。 密文密文(Ciphertext)或密報密報(Crypt

2、ogram)：明文經(jīng)密碼變換成的一種隱蔽形式。 加密加密(Encryption)：將明文變換為密文的過程。 解密解密(Decryption)：加密的逆過程，即由密文恢復(fù)出原明文的過程。 加密員加密員或密碼員密碼員(Cryptographer)：對明文進(jìn)行加密操作的人員。密碼學(xué)的基本概念(3)密碼學(xué)的基本概念(4) 加密算法加密算法(Encryption algorithm)：密碼員對明文進(jìn)行加密時所采用的一組規(guī)則。接收者接收者(Receiver)：傳送消息的預(yù)定對象。解密算法：解密算法：接收者對密文進(jìn)行解密時所采用的一組規(guī)則。密鑰密鑰(Key)：控制加密和解密算法操作的數(shù)據(jù)處理，分別稱作加密密

3、鑰加密密鑰和解密密鑰解密密鑰。截收者截收者(Eavesdropper)：在信息傳輸和處理系統(tǒng)中的非受權(quán)者，通過搭線竊聽、電磁竊聽、聲音竊聽等來竊取機(jī)密信息。密碼學(xué)的基本概念(5) 密碼分析密碼分析(Cryptanalysis)：截收者試圖通過分析從截獲的密文推斷出原來的明文或密鑰。 密碼分析員密碼分析員(Cryptanalyst)：從事密碼分析的人。 被動攻擊被動攻擊(Passive attack)：對一個保密系統(tǒng)采取截獲密文進(jìn)行分析的攻擊。 主動攻擊主動攻擊(Active attack)：非法入侵者入侵者(Tamper)、攻擊者攻擊者(Attcker)或黑客黑客(Hacker)主動向系統(tǒng)竄擾

4、，采用刪除、增添、重放、偽造等竄改手段向系統(tǒng)注入假消息，達(dá)到利已害人的目的。 一個密碼系統(tǒng)，通常簡稱為密碼體制，由5部分組成：密碼體制基本組成明文空間明文空間M密文空間密文空間C密鑰空間密鑰空間K加密算法加密算法E解密算法解密算法D信息加密傳輸?shù)倪^程w 加密加密: C = E(M,Ke)MCEKeCMKdDw 解密解密: M = D(C, Kd)M-明文 C-密文Ke-加密密鑰 Kd-解密密鑰E-加密算法 D-解密算法明文加密算法加密密鑰K1網(wǎng)絡(luò)信道解密算法明文解密密鑰K2密文用戶用戶A用戶用戶B傳送給B的信息B收到信息竊聽者竊聽者CC竊聽到的信息竊聽到的信息!#$% 根據(jù)密鑰的使用方式分類根

5、據(jù)密鑰的使用方式分類 對稱密碼體制（傳統(tǒng)密鑰密碼體制） 用于加密數(shù)據(jù)的密鑰和用于解密數(shù)據(jù)的密鑰相同，或者二者之間存在著某種明確的數(shù)學(xué)關(guān)系。 加密：EK(M)=C 解密：DK(C)=M 非對稱密碼體制（公鑰密碼體制） 用于加密的密鑰與用于解密的密鑰是不同的，而且從加密的密鑰無法推導(dǎo)出解密的密鑰。 用公鑰KP對明文加密可表示為：EKP(M)=C 用相應(yīng)的私鑰KS對密文解密可表示為：DKS(C)=M密碼系統(tǒng)的分類(1) 根據(jù)明文和密文的處理方式分類根據(jù)明文和密文的處理方式分類 分組密碼體制（Block Cipher） 設(shè)M為明文，分組密碼將M劃分為一系列明文塊Mi，通常每塊包含若干字符，并且對每一塊

6、Mi都用同一個密鑰Ke進(jìn)行加密。 M=(M1, M2, ,Mn) ，C=(C1, C2 , ,Cn,)，其中Ci=E(Mi,Ke)， i=1,2,n。 序列密碼體制（Stream Cipher） 將明文和密鑰都劃分為位(bit)或字符的序列，并且對明文序列中的每一位或字符都用密鑰序列中對應(yīng)的分量來加密。 M=(M1, M2, ,Mn) ， Ke=(ke1, ke2,ken)，C=(C1, C2,Cn)，其中Ci=E(mi,kei) ，i=1,2,n。 密碼系統(tǒng)的分類(2) 密碼分析（破解密碼）截收者在不知道解密密鑰及通信者所采用的加密體制的細(xì)節(jié)條件下，對密文進(jìn)行分析，試圖獲取機(jī)密信息。研究分析

7、解密規(guī)律的科學(xué)稱作密碼分析學(xué)。密碼分析在外交、軍事、公安、商業(yè)等方面都具有重要作用，也是研究歷史、考古、古語言學(xué)和古樂理論的重要手段之一。 密碼分析密碼設(shè)計和密碼分析是共生的、又是互逆的，兩者密切有關(guān)但追求的目標(biāo)相反。兩者解決問題的途徑有很大差別 密碼設(shè)計是利用數(shù)學(xué)來構(gòu)造密碼 密碼分析除了依靠數(shù)學(xué)、工程背景、語言學(xué)等知識外，還要靠經(jīng)驗、統(tǒng)計、測試、眼力、直覺判斷能力，有時還靠點(diǎn)運(yùn)氣。 密碼分析方法分析法 確定性分析法確定性分析法 利用一個或幾個已知量(比如，已知密文或明文-密文對)用數(shù)學(xué)關(guān)系式表示出所求未知量(如密鑰等)。已知量和未知量的關(guān)系視加密和解密算法而定，尋求這種關(guān)系是確定性分析法的關(guān)

8、鍵步驟。 統(tǒng)計分析法統(tǒng)計分析法 利用明文的已知統(tǒng)計規(guī)律進(jìn)行破譯的方法。密碼破譯者對截收的密文進(jìn)行統(tǒng)計分析，總結(jié)出其間的統(tǒng)計規(guī)律，并與明文的統(tǒng)計規(guī)律進(jìn)行對照比較，從中提取出明文和密文之間的對應(yīng)或變換信息。 密碼可能經(jīng)受的攻擊攻擊類型攻擊者擁有的資源惟密文攻擊v加密算法v截獲的部分密文已知明文攻擊v加密算法，v截獲的部分密文和相應(yīng)的明文選擇明文攻擊v加密算法v加密黑盒子，可加密任意明文得到相應(yīng)的密文選擇密文攻擊v加密算法v解密黑盒子，可解密任意密文得到相應(yīng)的明文 密碼分析方法-窮舉破譯法 對截收的密報依次用各種可解的密鑰試譯，直到得到有意義的明文；一般來說，要獲取成功必須嘗試所有可能密鑰的一半。

9、或在不變密鑰下，對所有可能的明文加密直到得到與截獲密報一致為止，此法又稱為完全試湊法完全試湊法(Complete trial-and-error Method)。 只要有足夠多的計算時間和存儲容量，原則上窮舉法總是可以成功的。但實際中，任何一種能保障安全要求的實用密碼都會設(shè)計得使這一方法在實際上是不可行的。 古典密碼分類 代換密碼（ substitution ）：代換是古典密碼中用到的最基本的處理技巧。所謂代換，就是將明文中的一個字母由其它字母、數(shù)字或符號替代的一種方法。 凱撒密碼 仿射密碼 單表代換 多表代換 置換密碼（permutation）：將明文字符按照某種規(guī)律重新排列而形成密文的過程

10、。l一種早期的 希臘變換密碼l一張紙條環(huán)繞在一個圓柱上 l消息沿著圓柱橫寫l紙條上的字母看起來是一些隨機(jī)字母l并不十分安全，密鑰是紙條和圓柱的寬度凱撒密碼(caesar cipher)已知最早的代換密碼，又稱移位密碼 代換表（密鑰）：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 zD 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凱撒密碼例:使用其后的第三個字母代換該字母明文：meet me after the toga party密文：PHHW PH DIWHU WKH WRJD SDU

11、WB愷撒密碼的攻擊用數(shù)字表示每個字母：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 Z0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25c = E(p) = (p + k) mod (26)p = D(c) = (c k) mod (26)明文p Z26，密文c Z26 ，密鑰k取1,25，只有25個 已知明文和密文、加密和解密算法，需要解同余方程，可以恢復(fù)密鑰 k = (c- p) mod (26)； 窮舉攻擊：已知密文，且明文為有意義字符，至多嘗試25次

12、，可以恢復(fù)明文.3.密碼分析（Cryptanalysis of Caesar ciphers） A maps to A,B,.Z 可以簡單的實驗每個密鑰（窮密鑰搜索） 給定一些密文，實驗每個密鑰。 LIZHZLVKWRUHSODFHOHWWHUV Original ciphertext KHYGYKUJVQTGRNCEGNGVVGTU try shift of 1 JGXFXJTIUPSFQMBDFMFUUFST try shift of 2 IFWEWISHTOREPLACELETTERS try shift of 3 * plaintext HEVDVHRGSNQDOKZBDKDSSDQR

13、 try shift of 4 GDUCUGQFRMPCNJYACJCRRCPQ try shift of 5 . MJAIAMWLXSVITPEGIPIXXIVW try shift of 25 eg. break ciphertext GCUA VQ DTGCM 仿射密碼（Affine Cipher） 移位密碼的擴(kuò)展明文p Z26，密文c Z26 ，密鑰k=(a,b) Z26 Z26, 且gcd(a,26)=1. 加密：c = E(p) = (a p + b) mod 26解密：p = D(c) = (c b) a-1mod 26仿射密碼例：令密鑰k=(7,3), 且gcd(7,26)=1

14、. 明文hot=(7,14,19)加密：(7 7 + 3) mod 26 = 0(7 14 + 3) mod 26 =23(7 19 + 3) mod 26 =6密文為(0,23,6)=(a,x,g)解密：7-1=15=-11 mod 26(0- 3) 15 mod 26 = 7(23- 3) 15 mod 26 =14(6- 3) 15 mod 26 =19明文為(7,14,19)=(h, o,t)仿射密碼 已知兩對明文和密文（p1,c1）和（p2,c2）、加密和解密算法，需要解2元同余方程組，可以恢復(fù)密鑰k=(a,b)；c1 = (a p1 + b) mod 26c2 = (a p2 +

15、b) mod 26 窮舉攻擊：已知密文，明文為有意義字符，至多嘗試26*(26)個，可以恢復(fù)明文.單表代換密碼 代換表是26個字母的任意置換 例：加密函數(shù):n o p q r s t u v wx y zX HT MY A UOL R GZ Na b c d e f g h i j k l mDK V QF I B J WP E S CNOP QR S T U V WX Y Zz u j d wl p t c i n r yA B C DE FGH I J K L Ms g ma k ex o f h b v q單表代換密碼 已知明文和密文，可以恢復(fù)部分加密函數(shù)（解密函數(shù)）； 窮舉攻擊：已知密

16、文，明文為有意義字符，至多嘗試26! = 288個，可以恢復(fù)明文代換表的個數(shù)為26！一般單表代換密碼簡單的方法給出密鑰寫出密鑰（刪除重復(fù)字母）write key (with repeated letters deleted) 在其下面依次寫出剩余字母（以橫、縱行）按列讀取字母得到密文。then read off by columns to get ciphertext equivalents 舉例給定密鑰字 STARWARS 去掉重復(fù)字母得到 STARW 填寫剩余字母： STARW BCDEF GHIJK LMNOP QUVXY Z 按列讀取字母得到密文 Plain: ABCDEFGHIJKL

17、MNOPQRSTUVWXYZ Cipher: SBGLQZTCHMUADINVREJOXWFKPY 可以用這個密鑰加密、解密 例如 Plaintext: I KNOW ONLY THAT I KNOW NOTHING Ciphertext: H UINF NIAP OCSO H UINF INOCHIT 多表代換密碼(Polyalphabetic Ciphers) 加密明文消息時采用不同的單表代換，由密鑰具體決定采用哪個表代換消息，密鑰通常是一個詞的重復(fù)。 簡化的多表代換密碼 -維吉尼亞密碼（ Vigenre Cipher ）：由26個類似 caesar密碼的代換表組成多表代換密碼 維吉尼亞密

18、碼：在長為m的密碼中，任何一個字母可被影射為26個字母中的一個明文p (Z26)m，密文c (Z26)m ，密鑰k (Z26)m 加密 c= (p1+k1 ,p2+k2 , , pm+km) mod 26; 解密 p = (c1-k1 ,c2-k2 , , cm-km) mod 26.多表代換密碼 例明文: nice work，密鑰：hot，求密文.多表代換密碼 已知m個連續(xù)的明文和密文，可以恢復(fù)維吉尼亞密碼的單表移位量（即密鑰）； 窮舉攻擊：已知密文，明文為有意義字符，至多嘗試26m 個，可以恢復(fù)明文密鑰空間大小是26m置換密碼 加密變換使得信息元素只有位置變化而形態(tài)不變，如此可以打破消息中

19、的某些固定模式（結(jié)構(gòu)） 明文p (Z26)m，密文c (Z26)m ， 密鑰k |定義在1,2,m上的置換 加密 c= (p (1) ,p ( 2) , , p ( m) mod 26; 解密 p = (c -1(1) ,c -1(2) , , c -1(m) mod 26.置換密碼例 密鑰明文：she sells sea shells by the sea shore分組：shesel lsseas hellsb ythese ashore置換：EESLSH SALSES LSHBLE HSYEET HRAEOS置換密碼X1234Pi(x)2413置換密碼 已知多對明文和密文，可以推導(dǎo)置換表

20、（即密鑰）； 窮舉攻擊：已知密文，明文為有意義字符，至多嘗試m！ 個，可以恢復(fù)明文分組為m，至多有m！個置換希爾密碼（Hill cipher）1929年，LesterS. Hill提出明文p (Z26)m，密文c (Z26)m ， 密鑰K 定義在Z26上m*m的可逆矩陣 加密 c = p * K mod 26 解密 p = c * K-1 mod 26擴(kuò)散希爾密碼 例希爾密碼 置換密碼可以看做是希爾密碼的特例。練習(xí)：設(shè)hill密碼的密鑰如下，求對應(yīng)置換密碼的置換表。希爾密碼 已知m組明文和密文、加密和解密算法，需要解m元同余方程組，可以恢復(fù)密鑰； 窮舉攻擊：已知密文，明文為有意義字符，至多嘗試

21、26m*m個，可以恢復(fù)明文11121m11121m11121mm1m2mmm1m2mmm1m2mmcccpppkkkcccpppkkk9。ADFGVX 乘積密碼 這樣命名是因為變換僅依賴與 ADFGVX 在WW1有德國人使用，并被英國人破譯 方法： 使用一個固定的替換表，把每個明文字母映射成一個字母對 (row-col index) 在用一個帶密鑰的塊變換把每個對分解then 利用帶密鑰的塊變換寫下所有字母對 寫出密文（按塊密碼形式）ADFGVX Substitution Table A D F G V X A K Z W R 1 F D 9 B 6 C L 5 F Q 7 J P G X G

22、 E V Y 3 A N V 8 O D H 0 2 X U 4 I S T M 11。 ADFGVX ADFGVX 加密舉例加密舉例 Plaintext: PRODUCTCIPHERS Intermediate Text: FG AG VD VF XA DG XV DG XF FG VG GA AG XG 帶密鑰的塊變換矩陣： D E U T S C H Key 2 3 7 6 5 1 4 Sorted Order F G A G V D V F X A D G X V D G X F F G V G G A A G X G Ciphertext: DXGX FFDG GXGG VVVG V

23、GFG CDFA AAXA 轉(zhuǎn)輪密碼（Rotor Machine） 19世紀(jì)20年代，開始出現(xiàn)機(jī)械加解密設(shè)備，最典型的是轉(zhuǎn)輪密碼機(jī) 1918年Arthur Scherbius發(fā)明的EIGMA，瑞典Haglin發(fā)明的Haglin，和日軍發(fā)明的“紫密”和“蘭密”都屬于轉(zhuǎn)輪密碼機(jī)。轉(zhuǎn)輪密碼Enigma密碼機(jī)密碼機(jī)轉(zhuǎn)輪密碼Dan BonehRotor Machines (cont.)Most famous: the Enigma (3-5 rotors)# keys = 264 = 218 (actually 236 due to plugboard) 惟密文攻擊 在攻擊者可以截獲（足夠）明密文的條件下，易于恢復(fù)用戶的密鑰； 當(dāng)攻擊者只能竊聽到密文時，若明文是有意義的（一段話等具有可讀性）字符時，利用窮舉搜索，可以通過密文解密出對應(yīng)明文，繼而恢復(fù)密鑰。（窮舉搜索的復(fù)雜度取決于密鑰空間的大小，古典密碼體制的密鑰空間通常比較小。）惟密文攻擊人類的語言存在冗余，以英文文檔為例 字母 e 是使用頻率最高的 其次是 T,R,N,I,O,A,S Z,J,K,Q,X 很少使用 A、I、U很少用在詞尾，E、N、R常出現(xiàn)在詞尾。E、S、D作為字母結(jié)尾字母的單詞超過一半，T、A、S、W為起始字