《消息認(rèn)證》課件

第5章

消息認(rèn)證1精選ppt第5章

消息認(rèn)證1精選ppt主要內(nèi)容消息認(rèn)證基本概念消息加密認(rèn)證消息認(rèn)證碼hash函數(shù)2精選ppt主要內(nèi)容消息認(rèn)證基本概念2精選ppt5.1消息認(rèn)證基本概念認(rèn)證(Authentication)：即鑒別、確認(rèn)，它是證實(shí)某事是否名副其實(shí)，或是否有效的一個(gè)過程。認(rèn)證與加密的區(qū)別：加密用以確保數(shù)據(jù)的保密性，阻止對手的被動(dòng)攻擊，如截取、竊聽。認(rèn)證用以確保報(bào)文發(fā)送者和接受者的真實(shí)性以及報(bào)文的完整性，阻止對手的主動(dòng)攻擊，如冒充、篡改、重播等。認(rèn)證往往是應(yīng)用系統(tǒng)中安全保護(hù)的第一道防線，極為重要。3精選ppt5.1消息認(rèn)證基本概念認(rèn)證(Authentication)基本思想通過驗(yàn)證稱謂者(人或事)的一個(gè)或多個(gè)參數(shù)的真實(shí)性和有效性，來達(dá)到驗(yàn)證稱謂者是否名副其實(shí)的目的。常用的參數(shù)有：口令、標(biāo)識符、密鑰、信物、智能卡、指紋、視網(wǎng)紋等。利用人的生理特征參數(shù)進(jìn)行認(rèn)證的安全性高，但技術(shù)要求也高，至今尚未普及。目前廣泛應(yīng)用的還是基于密碼的認(rèn)證技術(shù)。4精選ppt基本思想通過驗(yàn)證稱謂者(人或事)的一個(gè)或多個(gè)參數(shù)的真實(shí)性和有沒有消息認(rèn)證的通信系統(tǒng)是極為危險(xiǎn)的5精選ppt沒有消息認(rèn)證的通信系統(tǒng)是極為危險(xiǎn)的5精選ppt消息認(rèn)證(MessageAuthentication)消息認(rèn)證用于抗擊主動(dòng)攻擊驗(yàn)證接收消息的完整性完整性未被篡改、插入和刪除驗(yàn)證消息的順序性和時(shí)間性（未重排、重放和延遲）6精選ppt消息認(rèn)證(MessageAuthentication)消需求泄密：將消息透露給沒有合法秘密鑰的任何人或程序。傳輸分析：分析通信雙方的通信模式，如連接頻率，時(shí)間等偽裝：攻擊者產(chǎn)生一條消息并聲稱來自某合法實(shí)體內(nèi)容修改：對消息進(jìn)行插入、刪除、轉(zhuǎn)化、修改順序修改：對消息順序進(jìn)行插入、刪除、重新排序計(jì)時(shí)修改：對消息的延時(shí)和重放發(fā)送方否認(rèn)接受方否然對付1、2可用加密；對付3、4、5、6可用消息認(rèn)證；對付7、8可用數(shù)字簽名7精選ppt需求泄密：將消息透露給沒有合法秘密鑰的任何人或程序。7精選p消息認(rèn)證的基本概念消息認(rèn)證：驗(yàn)證所收到的消息和該消息被發(fā)送時(shí)是否相同，即是否被修改過。認(rèn)證符(authenticator)：一個(gè)用來認(rèn)證消息的值。由消息的發(fā)送方產(chǎn)生認(rèn)證符，并傳遞給接收方。認(rèn)證函數(shù)：產(chǎn)生認(rèn)證符的函數(shù)，認(rèn)證函數(shù)實(shí)際上代表了一種產(chǎn)生認(rèn)證符的方法。消息加密(Messageencryption)消息認(rèn)證碼(Messageauthenticationcode,MAC)Hash函數(shù)(Hashfunction

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

110101

←

Q

(商)P(除數(shù))→

1101101001000

←

2nM(被除數(shù))

1101

1110

1101

0111

0000

1110

1101

0110

0000

1100

1101

001←R(余數(shù))，作為FCS

FCS的原理說明M=10100113精選ppt

MFFCSEKDKM外部錯(cuò)誤控制F比較14精選pptMFFCSEKDKM外部錯(cuò)誤控制F比較14精選ppt消息加密認(rèn)證---在公鑰加密體制下MEKUbEKUb(M)DKRbMI.普通加密ABMM15精選ppt消息加密認(rèn)證---在公鑰加密體制下MEKUbEKUb(M)D消息加密認(rèn)證---在公鑰加密體制下由于只有A有用于產(chǎn)生EKRa(M)的密鑰，所以此方法提供認(rèn)證。MEKRaEKRa(M)DKUaMII.認(rèn)證和簽名ABMM16精選ppt消息加密認(rèn)證---在公鑰加密體制下由于只有A有用于產(chǎn)生EKR消息加密認(rèn)證---在公鑰加密體制下提供認(rèn)證和加密。一次通信中要執(zhí)行四次復(fù)雜的公鑰算法。MEKRaEKUb(M)DKUaMIII.加密認(rèn)證和簽名ABEKUbEKRa(EKUb(M))DKUaEKRa(M)17精選ppt消息加密認(rèn)證---在公鑰加密體制下提供認(rèn)證和加密。MEKRa把加密與認(rèn)證分開Thereareanumberofapplicationsinwhichthesamemessageisbroadcasttoanumberofdestinations.Thereceiverhasaheavyloadandcannotaffordthetimetodecryptallincomingmessages.Forsomeapplications,itmaynotbeofconcerntokeepmessagessecret,butitisimportanttoauthenticatemessages.Separationofauthenticationandconfidentialityfunctionsaffordsarchitecturalflexibility.18精選ppt把加密與認(rèn)證分開Thereareanumberof5.3消息認(rèn)證碼(MAC)MessageAuthenticaionCode消息認(rèn)證碼是消息和密鑰的公開函數(shù)，它產(chǎn)生定長的值，以該值作為認(rèn)證符。利用密鑰和消息生成一個(gè)固定長度的短數(shù)據(jù)塊，并將其附加在消息之后。通信雙方共享密鑰K19精選ppt5.3消息認(rèn)證碼(MAC)MessageAuthentiAMAC,alsoknownasacryptographicchecksum(密碼校驗(yàn)和),isgeneratedbyafunctionCoftheform：MAC=C(K,M)Where：Misavariable-lengthmessageKisasecretkeysharedonlybysenderandreceiverMACisthefixed-lengthauthenticator.TheMACisappendedtothemessageatthesourceatatimewhenthemessageisassumedorknowntobecorrect.ThereceiverauthenticatesthatmessagebyrecomputingtheMAC.20精選pptAMAC,alsoknownasacryptog消息認(rèn)證碼用于認(rèn)證A和B共享密鑰KA計(jì)算MAC=Ck(M),M和MAC一起發(fā)送到BB對收到的M，計(jì)算MAC，比較兩個(gè)MAC是否相同。MCMACKC比較KMAC如果兩個(gè)MAC相等，則：接收方可以相信消息未被修改，因?yàn)槿绻粽吒淖兞讼?，由于不知道k，無法生成正確的MAC。接收方可以相信消息的確來自確定的發(fā)送方。因?yàn)槠渌瞬荒苌珊驮枷⑾鄳?yīng)的MAC。21精選ppt消息認(rèn)證碼用于認(rèn)證A和B共享密鑰KMCMACKC比較KMACMAC函數(shù)與加密函數(shù)的區(qū)別MAC函數(shù)與加密函數(shù)類似，都需要明文、密鑰和算法的參與。但MAC算法不要求可逆性，而加密算法必須是可逆的。例如：使用100比特的消息和10比特的MAC，那么總共有2100個(gè)不同的消息，但僅有210個(gè)不同的MAC。也就是說，平均每290個(gè)消息使用的MAC是相同的。因此，認(rèn)證函數(shù)比加密函數(shù)更不易被攻破，因?yàn)榧幢愎テ埔矡o法驗(yàn)證其正確性。關(guān)鍵就在于加密函數(shù)是一對一的，而認(rèn)證函數(shù)是多對一的。22精選pptMAC函數(shù)與加密函數(shù)的區(qū)別MAC函數(shù)與加密函數(shù)類似，都需要明消息認(rèn)證碼的基本用途只提供消息認(rèn)證，不提供保密性。（見前）提供消息認(rèn)證和保密性：M||CK1CMCK(M)K1比較EK2DK2ABA和B共享K1和K2K1：用于生成MACK2：用于加密與明文有關(guān)的認(rèn)證23精選ppt消息認(rèn)證碼的基本用途只提供消息認(rèn)證，不提供保密性。（見前）M消息認(rèn)證碼的基本用途提供消息認(rèn)證和保密性：ABA和B共享K1和K2K1：用于生成MACK2：用于加密與密文有關(guān)的認(rèn)證M||CK1CK1比較EK2DK224精選ppt消息認(rèn)證碼的基本用途提供消息認(rèn)證和保密性：ABA和B共享K15.3.2消息認(rèn)證碼的安全性攻擊密鑰攻擊算法25精選ppt5.3.2消息認(rèn)證碼的安全性攻擊密鑰25精選ppt對MAC的攻擊—攻擊密鑰已知消息M1和MAC算法C，以及MAC1=

Ck1(M1)

，現(xiàn)要破解k1。密鑰為k個(gè)bit，MAC為n個(gè)bit。當(dāng)k>n：可能的密鑰個(gè)數(shù)為2k。可能的MAC個(gè)數(shù)為2n個(gè)。

所以許多不同的密鑰(約2k-n個(gè))，計(jì)算出來的MAC都等于MAC1。這些密鑰中哪一個(gè)是正確的密鑰不得而知。這時(shí)需要新的M-MAC對來測試這2k-n個(gè)密鑰，于是有如下的重復(fù)攻擊：26精選ppt對MAC的攻擊—攻擊密鑰已知消息M1和MAC算法C，以及MA重復(fù)攻擊Step1:給定M1和MAC1=

Ck1(M1)

對所有2k個(gè)密鑰，判斷MACi=

Cki(M1)

匹配數(shù)約為：2k-nStep2:給定M2和MAC2=

Ck2(M1)對所有2k個(gè)密鑰，判斷MACi=

Cki(M2)匹配數(shù)約為：2k-2n平均來講，若k=x*n，則需x次循環(huán)才能找到正確的密鑰。所以，用窮舉法攻破MAC比攻破加密算法要困難得多。27精選ppt重復(fù)攻擊Step1:27精選ppt對MAC的攻擊—攻擊算法考慮下面的算法：

消息M=(X1‖X2‖…‖Xm)是由64比特長的分組Xi(i=1,…,m)鏈接而成MAC算法是：加密算法是DES。因此，密鑰長為56比特。如果敵手得到M‖CK(M)，那么敵手使用窮搜索攻擊尋找K將需做256次加密。很困難!但攻擊者可以改變M的內(nèi)容，卻使MAC正確。方法如下：28精選ppt對MAC的攻擊—攻擊算法考慮下面的算法：28精選ppt用Y1替換X1，Y2替換X2，…，Ym替換Xm，其中Y1，Y2，…，Ym是攻擊者編造的假消息。且Ym=Y1Y2…Ym-1Δ(M)，當(dāng)接收者收到這個(gè)消息：M’=(Y1‖Y2‖…‖Ym)則Δ(M’)=Y1Y2…Ym

=

Δ(M)所以：CK(M)=CK(M’)通過了驗(yàn)證，攻擊得逞。29精選ppt用Y1替換X1，Y2替換X2，…，Ym替換Xm，其MAC函數(shù)應(yīng)具有的性質(zhì)若攻擊者已知M和CK(M)，則他構(gòu)造滿足：

CK(M)=CK(M’)的消息M’在計(jì)算上不可行CK(M)應(yīng)是均勻分布的，即對于隨機(jī)消息M和M’，CK(M)=CK(M’)的概率是2-n，n是MAC的位數(shù)若M’是M的某個(gè)變換，即M’=f(M)，那么Pr[CK(M)=CK(M’)]=2-n。30精選pptMAC函數(shù)應(yīng)具有的性質(zhì)若攻擊者已知M和CK(M)，則他構(gòu)造滿5.3.3基于DES的消息認(rèn)證碼

MessageAuthenticationCodeBasedonDES

使用最廣泛的MAC算法之一：數(shù)據(jù)認(rèn)證算法過程：把需要認(rèn)證的數(shù)據(jù)分成連續(xù)的64位的分組。若最后一個(gè)分組不是64位，則填0利用DES加密算法E和密鑰K，計(jì)算認(rèn)證碼。31精選ppt5.3.3基于DES的消息認(rèn)證碼

MessageAut32精選ppt32精選ppt數(shù)據(jù)認(rèn)證算法似乎可以滿足前面提出的要求。DACM-bits(16to64bits)33精選ppt數(shù)據(jù)認(rèn)證算法似乎可以滿足前面提出的要求。DACM-bits5.4Hash函數(shù)(雜湊函數(shù)、散列函數(shù))Hash的特點(diǎn)：與消息認(rèn)證碼一樣，hash函數(shù)的輸入是可變的消息M，輸出是固定大小的hash碼H(M)，或稱消息摘要(MessageDigest)、hash值。與消息認(rèn)證碼不同的是，hash碼的產(chǎn)生過程中并不使用密鑰。Hash碼是所有消息的函數(shù)，改變消息的任何一位或多位，都會(huì)導(dǎo)致hash碼的改變。Hash算法通常是公開的。又稱為：哈希函數(shù)、數(shù)字指紋（Digitalfingerprint)、壓縮（Compression)函數(shù)、緊縮（Contraction）函數(shù)、數(shù)據(jù)鑒別碼DAC（Dataauthenticationcode）、篡改檢驗(yàn)碼MDC(Manipulationdetectioncode)34精選ppt5.4Hash函數(shù)(雜湊函數(shù)、散列函數(shù))Hash的特點(diǎn)：3h=H(M)假定兩次輸入同樣的數(shù)據(jù)，那么散列函數(shù)應(yīng)該能夠生成相同的散列值。輸入數(shù)據(jù)中的一位發(fā)生了變化，會(huì)導(dǎo)致生成的散列值完全不一樣。散列函數(shù)有個(gè)非常重要的特性為單向性，也就是從M計(jì)算h容易，而從h計(jì)算M不可能。

35精選ppth=H(M)假定兩次輸入同樣的數(shù)據(jù)，那么散列函數(shù)應(yīng)該能夠生36精選ppt36精選ppt37精選ppt37精選ppt38精選ppt38精選ppt39精選ppt39精選ppt方法e的優(yōu)點(diǎn)不含加密處理加密軟件很慢加密硬件的開銷很大加密硬件是對大長度數(shù)據(jù)進(jìn)行優(yōu)化的加密算法可能受專利保護(hù)加密算法可能受出口的限制.40精選ppt方法e的優(yōu)點(diǎn)不含加密處理40精選ppt對HASH函數(shù)h=H(M)的要求Hcanbeappliedtoablockofdataofanysize.Hproducesafixed-lengthoutput.H(x)isrelativelyeasytocomputeforanygivenx,makingbothhardwareandsoftwareimplementationspractical.Foranygivenvalueh,itiscomputationallyinfeasibletofindxsuchthatH(x)=h.Thisissometimesreferredtointheliteratureastheone-wayproperty（單向性）.41精選ppt對HASH函數(shù)h=H(M)的要求Hcanbeapp對HASH函數(shù)h=H(M)的要求Foranygivenblockx,itiscomputationallyinfeasibletofindy≠xsuchthatH(y)=H(x).Thisissometimesreferredtoasweakcollisionresistance（弱碰撞性）.Itiscomputationallyinfeasibletofindanypair(x,y)suchthatH(x)=H(y).Thisissometimesreferredtoasstrongcollisionresistance（強(qiáng)碰撞性）.42精選ppt對HASH函數(shù)h=H(M)的要求Foranygive前三條要求具有實(shí)用性第4條是單向性質(zhì)，即給定消息可以產(chǎn)生一個(gè)散列碼，而給定散列碼不可能產(chǎn)生對應(yīng)的消息第5條性質(zhì)是保證一個(gè)給定的消息的散列碼不能找到與之相同的另外的消息。即防止偽造。第6條是對已知的生日攻擊方法的防御能力,強(qiáng)無碰撞。43精選ppt前三條要求具有實(shí)用性43精選pptHash與MAC的區(qū)別MAC需要對全部數(shù)據(jù)進(jìn)行加密MAC速度慢Hash是一種直接產(chǎn)生認(rèn)證符的方法Hash可用于數(shù)字簽名44精選pptHash與MAC的區(qū)別44精選ppt5.4.3常用Hash算法45精選ppt5.4.3常用Hash算法45精選ppt迭代型hash函數(shù)的一般結(jié)構(gòu)fffY0Y1YL-1bbbnnnnnIV=CV0CV1CVL-1CVL明文M被分為L個(gè)分組Y0,Y1,…,YL-1b:明文分組長度n:輸出hash長度CV：各級輸出，最后一個(gè)輸出值是hash值無碰撞壓縮函數(shù)f是設(shè)計(jì)的關(guān)鍵46精選ppt迭代型hash函數(shù)的一般結(jié)構(gòu)fffY0Y1YL-1bbbnn迭代型hash函數(shù)這種結(jié)構(gòu)的hash函數(shù)已被證明是合理的，如果采用其他結(jié)構(gòu)，不一定安全。設(shè)計(jì)新的hash函數(shù)只是改進(jìn)這種結(jié)構(gòu)，或者增加hash碼長。算法的核心技術(shù)是設(shè)計(jì)無碰撞的壓縮函數(shù)f，而敵手對算法的攻擊重點(diǎn)是f的內(nèi)部結(jié)構(gòu)，由于f和分組密碼一樣是由若干輪處理過程組成，所以對f的攻擊需通過對各輪之間的位模式的分析來進(jìn)行，分析過程常常需要先找出f的碰撞。由于f是壓縮函數(shù)，其碰撞是不可避免的，因此在設(shè)計(jì)f時(shí)就應(yīng)保證找出其碰撞在計(jì)算上是不可行的。47精選ppt迭代型hash函數(shù)這種結(jié)構(gòu)的hash函數(shù)已被證明是合理的，如MD5hash算法

MD5HashAlgorithm

MD4是MD5雜湊算法的前身，由RonRivest于1990年10月作為RFC提出，1992年4月公布的MD4的改進(jìn)（RFC1320，1321）稱為MD5。48精選pptMD5hash算法

MD5HashAlgorithm

MD5的算法框圖輸入消息可任意長，壓縮后輸出為128bits。49精選pptMD5的算法框圖輸入消息可任意長，壓縮后輸出為128bits算法步驟(1)－分組填充

消息100…064bit消息長度填充圖樣L×512bitKbit如果消息長度大于264，則取其對264的模。執(zhí)行完后，消息的長度為512的倍數(shù)（設(shè)為L倍），則可將消息表示為分組長為512的一系列分組Y0，Y1，…，YL-1，而每一分組又可表示為16個(gè)32比特長的字，這樣消息中的總字?jǐn)?shù)為N=L×16，因此消息又可按字表示為M[0,…,N-1]。50精選ppt算法步驟(1)－分組填充消息100…064bit消息長度填算法步驟(2)－緩沖區(qū)初始化hash函數(shù)的中間結(jié)果和最終結(jié)果保存于128位的緩沖區(qū)中，緩沖區(qū)用32位的寄存器表示?？捎?個(gè)32bits字表示：A,B,C,D。初始存數(shù)以十六進(jìn)制表示為A=01234567B=89ABCDEFC=FEDCBA98D=7654321051精選ppt算法步驟(2)－緩沖區(qū)初始化hash函數(shù)的中間結(jié)果和算法步驟(3)-HMD5運(yùn)算以分組為單位對消息進(jìn)行處理每一分組Yq(q=0,…,L-1)都經(jīng)一壓縮函數(shù)HMD5處理。HMD5是算法的核心，其中又有4輪處理過程。HMD5的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。每輪又要進(jìn)行16步迭代運(yùn)算，4輪共需64步完成。第四輪的輸出與第一輪的輸入相加得到最后的輸出。52精選ppt算法步驟(3)-HMD5運(yùn)算以分組為單位對消息進(jìn)行處理每一53精選ppt53精選ppt壓縮函數(shù)中的一步迭代54精選ppt壓縮函數(shù)中的一步迭代54精選ppt基本邏輯函數(shù)定義

輪基本函數(shù)gg(b,c,d)fFF(b,c,d)(b^c)V(bˉ^d)fGG(b,c,d)(b^d)V(c^dˉ)fHH(b,c,d)b?c?dfII(b,c,d)c?(bV

dˉ)55精選ppt基本邏輯函數(shù)定義輪基本函數(shù)gg(b,c,d)fFF(b,X[k]當(dāng)前分組的第k個(gè)32位的字。第1輪x[0]x[1]x[2]x[3]x[4]x[5]x[6]x[7]x[8]x[9]x[10]x[11]x[12]x[13]x[14]x[15]第2輪x[1]x[6]x[11]x[0]x[5]x[10]x[15]x[4]x[9]x[14]x[3]x[8]x[13]x[2]x[7]x[12]第3輪x[5]x[8]x[11]x[14]x[1]x[4]x[7]x[10]x[13]x[0]x[3]x[6]x[9]x[12]x[15]x[2]第4輪x[0]x[7]x[14]x[5]x[12]x[3]x[10]x[1]x[8]x[15]x[6]x[13]x[4]x[11]x[2]x[9]56精選pptX[k]當(dāng)前分組的第k個(gè)32位的字。第1輪x[0]x[1]xT[i]T[1,…,64]為64個(gè)元素表，分四組參與不同輪的計(jì)算。T[i]為232×abs(Sin(i))的整數(shù)部分，i是弧度。T[i]可用32bit二元數(shù)表示，T是32bit隨機(jī)數(shù)源。57精選pptT[i]T[1,…,64]為64個(gè)元素表，分四組參與不同輪的T[1]=d76aa478T[17]=f61e2562T[33]=fffa3942T[49]=f4292244T[2]=e8c7b756T[18]=c040b340T[34]=8771f681T[50]=432aff97T[3]=242070dbT[19]=265e5a51T[35]=6d9d6122T[51]=ab9423a7T[4]=c1bdceeeT[20]=e9b6c7aaT[36]=fde5380cT[52]=fc93a039T[5]=f57c0fafT[21]=d62f105dT[37]=a4beea44T[53]=655b59c3T[6]=4787c62aT[22]=02441453T[38]=4bdecfa9T[54]=8f0ccc92T[7]=a8304613T[23]=d8a1e681T[39]=f6bb4b60T[55]=ffeff47dT[8]=fd469501T[24]=e7d3fbc8T[40]=bebfbc70T[56]=85845dd1T[9]=698098d8T[25]=21e1cde6T[41]=289b7ec6T[57]=6fa87e4fT[10]=8b44f7afT[26]=c33707d6T[42]=eaa127faT[58]=fe2ce6e0T[11]=ffff5bb1T[27]=f4d50d87T[43]=d4ef3085T[59]=a3014314T[12]=895cd7beT[28]=455a14edT[44]=04881d05T[60]=4e0811a1T[13]=6b901122T[29]=a9e3e905T[45]=d9d4d039T[61]=f7537e82T[14]=fd987193T[30]=fcefa3f8T[46]=e6db99e5T[62]=bd3af235T[15]=a679438eT[31]=676f02d9T[47]=1fa27cf8T[63]=2ad7d2bbT[16]=49b40821T[32]=8d2a4c8aT[48]=c4ac5665T[63]=eb86d39158精選pptT[1]=d76aa478T[17]=f61e2562TCLSs：循環(huán)左移s位第一輪：7、12、17、22第二輪：5、9、14、20第三輪：4、11、16、23第四輪：6、10、15、2159精選pptCLSs：循環(huán)左移s位第一輪：7、12、17、2259精選MD-5的安全性MD-5的輸出為128-bit，若采用純強(qiáng)力攻擊尋找一個(gè)消息具有給定Hash值的計(jì)算困難性為2128，用每秒可試驗(yàn)1000000000個(gè)消息的計(jì)算機(jī)需時(shí)1.07×1022年。采用生日攻擊法，找出具有相同雜湊值的兩個(gè)消息需執(zhí)行264次運(yùn)算。60精選pptMD-5的安全性MD-5的輸出為128-bit，若采用純強(qiáng)力碰撞如果兩個(gè)輸入串的hash函數(shù)的值一樣，則稱這兩個(gè)串是一個(gè)碰撞(Collision)。既然是把任意長度的字符串變成固定長度的字符串，所以，必有一個(gè)輸出串對應(yīng)無窮多個(gè)輸入串，碰撞是必然存在的。2004年8月17日，美國加州圣巴巴拉正在召開國際密碼學(xué)會(huì)議，山東大學(xué)王小云教授公布了快速尋求MD5算法碰撞的算法。61精選ppt碰撞如果兩個(gè)輸入串的hash函數(shù)的值一樣，則稱這兩個(gè)串是一個(gè)SHA算法SecureHashAlgorithm62精選pptSHA算法SecureHashAlgorithm62精算法簡介美國標(biāo)準(zhǔn)與技術(shù)研究所NIST設(shè)計(jì)1993年成為聯(lián)邦信息處理標(biāo)準(zhǔn)(FIPSPUB180)基于MD4算法，與之非常類似。輸入為小于264比特長的任意消息分組512bit長輸出160bit63精選ppt算法簡介美國標(biāo)準(zhǔn)與技術(shù)研究所NIST設(shè)計(jì)63精選ppt迭代型hash函數(shù)的一般結(jié)構(gòu)fffY0Y1YL-1bbbnnnnnIV=CV0CV1CVL-1CVL明文M被分為L個(gè)分組Y0,Y1,…,YL-1b:明文分組長度n:輸出hash長度CV：各級輸出，最后一個(gè)輸出值是hash值無碰撞壓縮函數(shù)f是設(shè)計(jì)的關(guān)鍵64精選ppt迭代型hash函數(shù)的一般結(jié)構(gòu)fffY0Y1YL-1bbbnn算法描述消息填充：與MD5完全相同附加消息長度：64bit長度緩沖區(qū)初始化A＝67452301B＝EFCDAB89C＝98BADCFBD＝10325476E＝C3D2E1F065精選ppt算法描述消息填充：與MD5完全相同65精選ppt分組處理模232加66精選ppt分組處理模232加66精選pptSHA-1壓縮函數(shù)（單步）67精選pptSHA-1壓縮函數(shù)（單步）67精選pptft----基本邏輯函數(shù)68精選pptft----基本邏輯函數(shù)68精選pptCLS5：32位的變量循環(huán)左移5位。CLS30：32位的變量循環(huán)左移30位。69精選pptCLS5：32位的變量循環(huán)左移5位。69精選pptWt---從當(dāng)前512位輸入分組導(dǎo)出的32位字前16個(gè)值（即W0,W1,…,W15）直接取為輸入分組的16個(gè)相應(yīng)的字，其余值（即W16,W17,…,W79）取為70精選pptWt---從當(dāng)前512位輸入分組導(dǎo)出的32位字前16個(gè)值（Kt---加法常量步驟十六進(jìn)制0≤t≤19Kt=5A82799920≤t≤39Kt=6ED9EBA140≤t≤59Kt=8F1BBCDC60≤t≤79Kt=CA62C1D671精選pptKt---加法常量步驟十六進(jìn)制0≤t≤19Kt=5A827SHA與MD5的比較抗窮舉搜索能力尋找指定hash值，SHA：O(2160)，MD5：O(2128)生日攻擊：SHA：O(280)，MD5：O(264)抗密碼分析攻擊的強(qiáng)度SHA似乎高于MD5速度SHA較MD5慢簡捷與緊致性描述都比較簡單，都不需要大的程序和代換表72精選pptSHA與MD5的比較抗窮舉搜索能力72精選ppt2005年2月15日，在美國召開的國際信息安全RSA研討會(huì)上，國際著名密碼學(xué)專家AdiShamir宣布，他收到了來自中國山東大學(xué)王小云、尹依群、于紅波等三人的論文，論文證明SHA-1在理論上也被破解。她證明了160位SHA-1，只需要大約269次計(jì)算就能找出來，而理論值是280次。73精選ppt2005年2月15日，在美國召開的國際信息安全RSA研討會(huì)上其它hash算法MD4MD4使用三輪運(yùn)算，每輪16步；MD5使用四輪運(yùn)算，每輪16步。MD4的第一輪沒有使用加法常量，第二輪運(yùn)算中每步迭代使用的加法常量相同，第三輪運(yùn)算中每步迭代使用的加法常量相同，但不同于第二輪使用的加法常量；MD5的64部使用的加法常量T[i]均不同。MD4使用三個(gè)基本邏輯函數(shù)，MD5使用四個(gè)。MD5中每步迭代的結(jié)果都與前一步的結(jié)果相加，MD4則沒有。MD5比MD4更復(fù)雜，所以其執(zhí)行速度也更慢，Rivest認(rèn)為增加復(fù)雜性可以增加安全性。74精選ppt其它hash算法MD474精選pptRIPEMD-160歐共體RIPE項(xiàng)目組研制。輸入可以是任意長的報(bào)文，輸出160位摘要。對輸入按512位分組。以分組為單位處理。算法的核心是具有十輪運(yùn)算的模塊，十輪運(yùn)算分成兩組，每組五輪，每輪16步迭代。75精選pptRIPEMD-160歐共體RIPE項(xiàng)目組研制。75精選ppt5.4.4對Hash函數(shù)的攻擊對一個(gè)hash算法的攻擊可分三個(gè)級別：預(yù)映射攻擊（PreimageAttack）：給定Hash值h，找到其所對應(yīng)的明文M，使得Hash(M)=h，這種攻擊是最徹底的，如果一個(gè)hash算法被人找出預(yù)映射，那這種算法是不能使用的。次預(yù)映射攻擊（SecondPreimageAttack）：給定明文M1，找到另一明文M2（M1≠M(fèi)2），使得hash(M1)=hash(M2)，這種攻擊其實(shí)就是要尋找一個(gè)弱碰撞；碰撞攻擊(CollisionAttack)：找到M1和M2，使得hash(M1)=hash(M2)，這種攻擊其實(shí)就是要尋找一個(gè)強(qiáng)碰撞。76精選ppt5.4.4對Hash函數(shù)的攻擊對一個(gè)hash算法的攻擊可生日攻擊給定一個(gè)散列函數(shù)H和某hash值H(x)，假定H有n個(gè)可能的輸出。如果H有k個(gè)隨機(jī)輸入,k必須為多大才能使至少存在一個(gè)輸入y,使得H(y)=H(x)的概率大于0.5？77精選ppt生日攻擊給定一個(gè)散列函數(shù)H和某hash值H(x)，假定H有n結(jié)論如果hash碼為m位，則有2m個(gè)可能的hash碼。如果給定h=H(X)，要想找到一個(gè)y，使H(y)=h的概率為0.5，則要進(jìn)行多次的嘗試，嘗試的次數(shù)k=2m/2=2m-1所以，對于一個(gè)使用64位的hash碼，攻擊者要想找到滿足H(M’)=H(M)的M’來替代M，平均來講，他要找到這樣的消息大約要進(jìn)行263次嘗試。但是，存在一種攻擊，稱為“生日攻擊”，卻可以大大減小嘗試的次數(shù)，對于64位的hash碼，所需的代價(jià)僅為232次。78精選ppt結(jié)論如果hash碼為m位，則有2m個(gè)可能的hash碼。78精生日悖論一個(gè)教室中，最少應(yīng)有多少學(xué)生，才使至少有兩人具有相同生日的概率不小于1/2？79精選ppt生日悖論一個(gè)教室中，最少應(yīng)有多少學(xué)生，才使至少有兩人具有相同生日悖論概率結(jié)果與人的直覺是相違背的.實(shí)際上只需23人,即任找23人，從中總能選出兩人具有相同生日的概率至少為1/2。80精選ppt生日悖論80精選ppt一個(gè)不等式：(1-x)≤e-x(x≥0)當(dāng)x很小，趨近于0時(shí)，(1-x)≈e-x81精選ppt一個(gè)不等式：(1-x)≤e-x(x≥0)當(dāng)x很小，趨近于兩個(gè)集合中元素的重復(fù)給定兩個(gè)集合X和Y，每個(gè)集合有k個(gè)元素：X:{x1,x2,…,xk},Y:{y1,y2,…,yk},其中，各元素的取值是1~n之間的均勻分布的隨機(jī)值(k<n)那么，這兩個(gè)集合中至少有一個(gè)元素相同(重復(fù))的概率R(n,k)是多