第11章 杂凑hash）函数.ppt

第11章杂凑(hash),若下面两个条件成立。(1)计算hn(x)是容易的,即存在一个多项式时间算法F,若F的输入为1n和 ,则其输出为hn(x)。(2)给定算法F要找两个不同的消息,使得是困难的,即对每一个多项式时间概率算法M’,每一正多项式p(n)和一切充分大的n有() 其中Un表示{0,1}n上的均匀分布随机变量。,则它也是一个强无碰撞压缩函数族。反之,若函数族 为一强无碰撞压缩函数族,且对(充分大的)每个n及x∈{0,1}n,hn(x)的原象集中至少包含两个原象,则它也是一个强单向函数族。强无碰撞压缩函数族中的函数也称无碰撞压缩函数或单向压缩函数。。(1)h可应用于任意长的消息或文件;(2)h的值(杂凑值)是固定长的,但要足够长才能抵抗生日攻击。(3)计算h的值h(x)是容易的,即h(x)是多项式时间可计算的;(4)给定算法h,要找两个不同的消息x1≠x2,使其杂凑值h(x1)=h(x2)是困难的(计算不可行的),即是由强无碰撞压缩函数族中的压缩函数所构造的(构造方法见后)。,其中l≥m+2为一选定的正整数。首先将输入h的消息分为长l-m-1的组,记作 。若x的长|x|不能被l-m-1整除,则在xr后面添加d个0使n=|x|+d被l-m-1整除。不妨将x,0d仍记作x,使|xr|=l-m-1,再附加一个分组xr+1,它由d的二进数表示在其前面添加若干个0构成,使|xr+1|=l-m-1。杂凑函数h(x)的值由下面的迭代算法定义。。-1nCVL-1fCV1nnIV=初始值CV=链接值Yi=第i个输入数据块f=压缩算法n=散列码的长度b=输入块的长度8安全杂凑算法的一般结构CVLCV0=IV=initialn-bitvalueCVi=f(CVi-1,Yi-1)(1iL)H(M)=CVL9MD5算法逻辑输入:任意长度的消息输出:128位消息摘要处理:以512位输入数据块为单位MD5(RFC1321)developedbyRonRivestatMITin90’512bits=N32bits报文长度(Kmod264)100…0Y0512bitsY1512bitsYq512bitsYL-1512bitsHMD5IV128HMD5CV1128HMD5CVq128HMD5CVL-11285125**********-bit摘要MD5产生报文摘要的过程填充(1to512bits)11MD5算法描述步骤1:添加填充位(一个1和若干个0)。在消息的最后添加适当的填充位使得数据位的长度满足length448mod512。步骤2:添加长度。原始消息长度(二进制位的个数),用64位表示。表示为L个512位的数据块:Y0,Y1,…,YL-1。其长度为L512bits。令N=L16,则长度为N个32位的字。令M[0…N-1]表示以字为单位的消息表示。