引言

学术界普遍认为绝对不能选用e=3作为RSA公钥指数，就好像说我们再也不能用md5一样。但实际上，md5今天仍然广泛使用。一个密码算法在理论上被攻破，并不等于实践中就一定会有安全风险。比如，md5作为一种密码哈希函数，理论上它必须满足三个性质：(1) 输出的均匀分布性；(2) 抗碰撞攻击；(3) 抗原像攻击。当王小云发现了md5不满足性质(2)之后，理论上md5算法就被攻破——md5将从“密码哈希函数”的家族中退出。尽管如此，我们的软件系统中若使用了md5，就真的不安全了吗？非也！因为实践中的md5主要用于计算登录密码的摘要、数字签名摘要，这些都只是依赖于md5的性质(3)，只要仍然满足抗原像攻击，md5的实践安全性就不会受到影响。

对于RSA算法，由于大多数软件系统都可能基于openssl来开发，而openssl的低级版本一般会将e=3作为默认的RSA公钥指数。选取小公钥指数主要是为了提高加密或签名验证的性能，比如选e=3只需要2次模乘(ModMul)，而随机选择的e(假设n是1024-bit)则大概需要1000次模乘。正因为如此，选用小公钥指数的RSA在签名验证和加密操作上要比ECC算法(ANSI X9.62)高效得多。

那么，选用e=3对PKCS#1的安全性有多大影响呢？在实现RSA算法时，只要不局限于自己对RSA的教科书式理解，比如遵循了PKCS#1 v2.1/v1.5 (2002/1993)或IEEE P1363的建议，或者使用公开的密码算法库（如OpenSSL），那么你几乎可以放心使用e=3。我所得结论是来自于我对RSA诞生以来学术界及业界针对小公钥指数(e=3)的安全性分析。

2. e=3的安全性分析

(1) Hastad攻击

Hastad描述的攻击经常也被称为广播攻击[1]。

攻击场景：如果Alice打算将消息M加密发送给一组用户，并且这组用户选择的公钥指数e=3，那么攻击者Malice可以通过截获3个密文

便能够有效地恢复出明文M。Hastad进一步指出，即使Alice在加密M之前对M进行了f运算（这里f是一个公开的多项式函数），攻击者仍然能有效地恢复出明文M。所以建议在进行消息填充时一定要选择随机化填充方法，比如OAEP[2]，而不是一个确定的填充方法。

影响：PKCS#1 v2.1和v1.5均不受此攻击的影响。

(2) Franklin-Reiter攻击

Franklin-Reiter攻击是一种明文相关性攻击[3]。

攻击场景：假设Bob的公钥为(3, N)，Alice发送消息M1和M2给Bob，并且M1 = f(M2) mod N，f是一个已知的多项式。那么攻击者Malice可以截获密文

便能够有效地恢复出明文M。所以建议明文在加密前一定要做随机化处理。

影响：PKCS#1 v2.1和v1.5均不受此攻击的影响。

(3) Coppersmith攻击

首先我们介绍Coppersmith发现的短填充攻击[4]。

攻击场景：假设Bob的公钥为(3, N)，Alice发送消息M给Bob。消息M的填充方法是遵循PKCS#1 v1.5，即在消息尾部或头部直接填充随机串。如果攻击者截获到Alice发送给Bob的关于消息M的两个不同的密文，即

如果填充的随机串r的长度低于消息长度的1/9，那么攻击者便能够有效地恢复出明文M。注意该攻击对e = 65537无效。

影响：PKCS#1 v2.1不受影响，但PKCS#1 v1.5受此攻击的影响。

[ 补充说明 ] Coppersmith在密码分析领域做了很多杰出的工作，比如Coppersmith定理[4]已经成为一个密码分析工作的奠基石。

Coppersmith定理 ：令N为大整数，f是度为e的多项式。给定N和f，可以有效地计算出方程f(x)=0 mod N所有小于N^(1/e)的解。

应用该定理，另一个简单的攻击如下：当e=3时，给定一个密文，如果攻击者已知2/3的明文比特，则能恢复出整个明文。

(4) BDF攻击

BDF攻击[5]是针对私钥d在部分暴露之后的攻击。

攻击结论：令(N, d)为私钥，N的长度为n-bit。假若d的n/4个低位比特信息被泄露，那么在e < sqrt(N)条件下，攻击者可以有效地恢复出私钥d。

另外值得一提的是，如果e = 3，我们很容易知道d的取值范围，而且这个取值范围的区间为sqrt(N)量级。这也就是说，如果e = 3，RSA就天然地泄露了d的一半比特位信息，只不过泄露的是高位比特，而不是低位比特。但是目前还没有发现针对d的高位比特泄露的有效攻击。

影响：PKCS#1 v2.1和v1.5均不受此攻击的影响。

(5) 其它攻击

关于RSA的其它相关攻击，如小私钥指数攻击、共模攻击、盲化攻击、时间攻击等，请参见[6, 7].

3. 结论

(I) 对于RSA加密来说，如果在实现上遵循PKCS#1 v2.1 （OAEP填充），目前还没有发现有效的攻击；但如果是遵循PKCS#1 v1.5 (明文尾部直接填充)，那么存在Coppersmith攻击。

(II) 对于RSA签名来说，目前对于PKCS#1 v2.1 (PSS填充)和PKCS#1 v1.5 (填充方法：0001FF...FF00||ASN.1||H(M)) 来说都还没有发现有效的攻击。

综上所述，选用e=3作为RSA的公钥指数，只要使用正确，目前仍然是安全的。

附1: 关于e=65537 (0x10001) 的说明

NIST SP800-78 Rev 1 (2007) 曾强调“不允许使用比65537更低的公钥指数e”，但PKCS#1却从未有过类似的建议。e=65537=(2^16+1)，其签名/加密运算只需要17次模乘，性能也算不错。但我认为选这个值的目的只是一个介于小指数攻击和运算效率之间的一个折中考虑，即以防万一将来有一天"e=3"被攻破而侥幸"e=65537"可能还是安全的。

参考文献
 
[1] J. Hastad, Solving simultaneous modular equations of low degree. SIAM J. of Computing, 17: 336-341, 1988
[2] M. Bellare and P. Rogaway. Optimal asymmetric encryption. In EUROCRYPT'94, LNCS 950, pp 92-111, 1994.
[3] M. Franklin and M. Reiter, Low-exponent RSA with related messages. In EUROCRYPT'96, LNCS 1070, pp 1-9, 1996.
[4] D. Coppersmith. Small solutions to polynomial equations, and low exponent RSA vulnerabilities. Journal of Cryptology, 10: 233-260, 1997.
[5] D. Boneh, G. Durfee, and Y. Frankel. An attack on RSA given a fraction of the private key bits. In AsiaCrypt'98, LNCS 1514, pp 25-34, 1998
[6] D. Boneh, Twenty years of attacks on the RSA cryptosystem, 1999.
[7] http://www.rsa.com/rsalabs/node.asp?id=2216

*博客内容为网友个人发布，仅代表博主个人观点，如有侵权请联系工作人员删除。