古典密碼算法2015-6-91整理ppt提綱概述單表代換算法單符號代換算法凱撒密碼移位密碼單表密碼短語密碼仿射密碼攻擊方法小結(jié)2整理ppt當今的信息網(wǎng)絡(luò)蘊含了表現(xiàn)為信息形式的多種巨大利益政治的、軍事的、經(jīng)濟的、商業(yè)的……通過網(wǎng)絡(luò)非法獲取和利用信息可能隨時發(fā)生互聯(lián)網(wǎng)的開放性是根源網(wǎng)絡(luò)安全已成為網(wǎng)絡(luò)設(shè)計、建設(shè)和維護的重要內(nèi)容密碼學/密碼算法成為保護網(wǎng)絡(luò)信息的利器以數(shù)學為工具，將信息明文變換為密文成為保護信息的核心屏障網(wǎng)絡(luò)與密碼算法3整理ppt密碼學的目的合法通信雙方Alice和Bob在不安全的信道上進行安全通信，而破譯者Oscar不能理解他們通信的內(nèi)容“安全”指機密性、完整性、鑒別、不可抵賴簡單加密系統(tǒng)模型簡單加密系統(tǒng)模型密碼系統(tǒng)4整理ppt密碼系統(tǒng)包含帶參數(shù)K的變換EK()、帶參數(shù)K的逆變換DK()、信息傳送信道、密鑰傳送信道變換EK得將明文消息P變換為密文C，這個過程稱為加密E為加密算法，K為密鑰。E不同或K不同，密文C就不同典型的密碼系統(tǒng)密碼系統(tǒng)小游戲角色1——如何給你的朋友發(fā)一封由你自己加密的電子郵件？角色2——如何解密你朋友給你發(fā)來的加密郵件？5整理ppt對密碼算法的基本要求加密能力強當密文或明文－密文對被截獲時，破解密鑰或明文在計算上是不可行的安全性不依賴于密碼算法本身的保密，而依賴于密鑰易于實現(xiàn)，使用方便對密碼算法的基本要求6整理ppt古典密碼（ClassicalCryptography）密碼算法針對的基本操作對象是字符/字母方法——字符代換（Substitution）或字符置換（Permutation）1949年之前此類密碼學還不是科學，而是藝術(shù)產(chǎn)生了一些密碼算法和加密設(shè)備也出現(xiàn)簡單的密碼分析手段古典密碼7整理ppt古典密碼分類代換Substitution置換Transposition單表代換Monoalphabetic~多表代換Polyalphabetic~單字符單表代換多字符單表代換移位密碼單表密碼短語單表密碼Playfair密碼Beaufort密碼Vigenère密碼行變換密碼柵格密碼Hill密碼仿射密碼Autokey密碼轉(zhuǎn)子機凱撒密碼一次性密碼8整理ppt代換與置換代換密碼算法（SubstitutionCipher）將明文中的每一個字符均被替換成另一個字符（密文字符）。接收者對密文做反向替換就可以恢復(fù)出明文置換密碼算法（PermutationCipher）又稱換位密碼算法（TranspositionCipher）：改變明文中各個字母的位置次序，但明文字母（的出現(xiàn)及出現(xiàn)次數(shù)）保持不變

9整理ppt代替密碼單表密碼算法（MonoalphabeticCipher)密碼表僅1個——固定任何明文加密、密文解密均使用同一個密碼表加密明文中相同的字母必然被加密成相同的密文字母10整理ppt代替密碼多表密碼算法（PolyalphabeticCipher)密碼表多個——不固定一條明文加密和解密同時使用多個密碼表明文中兩個相同的字母可能被加密成不同的密文字母11整理ppt提綱概述單表代換算法單符號代換算法凱撒密碼移位密碼單表密碼短語密碼仿射密碼攻擊方法小結(jié)12整理ppt凱撒密碼愷撒密碼（CaesarCipher）JuliusCaesar發(fā)明，是已知最早的代換密碼明文字母用其后的第三個字母代替，作為其密文字母，即，將明文字母表循環(huán)左移三位作為密碼表13整理ppt兩個字母表明文字母表 P＝{p0,p1,…,p25}密文字母表 C＝{C0,C1,…,C25}基本型凱撒密碼等于如下變換明文字母表密文字母表明文表和密文表共同構(gòu)成密鑰加密

解密凱撒密碼14整理ppt讓每個字母對應(yīng)一個數(shù)值

則基本型凱撒密碼可以表示為加密： Ci=E(pi)=(pi+3)mod26解密： pi=D(Ci)=(Ci3)mod26密鑰數(shù)量：1凱撒密碼15整理ppt凱撒密碼凱撒密碼實例明文： meetmeaftertheparty密文： PHHWPHDIWHUWKHSDUWB16整理ppt凱撒密碼特點極為簡單密鑰數(shù)為1，極其脆弱17整理ppt提綱概述單表代換算法單符號代換算法凱撒密碼移位密碼單表密碼短語密碼仿射密碼攻擊方法小結(jié)18整理ppt移位密碼（ShiftCipher）明文字母用其后的第k個字母代替，作為其密文字母，即，將明文字母表循環(huán)左移k位作為密碼表明文字母用任一個密文字母代替，即，

明文字母表的任一個排列均構(gòu)成一個對應(yīng)的密碼表加密： Ci=E(pi)=(pi+k)mod26解密： pi=D(Ci)=(Cik)mod26移位密碼19整理ppt移位密碼移位密碼20整理ppt例如，k=5明文字母表：密文字母表：密鑰數(shù)量：25明文密文移位密碼21整理ppt特點非常簡單密鑰數(shù)為25，仍非常脆弱移位密碼22整理ppt提綱概述單表代換算法單符號代換算法凱撒密碼移位密碼單表密碼短語密碼仿射密碼攻擊方法小結(jié)23整理ppt單表密碼（MonoalphabeticCipher）明文字母用任一個密文字母代替，即，

明文字母表的任一個全排列均構(gòu)成一個對應(yīng)的密碼表加密： Ci=E(pi)=(pi+ki)mod26解密： pi=D(Ci)=(Ciki)mod26

當pipj

有CiCj,ki,kj=0,1,2,…25例：明文字母表：密文字母表： ki

:

13172124……單表密碼abcdefghijklmnopqrstuvwxyzNSXCHMRWBGLQVAFKPUZEJOTYDI24整理ppt密鑰數(shù)量：26!=403,291,461,126,605,635,584,000,000

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

GUANGZHOUBAIYUNSHAN去重前置：

GUANZHOBIYS剩余后置： TVWXCDEFJKLMPQR明文字母表：密文字母表：abcdefghijklmnopqrstuvwxyzGUANZHOBIYSTVWXCDEFJKLMPQR短語密碼28整理ppt短語密碼密碼表構(gòu)造方法2指定一個關(guān)鍵詞，去重復(fù)、空格，按行排陣將剩余的字母依次繼續(xù)按行排陣陣的各列構(gòu)成密碼表例：關(guān)鍵詞=COLLEGE

陣：明文字母表密文字母表短語密碼29整理ppt提綱概述單表代換算法單符號代換算法凱撒密碼移位密碼單表密碼短語密碼仿射密碼攻擊方法小結(jié)30整理ppt仿射密碼仿射密碼（AffineCipher）用仿射變換構(gòu)造密碼表（密碼表便于記憶）密碼表兩個字母表明文字母表 P＝{p0,p1,…,pn-1}密文字母表 C＝{C0,C1,…,Cn-1}引入兩個參數(shù)、，使明文字母P用字母aP+b代替，作為其密文字母加密： Ci=E(pi)=(pi+

)modn解密： pi=D(Ci)=1(Ci)modn31整理ppt仿射密碼實例取參數(shù)=5,=8明文=AFFINECIPHER密文=IHHWVCSWFRCP明文AFFINECIPHERpi055813428157417(5pi+8)83333487328184883432893(5pi+8)mod26877222121822517215CiIHHWVCSWFRCP32整理ppt仿射密碼提示仿射加密函數(shù)要求和n互素，即gcd(,n)=1，否則，(pi+

)modn就不是一個單射函數(shù)當=1、=3時，仿射密碼就是著名的凱撒密碼在解密時，需求解在有限域Zn上的乘法逆元1Zn，這可由擴展歐幾里得算法求解Z26上所有與26互素的元素的乘法逆元：33整理ppt提綱概述單表代換算法單符號代換算法凱撒密碼移位密碼單表密碼短語密碼仿射密碼攻擊方法小結(jié)34整理ppt對單表代換密碼的攻擊兩種典型的攻擊直接攻擊文本方法——頻度分析直接攻擊密鑰方法——暴力破解（窮舉破解）兩種攻擊聯(lián)合使用或單獨使用可一舉破解單表代換密碼35整理ppt直接攻擊文本——頻度分析9世紀阿爾-金迪:《關(guān)于破譯加密信息的手稿》西文語言的獨到特征文章中字母的出現(xiàn)頻度有統(tǒng)計規(guī)律：元音字母頻度高對單表代換密碼的攻擊36整理ppt頻度分析的步驟統(tǒng)計密碼字母的頻度排序按照已知頻度分布替換密文字母對單表代換密碼的攻擊37整理ppt密文頻度分析h:可能是e,a,i,o…嘗試h

e,d

a,l

i,ro,……結(jié)果

密文:

明文:頻度分析攻擊：實例

38整理ppt直接攻擊密鑰——暴力破解前提——已知采用的是代換密碼暴力破解的要點嘗試所有可能的密碼表（移位密碼：最多僅需嘗試25次）暴力破解的步驟選擇一個密碼表作逆代換檢查逆代換后的文本是否有意義，有則結(jié)束，否則換另一個密碼表，進入步驟2對單表代換密碼的攻擊39整理ppt實例密文明文對單表代換密碼的攻擊40整理ppt本質(zhì)選取字母表的一個全排列作為對稱密鑰密鑰數(shù)量26!（41026）單表代換密碼：小結(jié)41整理ppt提綱概述單表代換算法單符號代換算法凱撒密碼移位密碼單表密碼短語密碼仿射密碼攻擊方法小結(jié)42整理ppt特征代換固定——明文字符的代換字符固定位置相同——密文字符與明文字符的位置相同優(yōu)點簡單——得到密文所需的計算量小缺點繼承——密文繼承了明文的統(tǒng)計特性（頻率…）跟隨——明文字符的跟隨關(guān)系反映在密文中單字符代換算法：小結(jié)43整理ppt存在多種不同的破解途徑攻擊密文——頻