安全機構和標準拒絕什麼e=3和=3e=3在 RSA 中，何時以及有什麼理由？
在 RSA 中，一些安全機構和/或標准允許公共指數 $ e=3 $ , 其他人要求或推薦 $ e>2^{16} $ （或者可能是其他一些最小值）。我收集了以下內容：
- PKCS#1允許 $ e=3 $ 對於 RSA 數字簽名和加密（但請參見下面的 3.）。
- ISO/IEC 9796-2允許 $ e=3 $ （在 RSA 數字簽名的上下文中）。
- FIPS 186-4 B.3.1 節要求 $ e>2^{16} $ （在 RSA 數字簽名的上下文中）；沒有給出任何理由。
- ANSSI 的 RGS 1.0 附件 B1（法國官方建議）第 2.2.1.1 節要求 $ e>2^{16} $ 用於加密並推薦用於 RSA 的每個應用程序。基本原理提到了對 RSA 加密方案的現有攻擊，其指數非常小，但未具體說明。
我在詢問其他標準和權威機構的狀態，以及他們給出或存在的禁止低公共指數的任何理由，包括在實施攻擊的背景下（例如側通道攻擊）。
最終，我想了解使用 RSA 的條件 $ e=3 $ 安全，並儘可能不與官方安全建議或至少與他們的理由相衝突。那是因為我正在考慮使用 $ e=3 $ 對於一些 RSA 數字簽名方案，以及基於隨機挑戰的 RSA 加密的身份驗證。在此類應用中， $ e=2^{16}+1 $ 會使驗證者的工作慢八倍 $ e=3 $ .
我不使用低公共指數的原因列表，特別是 $ e=3 $ , 已成長為：
- 沒有填充的 RSA容易受到非模組化 $ e^{th} $ 根攻擊，對於輸入大小的一些限制，這是低的一個問題 $ e $ 只要。
- RSA 加密在向 $ e $ 收件人對每個收件人使用相同的填充。為此（以及下文 3. 中對攻擊的溫和介紹），請參閱 Dan Boneh 的RSA Cryptosystem 的二十年攻擊，第 4 節。注意：@CodesInChaos 的精彩評論解釋瞭如何使用接收者的公鑰而不是隨機性修復多收件人漏洞；然而，語義安全仍然需要一些隨機性，就像在任何公鑰加密方案中一樣。
- 少於約 $ n/e^2 $ 隨機填充位（其中 $ n $ 是公共模數 N) 的位長，RSA 加密是易受攻擊的；請參閱 Don Coppersmith 的多項式方程小解和低指數 RSA 漏洞。Coron、Joye、Naccache 和 Paillier在 PKCS#1 v1.5 加密的新攻擊中在實際案例中擴展了這個界限，假設明文的合適部分全為零。PKCS#1v2.2現在警告在將 RSAES-PKCS1-V1_5 與低公共指數結合使用時要防範這些攻擊，並建議不要使用此方案來加密任意明文（與隨機密鑰相反，它可能表現出啟用新密鑰的特性）攻擊，對任何公共指數的威脅程度較小）。
- 一些有問題的 RSA 簽名填充方案在指數較低的情況下會更糟。一個例子是INCITS/ISO/IEC 9796:1991數字簽名標準（也在《應用密碼學手冊》的第 11.3.5 節中），該標准在受到攻擊後被撤銷：填充方案被證明對 $ e=3 $ 比 $ e=2^{16}+1 $ （從單個選定消息的簽名中偽造 $ e=3 $ ，而不是一個盛大的三個選擇的消息 $ e=2^{16}+1 $ ).
- （最新更新）Desmedt 和 Odlyzko 在A selected text attack on the RSA cryptosystem and some distinct logarithm scheme 中介紹了基於對填充不良消息進行分解的一般攻擊，可能（我還沒有下定決心）稍微容易一些對於低公共指數 $ e $ ，特別是當應用於對某些 ad-hoc 簽名方案（如 ISO/IEC 9796-2 方案 1）的選擇消息攻擊時，就像在此攻擊中一樣（因為限制步驟是選擇稀疏向量的非平凡線性組合總和為零，向量的元素在 $ \mathbb Z_e $ ).
- （更新）一些基於私鑰部分資訊的實現攻擊（例如，通過冷啟動攻擊近似提取 DRAM 內容）報告成本隨著 $ e $ ; 例如 Heninger 和 Shacham 的Reconstructing RSA Private Keys from Random Key Bits，也許還有 Constantinos Patsakis 的RSA private key rebuild from random bits using SAT solvers。
除了對實現的攻擊之外，到目前為止，我還沒有發現低 RSA 公共指數啟用的攻擊：
- 在一個加密方案中產生一個本質上隨機的元素 $ \mathbb Z_N $ 到公共指數，就像在裸 RSA 中一樣，消息是隨機的，大約是公共模數的大小；RSAES-PKCS1-v1_5 加密任意大小的隨機明文時；以及帶有任何明文的 RSAES-PSS；
- 在具有其他完全完整填充的簽名方案中，包括那些遵循全域雜湊原則隨機化的簽名方案（給出與底層 RSA 問題等價的有力論據 $ e=3 $ )，如PKCS#1v2的RSASSA-PSS，以及ISO/IEC 9796-2方案2和3（2002版引入，2010版未修改；方案1，也稱為ISO/IEC 9796-2:1997 ，沒有這樣的證據）。
避免的建議 $ e=3 $ 主要歸結為迷信、歷史慣性和普遍謹慎，而不是任何有堅實技術基礎的東西。
從歷史上看，一些早期的方案使用 $ e=3 $ 受到攻擊。當時，很多人得出的結論是，這意味著 $ e=3 $ 是不安全的。然而，我們現在知道這個結論是錯誤的。我們現在知道真正的問題是未能使用安全填充方案。
只要您使用安全的填充方案，使用 $ e=3 $ 非常安全。因此，請使用任何備受推崇的可證明安全的填充方案，並且 $ e=3 $ 很好。
事實上，沒有真正的理由需要使用 $ e=3 $ ， 任何一個。如果您想從驗證操作中擠出最後一點可能的性能，那麼 RSA 有一些非常安全的變體可以有效地使用 $ e=2 $ . 您必須對該方案進行一些細微的調整（以說明以下事實： $ \gcd(e,\varphi(n))\ne 1 $ )，但已經解決瞭如何做到這一點。如果您想盡可能快地進行驗證，Dan Bernstein 有幾篇論文展示瞭如何通過使用各種技巧來做到這一點：一個技巧是使用 $ e=2 $ ; 另一個技巧是檢查驗證條件（即， $ s^2=H(m) $ ) 以一個小的秘密素數為模。有關詳細資訊，請參閱他的論文。