0
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ 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$). $\endgroup$
    – fgrieu
    Aug 21, 2022 at 12:48
  • $\begingroup$ 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? $\endgroup$ Aug 21, 2022 at 13:23
  • $\begingroup$ 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. $\endgroup$
    – fgrieu
    Aug 21, 2022 at 14:34
  • $\begingroup$ Duplicate of crypto.stackexchange.com/a/26190 $\endgroup$ Aug 22, 2022 at 16:52
  • $\begingroup$ About the above: nearly the same question, with encryption where the other is for signature. $\endgroup$
    – fgrieu
    Aug 22, 2022 at 18:21

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – fgrieu
    Aug 22, 2022 at 9:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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