Breaking weak 1024-bit RSA keys with CUDA

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.