bugtraq - Re: Breaking RSA: Totient indirect factorization

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

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".