密碼編碼學與網(wǎng)絡安全(第五版)向金海02古典密碼算法課件

1、Chapter 2 傳統(tǒng)加密技術本章要點密碼學基本概念古典/傳統(tǒng)密碼體制代替/代換技術：凱撒密碼、單表代換密碼、Playfair密碼、Hill密碼、多表代替密碼；置換技術：柵欄技術轉輪密碼 隱寫術 *2基本概念密碼學： 研究如何進行秘密通信或保密通信的科學 密碼編碼學：對信息進行編碼，實現(xiàn)信息保密性 密碼分析學：研究、分析、破譯密碼*3*4密碼學的發(fā)展歷史 第1階段：1949年以前； 第2階段：從1949年到1975年； 標志：1949年Shannon發(fā)表保密系統(tǒng)的信息理論一文；第3階段：1976年至今。 標志：1976年Diffie和Hellman發(fā)表密碼學新方向一文。*5基本術語明文，pl

2、aintext - original message 密文，ciphertext - coded message 密碼體制，密碼，cipher - algorithm for transforming plaintext to ciphertext 密鑰，key - info used in cipher known only to sender/receiver 加密，encipher (encrypt) - converting plaintext to ciphertext 解密，decipher (decrypt) - recovering plaintext from ciphert

3、ext*6密碼編碼學Cryptography研究內(nèi)容主要研究對信息進行編碼，實現(xiàn)對信息的隱蔽。特征運算類型：代換與置換所用的密鑰數(shù)：單鑰與雙鑰處理明文的方法：分組密碼與流密碼*7密碼算法分類按照保密內(nèi)容受限制的（restricted）算法：算法的保密性基于保持算法的秘密；基于密鑰的（key-based）算法：算法的保密性基于對密鑰的保密基于密鑰的算法，按照密鑰特點對稱密碼算法（傳統(tǒng)密碼算法或單鑰密碼算法）非對稱算法（公開鑰密碼算法或雙鑰密碼算法）按照明文處理方式分組密碼流密碼*8安全要求加密算法必須足夠強最低要求：已知密文時不能破譯該密文或由密文推導出密鑰；加強形式：已知某些明、密文對，也不能

4、由此破譯出新的密文或發(fā)現(xiàn)密鑰。算法是基于密鑰的：通信雙方必須在某種安全形式下獲得密鑰并必須保證密鑰的安全*9密碼分析學Cryptanalysis密碼破譯攻擊的一般方法密碼分析學： cryptanalytic attack窮舉攻擊： brute-force attack*10基于密碼分析的攻擊Cryptanalytic Attacks惟密文攻擊，ciphertext only only know algorithm & ciphertext, is statistical, know or can identify plaintext 已知明文攻擊，known plaintext know/su

5、spect plaintext & ciphertext選擇明文攻擊，chosen plaintext select plaintext and obtain ciphertext選擇密文攻擊，chosen ciphertext select ciphertext and obtain plaintext選擇文本攻擊，chosen text select plaintext or ciphertext to en/decrypt*11兩個概念絕對安全，Unconditional Security 計算安全，Computational Security 19世紀，Kerckhoff原則： 系統(tǒng)的

6、保密性不依賴于對加密體制或算法的保密，而依賴于對密鑰的保密。*12窮舉攻擊Key Size (bits)Number of Alternative KeysTime required at 1 decryption/sTime required at 106 decryptions/s32232 = 4.3 109231 s = 35.8 minutes2.15 milliseconds56256 = 7.2 1016255 s = 1142 years10.01 hours1282128 = 3.4 10382127 s = 5.4 1024 years5.4 1018 years16821

7、68 = 3.7 10502167 s = 5.9 1036 years5.9 1030 years26 characters (permutation)26! = 4 10262 1026 s= 6.4 1012 years6.4 106 years*13非技術因素的攻擊偷竊收買逼問*142.1 對稱密碼的模型傳統(tǒng)密碼/常規(guī)密碼/私鑰密碼/單鑰密碼conventional / private-key / single-key發(fā)送方和接收方共享一個共同的密鑰sender and recipient share a common key所有的傳統(tǒng)密碼算法都是私鑰密碼20世紀70年代以前私鑰密碼是

8、唯一類型至今仍廣泛應用*15對稱密碼模型（Symmetric Cipher Model）*16對稱密碼安全的兩個必備條件:加密算法必須是足夠強的a strong encryption algorithm惟有發(fā)送者和接收者知道的秘密密鑰a secret key known only to sender / receiver數(shù)學表示:C = EK(P) P = DK(C)假設加/解密算法是已知的擁有一個安全通道用于分發(fā)密鑰*17*182.2 古典代替密碼將明文字母替換成其他字母、數(shù)字或符號的方法;如果把明文看成是0或1的序列，那么密文就是0或1比特序列的另一種表達。*192.2.1 愷撒密碼 Ca

9、esar Cipher所知道的最早的代替密碼Julius Caesar 首先用在軍事通信中用字母后的第三個字母代替明 文abcdefghijklmnopqrstuvwxyz密 文DEFGHIJKLMNOPQRSTUVWXYZABC*20愷撒密碼 - 加密方式一：公式計算明文編碼： 如a=0，b=1，z=25，則 明文P p1p2pn（加密）運算：Ci pi + k （mod 26）, i 1,2,n解碼得密文：C c1cc2cn*21愷撒密碼-加密方式二：查表（例k=3）明 文abcdefghijklmnopqrstuvwxyz密 文DEFGHIJKLMNOPQRSTUVWXYZABC*22愷

10、撒密碼 - 解密方式一：公式計算密文C c1c2cn（加密）運算：Pi ci - k （mod 26）, i1,2,n解碼得明文： P p1p2pn*23愷撒密碼-解密方式二：查表（例k=3）密文ABCDEFGHIJKLMNOPQRSTUVWXYZ明文xyzabcdefghijklmnopqrstuvw*24愷撒密碼c = E(p) = (p + k) mod (26)p = D(c) = (c k) mod (26)*25愷撒密碼的密碼分析 共有密鑰25個 可簡單地依次去測試 、強力搜索、窮舉攻擊 基于字母頻率的破譯方法所破譯的明文需要識別如：破譯密文 GCUA VQ DTGCM“ dzrx

11、 sn aqdzj （k=3） easy to break （k=2）密鑰短語密碼就是選一個英文短語作為密鑰字(Key Word)或密鑰短語(Key Phrase)，如HAPPY NEW YEAR，去掉重復字母得HAPYNEWR。將它依次寫在明文字母表之下，而后再將字母表中未在短語中出現(xiàn)過的字母依次寫于此短語之后，就可構造出一個字母代換表。*262.2.2 單表代替密碼若明文為：P = Casear cipher is a shift substitution則密文為：C=PHONHM PBKRNM BOH ORBEQ OSAOQBQSQBJI*27*28單表代替密碼分析不是簡單有序地字母移位

12、 任意地打亂字母的順序 每個明文字母映射到一個不同的隨機密文字母 密鑰數(shù)目： 26！ *29單表代替密碼分析密鑰空間： 26! 4 x 1026 貌似安全，實則不然 語言特性*30語言的冗余與密碼分析人類的語言是有冗余的 字母的使用頻率是不同的在英語中E使用的頻率最高 有些字母使用較少單字母、雙字母、三字母組合統(tǒng)計*31英語字母使用頻率*322.2.1 Playfair密碼單表代替密碼由于密鑰空間較小所以無法提供安全性；Playfair密碼是一個多表代替密碼 ；Charles Wheatstone 于1854年發(fā)明, 用其朋友Baron Playfair 命名。*33Playfair密鑰矩陣

13、5 X 5 填寫密鑰單詞用其他字母填寫剩下的空缺I = JMONARCHYBDEFGI/JKLPQSTUVWXZ*34加密明文分組（填充）：2個字母組同行字母對加密：循環(huán)向右，eiFK同列字母對加密：循環(huán)向下，cuEM，xiAS其它字母對加密：矩形對角線字母，且按行排序，yaBN，esIL（或JL）解密加密的逆向操作Playfair密碼的加/解密步驟*35Playfair密碼安全性分析安全性優(yōu)于單表代替密碼密鑰空間：25！1.61025在WW1（一戰(zhàn)）中使用多年雖然明文中字母的統(tǒng)計規(guī)律在密文中得到了降低，但密文中仍含有明文的部分結構信息給定幾百個字母，即可被攻破明、密文字母不是一一對應關系*3

14、6字母出現(xiàn)的相對頻率*372.2.4 希爾(Hill)密碼萊斯特S希爾（Lester S. Hill，18911961），美國數(shù)學家、教育家。1911年于哥倫比亞大學讀完學士學位，1926年在耶魯大學讀完博士學位，于1929年發(fā)明希爾密碼。是多表代替密碼利用模運算意義下的矩陣乘法、求逆矩陣、線性無關、線性空間與線性變換等概念和運算 *38Hill密碼的加/解密過程明文分組并編碼CKP mod 26，其中，K為密鑰矩陣，P、C分別為明、密文分組加密:解密:密文分組并編碼PK-1C mod 26 對密鑰矩陣K的要求：在mod 26下可逆*39密鑰矩陣K明文分組P“mor”明文編碼 P加密 C mo

15、d 26解碼 C，即C“HDL”Hill密碼的例子加密：K1*40密鑰矩陣K明文P“mor”明文 P解密 P mod 26CC“HDL”Hill密碼的例子解密：K1*41Hill密碼的特點字母的統(tǒng)計規(guī)律進一步降低明、密文字母不是一一對應關系*422.2.5 多表代替密碼Polyalphabetic Ciphers特點：在明文消息中采用不同的單表代換。安全性提高 使得字母的頻率分布更加平坦用一個密鑰指示明文消息中每個字母加解密時所用的代替表密鑰依次重復使用，代替表依次重復使用 例子：Vigenre（維吉利亞）密碼（1858）Vernam（唯爾南）密碼（1918）*43一、 Vigenre（維吉利

16、亞）密碼方式一：數(shù)學公式計算設明文 P = p1p2pn，密鑰 k = k1k2kn，密文C = c1c2cn 明文編碼； 計算 ci= pi+ki (mod 26)，=1，2，n； 密文解碼。說明：若明文長度大于n，則K重復使用。加密:*44方式二：查表法一、 Vigenre（維吉利亞）密碼*45一、 Vigenre（維吉利亞）密碼方法一：數(shù)學公式計算pi = ciki (mod 26)，=1，2，n；方法二：查表解密：*46Vigenre密碼例子加密過程：P“encode and decode”，k“mykey”字母序號123456789101112131415明文編碼P =4132143

17、401333421434密鑰編碼k =122410424122410424122410424加密C =1637121827162423727162624728模運算111102密文解碼C =QLMSBQYXHBQAYHB*47Vigenre密碼例子解密過程：C“QLMSBQYXHBQAYHB”，k“mykey”字母序號123456789101112131415密文編碼C=161112181162423711602472密鑰編碼k=122410424122410424122410424加密C=4-13214-2340133-234-24143-22模運算133324密文解碼C=encodeand

18、decode*48Vigenre密碼的安全性密鑰空間：|K|26n字母的統(tǒng)計規(guī)律進一步降低明、密文字母不是一一對應關系Vigenre本人建議：密鑰與明文一樣長特例：當k1 k2 kn k時，是Caesar密碼*492.2.6 一次一密隨機密鑰理論上不可破實際上不可行產(chǎn)生大量的隨機密鑰難密鑰分配與保護更難*50柵欄技術思想：以列（行）優(yōu)先寫出明文，以行（列）優(yōu)先讀出各字母作為密文例1：先行后列例2：先列后行改 進帶有密鑰再改進：重復加密，多步置換2.3 置換密碼Transposition Ciphers*51例：柵欄密碼(Rail Fence cipher)明文：meet me after the toga party寫作:m e m a t r h t g p r y e t e f e t e o a a t讀出密文為：MEMATRHTGPRYETEFETEOAAT柵欄技術：按對角線的順序寫出明文，以行的順序讀出作為密文密文消息 “MEMATEAKETETHPR”無密鑰的置換技術Example明文消息 “Meet me at the park”帶密鑰的置換技術置換操作中的加密密鑰和解密密鑰同一個密鑰在加密和解密（列置換）過程中，以不同的方向來使用在加解密過程中好像使用的是兩個不同的密鑰2. 帶密鑰的置換技術