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

Message-ID: <463079E3.1030504@infoline.su>
Date: Thu, 26 Apr 2007 14:07:31 +0400
From: Eugene Chukhlomin <chukh29ru@...oline.su>
To: full-disclosure@...ts.grok.org.uk
Subject: Re: Rapid integer factorization = end of RSA?

>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).

Well, let's proof:
some days ago RSA-640 was factored, therefore I'll use this number for proofing.
N = p*q = 3107418240490043721350750035888567930037346022842727545720161948823206440518081504556346829671723286782437916272838033415471073108501919548529007337724822783525742386454014691736602477652346609 
p = 1634733645809253848443133883865090859841783670033092312181110852389333100104508151212118167511579
q = 1900871281664822113126851573935413975471896789968515493666638539088027103802104498957191261465571

Hence p*(-q) = p*(N-q), we have: 
1634733645809253848443133883865090859841783670033092312181110852389333100104508151212118167511579*(3107418240490043721350750035888567930037346022842727545720161948823206440518081504556346829671723286782437916272838033415471073108501919548529007337724822783525742386454014691736602477652346609-1900871281664822113126851573935413975471896789968515493666638539088027103802104498957191261465571) = 5079801149330465928652035530544913704964519649664113022948507643221268839586387905945718488562426349551024378408981587404238854112680081565808050803367178098655476230508056302202082021498932996241380749611265431048278537997959344921052965979997472486960464297533557254211807262177876539002;

and, by my gypothesis:
p*(-q) = p*q *(p-1) = p*(N-q)
163473364580925384844313388386509085984178363092312181110852389333100104508151212118167511579*1900871281664822113126851573935413975471896789968515493666638539088027103802104498957191261465571*1634733645809253848443133883865090859841783670033092312181110852389333100104508151212118167511578 = 5079801149330465928652035530544913704964519649664113022948507643221268839586387905945718488562426349551024378408981587404238854112680081565808050803367178098655476230508056302202082021498932996241380749611265431048278537997959344921052965979997472486960464297533557254211807262177876539002;
Q.E.D

Any new idea?

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