請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/77312
標題: | Coppersmith方法的分析與實作 Analysis and Implementation of Coppersmith Method |
作者: | 黃政凱 Cheng-Kai Huang |
指導教授: | 陳君明 Jiun-Ming Chen |
關鍵字: | Coppersmith 方法,已知高位元攻擊,ROCA,RSA,因數分解, Coppersmith method,High bits known attack,ROCA,RSA,factorization, |
出版年 : | 2019 |
學位: | 碩士 |
摘要: | Don Coppersmith於1980年代推導出可以求得滿足單變數同餘方程式的較小的解之演算法,此演算法包含LLL演算法的應用。[1] Coppersmith的演算法可用於攻擊RSA密碼系統所生成的安全性較弱的密鑰,且過去至少有兩個已知的案例。
於2013年,臺灣自然人憑證所生成的部分質數因具有一定的規律而被破解。在現實的應用中,是第一個能成功利用Coppersmith方法破解的RSA密碼系統。[8] 於2017年,一組捷克的密碼研究團隊揭露一家德國的半導體廠商所生產的特定晶片中的加密函式庫(以下稱作RSALib)生成安全性較弱的密鑰,由RSALib生成的密鑰可能被攻擊者利用Coppersmith方法破解。由於RSALib生成的RSA質數不夠隨機,因此讓攻擊者獲得一些有利於攻擊這些質數的線索。[9] 在這篇論文中,我們將研究第二則案例 [9] 的攻擊方法,也會介紹由SageMath實作出來的完整攻擊。[10] 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] |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/77312 |
DOI: | 10.6342/NTU201902628 |
全文授權: | 未授權 |
顯示於系所單位: | 數學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-107-2.pdf 目前未授權公開取用 | 1.28 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。