为什么{3,17,65537}中没有使用PuTTYgen创建的RSA公共指数（e）？

#1 楼

答案在源文件sshrsag.c中的第9行：


#define RSA_EXPONENT 37 /* we like this prime */


此值$ e = 37 $符合条件对于合理的固定RSA公共指数：


$ e $是奇数，
$ e $至少是$ 3 $，
$ e $很小。

后一种情况


对于涉及公钥（加密和签名验证）的操作速度是有利的；
使其更难选择

$ e = 37 $是质数，简化了对公共模数的素因数的选择，从而简化了$ d $的取值范围。 $ N $，如后面的注释中所述：


生成$ p $和$ q $：素数与组合长度“位”成素数，与模数$ e $的$ 1 $不等价。 （严格来说，我们希望$（p-1）$和$ e $是互质的，而$（q-1）$和$ e $是互质的，但总的来说，安排起来比较麻烦。选择一个素元$ e $，我们可以简化判据。）


$ e = 37 = 2 ^ 5 + 2 ^ 2 + 1 $与$ e = 17相比唯一的缺点= 2 ^ 4 + 1 $或$ e = 3 = 2 ^ 1 + 1 $是将模数$ N $提高到第37次幂需要7个模乘，而第17个为5，第3个为2。

我们可以推测作者喜欢$ e = 37 $，因为它不是特殊形式，费马素数$ F_k = 2 ^ {（2 ^ k）} + 1 $和$ 0 \ le也是如此k \ le4 $，通常用作RSA公共指数。在较大与允许有效的公共密钥操作之间进行折衷可能不是考虑的一部分：较大的$ e = 41 = 2 ^ 5 + 2 ^ 3 + 1 $还仅需要7个模乘（作为奖励，更接近答案）。


该答案的其余部分报告了我对PuTTY 0.66的RSA代码的不完全审查，其目的是与相对较小的$ e = 37 $相关的弱点。我还没有确定生成的密钥是否由PuTTY（的那个版本）使用，并且所有其他依赖于相应公共密钥的实体都可以正确地使用它。否则，我不能排除某些系统具有的漏洞，相比于多个安全机构要求的最低值的传统$ e = 65537 $，使用PuTTY的$ e = 37 $可以更容易地利用这些漏洞。我特别考虑的是PKCS＃1 V1.5类型01签名的不正确验证，这比比皆是；请参阅基于实现错误的丹尼尔·布雷兴巴赫（Daniel Bleichenbacher）的RSA签名伪造（Crypto 2006臀部会议的Hal Finney存档的帐户）； UlrichKühn，Andrei Pyshkin，Erik Tews，Ralf-Philipp Weinmann Bleichenbacher对PKCS＃1 RSA签名的低指数攻击的变体；丹尼尔·布雷兴巴赫（Daniel Bleichenbacher）针对基于RSA加密标准PKCS＃1的协议对协议进行的选择密文攻击认为，对于填充类型02的PKCS＃1 V1.5，解密的脆弱（即使是一致的）实现也很容易（
）。在Crypto 2008会议记录中）。

当使用RSA且填充良好时（如PKCS＃1 V2中的RSASSA-PSS和RSAES-OAEP），使用小$ e $没有已知的弱点。 PuTTY中支持的其他RSA填充包括较小的PKCS＃1 V1.5填充，但是我没有找到可怕的填充类型00，它本质上是没有填充的，不安全的，对于小$ e $来说甚至更不安全。 PuTTY可以使用PKCS＃1 V1.5填充类型01进行签名，如PuTTY所执行的那样，它不存在用于正确验证的已知漏洞。它可以使用PKCS＃1 V1.5填充类型02进行加密，但不能通过可能存在漏洞的填充检查来实现解密。

#2 楼

使得$ \ gcd（e，（p-1）（q-1））= 1 $的任何$ e $都可以。不需要将它放在集合$ \ {3,17,65537 \} $中；选择这些最后一个数字主要是为了提高加密速度（两个设置位可以更快地计算模幂），这些数字恰好是质数，因此可以轻松检查条件。一个经常遇到其他$ e $，但是默认情况下，许多标准软件包都会产生这三个软件包之一。本质上，37美元并不比17美元安全得多。