Skip navigation

DSpace

機構典藏 DSpace 系統致力於保存各式數位資料(如:文字、圖片、PDF)並使其易於取用。

點此認識 DSpace
DSpace logo
English
中文
  • 瀏覽論文
    • 校院系所
    • 出版年
    • 作者
    • 標題
    • 關鍵字
  • 搜尋 TDR
  • 授權 Q&A
    • 我的頁面
    • 接受 E-mail 通知
    • 編輯個人資料
  1. NTU Theses and Dissertations Repository
  2. 理學院
  3. 數學系
請用此 Handle URI 來引用此文件: http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/77312
完整後設資料紀錄
DC 欄位值語言
dc.contributor.advisor陳君明zh_TW
dc.contributor.advisorJiun-Ming Chenen
dc.contributor.author黃政凱zh_TW
dc.contributor.authorCheng-Kai Huangen
dc.date.accessioned2021-07-10T21:55:23Z-
dc.date.available2024-08-13-
dc.date.copyright2019-08-14-
dc.date.issued2019-
dc.date.submitted2002-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.urihttp://tdr.lib.ntu.edu.tw/jspui/handle/123456789/77312-
dc.description.abstractDon Coppersmith於1980年代推導出可以求得滿足單變數同餘方程式的較小的解之演算法,此演算法包含LLL演算法的應用。[1] Coppersmith的演算法可用於攻擊RSA密碼系統所生成的安全性較弱的密鑰,且過去至少有兩個已知的案例。
於2013年,臺灣自然人憑證所生成的部分質數因具有一定的規律而被破解。在現實的應用中,是第一個能成功利用Coppersmith方法破解的RSA密碼系統。[8]
於2017年,一組捷克的密碼研究團隊揭露一家德國的半導體廠商所生產的特定晶片中的加密函式庫(以下稱作RSALib)生成安全性較弱的密鑰,由RSALib生成的密鑰可能被攻擊者利用Coppersmith方法破解。由於RSALib生成的RSA質數不夠隨機,因此讓攻擊者獲得一些有利於攻擊這些質數的線索。[9]
在這篇論文中,我們將研究第二則案例 [9] 的攻擊方法,也會介紹由SageMath實作出來的完整攻擊。[10]
zh_TW
dc.description.abstractIn 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.provenanceMade 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.isoen-
dc.titleCoppersmith方法的分析與實作zh_TW
dc.titleAnalysis and Implementation of Coppersmith Methoden
dc.typeThesis-
dc.date.schoolyear107-2-
dc.description.degree碩士-
dc.contributor.oralexamcommittee陳君朋;楊柏因;謝致仁;陳榮傑zh_TW
dc.contributor.oralexamcommittee;;;en
dc.subject.keywordCoppersmith 方法,已知高位元攻擊,ROCA,RSA,因數分解,zh_TW
dc.subject.keywordCoppersmith method,High bits known attack,ROCA,RSA,factorization,en
dc.relation.page26-
dc.identifier.doi10.6342/NTU201902628-
dc.rights.note未授權-
dc.date.accepted2019-08-06-
dc.contributor.author-college理學院-
dc.contributor.author-dept數學系-
顯示於系所單位:數學系

文件中的檔案:
檔案 大小格式 
ntu-107-2.pdf
  目前未授權公開取用
1.28 MBAdobe PDF
顯示文件簡單紀錄


系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。

社群連結
聯絡資訊
10617臺北市大安區羅斯福路四段1號
No.1 Sec.4, Roosevelt Rd., Taipei, Taiwan, R.O.C. 106
Tel: (02)33662353
Email: ntuetds@ntu.edu.tw
意見箱
相關連結
館藏目錄
國內圖書館整合查詢 MetaCat
臺大學術典藏 NTU Scholars
臺大圖書館數位典藏館
本站聲明
© NTU Library All Rights Reserved