第13讲--公钥密码3(EIGAMAL)(密码学)

1、第五章EIGamal体制与椭圆曲线,离散对数,求模下的整数幂根据欧拉定理，若gcd(a,n)=1,则af(n)1modn。考虑一般am1modn,如果a,n互素，至少有一个整数m满足这一方程。称满足这一方程的最小正整数m为模n下a的阶。例：a=7,n=19.717mod19,7211mod19,731mod19,所以7模19的阶为3。从幂次为4开始出现循环，循环周期与元素的阶相同,离散对数,定理：设a的阶为m，则ak1modn的充分必要条件是k是m的倍数。推论：a的阶整除j(n)。本原根（元）：a的阶m等于j(n)，a为n的本原根。如果a是n的本原根，a1,a2,.,aj(n)在模n下互不相同

2、且与n互素。本原根不唯一。并非所有元素都有本原根，仅有以下形式的整数才有本原根：2，4，pa,2pa,p是奇素数,离散对数,指标y=ax(a0,a1)的逆函数称为以a为底的对数，记为x=logay设p为素数，a是p的本原根，则a0,a1,.,ap-1产生1到p-1中所有值，且每个值只出现一次。对任一b1,p-1，都存在唯一的i(1ip)，使baimodp。i称为模p下以a为底b的指标，记为i=inda,p(b),离散对数,指标的性质inda,p(1)=0inda,p(a)=1inda,p(xy)=inda,p(x)+inda,p(y)modj(p)inda,p(yr)=rinda,p(y)mo

3、dj(p)后两个性质基于下列结论若azaqmodp,a和p互素，则zqmodj(p),离散对数,设p是素数，a是p的本原根。对b1,p-1,有唯一的i1,p-1,使baimodp。称i为模p下以a为底b的离散对数，记为ilogab(modp)=inda,p(b)已知a,p,i,求b比较容易，已知a,b,p,求i非常困难,EIGamal公钥密码体制,设计过程:(1)选取大素数p,再选取的一个本原元a,并将p和a公开.(2)随机选取整数,并计算出并将作为公开的加密密钥,将d作为保密的解密密钥.,加解密变换,加密变换:,秘密选择一个整数，则密文为其中解密变换:对任意密文明文为,解密正确性证明,因为所

4、以因此，解密变换能正确地从密文恢复出相应的明文。,特点,在EIGamal公钥密码体制中，密文依赖于明文m和秘密选取的随机整数k，因此，明文空间中的一个明文对应密文空间中的许多不同的密文。,实例,P=2597,取a2，秘密密钥为765，可以计算出公开密钥为y2765mod2597949。取明文M1299，随机数k853，则C12853mod2597435，C21299949853mod25972396所以密文为:（C1，C2）（435，2396）解密时计算:M2396(435765)-1mod25971299,特点,(1)密文长度扩展1倍;(2)只利用了有限域的乘法群的性质,即只使用了乘法运算和

5、求乘法逆的运算,安全性分析,因为该算法是基于有限域上的离散对数问题的，所以p的选取必须足够的大，为150位以上的十进制数，且p1有大素因子为了加密和签名的安全，k必须是一次性的,设计思想,(1)利用Diffie-Hellman密钥交换协议生成双方加密用的密钥.此时不同之处在于已将作为公开密钥公布,不需每次发送.(2)采取了一次一密的加密思想.将作为双方交换的密钥,利用它对明文进行加解密.,问题,为什么要求?答案:因为的周期为p-1,即备注:(1)参数可以全网公用,也可一人一套;(2)加密不同的明文分组时选用独立的随机数,但秘密的解密密钥需和其版本号一起长期不变.,实现方法,(1)大素数的选择与构造将大素数p选为安全素数,即p=2q+1且q为素数.实验表明,平均100个随机数中可选出1个素数,平均100素数中可选出1个安全素数.,(2)安全素数条件下本原元的判断方法,由Fermat定理知,即因而如果则有w整除p-1=2q,因而由q是素数知,w只能是2或q.此时本原元等价于且,安全素数条件下本原元的构造方法,在(p=2q+1)中随机选择一个,若且,则判定是