公钥密码学(二)

1、公钥密码学 （二）RSA安全性、DH密钥交换RSA算法RSA算法密钥产生选择两个大素数p、q计算n = p * q， (n) = (p-1)*(q-1)选择e，满足1 e (n)，gcd(n)、e) = 1计算d，满足de = 1 mod (n)，即d为e在模(n)下的乘法逆元e,n为公钥，d,p,q, (n)为私钥加密：设消息m n, c = m e mod n解密：m = c d mod nRSA安全性RSA安全性RSA基于大整数分解问题，其安全性完全依赖于大整数分解目前还未能从数学上证明，由c和e计算出m一定需要分解n如果新方法能使密码分析者推算出d，则发明了一种分解大整数的新方法若n

2、= pq被因子分解，则RSA被攻破。因为，如果pq已知， (n) = (p - 1)(q - 1)就可以算出。已知e，则可以根据de = 1 mod (n)计算出d。对RSA的攻击的困难程度不比大整数分解更难。目前还没有找到比分解大整数更好的攻击方法。RSA安全性若已知n，可以通过某种方法求得(n) ，则pq可以求得，因为：(n) = (p-1)(q-1) = pq (p+q) + 1又(p-q)2 = (p+q)2 -4pq所以p+q = n - (n) + 1p-q = (p+q)2 4n)1/2因此，pq还需要满足其他安全性条件RSA安全性p-q要求很大设设p-q = k, p-q =

3、k, 则则q = p+kq = p+k(p + q)2 (p - q)2 = 4pq = 4n(p + q)2 (p - q)2 = 4pq = 4n(p + q)2 = 4n + k2(p + q)2 = 4n + k2(p + q) = (4n + k2)1/2(p + q) = (4n + k2)1/2又又p q = kp q = k，固联立可以解得，固联立可以解得p p、q qp-1, q-1都应该有大的素因子要求要求e e在模在模k k下的阶很大下的阶很大RSA安全性使用时还需要注意：1、不同用户不能共享模n，如果共享，则可能将消息m从密文中恢复出来设两人加密密钥为e1,e2,模数为

4、n, 且满足(e1, e2) = 1; c1 = me1, c2 = m e2,因为存在s,r,使得r * e1 +s * e2 = 1计算c1r * c2 s = m(e1*r) *m(e2*r) = m(r*e1 + s*e2)=m2、不同用户选择的素数不能相同如果两个用户选择了相同的素数p，n1 = p*q1, n2 = p * q2可以根据欧几里德算法求得(n1, n2) = p,从而分解n1,n2Diffie-Hellman密钥交换算法离散对数 定义52 离散对数问题是指：给定一个素数p,Zp*的一个生成元g及一个元素bZp*,寻找整数x(0 xp-2)，使得gx=bmodp。 上述

5、定义可以推广到任意有限循环群上。 定义53 推广的离散对数问题（GDLP）是指：给定一个阶为n的有限循环群G，G的一个生成元g及一个元素bG，寻找整数x(0 xn-1),使得gx=b。 离散对数问题也可推广到更一般的情形：给定一个有限群G和元素g,b bG，寻找整数x,使得gx=b(如果这样的整数存在)。这里没有要求G是一个循环群，即使是，也不要求g是G的生成元。Diffie-Hellman密钥交换算法DH密钥交换算法，依赖于有限域上离散对数问题的难解性该算法可用于密钥交换，但不能用于加解密、数字签名假设实体A、B要产生私钥,首先约定两个大整数n和t(1tn)。这两个整数不必保密，双方可以通过不安全信道商定。这两个数也可以被一组用户共用。Diffie-Hellman密钥分配算法如下：A选取一个大的随机数a(1an)，将a保密，计算Xtamodn,并将X发送给B。B选取一个大的随机数b(1bn)，将b保密，计算Y=tbmodn,并将Y发送给A。A计算k=Yamodn。B计算k=Xbmodn。Diffie-Hellman密钥交换算法 显而易见，k=k=tabmodn,除A和B之外，其他在信道上偷听的人不能计算这个值，它们只知道n,t,X和Y。除非能计算离散对数以恢