《認(rèn)證哈希算法》PPT課件

第十一講認(rèn)證、哈希算法,上海交通大學(xué)計(jì)算機(jī)科學(xué)系,1.MessageAuthentication,消息認(rèn)證包括:消息完整性身份識(shí)別不可否認(rèn)性,2.消息認(rèn)證碼(MAC),messageauthenticationcode(MAC)簽名的電子等價(jià)形式與消息同時(shí)發(fā)送通過(guò)一些算法,依賴于消息及雙方共享的秘密消息可以是不任意長(zhǎng)MAC可以是任意長(zhǎng),但常選固定長(zhǎng)度這需要hashfunction“壓縮”消息成固定長(zhǎng)度,3.消息認(rèn)證過(guò)程,4.1利用對(duì)稱密碼進(jìn)行認(rèn)證,利用對(duì)稱密碼加密的消息可以作為認(rèn)證內(nèi)容因?yàn)橹挥忻荑€的擁有者才可以生成(要求消息有一定的冗余度)但不能解決消息的不可否認(rèn)性（無(wú)法證明誰(shuí)生成的消息）,4.2報(bào)文鑒別碼,H,H(M),H,H,5.HashingFunctions,把任意長(zhǎng)的消息“壓縮”成固定長(zhǎng)的消息的算法數(shù)字簽名時(shí)，常被使用通常，HASH函數(shù)是公開(kāi)的輸出長(zhǎng)度應(yīng)足夠大，防止生日攻擊64-bits認(rèn)為太小通常128-512bits,6.Hash函數(shù)設(shè)計(jì)原理,H能用于任何大小的數(shù)據(jù)分組;H產(chǎn)生定長(zhǎng)輸出;對(duì)任意給定的x,H(x)要相對(duì)易于計(jì)算,使得軟硬件實(shí)現(xiàn)都實(shí)際可行;對(duì)任意給定的碼h,尋求x使得H(x)=h在計(jì)算上是不可行的(單向性);任意給定分組x,尋求不等于x的y,使得H(y)=H(x)在計(jì)算上不可行(弱抗攻擊性);尋求對(duì)任何的(x,y)對(duì)使得H(x)=H(y)在計(jì)算上不可行(強(qiáng)抗攻擊性);,7Hash函數(shù)設(shè)計(jì)原理,生日攻擊(基于生日悖論)在k個(gè)人中,找一個(gè)與某人生日相同的人的概率超過(guò)0.5時(shí),只需k183;而在此人群中,至少有兩個(gè)人生日相同的概率超過(guò)0.5,只需k23.,b,Y0,n,f,b,Y1,n,f,b,YL-1,n,CVL-1,f,CV1,n,n,IV=初始值CV=鏈接值Yi=第i個(gè)輸入數(shù)據(jù)塊f=壓縮算法n=散列碼的長(zhǎng)度b=輸入塊的長(zhǎng)度,8安全雜湊算法的一般結(jié)構(gòu),CVL,CV0=IV=initialn-bitvalueCVi=f(CVi-1,Yi-1)(1iL)H(M)=CVL,9MD5算法邏輯,輸入：任意長(zhǎng)度的消息輸出：128位消息摘要處理：以512位輸入數(shù)據(jù)塊為單位MD5(RFC1321)developedbyRonRivestatMITin90s.,報(bào)文,Kbits,L512bits=N32bits,1000,Y0,512bits,Y1,512bits,Yq,512bits,YL-1,512bits,HMD5,IV,128,HMD5,CV1,128,HMD5,CVq,128,HMD5,CVL-1,128,512,512,512,512,128-bit摘要,MD5產(chǎn)生報(bào)文摘要的過(guò)程,11MD5算法描述,步驟1：添加填充位(一個(gè)1和若干個(gè)0)。在消息的最后添加適當(dāng)?shù)奶畛湮皇沟脭?shù)據(jù)位的長(zhǎng)度滿足length448mod512。步驟2：添加長(zhǎng)度。原始消息長(zhǎng)度（二進(jìn)制位的個(gè)數(shù)），用64位表示。表示為L(zhǎng)個(gè)512位的數(shù)據(jù)塊：Y0,Y1,YL-1。其長(zhǎng)度為L(zhǎng)512bits。令N=L16,則長(zhǎng)度為N個(gè)32位的字。令M0N-1表示以字為單位的消息表示。,12MD5算法描述(Cont.),步驟3：初始化MD緩沖區(qū)。一個(gè)128位MD緩沖區(qū)用以保存中間和最終散列函數(shù)的結(jié)果。它可以表示為4個(gè)32位的寄存器(A,B,C,D)。寄存器初始化為以下的16進(jìn)制值。A=67452301B=EFCDAB89C=98BADCFED=10325476,13,WordA:01234567WordB:89ABCDEFWordC:FEDCBA98WordD:76543210,14MD5算法描述(Cont.),步驟4：處理消息塊（512位=16個(gè)32位字）。一個(gè)壓縮函數(shù)是本算法的核心(HMD5)。它包括4輪處理。四輪處理具有相似的結(jié)構(gòu),但每次使用不同的基本邏輯函數(shù)，記為F,G,H,I。每一輪以當(dāng)前的512位數(shù)據(jù)塊(Yq)和128位緩沖值A(chǔ)BCD作為輸入，并修改緩沖值的內(nèi)容。每次使用64元素表T164中的四分之一,T表，由sin函數(shù)構(gòu)造而成。T的第i個(gè)元素表示為T(mén)i，其值等于232abs(sin(i),其中i是弧度。由于abs(sin(i)是一個(gè)0到1之間的數(shù)，T的每一個(gè)元素是一個(gè)可以表示成32位的整數(shù)。T表提供了隨機(jī)化的32位模板，消除了在輸入數(shù)據(jù)中的任何規(guī)律性的特征,15T表,T49=F4292244T50=432AFF97T51=AB9423A7T52=FC93A039T64=EB86D391,T1=D76AA478T2=E8C7B756T3=242070DBT4=C1BDCEEET16=49b40821,16MD5算法描述(Cont.),步驟5：輸出結(jié)果。所有L個(gè)512位數(shù)據(jù)塊處理完畢后，最后的結(jié)果就是128位消息摘要。CV0=IVCVq+1=SUM32(CVq,RFIYq,RFHYq,RFGYq,RFFYq,CVq)MD=CVL其中：IV=ABCD的初始值（見(jiàn)步驟3）Yq=消息的第q個(gè)512位數(shù)據(jù)塊L=消息中數(shù)據(jù)塊數(shù)；CVq=鏈接變量，用于第q個(gè)數(shù)據(jù)塊的處理RFx=使用基本邏輯函數(shù)x的一輪功能函數(shù)。MD=最終消息摘要結(jié)果SUM32=分別按32位字計(jì)算的模232加法結(jié)果。,F,T116,Xi16steps,G,T1732,X2i16steps,H,T3348,X3i16steps,I,T4964,X4i16steps,+,+,+,+,A,B,C,D,A,B,C,D,A,B,C,D,A,B,C,D,CVq,128,32,Yq,512,CVq+1,128,+ismod232,單個(gè)512-bit分組的MD5處理過(guò)程,17MD5壓縮函數(shù),每一輪包含對(duì)緩沖區(qū)ABCD的16步操作所組成的一個(gè)序列。ab+(a+g(b,c,d)+Xk+Ti)s)其中，a,b,c,d=緩沖區(qū)的四個(gè)字，以一個(gè)給定的次序排列;g=基本邏輯函數(shù)F,G,H,I之一；s=對(duì)32位字循環(huán)左移s位Xk=Mq16+k=在第q個(gè)512位數(shù)據(jù)塊中的第k個(gè)32位字Ti=表T中的第i個(gè)32位字；+=模232的加；,A,B,C,D,A,B,C,D,+,+,+,CLSs,+,g,Xk,Ti,2i=(1+5i)mod163i=(5+3i)mod162i=7imod16,基本MD5操作(單步),Functiongg(b,c,d)1F(b,c,d)(bc)(bd)2G(b,c,d)(bd)(cd)3H(b,c,d)bcd4I(b,c,d)c(bd),19MD4(1990年10月作為RFC1320發(fā)表)byRonRivestatMIT,MD4的設(shè)計(jì)目標(biāo)安全性：速度：32位體系結(jié)構(gòu)下計(jì)算速度快.簡(jiǎn)明與緊湊：易于編程.有利的小數(shù)在前的結(jié)