Understanding Common Factor Attacks: An RSA-Cracking Puzzle
In February 2012, two groups of researchers revealed that large numbers of RSA encryption keys that are actively used on the Internet can be cracked because the random numbers used to generate these keys were not random enough. Here, I offer a puzzle in which you will identify and crack RSA keys that are vulnerable in the same way — using a slightly simpler version of the same technique. This should provide a clearer understanding of how this problem arises and how it can be exploited, as well as more familiarity with the RSA algorithm and Euclid's algorithm.
This challenge is aimed at novice programmers who want to practice their programming skills with some real-world cryptography, and at anyone who was interested in Lenstra et al. and Heninger et al.'s research but found the math involved daunting or unfamiliar.
I'll start with an explanation about RSA to put these attacks in some context and explain some of the steps involved in solving this challenge. If you're already familiar with the RSA algorithm and with the details of these attacks, you could skip directly to the challenge part.
