Being coy about a factorisation

[fivemack]

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]

[ewmayer]

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?

[fivemack]

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.

[retina]

Originally Posted by fivemack

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

[fivemack]

Originally Posted by retina

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.

[retina]

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.

[Orgasmic Troll]

(this thread seemed worthy of an upgrade)

[maxal]

Originally Posted by fivemack

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.