引言
现有的大部分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却从未有过类似的建议。
(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
[7] http://www.rsa.com/rsalabs/node.asp?id=2216
相关推荐
(去掉注释13.6kb)微信小程序RSA加密模块,用法请参考文件里面的注释。 //加载RSA模块 var RSA = require('rsa.js'); var rsa_res = new RSA.RSAKey(); //配置公钥证书 let public_n = ''; let public_e = ''; ...
计算机网络安全》(第二版)刘远生 辛一主编的P177题目: 6.在RSA算法中,取密钥e=3,d=7,则明文4的密文是()。 A.28 B.29 C.30 D.31 C语言源代码
linux下从公钥指数(Exponent)和模数(Modulus)得到RSA公钥和pem公钥文件,完整C代码,可直接编译验证。 在网上找了好久都没有合适的,自己做了一个完整的demo。
C#通过 n、e和d(模数、公钥指数和私钥指数)三个参数来RSA加解密及签名和验签。如果只是公钥解密和验证签名,那么可以不需要知道私钥指数(D),这在某些时候对方传过来N和E来解密和验签的时候非常管用(验证签名的...
有时候和其他系统对接的时候,对方发送的公钥指数、私钥指数和模数等参数,C#这边可以用这3个参数来实现加解密,即实现了从这三个参数得到密钥对,然后用密钥对去做加解密。如果只有公钥指数和模数,那么就可实现...
linux下C语言从N(模数)、E(公钥指数)、D(私钥指数)得到了RSA结构体,可以进行RSA加密解密,也可以进行签名和验证签名(本代码没做这个,有RSA结构体这个很简单了)。完整源代码,可编译和测试。
asp.net RSA 私钥加密公钥解密 能解 php Java 实现RSA加密互通 ,PKCS#8 格式的的密钥文件 ,公钥解密 依赖于BouncyCastle.Crypto.dll
应用场景用于当你使用的是.net技术需要调用对方的接口时,但对方使用的是java语言时需要把对方提供的RSA私钥或者RSA公钥进行转换成.net格式进行使用。否则可能会出现解密失败的情况出现,相反就是你是java技术需要...
【delphiRSA加解密】支持RSA公钥加密私钥解密,RSA私钥加密公钥解密,秘钥格式支持PKCS8和PKCS1,D7~XE10可用
利用System.Numerics.BigInteger实现,私钥加密,公钥解密。兼容PKCS1填充方式。有效文件只有MyRSA.cs一个,其它文件是因为带了一个演示窗口。
RSA公钥加密RSA公钥加密
基于.net的RSA私钥加密 公钥解密的源码--201903
可以直接运行成功的RSA加密解密示例 JAVA端采用公钥加密,服务端C#采用私钥解密。
Java实现,公钥私钥通过计算生产,没有调用API,可以更直观的理解RSA公钥私钥的生成 资源中包含源码、jar包。不管是不想造轮子还是想要学习的同学都适用 也可以根据需要改造代码
公钥密码学与RSA公钥密码学与RSA公钥密码学与RSA公钥密码学与RSA公钥密码学与RSA公钥密码学与RSA
.net的RSA私钥加密 公钥解密的源码.net的RSA私钥加密 公钥解密的源码.net的RSA私钥加密 公钥解密的源码
RSA算法是第一个能同时... RSA的安全性依赖于大整数的因式分解问题, 只要其钥匙的长度足够长,用RSA加密的信息实际上是不能被解破的。但在分布式计算技术和量子计算机理论日趋成熟的今天,RSA加密安全性受到了挑战。
C# .net 使用Java公钥实现RSA加密
用于私钥加密 公钥解密用于私钥加密 公钥解密用于私钥加密 公钥解密
iOS RSA 加密根据公钥文件加密