Full Disclosure mailing list archives
Re: Rapid integer factorization = end of RSA?
From: Stanislaw Klekot <dozzie () dynamit im pwr wroc pl>
Date: Thu, 26 Apr 2007 10:58:35 +0200
On Thu, Apr 26, 2007 at 10:53:56AM +0400, Eugene Chukhlomin wrote:
Hi list! I discovered a new method of integer factorization for any precision numbers, probable it should be an end of RSA era. Details: Let N - the ring and N = p*q Then, (-p) in terms of ring(N) is equal (N-p) Lemma: p*(-q)=p*q*(-p) and respective: (-p)*q=p*q*(-q) Proof: p*(-q)=p*(N-q) - by the data, then p*(-q)=p*(p*q-q)=p*pq-p*q=p*q*p-p*q=(p-1)*(p*q) (-p)*q=q*(N-p) - by the data, then (-p)*q=(p*q-p)*q=p*q*q-p*q=p*q*q-p*q=(q-1)*(p*q) Q. E. D.
Funny way to pull the -1 out from the parenthesis. p * (-q) = p * (-1) * q = p * q * (-1) (mod pq) That is, p * (-q) = 0 (mod pq).
Gypothesis: Let N = p*q = A1*B1 + A2*B2... + An*Bn Then exists some subset(A1...An) and respective subset(B1...Bn), which satisfies for equality: A1*(-B1)+A2*(-B2)...+An*(-Bn) = p*(-q)=p*q*(p-1) or A1*(-B1)+A2*(-B2)...+An*(-Bn) = (-p)*q=p*q*(q-1)
For example, whole A_k and B_k, k = {1..n} sets? Second and third expressions in both lines are congruent to 0 mod pq.
If found such (A1...An) and (B1...Bn), we can find p or q by dividing p*(q-1) on p*q: p*(q-1)=p*q*(p-1) => (p*(q-1))/(p*q)=(p-1) => (p-1)+1 = p
^^^^^^^^^^^^^^^^^ This is untrue. p * (q - 1) = p * q - p = -p != 0 (mod pq) p * q * (p - 1) = 0 * (p - 1) = 0 (mod pq)
p*(q-1)=p*q*(p-1) => (p*(q-1))/(p*q)=(p-1) => (p-1)+1 = p
^^^^^^^^^^^^^^^ Dividing by zero in _any ring_ is illegal. By the way, if you find x = p * (q - 1) you can use Euclidean algorithm to find GCD(x, pq). Since GCD(q - 1, q) = 1, you get GCD(x, p), and that would be p as p divides x.
Sample: 21 = 3*7 Let's view a binary representation of this number: 10101 => 2^4 + 2^2 + 1 => 4*4+2*2+1*1 Then, we can try to find 7*(-3) in terms of ring(21):
^^^^^^
4*(-4) + 2(-2) + 1*(-1) => 4*(21-4)+2*(21-2)+1*(21-1)=>4*17+2*19+1*20 = 68+38+20=> 68+38+20 = 126 = 6*21 6+1=7
OK, but where did you get 7 and -3 (from underscored expression) from? 3*7 is public, but both 3 and 7, as elements of multiplication, are private. And if you get (7, -3) pair, why didn't you simply multiplicate the second element of this pair by -1?
This implementation of my gypothesis has very hard complexity (about a log2(N)! comparations), but exists a short way with fixed complexity for implementation of hypothesis ("plan B") - but, by ethical reason, I'll not post it here. Regards, Eugene Chukhlomin
-- Stanislaw Klekot _______________________________________________ Full-Disclosure - We believe in it. Charter: http://lists.grok.org.uk/full-disclosure-charter.html Hosted and sponsored by Secunia - http://secunia.com/
Current thread:
- Rapid integer factorization = end of RSA? Eugene Chukhlomin (Apr 26)
- Re: Rapid integer factorization = end of RSA? Stanislaw Klekot (Apr 26)
- Re: Rapid integer factorization = end of RSA? Kurt Buff (Apr 26)
- Message not available
- Re: Rapid integer factorization = end of RSA? e.chukhlomin (Apr 26)
- Re: Rapid integer factorization = end of RSA? Valdis . Kletnieks (Apr 26)
- Re: Rapid integer factorization = end of RSA? Pavel Kankovsky (Apr 27)
- Re: Rapid integer factorization = end of RSA? e.chukhlomin (Apr 26)
- <Possible follow-ups>
- Re: Rapid integer factorization = end of RSA? Eugene Chukhlomin (Apr 26)
- Re: Rapid integer factorization = end of RSA? Stanislaw Klekot (Apr 26)
- Re: Rapid integer factorization = end of RSA? virus (Apr 26)
- Re: Rapid integer factorization = end of RSA? Brendan Dolan-Gavitt (Apr 26)
- Re: Rapid integer factorization = end of RSA? virus (Apr 26)
- Re: Rapid integer factorization = end of RSA? Stephan Gammeter (Apr 26)