密碼學(xué)-古典密碼(2)

1、第二章、密碼學(xué) 主要內(nèi)容 密碼學(xué)的歷史發(fā)展過程 基本術(shù)語和定義 相關(guān)基礎(chǔ)數(shù)學(xué)理論 古典密碼 現(xiàn)代密碼1、密碼學(xué)的起源 隱寫術(shù)(Steganography)：通過隱藏消息的存在來保護(hù)消息。常用的手段包括：隱形墨水、字符格式的變化、圖形圖像（水?。?。1、密碼學(xué)的起源 象形文字的修改(Modified Hieroglyphics)：密碼學(xué)的第一個(gè)例子是對標(biāo)準(zhǔn)書寫符號的修改，例如古埃及法老墳?zāi)股系奈淖郑?200-1100 B.C.），核心思想是代替(Substitution)1、密碼學(xué)的起源 500 B.C.，斯巴達(dá)人在軍事上用于加解密 發(fā)送者把一條羊皮紙螺旋形地纏在一個(gè)圓柱形木棒上，核心思想是置換（

2、Permutation）1、密碼學(xué)的起源 205-123 B.C.，棋盤密碼 1 2 3 4 5 1 A B C D E 2 F G H IJ K 3 L M N O P 4 Q R S T U 5 V W X Y Z HELLO 23153131341、密碼學(xué)的起源 50 B.C.，愷撒密碼HELLO KHOOR A B C D E F G X Y Z D E F G H I J A B C 2、密碼學(xué)發(fā)展的三個(gè)階段 1949年之前 古典密碼 19491975年 傳統(tǒng)密碼 1976年以后 現(xiàn)代密碼2、密碼學(xué)發(fā)展的三個(gè)階段 1949年之前 古典密碼 密碼學(xué)還不是科學(xué)，而是藝術(shù) 出現(xiàn)一些密碼算法

3、和加密設(shè)備 密碼算法的基本手段(代替 &置換)出現(xiàn)，針對的是字符 簡單的密碼分析手段出現(xiàn) 基于字符的密碼2、密碼學(xué)發(fā)展的三個(gè)階段 代替密碼（substitution cipher） 明文中的每個(gè)字符被替換成密文中的另外的字符。接收者對密文做反向替換就可以恢復(fù)出明文。 簡單代替密碼（單字母密碼） 多字母密碼 置換密碼(permutation cipher)2、密碼學(xué)發(fā)展的三個(gè)階段 簡單代替密碼 明文的一個(gè)字符用相應(yīng)的一個(gè)密文字符代替。 單表代換 一個(gè)明文字符對應(yīng)固定的一個(gè)密文字符 可用頻率分析的方法破解 多表代換 一個(gè)明文字符對應(yīng)幾個(gè)密文字符，加密時(shí)任選其中一個(gè) 可隱藏明文字母的統(tǒng)計(jì)信息

4、 增大了密文空間2、密碼學(xué)發(fā)展的三個(gè)階段 單表代替密碼的頻率分析2、密碼學(xué)發(fā)展的三個(gè)階段 多表代替密碼的設(shè)計(jì) 出現(xiàn)頻率高的字符用更多的密文來代替，以隱藏明文字母的統(tǒng)計(jì)信息 例如： a2,41,89 c9,38 k78 t1,8,43,66,91 明文ATTACK可加密為(2,1,8,41,9,78)或(41,43,91,38,78)2、密碼學(xué)發(fā)展的三個(gè)階段 多字母密碼 明文中的字符映射到密文空間的字符還依賴于它在上下文中的位置?？梢杂镁仃囎儞Q方便地描述多字母代換密碼，有時(shí)又稱起為矩陣變換密碼。 Playfair密碼2、密碼學(xué)發(fā)展的三個(gè)階段 Playfair密碼 將明文中的雙字母組合作為一個(gè)單元

5、對待，并將這些單元轉(zhuǎn)換為密文的雙字母組合。采用55變換矩陣，如以CIPHER作密鑰：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, rb BF 同列取下邊: dm MT, bs SP 其他取交叉: kt MQ, od TR2、密碼學(xué)發(fā)展的三個(gè)階段 Playfair密碼分析： 有2626=676種字母對組合 字符出現(xiàn)幾率一定程度上被均勻化 基于字母頻率的攻擊比較困難 依然保留了相當(dāng)?shù)慕Y(jié)構(gòu)信息2、密碼學(xué)發(fā)展的三個(gè)階段 代替密碼（su

6、bstitution cipher） 置換密碼（permutation cipher） 又稱換位密碼（transposition cipher) 明文的字母保持相同，但順序被打亂了。2、密碼學(xué)發(fā)展的三個(gè)階段 換位密碼（transposition cipher) 換位密碼把明文按列寫入，按行讀出 密鑰包含3方面信息: 行寬, 列高, 讀出順序密鑰密鑰:4 3 1 2 5 6 7明文明文:a t t a c k po s t p o n ed u n t i l tw o a m x y z密文：密文： TTNA APTM TSUO AODW COIX PETZ2、密碼學(xué)發(fā)展的三個(gè)階段 19491

7、975年 傳統(tǒng)密碼 計(jì)算機(jī)使得基于復(fù)雜計(jì)算的密碼成為可能 Shannon, The Comm Theory of Secret Systems, 1949 David Kahn, The Codebreakers, 1967 J.L.Smith, A Cryptographic Device for Data Comm, 1971 H.Feistel, Cryptography and Computer Privacy, 1973 數(shù)據(jù)的安全基于密鑰而不是算法的保密2、密碼學(xué)發(fā)展的三個(gè)階段 加密通信模型HelloHelloHello2、密碼學(xué)發(fā)展的三個(gè)階段 加密通信模型HelloHello加密

8、機(jī)解密機(jī)#$&#$&#$&密鑰源安全信道安全信道2、密碼學(xué)發(fā)展的三個(gè)階段 1976年以后 現(xiàn)代密碼 Diffie, Hellman. New Directions in Cryptography, 1976 1977年Rivest,Shamir & Adleman提出了RSA公鑰算法 90年代逐步出現(xiàn)橢圓曲線等其他非對稱算法 非對稱密碼使得無密鑰傳輸?shù)谋Ｃ芡ㄐ懦蔀榭赡埽?對稱密鑰密碼算法進(jìn)一步發(fā)展 1977年DES加密算法正式成為標(biāo)準(zhǔn) 90年代RC6, MARS, Twofish, Serpent等加密算法出現(xiàn) 2001年Rijndael算法成為DES的替代者B

9、的公開密鑰的公開密鑰2、密碼學(xué)發(fā)展的三個(gè)階段 非對稱密碼加密通信模型HelloHello加密機(jī)解密機(jī)#$&#$&#$&公開密鑰庫B的私人密鑰的私人密鑰3、基礎(chǔ)知識和基本術(shù)語 問題的描述 發(fā)送者(Sender)把消息(Message)傳遞給接收者(Receiver)，他想確保除接收者以外的任何人都不能閱讀發(fā)送的消息。 消息的內(nèi)容被稱為明文(Plaintext)，用某種方法偽裝消息以隱藏其內(nèi)容的過程成為加密(Encrypt)或譯成密碼(Encipher) 被加密的消息成為密文(Ciphertext)，而把密文還原為明文的過程稱為解密(Decrypt)或解譯密碼(Deciph

10、er)。3、基礎(chǔ)知識和基本術(shù)語 密碼學(xué)(Cryptology) 是研究信息系統(tǒng)安全保密的科學(xué)。是數(shù)學(xué)的一個(gè)分支，包括密碼編碼學(xué)和密碼分析學(xué)。 密碼編碼學(xué)(Cryptography) 主要研究對信息進(jìn)行編碼，實(shí)現(xiàn)對信息的隱蔽。 密碼分析學(xué)(Cryptanalytics) 主要研究加密消息的破譯或消息的偽造。3、基礎(chǔ)知識和基本術(shù)語 密碼算法(Cryptography Algorithm) 是用于加密和解密的數(shù)學(xué)函數(shù)。 密碼員對明文進(jìn)行加密操作時(shí)所采用的一組規(guī)則稱作加密算法(Encryption Algorithm)。 接收者對密文解密所采用的一組規(guī)則稱為解密算法(Decryption Algori

11、thm)。3、基礎(chǔ)知識和基本術(shù)語 密碼算法的數(shù)學(xué)表達(dá) 明文用M或P表示，密文用C表示，加密函數(shù)E作用于M得到C，數(shù)學(xué)公式表示為：E(M) = C 相反地，解密函數(shù)D作用于C產(chǎn)生MD(C) = M 如果使用了密鑰K，則可表示為：EK(M) = C; DK(C) = M3、基礎(chǔ)知識和基本術(shù)語 密碼系統(tǒng)（密碼體制）的數(shù)學(xué)描述 它是一個(gè)五元組（P, C, K, E, D）滿足條件：（1）P是可能明文的有限集；（明文空間）（2）C是可能密文的有限集；（密文空間）（3）K是一切可能密鑰構(gòu)成的有限集；（密鑰空間）（4）E是加密算法的有限集，D是解密算法的有限集（5）對任意的kK，有一個(gè)加密算法ekE和相應(yīng)的

12、解密算法dkD，使得ek: P-C 和dk: C-P分別為加密解密函數(shù)，滿足dk(ek(x)=x，這里xP。4、密碼算法的分類 按照明文的處理方法可分為分組密碼(block cipher)和流密碼(stream cipher) 分組密碼將明文分成固定長度的組塊，用同一密鑰和算法對每一塊加密，每塊輸出也是固定長度的密文。 流密碼又稱序列密碼。序列密碼每次加密一位或一字節(jié)的明文，是手工和機(jī)械密碼時(shí)代的主流。4、密碼算法的分類 按照保密的條件可分為受限制的（Restricted）算法和基于密鑰（key-based）的算法 如果加脫密的保密性是基于保持算法的秘密，這種算法稱為受限制的算法。 缺陷：無法

13、用于大的或經(jīng)常變換的用戶組織。 如果加脫密的保密性是基于保持密鑰的秘密，而算法本身可以完全公開，則稱為基于密鑰的算法?；诿荑€的算法通常有兩類：對稱算法和公開密鑰算法。4、密碼算法的分類 對稱算法(Symmetric Algorithm)就是加密密鑰和解密密鑰相同或能相互推導(dǎo)的密碼算法。 秘密密鑰算法或單密鑰算法，要求發(fā)送者和接收者在安全通信之前，商定一個(gè)密鑰。 對稱算法的安全性完全依賴于密鑰，加密和解密表示為：EK(M) = CDK(C) = M4、密碼算法的分類 公開密鑰算法(Public Key Algorithm)就是加密密鑰和解密密鑰無法相互推導(dǎo)（至少在假定的長時(shí)間內(nèi)）的密碼算法。

14、加密密鑰可以公開，任何人能用加密密鑰加密信息，但只有相應(yīng)的解密密鑰才能解密信息。這里，加密密鑰叫做公開密鑰(Public Key)，用PuK表示EPuK(M) = C 解密密鑰不可公開，只為解密者(接收方)個(gè)人所持有，因此叫做私人密鑰(Private Key)或秘密密鑰，用PrK表示DPrK(C) = M4、密碼算法的分類 有些算法用私人密鑰加密而用公開密鑰解密，這種算法通常叫數(shù)字簽名算法，可以表示為：EPrK(M) = CDPuK(C) = M5、密碼分析方法 密碼分析學(xué)是在不知道密鑰的情況下，恢復(fù)出明文的科學(xué)。 分析者是在已知密碼體制（密碼算法及其實(shí)現(xiàn)的全部詳細(xì)資料）的前提下來破譯使用的密

15、鑰。 常用的密碼分析攻擊有四類5、密碼分析方法 四類常用的密碼分析攻擊方式 唯密文攻擊(Ciphertext-only Attack) 分析者有一些消息的密文，這些密文都用同一加密算法加密，任務(wù)是盡可能恢復(fù)這些密文，或推算出加密的密鑰。 已知明文攻擊(Known-plaintext Attack) 分析者不但有一些消息的密文，還知道這些密文對應(yīng)的明文，任務(wù)是推算出加密的密鑰，或推導(dǎo)出可以對新密文進(jìn)行解密的算法5、密碼分析方法 四類常用的密碼分析攻擊方式 選擇明文攻擊(Chosen-plaintext Attack) 分析者可獲得對加密機(jī)的暫時(shí)訪問，因此他能自由選擇明文串并構(gòu)造出相應(yīng)的密文串，任

16、務(wù)是推算出加密的密鑰，或推導(dǎo)出可以對新密文進(jìn)行解密的算法 選擇密文攻擊(Chosen-ciphertext Attack) 分析者可獲得對解密機(jī)的暫時(shí)訪問，因此他能自由選擇密文串并構(gòu)造出相應(yīng)的明文串，任務(wù)是推算出加密的密鑰，或推導(dǎo)出可以對新密文進(jìn)行解密的算法6、密碼算法的安全性 無條件安全（Unconditionally secure）： 無論破譯者有多少密文，他也無法解出對應(yīng)的明文，即使他解出了，他也無法驗(yàn)證結(jié)果的正確性。 唯一的算法是一次一密亂碼本（One-time pad）6、密碼算法的安全性 一次一密亂碼本是一個(gè)大的、不重復(fù)的真隨機(jī)密鑰字母集，每個(gè)密鑰字母加密一個(gè)明文字母，每個(gè)密鑰僅對

17、消息使用一次。使用過的密鑰銷毀。 (PiKi) mod 26 = Ci 接收者有一個(gè)同樣的密鑰字母集，每個(gè)密鑰字母脫密一個(gè)密文字母，使用過的密鑰銷毀。 (CiKi) mod 26 = Pi6、密碼算法的安全性 一次一密亂碼本使用過程發(fā)送者接收者+-亂碼本亂碼本亂碼本亂碼本6、密碼算法的安全性 一次一密亂碼本存在的問題 密鑰必須隨機(jī)，不能重復(fù)使用。 無法在高帶寬的信道上使用。 1M帶寬上通信24小時(shí)就需要90G的亂碼本 必須保證發(fā)送者和接收者完全同步 不提供鑒別6、密碼算法的安全性 計(jì)算上安全（Computationally secure）： 破譯的代價(jià)超出信息本身的價(jià)值 破譯的時(shí)間超出了信息的

18、有效期 用窮舉法破解129位DES算法，平均需要2128次攻擊嘗試，以每秒100萬次攻擊嘗試，用100萬臺PC并行處理，需要花費(fèi)1019年（宇宙年齡的10億倍）7、密碼學(xué)相關(guān)基礎(chǔ)數(shù)學(xué) 模運(yùn)算 生活中的求模運(yùn)算： 現(xiàn)在是3點(diǎn)鐘，25小時(shí)以后是幾點(diǎn)鐘？52小時(shí)以后呢？ (52+3)24余7，52小時(shí)后應(yīng)該是7點(diǎn)鐘 今天是星期二，9天以后是星期幾？90天以后呢？ (90+2)7余5，90天以后應(yīng)該是星期五7、密碼學(xué)相關(guān)基礎(chǔ)數(shù)學(xué) 模運(yùn)算和同余 給定任意整數(shù)a和q，以q除a，余數(shù)是r，則可以表示為a=sq+r, 0rq。 稱q為模數(shù)，r為a模q的剩余，記為 ra mod q 若整數(shù)a和b有(a mod

19、q)=(b mod q)，則稱a與b在模q下同余。(即a和b的差是q的倍數(shù)) 例如11和19在模4下同余(3)。7、密碼學(xué)相關(guān)基礎(chǔ)數(shù)學(xué) 模的逆元 求a對于模b的逆元，即求x滿足ax mod b 1 ，可記做 x a-1 mod b 或 a x-1 mod b 如： 39 1 26 1 ，則稱9和3對于模26互逆，記做9-1 mod 26 = 3或3-1 mod 26 = 9 將模數(shù)的倍數(shù)加1后分解為兩個(gè)數(shù)的乘法，即可得到兩個(gè)關(guān)于模數(shù)互逆的數(shù)。7、密碼學(xué)相關(guān)基礎(chǔ)數(shù)學(xué) 模運(yùn)算舉例 14342, 2是14模4的余，214 mod 4 （2也是14模3的余） 通常對rq的條件并不嚴(yán)格要求，如 1934

20、7，7 19 mod 4 負(fù)數(shù)亦可參與求模（保證余數(shù)大于零即可) (-13)(-4)43，3 (-13) mod 4 7(-3)419，19 7 mod 4 1(-1)1112， 12 1 mod 117、密碼學(xué)相關(guān)基礎(chǔ)數(shù)學(xué) 模運(yùn)算的基本性質(zhì)： 若q|(a-b)，則ba mod q。如113能被4整除，則3是11模4的余； (a mod q)=(b mod q)意味著ab mod q。如3 mod 4 = 11 mod 4，則3是11模4的余； ab mod q等價(jià)于ba mod q。如3是11模4的余，同時(shí)4是11模3的余； 若ab mod q且bc mod q，則ac mod q。如37

21、mod 4且711 mod 4，則311 mod 4 模運(yùn)算滿足交換律、分配律、結(jié)合律7、密碼學(xué)相關(guān)基礎(chǔ)數(shù)學(xué) 模算術(shù)（不要求rq） 加法：(a mod q)(b mod q) = (ab) mod q例：(3 mod 4)(7 mod 4) = 6 = 10 mod 4 乘法：(a mod q)(b mod q) = (ab) mod q例：(3 mod 4)(7 mod 4) = 9 = 21 mod 4 指數(shù)：an mod q = an-1 mod q a mod qamn mod q = (am mod q)n7、密碼學(xué)相關(guān)基礎(chǔ)數(shù)學(xué) 為什么引入模運(yùn)算 模運(yùn)算可將很大的數(shù)變成較小的數(shù)，同時(shí)

22、保持?jǐn)?shù)的某些周期性的性質(zhì)不變 比如1和32085在26下同余，都可以表示字母B 密碼運(yùn)算涉及指數(shù)、對數(shù)等大數(shù)的運(yùn)算，模運(yùn)算將運(yùn)算的數(shù)值始終限定在一定范圍內(nèi)，利于計(jì)算機(jī)快速處理7、密碼學(xué)相關(guān)基礎(chǔ)數(shù)學(xué) 位的異或運(yùn)算 0 0=0, 0 1=1, 1 01, 1 1=0 特性：兩次異或運(yùn)算以后還原，可設(shè)計(jì)加密和脫密完全相同的函數(shù)。 1918年，弗納姆(Vernam)密碼采用二進(jìn)制數(shù)據(jù)： 加密：Ci = Pi Ki 解密：Pi = Ci Ki7、密碼學(xué)相關(guān)基礎(chǔ)數(shù)學(xué) 素?cái)?shù)（質(zhì)數(shù)）及其特性 大于1、只能被1和自己整除的數(shù)：如2、3、5、2521、2365347734339、27568391 公開密鑰密碼學(xué)常

23、用大的素?cái)?shù)（512位或1024位） 512位的數(shù)以內(nèi)，有超過10151個(gè)素?cái)?shù) 費(fèi)爾馬小定理 如果m是一個(gè)素?cái)?shù)，且a不是m的倍數(shù)，那么有： am-1 1 mod m 推論: m是素?cái)?shù)，a是任意整數(shù),則: am mod m a8、模運(yùn)算用于數(shù)據(jù)加密 字母編碼表，將字母AZ對應(yīng)于數(shù)字0258、模運(yùn)算用于數(shù)據(jù)加密 移位密碼 定義加密函數(shù)為E(x)=(x + a) mod 26 = y 解密函數(shù)則為D(y)=(ya) mod 26 = x 當(dāng)a=3時(shí)，即為愷撒密碼 對移位密碼的攻擊最多嘗試25次8、模運(yùn)算用于數(shù)據(jù)加密 移位密碼舉例 已知移位密碼加密函數(shù)為E(x)=(x + 5) mod 26，試加密明文TODAY 解答：TODAY可編碼為19 14 3 0 24，經(jīng)過加密函數(shù)運(yùn)算可得24 19 8 5 3，即對應(yīng)于密文字符YTIFD8、模運(yùn)算用于數(shù)據(jù)加密 維吉尼亞（Vigenere）密碼 是一種多表移位代替密碼。密鑰由序列K(k1, k2, , kd)給定，第i+td個(gè)明文字母由密鑰ki決定： Ek(xi+td) = (xi+td+ki) mod 26 = yi+td Dk(yi+td) = (yi+td-ki) mod 26 = xi+td 當(dāng)K的長度和X一樣時(shí)，就成為滾動(dòng)密鑰密碼 當(dāng)K永遠(yuǎn)不重復(fù)時(shí)，就是一次一密亂碼本8、模運(yùn)算用于數(shù)據(jù)加密