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]

Message-ID: <20070427202409.46A1.0@argo.troja.mff.cuni.cz>
Date: Fri, 27 Apr 2007 20:42:16 +0200 (MET DST)
From: Pavel Kankovsky <peak@...o.troja.mff.cuni.cz>
To: "e.chukhlomin" <chukh29ru@...oline.su>
Cc: full-disclosure@...ts.grok.org.uk
Subject: Re: Rapid integer factorization = end of RSA?

On Thu, 26 Apr 2007, e.chukhlomin wrote:

> 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 and:
> 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)

Let n = 1, A1 = p, B1 = q. Then
1. A1B1 = pq = N.
2. A1(-B1) = p(-q) =
   [let's pretend this careless mixing of equalities in Z an
    congruences in Z_N makes any sense and assume -X stands for N-X]
   = p(N-q) = p(pq-q) = p(p-1)q = pq(p-1).
QED.

Ok. Your "gypothesis" holds (sort of). We can factor N when we know its
factors. What a breakthrough. Perhaps Bill Gates will mention it in
"The Road Ahead II".

--Pavel Kankovsky aka Peak  [ Boycott Microsoft--http://www.vcnet.com/bms ]
"Resistance is futile. Open your source code and prepare for assimilation."

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