0
$\begingroup$

When signing using RSA with $e = 65537$ and many pairs of m and c, where $$c^e \bmod (n)=m$$ is there a way to find n (n is 2048 bits)?

I planned on computing $ c^e-m $ and then treating those as a basis for a lattice. But $c^e$ was too large.

$\endgroup$
2
  • $\begingroup$ Duplicate of crypto.stackexchange.com/questions/26188 $\endgroup$ Aug 22 at 22:50
  • $\begingroup$ The answer provided by @poncho worked well. Also, moving from Python to SageMath improved the speed and made this doable on my machine. $\endgroup$
    – rozi
    Aug 22 at 22:55
2
$\begingroup$

is there a way to find n (n is 2048 bits)?

Yes, if you assume deterministic padding (which is sometimes used for signatures, which appears to be the case you're considering)

You're on the right track by considering $c^e - m$ (which will be a multiple of $n$); given that we have several, what we can do is take two, and compute:

$$\gcd( c^e-n, c'^e-m' )$$

This will be $n$ (multiplied by an integer with a high probability of being small; that's easy to scrap off); that's your answer.

The values we're taking the GCD of are about $2^{27}$ bits in length - using the standard binary or Euclidean algorithms would probably take rather longer than we would prefer to wait. However, Lehmer's GCD algorithm should bring it into a range that's not intolerable...

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.