I have a problem where I have to find mod N in a RSA cipher.
I am given the following information:
- The public key (e)
- Plaintext (M)
- Cipher text (C)
How can I reverse the equation C = (M^e) mod N to find N?
$\begingroup$
$\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 ♦Commented 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$– Blinky_BlinderCommented 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 ♦Commented Aug 21, 2022 at 14:34
-
$\begingroup$ Duplicate of crypto.stackexchange.com/a/26190 $\endgroup$– Samuel NevesCommented Aug 22, 2022 at 16:52
-
$\begingroup$ About the above: nearly the same question, with encryption where the other is for signature. $\endgroup$– fgrieu ♦Commented Aug 22, 2022 at 18:21
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
-
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 ♦Commented Aug 22, 2022 at 9:37