1、第九章 散列算法1 离散对数的散列函数算法(ChaumVan, HeijstPfitzmann散列算法）设 P是一个大素数，且 q=(p-1)/2也为素数，取定 FP（ P元有限域）中的一个本原元 ， 给定一个保密的指数 ，（ ， p1） =1， 于是 =也为 FP中的本原元。值=log不公开，计算这个对数值是计算上难处理的。散列算法h:0,1,q-1 0,1,q-1 Fp*定义为h(x1,x2)=x1x2(mod p)下面要证明，散列算法 h是强无碰撞的！相当于证明 :定理定理 ：若上述算法 h的碰撞算法是可行的，那么计算离散对数 log也是可行的。证明：假设我们给了一个碰撞 h （ x1,
2、 x2） =h （ x3, x4） 其中 （ x1,x2） （ x3, x4）， 则有下列同余式x1x2x3x4(modp)也即， x1-x3x4-x2(mod p)记 gcd(x4-x2,p-1)=d， 易 见 d 1,2,q,p-1 ， 原因是 p1=2q.1若 d=1， 此时可设y= （ x4x2） 1（ mod p1）有 (x4-x2)y(mod p) (x1-x3)y(modp)于是，计算出离散对数log=（ x1x3） y=（ x1x3）（ x4x2） 1 （ mod p1）2若 d=2: 由 p-1=2q, q为奇素数，必有 gcd （ x4-x2, q） =1,设 y= （ x
3、4-x2） -1 （ mod q）于是 （ x4-x2） * y1 （ mod q）也就是存在整数 k使得（ x4-x2） *y=k*q+1所以 (x4-x2)*yk*q+1(mod p)(-1)k(mod p) (因为 (p-1)/2 -1(mod p) (modp)这样 (x1-x2)y (x4-x2)*y(modp) (mod p)(i)若 (x1-x3)y (mod p)则 log=(x1-x3)y (mod p-1)(ii)若 (x1-x3)y (mod p) (p-1)/2*(mod p)=(x1-x3)y*(p-1)/2 (mod p)所以， log=(x1-x3)y+(p-1)
4、/2(mod p-1)可见，（ i）、（ ii） 都是易计算的。3若 d=q:因为 0x2q-1,0x4q-1有结果， gcd（ x4-x2, p-1） =q是不可能的。4若 d=p-1， 此时仅当 x4=x2时发生，此时有x1x2x3x2(mod p)x1 x3(mod p)=x1=x3于是，（ x1,x2） =（ x3,x4） 与假设矛盾，此种情况不可能发生。综上知，如果计算 FP中离散对数 log是不可行的，那么我们推出该算法 h是强无碰撞的。2 扩展的散列函数我们已研究过具有有限定义域的散列函数。现在研究如何把具有有限定义域的强无碰撞的散列函数扩展为具有无限定义域的强无碰撞散列函数，这
5、将使我们能签名任意长度的消息。假设 h: (F2)m(F2)t是一个强无碰撞的散列函数，这里mt+1。 我们的目的是想从 h入手，构造无限定义域的散列函数 h*:X(F2)t,其中首先考虑首先考虑 mt+2的情况：的情况：符号： |x|表示 x的长度。（比特数目）x|y表示比特串 x和 y的并。假设 |x|=n m，（ x为一段信息 bit串）则先将 x表为 x=x1|x2| xk这里 ,|x1|=|x2|=| xk-1|=m-t-1且|xk|=m-t-1-d， 易 见 0dm-t-2而 k=n/(m-t-1) （ 上整数部分）下面给出扩展的散列函数下面给出扩展的散列函数 h*的生成算法：的生
6、成算法：从 h到 h*算法，注意 |x|=n m， mt+2情形：x=x1|x2| xk; |x1|=|x2|=| xk-1|=m-t-1; |xk|=m-t-1-d1对 i=1到 k-1做 yi=xi2yk=xk|od3设 yk+1是 d的二进制表示， (右边补 0,使 yk+1=m-t-1)4g1=h（ ot+1|y1）5对 i=1到 k做 gi+1=h(gi|1|yi+1)6h*(x)=gk+1注：可以记 y(x)=y1|y2| yk|yk+1,其中 yk是由 xk后面（右边）补上 d个零来形成的，所以所有的块 yi（ 1ik） 的长度为 m-t-1； 在第 3步中也将在yk+1的左边补
7、上零，使得 |yk+1|=m-t-1。为了散列 x， 首先构造 y（ x）， 然后以特定方式处理块（分组） y1， y2， ， yk+1。 对于任意数对 x,x,只要xx ， 易 见 y（ x） y（ x ）。下面证明，在下面证明，在 h是安全的前提下，是安全的前提下， h*也是安全的！也是安全的！定理定理 ，假设 h: (F2)m|(F2)t 是一个强无碰撞的散列函数，这里 mt+2。 那么按上述方式所构造的函数 h*: 是一个强无碰撞的散列函数。证明：（假设我们能找到 xx 满足 h*(x)=h*(x )， 那么如果能证明在多项式时间内可找到 h的一个碰撞，这就与 h假设为强无碰撞的事实矛盾，这样就证明了 h*为强无碰撞的散列函数。）若有方法找到 xx 使 h*(x)=h*(x )：记 y(x)=y1|y2| yk|yk+1和 y(x )=y1 |y2 | yl |yl+1 考虑上述算法中，第 2步 x和 x 分别补上 d个和 d 个零；记第 4步，第 5步计算出的值分别为 g1, ， gk+1和g 1,g l+1。对于 |x|不知道是否 |x | (mod m-t 1),分两种情况：
