第6講 經(jīng)典密碼學(xué)

1、第第6 6講講 經(jīng)典密碼學(xué)經(jīng)典密碼學(xué)o古典加密算法o分組加密算法密碼學(xué)相關(guān)術(shù)語o密碼編碼學(xué)(cryptography)是密碼體制的設(shè)計(jì)學(xué)，而密碼分析學(xué)(cryptanalysis)則是在未知密鑰的情況下從密文推演出明文或密鑰的技術(shù)。密碼編碼學(xué)與密碼分析學(xué)合起來即為密碼學(xué)(cryptology)。o如果不論截取者獲得了多少密文，但在密文中都沒有足夠的信息來惟一地確定出對(duì)應(yīng)的明文，則這一密碼體制稱為無條件安全的，或稱為理論上是不可破的。o如果密碼體制中的密碼不能被可使用的計(jì)算資源破譯，則這一密碼體制稱為在計(jì)算上是安全的。 基本術(shù)語o使消息保密的技術(shù)和科學(xué)叫做密碼編碼學(xué)密碼編碼學(xué)（cryptogra

2、phy），o從事此行業(yè)的叫做密碼編碼者密碼編碼者（cryptographer），o密碼分析者密碼分析者（cryptanalyst）是從事密碼分析的專業(yè)人員，o密碼分析學(xué)密碼分析學(xué)（cryptanalysis）就是破譯密文的科學(xué)和技術(shù)。o密碼學(xué)密碼學(xué)（cryptology）作為數(shù)學(xué)的一個(gè)分支，包括密碼編碼學(xué)和密碼分析學(xué)兩部分?；拘g(shù)語(續(xù))o消息被稱為明文明文(Plaintext)(Plaintext)，用某種方法偽裝消息以隱藏它的內(nèi)容的過程稱為加密加密(Encrtption)(Encrtption)，被加密的消息稱為密文密文(Ciphertext)(Ciphertext)，而把密文轉(zhuǎn)變?yōu)槊魑牡?/p>

3、過程稱為解密解密(Decryption)(Decryption) o密碼算法密碼算法(Cryptography Algorithm):(Cryptography Algorithm):是用于加密和解密的數(shù)學(xué)函數(shù)o發(fā)送者對(duì)明文進(jìn)行加密操作時(shí)所采用的一組規(guī)則稱作加密算法加密算法(Encryption Algorithm)(Encryption Algorithm)o接收者對(duì)密文解密所采用的一組規(guī)則稱為解密算解密算法法(Decryption Algorithm)(Decryption Algorithm) 加解密過程示意圖o加密和解密算法的操作通常都是在一組密鑰的控制下進(jìn)行的,分別稱為加密密鑰加密密

4、鑰(Encryption Key) 和解密密鑰解密密鑰(Decryption Key)明文明文密文加密算法解密算法加密密鑰解密密鑰一般的數(shù)據(jù)加密模型 E加密算法D解密算法加密密鑰 K解密密鑰 K明文 X明文 X密文 Y = EK(X)截取者截獲篡改密鑰源安全信道密碼體制o密碼體制：它是一個(gè)五元組（P,C,K,E,D)滿足條件： （1）P是可能明文的有限集；（明文空間） （2）C是可能密文的有限集；（密文空間） （3）K是一切可能密鑰構(gòu)成的有限集；（密鑰空間） *（4）任意k K,有一個(gè)加密算法 和相應(yīng)的解密算法 ，使得 和 分別為加密解密函數(shù)，滿足dk(ek(x)=x, 這里 x P。EekD

5、dkCPek:PCdk:密碼分析密碼分析o密碼分析學(xué)，是攻擊者在不知道密鑰的情況密碼分析學(xué)，是攻擊者在不知道密鑰的情況下，恢復(fù)出明文的科學(xué)。對(duì)密碼進(jìn)行分析的下，恢復(fù)出明文的科學(xué)。對(duì)密碼進(jìn)行分析的嘗試稱為攻擊（嘗試稱為攻擊（Attack)。o攻擊密碼的方法：攻擊密碼的方法： 窮舉法，又稱強(qiáng)力法（窮舉法，又稱強(qiáng)力法（Brute-force） 分析法分析法密碼分析oKerchkhoff原則n假設(shè)攻擊者是在已經(jīng)密碼體制的前提下來破譯密碼系統(tǒng)的密鑰；o最常見的破解類型如下：n唯密文攻擊：o攻擊者有一些密文，它們是使用同一加密算法和同一密鑰加密的；n已知明文攻擊：o攻擊者不但得到一些密文，而且能夠得到這些

6、密文對(duì)應(yīng)的明文；密碼分析n3 選擇明文攻擊：o攻擊者不僅得到一些密文和明文，而且能選擇用于加密的明文；n4 選擇密文攻擊：o攻擊者可以選擇不同的密文來解密，并能夠得到解密后的明文；o這一切的目的都是：破譯出密鑰o一般說來：密碼系統(tǒng)應(yīng)該經(jīng)得起已知明文的攻擊。o如果攻擊者無論得到多少密文，都沒有足夠的信息去恢復(fù)明文，則密碼系統(tǒng)是無條件安全的。理論上，只有一次一密的系統(tǒng)才能真正實(shí)現(xiàn)。古典密碼-信息隱藏oSteganography也稱隱寫術(shù)：將秘密消息隱藏在其他消息中。o隱形墨水，字符上的針眼，手寫字符的差異，字符上的鉛筆記號(hào)等o圖象中隱寫：用消息位代替圖象的每個(gè)字節(jié)的最不重要的位，而肉眼無法看出差異

7、；o隱寫術(shù)不使用算法或者密鑰Steganographyo(a) Three zebras and a tree. (b) Three zebras, a tree, and the complete text of five plays by William Shakespeare.o(a) Three zebras and a tree. o(b) Three zebras, a tree, and the complete text of five plays by William Shakespeare.1.1.移位密碼體制移位密碼體制( (單字母單字母) )o設(shè)P=C=K=Z/(26)

8、,對(duì) ,定義 同時(shí)dk(y)=y-k (mod 26)注1*：26個(gè)英文字母與模26剩余類集合0,.,25建立一一對(duì)應(yīng)：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 25 2*.當(dāng)k=3時(shí)，為Caesar密碼： 若明文： caesar cipher 密文： FDHVDU FLSKHU 實(shí)際算法為： 有 同時(shí)有，d3(y)=y-3 (mod 26)Pxyxxe)26(mod3)(3KkCykxxek)26(mod

9、)(3*.一個(gè)密碼體制要是實(shí)際可用必須滿足的特性o每一個(gè)加密函數(shù)ek和每一個(gè)解密函數(shù)dk都能有效地計(jì)算。o破譯者取得密文后，將不能在有效的時(shí)間內(nèi)破解出密鑰k或明文x。o一個(gè)密碼體制是安全的必要條件窮舉密鑰搜索將是不可行的，即密鑰空間將是非常大的。移位密碼o移位密碼(substitution cipher)的原理可用一個(gè)例子來說明。（密鑰是 3） abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABCcaesar cipherFDHVDU FLSKHU明文密文明文 c 變成了密文 F移位密碼o移位密碼(substitution cipher)的原

10、理可用一個(gè)例子來說明。（密鑰是 3） abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABCcaesar cipherFDHVDU FLSKHU明文密文明文 a 變成了密文 D移位密碼o移位密碼(substitution cipher)的原理可用一個(gè)例子來說明。（密鑰是 3） abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABCcaesar cipherFDHVDU FLSKHU明文密文明文 e 變成了密文 H凱撒密碼的改進(jìn)o凱撒密碼只有25個(gè)密鑰k，非常不安全；o若有意改變字母的排列順序，可

11、增大密鑰空間；o例如：使用密鑰nKeyoABCDEFGHIJKLMNOPQRSTUVWXYZokeyabcdfghijlmnopgrstuvwxznspectacularoABCDEFGHIJKLMNOPQRSTUVWXYZospectacularbdfghijkmnoqvwxyzn泄露給破譯者的信息更少；2.替換密碼體制替換密碼體制o設(shè)P=C=Z/(26)，K是由26個(gè)符號(hào)0，1,.,25的所有可能置換組成。任意 ，定義 d (y)=-1(y)=x, -1是的逆置換。 注：1*. 置換的表示： 2*密鑰空間K很大，|K|=26! 41026，破譯者窮舉搜索是不行的，然而，可由統(tǒng)計(jì)的方式破譯它

12、。3*移位密碼體制是替換密碼體制的一個(gè)特例，它僅含26個(gè)置換做為密鑰空間K且yxxe)()(252423 3 2 1 025242332103.仿射密碼體制仿射密碼體制o替換密碼的另一個(gè)特例就是仿射密碼。 加密函數(shù)取形式為 要求唯一解的充要條件是gcd( a,26)=1 該體制描述為： 設(shè)P=C=Z/(26) 對(duì) 定義 ek(x)=ax+b (mod 26) dk(y)=a-1(y-b)(mod 26) )26/(,),26(mod)(Zbabaxxe,1)26,gcd(| )26/()26/(),(aZZbaK,),(Kbak)26/(,Zyxo例子，設(shè)k（7，3），注意到7-1(mod 2

13、6)=15,加密函數(shù)是ek(x)=7x+3,相應(yīng)的解密函數(shù)是dk(y)=15(y-3)=15y-19 , 易見 dk(ek(x)=dk(7x+3)=15(7x+3)-19 =x+45-19 =x (mod 26) 若加密明文：hot ，首先轉(zhuǎn)換字母h,o,t成為數(shù)字7,14,19,然后加密：解密：);26(mod6230333191477GXA19147191919623015英文中字母的使用頻率 02468101214A B C D E F G HI J K L MNOP QR S T U V WX Y Z頻率頻率E使用最多；使用最多；然后是然后是T R N I O A S其他字母使用較少其

14、他字母使用較少最少的是最少的是J K Q X Z4.4.維吉尼亞密碼維吉尼亞密碼 (Vigenere,多字母多字母)o設(shè)m為一固定的正整數(shù)，定義P=C=K=(Z/(26)m,對(duì)一個(gè)密鑰K（ k1,k2,km),定義 ek(x1,x2,xm)=(x1+k1,x2+k2,xm+km)=y dk(y1,y2,ym)= (x1-k1,x2-k2,xm-km) =x這里的所有的運(yùn)算都是在（mod 26)中進(jìn)行的。維基尼亞密碼（Vigenere）-示例o若密鑰字為deceptive，即m=9o明文wearediscoveredsav的加密過程：n明文：wearediscoeredsavn密鑰：decept

15、ivedeceptiven密文：ZICVTWQNGRZGVTWAVZo密鑰字母d對(duì)應(yīng)數(shù)字3，因而明文字母w在密鑰字母d的作用下向后移位3，得到密文字母Z。依次類推；維基尼亞密碼（Vigenere）o維基尼亞密碼是多表替換體制，分析起來更加困難。o密鑰空間大，可能的密鑰字達(dá)26m o如果秘要字的長(zhǎng)度是m，明文中的一個(gè)字母能夠映射成這m個(gè)可能的字母中的一個(gè)；o例如，當(dāng)m=5，密鑰空間所含密鑰的數(shù)量是1.1x107 o明文和密文的字母頻率分布相同，仍然能使用統(tǒng)計(jì)分析破譯 5.Hill密碼體制密碼體制o設(shè)為某個(gè)固定的正整數(shù)，P=C=(Z/(26)m, K=Z/(26)上的mm可逆矩陣 對(duì)每一個(gè) ,定義

16、ek(x)=xk (mod 26)和 dk(y)=yk-1 (mod 26)注：明文與密文都是 m元的向量（x1, x2 , xm );(y1, y2,ym)，Z/(26)為同余類環(huán)。在這個(gè)環(huán)上的可逆矩陣Amxm,是指行列式detAmxm的值 Z*/(26),它為Z/(26)中全體可逆元的集合。Z*/(26)= a Z/(26)|(a,26)=1， Z*/(26)=1,3,5,7,9,11,15,17,19,21,23,25例子：當(dāng) m=2時(shí)，明文元素x=(x1,x2),密文元素y=(y1,y2) (y1,y2)=(x1,x2) k 73811Kko事實(shí)上yi為x1,x2的線性組合，y1=11

17、x1+3x2;y2=8x1+7x2，一般，將取mm的矩陣K作為我們的密鑰：有 y=(y1, y2, ym,)=(x1, x2, xm) 換言之，y=xK;且有x=yK-1 若K= ,可得K-1 = 若對(duì)明文july加密，它分成2個(gè)元素（j,u),(l,y),分別對(duì)應(yīng)于（9,20）,（11,24）,有mmmmmmkkkkkkkkk212222111211738111123187（9,20） （9960,72140）（3,4） 且（11,24 ） (12172,88168) （11,22）于是對(duì) july加密的結(jié)果為DELW。 為了解密，Bob計(jì)算 且 因此，得到了正確的明文“july”73811

18、73811 )20, 9(1123187)4 , 3()24,11(1123187)22,11(6.置換密碼體制置換密碼體制o設(shè)m為固定的正整數(shù)，P=C=(Z/(26)m, K是由1,2,.,m的所有置換構(gòu)成，對(duì)一個(gè)密鑰K，定義 e (x1, x2,., xm)=(x(1),.,x(m) 和 d (y1, y2,., ym)=(y(1),.,y(m) 這里1為的逆置換。注：這里的加密與解密僅僅用了置換，無代數(shù)運(yùn)算。例子： 設(shè)m=6, 取密鑰 而) 6452)(31 (264564135231) 5462)(31 (4625541362311若給定的明文是：cryptography 首先找分成6

19、個(gè)字母長(zhǎng)的明文組：crypto|graphy 求得的密文是：YTCOPRAHGYPR注：事實(shí)上，置換密碼是Hill密碼的特例。給定一個(gè)集合1,2,.,m的置換矩陣 (置換矩陣是每一行和每一列剛好在一個(gè)“1”，而其余元素為“0”的矩陣。)請(qǐng)同學(xué)們驗(yàn)證YTCOPRroptopcytryccryptoAHGYPRryphypgahraggraphy否則若0)(1)(ijkkKijnmij對(duì)上面例子決定的置換 對(duì)應(yīng)：000010001000100000000001010000000100K00100000001001000000000110000000010011KKCIPHER145326attac

20、kbeginsatfour置換密碼o置換密碼(transposition cipher)則是按照某一規(guī)則重新排列消息中的比特或字符順序。 密鑰順序明文根據(jù)英文字母在 26 個(gè)字母中的先后順序，我們可以得出密鑰中的每一個(gè)字母的相對(duì)先后順序。因?yàn)槊荑€中沒有 A 和 B，因此 C 為第 1。同理，E 為第 2，H 為第 3,，R 為第 6。于是得出密鑰字母的相對(duì)先后順序?yàn)?145326。 CIPHER145326attackbeginsatfour置換密碼o置換密碼(transposition cipher)則是按照某一規(guī)則重新排列消息中的比特或字符順序。 密鑰順序明文根據(jù)英文字母在 26 個(gè)字母中

21、的先后順序，我們可以得出密鑰中的每一個(gè)字母的相對(duì)先后順序。因?yàn)槊荑€中沒有 A 和 B，因此 C 為第 1。同理，E 為第 2，H 為第 3,，R 為第 6。于是得出密鑰字母的相對(duì)先后順序?yàn)?145326。 CIPHER145326attackbeginsatfour置換密碼o置換密碼(transposition cipher)則是按照某一規(guī)則重新排列消息中的比特或字符順序。 密鑰順序明文根據(jù)英文字母在 26 個(gè)字母中的先后順序，我們可以得出密鑰中的每一個(gè)字母的相對(duì)先后順序。因?yàn)槊荑€中沒有 A 和 B，因此 C 為第 1。同理，E 為第 2，H 為第 3,，R 為第 6。于是得出密鑰字母的相對(duì)先

22、后順序?yàn)?145326。 CIPHER145326attackbeginsatfour置換密碼o置換密碼(transposition cipher)則是按照某一規(guī)則重新排列消息中的比特或字符順序。 密鑰順序明文根據(jù)英文字母在 26 個(gè)字母中的先后順序，我們可以得出密鑰中的每一個(gè)字母的相對(duì)先后順序。因?yàn)槊荑€中沒有 A 和 B，因此 C 為第 1。同理，E 為第 2，H 為第 3,，R 為第 6。于是得出密鑰字母的相對(duì)先后順序?yàn)?145326。 CIPHER145326attackbeginsatfour置換密碼o置換密碼(transposition cipher)則是按照某一規(guī)則重新排列消息中的

23、比特或字符順序。 密鑰順序明文根據(jù)英文字母在 26 個(gè)字母中的先后順序，我們可以得出密鑰中的每一個(gè)字母的相對(duì)先后順序。因?yàn)槊荑€中沒有 A 和 B，因此 C 為第 1。同理，E 為第 2，H 為第 3,，R 為第 6。于是得出密鑰字母的相對(duì)先后順序?yàn)?145326。 CIPHER145326attackbeginsatfour置換密碼o置換密碼(transposition cipher)則是按照某一規(guī)則重新排列消息中的比特或字符順序。 密鑰順序明文根據(jù)英文字母在 26 個(gè)字母中的先后順序，我們可以得出密鑰中的每一個(gè)字母的相對(duì)先后順序。因?yàn)槊荑€中沒有 A 和 B，因此 C 為第 1。同理，E 為第

24、 2，H 為第 3,，R 為第 6。于是得出密鑰字母的相對(duì)先后順序?yàn)?145326。 CIPHER145326attackbeginsatfour密文的得出密鑰順序明文先讀順序?yàn)?1 的明文列，即 aba CIPHER145326attackbeginsatfour密文的得出密鑰順序明文再讀順序?yàn)?2 的明文列，即 cnu CIPHER145326attackbeginsatfour密文的得出密鑰順序明文再讀順序?yàn)?3 的明文列，即 aio CIPHER145326attackbeginsatfour密文的得出密鑰順序明文再讀順序?yàn)?4 的明文列，即 tet CIPHER145326attac

25、kbeginsatfour密文的得出密鑰順序明文再讀順序?yàn)?5 的明文列，即 tgf CIPHER145326attackbeginsatfour密文的得出密鑰順序明文最后讀順序?yàn)?6 的明文列，即 ksr 因此密文就是：abacnuaiotettgfksr CIPHER145326attackbeginsatfour接收端收到密文后按列寫下密鑰順序明文先寫下第 1 列密文 aba 收到的密文：abacnuaiotettgfksr CIPHER145326attackbeginsatfour接收端收到密文后按列寫下密鑰順序明文再寫下第 2 列密文 cnu 收到的密文：abacnuaiotett

26、gfksr CIPHER145326attackbeginsatfour接收端收到密文后按列寫下密鑰順序明文再寫下第 3 列密文 aio 收到的密文：abacnuaiotettgfksr CIPHER145326attackbeginsatfour接收端收到密文后按列寫下密鑰順序明文再寫下第 4 列密文 tet 收到的密文：abacnuaiotettgfksr CIPHER145326attackbeginsatfour接收端收到密文后按列寫下密鑰順序明文再寫下第 5 列密文 tgf 收到的密文：abacnuaiotettgfksr CIPHER145326attackbeginsatfour接收端收到密文后按列寫下密鑰順序明文最后寫下第 6 列密文 ksr 收到的密文：abacnuaiotettgfksr CIPHER145326attackbeginsatfour接收端從密文解出明文密鑰順序明文最后按行讀出明文收到的密文：abacnuaiotettgfksr CIPHER145326attackbeginsatfour接收端從密文解出明文