公鑰密碼學(xué)與RSA課件

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

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

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

4、3頁，共26頁。RSA算法描述加密： C=Me mod N, where 0MN解密： M=Cd mod N 公鑰為（e，N）， 私鑰為（d，N）必須滿足以下條件：Med = M mod N計(jì)算Me和Cd是比較容易的由e和n確定d是不可行的第14頁，共26頁。RSA 密鑰產(chǎn)生過程隨機(jī)選擇兩個(gè)大素?cái)?shù) p, q 計(jì)算 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 計(jì)算: C=Me mod N, where 0MN接收方解密密文C: 使用自己的私鑰 KR=d,N 計(jì)算: M=Cd mod N 注意：M必須比N小第16頁，共26頁。為什么RSA 可以加解密因?yàn)?Euler 定理的一個(gè)推論: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頁。模冪運(yùn)算模冪運(yùn)算是RSA中的主要運(yùn)算 (a mod n) (b mod n) mod n = (a b) mod n利用中間結(jié)果對(duì)n取模，實(shí)現(xiàn)高效算法第20頁，共26頁。Exponentiation第21頁，共26頁。RSA 密鑰生成必須做確定兩個(gè)大素?cái)?shù)： p, q 選擇e或者d，并計(jì)算d或者e素?cái)?shù)測(cè)試是重要的算法由e求d要使用到擴(kuò)展Euclid算法第22頁，共26頁。RSA 的安全性三種攻擊 RSA的方法:強(qiáng)力窮舉密鑰數(shù)學(xué)攻擊 ：實(shí)質(zhì)上是

8、對(duì)兩個(gè)素?cái)?shù)乘積的分解時(shí)間攻擊：依賴解密算法的運(yùn)行時(shí)間第23頁，共26頁。因子分解問題三種數(shù)學(xué)攻擊方法分解 N=p.q, 因此可計(jì)算出 (N)，從而確定d直接確定(N)，然后找到d直接確定d大家相信：由N確定(N)等價(jià)于因子分解第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