How to calculate the time it'll take to crack RSA or DH?

Question

Sometimes the easiest way to describe security of a type of cryptography is to say that "the time it takes to solve for an x-bit key would be y years". How would one go about doing such a calculation for RSA, DH, and ElGamal. In other words, given x, how to solve for y?

_{If this fits better on Math.SE, please move it there}

Answer 1

There is an asymptotic formula for the General Number Field Sieve for factoring big integers. This is the most efficient known algorithm for breaking RSA keys which are longer than 400 bits or so (since the current world record is 768 bits, a 400-bit RSA key is quite weak). For discrete logarithm (to break DH), the best known algorithm is also known as "number field sieve" and it is much similar to the one for factorization. In particular, it has the same asymptotic complexity.

However, asymptotic formulas do not capture all the information you want:

• An asymptotic formula describes the behaviour of the function which gives the computation time depending on the size of the input, for large enough inputs. It says that "when the input size grows toward infinity, the complexity grows in a way similar to this formula". But that's still an approximation and nothing guarantees that an actual RSA key you are trying to break is large enough for the asymptotic formula to be reasonably accurate. For instance, Multi-Polynomial Quadratic Sieve is asymptotically slower than GNFS; but it is in practice faster than GNFS for 300-bit integers. This means that 300-bit integers are not large enough for asymptotic formulas to accurately rate factorization algorithms against each other.

• Even when the formula is accurate, it has an implicit multiplicative constant in front (which you can name "number of operations per second" if you wish). So the formula must be calibrated with an actual experiment. Speaking of which, even though GNFS for factorization and NFS for discrete logarithm share the same asymptotic behaviour, they do not have the same "constant" so, in practice, a 600-bit DH key seems to be substantially harder to break than a 600-bit RSA key (indeed, the current world record for discrete logarithm is "only" 530 bits).

• Time complexity formulas talk only about operations, but do not describe space requirements. In GNFS for large numbers, the storage space can become tremendous, especially for the last part of the algorithm (the "linear algebra") which is a conceptually simple operation (Gauss reduction) on a matrix of humungous size; in practice, that step is constrained by the RAM size and speed, and also how fast you can move the data around in a cluster. CPU is not the bottleneck, and the time complexity formula talks only about the CPU.

• The whole process is not streamlined. There are several steps in the algorithm (polynomial selection, sieving, linear algebra) and although there is good opensource code for that, it still requires some thinking by smart people at some crucial moments. To beat the world record in factorization, you need horsepower but also computer scientists who know the ins and outs of GNFS, and there are maybe a hundred of those worldwide.

So the practical way of estimating the breaking time for a RSA or DH key is to extrapolate from the published integer factorization records and discrete logarithm records.

There has been quite a lot of work on such "extrapolation", in particular in the search for "equivalences" between symmetric and asymmetric key lengths (as in: "a 1024-bit RSA key is roughly as robust as a 160-bit hash function"). See this site for a comprehensive summary of the resulting recommendations emitted by various organizations (with online calculators and many pointers). Given the points I evoke above, it is not surprising that the published recommendations do not really match each other...

The synthetic advice which is often given in 2011 is: "use 2048-bit RSA/DH/DSA keys, and you will be fine for a looong time."

Answer 2

These assertions always come with some assumptions, either spelled out or implicit.

In the case of most public-key algorithms, deriving the private key from the public key is best be done by solving some mathematical problem (as far as known now).

• For RSA, the fastest known way to break is factorizing the modulus (which should be a product of two large primes).
• For DSA, Diffie-Hellman and both ElGamals (signature, encryption), the fastest known way to break is solving a discrete logarithm problem.

So we then make assumptions like these:

• There will not be found a faster way of breaking the scheme than solving the corresponding problem.
• There will not be found algorithms to solve these problems that are much faster than what we know now.
• The computational power of a potential adversary will not go up much more than Moore's law allows. (There are alternate, more conservative calculations which reason about some minimum energy usage for each basic calculation, and set a limit like "converting Jupiter's mass to energy" or such.)

With these, we can simply calculate how long breaking the key will take (on average).