# RSA: Derive modulus from known ciphertexts encoded with same keypairs

I have two ciphertexts

$$c_1 = m_1^e \bmod n$$

$$c_2 = m_2^e \bmod n$$

I know $$c_1, c_2, m_1, m_2$$ and $$e$$. Is there a way to derive n from this? I first thought Franklin Reiter but I'd need an $$n$$ for that which is precisely what I am missing. What other approaches are there?

• Hint: $$a\equiv b\pmod m\iff \exists k\in\mathbb Z:a=b+k\cdot m$$ – SEJPM Mar 16 at 12:25
• So from this I derive: $m_1^e + m_2^e - c_1 - c_2 = (j+k) * n$ – S. L. Mar 16 at 12:33
• But this doesn't help for $e=65537$ – S. L. Mar 16 at 12:38
• Is this homework? I ask because if you're learning, I'd attempt to give you a hint; if you're just trying to solve the problem (while learning as little as possible), I'll just give you the answer – poncho Mar 16 at 13:21
• @poncho I'd rather get a hint and if all else fails the answer :) it's not homework but I still want to learn – S. L. Mar 16 at 13:30

• We know that we have $$m_1^e - c_1 = k_1n$$ for some integer $$k_1$$
• We know that we have $$m_2^e - c_2 = k_2n$$ for some integer $$k_2$$
So, given that we know the values $$k_1n$$ and $$k_2n$$, how can we recover the common $$n$$ value? Hint: look at the $$\gcd$$ function...