密碼編碼學-1(武武漢大學國際軟件學院信息安全課程)

1信息安全

密碼編碼學楊敏武漢大學國際軟件學院yangm@2密碼編碼學基本概念和術語密碼學的歷史古代密碼古典密碼現(xiàn)代密碼3基本概念和術語密碼技術的目的使不知道如何解密的黑客不可能由其截獲的亂碼中得到任何有意義的信息；使黑客不可能偽造任何亂碼型的信息。密碼學(密碼技術)分類密碼編碼學：對信息進行編碼實現(xiàn)信息隱蔽密碼分析學：研究加密消息的破譯或消息的偽造4基本概念和術語明文（plaintext）：被隱藏的消息密文（ciphertext）：隱藏后的消息加密（encryption）：由明文到密文的變換過程解密（decryption）：由密文恢復出原始明文的過程破譯：非法接收者試圖從密文分析出明文的過程5基本概念和術語密碼算法(cryptographyalgorithm)是用于加密和解密的數(shù)學函數(shù)。加密算法(encryptionalgorithm).對明文進行加密操作時所采用的一組規(guī)則解密算法(decryptionalgorithm)接收者對密文解密所采用的一組規(guī)則6基本概念和術語密鑰（Key）加密算法和解密算法是在一組僅有合法用戶知道的秘密信息，稱為密鑰的控制下進行的。加密和解密過程中使用的密鑰分別稱為加密密鑰和解密密鑰。7密碼體制加密解密明文X密文Y明文X密鑰(K)對稱密碼體制(symmetriccryptosystem)加密密鑰和解密密鑰是相同的Y=E(K,X)X=D(K,Y)8對稱密碼體制的特點：無論加密還是解密都使用同一個密鑰，因此，此密碼體制的安全性就是密鑰的安全。如果密鑰泄露，則此密碼系統(tǒng)便被攻破。最有影響的對稱密碼是1977年美國國家標準局頒布的DES算法。優(yōu)點：安全性高、加解密速度快。缺點：1)隨著網(wǎng)絡規(guī)模的擴大，密鑰的管理成為一個難點；2)無法解決消息確認問題；9密碼體制加密解密明文X密文Y明文X加密密鑰Ke解密密鑰KdY=E(Ke,X)X=D(Kd,Y)非對稱密碼體制(asymmetriccryptosystem)加密密鑰和解密密鑰是成對出現(xiàn)加密過程和解密過程不同，使用的密鑰也不同10非對稱密碼體制特點：是1976年W.Diffie和M.E.Hellman提出的一種新型密碼體制。加密密鑰與解密密鑰不同，此時不需要安全信道來傳送密鑰。優(yōu)點：由于加密和解密不同，且能公開加密密鑰，而僅需保密解密密鑰，所以非對稱密碼不存在密鑰管理問題。非對稱密碼還有一個優(yōu)點是可以擁有數(shù)字簽名等新功能。最有名的對稱密碼是1977年由Rivest，Shamir和Adleman三人提出的RSA密碼體制。缺點：非對稱密碼算法一般比較復雜，加解密速度慢。11密碼分析密碼分析是無須取得密鑰而能將密文信息恢復成明文的科學。企圖利用算法的性質和明文的一般特性或某些明密文推導出特別的明文或使用的密鑰。 攻擊類型密碼分析者已知的信息唯密文攻擊加密算法；要解密的密文已知明文攻擊加密算法；要解密的密文；用(與待解密文)同一密鑰加密的多個明密文對選擇明文攻擊加密算法；要解密的密文；分析者任選明文，并用(與待解密文)同一密鑰加密的密文選擇密文攻擊加密算法；要解密的密文；分析者有目的選擇密文，并用(與待解密文)同一密鑰解密的對應明文選擇文本攻擊加密算法；要解密的密文；分析者任選明文，并用(與待解密文)同一密鑰加密的密文；分析者有目的選擇密文，并用(與待解密文)同一密鑰解密的對于明文傳統(tǒng)密碼體制基于加密信息的攻擊類型13密碼分析窮舉攻擊攻擊者對一條密文嘗試所有可能的密鑰，直到得到有意義的明文。窮舉攻擊是最基本也是比較有效的一種攻擊方法。從理論上講，可以嘗試所有的密鑰。窮舉攻擊的代價與密鑰大小成正比。密碼算法可以通過增大密鑰位數(shù)或加大解密（加密）算法的復雜性來對抗窮舉攻擊。14下表是窮盡密鑰空間所需的時間。從表中我們可以發(fā)現(xiàn)，當密鑰長度達到128位以上時，以目前的資源來說，窮舉攻擊將不成功。15密碼的安全性考慮無條件安全(Unconditionallysecure)無論破譯者有多少密文,他也無法解出對應的明文,即使他解出了,他也無法驗證結果的正確性.一次一密計算上安全的破譯密碼的代價超出密文信息的價值破譯密碼的時間超出密文信息的有效生命期16基本概念和術語密碼學的歷史古代密碼古典密碼現(xiàn)代密碼密碼編碼學17密碼學的發(fā)展史古代加密方法（手工階段）古典密碼（機械階段）現(xiàn)代密碼（計算機階段）18古代加密方法起源于公元前440年出現(xiàn)在古希臘戰(zhàn)爭中的隱寫術(steganography)：通過隱藏消息的存在來保護消息.是現(xiàn)今信息隱藏的始祖

19隱寫術字符標記：印刷或打印的文本字母經(jīng)選擇用鉛筆重寫。該標記通常不可見，除非該紙以一定的角度對著亮光看。不可見墨水：使用一些物質來書寫，但不留下任何可見痕跡，除非加熱該紙或在該紙上涂上某種化學藥品。扎小孔：在所選的字母上扎小孔，這些小孔通常不可見，除非把該紙放在光的前面。格孔密寫卡：將它覆蓋在一張紙上從格孔中寫入密件，然后在紙上余下部分填入其它字句，使它像一般信件。20例如：格孔密寫卡密文：王先生：來信收悉，你的盛情難以報答。我已在昨天抵達廣州。秋雨連綿，每天需備傘一把。大約本月中旬即可返回，再談。弟：李明

明文：情報在雨傘把中。21古代加密方法斯巴達人用于加解密的一種軍事設備(SpartanScytale,400B.C.)發(fā)送者把一條羊皮螺旋形地纏在一個圓柱形棒上思想：置換（permutation)22古代加密方法Phaistos圓盤，一種直徑約為160mm的Cretan-Mnoan粘土圓盤，始于公元前17世紀。表面有明顯字間空格的字母，至今還沒有破解。23古代加密方法一個叫AeneasTacticus的希臘人在《論要塞的防護》一書中對傳輸密文做了最早的論述。公元前2世紀，一個叫Polybius的希臘人設計了一種將字母編碼成符號對的方法，他使用了一個稱為Polybius的校驗表，表中包含許多后來在加密系統(tǒng)中常見的方法，如代替與換位。24密碼學的發(fā)展史古代加密方法（手工階段）古典密碼（機械階段）現(xiàn)代密碼（計算機階段）25古典密碼古典密碼系統(tǒng)已經(jīng)初步體現(xiàn)出近代密碼系統(tǒng)的雛形，它比古代加密方法復雜，其變化較小。古典加密技術主要使用代換或者置換技術。古典密碼使用手工或機械變換的方式實現(xiàn)。26兩種基本加密技術代換（代替、替換）技術將明文字母替換成其它字母、數(shù)字或符號的方法。置換（換位）技術保持明文的所有字母不變，只是打亂明文字母的位置和次序。27古典代換加密技術又可以分為:簡單代換密碼，又稱為單字母代換密碼：它將明文的一個字符用相應的一個密文字符代替。使用一個字母表（明文的一個字母總是被同一個固定的字母代換）的簡單代換密碼也稱為單表代換密碼。例如：Caesar密碼。多字母代換密碼：它是對多于一個字母進行代換例如：Playfair密碼；Hill密碼。多表代換密碼：是將明文消息中出現(xiàn)的同一個字母，在加密時不是完全被同一個固定的字母代換，而是根據(jù)其出現(xiàn)的位置次序，用不同的字母代換。例如：Vigenere密碼。28代換密碼——單字母代換Caesar密碼：公元前50年，由JuliusCaesar發(fā)明，最早用在軍方。加密：將明文中的每個字母，用在字母表中它后面的第3個字母代替。解密：反過來，將密文中的每個字母，用它前面的第3個字母代替。ABCDEFGHIJKLMNOPQRSTUVWXYZDEFGHIJKLMNOPQRSTUVWXYZABC字母編碼明文：Systemmodels

密文：Vbvwhpprghov29代換密碼——單字母代換一般的愷撒密碼加密：每個明文字母用它后面的第k個字母代替解密：每個密文字母用它前面的第k個字母代替其中k為密鑰，1k25一般的愷撒密碼的破譯分析已知加密和解密算法需要測試的密鑰只有25個明文所用的語言是已知的，且其意義易于識別。因此：可以采用窮舉攻擊30練習密文：HTRUZYJWXDXYJR算法：一般的凱撒密碼明文:?Computersystem31Caesar密碼安全性上面的例子說明，凱撒密碼不足以對抗窮舉攻擊。因此是不安全的。這個例子說明一個密碼體制安全至少要能夠抵抗窮舉密鑰搜索攻擊，普通的做法是將密鑰空間變得足夠大。但是，很大的密鑰空間并不是保證密碼體制安全的充分條件，下面的例子可以說明這一點。32代換密碼——單表代換改進：使用密鑰詞的愷撒密碼使用密鑰詞控制字母表中的排列ABCDEFGHIJKLMNOPQRSTUVWXYZwordABCEFGHIJKLMNPQRSTUVXYZ字母編碼密鑰詞為word33單表代換分析密鑰空間增加(26!)，窮舉搜索這么多的密鑰很困難但這并不表示該密碼不容易破解破解這類密碼的突破點是由于語言本身的特點是充滿冗余的，每個字母使用的頻率不相等

而單表代換密碼沒有改變字母相對出現(xiàn)的頻率明文字母的統(tǒng)計特性在密文中能夠反映出來,當通過統(tǒng)計密文字母的出現(xiàn)頻率，可以確定明文字母和密文字母之間的對應關系34英文字母統(tǒng)計特性英文單字母的相對頻率表35單字母按照出現(xiàn)頻率的大小可以分為下面5類：

(1)e：出現(xiàn)的頻率大約為0.127(2)t,a,o,I,n,s,h,r：出現(xiàn)的頻率大約在0.06-0.09之間

(3)d,l：出現(xiàn)的頻率約為0.04(4)c,u,m,w,f,g,y,p,b：出現(xiàn)的頻率大約在0.015-0.028之間

(5)v,k,j,x,q,z：出現(xiàn)的頻率小于0.01英文字母統(tǒng)計特性36雙字母和三字母組合都有現(xiàn)成的統(tǒng)計數(shù)據(jù)，常見的雙字母組合和三字母組合統(tǒng)計表能夠幫助破解密文。頻率最高的30個雙字母（按照頻率從大到小排列）：

thheineranreedonesstenattonthandoueangasortiisetitartesehiof

頻率最高的20個3字母（按照頻率從大到小排列）：

theingandherereentthanthwasethfordthhatsheioninthissthersver英文字母統(tǒng)計特性37破解舉例例3.1

已知下面的密文式由單表代換生產(chǎn)的：UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ，試破譯該密文首先統(tǒng)計密文中字母出現(xiàn)的頻率，然后與英文字母出現(xiàn)頻率比較。密文中字母的相對頻率統(tǒng)計如下：38破解舉例39將統(tǒng)計結果與頻率表進行比較，可以猜測密文中P與Z可能是e和t，密文中的S,U,O,M出現(xiàn)頻率比較高，可能與明文字母中出現(xiàn)頻率相對較高的a,o,I,n,s,h,r這些字母對應密文中出現(xiàn)頻率很低的幾個字母C,K,L,N,R,I,J可能與明文字母中出現(xiàn)頻率較低的字母v,k,j,x,q,z對應。就這樣邊試邊改，最后得到明文如下：itwasdisclosedyesterdaythatseveralinformalbutdirectcontactshavebeenmadewithpoliticalrepresentativesofthevietconginmoscow破解舉例40在嘗試過程中，如果同時使用雙字母和三字母的統(tǒng)計規(guī)律，那么更容易破譯密文。如上面的密文中出現(xiàn)最多的雙字母是ZW，它可能對應明文雙字母出現(xiàn)頻率較大的th，那么ZWP就可能是the，這樣就更容易試出明文。破解舉例41代換密碼——多字母代換Playfair密碼1854年由英國科學家CharlesWheatstone發(fā)明。將明文中的雙字母音節(jié)作為一個單元并將其轉換成密文的“雙字母音節(jié)”。算法基于一個由密鑰詞構成的55字母矩陣。

42例：密鑰詞為monarchy，明文為balloon如果該字母對兩個字母相同，則它們之間加一個填充字母，如x；則明文分為四個字母對：balxloon落在矩陣同一行的明文字母對中的字母由其右邊的字母替換；on替換成na落在矩陣同一列的明文字母對中的字母由其下面的字母替換；ba替換成ib(或jb)其他的每組明文字母對中的字母如下替換：它所在的行是該字母的所在行，列則為另一個字母的所在列。

lo替換成pm

lx替換成suMONARCHYBDEFGI/JKLPQSTUVWXZ密文為：ibsupmna或jbsupmna43Playfair密碼的安全性Playfair密碼的安全性比單表代換密碼提高了許多雙字母共有26x26=676組合，因此頻率統(tǒng)計分析表中需要676條統(tǒng)計數(shù)據(jù)Playfair密碼中比單表代換更好地隱藏了明文中單字母的結構在第一次世界大戰(zhàn)中被英軍作為最好的密碼系統(tǒng)使用，在第二次世界大戰(zhàn)中也曾經(jīng)被美軍和盟軍大量使用當然現(xiàn)在看來，該密碼的安全性是很低的，它還保留明文的部分特征，只要給定幾百個字母的密文情況下，該加密方法就可以破解44練習：Playfair加密假設密鑰是cipher，使用Playfair算法加密如下明文：Playfaircipherwasactuallyinventedbywheatston45練習：Playfair加密由密鑰詞cipher可構建密鑰矩陣：將明文按照兩個字母分組為

playfaircipherwasactualxlyinventedbywheatstonx則密文為

BSDWRBCAIPHECFIKQBHOQFSPMXEKZCMUHFDXYIIFUTUQLZ

CI/JPHERABDFGKLMNOQSTUVWXYZ46代換密碼——多表代換多表代換：在明文消息中采用不同的單表代換。特征：采用相關的單表替換規(guī)則集由密鑰決定給定替換的具體規(guī)則47代換密碼——多表代換Vigenere密碼1858年法國密碼學家維吉尼亞提出替換規(guī)則由26個類似caesar密碼的替換表組成，其中每一個替換表是對明文字母移位0到25次后得到的替換單表。每個替換單表由一個密鑰字母表示。48ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJABCDEFGHIJKLMNOPQRSTUVWXYZBCDEFGHIJKLMNOPQRSTUVWXYZACDEFGHIJKLMNOPQRSTUVWXYZABDEFGHIJKLMNOPQRSTUVWXYZABCEFGHIJKLMNOPQRSTUVWXYZABCDFGHIJKLMNOPQRSTUVWXYZABCDEGHIJKLMNOPQRSTUVWXYZABCDEFHIJKLMNOPQRSTUVWXYZABCDEFGIJKLMNOPQRSTUVWXYZABCDEFGHJKLMNOPQRSTUVWXYZABCDEFGHI……

……Vigenere替換表密鑰:deceptive明文:wearediscoveredsaveyourself密文:明文密鑰deceptivedeceptivedeceptivewearediscoveredsaveyourselfzicvtwqngrzgvtwavzhcqyglmgj49Vigenere密碼的安全性

維吉尼亞密碼是將每個明文字母映射為幾個密文字母。如果密鑰字的長度是m，明文中的一個字母能夠映射成這m個可能的字母中的一個。密文中字母出現(xiàn)的頻率被隱蔽了，它的安全性明顯比單表代換密碼提高了。維吉尼亞密碼的密鑰空間比較大，對于長度是m的密鑰字，密鑰空間為26m

。當m=5，密鑰空間所含密鑰的數(shù)量大于1.1x107

Vigenere密碼的攻擊方法

如果兩個相同明文序列之間的距離是密鑰詞長度的整倍數(shù)，那么產(chǎn)生的密文序列也是相同的。找到重復序列，推斷出密鑰詞的長度。如果密鑰詞的長度是m,那么密碼實際上包含了m個單表代替。利用明文語言的頻率特征對這樣的單表密碼進行攻擊。5051練習：Vigenere密碼使用Vigenere密碼加密單詞explanation，密鑰為leg。密鑰：legleglegle明文：explanation密文：PBVWETLXOZR52一次一密：非周期多表代換密碼

使用與明文一樣長且無重復的隨機密鑰來加密明文，并且該密鑰使用一次后就不再使用。密文和明文沒有任何統(tǒng)計關系。理論上一次一密是不可攻破的。事實上，給出任何長度與密文一樣的明文，都存在一個密鑰產(chǎn)生這個明文。因此靠窮舉密鑰的方法，會得到大量可讀的明文。無法確定哪一個是真正需要的。53一次一密的例子密文：yvelpqnqv密鑰：fzqlabcmd明文：twoapples密文：yvelpqnqv密鑰：kiaxyqakr明文：oneorange另見課本P36所示的例子。54一次一密一次一密的安全性是取決于密鑰的隨機性。但產(chǎn)生大規(guī)模隨機密鑰是一件很困難的事情，目前還沒有很好的辦法來解決這個問題。密鑰分配也是一個難點，由于密鑰不允許重復使用，因此存在大量的密鑰分配問題。一次一密在實際中很少使用，主要是用于高度機密的低帶寬信道。55轉輪機：多輪代換56兩種基本加密技術代換（代替、替換）技術將明文字母替換成其它字母、數(shù)字或符號的方法。置換（換位）技術保持明文的所有字母不變，只是打亂明文字母的位置和次序。57置換密碼將明文的字母順序打亂，得到新的排列最簡單的置換密碼：柵欄技術明文

meetmeafterthetogaparty置換方法

mematrhtgpryetefeteoaat密文

mematrhtgpryetefeteoaat58置換密碼列置換以固定的寬