FactHacks

A typical 1024-bit RSA public key is a product of two secret 512-bit primes. The security of the cryptosystem relies on an attacker being unable to compute the user's secret primes. The attacker can try guessing one of the secret primes and checking whether it divides the user's public key, but this is very unlikely to work: there are more than 2^500 512-bit primes, far beyond the number of atoms in the universe.

Fortunately for the attacker, there are much faster ways to figure out the secret primes. Some of the danger is visible in public announcements of factorization records by academic teams; the largest publicly factored RSA key, announced in 2009, has 768 bits. But what does this mean for the security of 1024-bit RSA?

There are several different reasons that a real-world attacker doesn't have to play by the rules of an academic challenge. Sometimes users have bad random-number generators; sometimes users generate both primes from a single search; sometimes users choose special primes to try to make RSA run faster; sometimes users leak secret bits through side channels; sometimes the attacker has a botnet, or a 65-megawatt data center in Utah or Tianjin.

This talk will assess the real-world threat to RSA-1024, explaining what the best attacks can do and how you can replicate them in your very own home or local GPU farm. Attack algorithms will be presented as Python code snippets and will already be online before the talk.

This is a joint presentation by Daniel J. Bernstein, Nadia Heninger, and Tanja Lange, surveying work by many people.