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

Message-ID: <Pine.LNX.4.62.0704262005130.21392@element.ksp.sk>
Date: Thu, 26 Apr 2007 22:19:52 +0200 (CEST)
From: Peter Kosinar <goober@....sk>
To: full-disclosure@...ts.grok.org.uk
Subject: Re: Rapid integer factorization = end of RSA?

Hello,

>> If you have, in fact, come up with a fast method of integer
>> factorization, the currently unfactored challenges (RSA-704 and above)
>> would be better proof, no?
>
> no. We're talking about mathemetics, aren't we? So, an example for a
> assumption is not a *proof*. Neither are two or three...

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?

2) Could you demonstrate how your algorithm works for the number
    2^32+1, please? I have a quite good reason for asking about this
    particular number.

Peter

-- 
[Name] Peter Kosinar   [Quote] 2B | ~2B = exp(i*PI)   [ICQ] 134813278

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