I came to a problem when calculating some values for RSA encryption task.

So the data I have is this:



Now I have to calculate the original message($m$) and I have an issue because I can see what the solution for $m$ should be, but I get a different answer.

So far, I was able to figure out that $e=27$ and $d=3$.

Now I should calculate $m=(p-1)*(q-1)$ with the equation: $e*d \bmod m = 1$.

But the solution I have from this example says that $m=40 \rightarrow 4*10$ which gives us $p=5$ and $q=11$.

Now my question is why is $40$ correct and not $m=20 \rightarrow 2*10 \rightarrow p=3$ and $q=11$, which is what I got?

  • $\begingroup$ The question's givens do not allow to "figure out that $e=27$ and $d=3$", and allow several solutions. Something must be missing! Additionally, is $ed\bmod((p-1)(q-1))=1$ precisely the requirement? Assuming $p$ and $q$ are distinct primes, the necessary and sufficient condition for RSA to work is $ed\bmodλ=1$ with $λ=\operatorname{lcm}(p-1,q-1)$, and many authors require $d=e^{-1}\bmodλ$ or $d=e^{-1}\bmodφ$ where $φ=(p-1)(q-1)$, rather than $ed\bmodφ=1$. $\endgroup$
    – fgrieu
    Jan 11 '20 at 4:41

So, you're given the exponents (and the ciphertext), and are expected to recover the modulus? That's certainly not the standard way of using RSA.

It turns out that the necessary and sufficient conditions on $p, q$ is that $p-1, q-1$ are factors of $ed-1$; hence we know that $p, q \in \{ 3, 5, 11, 17, 41 \}$ (as those are the primes that meet this criteria), and any such combination of distinct $p, q$ would work (we also know that $pq > c$, however all combinations meet this criteria); by work, I mean that $(m^e)^d \equiv m \bmod{pq}$ for all messages $m$. Now, with some combinations, the $e, d$ combination might not be minimal; however nonminimal $e, d$ values do happen in practice.

As both $p, q = 5, 11$ and $p, q = 3, 11$ meet the above criteria, both lead to valid answers. If the original question did not add any additional information, well, they did not specify the question sufficiently.

  • $\begingroup$ tnx for the explanation, can i just ask if the combination has to be minimal, which is the correct answer and how do you know that? $\endgroup$
    – masterdodo
    Jan 10 '20 at 22:21
  • $\begingroup$ @masterdodo: as for whether the combination has to be minimal, well, that's something that the poser of the question would need to answer. As for why the above criteria work, well, $(m^e)^d \equiv m \pmod{pq}$ iff $m^{ed} \equiv m \pmod p$ and $m^{ed} \equiv m \pmod q$; the last two are true for all $m$ iff $ed \equiv 1 \pmod{p-1}$ and $ed \equiv 1 \pmod{q-1}$; the later are equivlant to the statement $p-1, q-1$ are both factors of $ed-1$ $\endgroup$
    – poncho
    Jan 11 '20 at 2:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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