RSA加密演算法

RSA
概述
設計者	羅納德·李維斯特; 阿迪·薩莫爾; 倫納德·阿德曼
首次發布	1977
認證	PKCS#1, ANSI X9.31, IEEE 1363
密碼細節
金鑰長度	2048 - 4096 位（常規情況）
重複回數	1
最佳公開破解
	傳統電腦：普通數體篩選法; 量子電腦：秀爾演算法; RSA-250（829位）已經被攻破

RSA加密演算法是一種非對稱加密演算法，在公開金鑰加密和電子商業中被廣泛使用。RSA是由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）在1977年一起提出的。當時他們三人都在麻省理工學院工作。RSA 就是他們三人姓氏開頭字母拼在一起組成的。^[1]

1973年，在英國政府通訊總部工作的數學家克里福·柯克斯（Clifford Cocks）在一個內部檔案中提出了一個與之等效的演算法，但該演算法被列入機密，直到1997年才得到公開。^[2]

對極大整數做因數分解的難度決定了 RSA 演算法的可靠性。換言之，對一極大整數做因數分解愈困難，RSA 演算法愈可靠。假如有人找到一種快速因數分解的演算法的話，那麼用 RSA 加密的訊息的可靠性就會極度下降。但找到這樣的演算法的可能性是非常小的。今天只有短的 RSA 鑰匙才可能被強力方式破解。到2020年為止，世界上還沒有任何可靠的攻擊RSA演算法的方式。只要其鑰匙的長度足夠長，用RSA加密的訊息實際上是不能被破解的。

1983年9月12日麻省理工學院在美國為RSA演算法申請了專利。^[3]這個專利於2000年9月21日失效。^[4]由於該演算法在申請專利前就已經被發表了^[5]，在世界上大多數其它地區這個專利權不被承認。

操作

公鑰與私鑰的產生

假設Alice想要通過不可靠的媒體接收Bob的私人訊息。她可以用以下的方式來產生一個公鑰和一個私鑰：

隨意選擇兩個大的質數 $p$ 和 $q$ ， $p$ 不等於 $q$ ，計算 $N=pq$ 。
根據歐拉函數，求得 $r=\varphi (N)=\varphi (p)\times \varphi (q)=(p-1)(q-1)$
選擇一個小於 $r$ 的整數 $e$ ，使 $e$ 與 $r$ 互質。並求得 $e$ 關於 $r$ 的模反元素，命名為 $d$ （求 $d$ 令 $ed\equiv 1{\pmod {r}}$ ）。（模反元素存在，若且唯若 $e$ 與 $r$ 互質）
將 $p$ 和 $q$ 的記錄銷毀。

$(N,e)$ 是公鑰， $(N,d)$ 是私鑰。Alice將她的公鑰 $(N,e)$ 傳給Bob，而將她的私鑰 $(N,d)$ 藏起來。

加密訊息

假設Bob想給Alice送訊息 $m$ ，他知道Alice產生的 $N$ 和 $e$ 。他使用起先與Alice約好的格式將 $m$ 轉換為一個小於 $N$ 的非負整數 $n$ ，比如他可以將每一個字轉換為這個字的Unicode碼，然後將這些數字連在一起組成一個數字。假如他的資訊非常長的話，他可以將這個資訊分為幾段，然後將每一段轉換為 $n$ 。用下面這個公式他可以將 $n$ 加密為 $c$ ：

c=n^{e}{\bmod {N}}

這裡的 $c$ 可以用模冪演算法快速求出來。Bob算出 $c$ 後就可以將它遞移給Alice。

解密訊息

Alice得到Bob的訊息 $c$ 後就可以利用她的金鑰 $d$ 來解碼。她可以用以下這個公式來將 $c$ 轉換為 $n$ ：

n=c^{d}{\bmod {N}}

與 Bob 計算 $c$ 類似，這裡的 $n$ 也可以用模冪演算法快速求出。得到 $n$ 後，她可以將原來的資訊 $m$ 重新復原。

解碼的原理是

c^{d}\equiv n^{e\cdot d}\ (\mathrm {mod} \ N)

已知 $ed\equiv 1{\pmod {r}}$ ，即 $ed=1+h\varphi (N)$ 。那麼有

n^{ed}=n^{1+h\varphi (N)}=n\cdot n^{h\varphi (N)}=n\left(n^{\varphi (N)}\right)^{h}

若 $n$ 與 $N$ 互質，則由歐拉定理得：

n^{ed}\equiv n\left(n^{\varphi (N)}\right)^{h}\equiv n(1)^{h}\equiv n{\pmod {N}}

若 $n$ 與 $N$ 不互質，則不失一般性考慮 $n=ph$ ，以及 $ed-1=k(q-1)$ ，得：

n^{ed}=(ph)^{ed}\equiv 0\equiv ph\equiv n{\pmod {p}}

n^{ed}=n^{ed-1}n=n^{k(q-1)}n=(n^{q-1})^{k}n\equiv 1^{k}n\equiv n{\pmod {q}}

故 $n^{ed}\equiv n{\pmod {N}}$ 得證。

簽章訊息

RSA也可以用來為一個訊息署名。假如Alice想給Bob遞移一個署名的訊息的話，那麼她可以為她的訊息計算一個雜湊值（Message digest），然後用她的私鑰「加密」（如同前面「加密訊息」的步驟）這個雜湊值並將這個「署名」加在訊息的後面。這個訊息只有用她的公鑰才能被解密。Bob獲得這個訊息後可以用Alice的公鑰「解密」（如同前面「解密訊息」的步驟）這個雜湊值，然後將這個資料與他自己為這個訊息計算的雜湊值相比較。假如兩者相符的話，那麼Bob就可以知道發信人持有Alice的私鑰，以及這個訊息在傳播路徑上沒有被篡改過。

正確性證明

首選取兩個互質數 $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公鑰為 $(N,e)$ ,私鑰為 $(N,d)$ 。

加密原文 $m$ 得到密文

x=m^{e}\%N

解密公式為

m=x^{d}\%N

證明解密邏輯：

在 $m<N$ 的狀況下證明 $m=x^{d}\%N$ ，就是證明 $x^{d}\%N-m=0$

$x^{d}\%N-m$

$=(m^{e}\%N)^{d}\%N-m$

$=m^{ed}\%N-m\quad \because a^{b}\%p=((a\%p)^{b})\%p$

$=m^{k(p-1)(q-1)+1}\%N-m$

$=m*(m^{k(p-1)(q-1)}-1)\%N$

當m與N互質時，根據費馬小定理公式

$a^{p-1}\equiv 1(mod\ p)$

$\Rightarrow (m^{k(q-1)})^{p-1}\equiv 1(mod\ p)$

$\Rightarrow (m^{k(p-1)})^{q-1}\equiv 1(mod\ q)$

$\Rightarrow m^{k(p-1)(q-1)}\equiv 1(mod\ pq)$

$\Rightarrow m^{k(p-1)(q-1)}\equiv 1(mod\ N)$

$\Rightarrow m*(m^{k(p-1)(q-1)}-1)\%N=0$

當m與N不互質時，不妨設公因子為p，即 $m=ph_{1}(h_{1}<q)$

假設q整除m。因此 $q\mid ph_{1}$ ，因為q與p互質，根據歐幾里德引理， $q\mid h_{1}$ 。所以 $q\leq h_{1}$ ，而這與 $h_{1}<q$ 矛盾，所以q不整除m。

此時m與q互質，根據費馬小定理公式

$a^{p-1}\equiv 1(mod\ p)$

$\Rightarrow m^{q-1}\equiv 1(mod\ q)$

$\Rightarrow m^{k(p-1)(q-1)}\equiv 1(mod\ q)$

$\Rightarrow m^{k(p-1)(q-1)}-1=qh_{2}$

$\Rightarrow m*(m^{k(p-1)(q-1)}-1)\%N=ph_{1}*qh_{2}\%N=Nh_{1}h_{2}\%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^[6]，使人們開始質疑1024位元長的N的安全性，目前推薦 $N$ 的長度至少為2048位元。^[7]

1994年，彼得·秀爾證明一台量子電腦可以在多項式時間內進行因數分解。假如量子電腦有朝一日可以成為一種可行的技術的話，那麼秀爾的演算法可以淘汰RSA和相關的衍生演算法。（即依賴於分解大整數困難性的加密演算法）

假如有人能夠找到一種有效的分解大整數的演算法的話，或者假如量子電腦可行的話，那麼在解密和製造更長的鑰匙之間就會展開一場競爭。但從原理上來說RSA在這種情況下是不可靠的。

實現細節

金鑰生成

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

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

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

此外金鑰 $d$ 必須足夠大，1990年有人證明假如 $p$ 大於 $q$ 而小於 $2q$ （這是一個很常見的情況）而 $d<{\frac {1}{3}}\times N^{\frac {1}{4}}$ ，那麼從 $N$ 和 $e$ 可以很有效地推算出 $d$ 。此外 $e=2$ 永遠不應該被使用。

速度

比起AES、3DES和其它對稱演算法來說，RSA要慢得多。實際的運用（如TLS）一般結合了對稱加密（如AES）和非對稱加密（如RSA）兩者。

金鑰分配

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

典型金鑰長度

NIST建議的RSA金鑰長度為至少2048位元^[8]。實作上，強制設定金鑰長度為2048位元的稱RSA或RSA2(意即RSA version 2)，而未強制設定的稱RSA1以資區別，兩者差異主要在金鑰長度。

已公開的或已知的攻擊方法

大數因數分解

最常見的針對RSA的攻擊是基於大數因數分解。1999年，RSA-155（512 bits）被成功分解，花費五個月時間（約8000 MIPS年）、224 CPU小時，在一台有3.2G中央主記憶體^{[需要解釋]}的Cray C916電腦上完成。^[9]

RSA-155表示如下：

39505874583265144526419767800614481996020776460304936454139376051579355626529450683609
727842468219535093544305870490251995655335710209799226484977949442955603

= 3388495837466721394368393204672181522815830368604993048084925840555281177×
  11658823406671259903148376558383270818131012258146392600439520994131344334162924536139

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

RSA-768表示如下：

123018668453011775513049495838496272077285356959533479219732245215172640050726
365751874520219978646938995647494277406384592519255732630345373154826850791702
6122142913461670429214311602221240479274737794080665351419597459856902143413

= 3347807169895689878604416984821269081770479498371376856891
  2431388982883793878002287614711652531743087737814467999489×
  3674604366679959042824463379962795263227915816434308764267
  6032283815739666511279233373417143396810270092798736308917

時間攻擊

1995年，丹·博內（英語：Dan Boneh）和大衛·布魯姆利（英語：David Brumley）提出了一種出人意料的攻擊方式：假如Eve（竊密者）對Alice的硬體有充分的了解，而且知道它對一些特定的訊息加密時所需要的時間的話，那麼她可以很快地推導出d。這種攻擊方式之所以會成立，主要是因為在進行加密時所進行的模指數運算是一個位元一個位元進行的，而位元為1所花的運算比位元為0的運算要多很多，因此若能得到多組訊息與其加密時間，就會有機會可以反推出私鑰的內容。^[11]

參考文獻

^ Calderbank, Michael. The RSA Cryptosystem: History, Algorithm, Primes (PDF). 2007-08-20. （原始內容 (PDF)存檔於2016-12-13）.
^ Cocks, C.C. A Note on Non-Secret Encryption (PDF). www.gchq.gov.uk. 1973-11-20 [2017-05-30]. （原始內容存檔 (PDF)於2017-02-16）.
^ Cryptographic communications system and method, 1977-12-14 [2018-04-09], （原始內容存檔於2019-02-17）
^ RSA Security Releases RSA Encryption Algorithm into Public Domain. [2010-03-03]. （原始內容存檔於2007-06-21）.
^ Robinson, Sara. Still Guarding Secrets after Years of Attacks, RSA Earns Accolades for its Founders (PDF). SIAM News. June 2003, 36 (5) [2018-04-09]. （原始內容 (PDF)存檔於2017-01-16）.
^ Tromer, Eran. TWIRL (The Weizmann Institute Relation Locator). cs.tau.ac.il. [2018-04-16]. （原始內容存檔於2018-04-20）.
^ Has the RSA algorithm been compromised as a result of Bernstein's Paper? （頁面存檔備份，存於網際網路檔案館） What key size should I be using?
^ Keylength - NIST Report on Cryptographic Key Length and Cryptoperiod (2019). www.keylength.com. [2020-04-22]. （原始內容存檔於2020-04-04）.
^ 存档副本. [2018-04-09]. （原始內容存檔於2017-07-01）. ^{[需要較佳來源]}
^ Factorization of a 768-bit RSA modulus (PDF). 2010年1月7日 [2010年1月10日]. （原始內容 (PDF)存檔於2010年3月31日）.
^ Remote timing attacks are practical. （頁面存檔備份，存於網際網路檔案館）. SSYM'03 Proceedings of the 12th conference on USENIX Security Symposium.

外部連結

RSA, The Security Division of EMC（頁面存檔備份，存於網際網路檔案館）
RSA演算法詳解（頁面存檔備份，存於網際網路檔案館）

[1] Calderbank, Michael. The RSA Cryptosystem: History, Algorithm, Primes (PDF). 2007-08-20. （原始內容 (PDF)存檔於2016-12-13）.

[2] Cocks, C.C. A Note on Non-Secret Encryption (PDF). www.gchq.gov.uk. 1973-11-20 [2017-05-30]. （原始內容存檔 (PDF)於2017-02-16）.

[3] Cryptographic communications system and method, 1977-12-14 [2018-04-09], （原始內容存檔於2019-02-17）

[4] RSA Security Releases RSA Encryption Algorithm into Public Domain. [2010-03-03]. （原始內容存檔於2007-06-21）.

[SIAM-5] Robinson, Sara. Still Guarding Secrets after Years of Attacks, RSA Earns Accolades for its Founders (PDF). SIAM News. June 2003, 36 (5) [2018-04-09]. （原始內容 (PDF)存檔於2017-01-16）.

[6] Tromer, Eran. TWIRL (The Weizmann Institute Relation Locator). cs.tau.ac.il. [2018-04-16]. （原始內容存檔於2018-04-20）.

[7] Has the RSA algorithm been compromised as a result of Bernstein's Paper? （頁面存檔備份，存於網際網路檔案館） What key size should I be using?

[8] Keylength - NIST Report on Cryptographic Key Length and Cryptoperiod (2019). www.keylength.com. [2020-04-22]. （原始內容存檔於2020-04-04）.

[9] 存档副本. [2018-04-09]. （原始內容存檔於2017-07-01）. ^{[需要較佳來源]}

[10] Factorization of a 768-bit RSA modulus (PDF). 2010年1月7日 [2010年1月10日]. （原始內容 (PDF)存檔於2010年3月31日）.

[11] Remote timing attacks are practical. （頁面存檔備份，存於網際網路檔案館）. SSYM'03 Proceedings of the 12th conference on USENIX Security Symposium.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

操作