ElGamal公钥密码体制及安全性

1、第五章 公钥密码ElGamal体制,5.4.1 ElGamal密码体制 5.4.2. ElGamal公钥密码体制的安全性,5.4 ELGamel公钥密码,5.4.1 ElGamal公钥密码体制 ElGamal公钥密码体制是由T. ElGamal于1985年提 出。它至今仍然是一个安全性能良好的公钥密码体制。 ElGamal公钥密码体制描述如下： (1)选择大素数 ,zp* 是一个本原元.p和公开 (2)随机选取整数d，1dp2，计算 =d mod p. 是公开的加密密钥，d 是保密的解秘密钥。 (3) 明文空间为zp* ，密文空间为 zp*zp*. (4) 加密变换：对任意明文mzp* ，秘密

2、随机选取整数 k, 1kp2密文为 c = (c1,c2),其中 c1 =kmod p, c2 = mk mod p. (5) 解密变换：对任意密文 c = (c1,c2) zp* zp*，明文为 m = c2(c1d)1 mod p. 现在我们来证明解密变换能正确的从密文恢复相应的明文。因为 c1 =kmod p, c2 = mk mod p, =d mod p,所以 c2(c1d)1mk(dk ) 1 (mod p) mdk (dk ) 1(mod p) zp* m(mod p). 因此，解密变换能正确的从密文恢复相应的明文。,5.4.2. ElGamal公钥密码体制的安全性,5.4.3

3、有限域上的离散对数的计算方法 1. Shanks算法 设p 是一个素数，是zp* 的生成元，zp* . 令m = p1.求 log的算法描述如下： (1)计算mj mod p, 0jm1. (2)将m个有序对(j,mj mod p)按第二个坐标排序,得到表L1. (3)计算imod p, 0im1. (4)将m个有序对 (j, i mod p)按第二个坐标排序,得到表L2. (5)寻找(j,y)L1和(j,y)L2，它们的第二各坐标相同. (6)计算loga = mj + i mod(p1).,在Shanks算法中，如果(j,y)L1, (j,y)L2，则 mj mod p = y = i m

4、od p. 因此 mj+i = , log = mj + i mod(p1). 反过来，因为 m = p1，0log p2,所以存在j 和 i使得 log = mj + I, 其中0j, im1. 因此，在算法的第(5)步中，一定可以在表L1和 L2中找到第二个坐标相同的一对有序对。,由上面的讨论知， Shanks算法能够成功计算log. 例5.6 设p = 809. 计算log3 525. 因为= 3， = 525,m = p1= 29, 所以, 29 mod 809 = 99. 计算有序对(j, 99j mod 809)，.我们得到下表： (0,1) (1,99) (2,93) (3, 3

5、08) (4,559) (5,329) (6,221) (7,664) (8,207) (9,268) (10,644) (11,654) (12,26) (13,147) (14,800) (15,727) (16,781) (17,464) (18,632) (19,275) (20,528) (21,496) (22,564) (23,15) (24,676) (25,586) (26,575) (27,295) (28, 81),将上表按第二个坐标排序就得到表L1 . 计算有序对(i, 525 (3j ) i mod 809)，0j28.我们得到下表： (0,525) (1,175)

6、(2,328) (3, 379) (4,396) (5,132) (6,44) (7,554) (8,724) (9,551) (10,440) (11,686) (12,768) (13,256) (14,355) (15,388) (16,399) (17,133) (18,314) (19,644) (20,754) (21,521) (22,713) (23,777) (24,259) (25,356) (26,658) (27,489) (28, 163),将上表按第二个坐标排序就得到表L2. 查找表L1和 L2，我们得到(10,644) L1和(19,644) L2，他们的第二个坐

7、标相同. 因此， log3 525 = 29 10 + 19 = 309 容易验证，3309 525(mod 809). 2. 指标计算法 p是一个素数，是zp* 的生成元，zp*. 设= p1, p2 , pB 是一个“小”素数的集合。指标计算法的基本思想是利用logpi , 1iB.来计算log.,现在来考虑如何计算log. 随机选取s，1sp2,使 的素因子都在中，则我们有 即 log + s c1 logp1 + c2 logp1 + cBlogpB (mod (p1). 在上式中，除了 log未知外，其它都是已知的. 因此，我们可求出log.,例5.7 设p = 10007, = 5

8、.设 = 2,3,5,7. 显然log55 = 1. 只需计算log52, log53以及 log57. 选取，计算x = 4063, 5136, 9865, 计算 54063 mod 10007 = 42 = 237, 5 5136mod 10007 = 54 = 233, 59865 mod 10007 = 189 = 337. 我们有 log52 + log53 + log57 4063 (mod 10006),log52 + 3log53 5136 (mod 10006), 3log53 + log57 9865 (mod 10006). 由此可求得 log52 = 6578, log

9、53 = 6190, log57 = 1301. 设 = 9451. 我们来计算log59451. 选取s = 7736, 计算 945157736 mod 10007 = 8400 = 243527. 我们得到 log5 9451= 4 log52 + log53 + 2log 55 + log57 s mod 10006 = 4 6578 + 6190 + 21 + 1301 7736 mod 10006 = 6057. 易验证, 56057 mod 10007 = 9451.,3. Pohlig-Hellman算法 设p是一个素数，是zp* 的生成元，zp* . 下面我们来介绍求 log

10、 的算法。Pohlig-Hellman算法适应于p1的素因子都是小素数的情况。 设 其中是素数，1 ik. 我们的目的是计算log ，即寻找 ，0 p2, 使得 如能求得 i= 1,2, ,k, 则由中国剩余定理，可求得 mod(p1)，即求得log 。,首先计算 , 其中i= 1,2, ,k, s = 0, 1,2, qi 1. 将这些 排成一个表L. 下面利用表L求 , i= 1,2, ,k. 设 其中0ajqi , 0jei1. 因为 并且由Fermat定理知,所以 . 因此在表L中一定存在 ，0s0qi 1, 使得 . 于是，通过计算 ，然后与表L 中的元 s = 0,1,2, qi

11、1, 进行比较，可得 .进一步我们来确定 .令 .,在表L中一定存在 ，0s1qi 1，使得 于是，通过计算 ，然后与表L中的元素(s=0,1,2, qi 1)进行比较，可得 . 一般地，假设我们已求得 ,1jei 1.,令 在表L中一定存在 ，0sjqi 1，使得,于是，通过计算 , 然后与表L中的元素 (s = 0,1,2, qi 1)进行比较，可得j = sj。由以上讨论，我们可确定 ，从而求得 ，由中国剩余定理可求得 ，即求得 . 根据目前的计算能力，只有当p-1 的素因子是小素数时，才能有效分解 p-1求得 。因此，Pohlig-Hellman 算法适用于p-1 的素因子是小素数的情

12、况。 例5.8 设p = 29, 则 p-1= 28 = 227.设= 2, = 18.求 。令 . 下面我们首先计算,2,0 =0(p-1)/2 mod 29 = 20 mod 29 = 1, 2,1 =1(p-1)/2mod 29 = 228/2 mod 29 = 28. 因为 mod 29 = 1828/2 mod 29 = 28 =2,1 , 所以 = 1.令,1 = -1 = 182-1= 9. 因为 1(p-1)/2 mod 29 = 9 28/4 mod 29 = 28 =2,1 , 所以 下面来计算 。首先利用7，s= a s（p-1）/7mod 29 0s6 求得 7，0 =

13、1，7，1 =16，7，2 =24，7，3 =7 ，7，4 =25，7，5 =23，7，6 =20。 因为,，(p-1)/7 mod 29 = 1828/7 mod 29 = 25 =7，4 所以 。因此, 最后，由同余方程组 根据中国剩余定 理可求得 。因此求得Z29中Log2 18 =11,55椭圆曲线上的Menezes-Vanstone 公钥密码 551有限域上的椭圆曲线 椭圆曲线是指由方程y2 + a1 xy+ a3 y= x3 + a2 x2 + a4x+ a6 所确定的平面曲线。也可坐标变换后化为：y2 = x3 + a x + b 定义5.10 设p3 是一个素数。有限域Zp上的

14、椭圆曲线y2 = x3 + a x + b 是由一个无群远点和满足同余方程y2 x3 + a x + b(modp) 的点(x,y) Zp Zp组成的集合，其中，a,bZp, 4 a3 +27 b20(modp) 椭圆曲线E上定义加法如下：对任意P=( x1 ,y1 ) E,Q=( x2 ,y2,) E,P+Q= , 如果x1 =x2, y1 = y2, P+Q= ( x1 ,y1 ) 否则 其中, x3 = 2 x1 x2, . y3 = (x1 x3) y1 (y2 y1) /(x2 x1) 如果 P Q = (3 x12 +a)/2 y1 如果 P= Q 另外，对任意P=( x1 ,y1

15、 ) E, P+=+P=P,设P 和Q是椭圆曲线E上的任意两点，L 是连接P 和Q的直线。如果P= Q ，则L为P点的切线。设 L与椭圆曲线E相交于另一点R。过R点做y轴的平行线L，即L 是过点R 和的直线。L 与椭圆曲线E相交于另一点，这一点就是P+Q. 定理5.15(Hasse定理)设 E是有限域Zp上的椭圆曲线，则 例59设p=11 ，E是由y2 x3 + x +6(mod11) 所确定的有限域Z11上的椭圆曲线。 要确定E的点，可以对每个x Z11，先计算z x3 + x +6(mod11) ，然后再求同余方程y2 z(mod11) 的解来实现。,要确定z 是一个模P 的平方剩余，可用

16、Euler 准则来实现，即如果p 是一个奇素数，则z是模p 的平方剩余当切仅当z(p-1)/2 = 1 mod p 。当p=3(mod4)时，如果z 是模p 的平方剩余，则+ z(p-1)/4 modp = 就是z 的两个模p 平方根，这是因为(+ z(p-1)/4 )2z(p-1)/2(modp) zz(p-1)/2(modp) z(modp) 由上面的讨论，可却顶E中的 所有点，结果如表 5.1 所示。设= (2,7). 我们来计算2=+.先计算 = (322 + 1)(27)-1 mod 11 = 23 -1 mod 11 = 24 mod 11 = 8.,于是, x3 = 82 - 2

17、 - 2 mod 11 = 5, y3= 8(2-5)-7 mod 11 =2. 因此，2= (5,2). 再来计算3=2+= (5,2) + (2,7).首先计算 =(7-2)(2-5) -1 mod 11 = 58-1 mod 11 = 57 mod 11 = 2.,于是, x3 = 22 5 - 2 mod 11= 8, y3=2(5-8)-2mod11=3 因此, 3=(8,3).类似地，可计算出n，n 1, 如下所示： =(2,7) 2=(5,2) 3=(8,3) 4=(10,2) 5=(3,6) 6=(7,9) 7=(7,2) 8=(3,6) 9=(10,9) 10=(8,8) 1

18、1=(5,9) 12=(2,4) 13= 因此，=(2,7)是E 的生成元，E 是一个循环群。,定义5.11 设E 是有限域Zp上的椭圆曲线，PE ,P的阶是满足nP=P+P+P+P= 的最小正整数n，记为ord()，其中是无穷远点。 定义5.12 设 P3是一个素数，E 是有限域Zp上的椭圆曲线。设G 是的一个循环子群，是G的一个生成元G， 已知 和 ，求满足 n = 的唯一整数n，0nord()1, 称为椭圆曲线上的离散对数问题。 5.5.2 Menezes-Vanstone公钥密码体制 Menezes-Vanstone公钥密码体制描述如下: （1）设p3 是一个大素数，E为有限域Zp上的

19、椭圆曲线, E是椭圆曲线上的一个点，且的阶足够大，,使得在由 生成的循环子群上的离散对数问题是难解的。p和E以及 都公开。 （2）随机选取整数 d， 计算1 dord()1, =d。是公开的加密密钥，d 是保密的解密密钥。 （3）明文空间为Zp* Zp*，密文空间EZp* Zp*， （4）加密变换：对任意明文x=( x1 ,y1 )Zp* Zp*，秘密随机选取一整数k，1 kord()1密文为 y=( y0 ,y1, ,y2) EZp* Zp* 其中 y0=k,( c1 ,c2 )=k， y1= c1x1 modp，y2=c2x2modp,（5）解密变换：对任意密文y=( y0 ,y1, ,y2) EZp* Zp*，明文为x=( y1c1-1 modp , y2c2-1modp) 其中( c1 ,c2)=d y0 现说明解密变换能正确从密文恢复相应的明文。 因为( c1 ,c2)=k y0=k, =d, 所以( c1 ,c2