密碼學(xué)及安全應(yīng)用2_2

1、第二章 密碼學(xué)基礎(chǔ)http:/http:/目錄v2.5公鑰密碼體制解決的問題公鑰密碼體制解決的問題v2.6 數(shù)字信封數(shù)字信封v2.7 單向散列函數(shù)單向散列函數(shù)http:/http:/2.5 公鑰密碼體制解決的問題對(duì)稱密碼體制已經(jīng)能夠?qū)π畔⑦M(jìn)行加密，對(duì)稱密碼體制已經(jīng)能夠?qū)π畔⑦M(jìn)行加密，為什么還需要公鑰密碼體制呢？為什么還需要公鑰密碼體制呢？公鑰密碼體制僅僅比對(duì)稱密鑰密碼體制多用公鑰密碼體制僅僅比對(duì)稱密鑰密碼體制多用了一個(gè)密鑰而已嗎，兩個(gè)密鑰好在哪里呢？了一個(gè)密鑰而已嗎，兩個(gè)密鑰好在哪里呢？思考http:/http:/公鑰密碼體制解決的問題v密鑰分配密鑰分配 v密碼系統(tǒng)密鑰管理問題密碼系統(tǒng)密鑰管理

2、問題 v數(shù)字簽名問題數(shù)字簽名問題http:/http:/2.5.1 密鑰分配用密鑰用密鑰K加密的密文加密的密文生成密鑰生成密鑰K攻擊者攻擊者接收方接收方B發(fā)送方發(fā)送方A明文可能被竊聽明文可能被竊聽信息的明文信息的明文信息是否安全了呢信息是否安全了呢密文加密后可防止被竊取密文加密后可防止被竊取http:/http:/發(fā)送方生成密鑰加密明文v問題：密鑰問題：密鑰K可能被竊取可能被竊取用密鑰用密鑰K加密的密文加密的密文密鑰密鑰K（明文形式）（明文形式）生成密鑰生成密鑰K攻擊者攻擊者接收方接收方B發(fā)送方發(fā)送方A問題：密鑰可能被竊取問題：密鑰可能被竊取http:/http:/改進(jìn)第一步：接收方生成密鑰v

3、改進(jìn)傳遞加密信息的過程（第一步）改進(jìn)傳遞加密信息的過程（第一步） 用密鑰用密鑰K加密的密文加密的密文密鑰密鑰K（明文形式）（明文形式）生成密鑰生成密鑰K攻擊者攻擊者接收方接收方B發(fā)送方發(fā)送方A竊取密鑰為了解密竊取密鑰為了解密使發(fā)送方和攻擊者獲取密鑰的目的不同。使發(fā)送方和攻擊者獲取密鑰的目的不同。獲得密鑰為了加密獲得密鑰為了加密http:/http:/改進(jìn)第二步：接收方生成公鑰用公鑰用公鑰KUB加密的密文加密的密文公鑰公鑰KUB:明文形式明文形式生成生成公鑰公鑰KUB和私鑰和私鑰KRB攻擊者攻擊者接收方接收方B發(fā)送方發(fā)送方A公鑰被竊取也不能解密公鑰被竊取也不能解密http:/http:/總結(jié)v解

4、決密鑰分配問題的關(guān)鍵有兩點(diǎn)：解決密鑰分配問題的關(guān)鍵有兩點(diǎn)：w 第一，線路上傳輸?shù)谋仨毷枪€；第一，線路上傳輸?shù)谋仨毷枪€；w 第二，這個(gè)公鑰必須是接收方的。第二，這個(gè)公鑰必須是接收方的。提示：如果提示：如果A、B雙方需要使用公鑰加密算法相雙方需要使用公鑰加密算法相互發(fā)送加密的信息給對(duì)方，則需要互發(fā)送加密的信息給對(duì)方，則需要兩對(duì)公兩對(duì)公/私鑰私鑰，即即A用用B的公鑰加密信息發(fā)送給的公鑰加密信息發(fā)送給B，B用用A的公鑰的公鑰加密信息發(fā)送給加密信息發(fā)送給A。 http:/http:/v這樣，發(fā)送方用接收方的公鑰加密信息，接收方這樣，發(fā)送方用接收方的公鑰加密信息，接收方用該公鑰對(duì)應(yīng)的私鑰解密信息，攻擊

5、者即使截獲用該公鑰對(duì)應(yīng)的私鑰解密信息，攻擊者即使截獲公鑰也不能解密信息。公鑰也不能解密信息。 v但要防止接收方的公鑰被假冒但要防止接收方的公鑰被假冒v即攻擊者也生成一對(duì)公私鑰，然后把自己的公鑰即攻擊者也生成一對(duì)公私鑰，然后把自己的公鑰Ku冒充接收方冒充接收方B的公鑰的公鑰Ku發(fā)給發(fā)送方，發(fā)送方發(fā)給發(fā)送方，發(fā)送方?jīng)]有察覺，于是用該假冒的公鑰沒有察覺，于是用該假冒的公鑰Ku加密信息，加密信息，攻擊者就能用其對(duì)應(yīng)的私鑰攻擊者就能用其對(duì)應(yīng)的私鑰Kr解密該信息了。解密該信息了。 要防止攻擊者假冒公鑰http:/http:/攻擊者假冒公鑰用公鑰用公鑰KUB加密加密的密文的密文假冒的公鑰假冒的公鑰KUB生成

6、公鑰生成公鑰KUB和私和私鑰鑰KRB攻擊者攻擊者接收方接收方B發(fā)送方發(fā)送方A生成公鑰生成公鑰KUB和私鑰和私鑰KRB竊取竊取KUB加密的密文加密的密文http:/http:/公鑰的特殊要求v公鑰雖然不需要保密，但需要保證其真實(shí)性公鑰雖然不需要保密，但需要保證其真實(shí)性v常用手段：常用手段：數(shù)字證書數(shù)字證書http:/http:/本節(jié)提綱v密鑰分配密鑰分配 v密碼系統(tǒng)密鑰管理問題密碼系統(tǒng)密鑰管理問題 v數(shù)字簽名問題數(shù)字簽名問題http:/http:/對(duì)稱密碼系統(tǒng)需要的密鑰數(shù)v思考：在一個(gè)密碼系統(tǒng)中，用戶通常不止思考：在一個(gè)密碼系統(tǒng)中，用戶通常不止A和和B兩個(gè)人，有時(shí)候有幾千人之間要相互發(fā)送加密兩個(gè)

7、人，有時(shí)候有幾千人之間要相互發(fā)送加密信息，能否使用對(duì)稱密鑰進(jìn)行操作呢？信息，能否使用對(duì)稱密鑰進(jìn)行操作呢？ v假設(shè)假設(shè)A要與兩個(gè)人（要與兩個(gè)人（B和和C）安全通信，）安全通信，A能否用能否用同一個(gè)密鑰處理與同一個(gè)密鑰處理與B和與和與C的消息？的消息？v當(dāng)然，這是不行的，否則怎么保證當(dāng)然，這是不行的，否則怎么保證B不會(huì)打開不會(huì)打開A給給C的信，的信，C不會(huì)打開不會(huì)打開A給給B的信？的信？ http:/http:/對(duì)稱密碼系統(tǒng)需要的密鑰數(shù)v因此，因此，A為了和兩個(gè)人安全通信，必須使用兩個(gè)為了和兩個(gè)人安全通信，必須使用兩個(gè)密鑰（密鑰（KAB與與KAC），如果），如果B要與要與C通信，則要另通信，則要另

8、一個(gè)密鑰（一個(gè)密鑰（KBC），因此三方通信的話需要），因此三方通信的話需要3個(gè)個(gè)密鑰。密鑰。v對(duì)稱密碼系統(tǒng)有對(duì)稱密碼系統(tǒng)有n人需要安全通信時(shí)，這人需要安全通信時(shí)，這n人中人中兩兩之間需要一個(gè)密鑰，需要的密鑰數(shù)是：兩兩之間需要一個(gè)密鑰，需要的密鑰數(shù)是：v密鑰數(shù)與參與通信人數(shù)的平方成正比密鑰數(shù)與參與通信人數(shù)的平方成正比 2) 1(2nnCnhttp:/http:/公鑰密碼系統(tǒng)需要的密鑰數(shù)v采用公鑰密碼系統(tǒng)，假設(shè)采用公鑰密碼系統(tǒng)，假設(shè)A要與要與n個(gè)人進(jìn)行安全個(gè)人進(jìn)行安全通信，他只需把他的公鑰發(fā)布出去通信，他只需把他的公鑰發(fā)布出去v。v也就是說，也就是說，A與與n人之間安全通信，只需要一對(duì)人之間安全通

9、信，只需要一對(duì)密鑰，同樣，密鑰，同樣，B與與n人之間安全通信，也只需要人之間安全通信，也只需要一對(duì)密鑰。一對(duì)密鑰。 v對(duì)于公鑰密碼系統(tǒng)，有對(duì)于公鑰密碼系統(tǒng)，有n人之間需要相互安全通人之間需要相互安全通信時(shí)，只需要信時(shí)，只需要n對(duì)密鑰對(duì)密鑰即可，即可，密鑰量大大減少密鑰量大大減少。 v這這n對(duì)密鑰中的私鑰由用戶自己保存，公鑰由專對(duì)密鑰中的私鑰由用戶自己保存，公鑰由專門的公鑰管理機(jī)構(gòu)保管和分發(fā)。門的公鑰管理機(jī)構(gòu)保管和分發(fā)。http:/http:/兩種系統(tǒng)密鑰管理的比較v公鑰密碼系統(tǒng)所需管理的密鑰數(shù)（公鑰密碼系統(tǒng)所需管理的密鑰數(shù)（n對(duì)）比對(duì)稱對(duì)）比對(duì)稱密碼系統(tǒng)所需的密鑰數(shù)（密碼系統(tǒng)所需的密鑰數(shù)（n2

10、個(gè)）大大減少個(gè)）大大減少v對(duì)稱密碼系統(tǒng)和公鑰密碼系統(tǒng)都需要一個(gè)密鑰對(duì)稱密碼系統(tǒng)和公鑰密碼系統(tǒng)都需要一個(gè)密鑰分配中心（分配中心（KDC）。因此，不要誤認(rèn)為公鑰密）。因此，不要誤認(rèn)為公鑰密碼技術(shù)使得密鑰管理非常簡(jiǎn)單，事實(shí)上，仍需碼技術(shù)使得密鑰管理非常簡(jiǎn)單，事實(shí)上，仍需要一個(gè)代理中心。只是它需要管理的密鑰可以要一個(gè)代理中心。只是它需要管理的密鑰可以大大減少大大減少http:/http:/本節(jié)提綱v密鑰分配密鑰分配 v密碼系統(tǒng)密鑰管理問題密碼系統(tǒng)密鑰管理問題 v數(shù)字簽名問題數(shù)字簽名問題http:/http:/2.5.3 數(shù)字簽名問題v公鑰密碼算法的加密機(jī)制是：公鑰密碼算法的加密機(jī)制是：v下面考慮另外一

11、種機(jī)制：下面考慮另外一種機(jī)制：vA的公鑰是公開的，從而無法實(shí)現(xiàn)保密性。的公鑰是公開的，從而無法實(shí)現(xiàn)保密性。 如果如果A是發(fā)送方，是發(fā)送方，B是接收方，則是接收方，則A用用B的公的公鑰加密信息，并將其發(fā)送給鑰加密信息，并將其發(fā)送給B如果如果A是發(fā)送方，是發(fā)送方，B是接收方，則是接收方，則A用用A的私的私鑰加密信息，并將其發(fā)送給鑰加密信息，并將其發(fā)送給Bhttp:/http:/數(shù)字簽名的基本原理 A的私鑰的私鑰發(fā)送方發(fā)送方A明明文文-密密文文加密加密A的公鑰的公鑰接收方接收方B明明文文密密文文解密解密http:/http:/實(shí)現(xiàn)消息認(rèn)證v接收方用接收方用A的公鑰解密，如果解密成功，則的公鑰解密，如

12、果解密成功，則B可可以斷定這個(gè)消息是以斷定這個(gè)消息是A發(fā)來的。發(fā)來的。v因?yàn)?，用因?yàn)?，用A的私鑰加密的信息只能用的私鑰加密的信息只能用A的公鑰解的公鑰解密，反過來說，用密，反過來說，用A的公鑰能解密成功就證明消的公鑰能解密成功就證明消息一定是用息一定是用A的私鑰加密的。的私鑰加密的。http:/http:/實(shí)現(xiàn)不可抵賴性v如果今后發(fā)生爭(zhēng)議，如果今后發(fā)生爭(zhēng)議，A也無法否認(rèn)自己發(fā)了消息，也無法否認(rèn)自己發(fā)了消息，因?yàn)橐驗(yàn)锽可以拿出加密信息，用可以拿出加密信息，用A 的公鑰解密，從的公鑰解密，從而證明這個(gè)消息是而證明這個(gè)消息是A發(fā)來的。發(fā)來的。http:/http:/總結(jié)：數(shù)字簽名的作用v消息認(rèn)證消息

13、認(rèn)證：證實(shí)某個(gè)消息確實(shí)是某用戶發(fā)：證實(shí)某個(gè)消息確實(shí)是某用戶發(fā)出的。出的。v實(shí)現(xiàn)不可抵賴性實(shí)現(xiàn)不可抵賴性：消息的發(fā)送方不能否認(rèn)：消息的發(fā)送方不能否認(rèn)他曾經(jīng)發(fā)過該消息。他曾經(jīng)發(fā)過該消息。v完整性保證完整性保證：如果消息能夠用公鑰解密成：如果消息能夠用公鑰解密成功，還可確信消息在傳輸過程中沒有被篡功，還可確信消息在傳輸過程中沒有被篡改過。改過。 http:/http:/v2.5公鑰密碼體制解決的問題公鑰密碼體制解決的問題v2.6 數(shù)字信封數(shù)字信封v2.7 單向散列函數(shù)單向散列函數(shù)目錄http:/http:/公鑰密碼體制的優(yōu)缺點(diǎn)v公鑰密碼體制公鑰密碼體制存在一個(gè)嚴(yán)重的缺點(diǎn)，就是存在一個(gè)嚴(yán)重的缺點(diǎn)，就是

14、加、解密速度很慢加、解密速度很慢例如：例如：512比特模數(shù)的比特模數(shù)的RSA算法與算法與DES算法相算法相比，用軟件實(shí)現(xiàn)的話比，用軟件實(shí)現(xiàn)的話RSA大約比大約比DES慢慢1000倍，倍，用硬件實(shí)現(xiàn)的話用硬件實(shí)現(xiàn)的話RSA大約比大約比DES慢慢1500倍倍http:/http:/對(duì)稱密鑰加密與公鑰加密比較 特征特征對(duì)稱密鑰加密對(duì)稱密鑰加密公鑰加密公鑰加密加密加密/解密所用解密所用的密鑰的密鑰相同相同不同不同加密加密/解密速度解密速度 快快慢慢得到的密文長(zhǎng)得到的密文長(zhǎng)度度通常等于或小于明通常等于或小于明文長(zhǎng)度文長(zhǎng)度大于明文長(zhǎng)度大于明文長(zhǎng)度密鑰分配密鑰分配大問題大問題沒問題沒問題系統(tǒng)所需密鑰系統(tǒng)所需

15、密鑰總數(shù)總數(shù)大約為參與者的平大約為參與者的平方個(gè)方個(gè)等于參與者的個(gè)數(shù)等于參與者的個(gè)數(shù)用法用法主要用于加密主要用于加密/解解密密主要用于加密會(huì)話密鑰，主要用于加密會(huì)話密鑰，數(shù)字簽名數(shù)字簽名http:/http:/數(shù)字信封（混合密碼體制）v數(shù)字信封數(shù)字信封用一個(gè)對(duì)稱密鑰加密明文，而用公用一個(gè)對(duì)稱密鑰加密明文，而用公鑰密碼體制的公鑰加密這個(gè)對(duì)稱密鑰鑰密碼體制的公鑰加密這個(gè)對(duì)稱密鑰v這樣就既能使加密有很高的效率，又不必?fù)?dān)心對(duì)這樣就既能使加密有很高的效率，又不必?fù)?dān)心對(duì)稱密鑰在傳輸中被竊取，實(shí)現(xiàn)了兩全其美的效果稱密鑰在傳輸中被竊取，實(shí)現(xiàn)了兩全其美的效果v具體是：信息發(fā)送方具體是：信息發(fā)送方A首先利用隨機(jī)產(chǎn)

16、生的對(duì)稱首先利用隨機(jī)產(chǎn)生的對(duì)稱密鑰加密信息，再利用接收方密鑰加密信息，再利用接收方B的公鑰加密該對(duì)的公鑰加密該對(duì)稱密鑰，被公鑰加密后的對(duì)稱密鑰被稱之為稱密鑰，被公鑰加密后的對(duì)稱密鑰被稱之為數(shù)字?jǐn)?shù)字信封信封。http:/http:/數(shù)字信封的工作過程 v在實(shí)際中，公鑰密碼體制更多的用來加密對(duì)稱在實(shí)際中，公鑰密碼體制更多的用來加密對(duì)稱密碼體制的密鑰，而不是加密普通的明文信息。密碼體制的密鑰，而不是加密普通的明文信息。明文信息一般用對(duì)稱密鑰加密。此時(shí)對(duì)稱密鑰明文信息一般用對(duì)稱密鑰加密。此時(shí)對(duì)稱密鑰也被稱為也被稱為會(huì)話密鑰會(huì)話密鑰該會(huì)話密鑰需要經(jīng)常更換。該會(huì)話密鑰需要經(jīng)常更換。 發(fā)送方發(fā)送方A接收方接

17、收方B對(duì)稱對(duì)稱密鑰密鑰對(duì)稱對(duì)稱密鑰密鑰明文密文加密加密A的公鑰明文解密解密接收方接收方公鑰公鑰加密加密密文接收方接收方私鑰私鑰解密數(shù)字?jǐn)?shù)字信封信封http:/http:/v2.5公鑰密碼體制解決的問題公鑰密碼體制解決的問題v2.6 數(shù)字信封數(shù)字信封v2.7 單向散列函數(shù)單向散列函數(shù)目 錄http:/http:/不可逆加密體制v不可逆加密體制又稱為不可逆加密體制又稱為單向密碼體制單向密碼體制，它是一，它是一種從明文到密文的不可逆變換，種從明文到密文的不可逆變換，v通常在明文到密文的轉(zhuǎn)換中存在信息的損失，通常在明文到密文的轉(zhuǎn)換中存在信息的損失，因此密文無法恢復(fù)成明文，實(shí)現(xiàn)不可逆密碼體因此密文無法恢

18、復(fù)成明文，實(shí)現(xiàn)不可逆密碼體制的方法是通過制的方法是通過單向散列函數(shù)單向散列函數(shù)。v單向散列函數(shù)用于某些只需要加密、不需要解單向散列函數(shù)用于某些只需要加密、不需要解密的特殊場(chǎng)合，例如密的特殊場(chǎng)合，例如:w 文件完整性保證文件完整性保證w 口令存儲(chǔ)口令存儲(chǔ)http:/http:/單向散列函數(shù)的性質(zhì) 函數(shù)的輸入（明文）可以是任意長(zhǎng)度；函數(shù)的輸入（明文）可以是任意長(zhǎng)度； 函數(shù)的輸出（密文）是固定長(zhǎng)度的；函數(shù)的輸出（密文）是固定長(zhǎng)度的； 已知明文已知明文m，求，求H(m)較為容易，可用硬件或軟件實(shí)現(xiàn)；較為容易，可用硬件或軟件實(shí)現(xiàn)； 已知散列值已知散列值h，求使得，求使得H(m)=h的明文的明文m在計(jì)算上

19、是不可行在計(jì)算上是不可行的，這一性質(zhì)稱為函數(shù)的單向性，稱的，這一性質(zhì)稱為函數(shù)的單向性，稱H(m)為單向散列函為單向散列函數(shù)；數(shù)； 散列函數(shù)具有防偽造性（又稱弱抗沖突性），即已知散列函數(shù)具有防偽造性（又稱弱抗沖突性），即已知m，找出找出m(mm)使得使得H(m)=H(m)在計(jì)算上是不可行的；在計(jì)算上是不可行的； 散列函數(shù)具有很好的抵抗攻擊的能力（又稱強(qiáng)抗沖突散列函數(shù)具有很好的抵抗攻擊的能力（又稱強(qiáng)抗沖突性），即找出任意兩個(gè)不同的輸入性），即找出任意兩個(gè)不同的輸入x、y，使得，使得H(y)=H(x)在計(jì)算上是不可行的。在計(jì)算上是不可行的。http:/http:/單向散列函數(shù)的性質(zhì)和種類v提示：強(qiáng)抗

20、沖突性自然包含弱抗沖突性。提示：強(qiáng)抗沖突性自然包含弱抗沖突性。v第第和第和第個(gè)條件給出了散列函數(shù)無碰撞性的個(gè)條件給出了散列函數(shù)無碰撞性的概念，如果散列函數(shù)對(duì)不同的輸入可產(chǎn)生相同概念，如果散列函數(shù)對(duì)不同的輸入可產(chǎn)生相同的輸出，則稱該函數(shù)具有碰撞性的輸出，則稱該函數(shù)具有碰撞性collision。v常見的單向散列函數(shù)有常見的單向散列函數(shù)有MD5和和SHA-1，散列函，散列函數(shù)的安全性主要來源于它的單向性。數(shù)的安全性主要來源于它的單向性。http:/http:/散列函數(shù)算法被破解的含義vMD5的散列碼長(zhǎng)度是的散列碼長(zhǎng)度是128比特，而比特，而SHA-1的散列的散列碼長(zhǎng)度是碼長(zhǎng)度是160比特。近年來有報(bào)

21、道稱已可以在比特。近年來有報(bào)道稱已可以在24小時(shí)內(nèi)找到小時(shí)內(nèi)找到MD5的一個(gè)沖突，使得的一個(gè)沖突，使得MD5對(duì)于不對(duì)于不同的輸入有相同的輸出結(jié)果，因此說同的輸入有相同的輸出結(jié)果，因此說MD5算法算法已經(jīng)被破解。已經(jīng)被破解。v注意：注意：說說MD5算法被破解，只是說可以通過密算法被破解，只是說可以通過密文找到與明文有相同散列值的一個(gè)碰撞，而絕文找到與明文有相同散列值的一個(gè)碰撞，而絕不是說可以將不是說可以將MD5算法加密的密文還原成明文。算法加密的密文還原成明文。 http:/http:/2.7.2 對(duì)散列函數(shù)的攻擊 v由于單向散列函數(shù)接受的輸入長(zhǎng)度是任意的，由于單向散列函數(shù)接受的輸入長(zhǎng)度是任意的

22、，而它的輸出長(zhǎng)度是固定值，因此單向散列函數(shù)而它的輸出長(zhǎng)度是固定值，因此單向散列函數(shù)將帶來數(shù)據(jù)的壓縮，單向散列函數(shù)肯定會(huì)存在將帶來數(shù)據(jù)的壓縮，單向散列函數(shù)肯定會(huì)存在碰撞的可能。碰撞的可能。v如果用單向散列函數(shù)對(duì)消息求散列值，是不希如果用單向散列函數(shù)對(duì)消息求散列值，是不希望發(fā)生碰撞的，否則攻擊者可以把消息修改成望發(fā)生碰撞的，否則攻擊者可以把消息修改成特定的模式，使其和原始消息具有相同的散列特定的模式，使其和原始消息具有相同的散列值，而用戶卻無法通過計(jì)算散列值發(fā)現(xiàn)數(shù)據(jù)已值，而用戶卻無法通過計(jì)算散列值發(fā)現(xiàn)數(shù)據(jù)已經(jīng)被修改經(jīng)被修改 v因此散列函數(shù)又被稱為因此散列函數(shù)又被稱為數(shù)字指紋數(shù)字指紋，就是說一般，就

23、是說一般每個(gè)不同的消息都有其獨(dú)特的散列值。每個(gè)不同的消息都有其獨(dú)特的散列值。 http:/http:/兩類生日攻擊v對(duì)單向散列函數(shù)的攻擊是指找到散列函數(shù)對(duì)不對(duì)單向散列函數(shù)的攻擊是指找到散列函數(shù)對(duì)不同輸入的碰撞，這稱為生日攻擊，它包括兩類，同輸入的碰撞，這稱為生日攻擊，它包括兩類，分別對(duì)應(yīng)攻擊散列函數(shù)的弱抗沖突性和強(qiáng)抗沖分別對(duì)應(yīng)攻擊散列函數(shù)的弱抗沖突性和強(qiáng)抗沖突性突性 v1. 第第類生日攻擊類生日攻擊v2. 第第類生日攻擊（基于生日悖論）類生日攻擊（基于生日悖論）http:/http:/第類生日攻擊 v已知一散列函數(shù)已知一散列函數(shù)H有有n個(gè)可能的輸出，個(gè)可能的輸出，H(x)是一是一個(gè)特定的輸出，

24、如果對(duì)個(gè)特定的輸出，如果對(duì)H隨機(jī)取隨機(jī)取k個(gè)輸入，則至個(gè)輸入，則至少有一個(gè)輸入少有一個(gè)輸入y使得使得H(y)=H(x)的概率為的概率為0.5時(shí)，時(shí)，k有多大？有多大？v由由(1+x)k1+kx，其中，其中|x|1，可得，可得1-1-1/nk1-1-k/n=k/nv 若使上述概率等于若使上述概率等于0.5，則，則k=n/2。特別地，如。特別地，如果果H的輸出為的輸出為m比特長(zhǎng)，即可能的輸出個(gè)數(shù)比特長(zhǎng)，即可能的輸出個(gè)數(shù)n=2m，則則k=2m-1 http:/http:/第類生日攻擊（基于生日悖論）v生日悖論是指：任意找生日悖論是指：任意找23個(gè)人，則他們中有兩個(gè)人，則他們中有兩個(gè)人生日相同的概率會(huì)

25、大于個(gè)人生日相同的概率會(huì)大于50%，如果有，如果有30人，人，則此概率大約為則此概率大約為70%，這比我們憑感覺認(rèn)為的，這比我們憑感覺認(rèn)為的概率要大得多，因此稱為生日悖論。概率要大得多，因此稱為生日悖論。v設(shè)散列函數(shù)設(shè)散列函數(shù)H有有2m個(gè)可能的輸出（即輸出長(zhǎng)為個(gè)可能的輸出（即輸出長(zhǎng)為m比特），如果比特），如果H的的k個(gè)隨機(jī)輸入中至少有兩個(gè)產(chǎn)個(gè)隨機(jī)輸入中至少有兩個(gè)產(chǎn)生相同輸出的概率大于生相同輸出的概率大于0.5，則，則k=2m/2。稱尋找函。稱尋找函數(shù)數(shù)H的具有相同輸出的兩個(gè)任意輸入的攻擊方式的具有相同輸出的兩個(gè)任意輸入的攻擊方式為第為第類生日攻擊。類生日攻擊。 http:/http:/兩類生日

26、攻擊的難度比較v可看出第可看出第類生日攻擊比第類生日攻擊比第類生日攻擊容易，類生日攻擊容易，因?yàn)樗恍枰獙ふ乙驗(yàn)樗恍枰獙ふ?m/2個(gè)輸入。因此抵抗第個(gè)輸入。因此抵抗第類類生日攻擊（對(duì)應(yīng)強(qiáng)抗沖突性）比抵抗第生日攻擊（對(duì)應(yīng)強(qiáng)抗沖突性）比抵抗第類生類生日攻擊（對(duì)應(yīng)弱抗沖突性）要難。日攻擊（對(duì)應(yīng)弱抗沖突性）要難。v例子：針對(duì)散列函數(shù)的第例子：針對(duì)散列函數(shù)的第類生日攻擊的方法類生日攻擊的方法 http:/http:/散列函數(shù)的設(shè)計(jì)及MD5算法v一個(gè)好的散列函數(shù)的設(shè)計(jì)有一些基本原則：一個(gè)好的散列函數(shù)的設(shè)計(jì)有一些基本原則：v1）對(duì)不同的輸入，要盡量不產(chǎn)生相同的散列值）對(duì)不同的輸入，要盡量不產(chǎn)生相同的散列值

27、（抗沖突性抗沖突性）。）。v2）兩個(gè)明文即使只有微小的差別（如只有一位）兩個(gè)明文即使只有微小的差別（如只有一位不同），它們的散列值也會(huì)有很多位都發(fā)生變不同），它們的散列值也會(huì)有很多位都發(fā)生變化（化（擴(kuò)散性擴(kuò)散性），這樣根本不能從散列值看出兩），這樣根本不能從散列值看出兩個(gè)明文的相似性。個(gè)明文的相似性。v3）將明文的長(zhǎng)度信息記錄在散列值中將明文的長(zhǎng)度信息記錄在散列值中，這樣可，這樣可以更好的防止沖突以更好的防止沖突 http:/http:/MD5散列算法http:/http:/散列函數(shù)的分類 v1）帶秘密密鑰的）帶秘密密鑰的Hash函數(shù)函數(shù)：消息的散列值由：消息的散列值由只有通信雙方知道的秘密密鑰只有通信雙方知道的秘密密鑰K來控制。此時(shí)，來控制。此時(shí)，散列碼稱作散列碼稱作MAC（Message Authentication Code，消息認(rèn)證碼），消息認(rèn)證碼） 原文消息摘要MACHash函數(shù)密鑰密鑰khttp:/http:/消息認(rèn)證碼的實(shí)現(xiàn)vMAC的實(shí)現(xiàn)的一個(gè)簡(jiǎn)單方法是先對(duì)消息求散列的實(shí)現(xiàn)的一個(gè)簡(jiǎn)單方法是先對(duì)消息求散列值，再用一個(gè)對(duì)稱