high performance computing on graphics processing units: hgpu.org

Modern-day computer security relies heavily on cryptography as a means to protect the data that we have become increasingly reliant on. As the Internet becomes more ubiquitous, methods of security must be better than ever. Validation tools can be leveraged to help increase our confidence and accountability for methods we employ to secure our systems. Security validation, however, can be difficult and time-consuming. As our computational ability increases, calculations that were once considered "hard" due to length of computation, can now be done in minutes. We are constantly increasing the size of our keys and attempting to make computations harder to protect our information. This increase in "cracking" difficulty often has the unfortunate side-effect of making validation equally as difficult. We can leverage massive-parallelism and the computational power that is granted by today’s commodity hardware such as GPUs to make checks that would otherwise be impossible to perform, attainable. Our work presents a practical tool for validating RSA keys for poor prime numbers: a fundamental problem that has led to significant security holes, despite the RSA algorithm’s mathematical soundness. Our tool, PARIS, leverages NVIDIA’s CUDA framework to perform a complete set of greatest common divisor calculations between all keys in a provided set. Our implementation offers a 27.5 times speedup using a GTX 480 and 33.9 times speedup using a Tesla K20Xm: both compared to a reference sequential implementation for sets of less than 200000 keys. This level of speedup brings this validation into the realm of practicality due to decreased runtime.