請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/77312
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 陳君明 | zh_TW |
dc.contributor.advisor | Jiun-Ming Chen | en |
dc.contributor.author | 黃政凱 | zh_TW |
dc.contributor.author | Cheng-Kai Huang | en |
dc.date.accessioned | 2021-07-10T21:55:23Z | - |
dc.date.available | 2024-08-13 | - |
dc.date.copyright | 2019-08-14 | - |
dc.date.issued | 2019 | - |
dc.date.submitted | 2002-01-01 | - |
dc.identifier.citation | [1] Arjen Klaas Lenstra, Hendrik Willem Lenstra, and László Lovász. 1982. Factoring polynomials with rational coefficients. Mathematische Annalen 261 (4), pages 515-534.
[2] Don Coppersmith. 1996. Finding a Small Root of a Univariate Modular Equation. In International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, pages 155-165. [3] Nicholas Howgrave-Graham. 2001. Finding Small Roots of Univariate Modular Equations Revisited. In IMA International Conference on Cryptography and Coding. Springer, Berlin, Heidelberg, pages 131-142. [4] Alexander May. 2003. New RSA Vulnerabilities Using Lattice Reduction Methods. PhD Thesis. University of Paderborn. [5] David Wong. 2005. Survey: Lattice Reduction Attacks on RSA. https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/survey_final.pdf [6] Stephen Pohlig, and Martin Hellman. 2006. An Improved Algorithm for Computing Logarithms over GF(p) and Its Cryptographic Significance. IEEE Transactions on Information Theory 24 (1), pages 106-110. [7] Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. 2008. An Introduction to Mathematical Cryptography. New York: springer. [8] Daniel J. Bernstein, Yun-An Chang, Chen-Mou Cheng, Li-Ping Chou, Nadia Heninger, Tanja Lange, and Nicko van Someren. 2013. Factoring RSA keys from certified smart cards: Coppersmith in the wild. In International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, pages 341-360. [9] Matus Nemec, Marek Sys, Petr Svenda, Dusan Klinec, and Vashek Matyas. 2017. The Return of Coppersmith's Attack: Practical Factorization of Widely Used RSA Moduli. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. ACM, pages 1631-1648. [10] William A. Stein, T. Abbott, and M. Abshoff. 2018. Sage Mathematics Software (Version 8.2). The Sage Development Team. http://www.sagemath.org/ | - |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/77312 | - |
dc.description.abstract | Don Coppersmith於1980年代推導出可以求得滿足單變數同餘方程式的較小的解之演算法,此演算法包含LLL演算法的應用。[1] Coppersmith的演算法可用於攻擊RSA密碼系統所生成的安全性較弱的密鑰,且過去至少有兩個已知的案例。
於2013年,臺灣自然人憑證所生成的部分質數因具有一定的規律而被破解。在現實的應用中,是第一個能成功利用Coppersmith方法破解的RSA密碼系統。[8] 於2017年,一組捷克的密碼研究團隊揭露一家德國的半導體廠商所生產的特定晶片中的加密函式庫(以下稱作RSALib)生成安全性較弱的密鑰,由RSALib生成的密鑰可能被攻擊者利用Coppersmith方法破解。由於RSALib生成的RSA質數不夠隨機,因此讓攻擊者獲得一些有利於攻擊這些質數的線索。[9] 在這篇論文中,我們將研究第二則案例 [9] 的攻擊方法,也會介紹由SageMath實作出來的完整攻擊。[10] | zh_TW |
dc.description.abstract | In 1980s, Don Coppersmith derived an algorithm for finding a small root of a univariate modular equation. This algorithm is based on the LLL lattice reduction algorithm. [1] An application of Coppersmith’s algorithm is to attack RSA weak keys. There are two cases that are cracked because of weak implementation on RSA keys.
In 2013, Taiwan Citizen Digital Certificates were cracked since the patterns of RSA secret keys generated by the system were known. This is the first world’s well-known application of Coppersmith attacks to RSA weak keys in the wild. [8] In 2017, a Czech cryptography research group revealed that a German semiconductor manufacturer’s on-chip cryptographic library (further denoted as RSALib) generates weak keys, which could be cracked using Coppersmith method. Since the distribution of RSA primes generated by the RSALib is too far from uniform, it provides a good guess of these primes. [9] In this thesis, we study the algorithms for the attack in [9]. We also introduce an implementation of the attack by programming with SageMath. [10] | en |
dc.description.provenance | Made available in DSpace on 2021-07-10T21:55:23Z (GMT). No. of bitstreams: 1 ntu-108-R04221015-1.pdf: 1313763 bytes, checksum: 3a13463ea8d246ae0dfc9bad87ef640f (MD5) Previous issue date: 2019 | en |
dc.description.tableofcontents | 口試委員會審定書 i
誌謝 ii 摘要 iii Abstract iv 1. Introduction 1 1.1 Overview of this work 1 1.2 Notations 3 2 Preliminary 4 2.1 Coppersmith method 4 2.2 Howgrave-Graham Theorem 5 2.3 High bits known attack 7 2.4 ROCA 8 3 RSA Primes Generated by the RSALib 9 4 Optimization of the Parameter M' 10 4.1 Greedy heuristic 11 4.2 Local brute force search 12 4.3 Results 13 5 Factorization 15 5.1 Factorization algorithm 15 5.2 Parallel computing 17 5.3 Performance 17 6 Implementation 19 7 Conclusions 23 References 24 Appendix 25 | - |
dc.language.iso | en | - |
dc.title | Coppersmith方法的分析與實作 | zh_TW |
dc.title | Analysis and Implementation of Coppersmith Method | en |
dc.type | Thesis | - |
dc.date.schoolyear | 107-2 | - |
dc.description.degree | 碩士 | - |
dc.contributor.oralexamcommittee | 陳君朋;楊柏因;謝致仁;陳榮傑 | zh_TW |
dc.contributor.oralexamcommittee | ;;; | en |
dc.subject.keyword | Coppersmith 方法,已知高位元攻擊,ROCA,RSA,因數分解, | zh_TW |
dc.subject.keyword | Coppersmith method,High bits known attack,ROCA,RSA,factorization, | en |
dc.relation.page | 26 | - |
dc.identifier.doi | 10.6342/NTU201902628 | - |
dc.rights.note | 未授權 | - |
dc.date.accepted | 2019-08-06 | - |
dc.contributor.author-college | 理學院 | - |
dc.contributor.author-dept | 數學系 | - |
顯示於系所單位: | 數學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-107-2.pdf 目前未授權公開取用 | 1.28 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。