I'm having a hard time creating a functioning RSA algorithm for some reason even though I have all the steps right (or at least I think I do). So I have the following :

I picked prime numbers, $p$ and $q$ as:

$$p = 13691$$ $$q = 29387$$

I picked $n$ as $p \cdot q$ $$n = 402337417$$

So $$\phi(n) = 402294340$$

I picked a random $e$ between $1$ and $\phi(n)$ $e = 46117$

My message was $M=3$

I got $d$ by the Extended Euclidean Algorithm as the following: $d= 7795$

When I do the encryption using $M^e \,\text{mod}\, n$ I get: $c= 399797630$

When I do the decryption using $C^d \,\text{mod}\, n$, I get $243069037$, which is not $M = 3$?

Any idea what can be the reason behind this? My guess is that $d$ is incorrect.


2 Answers 2


Your $d$ is wrong, double check your EEA calculation. You picked up the wrong Bezout coefficient from $7795\times 402294340 - 67998447\times 46117 =1$. You should use $d= -67998447 \equiv 334295893 \pmod {\phi(n)}.$


You computed $d$ incorrectly; without knowing exactly what you did, I can't say what you did wrong.

Try $d = 334295893$; in addition, $d = 133148723$ also works as a decryption exponent.

  • $\begingroup$ How is it possible to have 2 d's that works for the decryption? $\endgroup$
    – rullzing
    Oct 17, 2017 at 22:44
  • $\begingroup$ @rullzing: actually, there are an infinite number of $d$ values that all work for decryption; the two values listed are only the smallest ones. $\endgroup$
    – poncho
    Oct 18, 2017 at 2:16
  • $\begingroup$ @rullzing: specifically, adding or subtracting any multiple of lcm(13690,29386)=201147170 works $\endgroup$ Oct 18, 2017 at 3:27

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.