RSA演演算法

RSA公開密鑰密碼體制。所謂的公開密鑰密碼體制就是使用不同的加密密鑰與解密密鑰，是一種“由已知加密密鑰推導出解密密鑰在計算上是不可行的”密碼體制。

在公開密鑰密碼體制中，加密密鑰（即公開密鑰）PK是公開信息，而解密密鑰（即秘密密鑰）SK是需要保密的。加密演演算法E和解密演演算法D也都是公開的。雖然解密密鑰SK是由公開密鑰PK決定的，由於無法計算出大數n的歐拉函數phi(N)，所以不能根據PK計算出SK。

正是基於這種理論，1978年出現了著名的RSA演演算法，它通常是先生成一對RSA 密鑰，其中之一是保密密鑰，由用戶保存；另一個為公開密鑰，可對外公開，甚至可在網路伺服器中註冊。為提高保密強度，RSA密鑰至少為500位長，一般推薦使用1024位。這就使加密的計算量很大。為減少計算量，在傳送信息時，常採用傳統加密方法與公開密鑰加密方法相結合的方式，即信息採用改進的DES或IDEA密鑰加密，然後使用RSA密鑰加密對話密鑰和信息摘要。對方收到信息后，用不同的密鑰解密並可核對信息摘要。

RSA演演算法是第一個能同時用於加密和數字簽名的演演算法，也易於理解和操作。RSA是被研究得最廣泛的公鑰演演算法，從提出到現今的三十多年裡，經歷了各種攻擊的考驗，逐漸為人們接受，截止2017年被普遍認為是最優秀的公鑰方案之一。

SET(Secure Electronic Transaction)協議中要求CA採用2048bits長的密鑰，其他實體使用1024比特的密鑰。RSA密鑰長度隨著保密級別提高，增加很快。下表列出了對同一安全級別所對應的密鑰長度。

這種演演算法1978年就出現了，它是第一個既能用於數據加密也能用於數字簽名的演演算法。它易於理解和操作，也很流行。演演算法的名字以發明者的名字命名：Ron Rivest, Adi Shamir 和 Leonard Adleman。早在1973年，英國國家通信總局的數學家Clifford Cocks就發現了類似的演演算法。但是他的發現被列為絕密，直到1997年才公諸於世。

RSA演演算法是一種非對稱密碼演演算法，所謂非對稱，就是指該演演算法需要一對密鑰，使用其中一個加密，則需要用另一個才能解密。

RSA的安全性依賴於大數分解，但是否等同於大數分解一直未能得到理論上的證明，也並沒有從理論上證明破譯。RSA的難度與大數分解難度等價。因為沒有證明破解RSA就一定需要做大數分解。假設存在一種無須分解大數的演演算法，那它肯定可以修改成為大數分解演演算法，即RSA的重大缺陷是無法從理論上把握它的保密性能如何，而且密碼學界多數人士傾向於因子分解不是NPC問題。

目前，RSA的一些變種演演算法已被證明等價於大數分解。不管怎樣，分解n是最顯然的攻擊方法。現在，人們已能分解140多個十進位位的大素數。因此，模數n必須選大些，視具體適用情況而定。

RSA演演算法的保密強度隨其密鑰的長度增加而增強。但是，密鑰越長，其加解密所耗用的時間也越長。因此，要根據所保護信息的敏感程度與攻擊者破解所要花費的代價值不值得以及系統所要求的反應時間來綜合考慮，尤其對於商業信息領域更是如此。

首先要使用概率演演算法來驗證隨機產生的大的整數是否是質數，這樣的演演算法比較快而且可以消除掉大多數非質數。假如有一個數通過了這個測試的話，那麼要使用一個精確的測試來保證它的確是一個質數。

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

此外尋找質數的演演算法不能給攻擊者任何信息，這些質數是怎樣找到的，尤其產生隨機數的軟體必須非常好。要求是隨機和不可預測。這兩個要求並不相同。一個隨機過程可能可以產生一個不相關的數的系列，但假如有人能夠預測出（或部分地預測出）這個系列的話，那麼它就已經不可靠了。比如有一些非常好的隨機數演演算法，但它們都已經被發表，因此它們不能被使用，因為假如一個攻擊者可以猜出p和q一半的位的話，那麼他們就已經可以輕而易舉地推算出另一半。

此外密鑰d必須足夠大，1990年有人證明假如p大於q而小於2q（這是一個很經常的情況）而d < N^(1/4)/3,那麼d是e/N的某一個漸進分數的分母（這個演演算法的原理是利用N=pq來逼近phi(N):=(p-1)(q-1)，而演演算法要求d*e除以phi(N)的餘數是1，所以de=k phi(N)+1，e/phi(N)=k/d +1/phi(N)，這說明了e/phi(N)與k/d近似相等，從而可以通過e/N的漸進分數來尋找d（當然更多的，我們也可以更好地估計phi(N)來獲得一個更好的估計，但對通常情況（e=65537），RSA演演算法仍然是安全的））。

最後，RSA的原理保證了d和e必須與(p-1)(q-1)的因子互素，因此d，e都不可能為2。

由於進行的都是大數計算，使得RSA最快的情況也比DES慢上好幾倍，無論是軟體還是硬體實現。速度一直是RSA的缺陷。一般來說只用於少量數據加密。RSA的速度是對應同樣安全級別的對稱密碼演演算法的1/1000左右。

比起DES和其它對稱演演算法來說，RSA要慢得多。實際上Bob一般使用一種對稱演演算法來加密他的信息，然後用RSA來加密他的比較短的對稱密碼，然後將用RSA加密的對稱密碼和用對稱演演算法加密的消息送給Alice。

這樣一來對隨機數的要求就更高了，尤其對產生對稱密碼的要求非常高，因為否則的話可以越過RSA來直接攻擊對稱密碼。

和其它加密過程一樣，對RSA來說分配公鑰的過程是非常重要的。分配公鑰的過程必須能夠抵擋中間人攻擊。假設Eve交給Bob一個公鑰，並使Bob相信這是Alice的公鑰，並且她可以截下Alice和Bob之間的信息傳遞，那麼她可以將她自己的公鑰傳給Bob，Bob以為這是Alice的公鑰。Eve可以將所有Bob傳遞給Alice的消息截下來，將這個消息用她自己的密鑰解密，讀這個消息，然後將這個消息再用Alice的公鑰加密後傳給Alice。理論上Alice和Bob都不會發現Eve在偷聽他們的消息。今天人們一般用數字認證來防止這樣的攻擊。

1995年有人提出了一種非常意想不到的攻擊方式：假如Eve對Alice的硬體有充分的了解，而且知道它對一些特定的消息加密時所需要的時間的話，那麼她可以很快地推導出d。這種攻擊方式之所以會成立，主要是因為在進行加密時所進行的模指數運算是一個位元一個位元進行的而位元為1所花的運算比位元為0的運算要多很多，因此若能得到多組訊息與其加密時間，就會有機會可以反推出私鑰的內容。

1，針對RSA最流行的攻擊一般是基於大數因數分解。1999年，RSA-155 (512 bits)被成功分解，花了五個月時間（約8000 MIPS年）和224 CPU hours在一台有3.2G中央內存的Cray C916計算機上完成。

RSA-158表示如下：

39505874583265144526419767800614481996020776460304936454139376051579355626529450683609727842468219535093544305870490251995655335710209799226484977949442955603= 3388495837466721394368393204672181522815830368604993048084925840555281177× 11658823406671259903148376558383270818131012258146392600439520994131344334162924536139

2009年12月12日，編號為RSA-768（768 bits, 232 digits）數也被成功分解。這一事件威脅了現通行的1024-bit密鑰的安全性，普遍認為用戶應儘快升級到2048-bit或以上。

RSA-768表示如下：

1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413= 3347807169895689878604416984821269081770479498371376856891 2431388982883793878002287614711652531743087737814467999489× 3674604366679959042824463379962795263227915816434308764267 6032283815739666511279233373417143396810270092798736308917

2，秀爾演演算法

量子計算里的秀爾演演算法能使窮舉的效率大大的提高。由於RSA演演算法是基於大數分解（無法抵抗窮舉攻擊），因此在未來量子計算能對RSA演演算法構成較大的威脅。一個擁有N量子比特的量子計算機，每次可進行2^N次運算，理論上講，密鑰為1024位長的RSA演演算法，用一台512量子比特位的量子計算機在1秒內即可破解。

RSA公開密鑰密碼體制的原理是：根據數論，尋求兩個大素數比較簡單，而將它們的乘積進行因式分解卻極其困難，因此可以將乘積公開作為加密密鑰。

迄今為止，對RSA的攻擊已經很多，但都沒有對它構成真正的威脅。在這裡，我們討論一些典型的攻擊方法。

RSA的選擇密碼攻擊

RSA在選擇密碼攻擊面前顯得很脆弱。一般攻擊者是將某一信息進行下偽裝，讓擁有私鑰的實體簽名；然後，經過計算就可得到它所想要的信息。實際上，攻擊利用的都是同一個弱點，即存在這樣一個事實：乘冪保留了輸入的乘法結構。前面已經提到，這個固有的問題來自於公鑰密碼系統的最基本的特徵，即每個人都能使用公鑰加密信息。從演演算法上無法解決這一問題，改進措施有兩條：是採用好的公鑰協議保證工作過程中實體不對其他實體任意產生的信息解密，不對自己一無所知的信息簽名；二是決不對陌生人送來的隨機文檔簽名，或簽名時首先對文檔作Hash處理，或同時使用不同的簽名演演算法。

RSA的小指數攻擊

當公鑰e取較小的值，雖然會使加密變得易於實現，速度有所提高，但這樣做也是不安全的。最簡單的辦法就是e和d都取較大的值。

因為密鑰的產生受素數產生技術的限制，所以也有它的局限性。

（1）密鑰的產生受素數產生技術的限制，因而難以做到一次一密；

（2）分組長度太大，為保證安全性，n至少也要600比特以上，使運算代價很高，尤其是速度較慢，比對稱密碼演演算法慢幾個數量級；隨著大整數素因數分解演演算法的改進和計算機計算能力的提高，對n的長度在不斷增加，不利於實現數據格式的標準化。

● 公開密鑰加密

● 量子計算機

● 秀爾演演算法