RSA加密演算法
 |
RSA加密演算法是一種非對稱加密演算法，在公開密鑰加密和電子商業中被廣泛使用。RSA是由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）在1977年一起提出的。當時他們三人都在麻省理工學院工作。RSA 就是他們三人姓氏開頭字母拼在一起組成的。
1973年，在英國政府通訊總部工作的數學家克利福德·柯克斯（Clifford Cocks）在一個內部文件中提出了一個與之等效的算法，但該算法被列入機密，直到1997年才得到公開。
對極大整數做因數分解[1] 的難度決定了 RSA 算法的可靠性。換言之，對一極大整數做因數分解愈困難，RSA 算法愈可靠。假如有人找到一種快速因數分解的算法的話，那麼用 RSA 加密的:信息:訊息的可靠性就會極度下降。但找到這樣的算法的可能性是非常小的。今天只有短的 RSA 鑰匙才可能被強力方式破解。到目前為止，世界上還沒有任何可靠的攻擊RSA算法的方式。只要其鑰匙的長度足夠長，用RSA加密的-信息:訊息實際上是不能被破解的。
1983年9月12日麻省理工學院在美國為RSA算法申請了專利。這個專利於2000年9月21日失效。由於該算法在申請專利前就已經被發表了，在世界上大多數其它地區這個專利權不被承認。
目錄
正確性證明
首選取兩個互質數p和q, 乘法計算p * q得到N。
然後計算出歐拉\Phi (N)： \Phi函數\Phi (N)是小於或等於N的正整數中與N互質的數的數目。 根據歐拉公式，由於p和q都是質數，故
- \Phi (N) = (p - 1) * (q - 1)
這時候我們隨機選擇一個整數e，條件是1 < e < \Phi(N)，且e與\Phi(N) 互質。 接着我們計算e對\Phi(N)的模逆元得到d：
- e * d \equiv 1 \mod \Phi(N)
這個公式簡單的說就是 e * d除以\Phi(N)得到的餘數為1，這個公式可以轉換成
- ed \ \%\ ((p - 1) (q - 1)) = 1
即
- ed = k(p-1)(q-1)+1
於是，RSA公鑰為(e,n),私鑰為(d,n)。
加密原文x得到密文
- m = x^e \% n
解密公式為
- x = m^d \% n
證明解密邏輯：
證明 x = m^d \% n ，就是證明 m^d \% n - x = 0
m^d%n-x //如何=0，往下分解：
=(x^e%n)^d%n-x //代入加密原文
=x^ed%n-x //根據模運算公式：a ^ b % p = ((a % p)^b) % p
=x^(k(p-1)(q-1)+1)%n-x //代入ed的值
=x*(x^(k(p-1)(q-1))-1)%n //x挪到括號外，條件x<n
根據費馬小定理公式：a^(p-1) - 1可以被p整除。 所以x^(k(q-1))^(p-1) - 1 可以被p整除，x^(k(p-1))^(q-1) - 1 可以被q整除。 所以x^(k(p-1)(q-1)) - 1 可以被pq整除，也就是可以被N整除。 就是x*(x^(k(p-1)(q-1))-1)%n=0,證明完成。
安全性
假設偷聽者Eve獲得了Alice的公鑰N和e以及Bob的加密消息c，但她無法直接獲得Alice的密鑰d。要獲得d，最簡單的方法是將N分解為p和q，這樣她可以得到同餘方程de \equiv 1 (\mathrm{mod}(p-1)(q-1))並解出d，然後代入解密公式
- c^d \equiv n\ (\mathrm{mod}\ N)
導出n（破密）。但至今為止還沒有人找到一個多項式時間的算法來分解一個大的整數的因子，同時也還沒有人能夠證明這種算法不存在（見因數分解）。
至今為止也沒有人能夠證明對N進行因數分解是唯一的從c導出n的方法，直到今天也還沒有找到比它更簡單的方法。（至少沒有公開的方法。）
因此今天一般認為只要N足夠大，那麼駭客就沒有辦法了。
假如N的長度小於或等於256位，那麼用一台個人電腦在幾個小時內就可以分解它的因子了。1999年，數百台電腦合作分解了一個512位長的N。一個由Shamir 和Tromer在2003年從理論上構建的硬件TWIRL，使人們開始質疑1024位長的N的安全性，目前推N的長度至少為2048位。
1994年彼得·秀爾（Peter Shor）證明一台量子計算機可以在多項式時間內進行因數分解。假如量子計算機有朝一日可以成為一種可行的技術的話，那麼秀爾的算法可以淘汰RSA和相關的衍生算法。（即依賴於分解大整數困難性的加密算法）
假如有人能夠找到一種有效的分解大整數的算法的話，或者假如量子計算機可行的話，那麼在解密和製造更長的鑰匙之間就會展開一場競爭。但從原理上來說RSA在這種情況下是不可靠的。
簽名消息
RSA也可以用來為一個消息署名。假如Alice想給Bob傳遞一個署名的消息的話，那麼她可以為她的消息計算一個散列值（Message digest），然後用她的私鑰「加密」（如同前面「加密消息」的步驟）這個散列值並將這個「署名」加在消息的後面。這個消息只有用她的公鑰才能被解密。Bob獲得這個消息後可以用Alice的公鑰「解密」（如同前面「解密消息」的步驟）這個散列值，然後將這個數據與他自己為這個消息計算的散列值相比較。假如兩者相符的話，那麼Bob就可以知道發信人持有Alice的私鑰，以及這個消息在傳播路徑上沒有被篡改過。