密碼學/RSA

RSA 是一種非對稱的公鑰密碼學演算法，廣泛應用於電子商務。該演算法由羅恩·裡維斯特、阿迪·薩莫爾和倫納德·阿德曼在 1977 年描述；RSA 這三個字母分別代表他們姓氏的首字母。

克利福德·考克斯，一位在英國政府通訊總部工作的英國數學家，在 1973 年的一份內部檔案中描述了等效系統。然而，由於其最高機密分類，他的發現直到 1997 年才公佈。

RSA 系統的安全性依賴於 對非常大的整數進行因式分解 的難度。該領域的新型快速演算法可能會使 RSA 不安全，但這通常被認為不太可能發生。

該演算法於 1983 年在美國由麻省理工學院獲得專利。專利於 2000 年 9 月 21 日到期。由於該演算法在專利申請之前已經公佈，因此它無法在其他國家獲得專利。

操作

金鑰生成

假設使用者 Alice 希望允許 Bob 透過不安全的傳輸介質向她傳送私密訊息。她需要執行以下步驟來生成一個公鑰和一個私鑰

1. 隨機選擇兩個大的質數 p ≠ q，並且彼此獨立。計算 N = p q。
2. 選擇一個整數 1 < e < N，該整數與 (p-1)(q-1) 互質。
3. 計算 d 使得 d e ≡ 1 (mod (p-1)(q-1))。
4. 銷燬所有關於 p 和 q 的記錄。

• (步驟 2 和 3 可以使用擴充套件歐幾里得演算法執行；請參閱模運算。此外，可以使用丟番圖方程 $ed-k\phi (n)=1$ 來求解 e 或 d 的值。)

N 和 e 是公鑰，而 N 和 d 是私鑰。請注意，只有 d 是秘密，因為 N 是公開的。Alice 將公鑰傳送給 Bob，並保密私鑰。

您可以使用 OpenSSL 和一些 Unix 工具來生成和檢查真實的 RSA 金鑰對。（密碼學/使用 OpenSSL 生成金鑰對）。

加密訊息

假設 Bob 希望向 Alice 傳送訊息 m。他知道 Alice 公開的 N 和 e。他使用一些預先商定的可逆協議將 m 轉換為一個數字 n < N。例如，明文訊息中的每個字元都可以轉換為其 ASCII 碼，並將這些碼連線成一個數字。如果需要，他可以將 m 分成幾段，並分別加密每段。然後，他計算密文 c

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

這可以透過 平方求冪 的方法快速完成。然後 Bob 將 c 傳輸給 Alice。

解密訊息

Alice 從 Bob 處收到 c，並知道她的私鑰 d。她可以透過以下程式從 c 中恢復 n

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

然後，Alice 可以提取 n，因為 n < N。有了 n，她就可以恢復原始訊息 m。

解密過程有效是因為

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

並且 ed ≡ 1 (mod p-1) 以及 ed ≡ 1 (mod q-1)。費馬小定理得出

$n^{e\cdot d}\equiv n\ (\mathrm {mod} \ p)$     以及     $n^{e\cdot d}\equiv n\ (\mathrm {mod} \ q)$

這意味著（因為 p 和 q 是不同的質數）

$n^{e\cdot d}\equiv n\ (\mathrm {mod} \ pq)$

簽名訊息

RSA 也可以用於簽名訊息。假設 Alice 希望向 Bob 傳送簽名訊息。她生成訊息的雜湊值，用她的私鑰加密它，並將它作為“簽名”附加到訊息中。該簽名只能用她的公鑰解密。當 Bob 收到簽名訊息時，他用 Alice 的公鑰解密簽名，並將生成的雜湊值與訊息的實際雜湊值進行比較。如果兩者一致，他知道訊息的作者擁有 Alice 的私鑰，並且訊息自簽名後未被篡改。

安全

假設竊聽者 Eve 攔截了公鑰 N 和 e，以及密文 c。但是，她無法直接獲得 Alice 保密的 d。Eve 從 c 中推斷出 n 的最明顯方法是將 N 分解成 p 和 q，以便計算 (p-1)(q-1)，從而從 e 中確定 d。目前尚未發現經典計算機上用於分解大整數的多項式時間方法，但也沒有證明不存在此類方法。有關此問題的討論，請參見整數分解。

尚未證明分解 N 是從 c 推斷出 n 的唯一方法，但尚未發現更簡單的方法（至少公開知識中沒有）。

因此，通常假定如果 N 足夠大，Eve 就會在實踐中失敗。

如果 N 為 256 位或更短，可以使用現有的免費軟體在個人計算機上用幾小時時間分解。如果 N 為 512 位或更短，截至 1999 年，它可以被數百臺計算機分解。目前建議 N 的長度至少為 1024 位。

1993 年，Peter Shor 證明了量子計算機原則上可以以多項式時間執行分解。如果（或當）量子計算機成為一種實用技術時，Shor 演算法將使 RSA 及其相關演算法過時。

如果發現高效的經典分解程式碼或構建了實用的量子計算機，則使用更大的金鑰長度可以提供一種權宜措施。但是，RSA 中的任何此類安全漏洞顯然是追溯性的。竊聽者可以記錄公鑰和使用該公鑰生成的任何密文（只需記錄到該公鑰所有者的流量即可輕鬆找到），然後只需等待此類突破。然後將該密文解密為明文訊息。因此，使用 RSA 或任何具有類似漏洞的密碼交換長期秘密從本質上講是不安全的。

實際考慮因素

金鑰生成

找到大的素數 p 和 q 通常是透過使用機率素性測試對正確大小的隨機數進行測試來完成的，這種測試可以快速排除大多數非素數。如果這種測試發現了一個“可能的素數”，那麼應該使用確定性測試來驗證該數確實是素數。

p 和 q 不應該“太接近”，以免費馬分解對 N 成功。此外，如果 p-1 或 q-1 只有小的素數因子，則 N 可以快速分解，因此應丟棄這些 p 或 q 值。

不應採用任何向攻擊者提供有關素數資訊的素數搜尋方法。特別是，需要使用一個良好的隨機數生成器作為起始值。請注意，這裡要求既是“隨機”又是“不可預測”。這些不是相同的標準；一個數字可能是透過隨機過程選擇的（即結果沒有模式），但如果它以任何方式（甚至部分可預測）是可預測的，則使用的方法將導致安全性的喪失。例如，蘭德公司在 1950 年代出版的隨機數表可能非常隨機，但它已經出版，因此也可以作為攻擊者的工具。如果攻擊者可以猜出 p 或 q 的一半數字，他們可以快速計算出另一半（由 Coppersmith 在 1997 年證明）。

金鑰 d 必須足夠大。Wiener 在 1990 年證明，如果 p 在 q 和 2q 之間（這是相當典型的）並且 d < N^1/4/3，那麼 d 可以從 N 和 e 中有效地計算出來。加密金鑰 e = 2 也不應該使用。

速度

RSA 比 DES 和其他對稱密碼系統慢得多。在實踐中，Bob 通常會使用對稱演算法加密秘密訊息，使用 RSA 加密（相對較短的）對稱金鑰，並將 RSA 加密的對稱金鑰和對稱加密的訊息都傳輸給 Alice。

此過程引發了額外的安全問題。例如，使用強大的隨機數生成器生成對稱金鑰至關重要，因為否則 Eve 可以透過猜測對稱金鑰來繞過 RSA。

金鑰分發

與所有密碼一樣，RSA 公鑰的分發方式很重要。金鑰分發必須確保防範中間人攻擊。假設 Eve 能夠以某種方式向 Bob 提供任意金鑰，並讓他相信這些金鑰屬於 Alice。假設 Eve 還能夠攔截 Alice 和 Bob 之間的傳輸。Eve 向 Bob 傳送她自己的公鑰，Bob 認為這是 Alice 的公鑰。然後，Eve 可以攔截 Bob 傳送的任何密文，使用她自己的私鑰解密，保留訊息副本，使用 Alice 的公鑰加密訊息，並將新的密文傳送給 Alice。原則上，Alice 和 Bob 都無法檢測到 Eve 的存在。針對此類攻擊的防禦措施通常基於數字證書或公鑰基礎設施的其他元件。

計時攻擊

Kocher 在 1995 年描述了一種巧妙的、出乎意料的針對 RSA 的新攻擊：如果攻擊者 Eve 知道 Alice 的硬體並且能夠測量多個已知密文的解密時間，她可以快速推斷出解密金鑰 d。為了阻止這種攻擊，解密程式碼應以恆定時間解密。這被稱為RSA 盲化。

自適應選擇密文攻擊

1998 年，Daniel Bleichenbacher 描述了第一次針對使用 PKCS #1 v1 冗餘函式的 RSA 加密訊息的實用自適應選擇密文攻擊（冗餘函式向 RSA 加密訊息新增結構，因此可以確定解密的訊息是否有效）。由於 PKCS #1 方案存在缺陷，Bleichenbacher 能夠對安全套接字層協議的 RSA 實現發起實際攻擊，並可能洩露會話金鑰。由於這項工作，密碼學家現在建議使用可證明安全的冗餘檢查，例如最佳非對稱加密填充，RSA 實驗室釋出了不受這些攻擊影響的 PKCS #1 新版本。