RSA加密演演算法

RSA加密演演算法是一種非對稱加密演演算法，在公開金鑰加密和電子商業中被廣泛使用。RSA是由羅納德·李維斯特在1977年一起提出的。當時他們三人都在麻省理工學院工作。RSA 就是他們三人姓氏開頭字母拼在一起組成的。1973年，在英國政府通訊總部工作的數學家克利福德·柯克斯在一個內部檔案中提出了一個與之等效的演算法，但該演算法被列入機密，直到1997年才得到公開。對極大整數做因數分解的難度決定了 RSA 演算法的可靠性。換言之，對一極大整數做因數分解愈困難，RSA 演算法愈可靠。假如有人找到一種快速因數分解的演算法的話，那麼用 RSA 加密的-{zh-hans:資訊;zh-tw:訊息}-的可靠性就會極度下降。但找到這樣的演算法的可能性是非常小的。今天只有短的 RSA 鑰匙才可能被強力方式破解。到2020年為止，世界上還沒有任何可靠的攻擊RSA演算法的方式。只要其鑰匙的長度足夠長，用RSA加密的-{zh-hans:資訊;zh-tw:訊息}-實際上是不能被破解的。1983年9月12日麻省理工學院在美國為RSA演算法申請了專利。這個專利於2000年9月21日失效。由於該演算法在申請專利前就已經被發表了，在世界上大多數其它地區這個專利權不被承認。操作.公鑰與私鑰的產生.假設Alice想要透過不可靠的媒體接收Bob的私人訊息。她可以用以下的方式來產生一個公鑰和一個私鑰：formula_20是公鑰，formula_21是私鑰。Alice將她的公鑰formula_20傳給Bob，而將她的私鑰formula_21藏起來。加密訊息.假設Bob想給Alice送訊息formula_24，他知道Alice產生的formula_25和formula_8。他使用起先與Alice約好的格式將formula_24轉換為一個小於formula_25的非負整數formula_29，比如他可以將每一個字轉換為這個字的Unicode碼，然後將這些數字連在一起組成一個數字。假如他的資訊非常長的話，他可以將這個資訊分為幾段，然後將每一段轉換為formula_29。用下面這個公式他可以將formula_29加密為formula_32：formula_33計算formula_32並不複雜。Bob算出formula_32後就可以將它傳遞給Alice。解密訊息.Alice得到Bob的訊息formula_32後就可以利用她的金鑰formula_13來解碼。她可以用以下這個公式來將formula_32轉換為formula_29：formula_40得到formula_29後，她可以將原來的資訊formula_24重新復原。解碼的原理是formula_43已知formula_15，即 formula_45。那麼有formula_46若formula_47與formula_48互質，則由尤拉定理得：formula_49若formula_47與formula_48不互質，則不失一般性考慮formula_52，以及formula_53，得：formula_54formula_55故 formula_56 得證。簽名訊息.RSA也可以用來為一個訊息署名。假如Alice想給Bob傳遞一個署名的訊息的話，那麼她可以為她的訊息計算一個雜湊值這個雜湊值，然後將這個資料與他自己為這個訊息計算的雜湊值相比較。假如兩者相符的話，那麼Bob就可以知道發信人持有Alice的私鑰，以及這個訊息在傳播路徑上沒有被篡改過。正確性證明.首選取兩個互質數formula_1和formula_2,乘法計算formula_59得到formula_25。然後計算出尤拉formula_61：formula_62函式formula_61是小於或等於formula_25的正整數中與formula_25互質的數的數目。根據尤拉公式，由於formula_1和formula_2都是質數，故formula_68這時候我們隨機選擇一個整數formula_8，條件是formula_70，且formula_8與formula_72 互質。接著我們計算formula_8對formula_72的模逆元得到formula_13：formula_76這個公式簡單的說就是 formula_77除以formula_72得到的餘數為1，這個公式可以轉換成formula_79即formula_80於是，RSA公鑰為formula_20,私鑰為formula_21。加密原文formula_24得到密文formula_84解密公式為formula_85證明解密邏輯：在 formula_86 的狀況下證明formula_85，就是證明formula_88formula_89formula_90formula_91formula_92formula_93當m與N互質時，根據費馬小定理公式formula_94formula_95formula_96formula_97formula_98formula_99當m與N不互質時，不妨設公因子為p，即formula_100假設q整除m。因此formula_101，因為q與p互質，根據歐幾裡德引理，formula_102。所以formula_103，而這與formula_104矛盾，所以q不整除m。此時m與q互質，根據費馬小定理公式formula_94formula_106formula_107formula_108formula_109,證明完成。安全性.假設偷聽者Eve獲得了Alice的公鑰formula_25和formula_8以及Bob的加密訊息formula_32，但她無法直接獲得Alice的金鑰formula_13。要獲得formula_13，最簡單的方法是將formula_25分解為formula_1和formula_2，這樣她可以得到同餘方程formula_118並解出formula_13，然後代入解密公式formula_120匯出"n"。至今為止也沒有人能夠證明對formula_25進行因數分解是唯一的從formula_32匯出formula_29的方法，直到今天也還沒有找到比它更簡單的方法。因此今天一般認為只要formula_25足夠大，那麼駭客就沒有辦法了。假如formula_25的長度小於或等於256位，那麼用一臺個人電腦在幾個小時內就可以分解它的因子了。1999年，數百臺電腦合作分解了一個512位長的formula_25。一個由Shamir 和Tromer在2003年從理論上構建的硬體TWIRL，使人們開始質疑1024位長的N的安全性，目前推薦formula_25的長度至少為2048位。1994年，彼得·秀爾證明一臺量子計算機可以在多項式時間內進行因數分解。假如量子計算機有朝一日可以成為一種可行的技術的話，那麼秀爾的演算法可以淘汰RSA和相關的衍生演算法。假如有人能夠找到一種有效的分解大整數的演算法的話，或者假如量子計算機可行的話，那麼在解密和製造更長的鑰匙之間就會展開一場競爭。但從原理上來說RSA在這種情況下是不可靠的。實現細節.金鑰生成.首先要使用機率演算法來驗證隨機產生的大的整數是否質數，這樣的演算法比較快而且可以消除掉大多數非質數。假如有一個數通過了這個測試的話，那麼要使用一個精確的測試來保證它的確是一個質數。除此之外這樣找到的formula_1和formula_2還要滿足一定的要求，首先它們不能太靠近，此外formula_130或formula_131的因子不能太小，否則的話formula_25也可以被很快地分解。此外尋找質數的演算法不能給攻擊者任何資訊，這些質數是怎樣找到的，尤其產生隨機數的軟體必須非常好。要求是隨機和不可預測。這兩個要求並不相同。一個隨機過程可能可以產生一個不相關的數的系列，但假如有人能夠預測出這個系列的話，那麼它就已經不可靠了。比如有一些非常好的隨機數演算法，但它們都已經被髮表，因此它們不能被使用，因為假如一個攻擊者可以猜出formula_1和formula_2一半的位的話，那麼他們就已經可以輕而易舉地推算出另一半。此外金鑰formula_13必須足夠大，1990年有人證明假如formula_1大於formula_2而小於formula_138而formula_139，那麼從formula_25和formula_8可以很有效地推算出formula_13。此外formula_143永遠不應該被使用。速度.比起AES、3DES和其它對稱演算法來說，RSA要慢得多。實際的運用兩者。金鑰分配.和其它加密過程一樣，對RSA來說分配公鑰的過程是非常重要的。分配公鑰的過程必須能夠抵擋中間人攻擊。假設Eve交給Bob一個公鑰，並使Bob相信這是Alice的公鑰，並且她可以截下Alice和Bob之間的資訊傳遞，那麼她可以將她自己的公鑰傳給Bob，Bob以為這是Alice的公鑰。Eve可以將所有Bob傳遞給Alice的訊息截下來，將這個訊息用她自己的金鑰解密，讀這個訊息，然後將這個訊息再用Alice的公鑰加密後傳給Alice。理論上Alice和Bob都不會發現Eve在偷聽他們的訊息。今天人們一般用可靠的第三方機構簽發憑證來防止這樣的攻擊。典型金鑰長度.NIST建議的RSA金鑰長度為至少2048位元。已公開的或已知的攻擊方法.大數因數分解.針對RSA最流行的攻擊一般是基於大數因數分解。1999年，RSA-155和224 CPU hours在一臺有3.2G中央記憶體的Cray C916計算機上完成。RSA-155表示如下：39505874583265144526419767800614481996020776460304936454139376051579355626529450683609727842468219535093544305870490251995655335710209799226484977949442955603= 3388495837466721394368393204672181522815830368604993048084925840555281177×116588234066712599031483765583832708181310122581463926004395209941313443341629245361392009年12月12日，編號為RSA-768數也被成功分解。這一事件威脅了現通行的1024-bit金鑰的安全性，普遍認為使用者應儘快升級到2048-bit或以上。RSA-768表示如下：1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413= 33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489×36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917時間攻擊.1995年，和提出了一種非常意想不到的攻擊方式：假如Eve對Alice的硬體有充分的瞭解，而且知道它對一些特定的訊息加密時所需要的時間的話，那麼她可以很快地推匯出"d"。這種攻擊方式之所以會成立，主要是因為在進行加密時所進行的模指數運算是一個位元一個位元進行的，而位元為1所花的運算比位元為0的運算要多很多，因此若能得到多組訊息與其加密時間，就會有機會可以反推出私鑰的內容。