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 [EMAIL PROTECTED]