Bugtraq
mailing list archives
Re: PGP Distributed Attack
From: pcl () FOO OUCS OX AC UK (Paul C Leyland)
Date: Tue, 15 Apr 1997 09:33:58 +0100
Perry wrote:
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 384bit BlackNet
key which I and 3 colleagues finished almost two years ago. The largest
RSA key broken was RSA129, 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 512bit
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 512bit factorizations are straightforward to a project
similar in magnitude to the current DES and 56bit RC4 challenges.
768bit keys might be vulnerable to an effort similar in magnitude to
the Manhattan or Apollo projects. 1024 is *right* out.
Paul
By Date
By Thread
Current thread:
 Re: [ANNOUNCE]: ipfilter for FreeBSD2.2.x + FreeBSD3.0current, (continued)
