Let’s Talk About Keysizes in RSA
I was talking with a lead from a security team the other day, and they said that their company was using 2K RSA keys. I asked, “But, why 2K?”. “I don’t know!”, was the answer. “No one has asked me that before. Maybe it’s 256 bits. I can’t remember.” To me, this is a bit like an electrician saying that they didn’t quite know if the red wire was live, or if it was the blue wire.
40 quadrillion years
RSA has been around for over 40 years, and it is still going strong. In fact, it is providing the identity of most of the Web sites that we connect to — and using RSA signatures, which are proven with the public key of the site. At the core of the difficulty of RSA is the factorization of a public modulus into the two prime numbers that create it. Just after it was created, Martin Gardner wrote that to find the 63-digit prime factors for a 126–digit would take 40 quadrillion years:
Contrast this with the difficulty of finding the two prime factors of a 125- or 126-digit number obtained by multiplying two 63-digit primes. If the best algorithm known and the fastest of today’s computers were used, Rivest estimates that the running time required would be about 40 quadrillion years’
In fact, in 1991, Arjen Lenstra et al cracked a 100-digit (330-bit) version of the public modulus [here]. And then the 40…
