跳到主要內容

臺灣博碩士論文加值系統

(44.201.99.222) 您好!臺灣時間:2022/12/05 23:06
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:陳宣同
研究生(外文):Chiuan-Tung Chen
論文名稱:藉由估計RSA模數的質因數來延伸WienerAttack
論文名稱(外文):An Extension of the Wiener Attack via Estimating the Prime-Factors of RSA Modulus
指導教授:孫宏民
指導教授(外文):Hung-Min Sun
學位類別:碩士
校院名稱:國立清華大學
系所名稱:資訊系統與應用研究所
學門:電算機學門
學類:系統設計學類
論文種類:學術論文
論文出版年:2007
畢業學年度:95
語文別:英文
論文頁數:50
中文關鍵詞:RSA連分數Wiener攻擊
外文關鍵詞:RSAContinued FractionsWiener Attack
相關次數:
  • 被引用被引用:0
  • 點閱點閱:128
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在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位元。
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.
Chapter 1 Introduction 1
1.1 Our Contribution 2
Chapter 2 Preliminary 4
2.1 Public Key Cryptosystem 4
2.2 RSA Cryptosystem 5
2.2.1 Background Knowledge of RSA 6
2.2.2 RSA Algorithm 7
2.2.3 Security Consideration of RSA 10
2.3 Continued Fractions 11
2.4 The Wiener Attack 12
2.5 Verheul and Tilborg's Extension of the Wiener Attack 15
Chapter 3 The Proposed Approach (EPF) to Estimate the Prime-Factors of N = pq 21
3.1 How to Estimate p + q? 21
3.2 Estimated Prime-Factors of N (EPFs of N) 37
3.3 The Accuracy of EPFs of N 38
Chapter 4 Another Look on Verheul and Tilborg's Extension and Its Improvement 39
4.1 Improvement of the Wiener Attack 39
4.2 Applying EPF to the Proposed Extension of the Wiener Attack 41
4.3 Better Result Compared with Verheul and Tilborg's Extension 42
Chapter 5 Conclusion 45
References 46
Appendix Example 48
[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.
[3] H.-M. Sun, W.-C. Yang, and C.-S. Laih, "On the Design of RSA with Short secret-exponent," Proceedings of Cryptology - ASIACRYPT'99, LNCS 1716, Springer-Verlag, pp. 150-164, 1999.
[4] D. Boneh and H. Shacham, "Fast Variants of RSA," CryptoBytes, vol. 5, no. 1, pp. 1-9, 2002.
[5] D. Boneh, "Twenty Years Attacks on the RSA Cryptosystem," Notices of the American Mathematical Society, vol. 46, no. 2, pp. 203-213, 1999.
[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.
[7] B. de Weger, "Cryptanalysis of RSA with small prime difference," Applicable Algebra in Engineering, Communication and Computing, vol. 13, pp. 17-28, 2002.
[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.
[10] D. Boneh and G. Durfee, "Cryptanalysis of RSA with private key d less than N0.292," IEEE Trans. on Information Theory, vol. 46, no. 4, pp. 1339-1449, 2000.
[11] E. Verheul and H. v. Tilborg, "Cryptanalysis of less short RSA secret-exponents," Applicable Algebra in Engineering, Communication and Computing, Vol. 8, Springer-Verlag, pp. 425-435, 1997.
[12] W. Diffie and M. E. Hellman, "New Directions in Cryptography," Proceedings of the AFIPS National Computer Conference, June 1976.
[13] W. Diffie and M. E. Hellman, "Multiuser Cryptographic Techniques," IEEE Transactions on Information Theory, November 1976.
[14] P. Ribenboim, The New Book of Prime Number Records: New York: Springer-Verlag, 1996.
[15] D. Boneh and R. Venkatesan, "Breaking RSA may not be equivalent to factoring," Advances in Cryptology-ASIACRYPT '98 (Lecture Notes in Computer Science), vol. 1233, pp. 59-71, 1998.
[16] I. Niven and H. S. Zuckerman, An Introduction to the Theory of Number: John Wiley and Sons Inc, 1991.
[17] D. E. Knuth, The art of computer programming, Seminumerical algorithms. 2 ed. vol. 2, 1981.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top