Coppersmith方法的分析與實作

Abstract

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]