選擇哪個是公鑰和私鑰
當我計算兩個 RSA 密鑰時，如果有的話，我稱之為公共密鑰與我稱之為私有密鑰的區別會怎樣？
在任何 RSA 類型的密碼系統中，公鑰都必須有一個模數 $ n $ , 有時有一個指數 $ e $ 如果密碼系統沒有規定。像 RSA-KEM 這樣的合理密碼系統可以規定 $ e = 3 $ ，但一些有缺陷的標準，基於 RSAES-PKCS1-v1_5 等錯誤，可能需要 $ e $ 成為 $ e = 65537 $ 或更大，並且可能允許 $ e $ 改變。
私鑰可以有以下幾種形式中的任何一種：
- 因素 $ p $ 和 $ q $ 的 $ n = pq $
- 私人指數 $ d $ , 這解決了 $ e \cdot d \equiv 1 \pmod{\lambda(n)} $
- 中國剩餘定理指數 $ d_p \equiv d \pmod{p - 1} $ 和 $ d_q \equiv d \pmod{q - 1}) $
任何這些形式的私鑰都是等價的，只要知道 $ n $ ： 從 $ p $ 和 $ q $ 你可以計算 $ \lambda(n) = \operatorname{lcm}(p - 1, q - 1) $ 並解決 $ e d \equiv 1 \pmod{\lambda(n)} $ 使用擴展歐幾里得算法；從 $ d $ 你可以恢復多個 $ e \cdot d - 1 $ 的 $ \lambda(n) $ 並且沒有太多額外的困難繼續考慮因素 $ n $ ; 等等。 通常，例如在OpenSSL 中，私鑰的許多冗餘部分儲存在一起以加快計算速度。
那麼，主要問題是：公共指數 $ e $ 和私人指數 $ d $ 可互換？ 答案是：沒有**。**
在Rivest、Shamir 和 Adleman 的開創性論文中，提出的方法是選擇 $ d $ 隨機互質 $ \phi(n) = (p - 1)(q - 1) $ 然後推導出 $ e $ 從 $ d $ 通過解決 $ ed \equiv 1 \pmod{\phi(n)} $ . 可以反過來做：選擇 $ e $ 隨機互質 $ \phi(n) $ ，然後推導出 $ d $ 從 $ e $ 通過解決 $ ed \equiv 1 \pmod{\phi(n)} $ . 所以，如果你被困在 1978 年，看起來這兩個指數的角色是可以互換的——但如果你被困在 1978 年，你的加密方案也很容易被破解，*所以也許你不想留在1978 年。
RSA 使用者的主要成本是計算模冪，對於指數 $ x $ 費用 $ \lfloor\log_2 x\rfloor $ 平方和 $ H(x) - 1 $ 乘法，其中 $ H $ 是漢明權重。最有效的指數是 3，但您只能對公共指數執行此操作！如果你總是選擇私人指數 $ d = 3 $ ，你仍然需要發布 $ e $ 為了讓任何人都可以加密消息——但如果你這樣做了，那麼就掌握了以下知識 $ e $ 和 $ d $ 我能找到 $ \lambda(n) $ 和因素 $ n $ 並破解整個密碼系統！
“好吧，好吧，”你說，“所以 $ d = 3 $ 不好，但如果我只是選擇 $ d $ 小來加速解密？碰巧，如果 $ d $ 僅小於約 $ \sqrt[4] n $ ，我可以使用維納的攻擊或其變種來恢復它！因此，私人指數至關重要 $ d $ 在整個可能的空間中幾乎均勻分佈，即使您選擇公共指數也是如此 $ e $ 總是像 3 或 65537 這樣的小東西。
因此，雖然在明智的 RSA 類型密碼系統中始終使用它是完全安全的 $ e = 3 $ ，即使選擇適度小也是危險的 $ d $ ; 指數是非常不可互換的。**
PS 你可能會被方程的誘人對稱性所吸引 $ c = m^e \bmod n $ 和 $ m = c^d \bmod n $ , 將加密和簽名也視為可互換的。不要這樣做！這是一個陷阱！如果你試圖將資訊硬塞到這種形狀中，你最終可能會在腳上開槍。加密和簽名還有更多內容，除了使用求冪之外，它們幾乎沒有相似之處——如果你天真地嘗試將兩者與相同的密鑰結合起來，你可能也會把自己放在另一隻腳上。到那時，你最好希望自己是一隻章魚。
*他們推薦了有效的 RSA-ECB 進行加密，以及一種可輕鬆偽造的無雜湊簽名方案。現代標準的第一個安全簽名方案——假設參數適當縮放——直到一年後由拉賓在 1979 年發布，使用質量不同的指數 $ e = 2 $ ，而第一個現代標準的安全加密方案直到此後一段時間才發布。
理論上，RSA 密鑰是對稱的。這意味著您使用哪一個作為私鑰或公鑰並不重要。然而，在實踐中，有一些微妙的限制打破了這種對稱性。
首先，您通常希望您的公鑰相對較小。這樣，加密操作就不會花費太多時間來執行（儘管不要選擇太小的公鑰，因為這樣攻擊者可能能夠解密消息）。
另一方面，私鑰需要很大。如果私鑰小於 $ \frac{1}{3}n^{\frac{1}{4}} $ （和 $ n $ 作為 RSA 密鑰的模數），那麼攻擊者可以執行非常快速的攻擊并快速恢復私鑰。
因此，您必須以不同的方式處理私鑰和公鑰。但是，如果加密的效率無關緊要並且您選擇使用大於 $ \frac{1}{3}n^{\frac{1}{4}} $ 對於私鑰和公鑰，您可以發布其中一個並將另一個保密，您仍然將擁有一個安全且有效的 RSA 密碼系統。