# In RSA signing find n from e and many pairs of m and c

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.

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

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