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