第02-01章 現(xiàn)代密碼技術(shù)及其應(yīng)用-概述

第02-01章現(xiàn)代密碼技術(shù)及其應(yīng)用

---概述主講人：李學(xué)明單位：重慶大學(xué)計算機學(xué)院2013年1月2.1密碼技術(shù)概述2.2古典密碼2.3現(xiàn)代密碼技術(shù)2.4消息鑒別2.5數(shù)字簽名2.6消息隱藏與數(shù)字水印目錄2.1密碼技術(shù)概述2.1.1密碼技術(shù)發(fā)展的四個里程碑2.1.2密碼學(xué)基本概念2.1.3密碼系統(tǒng)的安全性1、第一階段：1949年以前，又稱古典密碼階段密碼學(xué)發(fā)展初期階段，密碼學(xué)未形成一門獨立的科學(xué)；

特點：

1）利用手工、機械或初級電子設(shè)備方式實現(xiàn)加解密

2）采用替代與置換技術(shù)

3）保密性基于方法

4）缺少堅實的數(shù)學(xué)基礎(chǔ)

5）未在學(xué)術(shù)界形成公開的討論和研究

2.1.1密碼技術(shù)發(fā)展的四個里程碑(1)2、第二階段：1949～1976，密碼學(xué)形成階段

1）標(biāo)志：

1949年，香農(nóng)(30多歲)發(fā)表“保密通信的信息理論”

2)1967年，kahn發(fā)表“thecodebreakers”3)1971～1973，F(xiàn)eistel等(IBM)發(fā)表的技術(shù)報告

Lucifer-DES分組密碼算法(IBM)4)采用電子計算機實現(xiàn)加解密

5)保密性基于密鑰

6)有較強的數(shù)學(xué)基礎(chǔ)

Kerckoffs假設(shè)：如果密碼系統(tǒng)的強度依賴于攻擊者不知道算法的內(nèi)部機理，則該密碼系統(tǒng)注定會失敗算法不容易保密，可以通過反匯編、逆向設(shè)計、非技術(shù)手段獲得算法實例：

1994年，RC4算法源碼就被公開了

3、第三階段：1976后，公鑰密碼體制的誕生與發(fā)展

1）標(biāo)志：1976年，不對稱密碼

1976年,Diffie&Hellman,發(fā)表“NewdirectionsinCryptography”,提出不對稱密碼

2)1977年,RSA算法

1977年,MIT的Rivert、Shamir、Adleman發(fā)表RSA算法

3)1985年,ECC1985年,N.Koblitz和Miller提出將橢圓曲線用于公鑰密碼系統(tǒng)，并逐漸形成ECC體系

4、第四階段：1984后，量子密碼學(xué)產(chǎn)生階段

1984年，bennettCH和BrassardG發(fā)表BB84協(xié)議

特點：

1)唯一理論上安全的,即使P=NP,其也是安全的；

2)其它都是計算安全的，基于計算復(fù)雜性，但當(dāng)NP=P時，就無安全可言；第二、三、四階段也稱為現(xiàn)代密碼學(xué)階段；此外，混沌密碼學(xué)的研究也成為一個新的研究熱點主要內(nèi)容

1、一般的加密系統(tǒng)模型

2、密碼系統(tǒng)

3、密碼學(xué)基本概念

4、密碼分析簡介

5、密碼學(xué)的數(shù)學(xué)基礎(chǔ)2.1.2密碼學(xué)基本概念(1)1、一般的數(shù)據(jù)加密模型加密器E密鑰源加秘密鑰Ke明文m密文c=Eke(m)公開信道解密器D解密密鑰Kd明文m=Dkd(c)破譯者2.1.2密碼學(xué)基本概念(1)2、密碼系統(tǒng)(體制)

一個密碼系統(tǒng)(體制)可用一個五元組來表示(M,C,K,E,D)(1)明文mi和明文空間M

明文：是易于理解的信息。對計算機而言，是指數(shù)字化的信息?？梢允俏谋尽D像等二進(jìn)制序列。明文可被存儲、傳輸、加工。明文空間：

M={m=(m1,m2,…,ml)|mi∈X,1≤i≤l},明文長度為lX稱為明文字母表(2)密文Ci和密文空間C

密文：不易被理解的信息。對計算機而言，也是以二進(jìn)制形式存在的信息。密文空間：

C={c=(c1,c2.,…,ct)|ci∈Y,1≤i≤t},

密文長度為tY稱為密文字母表(3)密鑰空間K={(Ke,Kd)}

密鑰k:

加密算法E、解密算法D的運行控制參數(shù)

K={k=(k1,k2,…,ks)|ki∈B,1≤i≤s},

密鑰長度為sB稱為密鑰源字母表(4)加密算法E

在Ke的控制下，完成M到C的加密變換規(guī)則本質(zhì)上是M到C的映射(5)解密算法D

在Kd的控制下，完成C到M的解密變換規(guī)則本質(zhì)上是C到M的映射加密:c=Eke(m)

解密:m=Dkd(c)=Dkd(Eke(m))3、密碼系統(tǒng)的分類分類依據(jù)（1）保密內(nèi)容（2）密鑰數(shù)量（3）明文處理方式按保密內(nèi)容來分

A、受限制的（restricted)算法保密性基于保持算法的秘密

B、基于密鑰（key-based)的算法保密性基于對密鑰的保密，算法是公開的按密鑰數(shù)量來分

A、對稱密碼算法（symmetriccipher)：單密碼體制

kd=ke，或kd與ke間存在某種易于發(fā)現(xiàn)的關(guān)系；最大的問題：ke需要在加密方和解密方間進(jìn)行交換密鑰的傳輸和分配是最大問題

B、非對稱密鑰算法（asymmetriccipher)：雙密碼體制

Kd≠ke，且Kd和ke間不存在某種易于發(fā)現(xiàn)的關(guān)系

不存在密鑰交換問題。

Ke不需要保密，可以公開;只有Kd需要保密

按明文處理方式

A、分組密碼（blockcipher)

將明文分成固定長度的組，用同一密鑰和算法對每一塊加密，輸出也是固定長度的密文。

B、流密碼（streamcipher)

又稱序列密碼。序列密碼每次加密一位或一字節(jié)的明文密鑰搜索所需平均時間5、密碼學(xué)的數(shù)學(xué)基礎(chǔ)

(1)基礎(chǔ)數(shù)論基礎(chǔ)數(shù)論用于密碼學(xué)才只有幾十年時間，以RSA為典型

(2)近世代數(shù)群環(huán)域，布爾函數(shù)；如橢圓曲線密碼理論數(shù)理邏輯，BAN邏輯用于協(xié)議分析

(3)非線性復(fù)雜理論混沌序列擬隨機序列1、完善保密系統(tǒng)的含義（香農(nóng)）

I(M;C)=H(M)-H(M|C)=0，則稱相應(yīng)的密碼系統(tǒng)為完善保密系統(tǒng)。即知道密文，并不能獲取更多明文的信息；也即是說，無論截取多少密文，也無法獲得相關(guān)明文的信息密碼系統(tǒng)設(shè)計的基本原則：

確保明文與密文間的互信息為0；即明文空間與密文空間完全無關(guān)2、定理：完善保密系統(tǒng)的必要條件:H(K)≥H(M)

該定理由香農(nóng)在1949所證明：M和C要完全無關(guān)，密鑰熵不能小于明文熵,密鑰必須具有隨機特性，即K應(yīng)為真正的隨機序列2.1.3密碼系統(tǒng)的安全性2、密碼系統(tǒng)的安全性分類

（1）無條件安全（Unconditionallysecure）

無論破譯者有多少密文,他也無法解出對應(yīng)的明文,即使他解出了,他也無法驗證結(jié)果的正確性。

Onetimepad：一次一密；

滿足H(K)≥H(M)條件但不實用(2)計算上安全（Computationallysecure）破譯的代價超出信息本身的價值破譯的時間超出了信息的有效期破譯的時間復(fù)雜度不是多項式的算出和估計出破譯它的計算量下限，利用已有的最好的方法破譯該密碼系統(tǒng)所需要的努力超出了破譯者的破譯能力（諸如時間、空間、資金等資源）主要內(nèi)容

1、羊皮密碼

2、替代密碼

3、置換密碼

4、一次一密方案

5、轉(zhuǎn)輪機2.2古典密碼1、羊皮密碼

1)公元前400年，斯巴達(dá)人使用棍子和羊皮進(jìn)行秘密通信。

2)他們把羊皮螺旋狀地纏繞著棍子，然后沿著棍子的水平方向一行一行地寫。寫完后把紙條取下來，送到接收者手中。

3)羊皮上只有雜亂無章的字母，但當(dāng)接收者把它繞在同樣直徑(直徑可以看成是一種密鑰)的棍子上時，一段清楚的文字就神奇般地顯現(xiàn)出來。

4)該方法很可能是文字記載的最早加密算法。

5)該方法雖然很簡單，但還是起到了一定的保密作用。2、置換密碼根據(jù)一定規(guī)則重新安排明文，使重排后的明文失去可理解特性。

(m1,m2,…,ms)--->(mt1,mt2,…,mts)F的數(shù)量雖然有n!，但其不能抗攻擊，甚至是唯密文攻擊canyoudoitforme明文：Canyoudoitforme密文：coirautmndfeyoo輸入方向輸出方向美國南北戰(zhàn)爭3、替代密碼將明文空間中的一個字符或字符串替換成密文空間中的一個字符或字符串1)單表替代密碼(monoalphabeticsubstitutioncipher)2)同音替代密碼(homophonicsubstitutioncipher)3)多表替代密碼(polyalphabeticsubstitutioncipher)4)多字母替代密碼(polygramsubstitutioncipher)(1)單表替代密碼:一個名文字母對應(yīng)一個密文字母愷撒密碼caesercipher是一種單表替代密碼英文字母向前或后移動若干位，對應(yīng)的字母即為密文。其密碼本為：明文:abcdefghijklmnopqrstuvwxyz

密文:defghijklmnopqrstuvwxyzabc

例：明文caeserwasagreatleader

密文geiwivaewekviexpiehiv

一般的單表替換密碼可表示為：c=E(m)=(am+b)modn(仿射密碼)

對愷撒密碼：a=1,b=3,n=26

不能抗窮舉攻擊、統(tǒng)計攻擊(明文的字母統(tǒng)計特性反映在密文中)(2)同音替代密碼一個明文字母對應(yīng)對個多個密文字母

(1)canada’slargelandmassand(6)scatteredpopulationmakeefficientcommunication(11)anecessity.Extensiverailway,road(16)andothertransportationsystems,as(21)wellastelephone,telegraph,and(26)cablenetworks,havehelpedto(31)linkcommunitiesandhaveplayed(36)avitalpartinthe(40)country’sdevelopmentforfuture

密碼本：c:1、10、26、32、41(首字母為c的單詞的所在位置);m:4、8…

明文：Iloveherforever

密文：392173792891443171413371314(e:9或13)(3)多表替代密碼由多個單表替代密碼構(gòu)成。一個字母在不同位置上被替換成不同的密文字母。典型的Vigenere密碼

Vigenere形式化描述：

t個密文本，加密為：

ci=fi(mi)=(mi+ki)mod26,其中ki為密鑰,i=0,1,…,t-1t=1時，就是單表替代

對明文:m=(m0,m1,…,mt-1,mt,…)

密文為:c=(f0(m0),f1(m1,…,ft-1(mt-1),f0(mt),….)舉例說明：

k=(6,14,15,7,4,17),t=6m=meetmeintheallyaftermidnightc=sstaqvobioirrznhjkkfbpheouwaabcdefghijklmnopqrstuvwxyz012345678910111213141516171819202122232425

(4)多字母替代密碼明文字母串被替換成密文字母串，替代是以多個字母串為單位，而不是針對單個字母。典型例子為：playfair密碼（英國在一戰(zhàn)中使用過）用25個英文字母組成5階方陣(J不用，默認(rèn)為I)左邊密鑰矩陣是用firewallsecurity導(dǎo)出的1915年被德國破解加密方法：

1)明文以2個字母為單位進(jìn)行加密：m1m2--->c1c22)若m1、m2在同一行，則c1、c2分別為緊靠m1、m2右端的字母(第一列為最后一列的右端)3)若m1、m2在同一列，則c1、c2分別為緊靠m1、m2下端的字母(第一行為最后一行的下端)4)若m1、m2既不在同一行，又不在同一列，則c1、c2分別為m1、m2確定的矩形的兩個頂點所對應(yīng)的字母，c1與m1同行，c2與m2同行

5)若m1=m2，則在m1和m2見插入無效字母(如x)6)若明文字母數(shù)為奇數(shù)，則在其末附加一個無效字母明文：playfaircipherwasbroke分組：playfaircipherwasbroke密文：qaltatrelefpwefubmwmni4、一次一密方案(one-timepad,OTP)(1)一次一密體制的含義：

A.密鑰是真正的隨機序列

B.密鑰長度至少等于明文長度

C.一個密鑰只用一次

(2)滿足上述三個條件的密碼系統(tǒng)是絕對安全的，不會被破譯(香農(nóng)在1949年已證明)(3)Verman密碼(美國人摩波卡金其基礎(chǔ)上設(shè)計出一次一密體制)

美國電報電話公司的Verman弗納姆發(fā)明了弗納姆密碼。原理是利用電傳打字機的五單位碼與密鑰字母進(jìn)行模2相加(異或運算)

明文:m=(m1,m2,…,ms)

密鑰:k=(k1,k2,…,ks)

密文:c=(c1,c2,….cs)加密：A--->00000;b--->00001;c--->0001