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?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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:
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."
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).
So we then make assumptions like these:
With these, we can simply calculate how long breaking the key will take (on average).