# 臺灣博碩士論文加值系統

(44.201.99.222) 您好！臺灣時間：2022/12/05 23:06

:::

### 詳目顯示

:

• 被引用: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 11.1 Our Contribution 2Chapter 2 Preliminary 42.1 Public Key Cryptosystem 42.2 RSA Cryptosystem 52.2.1 Background Knowledge of RSA 62.2.2 RSA Algorithm 72.2.3 Security Consideration of RSA 102.3 Continued Fractions 112.4 The Wiener Attack 122.5 Verheul and Tilborg's Extension of the Wiener Attack 15Chapter 3 The Proposed Approach (EPF) to Estimate the Prime-Factors of N = pq 213.1 How to Estimate p + q? 213.2 Estimated Prime-Factors of N (EPFs of N) 373.3 The Accuracy of EPFs of N 38Chapter 4 Another Look on Verheul and Tilborg's Extension and Its Improvement 394.1 Improvement of the Wiener Attack 394.2 Applying EPF to the Proposed Extension of the Wiener Attack 414.3 Better Result Compared with Verheul and Tilborg's Extension 42Chapter 5 Conclusion 45References 46Appendix 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.
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 1 顏清洋︰〈蒲松齡的忠孝觀〉(國立臺灣體專學報第五期，1994年6月) 2 李福清︰〈《聊齋志異》在俄國─阿列克謝耶夫與《聊齋志異》的翻譯和研究〉(漢學研究通訊總80期，2001年11月) 3 歐宗智︰〈《聊齋．瑞雲》的主題特色〉，(中國語文第564期，2004年6月)

 1 已知區塊長度下之猛禽碼加速之研究 2 行動隨意網路下抵擋路由攻擊之防禦機制 3 電子商務中個人資訊利用與隱私保護探討 4 完全頂點覆蓋問題之計算複雜度 5 鑲嵌於單階晶格的多邊形之展開演算法 6 霧計算和智能網關實現的用法 - 基於管理需求方的博弈智能電網框架 7 通過社交網絡及情感分析探討員工關係 8 運用介面呼叫圖分析開發Android應用程式自動化操作劇本產生系統 9 Android設備上的追蹤好友位置的設計與實現 10 無監督學習：使用聚類算法檢測P2P殭屍網路流量 11 使用非監督式機器學習之僵屍網路偵測 12 辨識商品合法性之NFC晶片驗證機制 13 Android應用程序安全漏洞之動態檢測系統 14 Risk Assessment and User Attention on Android Permissions 15 Android設備之多來源Wi-Fi Display模型設計與實作

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室