mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2007-10-25, 22:47   #1
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

144548 Posts
Default Being coy about a factorisation

Suppose I claim to know the prime factors of

443010714176109914706062719399735837784888419454424993687966966355234791105604901627494851350770582163

and as evidence I tell you that

291423963431617699625266784773913140613841657204484201197140989542464400773582731403109417558223483732

119427483518486854181247739124795565127732359113308658130536891525701261106546136708919018267024127319

157520094591254666391292892953803503318347627033544019282262658910481182629167678068312685665643810948

239572651700526397232653310567005639418195632736211177608879033627897596067927907761541596172557189678

are the square roots mod N of 3, 7, 17 and 23 respectively.

You can check my claim, but don't bother; it's true.

Clearly, if I know the factors, I can compute the square roots.

Clearly if you tricked me into giving you another square root of one of the primes you could compute the factors with probability 1/2.

If I gave you the square roots of all the primes less than 10^10 mod N, you could do something like the quadratic sieve to recover the factors - find some T whose square mod N splits as a product of primes less than 10^10, check what I'd have claimed for the square root of that square, and with a good probability you can recover the factors by GCD.

If I told you the quadratic character mod N of every prime less than 1000, you'd have a large number of modular constraints on the factors, and each constraint rules out half the numbers, so the ensemble of constraints gives you the factors; but dense Chinese-remainder-theorem problems are hard to solve.

But can you use just the four square roots I've given you to recover the factors?

[this is not an interesting number, and now that I've closed the magma window I worked it out in I don't know the factors either, but running eight hours of GNFS to recover them is not in the spirit of the thing]
fivemack is offline   Reply With Quote
Old 2007-11-01, 17:10   #2
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

2D9C16 Posts
Default

Hi, Tom: I probably haven't given this the consideration it deserves, but I don't see how the quadratic residuacity information you give can narrow things down more than via the standard approximate-factor-of-2-for-each-added-QR. Is the fact that you provide actual explicit square-roots-modulo [rather than just the QR which the finding of any square root demonstrates] meaningful?
ewmayer is offline   Reply With Quote
Old 2007-11-01, 18:00   #3
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

192C16 Posts
Default

Giving the square roots explicitly produces almost irrefutable evidence that I know the factorisation; you can check that what I've given is a square root of what I've claimed.

As far as I recall, the proof that SQRT is equivalent to factorisation is 'take random numbers M, square them, ask your SQRT oracle for the root, check GCD(root-M,N); the oracle can't know which M you gave, so with probability 1/2 will give a square root which is in the other class mod one of the primes'; this obviously doesn't apply in this situation, where I will remember which classes modulo the primes the sqrts that I gave you came from, and take care that I don't accidentally tell you something useful.
fivemack is offline   Reply With Quote
Old 2007-11-01, 19:28   #4
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

630210 Posts
Default

Quote:
Originally Posted by fivemack View Post
But can you use just the four square roots I've given you to recover the factors?
I doubt it can (currently[1]) be done without GNFS, else if one could find the factors with the four pieces of information you give would that not also mean the RSA/Rabin public key cyphers could also be solved with a few sample encryptions.

[1] That is not to say in the future a useful and quick algorithm could be found that can find the factors without GNFS

Last fiddled with by retina on 2007-11-01 at 19:29
retina is online now   Reply With Quote
Old 2007-11-01, 19:39   #5
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

22×32×179 Posts
Default

Quote:
Originally Posted by retina View Post
I doubt it can (currently[1]) be done without GNFS, else if one could find the factors with the four pieces of information you give would that not also mean the RSA/Rabin public key cyphers could also be solved with a few sample encryptions.
I don't think this is equivalent to breaking RSA; if you can 'break RSA' in the sense of decrypting arbitrary messages, you can factorise by the same sort of argument I used before - ask for the cube root of a number that you cubed earlier. That is a real attack, and is why you sign (in the RSA sense) the suitably-padded hash of a message rather than the message itself.

But small primes really aren't arbitrary messages in this sense; you're not getting the kind of round-trip that the proof requires.

Could you suggest what kind of sample encryptions you'd be using to break RSA given an oracle for Nth roots of numbers less than 1000 ? Finding a number with a small enough or smooth enough cube is something of a feat without the factorisation.
fivemack is offline   Reply With Quote
Old 2007-11-01, 20:05   #6
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

2×23×137 Posts
Default

But the Rabin PKE uses squares. You've given square roots to prove you know the factors. The Rabin system also uses squared "encryptions" based upon the premise that finding square roots is equivalent to factoring in terms of computational difficulty of solving.

The Handbook of Applied Cryptography chapter 8.3 gives an explanation much better than I can do here.
retina is online now   Reply With Quote
Old 2007-11-10, 04:30   #7
Orgasmic Troll
Cranksta Rap Ayatollah
 
Orgasmic Troll's Avatar
 
Jul 2003

641 Posts
Default

(this thread seemed worthy of an upgrade)
Orgasmic Troll is offline   Reply With Quote
Old 2007-11-17, 01:27   #8
maxal
 
maxal's Avatar
 
Feb 2005

3748 Posts
Default

Quote:
Originally Posted by fivemack View Post
Clearly if you tricked me into giving you another square root of one of the primes you could compute the factors with probability 1/2.
The probability is 1, assuming that this other root is not just a negation mod N of the one that we already know.
maxal is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
factorisation devarajkandadai Factoring 7 2013-07-06 03:44
Records for complete factorisation Brian-E Math 25 2009-12-16 21:40
Kraitchik's factorisation method Robertcop Math 2 2006-02-06 21:03

All times are UTC. The time now is 12:27.


Mon Dec 6 12:27:03 UTC 2021 up 136 days, 6:56, 0 users, load averages: 1.27, 1.37, 1.36

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.