密碼學(xué)基礎(chǔ)(古典密碼 素材).ppt

1、BG,1,古典密碼算法 2015-6-9,BG,2,提 綱,概述 單表代換算法 單符號代換算法 凱撒密碼 移位密碼 單表密碼 短語密碼 仿射密碼 攻擊方法 小結(jié),BG,3,當(dāng)今的信息網(wǎng)絡(luò)蘊(yùn)含了表現(xiàn)為信息形式的多種巨大利益 政治的、軍事的、經(jīng)濟(jì)的、商業(yè)的 通過網(wǎng)絡(luò)非法獲取和利用信息可能隨時發(fā)生 互聯(lián)網(wǎng)的開放性是根源 網(wǎng)絡(luò)安全已成為網(wǎng)絡(luò)設(shè)計、建設(shè)和維護(hù)的重要內(nèi)容 密碼學(xué)/密碼算法成為保護(hù)網(wǎng)絡(luò)信息的利器 以數(shù)學(xué)為工具，將信息明文變換為密文 成為保護(hù)信息的核心屏障,網(wǎng)絡(luò)與密碼算法,BG,4,密碼學(xué)的目的 合法通信雙方Alice和Bob在不安全的信道上進(jìn)行安全通信，而破譯者Oscar不能理解他們通信的內(nèi)

2、容 “安全”指機(jī)密性、完整性、鑒別、不可抵賴 簡單加密系統(tǒng)模型,簡單加密系統(tǒng)模型,BG,5,密碼系統(tǒng) 包含帶參數(shù) K 的變換EK() 、帶參數(shù) K 的逆變換DK() 、信息傳送信道、密鑰傳送信道 變換EK得將明文消息P變換為密文C，這個過程稱為加密 E為加密算法，K為密鑰。E不同或K不同，密文C就不同 典型的密碼系統(tǒng),密碼系統(tǒng),BG,6,對密碼算法的基本要求 加密能力強(qiáng) 當(dāng)密文或明文密文對被截獲時，破解密鑰或明文在計算上是不可行的 安全性不依賴于密碼算法本身的保密，而依賴于密鑰 易于實(shí)現(xiàn)，使用方便,對密碼算法的基本要求,BG,7,古典密碼（Classical Cryptography） 密碼算

3、法針對的基本操作對象是字符/字母 方法字符代換（Substitution）或字符置換（Permutation） 1949年之前 此類密碼學(xué)還不是科學(xué)，而是藝術(shù) 產(chǎn)生了一些密碼算法和加密設(shè)備 也出現(xiàn)簡單的密碼分析手段,古典密碼,BG,8,古典密碼分類,代換 Substitution,置換 Transposition,單表代換 Monoalphabetic ,多表代換 Polyalphabetic ,單字符單表代換,多字符單表代換,移位密碼,單表密碼,短語單表密碼,Playfair密碼,Beaufort密碼,Vigenre密碼,行變換密碼,柵格密碼,Hill密碼,仿射密碼,Autokey密碼,轉(zhuǎn)子

4、機(jī),凱撒密碼,一次性密碼,BG,9,代換與置換,代換密碼算法（Substitution Cipher） 將明文中的每一個字符均被替換成另一個字符（密文字符）。接收者對密文做反向替換就可以恢復(fù)出明文 置換密碼算法（Permutation Cipher） 又稱換位密碼算法（Transposition Cipher）：改變明文中各個字母的位置次序，但明文字母（的出現(xiàn)及出現(xiàn)次數(shù)）保持不變,BG,10,代替密碼,單表密碼算法（ Monoalphabetic Cipher) 密碼表僅 1 個固定 任何明文加密、密文解密均使用同一個密碼表加密 明文中相同的字母必然被加密成相同的密文字母,BG,11,代替密碼

5、,多表密碼算法（Polyalphabetic Cipher) 密碼表多個不固定 一條明文加密和解密同時使用多個密碼表 明文中兩個相同的字母可能被加密成不同的密文字母,BG,12,提 綱,概述 單表代換算法 單符號代換算法 凱撒密碼 移位密碼 單表密碼 短語密碼 仿射密碼 攻擊方法 小結(jié),BG,13,凱撒密碼,愷撒密碼（Caesar Cipher） Julius Caesar 發(fā)明，是已知最早的代換密碼 明文字母用其后的第三個字母代替，作為其密文字母，即，將明文字母表循環(huán)左移三位作為密碼表,BG,14,兩個字母表 明文字母表 Pp0, p1, , p25 密文字母表 CC0, C1, , C25

6、 基本型凱撒密碼等于如下變換 明文字母表 密文字母表 明文表和密文表共同構(gòu)成密鑰 加密 解密,凱撒密碼,BG,15,讓每個字母對應(yīng)一個數(shù)值 則基本型凱撒密碼可以表示為 加密： Ci = E(pi) = (pi+3) mod 26 解密： pi = D(Ci) = (Ci3) mod 26 密鑰數(shù)量：1,凱撒密碼,BG,16,凱撒密碼,凱撒密碼 實(shí)例 明文： meet me after the party 密文： PHHW PH DIWHU WKH SDUWB,BG,17,凱撒密碼,特點(diǎn) 極為簡單 密鑰數(shù)為1，極其脆弱,BG,18,提 綱,概述 單表代換算法 單符號代換算法 凱撒密碼 移位密碼

7、單表密碼 短語密碼 仿射密碼 攻擊方法 小結(jié),BG,19,移位密碼（Shift Cipher） 明文字母用其后的第 k 個字母代替，作為其密文字母，即，將明文字母表循環(huán)左移 k 位作為密碼表 明文字母用任一個密文字母代替，即， 明文字母表的任一個排列均構(gòu)成一個對應(yīng)的密碼表 加密： Ci = E(pi) = (pi+k) mod 26 解密： pi = D(Ci) = (Cik) mod 26,移位密碼,BG,20,移位密碼,移位密碼,BG,21,例如，k = 5 明文字母表： 密文字母表： 密鑰數(shù)量：25,明文,密文,移位密碼,BG,22,特點(diǎn) 非常簡單 密鑰數(shù)為25，仍非常脆弱,移位密碼,B

8、G,23,提 綱,概述 單表代換算法 單符號代換算法 凱撒密碼 移位密碼 單表密碼 短語密碼 仿射密碼 攻擊方法 小結(jié),BG,24,單表密碼（Monoalphabetic Cipher） 明文字母用任一個密文字母代替，即， 明文字母表的任一個全排列均構(gòu)成一個對應(yīng)的密碼表 加密： Ci = E(pi)=(pi+ki) mod 26 解密： pi = D(Ci)=(Ciki) mod 26 當(dāng) pipj 有 CiCj, ki, kj = 0,1,2,25 例： 明文字母表： 密文字母表： ki : 13 17 21 24 ,單表密碼,BG,25,密鑰數(shù)量： 26! = 403,291,461,12

9、6,605,635,584,000,000 41026 = 400億億億 特點(diǎn) 密鑰數(shù)極大，安全性好 密鑰無規(guī)律，使用不便,單表密碼,BG,26,提 綱,概述 單表代換算法 單符號代換算法 凱撒密碼 移位密碼 單表密碼 短語密碼 仿射密碼 攻擊方法 小結(jié),BG,27,短語密碼,短語密碼（Keyword Cipher） 是單表密碼的一種實(shí)用形式 引入一個關(guān)鍵詞（短語）來構(gòu)造明文字母表的一個排列，從而構(gòu)成對應(yīng)的密碼表 密碼表構(gòu)造方法1 指定一個關(guān)鍵詞（詞組、句子） 去除關(guān)鍵詞中的重復(fù)字母和空格，前置于密碼表 將剩余的字母依次按序后置于密碼表 密鑰數(shù)量： 26!（ 41026 = 400億億億）,B

10、G,28,實(shí)例 關(guān)鍵詞： GUANG ZHOU BAI YUN SHAN 去重前置： GUANZHOBIYS 剩余后置： TVWXCDEFJKLMPQR 明文字母表： 密文字母表：,短語密碼,BG,29,短語密碼 密碼表構(gòu)造方法2 指定一個關(guān)鍵詞，去重復(fù)、空格，按行排陣 將剩余的字母依次繼續(xù)按行排陣 陣的各列構(gòu)成密碼表 例：關(guān)鍵詞=COLLEGE 陣： 明文字母表 密文字母表,短語密碼,BG,30,提 綱,概述 單表代換算法 單符號代換算法 凱撒密碼 移位密碼 單表密碼 短語密碼 仿射密碼 攻擊方法 小結(jié),BG,31,仿射密碼,仿射密碼（Affine Cipher） 用仿射變換構(gòu)造密碼表（密碼

11、表便于記憶） 密碼表 兩個字母表 明文字母表 Pp0, p1, , pn-1 密文字母表 CC0, C1, , Cn-1 引入兩個參數(shù) 、，使明文字母 P 用字母 aP+b 代替，作為其密文字母 加密： Ci = E(pi) = (pi + ) mod n 解密： pi = D(Ci) = 1(Ci ) mod n,BG,32,仿射密碼,實(shí)例 取參數(shù) =5, =8 明文 = AFFINECIPHER 密文 = IHHWVCSWFRCP,BG,33,仿射密碼,提示 仿射加密函數(shù)要求和n互素，即gcd(, n)=1，否則， (pi + ) mod n 就不是一個單射函數(shù) 當(dāng)=1、 =3時，仿射密碼

12、就是著名的凱撒密碼 在解密時，需求解在有限域Zn上的乘法逆元1Zn，這可由擴(kuò)展歐幾里得算法求解 Z26上所有與26互素的元素的乘法逆元：,BG,34,提 綱,概述 單表代換算法 單符號代換算法 凱撒密碼 移位密碼 單表密碼 短語密碼 仿射密碼 攻擊方法 小結(jié),BG,35,對單表代換密碼的攻擊,兩種典型的攻擊 直接攻擊文本 方法頻度分析 直接攻擊密鑰 方法暴力破解（窮舉破解） 兩種攻擊聯(lián)合使用或單獨(dú)使用可一舉破解單表代換密碼,BG,36,直接攻擊文本頻度分析 9世紀(jì)阿爾-金迪:關(guān)于破譯加密信息的手稿 西文語言的獨(dú)到特征 文章中字母的出現(xiàn)頻度有統(tǒng)計規(guī)律：元音字母頻度高,對單表代換密碼的攻擊,BG,

13、37,頻度分析的步驟 統(tǒng)計密碼字母的頻度 排序 按照已知頻度分布替換密文字母,對單表代換密碼的攻擊,BG,38,密文 頻度分析 h: 可能是 e, a, i, o 嘗試 h e, d a, l i, r o, 結(jié)果 密文: 明文:,頻度分析攻擊：實(shí)例,BG,39,直接攻擊密鑰暴力破解 前提已知采用的是代換密碼 暴力破解的要點(diǎn) 嘗試所有可能的密碼表（移位密碼：最多僅需嘗試25次） 暴力破解的步驟 選擇一個密碼表 作逆代換 檢查逆代換后的文本是否有意義，有則結(jié)束，否則換另一個密碼表，進(jìn)入步驟2,對單表代換密碼的攻擊,BG,40,實(shí)例,密文,明文,對單表代換密碼的攻擊,BG,41,本質(zhì) 選取字母表的

14、一個全排列作為對稱密鑰 密鑰數(shù)量 26! （ 41026）,單表代換密碼：小結(jié),BG,42,提 綱,概述 單表代換算法 單符號代換算法 凱撒密碼 移位密碼 單表密碼 短語密碼 仿射密碼 攻擊方法 小結(jié),BG,43,特征 代換固定明文字符的代換字符固定 位置相同密文字符與明文字符的位置相同 優(yōu)點(diǎn) 簡單得到密文所需的計算量小 缺點(diǎn) 繼承密文繼承了明文的統(tǒng)計特性（頻率） 跟隨明文字符的跟隨關(guān)系反映在密文中,單字符代換算法：小結(jié),BG,44,存在多種不同的破解途徑 攻擊密文頻度分析 攻擊密鑰窮舉密鑰 改進(jìn)思路：多角度同時抵御 針對頻度分析使頻度呈現(xiàn) “均勻分布” 針對窮舉密鑰增大密鑰空間 如何做到？,代換密碼算法：如何改進(jìn)？,BG,45,如何解密用短語代換密碼的密文？ 如何代換密碼加密中文？ 對于本次給出的四種代換密碼，指出它們是沿著什么思路改進(jìn)的？,進(jìn)階問題,BG,46,生成26個字母表的一個全排列，畫出計算機(jī)程序的流程圖。 生成短語代換密碼的一個密碼表，畫出計算機(jī)程序的流程圖。 畫出用短語代換密碼加密明文和解密密文的計算機(jī)程序流程圖。 選取一個代換密碼，利用郵件、微博或微信與你的朋友進(jìn)行一次秘密通信。 請一位第三方同學(xué)嘗試破