公鑰密碼學(二)

1、公鑰密碼學 （二）RSA安全性、DH密鑰交換RSA算法RSA算法密鑰產(chǎn)生選擇兩個大素數(shù)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基于大整數(shù)分解問題，其安全性完全依賴于大整數(shù)分解目前還未能從數(shù)學上證明，由c和e計算出m一定需要分解n如果新方法能使密碼分析者推算出d，則發(fā)明了一種分解大整數(shù)的新方法若n

2、= pq被因子分解，則RSA被攻破。因為，如果pq已知， (n) = (p - 1)(q - 1)就可以算出。已知e，則可以根據(jù)de = 1 mod (n)計算出d。對RSA的攻擊的困難程度不比大整數(shù)分解更難。目前還沒有找到比分解大整數(shù)更好的攻擊方法。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，固聯(lián)立可以解得，固聯(lián)立可以解得p p、q qp-1, q-1都應該有大的素因子要求要求e e在模在模k k下的階很大下的階很大RSA安全性使用時還需要注意：1、不同用戶不能共享模n，如果共享，則可能將消息m從密文中恢復出來設兩人加密密鑰為e1,e2,模數(shù)為

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、不同用戶選擇的素數(shù)不能相同如果兩個用戶選擇了相同的素數(shù)p，n1 = p*q1, n2 = p * q2可以根據(jù)歐幾里德算法求得(n1, n2) = p,從而分解n1,n2Diffie-Hellman密鑰交換算法離散對數(shù) 定義52 離散對數(shù)問題是指：給定一個素數(shù)p,Zp*的一個生成元g及一個元素bZp*,尋找整數(shù)x(0 xp-2)，使得gx=bmodp。 上述

5、定義可以推廣到任意有限循環(huán)群上。 定義53 推廣的離散對數(shù)問題（GDLP）是指：給定一個階為n的有限循環(huán)群G，G的一個生成元g及一個元素bG，尋找整數(shù)x(0 xn-1),使得gx=b。 離散對數(shù)問題也可推廣到更一般的情形：給定一個有限群G和元素g,b bG，尋找整數(shù)x,使得gx=b(如果這樣的整數(shù)存在)。這里沒有要求G是一個循環(huán)群，即使是，也不要求g是G的生成元。Diffie-Hellman密鑰交換算法DH密鑰交換算法，依賴于有限域上離散對數(shù)問題的難解性該算法可用于密鑰交換，但不能用于加解密、數(shù)字簽名假設實體A、B要產(chǎn)生私鑰,首先約定兩個大整數(shù)n和t(1tn)。這兩個整數(shù)不必保密，雙方可以通過不安全信道商定。這兩個數(shù)也可以被一組用戶共用。Diffie-Hellman密鑰分配算法如下：A選取一個大的隨機數(shù)a(1an)，將a保密，計算Xtamodn,并將X發(fā)送給B。B選取一個大的隨機數(shù)b(1bn)，將b保密，計算Y=tbmodn,并將Y發(fā)送給A。A計算k=Yamodn。B計算k=Xbmodn。Diffie-Hellman密鑰交換算法 顯而易見，k=k=tabmodn,除A和B之外，其他在信道上偷聽的人不能計算這個值，它們只知道n,t,X和Y。除非能計算離散對數(shù)以恢