hzh...@gmail.com wrote: >> And I really don't see how simple enumeration of range(2^2048) breaks >> RSA-2048, since that problem requires you to find two factors which, >> when multiplied together, give that specific value. >> > > I can tell you why is that. RSA-2048 has a composite of length less > than 2^2048, which is a product of two large primes. So one of its > factors cannot exceed 2^2047, and we can treat the multiplication as a > computation with constant complexity. So the time complexity of > enumerating 2^2048 strings is the same with factoring a composite with > length 2^2048 which is the product of two primes. > > And obviously, whenever we successfully factor the composite, we can > calculate the Euler function of it. So that given any public key > (n,e), calculating the private key (n,d) is easy. > So all I have to do to break RSA is to count to 2^2048?
regards Steve -- Steve Holden +1 571 484 6266 +1 800 494 3119 PyCon is coming! Atlanta, Feb 2010 http://us.pycon.org/ Holden Web LLC http://www.holdenweb.com/ UPCOMING EVENTS: http://holdenweb.eventbrite.com/ -- http://mail.python.org/mailman/listinfo/python-list
