Bugtraq mailing list archives
Re: Breaking RSA: Totient indirect factorization
From: gandlf <gandlf () gmail com>
Date: Thu, 15 Nov 2007 21:46:44 +0100
So what is the expected running time of your algorithm? For example, how long it will take on average to factor a 1024-bit modulus?
I don't know because I have to know the average biggest totient divisor of a 1024-bit modulus.
- 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
The algorithm ends when a == 1, and that happens when n is the biggest modulus' totient divisor. 4) - If "a" contains by power all the totien's divisors then "a^n mod m" will always be "1".
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)