Breaking Weak 1024-bit RSA Keys with CUDA
Breaking Weak 1024-bit RSA Keys with CUDA
复制标题
使用 CUDA 破解弱 1024 位 RSA 密钥
DOI：
10.1109/pdcat.2012.58
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Christopher Lupo
中科院分区：
文献类型：
--
作者：
Kerry Scharfglass;Darrin Weng;Joseph White;Christopher Lupo
最近发现了一个涉及RSA模的最大公约数（GCD）的漏洞[1]。本文提出了一个工具，可以有效地和完整地比较大量的1024位RSA公钥，并确定任何容易受到这个弱点的密钥。NVIDIA的图形处理单元（GPU）和CUDA并行编程模型是可用于加速此工具的强大工具。我们使用CUDA的方法与顺序CPU实现相比具有27.5的测量性能加速比，使其成为比较大型密钥集的更实用的方法。一个计算，用于找到200，000个键之间的GCD，即，在113分钟内完成了大约200亿次比较，相当于每秒大约290万次1024位GCD比较。
An exploit involving the greatest common divisor (GCD) of RSA moduli was recently discovered [1]. This paper presents a tool that can efficiently and completely compare a large number of 1024-bit RSA public keys, and identify any keys that are susceptible to this weakness. NVIDIA's graphics processing units (GPU) and the CUDA massively-parallel programming model are powerful tools that can be used to accelerate this tool. Our method using CUDA has a measured performance speedup of 27.5 compared to a sequential CPU implementation, making it a more practical method to compare large sets of keys. A computation for finding GCDs between 200,000 keys, i.e., approximately 20 billion comparisons, was completed in 113 minutes, the equivalent of approximately 2.9 million 1024-bit GCD comparisons per second.