為什么RSA 公鑰指數(shù)(e=65537)
加入技術(shù)交流群
引言
學(xué)術(shù)界普遍認(rèn)為絕對不能選用e=3作為RSA公鑰指數(shù)，就好像說我們再也不能用md5一樣。但實(shí)際上，md5今天仍然廣泛使用。一個(gè)密碼算法在理論上被攻破，并不等于實(shí)踐中就一定會有安全風(fēng)險(xiǎn)。比如，md5作為一種密碼哈希函數(shù)，理論上它必須滿足三個(gè)性質(zhì)：(1) 輸出的均勻分布性；(2) 抗碰撞攻擊；(3) 抗原像攻擊。當(dāng)王小云發(fā)現(xiàn)了md5不滿足性質(zhì)(2)之后，理論上md5算法就被攻破——md5將從“密碼哈希函數(shù)”的家族中退出。盡管如此，我們的軟件系統(tǒng)中若使用了md5，就真的不安全了嗎？非也！因?yàn)閷?shí)踐中的md5主要用于計(jì)算登錄密碼的摘要、數(shù)字簽名摘要，這些都只是依賴于md5的性質(zhì)(3)，只要仍然滿足抗原像攻擊，md5的實(shí)踐安全性就不會受到影響。
對于RSA算法，由于大多數(shù)軟件系統(tǒng)都可能基于openssl來開發(fā)，而openssl的低級版本一般會將e=3作為默認(rèn)的RSA公鑰指數(shù)。選取小公鑰指數(shù)主要是為了提高加密或簽名驗(yàn)證的性能，比如選e=3只需要2次模乘(ModMul)，而隨機(jī)選擇的e(假設(shè)n是1024-bit)則大概需要1000次模乘。正因?yàn)槿绱耍x用小公鑰指數(shù)的RSA在簽名驗(yàn)證和加密操作上要比ECC算法(ANSI X9.62)高效得多。
那么，選用e=3對PKCS#1的安全性有多大影響呢？在實(shí)現(xiàn)RSA算法時(shí)，只要不局限于自己對RSA的教科書式理解，比如遵循了PKCS#1 v2.1/v1.5 (2002/1993)或IEEE P1363的建議，或者使用公開的密碼算法庫（如OpenSSL），那么你幾乎可以放心使用e=3。我所得結(jié)論是來自于我對RSA誕生以來學(xué)術(shù)界及業(yè)界針對小公鑰指數(shù)(e=3)的安全性分析。
2. e=3的安全性分析
(1) Hastad攻擊
Hastad描述的攻擊經(jīng)常也被稱為廣播攻擊[1]。
便能夠有效地恢復(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]。
便能夠有效地恢復(fù)出明文M。所以建議明文在加密前一定要做隨機(jī)化處理。
影響：PKCS#1 v2.1和v1.5均不受此攻擊的影響。
(3) Coppersmith攻擊
首先我們介紹Coppersmith發(fā)現(xiàn)的短填充攻擊[4]。
如果填充的隨機(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)量級。這也就是說，如果e = 3，RSA就天然地泄露了d的一半比特位信息，只不過泄露的是高位比特，而不是低位比特。但是目前還沒有發(fā)現(xiàn)針對d的高位比特泄露的有效攻擊。
影響：PKCS#1 v2.1和v1.5均不受此攻擊的影響。
(5) 其它攻擊
關(guān)于RSA的其它相關(guān)攻擊，如小私鑰指數(shù)攻擊、共模攻擊、盲化攻擊、時(shí)間攻擊等，請參見[6, 7].
3. 結(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ù)，只要使用正確，目前仍然是安全的。
附1: 關(guān)于e=65537 (0x10001) 的說明
NIST SP800-78 Rev 1 (2007) 曾強(qiáng)調(diào)“不允許使用比65537更低的公鑰指數(shù)e”，但PKCS#1卻從未有過類似的建議。e=65537=(2^16+1)，其簽名/加密運(yùn)算只需要17次模乘，性能也算不錯。但我認(rèn)為選這個(gè)值的目的只是一個(gè)介于小指數(shù)攻擊和運(yùn)算效率之間的一個(gè)折中考慮，即以防萬一將來有一天"e=3"被攻破而僥幸"e=65537"可能還是安全的。
參考文獻(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
*博客內(nèi)容為網(wǎng)友個(gè)人發(fā)布，僅代表博主個(gè)人觀點(diǎn)，如有侵權(quán)請聯(lián)系工作人員刪除。
