mersenneforum.org > Math Being coy about a factorisation
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2007-10-25, 22:47 #1 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 2×7×461 Posts 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]
 2007-11-01, 17:10 #2 ewmayer ∂2ω=0     Sep 2002 República de California 101101111010102 Posts 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?
 2007-11-01, 18:00 #3 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 2×7×461 Posts 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.
2007-11-01, 19:28   #4
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

2·34·41 Posts

Quote:
 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

Last fiddled with by retina on 2007-11-01 at 19:29

2007-11-01, 19:39   #5
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

2·7·461 Posts

Quote:
 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.

 2007-11-01, 20:05 #6 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 2×34×41 Posts 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.
 2007-11-10, 04:30 #7 Orgasmic Troll Cranksta Rap Ayatollah     Jul 2003 28116 Posts (this thread seemed worthy of an upgrade)
2007-11-17, 01:27   #8
maxal

Feb 2005

4048 Posts

Quote:
 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.

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post devarajkandadai Factoring 7 2013-07-06 03:44 Brian-E Math 25 2009-12-16 21:40 Robertcop Math 2 2006-02-06 21:03

All times are UTC. The time now is 07:47.

Sat Dec 10 07:47:43 UTC 2022 up 114 days, 5:16, 0 users, load averages: 0.77, 0.80, 0.82

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔