第讲--认证哈希算法优秀文档

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第十一讲 认证、哈希算法,上海交通大学计算机科学系,1.Message Authentication,消息认证包括:,消息完整性,身份识别,不可否认性,2.消息认证码(MAC),message authentication code(MAC),签名的电子等价形式,与消息同时发送,通过一些算法,依赖于消息及双方共享的秘密,消息可以是不任意长,MAC 可以是任意长,但常选固定长度,这需要,hash function,“压缩”消息成固定长度,Message Authentication,a,b,c,d =缓冲区的四个字，以一个给定的次序排列;,MD5产生报文摘要的过程,T表提供了随机化的32位模板，消除了在输入数据中的任何规律性的特征,11 MD5算法描述,Hash 函数设计原理,4 I(b,c,d)c(bd),令N=L16,则长度,C=98BADCFE,H能用于任何大小的数据分组;,3i=(5+3i)mod 16,H能用于任何大小的数据分组;,MD=CVL,Message Authentication,(要求消息有一定的冗余度),3.消息认证过程,4.利用对称密码进行认证,利用对称密码加密的消息可以作为认证内容,因为只有密钥的拥有者才可以生成,(要求消息有一定的冗余度),但不能解决消息的不可否认性,（无法证明谁生成的消息）,5.Hashing Functions,把任意长的消息“压缩”成固定长的消息的算法,数字签名时，常被使用,通常，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)在计算上不可行(强抗攻击性);,7 Hash 函数设计原理,生日攻击(基于生日悖论),在k个人中,找一个与某人生日相同的人的,概率超过0.5时,只需k183;而在此人群中,至少有两个人生日相同的概率超过0.5,只需,k23.,b,Y,0,n,f,b,Y,1,n,f,b,Y,L-1,n,CV,L-1,f,CV,1,n,n,IV =,初始值,CV=链接值,Yi =第i 个输入数据块,f =压缩算法,n =散列码的长度,b =输入块的长度,8 安全杂凑算法的一般结构,CV,L,CV,0,=IV=initial n-bit value,CV,i,=f(CV,i-1,Y,i-1,)(1,i,L),H(M)=CV,L,9 MD5 算法逻辑,输入：任意长度的消息,输出：128位消息摘要,处理：以512位输入数据块为单位,MD5(RFC 1321)developed by Ron Rivest at MIT in 90s.,报文,K bits,L,512,bits=N,32bits,报文长度,(K mod 2,64,),1000,Y,0,512 bits,Y,1,512 bits,Y,q,512 bits,Y,L-1,512 bits,H,MD5,IV,128,H,MD5,CV,1,128,H,MD5,CV,q,128,H,MD5,CV,L-1,128,512,512,512,512,128-bit,摘要,MD5产生报文摘要的过程,填充,(1 to 512 bits),11 MD5算法描述,步骤1：,添加填充位(一个1 和若干个0)。在消息的最后添加适当的填充位使得数据位的长度满足length,448 mod 512。,步骤2：,添加长度。原始消息长度（二进制位的个数），用64位表示。,表示为L个512位的数据块：Y,0,Y,1,Y,L-1,。,其长度为L,512bits。令N=,L,16,则长度,为N个32位的字。令M0N-1表示以字为单位的消息表示。,B=EFCDAB89,1 F(b,c,d)(bc)(bd),17 MD5 压缩函数,F,T116,Xi,Word D:76 54 32 10,至少有两个人生日相同的概率超过0.,T51 =AB9423A7,L512 bits=N 32bits,一个128位MD缓冲区用以保存中间和最终散列函数的结果。,A=67452301,原始消息长度（二进制位的个数），用64位表示。,2 G(b,c,d)(bd)(cd),B=EFCDAB89,(K mod 264),19 MD4(1990年10月作为RFC1320发表)by Ron Rivest at MIT,Hash 函数设计原理,A=67452301,12 MD5算法描述(Cont.),步骤3：初始化MD缓冲区。一个128位MD缓冲区用以保存中间和最终散列函数的结果。它可以表示为4个32位的寄存器(A,B,C,D)。,寄存器初始化为以下的16进制值。,A=67452301,B=EFCDAB89,C=98BADCFE,D=10325476,13,Word A:01 23 45 67,Word B:89 AB CD EF,Word C:FE DC BA 98,Word D:76 54 32 10,14 MD5算法描述(Cont.),步骤4：处理消息块（512位=16个32位字）。一个压缩函数是本算法的核心(H,MD5,)。它包括4轮处理。四轮处理具有相似的结构,但每次使用不同的基本逻辑函数，记为F,G,H,I。每一轮以当前的512位数据块(Y,q,)和128位缓冲值ABCD,作为输入，并修改缓冲值的内容。每次使用64元素表T164中的四分之一,T,表，由sin 函数构造而成。T的第i个元素表示为Ti，其值等于 2,32,abs(sin(i),其中i是弧度。由于abs(sin(i)是一个0到1之间的数，T的每一个元素是一个可以表示成32位的整数。T表提供了随机化的32位模板，消除了在输入数据中的任何规律性的特征,15 T 表,T49 =F4292244,T50 =432AFF97,T51 =AB9423A7,T52 =FC93A039,T64 =EB86D391,T1 =D76AA478,T2 =E8C7B756,T3 =242070DB,T4 =C1BDCEEE,T16 =49b40821,速度：32位体系结构下计算速度快.,(K mod 264),输出长度应足够大，防止生日攻击,RFx =使用基本逻辑函数x的一轮功能函数。,上海交通大学计算机科学系,Word D:76 54 32 10,Hashing Functions,Hash 函数设计原理,Function g g(b,c,d),17 MD5 压缩函数,64-bits 认为太小,输出长度应足够大，防止生日攻击,64-bits 认为太小,16 MD5算法描述(Cont.),步骤5：输出结果。所有L个512位数据块处理完毕后，最后的结果就是128位消息摘要。,CV0=IV,CV,q+1,=SUM,32,(CV,q,RF,I,Y,q,RF,H,Y,q,RF,G,Y,q,RF,F,Y,q,CV,q,),MD=CV,L,其中：IV =ABCD,的初始值（见步骤3）,Y,q,=消息的第q个512位数据块,L =消息中数据块数；,CVq =链接变量，用于第q个数据块的处理,RFx =使用基本逻辑函数x的一轮功能函数。,MD =最终消息摘要结果,SUM,32,=分别按32位字计算的模2,32,加法结果。,F,T116,Xi,16 steps,G,T1732,X,2,i,16 steps,H,T3348,X,3,i,16 steps,I,T4964,X,4,i,16 steps,+,+,+,+,A,B,C,D,A,B,C,D,A,B,C,D,A,B,C,D,CV,q,128,32,Y,q,512,CV,q+1,128,+is mod 2,32,单个 512-bit 分组的,MD5 处理过程,17 MD5 压缩函数,每一轮包含对缓冲区ABCD的16步操作所组成的一个序列。,a,b+(a+g(b,c,d)+Xk+Ti)s),其中，,a,b,c,d =缓冲区的四个字，以一个给定的次序排列;,g =基本逻辑函数F,G,H,I之一；,s =对32位字循环左移s位,Xk =Mq,16+k=在第q个512位数据块中的第k个32位字,Ti =,表T中的第i个32位字；,+=模 2,32,的加；,A,B,C,D,A,B,C,D,+,+,+,CLSs,+,g,Xk,Ti,2,i=(1+5i)mod 16,3,i=(5+3i)mod 16,2,i=7i mod 16,基本MD5操作(单步,),Function g g(b,c,d),1 F(b,c,d)(b,c)(bd),2 G(b,c,d)(bd)(cd),3 H(b,c,d)bcd,4 I(b,c,d)c(bd),19 MD4,(1990年10月作为RFC1320发表)by Ron Rivest at MIT,MD4的设计目标,安全性：,速度：32位体系结构下计算速度快.,简明与紧凑：易于编程.,有利的小数在前的结构,(Intel 80 xxx,Pentium),MD4与MD5的区别,MD4用3轮,每轮16 步,MD5,用4轮,每轮16步.,MD4中第一轮没有常量加；MD5中64步每一步用了一个不同的常量 Ti；,MD5用了四个基本逻辑函数，每轮一个；MD4用了三个.,MD5每轮加上前一步的结果；MD4没有.,END,