公鑰加密算法

1、第十講公鑰加密算法 (續(xù)) 公鑰密碼(續(xù)) RSA ElGamal algorithms 1. 公鑰加密公鑰加密 公鑰加密算法: 用于加密任何消息 常能用于簽名和密鑰交換 eg. RSA, ElGamal 基于不同有限域的指數(shù)運算 (galois 整數(shù)域、 elliptic curves etc) 其它問題的公鑰體制 (Error Correcting Codes) 大多數(shù)都被攻破 2. RSA (Rivest, Shamir, Adleman) 使用最廣泛的公鑰加密算法 Rivest, Shamir & Adleman (RSA) in 1977 R L Rivest, A Sham

2、ir, L Adleman, On Digital Signatures and Public Key Cryptosystems, Communications of the ACM, vol 21 no 2, pp120-126, Feb 1978 3. RSA Setup 每個用戶生成自己的公鑰私鑰對: 選擇兩個隨機大素數(shù) (100 digit), p, q 計算模數(shù) N=p.q 選擇一個隨機加密密鑰匙 e : eN, gcd(e,(N)=1 解下列同余方程,求解密密鑰 d: e.d=1 mod (N) and 0=d=N 公開加密密鑰: Kr=er,Nr 保存其解密似鑰: K-1r=d

3、,p,q 4。RSA 參數(shù)選擇 需要選擇足夠大的素數(shù) p, q 通常選擇小的加密指數(shù)e,且與(N) 互素 e 對所有用戶可以是相同的 最初建議使用e=3 現(xiàn)在3太小 常使用 e=216-1 = 65535 解密指數(shù)比較大5. RSA Usage 要加密消息 M， 發(fā)送者要得到接收者的公鑰Kr=er,Nr 計算: C=Mer mod Nr, where 0=MN 為解密 C， 接收者使用私鑰 K-1r=d,p,q 計算: M=Cd mod Nr 6. RSA理論理論 RSA 基于Fermats Theorem: if N = pq where p, q are primes, then:X(N)

4、 = 1 mod N for all x not divisible by p or q, ie gcd(x,(N)=1 where (N)=(p-1)(q-1) 但在 RSA 中，e & d 是特殊選擇的 ie e.d=1 mod (N) 或e.d=1+R(N) hence have:M = Cd = Me.d = M1+R(N) = M1.(M(N)R = M1.(1)R = M1 mod N 8。RSA舉例例子：例子：1. 選素數(shù)選素數(shù)p=47和和q71，得，得n=3337, (n)=46703220；2. 選擇選擇e=79，求得私鑰，求得私鑰d=e -1 1019(mod 32

5、20）。）。3. 公開公開n=3337和和e=79.4. 現(xiàn)要發(fā)送明文現(xiàn)要發(fā)送明文688，計算：，計算：68879(mod 3337)=15705.收到密文收到密文1570后，用私鑰后，用私鑰d1019進行解密：進行解密： 15701019（mod 3337)=6889。RSA 安全性安全性 RSA 安全性基于計算 (N)的困難性 要求分解模N 10. RSA的實現(xiàn)問題的實現(xiàn)問題 需要計算模 300 digits (or 1024+ bits) 的乘法 計算機不能直接處理這么大的數(shù) （計算速度很慢） 需要考慮其它技術(shù)，加速RSA的實現(xiàn)11. RSA 的快速實現(xiàn)的快速實現(xiàn) 加密很快，指數(shù)小 解密

6、比較慢，指數(shù)較大 利用中國剩余定理CRT， CRT 對RSA解密算法生成兩個解密方程 （利用M = Cd mod R ） 即: M1 = M mod p = (C mod p)d mod (p-1) M2 = M mod q = (C mod q)d mod (q-1) 解方程 M = M1 mod p M = M2 mod q 具有唯一解（利用CRT ）： :M = (M2 +q - M1)u mod q p + M1 其中 p.u mod q = 1 12。El Gamal 公鑰加密方案公鑰加密方案 Diffie-Hellman key distribution scheme 的變形 能夠

7、用于安全交換密鑰 published in 1985 by ElGamal: T. ElGamal, A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, IEEE Trans. Information Theory, vol IT-31(4), pp469-472, July 1985. 安全性是基于離散對數(shù) 缺點：增加了消息長度（2倍） 13 密鑰建立 密鑰生成：密鑰生成： 選取一個大素數(shù)p及本原元a mod p 接收者 Bob有一個密秘鑰 xB 計算 yB = axB mod p 14

8、. El Gamal 加密加密 為加密 M 發(fā)送者選擇隨機數(shù)k, 0=k=p-1 計算消息密鑰 K : K = yBk mod p 計算密文對: C = C1,C2 C1 = ak mod p C2 = K.M mod p 發(fā)送到接收者 k 需要永久保密 15. El Gamal 解密解密 首先計算 message key K K = C1xB mod p = ak.xB mod p 計算明文: M = C2.K-1 mod p 16. El Gamal Example 選擇 p=97 及本原根 a=5 recipient Bob 選擇 秘密鑰xB=58 & 計算并發(fā)布公鑰yB=558

9、=44 mod 97 Alice 要加密 M=3 to Bob 首先得到 Bob的公開密鑰 yB=44 選擇隨機 k=36 計算:K=4436=75 mod 97 計算密文對: C1 = 536 = 50 mod 97 C2 = 75.3 mod 97 = 31 mod 97 發(fā)送 50,31 to Bob Bob 恢復(fù) message key K=5058=75 mod 97 Bob 計算 K-1 = 22 mod 97 Bob 恢復(fù)明文 M = 31.22 = 3 mod 97 17。公鑰密碼現(xiàn)狀 已知的安全算法是有限域上指數(shù)運算 素數(shù)域GF(p)上的整數(shù)運算 多項式運算 GF(2n) 橢圓曲線上的運算(elliptic curves) (harder to compute so use smaller sizes) 基于其它困難問題的體制18. 公鑰密碼方案的實際應(yīng)用公鑰密碼方案的實際應(yīng)用 實現(xiàn)速度 通常用于交換對稱算法的加密密鑰 數(shù)字簽名算法（下節(jié)內(nèi)容）19 小結(jié) RSA 算法 ElGamal 算法 實現(xiàn)問題Exercises Illustrate the operation of RSA, given the following parameters: System modulus n=119 (7x17) encryption exp e=11 Determin