Time needed to factor large integers

The optimal choice of factoring algorithm depends on the size of the number you want to factor. For numbers larger than a googol (10¹⁰⁰) the GNFS (general number field sieve) algorithm is the fastest known factoring algorithm, making GNFS the algorithm of choice for trying to factor public keys for RSA encryption

The expected time required to factor a number n using the GNFS is proportional to

exp( f(n) g(n) )

where f(n) is relatively constant andg(n) varies more strongly withn. More specifically

f(n) = (64/9)^1/3 + o(1)

and

g(n) = (log n)^1/3 (log log n)^2/3.

The notationo(1) means a term that goes to zero asn increases. Very often in practice you can ignore o(1) terms when your value of n is large. In cryptographic applications n is certainly large, at least 2¹⁰²⁴, and yet the o(1) term is still significant for values ofn seen in practice. I've seen one source say that for keys used in practice theo(1) term is around 0.27.

Security levels

It is widely stated that factoring a 1024-bit private key is comparable in difficulty to breaking an 80-bit symmetric encryption key, i.e. that 1024-bit keys provide 80-bit security.

To find the security level of a 1024-bit RSA key, the size of the o(1) term matters. But given this, if we want to find the security level of more RSA key sizes, it doesn't matter how big the o(1) term is. It only that the term is roughly constant over the range of key sizes we are interested in.

Iff(n) is relatively constant, then the log of the time to factorn is proportional tog(n), and the log of the time to break an encryption with security levelk is proportional tok. So the security level of a keyn should be proportional tog(n). Let's see if that's the case, using the reported security levels of various key sizes.

import numpy as np# RSA key sizes and security levelsdata = { 1024 : 80, 2048 : 112, 3072 : 128, 4096 : 140, 7680 : 192,}for d in data: x = d*np.log(2) # natural log of 2^d y = x**(1/3)*(np.log(x)**(2/3)) print(data[d]/y)

This prints the following:

2.55802.65842.55962.48192.6237

So the ratio is fairly constant, as expected. All the reported security levels are multiples of 4, which suggests there was some rounding done before reporting them. This would account for some of the variation above.

The output above suggests that the security level of an RSA key with b bits is roughly

2.55 x^1/3 log(x)^2/3

where x = log(2) b.

Aside on RSA security

RSA encryption is not broken by factoring keys but by exploiting implementation flaws.

Factoring a 2048-bit RSA key would require more energy than the world produces in a year, as explained here.

The post Time needed to factor large integers first appeared on John D. Cook.