D. J. Bernstein
Integer factorization
Circuits for integer factorization

Background: RSA and the number field sieve

The RSA public-key cryptosystem and the RSA public-key signature system are widely used to protect Internet communications against eavesdropping and forgery.

The speed and security of RSA depend on the size of the public keys used in RSA. For example, using 1024-bit keys takes somewhat longer than using 512-bit keys, but 1024-bit keys appear to provide much more protection against attackers.

For the sake of speed, users typically select the smallest key sizes that seem to provide adequate protection. Consequently it is important to understand exactly how much protection is provided by small key sizes.

Anyone who can factor 512-bit integers, i.e., discover the prime numbers that divide a given 512-bit integer, can break 512-bit RSA. Anyone who can factor 1024-bit integers can break 1024-bit RSA. All the other known ways to break RSA (when RSA is used properly) are more difficult than factorization.

The number field sieve (NFS) is the fastest known method to factor integers larger than about 300 bits. A team led by Herman te Riele used NFS on conventional computers to factor a difficult 512-bit integer in 1999. Bahr, Franke, and Kleinjung used NFS on conventional computers to factor a difficult 524-bit integer in 2002.