為什么RSA 公鑰指數(shù)(e=65537)

 引言

學(xué)術(shù)界普遍認(rèn)為絕對不能選用e=3作為RSA公鑰指數(shù)，就好像說我們再也不能用md5一樣。但實際上，md5今天仍然廣泛使用。一個密碼算法在理論上被攻破，并不等于實踐中就一定會有安全風(fēng)險。比如，md5作為一種密碼哈希函數(shù)，理論上它必須滿足三個性質(zhì)：(1) 輸出的均勻分布性；(2) 抗碰撞攻擊；(3) 抗原像攻擊。當(dāng)王小云發(fā)現(xiàn)了md5不滿足性質(zhì)(2)之后，理論上md5算法就被攻破——md5將從“密碼哈希函數(shù)”的家族中退出。盡管如此，我們的軟件系統(tǒng)中若使用了md5，就真的不安全了嗎？非也！因為實踐中的md5主要用于計算登錄密碼的摘要、數(shù)字簽名摘要，這些都只是依賴于md5的性質(zhì)(3)，只要仍然滿足抗原像攻擊，md5的實踐安全性就不會受到影響。

對于RSA算法，由于大多數(shù)軟件系統(tǒng)都可能基于openssl來開發(fā)，而openssl的低級版本一般會將e=3作為默認(rèn)的RSA公鑰指數(shù)。選取小公鑰指數(shù)主要是為了提高加密或簽名驗證的性能，比如選e=3只需要2次模乘(ModMul)，而隨機選擇的e(假設(shè)n是1024-bit)則大概需要1000次模乘。正因為如此，選用小公鑰指數(shù)的RSA在簽名驗證和加密操作上要比ECC算法(ANSI X9.62)高效得多。

那么，選用e=3對PKCS#1的安全性有多大影響呢？在實現(xiàn)RSA算法時，只要不局限于自己對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]。

攻擊場景：如果Alice打算將消息M加密發(fā)送給一組用戶，并且這組用戶選擇的公鑰指數(shù)e=3，那么攻擊者Malice可以通過截獲3個密文

便能夠有效地恢復(fù)出明文M。Hastad進一步指出，即使Alice在加密M之前對M進行了f運算（這里f是一個公開的多項式函數(shù)），攻擊者仍然能有效地恢復(fù)出明文M。所以建議在進行消息填充時一定要選擇隨機化填充方法，比如OAEP[2]，而不是一個確定的填充方法。

影響：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是一個已知的多項式。那么攻擊者Malice可以截獲密文

便能夠有效地恢復(fù)出明文M。所以建議明文在加密前一定要做隨機化處理。

影響：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，即在消息尾部或頭部直接填充隨機串。如果攻擊者截獲到Alice發(fā)送給Bob的關(guān)于消息M的兩個不同的密文，即

如果填充的隨機串r的長度低于消息長度的1/9，那么攻擊者便能夠有效地恢復(fù)出明文M。注意該攻擊對e = 65537無效。

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

[ 補充說明 ] Coppersmith在密碼分析領(lǐng)域做了很多杰出的工作，比如Coppersmith定理[4]已經(jīng)成為一個密碼分析工作的奠基石。

Coppersmith定理 ：令N為大整數(shù)，f是度為e的多項式。給定N和f，可以有效地計算出方程f(x)=0 mod N所有小于N^(1/e)的解。

應(yīng)用該定理，另一個簡單的攻擊如下：當(dāng)e=3時，給定一個密文，如果攻擊者已知2/3的明文比特，則能恢復(fù)出整個明文。

(4) BDF攻擊

BDF攻擊[5]是針對私鑰d在部分暴露之后的攻擊。

攻擊結(jié)論：令(N, d)為私鑰，N的長度為n-bit。假若d的n/4個低位比特信息被泄露，那么在e < sqrt(N)條件下，攻擊者可以有效地恢復(fù)出私鑰d。

另外值得一提的是，如果e = 3，我們很容易知道d的取值范圍，而且這個取值范圍的區(qū)間為sqrt(N)量級。這也就是說，如果e = 3，RSA就天然地泄露了d的一半比特位信息，只不過泄露的是高位比特，而不是低位比特。但是目前還沒有發(fā)現(xiàn)針對d的高位比特泄露的有效攻擊。

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

(5) 其它攻擊

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

3. 結(jié)論

(I) 對于RSA加密來說，如果在實現(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) 曾強調(diào)“不允許使用比65537更低的公鑰指數(shù)e”，但PKCS#1卻從未有過類似的建議。e=65537=(2^16+1)，其簽名/加密運算只需要17次模乘，性能也算不錯。但我認(rèn)為選這個值的目的只是一個介于小指數(shù)攻擊和運算效率之間的一個折中考慮，即以防萬一將來有一天"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