[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <51965efb0711151246r6f3aca7dhe51988cae10a4f9a@mail.gmail.com>
Date: Thu, 15 Nov 2007 21:46:44 +0100
From: gandlf <gandlf@...il.com>
To: bugtraq@...urityfocus.com
Subject: Re: Breaking RSA: Totient indirect factorization
> 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".
Powered by blists - more mailing lists