RSA算法

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

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

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

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

## 操作

### 公鑰與私鑰的產生

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

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

得到 $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，使人們開始質疑 1024 位元長的 N 的安全性，目前推薦 $N$ 的長度至少為 2048 位元。

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 位元。

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

### 大數因數分解

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

 

RSA-155 表示如下：

```
39505874583265144526419767800614481996020776460304936454139376051579355626529450683609
727842468219535093544305870490251995655335710209799226484977949442955603

= 3388495837466721394368393204672181522815830368604993048084925840555281177×
  11658823406671259903148376558383270818131012258146392600439520994131344334162924536139
```

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

RSA-768 表示如下：

```
123018668453011775513049495838496272077285356959533479219732245215172640050726
365751874520219978646938995647494277406384592519255732630345373154826850791702
6122142913461670429214311602221240479274737794080665351419597459856902143413

= 3347807169895689878604416984821269081770479498371376856891
  2431388982883793878002287614711652531743087737814467999489×
  3674604366679959042824463379962795263227915816434308764267
  6032283815739666511279233373417143396810270092798736308917
```

### 時間攻擊

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

## 相關條目

* 公開金鑰加密
* 橢圓曲線密碼學
* 量子電腦
* 秀爾演算法
* 米勒 - 拉賓質數判定法
* 迪菲 - 赫爾曼密鑰交換
* 快速冪
* 擴充歐幾里得演算法

## 參考文獻

## 外部連結

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