1、第5章 消息認(rèn)證主要內(nèi)容v消息認(rèn)證基本概念消息認(rèn)證基本概念 v消息加密認(rèn)證消息加密認(rèn)證 v消息認(rèn)證碼消息認(rèn)證碼 v hash函數(shù)函數(shù) 概 念v認(rèn)證(Authentication)：即鑒別、確認(rèn)，它是證實(shí)某事是否名副其實(shí)，或是否有效的一個(gè)過程。v認(rèn)證與加密的區(qū)別：加密用以確保數(shù)據(jù)的保密性，阻止對(duì)手的被動(dòng)攻擊，如截取、竊聽。認(rèn)證用以確保報(bào)文發(fā)送者和接受者的真實(shí)性以及保文的完整性，阻止對(duì)手的主動(dòng)攻擊，如冒充、篡改、重播等。v認(rèn)證往往是應(yīng)用系統(tǒng)中安全保護(hù)的第一道防線，極為重要?；舅枷雟通過驗(yàn)證稱謂者(人或事)的一個(gè)或多個(gè)參數(shù)的真實(shí)性和有效性，來達(dá)到驗(yàn)證稱謂者是否名副其實(shí)的目的。v常用的參數(shù)有：口令、

2、標(biāo)識(shí)符、密鑰、信物、智能卡、指紋、視網(wǎng)紋等。v利用人的生理特征參數(shù)進(jìn)行認(rèn)證的安全性高，但技術(shù)要求也高，至今尚未普及。目前廣泛應(yīng)用的還是基于密碼的認(rèn)證技術(shù)。沒有消息認(rèn)證的通信系統(tǒng)是極為危險(xiǎn)的 消息認(rèn)證(Message Authentication) v消息認(rèn)證用于抗擊主動(dòng)攻擊消息認(rèn)證用于抗擊主動(dòng)攻擊v驗(yàn)證接收消息的真實(shí)性和完整性驗(yàn)證接收消息的真實(shí)性和完整性v真實(shí)性真實(shí)性的確是由所聲稱的實(shí)體發(fā)過來的的確是由所聲稱的實(shí)體發(fā)過來的v完整性完整性未被篡改、插入和刪除未被篡改、插入和刪除v驗(yàn)證消息的順序性和時(shí)間性（未重排、重放驗(yàn)證消息的順序性和時(shí)間性（未重排、重放和延遲）和延遲）需求1.泄密：將消息透露給

3、沒有合法秘密鑰的任何人或程序。2.傳輸分析：分析通信雙方的通信模式，如連接頻率，時(shí)間等3.偽裝：攻擊者產(chǎn)生一條消息并聲稱來自某合法實(shí)體4.內(nèi)容修改：對(duì)消息進(jìn)行插入、刪除、轉(zhuǎn)化、修改5.順序修改：對(duì)消息順序進(jìn)行插入、刪除、重新排序6.計(jì)時(shí)修改：對(duì)消息的延時(shí)和重放7.發(fā)送方否認(rèn)8.接受方否然v對(duì)付1、2可用加密；v對(duì)付3、4、5、6可用消息認(rèn)證；v對(duì)付7、8可用數(shù)字簽名消息認(rèn)證的基本概念v消息認(rèn)證：驗(yàn)證所收到的消息確定是來自真正的發(fā)送方且未被修改過。v認(rèn)證符：一個(gè)用來認(rèn)證消息的值。由消息的發(fā)送方產(chǎn)生認(rèn)證符，并傳遞給接收方。v認(rèn)證函數(shù)：產(chǎn)生認(rèn)證符的函數(shù)，認(rèn)證函數(shù)實(shí)際上代表了一種產(chǎn)生認(rèn)證符的方法。消息

4、加密消息認(rèn)證碼Hash函數(shù)消息加密-在對(duì)稱加密體制下v由于攻擊者不知道密鑰K，他也就不知道如何改變密文中的信息位才能在明文中產(chǎn)生預(yù)期的改變。v接收方可以根據(jù)解密后的明文是否具有合理的語法結(jié)構(gòu)來進(jìn)行消息認(rèn)證。v但有時(shí)發(fā)送的明文本身并名優(yōu)明顯的語法結(jié)構(gòu)或特征，例如二進(jìn)制文件，因此很難確定解密后的消息就是明文本身。MEKEK(M)DKMv根據(jù)明文M和公開的函數(shù)F產(chǎn)生FCS，即錯(cuò)誤檢測碼，或幀校驗(yàn)序列，校驗(yàn)和。v把M和FCS合在一起加密，并傳輸。v接收端把密文解密，得到M。v根據(jù)得到的M，按照F計(jì)算FCS，并與接收到的FCS比較是否相等。MFFMFCS比較EK|()KEMF MDKMFCS內(nèi)部錯(cuò)誤控制

5、v攻擊者可以構(gòu)造具有正確錯(cuò)誤控制碼的消息，雖然攻擊者不知道解密后的明文，但可以造成混淆并破壞通信。()KEMMFFCSEK()KF EMDKM外部錯(cuò)誤控制F比較()KEM()KEM消息加密-在公鑰加密體制下v由于大家都知道B的公鑰，所以這種方式不提供認(rèn)證，只提供加密。MEKUbEKUb(M)DKRbMI. 普通加密AB消息加密-在公鑰加密體制下v由于只有A有用于產(chǎn)生EKRa (M)的密鑰，所以此方法提供認(rèn)證。v由于大家都有KUa ，所以此方法不提供加密。MEKRaEKRa (M)DKUaMII. 認(rèn)證和簽名AB消息加密-在公鑰加密體制下v提供認(rèn)證和加密。v一次通信中要執(zhí)行四次復(fù)雜的公鑰算法。M

6、EKRaEKRa (M)DKUaMIII. 加密認(rèn)證和簽名ABEKUbEKUb(EKRa (M)DKRbEKRa (M)消息認(rèn)證碼(MAC)vMessage Authenticaion Codev消息認(rèn)證碼是消息和密鑰的公開函數(shù)，它產(chǎn)生定長的值，以該值作為認(rèn)證符。v利用密鑰和消息生成一個(gè)固定長度的短數(shù)據(jù)塊，并將其附加在消息之后。v通信雙方共享密鑰K消息認(rèn)證碼用于認(rèn)證vA和B共享密鑰KvA計(jì)算MAC=Ck(M),vM和MAC一起發(fā)送到BvB對(duì)收到的M，計(jì)算MAC，比較兩個(gè)MAC是否相同。()KCMMCMACKC比較MKMAC如果兩個(gè)MAC相等，則：1. 接收方可以相信消息未被修改，因?yàn)槿绻粽?/p>

7、改變了消息，由于不知道k，無法生成正確的MAC。2. 接收方可以相信消息的確來自確定的發(fā)送方。因?yàn)槠渌瞬荒苌珊驮枷⑾鄳?yīng)的MAC。MAC函數(shù)與加密函數(shù)的區(qū)別vMAC函數(shù)與加密函數(shù)類似，都需要明文、密鑰和算法的參與。v但MAC算法不要求可逆性，而加密算法必須是可逆的。v例如：使用100比特的消息和10比特的MAC，那么總共有2100個(gè)不同的消息，但僅有210個(gè)不同的MAC。也就是說，平均每290個(gè)消息使用的MAC是相同的。v因此，認(rèn)證函數(shù)比加密函數(shù)更不易被攻破，因?yàn)榧幢愎テ埔矡o法驗(yàn)證其正確性。關(guān)鍵就在于加密函數(shù)是一對(duì)一的，而認(rèn)證函數(shù)是多對(duì)一的。消息認(rèn)證碼的基本用途v只提供消息認(rèn)證，不提供保

8、密性。（見前）v提供消息認(rèn)證和保密性：M|CK1CMCK(M)K1比較EK2)(|12MCMEKKDK2ABA和B共享K1和K2K1：用于生成MACK2：用于加密與明文有關(guān)的認(rèn)證消息認(rèn)證碼的基本用途v提供消息認(rèn)證和保密性：ABA和B共享K1和K2K1：用于生成MACK2：用于加密與密文有關(guān)的認(rèn)證M|CK1CK1比較EK2)(21MECKKDK2對(duì)MAC的攻擊攻擊密鑰v已知消息M1和MAC算法C，以及MAC1 = C k1 (M1) ，現(xiàn)要破解k1。密鑰為k個(gè)bit，MAC為n個(gè)bit。v當(dāng)knkn： 可能的密鑰個(gè)數(shù)為2k。可能的MAC個(gè)數(shù)為2n個(gè)。 所以許多不同的密鑰(約2k-n個(gè))，計(jì)算出來

9、的MAC都等于MAC1。這些密鑰中哪一個(gè)是正確的密鑰不得而知。這時(shí)需要新的M-MAC對(duì)來測試這2k-n個(gè)密鑰，于是有如下的重復(fù)攻擊：重復(fù)攻擊vStep 1:給定M1和MAC1 = C k1 (M1) 對(duì)所有2k個(gè)密鑰，判斷MACi = C ki (M1) 匹配數(shù)約為： 2k-n vStep 2:給定M2和MAC2 = C k2 (M1)對(duì)所有2k個(gè)密鑰，判斷MACi = C ki (M2)匹配數(shù)約為： 2k-2n v平均來講，若k=x*n，則需x次循環(huán)才能找到正確的密鑰。v所以，用窮舉法攻破MAC比攻破加密算法要困難得多。對(duì)MAC的攻擊攻擊算法v考慮下面的算法： 消息M=(X1X2Xm)是由6

10、4比特長的分組Xi(i=1,m)鏈接而成 MAC算法是： 加密算法是DES。因此，密鑰長為56比特。 如果敵手得到MCK(M)，那么敵手使用窮搜索攻擊尋找K將需做256次加密。很困難!v但攻擊者可以改變M的內(nèi)容，卻使MAC正確。 方法如下：12()()()mKKMXXXCMEMv用Y1替換X1 ， Y2替換X2 ， Ym替換Xm ，其中Y1 ，Y2 ， ，Ym 是攻擊者編造的假消息。且 Ym = Y1 Y2 Ym-1 (M)， v當(dāng)接收者收到這個(gè)消息： M=(Y1Y2Ym) 則(M)= Y1 Y2 Ym = (M)所以：CK(M)=CK(M) 通過了驗(yàn)證，攻擊得逞。MAC函數(shù)應(yīng)具有的性質(zhì)v若攻

11、擊者已知M和CK(M)，則他構(gòu)造滿足： CK(M)=CK(M)的消息M在計(jì)算上不可行vCK(M)應(yīng)試均勻分布的，即對(duì)于隨機(jī)消息M和M， CK(M)=CK(M)的概率是2-n，n是MAC的位數(shù)基于DES的消息認(rèn)證碼v使用最廣泛的MAC算法之一：數(shù)據(jù)認(rèn)證算法v過程：把需要認(rèn)證的數(shù)據(jù)分成連續(xù)的64位的分組。若最后一個(gè)分組不是64位，則填0利用DES加密算法E和密鑰K，計(jì)算認(rèn)證碼。112213321()()()()KKKNKNNOEDOEDOOEDOOEDO數(shù)據(jù)認(rèn)證算法似乎可以滿足前面提出的要求。DAC M-bits(16 to 64 bits)為什么不直接使用加密而使用分離的消息認(rèn)證碼？v保密性與真

12、實(shí)性是兩個(gè)不同的概念v根本上,信息加密提供的是保密性而非真實(shí)性v加密代價(jià)大(公鑰算法代價(jià)更大)v鑒別函數(shù)與保密函數(shù)的分離能提供功能上的靈活性v某些信息只需要真實(shí)性,不需要保密性廣播的信息難以使用加密(信息量大)網(wǎng)絡(luò)管理信息等只需要真實(shí)性政府/權(quán)威部門的公告Hash函數(shù)(雜湊函數(shù)、散列函數(shù))vHash的特點(diǎn)：與消息認(rèn)證碼一樣，hash函數(shù)的輸入是可變的消息M，輸出是固定大小的hash碼H(M) ，或稱消息摘要(Message Digest) 、hash值。與消息認(rèn)證碼不同的是， hash碼的產(chǎn)生過程中并不使用密鑰。Hash碼是所有消息的函數(shù)，改變消息的任何一位或多位，都會(huì)導(dǎo)致hash碼的改變。H

13、ash算法通常是公開的。又稱為：哈希函數(shù)、數(shù)字指紋（Digital finger print)、壓縮（Compression)函數(shù)、緊縮（Contraction ）函數(shù)、數(shù)據(jù)鑒別碼DAC（Data authentication code）、篡改檢驗(yàn)碼MDC(Manipulation detection code)h=H(M) v假定兩次輸入同樣的數(shù)據(jù)，那么散列函數(shù)應(yīng)該能夠生成相同的散列值。輸入數(shù)據(jù)中的一位發(fā)生了變化，會(huì)導(dǎo)致生成的散列值完全不一樣。v散列函數(shù)有個(gè)非常重要的特性為單向性，也就是從M計(jì)算h容易，而從h計(jì)算M不可能。 散列函數(shù)H必須滿足以下幾個(gè)性質(zhì) vH對(duì)于任何大小的數(shù)據(jù)分組，都能產(chǎn)生

14、定長的輸出。 v對(duì)于任何給定的M，H(M)要相對(duì)易于計(jì)算。 v單向性：對(duì)于任何給定的hash值h，計(jì)算出M在計(jì)算上不可行。 v弱無碰撞性：對(duì)任何給定的M1，尋找M2，使H(M1)=H(M2)在計(jì)算上不可行。 v強(qiáng)無碰撞性：尋找任何的（M1，M2），使H(M1)=H(M2)在計(jì)算上不可行。 Hash與MAC的區(qū)別vMAC需要對(duì)全部數(shù)據(jù)進(jìn)行加密vMAC速度慢vHash是一種直接產(chǎn)生鑒別碼的方法vHash可用于數(shù)字簽名常用Hash算法 迭代型hash函數(shù)的一般結(jié)構(gòu)fffY0Y1YL-1bbbnnnnnIV=CV0CV1CVL-1CVL明文M被分為L個(gè)分組Y0,Y1,YL-1b:明文分組長度n:輸出h

15、ash長度CV：各級(jí)輸出，最后一個(gè)輸出值是hash值無碰撞壓縮函數(shù)f是設(shè)計(jì)的關(guān)鍵迭代型hash函數(shù)v這種結(jié)構(gòu)的hash函數(shù)已被證明是合理的，如果采用其他結(jié)構(gòu)，不一定安全。v設(shè)計(jì)新的hash函數(shù)只是改進(jìn)這種結(jié)構(gòu)，或者增加hash碼長。v算法的核心技術(shù)是設(shè)計(jì)無碰撞的壓縮函數(shù)f，而敵手對(duì)算法的攻擊重點(diǎn)是f 的內(nèi)部結(jié)構(gòu)，由于f 和分組密碼一樣是由若干輪處理過程組成，所以對(duì)f 的攻擊需通過對(duì)各輪之間的位模式的分析來進(jìn)行，分析過程常常需要先找出f 的碰撞。由于f 是壓縮函數(shù)，其碰撞是不可避免的，因此在設(shè)計(jì)f 時(shí)就應(yīng)保證找出其碰撞在計(jì)算上是不可行的。MD5 hash算法MD5 Hash Algorithm

16、MD4是MD5雜湊算法的前身，由Ron Rivest于1990年10月作為RFC提出，1992年4月公布的MD4的改進(jìn)（RFC 1320，1321）稱為MD5。MD5的算法框圖v輸入消息可任意長，壓縮后輸出為128bits。算法步驟(1)分組填充 消息100064bit消息長度填充圖樣L512bitKbitv如果消息長度大于264，則取其對(duì)264的模。v執(zhí)行完后，消息的長度為512的倍數(shù)（設(shè)為L倍），則可將消息表示為分組長為512的一系列分組Y0，Y1，YL-1，而每一分組又可表示為16個(gè)32比特長的字，這樣消息中的總字?jǐn)?shù)為N=L16，因此消息又可按字表示為M0,N-1。算法步驟(2)緩沖區(qū)初

17、始化 hash hash函數(shù)的中間結(jié)果和最終結(jié)果保存于函數(shù)的中間結(jié)果和最終結(jié)果保存于128128位位的緩沖區(qū)中，緩沖區(qū)用的緩沖區(qū)中，緩沖區(qū)用3232位的寄存器表示。可位的寄存器表示?？捎糜? 4個(gè)個(gè)32bits32bits字表示：字表示：A A, ,B B, ,C,DC,D。初始存數(shù)以十。初始存數(shù)以十六進(jìn)制表示為六進(jìn)制表示為A A=01234567=01234567B B=89=89ABCDEFABCDEFC C=FEDCBAFEDCBA9898D D=76543210=76543210算法步驟(3) -HMD5運(yùn)算v以分組為單位對(duì)消息進(jìn)行處理每一分組Yq(q=0,L-1)都經(jīng)一壓縮函數(shù)HMD

18、5處理。HMD5是算法的核心，其中又有4輪處理過程。vHMD5的4輪處理過程結(jié)構(gòu)一樣，但所用的邏輯函數(shù)不同，分別表示為F、G、H、I。每輪的輸入為當(dāng)前處理的消息分組Yq和緩沖區(qū)的當(dāng)前值A(chǔ)、B、C、D，輸出仍放在緩沖區(qū)中以產(chǎn)生新的A、B、C、D。v每輪又要進(jìn)行16步迭代運(yùn)算，4輪共需64步完成。v第四輪的輸出與第一輪的輸入相加得到最后的輸出。壓縮函數(shù)中的一步迭代基本邏輯函數(shù)定義 輪基本函數(shù)gg(b, c, d)fFF( b,c,d)( bc)V(bd)fGG( b,c,d)( bd)V(c d)fHH( b,c,d)b c dfII( b,c,d)c ( b V d)Xkv當(dāng)前分組的第k個(gè)32位

19、的字。第1輪 x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11x12x13x14x15第2輪 x1 x6 x11 x0 x5 x10 x15 x4 x9 x14 x3 x8 x13 x2 x7 x12第3輪 x5 x8 x11x14 x1 x4 x7 x10 x13 x0 x3 x6 x9 x12x15 x2第4輪 x0 x7 x14 x5 x12 x3 x10 x1 x8 x15 x6 x13 x4 x11 x2 x9TivT1,64為64個(gè)元素表，分四組參與不同輪的計(jì)算。Ti為232abs(Sin(i)的整數(shù)部分，i是弧度。Ti可用32 bit二元數(shù)表示，T是32

20、 bit隨機(jī)數(shù)源。T1= d76aa478T17= f61e2562T33= fffa3942T49= f4292244T2= e8c7b756T18= c040b340T34= 8771f681T50= 432aff97T3= 242070dbT19= 265e5a51T35= 6d9d6122T51= ab9423a7T4= c1bdceeeT20= e9b6c7aaT36= fde5380cT52= fc93a039T5= f57c0fafT21= d62f105dT37= a4beea44T53= 655b59c3T6= 4787c62aT22= 02441453T38= 4bdecf

21、a9T54= 8f0ccc92T7= a8304613T23= d8a1e681T39= f6bb4b60T55= ffeff47dT8= fd469501T24= e7d3fbc8T40= bebfbc70T56= 85845dd1T9= 698098d8T25= 21e1cde6T41= 289b7ec6T57= 6fa87e4fT10= 8b44f7afT26= c33707d6T42= eaa127faT58= fe2ce6e0T11= ffff5bb1T27= f4d50d87T43= d4ef3085T59= a3014314T12= 895cd7beT28= 455a14edT4

22、4= 04881d05T60= 4e0811a1T13= 6b901122T29= a9e3e905T45= d9d4d039T61= f7537e82T14= fd987193T30= fcefa3f8T46= e6db99e5T62= bd3af235T15= a679438eT31= 676f02d9T47= 1fa27cf8T63= 2ad7d2bbT16= 49b40821T32= 8d2a4c8aT48= c4ac5665T63= eb86d391CLSs ：循環(huán)左移s位v第一輪：7、12、17、22v第二輪：5、9、14、20v第三輪：4、11、16、23v第四輪：6、10、15

23、、21MD-5的安全性vMD-5的輸出為128-bit，若采用純強(qiáng)力攻擊尋找一個(gè)消息具有給定Hash值的計(jì)算困難性為2128，用每秒可試驗(yàn)1 000 000 000個(gè)消息的計(jì)算機(jī)需時(shí)1.071022年。v采用生日攻擊法，找出具有相同雜湊值的兩個(gè)消息需執(zhí)行264次運(yùn)算。SHA 算法Secure Hash Algorithm算法簡介v美國標(biāo)準(zhǔn)與技術(shù)研究所美國標(biāo)準(zhǔn)與技術(shù)研究所NISTNIST設(shè)計(jì)設(shè)計(jì)v19931993年成為聯(lián)邦信息處理標(biāo)準(zhǔn)年成為聯(lián)邦信息處理標(biāo)準(zhǔn)(FIPS PUB 180)(FIPS PUB 180)v基于基于MD4MD4算法，與之非常類似。算法，與之非常類似。v輸入為小于輸入為小于2

24、 26464比特長的任意消息比特長的任意消息v分組分組512bit512bit長長v輸出輸出160bit160bit迭代型hash函數(shù)的一般結(jié)構(gòu)fffY0Y1YL-1bbbnnnnnIV=CV0CV1CVL-1CVL明文M被分為L個(gè)分組Y0,Y1,YL-1b:明文分組長度n:輸出hash長度CV：各級(jí)輸出，最后一個(gè)輸出值是hash值無碰撞壓縮函數(shù)f是設(shè)計(jì)的關(guān)鍵算法描述v消息填充：與消息填充：與MD5完全相同完全相同v附加消息長度：附加消息長度：64bit長度長度v緩沖區(qū)初始化緩沖區(qū)初始化A67452301BEFCDAB89C98BADCFBD10325476EC3D2E1F0分組處理模232加

25、SHA-1壓縮函數(shù)（單步）ft -基本邏輯函數(shù)vCLS5：32位的變量循環(huán)左移5位。vCLS30：32位的變量循環(huán)左移30位。Wt -從當(dāng)前512位輸入分組導(dǎo)出的32位字v前16個(gè)值（即W0,W1,W15）直接取為輸入分組的16個(gè)相應(yīng)的字，其余值（即W16,W17,W79）取為1161483()tttttWCLS WWWWKt -加法常量步驟十六進(jìn)制0t19Kt=5A82799920t39Kt=6ED9EBA140t59Kt=8F1BBCDC60t79Kt=CA62C1D6SHA與MD5的比較v抗窮舉搜索能力抗窮舉搜索能力尋找指定尋找指定hashhash值，值， SHASHA：O(2O(216

26、0160) )，MD5MD5：O(2O(2128128) )生日攻擊：生日攻擊： SHASHA：O(2O(28080) )，MD5MD5：O(2O(26464) )v抗密碼分析攻擊的強(qiáng)度抗密碼分析攻擊的強(qiáng)度SHASHA似乎高于似乎高于MD5MD5v速度速度SHASHA較較MD5MD5慢慢v簡捷與緊致性簡捷與緊致性描述都比較簡單，都不需要大的程序和代換表描述都比較簡單，都不需要大的程序和代換表其它hash算法vMD4 MD4使用三輪運(yùn)算，每輪16步； MD5使用四輪運(yùn)算，每輪16步。MD4的第一輪沒有使用加法常量，第二輪運(yùn)算中每步迭代使用的加法常量相同，第三輪運(yùn)算中每步迭代使用的加法常量相同，但

27、不同于第二輪使用的加法常量；MD5的64部使用的加法常量Ti均不同。MD4使用三個(gè)基本邏輯函數(shù)，MD5使用四個(gè)。MD5中每步迭代的結(jié)果都與前一步的結(jié)果相加，MD4則沒有。MD5比MD4更復(fù)雜，所以其執(zhí)行速度也更慢，Rivest認(rèn)為增加復(fù)雜性可以增加安全性。RIPEMD-160v歐共體RIPE項(xiàng)目組研制。v輸入可以是任意長的報(bào)文，輸出160位摘要。v對(duì)輸入按512位分組。以分組為單位處理。v算法的核心是具有十輪運(yùn)算的模塊，十輪運(yùn)算分成兩組，每組五輪，每輪16步迭代。對(duì)Hash函數(shù)的攻擊 v對(duì)一個(gè)hash算法的攻擊可分三個(gè)級(jí)別：預(yù)映射攻擊（Preimage Attack）：給定Hash值h，找到其

28、所對(duì)應(yīng)的明文M，使得Hash(M)=h，這種攻擊是最徹底的，如果一個(gè)hash算法被人找出預(yù)映射，那這種算法是不能使用的。次預(yù)映射攻擊（Second Preimage Attack）：給定明文M1，找到另一明文M2（M1M2），使得hash(M1)=hash(M2)，這種攻擊其實(shí)就是要尋找一個(gè)弱碰撞；碰撞攻擊 (Collision Attack)：找到M1和M2，使得hash(M1)=hash(M2) ，這種攻擊其實(shí)就是要尋找一個(gè)強(qiáng)碰撞。生日攻擊v給定一個(gè)散列函數(shù)H和某和某hash值值H(x)，假定假定H有n個(gè)可能的輸出。如果H有k個(gè)隨機(jī)輸入, k必須為多大才能使至少存在一個(gè)輸入y,使得H(y)

29、=H(x)的概率大于0.5？K=n/2結(jié)論v如果hash碼為m位，則有2m個(gè)可能的hash碼。v如果給定h=H(X)，要想找到一個(gè)y，使H(y) =h的概率為0.5，則要進(jìn)行多次的嘗試，嘗試的次數(shù)k=2m/2=2m-1v所以，對(duì)于一個(gè)使用64位的hash碼，攻擊者要想找到滿足H(M)=H(M)的M來替代M，平均來講，他要找到這樣的消息大約要進(jìn)行263次嘗試。v但是，存在一種攻擊，稱為“生日攻擊”，卻可以大大減小嘗試的次數(shù)，對(duì)于64位的hash碼，所需的代價(jià)僅為232次。生日悖論v一個(gè)教室中，最少應(yīng)有多少學(xué)生，才使至少有兩人具有相同生日的概率不小于1/2？v概率結(jié)果與人的直覺是相違背的.v實(shí)際上只需23人,即任找23人，從中總能選出兩人具有