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

Date: Thu, 26 Apr 2007 11:07:48 -0700
From: "Kurt Buff" <kurt.buff@...il.com>
To: full-disclosure@...ts.grok.org.uk
Subject: Re: Rapid integer factorization = end of RSA?

Get it peer-reviewed, or go away.

On 4/25/07, Eugene Chukhlomin <chukh29ru@...oline.su> 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.
> 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)
>
> 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
> or
> (p-1)*q=p*q*(q-1)=>((-p)*q)/(p*q)=(q-1) => (q-1)+1 = q
>
> 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
> 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
>
> _______________________________________________
> Full-Disclosure - We believe in it.
> Charter: http://lists.grok.org.uk/full-disclosure-charter.html
> Hosted and sponsored by Secunia - http://secunia.com/
>

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