第九章散列算法

《第九章散列算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第九章散列算法1离散对数的散列函数算法(Chaum–Van,Heijst–Pfitzmann散列算法）设P是一个大素数，且q=(p-1)/2也为素数，取定FP（P元有限域）中的一个本原元α，给定一个保密的指数λ，（λ，p–1）=1，于是β=αλ也为FP中的本原元。值λ=logαβ不公开，计算这个对数值是计算上难处理的。散列算法h:{0,1,…,q-1}{0,1,…,q-1}Fp*定义为h(x1,x2)=αx1βx2(modp)下面要证明，散列算法h是强无碰撞的！相当于证明:定理：若上述算法h的碰撞算法是可行的，那么计算离散对数logαβ也是可行的。证明：假设我们给了一

2、个碰撞h（x1,x2）=h（x3,x4）其中（x1,x2）≠（x3,x4），则有下列同余式αx1βx2≡αx3βx4(modp)也即，αx1-x3βx4-x2(modp)记gcd(x4-x2,p-1)=d，易见d∈{1,2,q,p-1}，原因是p–1=2q.1°若d=1，此时可设y=（x4–x2）–1（modp–1）有ββ(x4-x2)y(modp)α(x1-x3)y(modp)于是，计算出离散对数logαβ=（x1–x3）y=（x1–x3）（x4–x2）–1（modp–1）2°若d=2:由p-1=2q,q为奇素数，必有gcd（x4-x2,q）=1,设y=（x4-x

3、2）-1（modq）于是（x4-x2）*y≡1（modq）也就是存在整数k使得（x4-x2）*y=k*q+1所以β(x4-x2)*yβk*q+1(modp)(-1)kβ(modp)(因为β(p-1)/2-1(modp))β(modp)这样α(x1-x2)yβ(x4-x2)*y(modp)±β(modp)(i)若α(x1-x3)yβ(modp)则logαβ=(x1-x3)y(modp-1)(ii)若α(x1-x3)yβ(modp)α(p-1)/2*β(modp)==>α(x1-x3)y*α(p-1)/2β(modp)所以，logαβ=(x1-x3)y

4、+(p-1)/2(modp-1)可见，（i）、（ii）都是易计算的。3°若d=q:因为0≤x2≤q-1,0≤x4≤q-1有结果，gcd（x4-x2,p-1）=q是不可能的。4°若d=p-1，此时仅当x4=x2时发生，此时有αx1βx2αx3βx2(modp)αx1αx3(modp)=>x1=x3于是，（x1,x2）=（x3,x4）与假设矛盾，此种情况不可能发生。综上知，如果计算FP中离散对数logαβ是不可行的，那么我们推出该算法h是强无碰撞的。2扩展的散列函数我们已研究过具有有限定义域的散列函数。现在研究如何把具有有限定义域的强无碰撞的散列函数扩展为具有无限定义域的

5、强无碰撞散列函数，这将使我们能签名任意长度的消息。假设h:(F2)m(F2)t是一个强无碰撞的散列函数，这里m≥t+1。我们的目的是想从h入手，构造无限定义域的散列函数h*:X(F2)t,其中首先考虑m≥t+2的情况：符号：

6、x

7、表示x的长度。（比特数目）x

8、

9、y表示比特串x和y的并。假设

10、x

11、=n＞m，（x为一段信息bit串）则先将x表为x=x1

12、

13、x2

14、

15、……

16、

17、xk这里,

18、x1

19、=

20、x2

21、=…=

22、xk-1

23、=m-t-1且

24、xk

25、=m-t-1-d，易见0≤d≤m-t-2而k=[n/(m-t-1)]（上整数部分）下面给出扩展的散列函数h*的生成算法：从h到h*算法，

26、注意

27、x

28、=n＞m，m≥t+2情形：x=x1

29、

30、x2

31、

32、……

33、

34、xk;

35、x1

36、=

37、x2

38、=…=

39、xk-1

40、=m-t-1;

41、xk

42、=m-t-1-d1°对i=1到k-1做yi=xi2°yk=xk

43、

44、od3°设yk+1是d的二进制表示，(右边补0,使∣yk+1∣=m-t-1)4°g1=h（ot+1

45、

46、y1）5°对i=1到k做gi+1=h(gi

47、

48、1

49、

50、yi+1)6°h*(x)=gk+1注：可以记y(x)=y1

51、

52、y2

53、

54、……

55、

56、yk

57、

58、yk+1,其中yk是由xk后面（右边）补上d个零来形成的，所以所有的块yi（1≤i≤k）的长度为m-t-1；在第3°步中也将在yk+1的左边补上

59、零，使得

60、yk+1

61、=m-t-1。为了散列x，首先构造y（x），然后以特定方式处理块（分组）y1，y2，…，yk+1。对于任意数对x,x,只要x≠x，易见y（x）≠y（x）。下面证明，在h是安全的前提下，h*也是安全的！定理，假设h:(F2)m

62、(F2)t是一个强无碰撞的散列函数，这里m≥t+2。那么按上述方式所构造的函数h*:是一个强无碰撞的散列函数。证明：（假设我们能找到x≠x满足h*(x)=h*(x)，那么如果能证明在多项式时间内可找到h的一个碰撞，这就与h假设为强无碰撞的事实矛盾，这样就证明了h*为强无碰撞