Bugtraq mailing list archives
Re: Breaking RSA: Totient indirect factorization
From: Clifton Royston <cliftonr () lava net>
Date: Thu, 15 Nov 2007 06:58:34 -1000
On Wed, Nov 14, 2007 at 10:59:42PM +0100, gandlf wrote: ..
Algorithm --------- - Repeat "a = a^n mod m" with n from 2 to m, saving all the results in a table until a == 1 (Statement 4).
Do I understand correctly that this step of your proposed algorithm can identify the private key corresponding to (e.g.) a 1024 bit public key, but only by doing on the order of Sum(2..2^1024) = ~ 2^1025 modular exponentiations and storing the results? If so, that would come to approximately 1E307 modular exponentiation operations. Divide that out by (for example) teraflops and the expected lifetime of the universe, and I don't think you will get a pleasing result. -- Clifton -- Clifton Royston -- cliftonr () iandicomputing com / cliftonr () lava net President - I and I Computing * http://www.iandicomputing.com/ Custom programming, network design, systems and network consulting services
Current thread:
- Breaking RSA: Totient indirect factorization gandlf (Nov 14)
- Re: Breaking RSA: Totient indirect factorization Alexander Klimov (Nov 15)
- Re: Breaking RSA: Totient indirect factorization Clifton Royston (Nov 15)
- Re: Breaking RSA: Totient indirect factorization gandlf (Nov 15)
- Re: Breaking RSA: Totient indirect factorization Erick Galinkin (Nov 16)
- Re: Breaking RSA: Totient indirect factorization gandlf (Nov 15)
- Re: Breaking RSA: Totient indirect factorization Watson Ladd (Nov 16)