> 1) The largest key thus cracked is perhaps one third that
> size. Factoring is an *exponential problem* in the size of the
> number being factored. Cracking a 1024 bit key right now would
> require far more compute power than is conceivably available.
I'll expand on each of those three sentences.
The largest PGP key known to have been broken was the 384-bit BlackNet
key which I and 3 colleagues finished almost two years ago. The largest
RSA key broken was RSA-129, 426 bits, which we finished three years ago.
State of the art is probably 512 bits. IMO, it's only that the
principal players in this game are busy with other things that a 512-bit
effort isn't underway now.
The best factoring algorithms are *not* exponential in the bit length of
the integer. They are subexponential. They are, however,
superpolynomial. The growth rate of the best known, the number field
sieve, is exp((1.9 + O(1)) (log N)^1/3 (log log N) 2^3)) and so, in some
sense, is two thirds the way towards being polynomial from exponential.
With current hardware and algorithms available to the open world, I
estimate that 512-bit factorizations are straightforward to a project
similar in magnitude to the current DES and 56-bit RC4 challenges.
768-bit keys might be vulnerable to an effort similar in magnitude to
the Manhattan or Apollo projects. 1024 is *right* out.
Paul