【转】RSA选用小公钥指数(e=3)真的不安全吗?

引言

现有的大部分RSA算法实现都遵循PKCS#1 v2.1/v1.5 (2002/1993)。根据PKCS#1的建议，公钥指数e是可以选取较小的素数3或65537(=2^16+1)。这样选取主要是为了提高加密或签名验证的性能，因为3或65537分别只需要2或17次模乘运算，而一个随机选择的e(假设n是1024-bit)则大约需要1000次。这种选用小公钥指数的方法使用户相信RSA在签名验证和加密操作方面确实要比“以高效著称的ECC”还要高效很多。

 

然而在选用小公钥指数时，有很多人则更倾向于选e=65537而不是e=3，他们认为3“似乎不安全”，然而又给不出所以然。今天我想说的是，在“正确使用”RSA算法的情况下，至今为止还没有发现公开的攻击方法能有效攻击e=3。那么何为正确使用呢？很简单，如果你不是密码专家，那么实现时请遵守PKCS#1 v2.1或IEEE P1363的建议，而不要局限于自己对RSA的教科书式的理解。或者使用公开的密码算法库，如OpenSSL，这些算法的实现一般都会遵守相关标准或建议。

选择e=3究竟有什么问题？

对于e=3的情形，至今以来，其签名验证或加密的性能优势是任何公钥密码算法都无法超越的。但对其所存在的安全脆弱性，我们应实事求是地进行分析，而不要轻易放弃使用e=3。下面我来梳理一下自从1977年RSA算法诞生以来针对小公钥指数(e=3)的密码分析中值得一提的结论。

 

(1) Hastad攻击

 

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

 

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

C1 = M^3 mod N1, C2 = M^3 mod N2, C3 = M^3 mod N3

便能够有效地恢复出明文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可以截获密文

C1 = M1^3 mod N, C2 = M2^3 mod N

便能够有效地恢复出明文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的两个不同的密文，即

C1 = (0002||r1||M)^3 mod N, C2 = (0002||r2||M)^3 mod N

如果填充的随机串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].

结论

(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的公钥指数，只要使用正确的填充方案，目前仍然是安全的。

关于e=65537的说明

这是一个推荐使用的公钥指数，我认为选这个值的目的只是一个介于低指数攻击和运算效率之间的一个折中考虑，即以防万一"e=3"被攻破而侥幸"e=65537"可能还是安全的。另外，NIST SP800-78 Rev 1 (2007) 也曾强调“不允许使用比65537更低的公钥指数e”，但对于该限制却没有给出任何理由。而PKCS#1却从未有过类似的建议。

参考文献：

[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