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加密方案的现有攻击，但未作详细说明。最终，我想了解安全地使用$ e = 3 $并使用RSA的条件，并且要尽可能避免这种情况的存在。不会与官方的安全建议或至少它们的原理发生冲突。
因为我正在考虑将$ e = 3 $用于某些RSA数字签名方案，以及用于基于随机挑战的RSA加密的身份验证。在此类应用中，$ e = 2 ^ {16} + 1 $将使验证者的工作比$ e = 3 $慢八倍。
我不使用低公共指数的原因清单，尤其是$ e = 3 $，已经发展为：
不带填充的RSA容易受到非模块化$ e ^ {th} $根攻击，这对输入大小有一定的限制仅需担心$ e $低。
当使用相同的填充向每个收件人发送相同的消息到$ e $收件人时，RSA加密很容易受到攻击。有关此内容（以及下面的3.中的攻击的简要介绍），请参见Dan Boneh对RSA加密系统的二十年攻击，第4节。注意：@CodesInChaos的一个不错的评论解释了如何使用收件人的公共密钥，而不是随机性。修复多收件人漏洞；但是，语义安全性仍需要某种随机性，就像任何公共密钥加密方案一样。
随机填充的比特数少于$ n / e ^ 2 $（其中$ n $是公共比特长度）模数N），RSA加密易受攻击;请参阅Don Coppersmith的多项式方程式小型解决方案和低指数RSA漏洞。在实际使用案例中，Coron，Joye，Naccache和Paillier在“对PKCS＃1 v1.5加密的新攻击”中扩展了此范围，假设明文的适当部分为全零。现在，当结合使用RSAES-PKCS1-V1_5和低公共指数时，PKCS＃1v2.2警告防止这些攻击，并建议不要使用此方案来加密任意明文（与随机密钥相反，该明文可能表现出启用新密码的特性）。攻击，对于任何公共指数而言，威胁的程度仍要小一些。一个例子是INCITS / ISO / IEC 9796：1991数字签名标准（也在《应用密码学手册》第11.3.5节中），该标准在遭受攻击后被撤消：对于$ e = 3，填充方案变得稍微差一点$比$ e = 2 ^ {16} + 1 $的伪造（针对$ e = 3 $的单个选定消息的签名进行伪造，而针对$ e = 2 ^ {16} + 1 $的三个选定消息的签名伪造） 。
（最新更新）由Desmedt和Odlyzko在“对RSA密码系统的选定文本攻击和一些离散对数方案”中引入的，基于填充不良的消息的分解的一般攻击，也许（我没有想到）稍微容易些适用于较低的公共指数$ e $，尤其是当应用于某些临时签名方案（例如ISO / IEC 9796-2方案1）的选定消息攻击时，例如在这种攻击中（因为限制步骤是选择非平凡的稀疏向量的线性组合总和为零，向量的元素在$ \ mathbb Z_e $中。通过冷启动攻击）报告的费用增加了$ e $；例如Heninger和Shacham的使用随机密钥位重构RSA私钥，也许是Constantinos Patsakis的使用SAT求解器从随机位重构RSA私钥。低RSA公共指数启用攻击：
在加密方案中将$ \ mathbb Z_N $中的本质上随机的元素提高到公共指数，例如在裸RSA中，消息随机且大小约为公共模数加密任意大小的随机明文时为RSAES-PKCS1-v1_5；和具有任何明文的RSAES-PSS；
在签名方案中具有完全不间断的填充，包括那些遵循全域哈希原理随机化的填充（给出了与等价于$ e = 3 $的基本RSA问题等效的强有力论据） ），例如PKCS＃1v2的RSASSA-PSS以及ISO / IEC 9796-2方案2和3（2002年引入，2010年版未修改;方案1，也称为ISO / IEC 9796-2：1997 ，则没有此类证明。）
#1 楼
避免$ e = 3 $的建议主要归因于迷信，历史惯性和一般谨慎，而不是任何具有坚实技术基础的东西。从历史上看，某些早期使用$ e的方案= 3 $受到攻击。当时，许多人得出的结论是，这意味着$ e = 3 $是不安全的。但是，我们现在知道该结论是错误的。现在我们知道真正的问题是无法使用安全的填充方案。
，只要您使用安全的填充方案，使用$ e = 3 $就是绝对安全的。因此，使用任何备受好评的可证明安全的填充方案，$ e = 3 $都可以。如果您想从验证操作中挤出所有可能的性能，那么在RSA上有一些非常安全的变体，可以有效地使用$ e = 2 $。您必须对该方案进行一些细微的调整（以考虑到$ \ gcd（e，\ varphi（n））\ ne 1 $的事实），但是已经解决了该问题。如果您想以最快的速度进行验证，则丹·伯恩斯坦（Dan Bernstein）有几篇论文展示了如何通过使用各种技巧来做到这一点：一种技巧是使用$ e = 2 $；另一种技巧是使用$ e = 2 $。另一个技巧是对验证条件（即$ s ^ 2 = H（m）$）以小秘密素数为模进行检查。有关更多详细信息，请参见他的论文。
评论
$ \ begingroup $
很高兴能毫不犹豫地看到这个声音！这使我更加愿意相信$ e = 3 $的“全域”填充方案（尽管我目前对$ e = 3 $与随机$ e $的RSA问题的理论难度的辩论缺乏了解）。但是，还有实现攻击的问题。也许$ e = 3 $使得加密中的侧信道泄漏更加令人担忧？
$ \ endgroup $
–fgrieu♦
13年5月28日在10:27
$ \ begingroup $
在使用$ e = 2 $时：我喜欢Rabin方案的性能。但是，存在一个非常实际的实际问题：即使是标准化方案（$ e = 2 $的ISO / IEC 9796-2），目前也缺乏对商业安全评估设备（智能卡，HSM）的支持。同样，对此的一般描述是一个远离完全灾难的错误/错误/弱点（搞清楚Jacobi评估揭示了秘密密钥，对填充的攻击也是如此）。和Jacobi评估（对于加密AFAIK的语义安全性是必需的，并且在签署机密材料时也要注意）几乎没有探索其通道泄漏。
$ \ endgroup $
–fgrieu♦
13年5月28日在10:32
$ \ begingroup $
@fgrieu就我个人而言，当我看到对e = 3的一系列局部攻击时，这使我担心将来会出现更广泛的攻击。为什么现在不通过使用较大的指数以最小的成本降低风险？
$ \ endgroup $
–锑
13年5月29日下午6:18
$ \ begingroup $
@Antinomy：我们拥有的“对e = 3的部分攻击”（至少与实现弱点无关的攻击）最好（IMHO）描述为对即席填充方案的攻击，碰巧会得到一些便利乘$ e = 3 $。但是具有安全性参数（或“证明”）的填充方案有一个适用于$ e = 3 $的填充方案，因此，当$ e = 3 $具有其他严重优势（例如是8倍）时，为什么拒绝使用此类方案的$ e = 3 $公钥方面更快？
$ \ endgroup $
–fgrieu♦
13年5月29日在6:22
$ \ begingroup $
@fgrieu：我想知道为什么公钥侧的8倍速差没有被视为显着吗？如果密钥长度受公开密钥操作的时间预算限制，那么性能的8倍增长将是在预算时间内可处理的密钥大小的两倍以上。
$ \ endgroup $
–超级猫
18年5月29日在18:58
#2 楼
我将这个问题作为答案，而不是将一个冗长的问题更长一些。作为该问题中所链接的法国安全建议更新过程的一部分，我建议（2013年6月）放弃对该要求/建议$ e> 2 ^ {16} $使用带有安全证明的填充方案时。合理地拒绝了此请求（6周之内）。于2014年6月获得批准（法文），构成了一般安全性参考RGS V2（法文）附件B1的更新后的规则和建议V2.03（法文）在这方面是相同的[尽管有明显的变化：2048位RSA被认为是到2030年的最佳版本，而不是上一版的2020年。]以下是基本原理，解释并压缩为$ 2 \ over5 $（最初为法语，归因于ANSSI / SDE / ST / LCR密码实验室）：
我可以说一个论点，即对于$ e = 3 $且具有安全证明的填充方案，目前尚无针对RSA的有效攻击。但是，保持一定的安全裕度通常是有用的。密码分析攻击的最新技术，因为这种裕度可以最大程度地减少新的密码分析进展的影响。
尽管RSA-OAEP的“经典”安全证明在假定随机存在的RSA问题的严重性的情况下也可以工作明文，与$ e $的大小无关，最近的文章[KOS10，LOS13]提出了基于“ Phi-Hiding”假设的标准模型中RSA-OAEP的证明。该证明需要足够大的e $，而不能保证低e $。因此，从可证明的安全性的角度来看，大$ e $可以说增加了安全保障。无法解释的参数示例包括数据格式错误，使用不良的RNG或哈希函数（RSA-OAEP的“经典”安全性证明使用随机oracle模型）。
对现有大量文献的回顾表明，低指数更容易受到影响。例如，许多针对RSA PKCS＃1 v1.5 [CFPR96，CNJP00，BCNTV10]的攻击仅适用于较小的$ e $。
建议对加密进行令人满意的区分（其中$ e <2 ^ {16}禁止+ 1 $）和签名（不鼓励使用$ e $），因为：
针对加密方案提出的利用低$ e $的攻击比针对签名方案的提议更多;这可能是因为一般而言，对加密的攻击更容易执行且难以预防。这是因为成功的攻击（例如针对RSA-OAEP）会损害过去消息的长期机密性；而在签名的情况下，有很多应用可以接受相对较短的签名有效性（例如访问控制）；或者，可以通过在攻击变为现实之前让授权机构重新发布签名来提高由过时机制制成的签名的有效性。
[KOS10] Eike Kiltz，Adam O'尼尔·亚当·史密斯（Neill），亚当·史密斯（Adam Smith）：在选择的明文攻击下RSA-OAEP的可实例性，在Crypto 2010诉讼中（全文）。及其应用，在EuroCrypt 2013诉讼中。
[CFPR96] Don Coppersmith，Matthew Franklin，Jacques Patarin，Michael Reiter：低指数RSA及其相关消息，在EuroCrypt 1996诉讼中。
[CNJP00] Jean-SébastienCoron，Marc Joye，David Naccache，Pascal Paillier：PKCS＃1 v1.5加密的新攻击，在EuroCrypt 2000诉讼中进行。 Tibouchi，Damien Vergnaud：在ACNS程序中，关于PKCS＃1 v1.5加密的广播和有效性检查安全性2010（全文）。
评论：我非常赞赏这种理论基础上的平衡论点。在第3点中，我解释了数据格式化中的错误[enFrançais：erreurs de formatage desdonnées]，其中包括错误注入，这确实是$ e = 3 $可以促进对具有可证明安全性的方案（签名或加密）的攻击的区域和随机消息代表。我的观点仍然是，除了故障注入和辅助渠道（定时，功率分析和朋友）之外，这种攻击的出现是非常不现实的。
评论
您无需随机填充即可避免$ e $收件人漏洞。您可以根据收件人的公共密钥来设置填充内容，例如哈希（e || n）。我想您发布的标准之间的差异仅仅是标准委员会对安全性有多保守的问题。像您一样，假设填充正确，我还没有发现针对$ e = 3 $的RSA遭受任何致命的攻击，但是我怀疑要求$ e> 2 ^ {16} $的标准对于实现者可能遇到的所有潜在陷阱感到不安属于$ e = 3 $。
老实说，我认为水平线以下的所有内容都可以很好地回答这个问题。
@Reid：我将考虑将第二部分做成单独的答案/社区Wiki。但这至少还不是令人满意的答案。恐怕我没有相关攻击的完整列表，更普遍地说，是避免使用非常低的公共指数的原因。特别是对于随机论证w.r.t.公共指数低；和实施攻击。还有其他标准和官方建议。
@吉尔斯：您评论中链接的问题不太集中。这也是（而且答案主要是）关于具有较小私有指数的RSA。总之，在一定程度上使用它会带来有价值的速度优势时，这是不安全的。