第9章鑰密碼學(xué)與RSA

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

2、ub,私鑰為krbn加密 y = ekub(x)n解密 x = dkrb(y) 公鑰密碼體制的加密公鑰密碼體制的認(rèn)證na向b發(fā)送消息xna的公鑰為kua，私鑰為kran“加密”： y = ekra(x) （數(shù)字簽名）n“解密”： x = dkua(y) n注意：不能保證消息的保密性公鑰密碼體制的認(rèn)證具有保密與認(rèn)證的公鑰體制 對(duì)稱密碼 公鑰密碼一般要求：一般要求：1、加密解密用相同的密鑰2、收發(fā)雙方必須共享密鑰安全性要求：安全性要求：1、密鑰必須保密2、沒有密鑰，解密不可行3、知道算法和若干密文不足以確定密鑰一般要求：一般要求：1、加密解密算法相同，但使用不同的密鑰2、發(fā)送方擁有加密或解密密鑰，

3、而接收方擁有另一個(gè)密鑰安全性要求：安全性要求：1、兩個(gè)密鑰之一必須保密2、無解密密鑰，解密不可行3、知道算法和其中一個(gè)密鑰以及若干密文不能確定另一個(gè)密鑰關(guān)于公鑰密碼的幾種誤解n公鑰密碼比傳統(tǒng)密碼安全？n公鑰密碼是通用方法，所以傳統(tǒng)密碼已經(jīng)過時(shí)？n公鑰密碼實(shí)現(xiàn)密鑰分配非常簡(jiǎn)單？rsa算法n由mit的 rivest, shamir & adleman 在 1977 提出n最著名的且被廣泛應(yīng)用的公鑰加密體制 n明文、密文是0到n-1之間的整數(shù)，通常n的大小為1024位或309位十進(jìn)制數(shù)rsa算法描述n加密： c=me mod n, where 0mnn解密： m=cd mod n n公鑰為（

4、e，n）， 私鑰為（d，n）n必須滿足以下條件：nmed = m mod nn計(jì)算me和cd是比較容易的n由e和n確定d是不可行的rsa 密鑰產(chǎn)生過程n隨機(jī)選擇兩個(gè)大素?cái)?shù) p, q n計(jì)算 n=p.qn注意 (n)=(p-1)(q-1) n選擇 e使得1e(n),且gcd(e,(n)=1 n解下列方程求出 d ne.d=1 mod (n) 且 0dn n公布公鑰: ku=e,n n保存私鑰: kr=d,p,q rsa 的使用n發(fā)送方要加密明文m:n獲得接收方的公鑰 ku=e,n n計(jì)算: c=me mod n, where 0mnn接收方解密密文c:n 使用自己的私鑰 kr=d,n n計(jì)算:

5、m=cd mod n n注意：m必須比n小為什么rsa 可以加解密n因?yàn)?euler 定理的一個(gè)推論:nmk(n)1 = m mod nnrsa 中:nn=p.qn(n)=(p-1)(q-1) n選擇 e & d 使得ed1 mod (n) n因此 存在k使得e.d=1+k.(n)n因此cd = (me)d = m1+k.(n) = m mod n rsa example1.select primes: p=17 & q=112.compute n = pq =1711=1873.compute (n)=(p1)(q-1)=1610=1604.select e : gcd(e,

6、160)=1; choose e=75.determine d: de=1 mod 160 and d 160 value is d=23 since 237=161= 10160+16.publish public key ku=7,1877.keep secret private key kr=23,17,11rsa example contnsample rsa encryption/decryption is: ngiven message m = 88 (nb. 88187)nencryption:c = 887 mod 187 = 11 ndecryption:m = 1123 m

7、od 187 = 88 模冪運(yùn)算n模冪運(yùn)算是rsa中的主要運(yùn)算n (a mod n) (b mod n) mod n = (a b) mod nn利用中間結(jié)果對(duì)n取模，實(shí)現(xiàn)高效算法exponentiationrsa 密鑰生成n必須做n確定兩個(gè)大素?cái)?shù)： p, q n選擇e或者d，并計(jì)算d或者en素?cái)?shù)測(cè)試是重要的算法n由e求d要使用到擴(kuò)展euclid算法rsa 的安全性n三種攻擊 rsa的方法:n強(qiáng)力窮舉密鑰n數(shù)學(xué)攻擊 ：實(shí)質(zhì)上是對(duì)兩個(gè)素?cái)?shù)乘積的分解n時(shí)間攻擊：依賴解密算法的運(yùn)行時(shí)間因子分解問題n三種數(shù)學(xué)攻擊方法n分解 n=p.q, 因此可計(jì)算出 (n)，從而確定dn直接確定(n)，然后找到dn直

8、接確定dn大家相信：由n確定(n)等價(jià)于因子分解timing attacksndeveloped in mid-1990snexploit timing variations in operationsneg. multiplying by small vs large number nor ifs varying which instructions executedninfer operand size based on time taken nrsa exploits time taken in exponentiationncountermeasuresnuse constant exponentiation timenadd random delaysnblind v