full-disclosure - Re: Rapid integer factorization = end of RSA?

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>] [day] [month] [year] [list]

Date: Sat, 28 Apr 2007 00:08:46 +0400
From: "e.chukhlomin" <chukh29ru@...oline.su>
To: full-disclosure@...ts.grok.org.uk
Subject: Re: Rapid integer factorization = end of RSA?

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
 
> Providing the factorization of a particular number (whose
> factorization is considered to be not known by anyone) is
> definitely a proof that you know the factorization of that number
> and that you had a method for finding it. Of course, it doesn't say
> anything about this method -- whether it is a general one or
> whether you were able to find the factors based on graph of
> temperature at the top of Elbrus  :-)
>
> On a more relevant note, let me try to explain the method described
> by the original poster, hopefully in a more readable way:
>
> Take an unknown number N, which we are going to factor. Then, by
> some mysterious process, represent the number N, such that (I)   N
> = A1*B1 + A2*B2 + ... An*Bn AND (II)  A1*(N-B1) + A2*(N-B2) + ... +
> An*(N-Bn) = N*(q-1) holds.
>
> In the examples provided by the original poster, these numbers were
> always created by taking the usual binary expansion of the number
> and splitting each term into a product Ak*Bk. The problem is that
> not all (if any) such splits produce the desired results. The
> original poster correcly stated that the obvious method for
> obtaining such a split (if it really exists under these conditions)
> runs in log(N)! steps (that's factorial of log(N), not just an
> exclamation... clearly, this number is greater than N, thus
> rendering this approach worse than trial division). He also claimed
> to have a much faster approach, though.
>
> Naturally, IF this can be done, one can find q-1 (thus also p,q)
> easily. In fact, the "easy" part of the algorithm can be even more
> simplified. The sum A1*(N-B1) + A2*(N-B2) + ... An*(N-Bn) can be
> rewritten as N*(A1+A2+...+An) - (A1*B1 + A2*B2 + ... An*Bn) =
> N*(A1+A2+...+An - 1) and the property (II) tells us that this
> number is equal to N*(q-1). In other words, q = (A1+A2+...An), so
> -once- we obtain the right sets A,B, finding the factorization is
> nothing but summing up a few numbers.
>
> Now, here are two questions for the original poster:
>
> 1) Did I understand your factorization "algorithm" correctly?
Yes, you are absolutely correct.
Regards,
Eugene Chukhlomin
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.2 (MingW32)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
 
iD8DBQFGMlhOna5g1zBq1QoRAoSxAKC1A3IjXQBQ+nTHKz75TOyjyXX0LACdGgcx
7Q4hHuxzLmM6QMj2O+lYfss=
=rQRk
-----END PGP SIGNATURE-----

_______________________________________________
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/