《认证哈希算法》PPT课件

第十一讲认证、哈希算法,上海交通大学计算机科学系,1.MessageAuthentication,消息认证包括:消息完整性身份识别不可否认性,2.消息认证码(MAC),messageauthenticationcode(MAC)签名的电子等价形式与消息同时发送通过一些算法,依赖于消息及双方共享的秘密消息可以是不任意长MAC可以是任意长,但常选固定长度这需要hashfunction“压缩”消息成固定长度,3.消息认证过程,4.1利用对称密码进行认证,利用对称密码加密的消息可以作为认证内容因为只有密钥的拥有者才可以生成(要求消息有一定的冗余度)但不能解决消息的不可否认性（无法证明谁生成的消息）,4.2报文鉴别码,H,H(M),H,H,5.HashingFunctions,把任意长的消息“压缩”成固定长的消息的算法数字签名时，常被使用通常，HASH函数是公开的输出长度应足够大，防止生日攻击64-bits认为太小通常128-512bits,6.Hash函数设计原理,H能用于任何大小的数据分组;H产生定长输出;对任意给定的x,H(x)要相对易于计算,使得软硬件实现都实际可行;对任意给定的码h,寻求x使得H(x)=h在计算上是不可行的(单向性);任意给定分组x,寻求不等于x的y,使得H(y)=H(x)在计算上不可行(弱抗攻击性);寻求对任何的(x,y)对使得H(x)=H(y)在计算上不可行(强抗攻击性);,7Hash函数设计原理,生日攻击(基于生日悖论)在k个人中,找一个与某人生日相同的人的概率超过0.5时,只需k183;而在此人群中,至少有两个人生日相同的概率超过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个输入数据块f=压缩算法n=散列码的长度b=输入块的长度,8安全杂凑算法的一般结构,CVL,CV0=IV=initialn-bitvalueCVi=f(CVi-1,Yi-1)(1iL)H(M)=CVL,9MD5算法逻辑,输入：任意长度的消息输出：128位消息摘要处理：以512位输入数据块为单位MD5(RFC1321)developedbyRonRivestatMITin90s.,报文,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产生报文摘要的过程,11MD5算法描述,步骤1：添加填充位(一个1和若干个0)。在消息的最后添加适当的填充位使得数据位的长度满足length448mod512。步骤2：添加长度。原始消息长度（二进制位的个数），用64位表示。表示为L个512位的数据块：Y0,Y1,YL-1。其长度为L512bits。令N=L16,则长度为N个32位的字。令M0N-1表示以字为单位的消息表示。,12MD5算法描述(Cont.),步骤3：初始化MD缓冲区。一个128位MD缓冲区用以保存中间和最终散列函数的结果。它可以表示为4个32位的寄存器(A,B,C,D)。寄存器初始化为以下的16进制值。A=67452301B=EFCDAB89C=98BADCFED=10325476,13,WordA:01234567WordB:89ABCDEFWordC:FEDCBA98WordD:76543210,14MD5算法描述(Cont.),步骤4：处理消息块（512位=16个32位字）。一个压缩函数是本算法的核心(HMD5)。它包括4轮处理。四轮处理具有相似的结构,但每次使用不同的基本逻辑函数，记为F,G,H,I。每一轮以当前的512位数据块(Yq)和128位缓冲值ABCD作为输入，并修改缓冲值的内容。每次使用64元素表T164中的四分之一,T表，由sin函数构造而成。T的第i个元素表示为Ti，其值等于232abs(sin(i),其中i是弧度。由于abs(sin(i)是一个0到1之间的数，T的每一个元素是一个可以表示成32位的整数。T表提供了随机化的32位模板，消除了在输入数据中的任何规律性的特征,15T表,T49=F4292244T50=432AFF97T51=AB9423A7T52=FC93A039T64=EB86D391,T1=D76AA478T2=E8C7B756T3=242070DBT4=C1BDCEEET16=49b40821,16MD5算法描述(Cont.),步骤5：输出结果。所有L个512位数据块处理完毕后，最后的结果就是128位消息摘要。CV0=IVCVq+1=SUM32(CVq,RFIYq,RFHYq,RFGYq,RFFYq,CVq)MD=CVL其中：IV=ABCD的初始值（见步骤3）Yq=消息的第q个512位数据块L=消息中数据块数；CVq=链接变量，用于第q个数据块的处理RFx=使用基本逻辑函数x的一轮功能函数。MD=最终消息摘要结果SUM32=分别按32位字计算的模232加法结果。,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,单个512-bit分组的MD5处理过程,17MD5压缩函数,每一轮包含对缓冲区ABCD的16步操作所组成的一个序列。ab+(a+g(b,c,d)+Xk+Ti)s)其中，a,b,c,d=缓冲区的四个字，以一个给定的次序排列;g=基本逻辑函数F,G,H,I之一；s=对32位字循环左移s位Xk=Mq16+k=在第q个512位数据块中的第k个32位字Ti=表T中的第i个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发表)byRonRivestatMIT,MD4的设计目标安全性：速度：32位体系结构下计算速度快.简明与紧凑：易于编程.有利的小数在前的结