藉由估計RSA模數的質因數來延伸Wiener Attack

An Extension of the Wiener Attack via Estimating the Prime-Factors of RSA Modulus

陳宣同(Chiuan-Tung Chen)

指導教授 ： 孫宏民

國立清華大學/電機資訊學院/資訊系統與應用研究所/碩士(2007年)

摘要

在RSA系統中，一個平衡模數N代表是由兩個大質數p和q相乘而來的，其中q < p < 2q。由於對一個大的整數做因數分解是一件相當困難的事情，所以我們通常借用sqrt(N)來當作p和q的估計值。而在Wiener attack 中，為了提高私密金鑰d的安全界線，Weger採用了2*sqrt(N)當作p + q的估計值。在本論文裡，我們提出了一種新的方法去估計N的質因數，稱之為 EPF。在N = pq用pE和qE來分別表示p和q的估計值。用pE + qE來取代2*sqrt(N)的話，可更準確的估計p + q的值。此外，我們將證明Verheul 和Tilborg對於Wiener attack的延伸可以轉換為暴力搜尋p + q的MSBs。而和他們的研究結果做比較的話，EPF在於徹底搜尋所需花費的計算能力，將可由2r + 8位元下降到 2r - 2 位元，其中r的值是取決於模數N和私密金鑰d之間的關係。Verheul和 Tilborg所提出的私密金鑰d的安全邊界將可再擴大5位元。

關鍵字

RSA ； 連分數 ； Wiener攻擊

並列摘要

In the RSA system, balanced modulus N denotes a product of two large prime numbers p and q, where q < p < 2q. Since Integer-Factorization is difficult, p and q are simply estimated as sqrt(N). In the Wiener attack, 2*sqrt(N) is adopted to be the estimation of p + q in order to raise the security boundary of private-exponent d. This work proposes a novel approach, called EPF, to determine the appropriate prime-factors of N. The estimated values are called “EPFs of N”, and are denoted as pE and qE. Thus pE and qE can be adopted to estimate p + q more accurately than by simply adopting 2*sqrt(N). In addition, we show that the Verheul and Tilborg’s extension of the Wiener attack can be considered to be brute-guessing for the MSBs of p + q. Comparing with their work, EPF can extend the Wiener attack to reduce the cost of exhaustive-searching for 2r + 8 bits down to 2r - 2 bits, where r depends on N and the private key d. The security boundary of private-exponent d can be raised 5 bits again over Verheul and Tilborg’s result.

並列關鍵字

RSA ； Continued Fractions ； Wiener Attack

參考文獻

[1] R. Rivest, A. Shamir, and L. Aldeman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems," Communications of the ACM, vol. 21, no. 2, pp. 120-126, 1978.

[2] H.-M. Sun and C.-T. Yang, "RSA with Balanced Short Exponents and Its Application to Entity Authentication," Proceeding of Public Key Cryptography 05 - PKC’05, LNCS 3386, Springer-Verlag, pp. 199-215, 2005.

[6] G. Durfee and P. Q. Nguyen, "Cryptanalysis of the RSA Schemes with Short Secret Exponent form Asiacrypt '99," Proceedings of Cryptology - ASIACRYPT'00, LNCS 1976, Springer-Verlag, pp. 1-11, 2000.

[8] M. J. Wiener, "Cryptanalysis of RSA with short secret-exponents," IEEE Trans. on Information Theory, vol. 36, pp. 553-558, 1990.

[9] H.-S. Hong, H.-K. Lee, H.-S. Lee, and H.-J. Lee, "The better bound of private key in RSA with unbalanced primes," Applied Mathematics and Computation, vol. 139, pp. 351-362, 2003.