Bernstein's NFS machine

[Nomen Nescio]

James Donald writes:
> On Tue, Feb 26, 2002 at 02:04:16AM -0000, Frog3 wrote:
> > The cost [To factor RSA 1024] is the need to build a 
> > machine that can do 53 billion simultaneous, independent 
> > ECM factorizations for smoothness testing. It's not clear 
> > how amenable this would be to hardware implementation.
> >
> > A time of 2^71 is considerably less threatening than 2^53.
>
> If I understand frog3's numbers correctly:
>
> If one builds extraordinarily massive hardware capable of
> dowing 53 billion simultaneous independent ECM
> factorizations, Bernstein's method wil take 2^71 steps.
>
> Assuming that the massively parallel hardware does fifty
> billion factorizations each microsecond, then it will take 
> Bernstein's super duper hardware about one hundred million
> years to factor an RSA 1024 modulus. 

No, this is not quite right.  The 2^71 is the cost in terms of elementary
operations (add, xor, etc.).  This is based on 2^53 ECM factorizations
per machine times 2^18 operations per factorization.

James' quoted time would be correct if the machine could do 50 billion
*operations* per microsecond (a clock rate of 50,000,000 gigahertz
(50 petahertz), compared to 1-2 gigahertz available today).  This fast
machine would then take 100 million years to break a 1024 bit key.

Even though these are "back of the envelope" calculations which ignore
o(1) terms that could theoretically be negative, the basic principles seem
sound.  The need to do 2^89 tests to get enough relations for a factor base
of 2^36 is based on the known fraction of multi-hundred bit numbers that
are going to be smooth.  This value doesn't have much "wiggle room".  You
could try to use a smaller factor base, but the size of the values to be
tested for smoothness is going to be in the hundreds of bits, and reducing
the factor base will make it even harder to find smooth values.

The 2^18 estimate for the cost of the ECM smoothness test will likewise
be hard to improve on significantly.  In addition, with a factor base of
size 2^36 and testing numbers up to ten times longer, each ECM factorizer
will have to do approximately 10 factorizations before it can determine
smoothness.

Even with the uncertainties, this calculation seems to be strong enough
to say that this machine cannot pose a threat to 1024 bit keys using
near-term technology.  You can assume impossibly large numbers of an
impossibly fast machine, and it still takes an impossibly large time.

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com