信息安全系統(tǒng)工程密碼學基礎和古典加密

1、一、密碼學基礎,1、密碼學概述2、密碼體制分類3、密碼分析,1、密碼學概述,密碼學是研究密碼系統(tǒng)或通信系統(tǒng)安全的科學，它包括兩個分支：密碼編碼學（Cryptography）密碼分析學（Cryptanalytics）密碼編碼學是研究信息的加密與解密的學科，通常將密碼編碼學簡稱為密碼學。,密碼體制,它是一個五元組（P,C,K,E,D)，并滿足條件： （1）P是可能明文的有限集（明文空間） （2）C是可能密文的有限集（密

2、文空間） （3）K是一切可能密鑰構成的有限集（密鑰空間） （4）對每一個 有一個加密規(guī)則 和相應的解密規(guī)則 ，每一個 和 是一個函數(shù)，它滿足其中關鍵的是性質4，它保證了如果使用 ek 對明文x 加密，則可使用相應的 dk 對密文解密ek 顯然應該是一個單射函數(shù)。,保密通信系統(tǒng)模型,數(shù)據(jù)加解密例子,,共享密鑰（類似于鑰匙）：F

3、AE1C96130140DA43FC6414BAF9CA886,對現(xiàn)代密碼體制的要求,1、一切秘密寓于密鑰之中（Kerckhoff原則）即現(xiàn)代密碼體制不能依賴于算法保密2、體制即使達不到理論上不可破譯（無條件保密），也必須是實際上不可破譯的（計算上保密）3、加解密算法適用于所有密鑰空間中的元素4、加密算法和解密算法能有效計算，便于實現(xiàn)和使用,密碼體制安全性評價方法,1、計算安全性如果攻擊者使用可利用的全部資源，在密文保密期內都

4、不能破譯密碼，則稱該密碼體制是計算安全的。2、可證明安全性將密碼體制的安全性歸結為某個數(shù)學難題，該數(shù)學難題被證明其求解是困難的。3、無條件安全性即使攻擊者擁有無窮的計算資源，依然無法破譯的密碼體制稱為是無條件安全的。,2、密碼體制分類,按通信雙方使用的密鑰，分為單鑰密碼體制和公鑰密碼體制按對明文數(shù)據(jù)的處理方式，分為分組密碼體制和流密碼體制,單鑰體制和公鑰體制,單鑰體制也叫對稱加密體制或常規(guī)加密體制同一次加解密中發(fā)送者和接收

5、者使用相同的密鑰（或雖然不同，但容易從一個密鑰推出另一個密鑰）公鑰體制也叫非對稱加密體制同一次加解密中發(fā)送者和接收者使用不同的密鑰（并且除了解密密鑰擁有者以外，其他任何人從加密密鑰難以導出解密密鑰）,單鑰體制和公鑰體制示意圖,單鑰密碼體制,公鑰密碼體制,單鑰密碼體制的特點,由于單鑰密碼體制中的加密密鑰和解密密鑰相同，所以，在實際應用中，要在收發(fā)雙方之間建立一條安全的秘密信道來傳遞密鑰若網絡中有 n 個通信主體，那么每人必須擁有

6、(n-1) 個密鑰，系統(tǒng)中需要有 n*(n-1) / 2 個不同的密鑰。當 n 很大時，密鑰的數(shù)量是驚人的。同時，單鑰密碼體制不具有防抵賴功能因為密鑰是雙方共有的，所以任何一方偽造或篡改消息，另一方都拿不出證據(jù)來澄清事實。,公鑰密碼體制的特點,在公鑰密碼體制中，各個主體都擁有一對密鑰：其中一個是秘密的，由本人產生、保管，用于解密，稱為私鑰；另一個則可以公開，用于加密，稱為公鑰。一般公鑰容易由相應的私鑰計算得到，但從公鑰卻很難推

7、出私鑰。公鑰密碼體制具有下述優(yōu)點：1、可用于公共網絡中的保密通信；2、可達到不可否認功能；3、使用公鑰密碼體制，簡化了密鑰的分配與管理。,分組密碼和流密碼,分組密碼體制加密體制一次處理一個明文分組（如8字節(jié)或16字節(jié)），并產生一個密文分組流密碼體制加密體制連續(xù)處理一個輸入元素（如 1 bit 或 1 字符），同時產生相應的一個輸出元素（1 bit 或 1 字符）,3、密碼分析,密碼分析：破譯者在不知道密鑰（但了解所采用的

8、加密體制以及明文空間的統(tǒng)計特性）的條件下，對密文進行分析，試圖發(fā)現(xiàn)明文或密鑰的過程。密碼分析方法包括窮舉攻擊法和統(tǒng)計分析法。在進行密碼設計和密碼分析時，應遵循著名的柯克霍夫（Kerckhoffs）基本假設：密碼分析者知道所要攻擊的密碼體制的加密體制或加、解密算法。也就是說，密碼體制的安全性不應取決于加、解密算法的保密，只取決于密鑰的保密。,密碼分析的攻擊條件,根據(jù)密碼分析者對明文、密文等信息掌握的多少，可將密碼分析分為以下四種情

9、形（強度依次遞增 ）：1、唯密文攻擊（Ciphertext Only Attack）：破譯者僅有待破譯的密文。2、已知明文攻擊（Known Plaintext Attack）：破譯者擁有一定數(shù)量的密文和對應的明文。3、選擇明文攻擊（Chosen Plaintext Attack）：破譯者可以選定一些明文，并獲得對應的密文。4、選擇密文攻擊（Chosen Ciphertext Attack）：破譯者可以選定一些密文，并獲得對應的明

10、文。,二、古典加密技術,1、移位密碼 (Shift Cipher)2、仿射密碼(Affine Cipher)3、維吉尼亞密碼 (Vigenere Cipher)4、置換密碼(Permutation or transposition Cipher)5、 ENIGMA密碼機,1、移位密碼 (Shift Cipher),定義：設P=C=K=Z26，對0<=K<=25，定義 ek(x)=x+K (mod 26)

11、， 同時dk(y)=y-K (mod 26)對英文字母而言，有如下映射,移位密碼 (Shift Cipher),凱撒密碼(Caesar Cipher)當移位密碼的密鑰 K=3 時，為凱撒密碼例，設 k = 3，明文 = meet me after the toga party密文 = PHHW PH DIWHO WKH WRJD SDUWB密鑰空間：26,對移位密碼的強行攻擊,由于移位密碼的可能密鑰只有 26 個，因此可以對

12、密鑰進行窮舉嘗試，將每一個密鑰帶入解密規(guī)則，直到獲得一個“有意義”的明文串例如對于前面凱撒密碼的例子進行強行攻擊如下（唯密文攻擊）：平均一個明文將在嘗試 26/2=13（即“密鑰數(shù)量/2”）次解密規(guī)則后確定,2、仿射密碼(Affine Cipher),定義：設P=C=K=Z26，且 K= { (a,b) ∈ Z26* Z26: gcd(a,26)=1 }, 對任意的 k=(a,b), 定義 加密變換為： ek

13、(x)=(a*x+b) mod 26 解密變換為： dk(y)=a-1*(y-b) mod 26例：設 k=(7,3)，則 a-1=7-1=15 (mod 26)，因此 加密變換為： ek(x)=(7*x+3) mod 26 解密變換為： dk(y)=15*(y-3)=15*y-19 mod 26 用它來加密明文“hot”： 首先將字母轉換為模 26下的數(shù)，分別

14、為7、14、19；將其分別加密為： (7*7+3) mod 26=0， (7*14+3) mod 26=23， (7*19+3) mod 26=6。因此密文為“AXG”.,仿射密碼(Affine Cipher),密鑰空間： ø(26) *26 = 12 * 26 = 312ø(n): 歐拉函數(shù)，表示比 n 小，并且與 n 互素的正整數(shù)的個數(shù)ø(26)={1,3,5,7,9,11,

15、15,17,19,21,23,25}顯然，移位密碼是仿射密碼的特例。此外，仿射密碼和移位密碼都是一種“單表代換”密碼。,3、維吉尼亞密碼 (Vigenere Cipher),由 16 世紀的法國人Blaise de Vigenere發(fā)明定義：設 m 為一固定的正整數(shù)，定義P=C=K=(Z26)m，對一個密鑰K＝( k1, k2, …, km)， 定義 ek(x1,x2,…,xm) = (x1+k

16、1,x2+k2,…,xm+km) = y， dk(y1,y2,…,ym) = (x1-k1, x2-k2,…, xm-km) = x 注：這里的所有的運算都是在(mod 26)中進行的。,維吉尼亞密碼（續(xù)）,維吉尼亞密碼是一種多表代換密碼，每個明文字母由不同的密文字母替換（在密鑰周期內），所有替換規(guī)則的集合由 26 個移位密碼組成。為了幫助理解該方法，可以構造如下表格（維吉尼亞表格）：,維吉尼亞密碼 （續(xù)）

17、,例：設密鑰為deceptive，對明文 We are discovered save yourself 加密假設Vigenere密碼的密鑰長度為 m，則其密鑰空間為 26m例如，當 m=5 時，其密鑰空間的大小超過 265=1.1*107。,4、置換密碼(Permutation Cipher),定義：設 m 為一正整數(shù)，P=C=(Z26)m，K是由 {1,2,..,m} 的所有置換構成。對一個密鑰 π∈K，定義

18、 eπ(x1, x2,.., xm)=(xπ(1),,..,xπ(m))， dπ(y1, y2,.., ym)=(yπ-1(1),,..,yπ-1(m)) 這里 π-1 為 π 的逆置換。,置換密碼（續(xù)）,例：設 m=6, 且密鑰如下 則對明文crypto加密，得,5、ENIGMA密碼機,,參見文章《ENIGMA的興亡》和電影《模仿游戲》,三、古典密碼分析,密碼分析中攻擊者了解什么：加密

19、和解密算法明文的語言明文的統(tǒng)計特性英文的字母的頻率分布（見下圖）雙字母組合的頻率分布(TH>HE>IN>ER>AN>RE>ED>ON>ES>ST…)等三字母組合的頻率分布 (THE>ING>AND>HER>ERE>ENT>THA…)等,對單表代換密碼的分析攻擊,由于單表代換密碼完整的保留了原始明文的統(tǒng)計特性，因此可以容易地進行分析攻

20、擊例：設密文為“UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMESXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ”（見《密碼編碼學與網絡安全:原理與實踐》第二版24頁），對其進行分析,對單表代換密碼的分析攻擊（續(xù)）,1）計算密文字母相對頻率如下,對單表代換密碼的分析攻擊（續(xù)）,2）將密文字母頻率

21、分布和英文字母頻率分布進行對照，可以猜測密文字母P、Z對應明文字母集{e、t}，字母S、U、O、M、H具有相對高的頻率，可能對應字母集{r、n、i、o、a、s}，具有最低頻率的字母(A,B,G,Y,I,J)很可能包括在集合{w,v,b,k,x,q,j,z}中。3）嘗試4）輔以雙字母頻率繼續(xù)進行分析和證實5）……,對單表代換密碼的分析攻擊（續(xù)）,6）解密的明文如下：It was disclosed yesterday that s

22、everal informal but direct contacts have been made with political representatives of the view cong in moscow,小結,1、密碼學基本概念2、古典加密體制3、古典密碼分析主要參考書《現(xiàn)代密碼學》作者：楊波；出版社：清華大學出版社《鐵路信息安全技術》主編：彭代淵；出版社：中國鐵道出版社《密碼編碼學與網絡安全:原理與實踐》

23、第二版作者：William Stallings； 譯者： 楊明 等,作業(yè),1、用移位密碼對“this is the message”加密，密鑰k=13。2、用仿射密碼e(x)=3*x+7 (mod 26)加密明文“meet me at midnight”。3、確定仿射密碼e(x)=3*x+7 (mod 26)的解密函數(shù)。4、已知維吉尼亞密碼的密鑰為“cipher”，對明文“this cryptosy