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

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

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

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

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

5、應(yīng)該說數(shù)據(jù)加密標(biāo)準(zhǔn)DES是單鑰體制的最成功的例子。n1973.5.15： 美國(guó)國(guó)家標(biāo)準(zhǔn)局（NSA）公開征求密碼體制的聯(lián)邦注冊(cè)；n1975.3.17：DES首次在聯(lián)邦記事公開，它由IBM開發(fā)，它是LUCIFER的改進(jìn)；n1977.2.15：DES被采用作為非國(guó)家機(jī)關(guān)使用的數(shù)據(jù)加密標(biāo)準(zhǔn)，此后，大約每五年對(duì)DES進(jìn)行依次審查，1992年是最后一次審查，美國(guó)政府已聲明，1998年后對(duì)DES不再審查了；n1977.2.15：聯(lián)邦信息處理標(biāo)準(zhǔn)版46（FIPS PUB46）給出了DES的完整描述。nDES密碼體制：它是應(yīng)用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是兩個(gè)置換， 表示比特的“異或”，S是一組八個(gè)變換S1，S2，S3， ，S8 ，稱為S盒，每個(gè)盒以6位輸入，4位輸出，S盒構(gòu)成了DES 安全的核心。nDES算法流程圖nS盒是唯一非線性組件：有人認(rèn)為其中可能含有某種“陷門”，國(guó)家安全機(jī)關(guān)可以解密。nDES的密鑰量太

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

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

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

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

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

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

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

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

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