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

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

---概述主講人：李學(xué)明單位：重慶大學(xué)計(jì)算機(jī)學(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ā)展的四個(gè)里程碑2.1.2密碼學(xué)基本概念2.1.3密碼系統(tǒng)的安全性1、第一階段：1949年以前，又稱(chēng)古典密碼階段密碼學(xué)發(fā)展初期階段，密碼學(xué)未形成一門(mén)獨(dú)立的科學(xué)；

特點(diǎn)：

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

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

3）保密性基于方法

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

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

2.1.1密碼技術(shù)發(fā)展的四個(gè)里程碑(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ù)報(bào)告

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

5)保密性基于密鑰

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

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

1994年，RC4算法源碼就被公開(kāi)了

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

1）標(biāo)志：1976年，不對(duì)稱(chēng)密碼

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

2)1977年,RSA算法

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

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

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

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

特點(diǎn)：

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

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

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

2、密碼系統(tǒng)

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

4、密碼分析簡(jiǎn)介

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

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

明文：是易于理解的信息。對(duì)計(jì)算機(jī)而言，是指數(shù)字化的信息。可以是文本、圖像等二進(jìn)制序列。明文可被存儲(chǔ)、傳輸、加工。明文空間：

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

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

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

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

密鑰k:

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

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

密鑰長(zhǎng)度為sB稱(chēng)為密鑰源字母表(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)的分類(lèi)分類(lèi)依據(jù)（1）保密內(nèi)容（2）密鑰數(shù)量（3）明文處理方式按保密內(nèi)容來(lái)分

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

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

A、對(duì)稱(chēng)密碼算法（symmetriccipher)：?jiǎn)蚊艽a體制

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

B、非對(duì)稱(chēng)密鑰算法（asymmetriccipher)：雙密碼體制

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

不存在密鑰交換問(wèn)題。

Ke不需要保密，可以公開(kāi);只有Kd需要保密

按明文處理方式

A、分組密碼（blockcipher)

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

B、流密碼（streamcipher)

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

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

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

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

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

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

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

（1）無(wú)條件安全（Unconditionallysecure）

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

Onetimepad：一次一密；

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

1、羊皮密碼

2、替代密碼

3、置換密碼

4、一次一密方案

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

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

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

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

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

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

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

密文:defghijklmnopqrstuvwxyzabc

例：明文caeserwasagreatleader

密文geiwivaewekviexpiehiv

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

對(duì)愷撒密碼：a=1,b=3,n=26

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

(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è)單表替代密碼構(gòu)成。一個(gè)字母在不同位置上被替換成不同的密文字母。典型的Vigenere密碼

Vigenere形式化描述：

t個(gè)密文本，加密為：

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

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

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

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

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

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

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

A.密鑰是真正的隨機(jī)序列

B.密鑰長(zhǎng)度至少等于明文長(zhǎng)度

C.一個(gè)密鑰只用一次

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

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

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

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

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