1、第9章 公鑰密碼學與RSA第1頁，共26頁。公鑰密碼學是密碼學一次偉大的革命1976年，Diffie和Hellman 在“密碼學新方向”一文中提出使用兩個密鑰：公密鑰、私密鑰加解密的非對稱性利用數(shù)論的方法是對對稱密碼的重要補充第2頁，共26頁。公鑰密碼學解決的基本問題密鑰交換對稱密碼進行密鑰交換的要求：已經(jīng)共享一個密鑰利用密鑰分配中心數(shù)字簽名與傳統(tǒng)的簽名比較第3頁，共26頁。公鑰密碼體制重要特點僅根據(jù)密碼算法和加密密鑰來確定解密密鑰在計算上不可行兩個密鑰中的任何一個都可用來加密，另一個用來解密。六個組成部分：明文、密文；公鑰、私鑰；加密、解密算法第4頁，共26頁。公鑰密碼體制第5頁，共26頁。

2、公鑰密碼體制的加密功能A向B發(fā)消息X，B的公鑰為KUb,私鑰為KRb加密 Y = EKUb(X)解密 X = DKRb(Y) 第6頁，共26頁。公鑰密碼體制的加密第7頁，共26頁。公鑰密碼體制的認證A向B發(fā)送消息XA的公鑰為KUa，私鑰為KRa“加密”： Y = EKRa(X) （數(shù)字簽名）“解密”： X = DKUa(Y) 注意：不能保證消息的保密性第8頁，共26頁。公鑰密碼體制的認證第9頁，共26頁。具有保密與認證的公鑰體制第10頁，共26頁。 對稱密碼 公鑰密碼一般要求：1、加密解密用相同的密鑰2、收發(fā)雙方必須共享密鑰安全性要求：1、密鑰必須保密2、沒有密鑰，解密不可行3、知道算法和若干

3、密文不足以確定密鑰一般要求：1、加密解密算法相同，但使用不同的密鑰2、發(fā)送方擁有加密或解密密鑰，而接收方擁有另一個密鑰安全性要求：1、兩個密鑰之一必須保密2、無解密密鑰，解密不可行3、知道算法和其中一個密鑰以及若干密文不能確定另一個密鑰第11頁，共26頁。關于公鑰密碼的幾種誤解公鑰密碼比傳統(tǒng)密碼安全？公鑰密碼是通用方法，所以傳統(tǒng)密碼已經(jīng)過時？公鑰密碼實現(xiàn)密鑰分配非常簡單？第12頁，共26頁。RSA算法由MIT的 Rivest, Shamir & Adleman 在 1977 提出最著名的且被廣泛應用的公鑰加密體制 明文、密文是0到n-1之間的整數(shù)，通常n的大小為1024位或309位十進制數(shù)第1

4、3頁，共26頁。RSA算法描述加密： C=Me mod N, where 0MN解密： M=Cd mod N 公鑰為（e，N）， 私鑰為（d，N）必須滿足以下條件：Med = M mod N計算Me和Cd是比較容易的由e和n確定d是不可行的第14頁，共26頁。RSA 密鑰產生過程隨機選擇兩個大素數(shù) p, q 計算 N=p.q注意 (N)=(p-1)(q-1) 選擇 e使得1e(N),且gcd(e,(N)=1 解下列方程求出 d e.d=1 mod (N) 且 0dN 公布公鑰: KU=e,N 保存私鑰: KR=d,p,q 第15頁，共26頁。RSA 的使用發(fā)送方要加密明文M:獲得接收方的公鑰

5、KU=e,N 計算: C=Me mod N, where 0MN接收方解密密文C: 使用自己的私鑰 KR=d,N 計算: M=Cd mod N 注意：M必須比N小第16頁，共26頁。為什么RSA 可以加解密因為 Euler 定理的一個推論:Mk(n)1 = M mod NRSA 中:N=p.q(N)=(p-1)(q-1) 選擇 e & d 使得ed1 mod (N) 因此 存在k使得e.d=1+k.(N)因此Cd = (Me)d = M1+k.(N) = M mod N 第17頁，共26頁。RSA ExampleSelect primes: p=17 & q=11Compute n = pq

6、=1711=187Compute (n)=(p1)(q-1)=1610=160Select e : gcd(e,160)=1; choose e=7Determine d: de=1 mod 160 and d 160 Value is d=23 since 237=161= 10160+1Publish public key KU=7,187Keep secret private key KR=23,17,11第18頁，共26頁。RSA Example contsample RSA encryption/decryption is: given message M = 88 (nb. 881

7、87)encryption:C = 887 mod 187 = 11 decryption:M = 1123 mod 187 = 88 第19頁，共26頁。模冪運算模冪運算是RSA中的主要運算 (a mod n) (b mod n) mod n = (a b) mod n利用中間結果對n取模，實現(xiàn)高效算法第20頁，共26頁。Exponentiation第21頁，共26頁。RSA 密鑰生成必須做確定兩個大素數(shù)： p, q 選擇e或者d，并計算d或者e素數(shù)測試是重要的算法由e求d要使用到擴展Euclid算法第22頁，共26頁。RSA 的安全性三種攻擊 RSA的方法:強力窮舉密鑰數(shù)學攻擊 ：實質上是

8、對兩個素數(shù)乘積的分解時間攻擊：依賴解密算法的運行時間第23頁，共26頁。因子分解問題三種數(shù)學攻擊方法分解 N=p.q, 因此可計算出 (N)，從而確定d直接確定(N)，然后找到d直接確定d大家相信：由N確定(N)等價于因子分解第24頁，共26頁。Timing Attacksdeveloped in mid-1990sexploit timing variations in operationseg. multiplying by small vs large number or IFs varying which instructions executedinfer operand size based on time taken RSA exploits time taken in exponentiationcountermeasuresuse constant exponentiation timeadd random delaysblind values used i