http://blog.chinaunix.net/uid-21880738-id-1813145.html

現(xiàn)有的大部分RSA算法實(shí)現(xiàn)都遵循PKCS#1 v2.1/v1.5?(2002/1993)。根據(jù)PKCS#1的建議，公鑰指數(shù)e是可以選取較小的素?cái)?shù)3或65537(=2^16+1)。這樣選取主要是為了提高加密或簽名驗(yàn)證的性能，因?yàn)?或65537分別只需要2或17次模乘運(yùn)算，而一個(gè)隨機(jī)選擇的e(假設(shè)n是1024-bit)則大約需要1000次。這種選用小公鑰指數(shù)的方法使用戶相信RSA在簽名驗(yàn)證和加密操作方面確實(shí)要比“以高效著稱的ECC”還要高效很多。

然而在選用小公鑰指數(shù)時(shí)，有很多人則更傾向于選e=65537而不是e=3，他們認(rèn)為3“似乎不安全”，然而又給不出所以然。今天我想說的是，在“正確使用”RSA算法的情況下，至今為止還沒有發(fā)現(xiàn)公開的攻擊方法能有效攻擊e=3。那么何為正確使用呢？很簡單，如果你不是密碼專家，那么實(shí)現(xiàn)時(shí)請遵守PKCS#1?v2.1或IEEE P1363的建議，而不要局限于自己對RSA的教科書式的理解。或者使用公開的密碼算法庫，如OpenSSL，這些算法的實(shí)現(xiàn)一般都會(huì)遵守相關(guān)標(biāo)準(zhǔn)或建議。
選擇e=3究竟有什么問題？

對于e=3的情形，至今以來，其簽名驗(yàn)證或加密的性能優(yōu)勢是任何公鑰密碼算法都無法超越的。但對其所存在的安全脆弱性，我們應(yīng)實(shí)事求是地進(jìn)行分析，而不要輕易放棄使用e=3。下面我來梳理一下自從1977年RSA算法誕生以來針對小公鑰指數(shù)(e=3)的密碼分析中值得一提的結(jié)論。
(1) Hastad攻擊
Hastad描述的攻擊經(jīng)常也被稱為廣播攻擊[1]。
攻擊場景：如果Alice打算將消息M加密發(fā)送給一組用戶，并且這組用戶選擇的公鑰指數(shù)e=3，那么攻擊者M(jìn)alice可以通過截獲3個(gè)密文 C1 = M^3 mod N1,?C2 = M^3 mod N2,?C3 = M^3 mod N3 便能夠有效地恢復(fù)出明文M。Hastad進(jìn)一步指出，即使Alice在加密M之前對M進(jìn)行了f運(yùn)算（這里f是一個(gè)公開的多項(xiàng)式函數(shù)），攻擊者仍然能有效地恢復(fù)出明文M。所以建議在進(jìn)行消息填充時(shí)一定要選擇隨機(jī)化填充方法，比如OAEP[2]，而不是一個(gè)確定的填充方法。
影響：PKCS#1 v2.1和v1.5均不受此攻擊的影響。
(2) Franklin-Reiter攻擊
Franklin-Reiter攻擊是一種明文相關(guān)性攻擊[3]。
攻擊場景：假設(shè)Bob的公鑰為(3, N)，Alice發(fā)送消息M1和M2給Bob，并且M1 = f(M2) mod N，f是一個(gè)已知的多項(xiàng)式。那么攻擊者Malice可以截獲密文 C1 = M1^3 mod N, C2 = M2^3 mod N 便能夠有效地恢復(fù)出明文M。所以建議明文在加密前一定要做隨機(jī)化處理。
影響：PKCS#1 v2.1和v1.5均不受此攻擊的影響。
(3) Coppersmith攻擊
首先我們介紹Coppersmith發(fā)現(xiàn)的短填充攻擊[4]。
攻擊場景：假設(shè)Bob的公鑰為(3, N)，Alice發(fā)送消息M給Bob。消息M的填充方法是遵循PKCS#1 v1.5，即在消息尾部或頭部直接填充隨機(jī)串。如果攻擊者截獲到Alice發(fā)送給Bob的關(guān)于消息M的兩個(gè)不同的密文，即 C1 = (0002||r1||M)^3 mod N, C2 = (0002||r2||M)^3 mod N 如果填充的隨機(jī)串r的長度低于消息長度的1/9，那么攻擊者便能夠有效地恢復(fù)出明文M。注意該攻擊對e = 65537無效。
影響：PKCS#1 v2.1不受影響，但PKCS#1?v1.5受此攻擊的影響。
[補(bǔ)充說明]?Coppersmith在密碼分析領(lǐng)域做了很多杰出的工作，比如Coppersmith定理[4]已經(jīng)成為一個(gè)密碼分析工作的奠基石。
Coppersmith定理：令N為大整數(shù)，f是度為e的多項(xiàng)式。給定N和f，可以有效地計(jì)算出方程f(x)=0 mod N所有小于N^(1/e)的解。
應(yīng)用該定理，另一個(gè)簡單的攻擊如下：當(dāng)e=3時(shí)，給定一個(gè)密文，如果攻擊者已知2/3的明文比特，則能恢復(fù)出整個(gè)明文。
(4) BDF攻擊
BDF攻擊[5]是針對私鑰d在部分暴露之后的攻擊。
攻擊結(jié)論：令(N, d)為私鑰，N的長度為n-bit。假若d的n/4個(gè)低位比特信息被泄露，那么在e < sqrt(N)條件下，攻擊者可以有效地恢復(fù)出私鑰d。
另外值得一提的是，如果e = 3，我們很容易知道d的取值范圍，而且這個(gè)取值范圍的區(qū)間為sqrt(N)量級(jí)。這也就是說，如果e = 3，RSA就天然地泄露了d的一半比特位信息，只不過泄露的是高位比特，而不是低位比特。但是目前還沒有發(fā)現(xiàn)針對d的高位比特泄露的有效攻擊。
影響：PKCS#1 v2.1和v1.5均不受此攻擊的影響。

(5) 其它攻擊

關(guān)于RSA的其它相關(guān)攻擊，如小私鑰指數(shù)攻擊、共模攻擊、盲化攻擊、時(shí)間攻擊等，請參見[6, 7].

結(jié)論

(I) 對于RSA加密來說，如果在實(shí)現(xiàn)上遵循PKCS#1 v2.1 （OAEP填充），目前還沒有發(fā)現(xiàn)有效的攻擊；但如果是遵循PKCS#1 v1.5 (明文尾部直接填充)，那么存在Coppersmith攻擊。

(II) 對于RSA簽名來說，目前對于PKCS#1 v2.1 (PSS填充)和PKCS#1 v1.5 （填充方法：0001FF...FF00||ASN.1||H(M)）來說都還沒有發(fā)現(xiàn)有效的攻擊。

綜上所述，選用e=3作為RSA的公鑰指數(shù)，只要使用正確的填充方案，目前仍然是安全的。

關(guān)于e=65537的說明

這是一個(gè)推薦使用的公鑰指數(shù)，我認(rèn)為選這個(gè)值的目的只是一個(gè)介于低指數(shù)攻擊和運(yùn)算效率之間的一個(gè)折中考慮，即以防萬一"e=3"被攻破而僥幸"e=65537"可能還是安全的。另外，NIST SP800-78 Rev 1 (2007) 也曾強(qiáng)調(diào)“不允許使用比65537更低的公鑰指數(shù)e”，但對于該限制卻沒有給出任何理由。而PKCS#1卻從未有過類似的建議。

參考文獻(xiàn)：
[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

總結(jié)

以上是生活随笔為你收集整理的RSA选用小公钥指数(e=3)真的不安全吗?的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。