第2章-密碼學基礎(chǔ)

1、密碼學基礎(chǔ)主講人：王弈E-mail: n密碼學基本概念 n對稱密碼體制 n公鑰密碼體制 n散列函數(shù) n數(shù)字簽名n信息隱藏與數(shù)字水印n無線網(wǎng)絡(luò)中的密碼應用 密碼學Crypology密碼編碼學Crypography密碼分析學Cryptoanalysis對稱密碼體制Sysmetic-key公鑰密碼體制Public-key安全協(xié)議Protocols流密碼Steam cipher分組密碼Block ciphern現(xiàn)代密碼系統(tǒng)(通常簡稱為密碼體制)一般由五個部分組成：明文空間M 密文空間C 密鑰空間K 加密算法E 解密算法D n則五元組（M，C，K，E，D）稱為一個密碼體制。n對稱密鑰體制：n非對稱密鑰體

2、制n根據(jù)密碼算法對明文信息的加密方式，對稱密碼體制常分為兩類：分組密碼(Block cipher，也叫塊密碼)DES、IDEA 、 BLOWFISH 序列密碼(Stream cipher，也叫流密碼)。A5 、FISH 、PIKE n當明文中的字符變化時，截取者不能預知密文會有何變化。我們把這種特性稱為混亂性(Confusion)。n混亂性好的算法，其明文、密鑰對和密文之間有著復雜的函數(shù)關(guān)系。這樣，截取者就要花很長時間才能確定明文、密鑰和密文之間的關(guān)系，從而要花很長的時間才能破譯密碼。n密碼還應該把明文的信息擴展到整個密文中去，這樣，明文的變化就可以影響到密文的很多部分，該原則稱為擴散性(Di

3、fusion)。n這是一種將明文中單一字母包含的信息散布到整個輸出中去的特性。好的擴散性意味著截取者需要獲得很多密文，才能去推測算法。又稱作蠻力攻擊，是指密碼分析者用試遍所有密鑰的方法來破譯密碼對可能的密鑰或明文的窮舉。指密碼分析者通過分析密文和明文的統(tǒng)計規(guī)律來破譯密碼。指密碼分析者針對加密算法的數(shù)學依據(jù)，通過數(shù)學求解的方法來破譯密碼。 根據(jù)密碼分析者掌握明、密文的程度密碼分析可分類為：僅根據(jù)密文進行的密碼攻擊。根據(jù)一些相應的明、密文對進行的密碼攻擊?？梢赃x擇一些明文，并獲取相應的密文，這是密碼分析者最理想的情形。例如，在公鑰體制中。密碼分析者能選擇不同的被加密的密文，并可得到對應的解密的明文

4、，密碼分析者的任務(wù)是推出密鑰。這種攻擊并不表示密碼分析者能夠選擇密鑰，它只表示密碼分析者具有不同密鑰之間關(guān)系的有關(guān)知識。 ：密碼分析者威脅、勒索，或者折磨某人，直到他給出密鑰為止。n理論上，除一文一密外，沒有絕對安全的密碼體制，通常，稱一個密碼體制是安全的是指計算上安全的，即：密碼分析者為了破譯密碼，窮盡其時間、存儲資源仍不可得，或破譯所耗資材已超出因破譯而獲得的獲益。經(jīng)典的密碼體制中，加密密鑰與解密密鑰是相同的，或者可以簡單相互推導，也就是說：知道了加密密鑰，也就知道了解密密鑰；知道了解密密鑰，也就知道了加密密鑰。所以，加、解密密鑰必須同時保密。這種密碼體制稱為最典型的是DES數(shù)據(jù)加密標準，

5、應該說數(shù)據(jù)加密標準DES是單鑰體制的最成功的例子。n1973.5.15： 美國國家標準局（NSA）公開征求密碼體制的聯(lián)邦注冊；n1975.3.17：DES首次在聯(lián)邦記事公開，它由IBM開發(fā)，它是LUCIFER的改進；n1977.2.15：DES被采用作為非國家機關(guān)使用的數(shù)據(jù)加密標準，此后，大約每五年對DES進行依次審查，1992年是最后一次審查，美國政府已聲明，1998年后對DES不再審查了；n1977.2.15：聯(lián)邦信息處理標準版46（FIPS PUB46）給出了DES的完整描述。nDES密碼體制：它是應用56位密鑰，加密64比特明文分組的分組秘鑰密碼體制nDES加密算法：（一）初始置換：x

6、0=L0R0=IP(x)；（二）16次迭代：xi-1=Li-1Ri-1， Li=Ri，Ri=Li f(Ri-1,ki) i=1,2,16；（三）逆置換：x16=L16R16，y=IP-1(x16)。n密鑰生成器：密鑰ki是由56位系統(tǒng)密鑰k生成的32位子密鑰。n函數(shù)f及S盒：f(Ri-1,ki)=P(S(E(Ri-1)ki)其中E，P是兩個置換， 表示比特的“異或”，S是一組八個變換S1，S2，S3， ，S8 ，稱為S盒，每個盒以6位輸入，4位輸出，S盒構(gòu)成了DES 安全的核心。nDES算法流程圖nS盒是唯一非線性組件：有人認為其中可能含有某種“陷門”，國家安全機關(guān)可以解密。nDES的密鑰量太

7、?。好荑€量為256n1977年：Diffie.Hellman提出制造一個每秒測試106的VLSI芯片，則一天就可以搜索完整個密鑰空間，當時造價2千萬美圓。nCRYPTO93：R.Session，M.Wiener提出并行密鑰搜索芯片，每秒測試5x107個密鑰，5760片這種芯片，造價10萬美元，平均一天即可找到密鑰。nInternet的超級計算能力：1997年1月28日，美國RSA數(shù)據(jù)安全公司在Internet上開展了一項“秘密密鑰挑戰(zhàn)”的競賽，懸賞一萬美圓，破解一段DES密文。計劃公布后，得到了許多網(wǎng)絡(luò)用戶的強力相應?？屏_拉州的程序員R.Verser設(shè)計了一個可以通過互聯(lián)網(wǎng)分段運行的密鑰搜索程

8、序，組織了一個稱為DESCHALL的搜索行動，成千上萬的的志愿者加入到計劃中。n第96天，即競賽公布后的第140天，1997年6月17日晚上10點39分，美國鹽湖城Inetz公司職員M.Sanders成功地找到了密鑰，解密出明文：The unknown Message is：“Stronge cryptography makes the word a safer place”(高強度密碼技術(shù)使世界更安全)。 Internet僅僅利用閑散資源，毫無代價就破譯了DES密碼，這是對密碼方法的挑戰(zhàn)，是Internet超級計算能力的顯示.n差分分析法：除去窮舉搜索密鑰外，還有其他形式的攻擊方法，最著名的

9、有Biham，Shamir的差分分析法。這是一個選擇明文攻擊方法。雖然對16輪DES沒有攻破，但是，如果迭代的輪數(shù)降低，則它可成功地被攻破。例如，8輪DES在一個個人計算機上只需要2分鐘即可被攻破。n在攻擊面前，雖然多重DES表現(xiàn)良好。不過，考慮到計算機能力的持續(xù)增長，人們需要一種新的、更加強有力的加密算法。1995年，美國國家標準技術(shù)研究所NIST開始尋找這種算法。最終，美國政府采納了由密碼學家Rijmen和Daemen發(fā)明的Rijindael算法，使其成為了高級加密標準AES(Advanced Encryption Standard)。nRijindael算法之所以最后當選，是因為它集安全

10、性、效率、可實現(xiàn)性及靈活性于一體。nAES算法是具有分組長度和密鑰長度均可變的多輪迭代型加密算法。分組長度一般為128比特位，密鑰長度可以是128/192/256位。實際上，AES算法的密鑰長度可以擴展為64的任意整數(shù)倍，盡管AES標準中只有128，192和256被認可。nAES的128位塊可以很方便地考慮成一個44矩陣，這個矩陣稱為“狀態(tài)”(state)。例如，假設(shè)輸入為16字節(jié)b0,b1,b15，這些字節(jié)在狀態(tài)中的位置及其用矩陣的表示如表2-8所示。注意，這些狀態(tài)用輸入數(shù)據(jù)逐列填充。保護信息機密 認證發(fā)送方之身份 確保信息完整性 收發(fā)雙方如何獲得其加密密鑰及解密密鑰？ 密鑰的數(shù)目太大 無法

11、達到不可否認服務(wù) n現(xiàn)代密碼學修正了密鑰的對稱性，1976年，Diffie，Hellmann提出了公開密鑰密碼體制提出了公開密鑰密碼體制（簡稱公鑰體制）（簡稱公鑰體制），它的加密、解密密鑰是不同的，也是不能（在有效的時間內(nèi)）相互推導。所以，它可稱為雙鑰密碼體制雙鑰密碼體制。它的產(chǎn)生，是密碼學革命性的發(fā)展，它一方面，為數(shù)據(jù)的保密性、完整性、真實性提供了有效方便的技術(shù)。另一方面，科學地解決了密碼技術(shù)的瓶頸密鑰的分配問題。 nRSA公鑰體制已得到了廣泛的應用。其后，諸如基于背包問題的Merkle-Hellman背包公鑰體制，基于有限域上離散對數(shù)問題的EIGamal公鑰體制，基于橢圓曲線的密碼體制等等

12、公鑰體制不斷出現(xiàn)，使密碼學得到了蓬勃的發(fā)展。 n 公鑰體制用于數(shù)據(jù)加密時：用戶將自己的公開（加密）密鑰登記在一個公開密鑰庫或?qū)崟r公開，秘密密鑰則被嚴格保密。信源為了向信宿發(fā)送信息，去公開密鑰庫查找對方的公開密鑰，或臨時向?qū)Ψ剿魅」€，將要發(fā)送的信息用這個公鑰加密后在公開信道上發(fā)送給對方，對方收到信息（密文）后，則用自己的秘密（解密）密鑰解密密文，從而，讀取信息?？梢?，這里省去了從秘密信道傳遞密鑰的過程。這是公鑰體制的一大優(yōu)點。 n任何人均可將明文加密成密文，此后只有擁有解密密鑰的人才能解密。 n公鑰體制用于數(shù)字簽名時：n信源為了他人能夠驗證自己發(fā)送的消息確實來自本人，他將自己的秘密（解密）密鑰

13、公布，而將公開（加密）密鑰嚴格保密。與別人通信時，則用自己的加密密鑰對消息加密稱為簽名，將原消息與簽名后的消息一起發(fā)送.n對方收到消息后，為了確定信源的真實性，用對方的解密密鑰解密簽名消息稱為（簽名）驗證，如果解密后的消息與原消息一致，則說明信源是真實的，可以接受，否則，拒絕接受。 Diffie，Hellman在“New Direction in Cryptography”(密碼學新方向)一文中首次提出公開密鑰密碼體制的思想。Rivest,Shamir,Adleman第一次實現(xiàn)了公開密鑰密碼體制，現(xiàn)稱為RSA公鑰體制。n散列函數(shù)沒有密鑰，散列函數(shù)就是把可變輸入長度串(叫做預映射，Pre-ima

14、ge)轉(zhuǎn)換成固定長度輸出串(叫做散列值)的一種函數(shù)。n散列函數(shù)又可稱為壓縮函數(shù)、雜湊函數(shù)、消息摘要、指紋、密碼校驗和、信息完整性檢驗(DIC)、操作認證碼(Message Authentication Code，MAC)。（1）它能處理任意大小的信息，并將其信息摘要生成固定大小的數(shù)據(jù)塊(例如128位，即16字節(jié))，對同一個源數(shù)據(jù)反復執(zhí)行Hash函數(shù)將總是得到同樣的結(jié)果。（2）它是不可預見的。產(chǎn)生的數(shù)據(jù)塊的大小與原始信息的大小沒有任何聯(lián)系，同時源數(shù)據(jù)和產(chǎn)生的數(shù)據(jù)塊的數(shù)據(jù)看起來沒有明顯關(guān)系，但源信息的一個微小變化都會對數(shù)據(jù)塊產(chǎn)生很大的影響。（3）它是完全不可逆的，即散列函數(shù)是單向的，從預映射的值很

15、容易計算其散列值，沒有辦法通過生成的散列值恢復源數(shù)據(jù)。（4）它是抗碰撞的，即尋找兩個輸入得到相同的輸出值在計算上是不可行的。n假設(shè)單向散列函數(shù)H(M)作用于任意長度的消息M，它返回一個固定長度的散列值h，其中h的長度為定數(shù)m，該函數(shù)必須滿足如下特性：給定M，很容易計算h；給定h，計算M很難；給定M，要找到另一消息M并滿足H(M)=H(M)很難。（1）MD2算法（2）MD4和MD5算法（3）SHA算法（4）RIPEMD算法nSHA (Secure Hash Algorithm)由美國國家標準和技術(shù)局NIST設(shè)計，1993年被作為聯(lián)邦信息處理標準(FIPS PUB 180)公布，1995年又公布了修訂版FIPS PUB 180-1，通常稱為SHA-1。n就當前的情況來看，SHA-1由于其安全強度及運算效率方面的優(yōu)勢已經(jīng)成為使用最為廣泛的散列函數(shù)。n該算法輸入消息的最大長度為264-1位，產(chǎn)生的輸出是一個160位的消息摘要。輸入按512 位的分組進行處理。n數(shù)字簽名最早被建議用來對禁止核試驗條律的驗證。禁止核試驗條律的締約國為了檢測對方的核試驗，需要把地震測