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…
Photo by Silas Köhler on Unsplash

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 quadrillion years melted away, when, in 1994, they broke the 129-digit version:

RSA-129 = 114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541
p=3490529510847650949147849619903898133417764638493387843990820577
q=32769132993266709549961988190834461413177642967992942539798288533

And, so where are we with the limits of cracking in RSA? Well, in 2020, Paul Zimmerman et al broke RSA-250 (829 bits) and which required the equivalent of 2,700 CPUs running for one year. The public modulus was:

2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937

and the prime number numbers discovered:

p=64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367
q=33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711

With RSA, once we know p and q, we can easily discover the private key, and then crack the cipher.

So can I now prove that the public modulus is not prime (as made up by two prime numbers), and the other two numbers are primes? Well, we can test using the Miller-Rabin method:

  • Is 6413528947 … 3367 prime (125 digits)? One of the primes for RSA-250, and should be prime. Try
  • Is 333720275949781565 … 062711 prime (125 digits)? One of the primes for RSA-250, and should be prime. Try
  • Is 214032465024074 … 5937497937 prime (250 digits)? This is the public modulus for RSA-250, and should not be prime (as p×q). Try

One way to measure the cost of cracking key sizes is to estimate the amount of energy it takes. For this, Lenstra estimated that it would take the amount of energy to boil the water in a swimming pool to crack a 745-bit RSA modulus, but require you to boil the rain for a 1,130-bit RSA modulus [here]:

Ref: Here

A Bit of History

In August 1977, The Stranglers were in the charts with “Something Better Change” and something really was changing, and it was something that would change the world forever. This was the month that Martin Gardner, in his Scientific American column, posted a challenge of a method that has stood the test of time: RSA.

It related to the work of R(ivest), A(dleman) and S(hamir) and was a puzzle on their discovery of a method which allowed two keys to be created, where one could encrypt, and the other to decrypt. Their work had been based on a proposal from Whitfield Diffie and Martin Hellman on trapdoor functions that could be used to create the key pair.

In order to explain the RSA concept, Martin’s provided a background on the Diffie-Hellman method for which he outlined:

Then in 1975 a new kind of cipher was proposed that radically altered the situation by supplying a new definition of “unbreakable.” a definition that comes from the branch of computer science known as complexity theory. These new ciphers are not absolutely unbreakable in the sense of the one-time pad. but in practice they are unbreakable in a much stronger sense than any cipher previously designed for widespread use. In principle these new ciphers can be broken. but only by computer programs that run for millions of years!

Overall the Diffie-Hellman method has had a good run, but it has struggled in recent years to keep up with the processing power for computers, and the millions of years of running is not quite the case in the modern area, and where the original ciphers could now easily be broken with the simplest of computers within minutes.

With the RSA method, Martin Gardner outlined:

Their work supported by grants from the NSF and the Office of Naval Research. appears in On Digital Signatures and Public-Key Cryptosystems (Technical Memo 82. April. 1977) issued by the Laboratory for Computer Science Massachusetts Institute of Technology 545 Technology Square. Cambridge Mass. 02139.
The memorandum is free to anyone who writes Rivest at the above address enclosing a self-addressed. 9-by-12-inch clasp.

On receipt the requesters eventually (it took over four months in many cases) received a precious piece of history:

It seems unbelievable these days, but the original methods were based on two 63-digital prime numbers that would be multiplied to create a 126-digit value:

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’

A 256-bit number, at its maximum, generates 78-digits [here]:

115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665, 640,564,039,457,584,007,913,129,639,936

The 40 quadrillion years to crack has not quite happened, and where 512-bit keys are easily broken in Cloud. If you are interested, here is a 512-bit integer value and which has 148 digits, such as [example]:

13,407,807,929,942,597,099,574,024,998,205,846,127,479,365,820,5 92,393,377,723,561,443,721,764,030,073,546,976,801,874,298,166,9 03,427,690,031,858,186,486,050,853,753,882,811,946,569,946,433,6 49,006,084,096

The search for prime numbers, too, has been progressive since 1977, and by 2014, the world discovered a 17,425,170-digit prime number. The finding of prime numbers makes the finding of them in the RSA method must easier.

So the RSA method has been under attack for years, from both discovering prime numbers and also in factorizing. Along with this computing power has increased massively. If think that 40 years have passed, and take a quick assumption that computing power doubles every year then we get:

1977 4 Quadrillion Years (4,000,000,000,000,000)
1978 2 Quadrillion Year
1979 1 Quadrillion Year...2015 3,637 years

and if we get an NVIDIA card with 4,000 processors, we take it to less than a year, and we get of few of them today into a cluster, and we crack it within one day! The FREAK vulnerability was actually caused by the limiting of RSA keys, due to US Export controls, to 512-bits [view].

Conclusions

With RSA, we start at 1,024 bits for the public modulus and probably double that to make sure. So, only use 2,048-bit keys, or above!