rsa加密算法詳解與舉例說(shuō)明

　　RSA公鑰加密算法是1977年由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）一起提出的。1987年7月首次在美國(guó)公布，當(dāng)時(shí)他們?nèi)硕荚诼槭±砉W(xué)院工作實(shí)習(xí)。RSA就是他們?nèi)诵帐祥_(kāi)頭字母拼在一起組成的。RSA是目前最有影響力和最常用的公鑰加密算法，它能夠抵抗到目前為止已知的絕大多數(shù)密碼攻擊，已被ISO推薦為公鑰數(shù)據(jù)加密標(biāo)準(zhǔn)。

　　今天只有短的RSA鑰匙才可能被強(qiáng)力方式解破。到2008年為止，世界上還沒(méi)有任何可靠的攻擊RSA算法的方式。只要其鑰匙的長(zhǎng)度足夠長(zhǎng)，用RSA加密的信息實(shí)際上是不能被解破的。但在分布式計(jì)算和量子計(jì)算機(jī)理論日趨成熟的今天，RSA加密安全性受到了挑戰(zhàn)和質(zhì)疑。RSA算法基于一個(gè)十分簡(jiǎn)單的數(shù)論事實(shí)：將兩個(gè)大質(zhì)數(shù)相乘十分容易，但是想要對(duì)其乘積進(jìn)行因式分解卻極其困難，因此可以將乘積公開(kāi)作為加密密鑰。

　　安全性

　　RSA的安全性依賴(lài)于大數(shù)分解，但是否等同于大數(shù)分解一直未能得到理論上的證明，因?yàn)闆](méi)有證明破解RSA就一定需要作大數(shù)分解。假設(shè)存在一種無(wú)須分解大數(shù)的算法，那它肯定可以修改成為大數(shù)分解算法。 RSA 的一些變種算法已被證明等價(jià)于大數(shù)分解。不管怎樣，分解n是最顯然的攻擊方法。人們已能分解多個(gè)十進(jìn)制位的大素?cái)?shù)。因此，模數(shù)n必須選大一些，因具體適用情況而定。

　　實(shí)現(xiàn)細(xì)節(jié)

　　密鑰生成

　　首先要使用概率算法來(lái)驗(yàn)證隨機(jī)產(chǎn)生的大的整數(shù)是否質(zhì)數(shù)，這樣的算法比較快而且可以消除掉大多數(shù)非質(zhì)數(shù)。假如有一個(gè)數(shù)通過(guò)了這個(gè)測(cè)試的話(huà)，那么要使用一個(gè)精確的測(cè)試來(lái)保證它的確是一個(gè)質(zhì)數(shù)。

　　除此之外這樣找到的p和q還要滿(mǎn)足一定的要求，首先它們不能太靠近，此外p-1或q-1的因子不能太小，否則的話(huà)N也可以被很快地分解。

　　此外尋找質(zhì)數(shù)的算法不能給攻擊者任何信息，這些質(zhì)數(shù)是怎樣找到的，尤其產(chǎn)生隨機(jī)數(shù)的軟件必須非常好。要求是隨機(jī)和不可預(yù)測(cè)。這兩個(gè)要求并不相同。一個(gè)隨機(jī)過(guò)程可能可以產(chǎn)生一個(gè)不相關(guān)的數(shù)的系列，但假如有人能夠預(yù)測(cè)出（或部分地預(yù)測(cè)出）這個(gè)系列的話(huà)，那么它就已經(jīng)不可靠了。比如有一些非常好的隨機(jī)數(shù)算法，但它們都已經(jīng)被發(fā)表，因此它們不能被使用，因?yàn)榧偃缫粋€(gè)攻擊者可以猜出p和q一半的位的話(huà)，那么他們就已經(jīng)可以輕而易舉地推算出另一半。

　　此外密鑰d必須足夠大，1990年有人證明假如p大于q而小于2q（這是一個(gè)很經(jīng)常的情況）而，那么從N和e可以很有效地推算出d。此外e = 2永遠(yuǎn)不應(yīng)該被使用。

　　運(yùn)算速度

　　由于進(jìn)行的都是大數(shù)計(jì)算，使得RSA最快的情況也比DES慢上好幾倍，無(wú)論是軟件還是硬件實(shí)現(xiàn)。速度一直是RSA的缺陷。一般來(lái)說(shuō)只用于少量數(shù)據(jù)加密。RSA的速度比對(duì)應(yīng)同樣安全級(jí)別的對(duì)稱(chēng)密碼算法要慢1000倍左右。

　　比起DES和其它對(duì)稱(chēng)算法來(lái)說(shuō)，RSA要慢得多。實(shí)際上Bob一般使用一種對(duì)稱(chēng)算法來(lái)加密他的信息，然后用RSA來(lái)加密他的比較短的對(duì)稱(chēng)密碼，然后將用RSA加密的對(duì)稱(chēng)密碼和用對(duì)稱(chēng)算法加密的消息送給Alice。

　　這樣一來(lái)對(duì)隨機(jī)數(shù)的要求就更高了，尤其對(duì)產(chǎn)生對(duì)稱(chēng)密碼的要求非常高，因?yàn)榉駝t的話(huà)可以越過(guò)RSA來(lái)直接攻擊對(duì)稱(chēng)密碼。

　　密鑰分配

　　和其它加密過(guò)程一樣，對(duì)RSA來(lái)說(shuō)分配公鑰的過(guò)程是非常重要的。分配公鑰的過(guò)程必須能夠抵擋一個(gè)從中取代的攻擊。假設(shè)Eve交給Bob一個(gè)公鑰，并使Bob相信這是Alice的公鑰，并且她可以截下Alice和Bob之間的信息傳遞，那么她可以將她自己的公鑰傳給Bob，Bob以為這是Alice的公鑰。Eve可以將所有Bob傳遞給Alice的消息截下來(lái)，將這個(gè)消息用她自己的密鑰解密，讀這個(gè)消息，然后將這個(gè)消息再用Alice的公鑰加密后傳給Alice。理論上Alice和Bob都不會(huì)發(fā)現(xiàn)Eve在偷聽(tīng)他們的消息。今天人們一般用數(shù)字認(rèn)證來(lái)防止這樣的攻擊。

　　時(shí)間攻擊

　　1995年有人提出了一種非常意想不到的攻擊方式：假如Eve對(duì)Alice的硬件有充分的了解，而且知道它對(duì)一些特定的消息加密時(shí)所需要的時(shí)間的話(huà)，那么她可以很快地推導(dǎo)出d。這種攻擊方式之所以會(huì)成立，主要是因?yàn)樵谶M(jìn)行加密時(shí)所進(jìn)行的模指數(shù)運(yùn)算是一個(gè)位元一個(gè)位元進(jìn)行的而位元為1所花的運(yùn)算比位元為0的運(yùn)算要多很多，因此若能得到多組訊息與其加密時(shí)間，就會(huì)有機(jī)會(huì)可以反推出私鑰的內(nèi)容。

　　分解 從而在已知n d的情況下無(wú)法獲得e；同樣在已知n e的情況下無(wú)法 求得d。

　　實(shí)踐：

　　接下來(lái)我們來(lái)一個(gè)實(shí)踐，看看實(shí)際的操作： 找兩個(gè)素?cái)?shù)： p=47 q=59 這樣 n=p*q=2773 t=（p-1）*（q-1）=2668 取e=63，滿(mǎn)足e《t并且e和t互素 用perl簡(jiǎn)單窮舉可以獲得滿(mǎn)主 e*d%t ==1的數(shù)d： C：\Temp》perl -e “foreach $i （1..9999）{ print（$i），last if $i*63&68==1 }” 847 即d＝847

　　最終我們獲得關(guān)鍵的 n=2773 d=847 e=63

　　取消息M=244我們看看

　　加密：

　　c=M**d%n = 244**847‘73 用perl的大數(shù)計(jì)算來(lái)算一下： C：\Temp》perl -Mbigint -e “print 244**847’73” 465 即用d對(duì)M加密后獲得加密信息c＝465

　　解密：

　　我們可以用e來(lái)對(duì)加密后的c進(jìn)行解密，還原M： m=c**e%n=465**63‘73 ： C：\Temp》perl -Mbigint -e “print 465**63’73” 244 即用e對(duì)c解密后獲得m=244 ， 該值和原始信息M相等。