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 12:35:23 +0200
On Thu, Apr 26, 2007 at 02:07:31PM +0400, Eugene Chukhlomin wrote:
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
Of course it's equal. And equal to zero modulo n, as I pointed. #v+ gap> p; 163473364580925384844313388386509085984178367003309231218111085238933310010450\ 8151212118167511579 gap> q; 190087128166482211312685157393541397547189678996851549366663853908802710380210\ 4498957191261465571 gap> n := p * q; 310741824049004372135075003588856793003734602284272754572016194882320644051808\ 150455634682967172328678243791627283803341547107310850191954852900733772482278\ 3525742386454014691736602477652346609 gap> (p * (n - q)) mod n; 0 gap> #v- What is it supposed to proove? -- 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)
- Re: Rapid integer factorization = end of RSA? ShadowGamers (Apr 26)
- Re: Rapid integer factorization = end of RSA? Peter Kosinar (Apr 26)
- Re: Rapid integer factorization = end of RSA? Stanislaw Klekot (Apr 26)