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.


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 '17 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 '17 at 2:16
  • $\begingroup$ @rullzing: specifically, adding or subtracting any multiple of lcm(13690,29386)=201147170 works $\endgroup$ Oct 18 '17 at 3:27

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.