# How to find mod N in RSA algorithm given ciphertext and plaintext

I have a problem where I have to find mod N in a RSA cipher.

I am given the following information:

1. The public key (e)
2. Plaintext (M)
3. Cipher text (C)

How can I reverse the equation C = (M^e) mod N to find N?

• Hint1: write down what $C=M^e\bmod N$ means, by definition of that. Notice that gives you both an integer known to be a multiple of $N$, and likely an order of magnitude of $N$. Hint2: if, as often, this is stated with two $(M,C)$ pairs: you get two integers that $N$ divides (and two shots at evaluating the order of magnitude of $N$).
– fgrieu
Aug 21, 2022 at 12:48
• Hi, thank you so much for your response. The trouble I am having with this is my given e value is 55317 and my (M,C) pairs are (189,200) and (69,79). When i plug these into the equation 𝐶=M^𝑒 mod𝑁, I get 79 = (69^55317) mod N. It is really hard for me to find N as I cannot evaluate 69^55317. Is there another way to find N? Aug 21, 2022 at 13:23
• You'll need to find a way to manipulate numbers like $69^{55317}$. Python is one. You'll also need to turn $79 = 69^{55317}\bmod N$ into something more directly exploitable about $N$. And you'll need both pairs. [Addition] And your numbers are wrong or there's a trap.
– fgrieu
Aug 21, 2022 at 14:34
• Duplicate of crypto.stackexchange.com/a/26190 Aug 22, 2022 at 16:52
• About the above: nearly the same question, with encryption where the other is for signature.
– fgrieu
Aug 22, 2022 at 18:21

something is wrong with your numbers:

>>> cr=69**55317
>>> cr2=189**55317
>>>
>>> from math import gcd
>>> gcd(cr-79,cr2-200)
1


We calculate the raw exponent, we subtract the cipher text and expect to get 0 mod N, we have two such ciphertexts so we expect to get $$a*N$$, $$b*N$$ for natural integers a and b. We calculate gcd to extract $$N$$ but with your numbers we get 1 which means, something is wrong with the input, or possibly in how are interpreting the input.

• Addition: the GCD $G$ thus obtained might not be exactly $N$, but rather the product of $N$ and some usually small residual factor(s). We should eliminate such small factors of $G$, e.g. any $f$ dividing $G$ that we can find and such that $G/f$ is not prime and $G/f$ is larger than the largest plaintexts and ciphertexts that we have.
– fgrieu
Aug 22, 2022 at 9:37