Apologies for the obviously ridiculous question but I need to know where I'm going wrong here.

For RSA, we compute $n=pq$ for primes $p$ and $q$. We then choose an $e$ such that $gcd(e, \varphi(n))=1$ and compute $d$ such that $ed = 1 \mod \varphi(n)$. The public key is $(n, e)$ and private key is $(\varphi(n), d)$. I see how this is correct and so on.

My question is this: Why doesn't an attacker just compute $d'$ such that $ed'=1 \mod n$? Then surely decryption will work mod $n$?

eg where does this go wrong? $e=3, p=11, q=17, n=187, M=2$ Then $C=M^3=8$ Attacker calculates $e^{-1} \mod n = d' = 26$ and $8^{26}= 2 \mod n$?? More generally $C=M^{ed'} \mod n = M^{1} \mod n = M$?

  • $\begingroup$ An attacker could compute $d'$, but that wouldn't help him anything, because you need the special relation mentioned in your question for the decryption using $d$ to work ($ed\equiv 1 \pmod{\phi(n)}$) $\endgroup$
    – SEJPM
    May 14, 2015 at 13:29
  • 1
    $\begingroup$ In the example you cited $8^{26} = 47 \bmod 187$, and not $2$ $\endgroup$
    – poncho
    May 14, 2015 at 13:30
  • $\begingroup$ Why doesn't $M^{ed'}=M^{1} \mod n$ (because $ed' = 1 \mod n)$? $\endgroup$
    – Louise
    May 14, 2015 at 13:32
  • $\begingroup$ Becsuse $ed'-1$ is (in general) not a multiple of the order of the group, which is $lcm(p-1,q-1)$ $\endgroup$
    – poncho
    May 14, 2015 at 13:33
  • $\begingroup$ Also, the private key is $(n,d)$, not $(\varphi(n),d)$. $\endgroup$
    – Carl Knox
    Jan 30, 2017 at 3:06

1 Answer 1


You are essentially asserting that if $k \equiv 1 \pmod N$, then $a^k \equiv a \pmod N$. This is false in general. The correct assertion is the following: $a^k \equiv a^\ell \pmod N$ if $k\equiv \ell \pmod{\phi(N)}$.

In more general group-theoretic terms, if $a$ is an element of order $n$ in a group $G$, then $a^k = a^\ell$ if and only if $k \equiv \ell \pmod n$. Note that in the statement of the previous paragraph, $\phi(N)$ is not necessarily the order of $a$, hence it did not have the "only if" part.

EDITED to add: This is actually an important issue which bears emphasis because it occurs often in cryptographic contexts. When working with powers of an element in a group, it is important to remember that the exponents should be viewed as integers modulo the order of the element. In an abstract group this is not a problem, but when the group is integers modulo some $N$, it is easy to "think modulo $N$" also for the exponents, but it leads to this sort of errors.

  • 1
    $\begingroup$ Makes sense. Apologies for being stupid. $\endgroup$
    – Louise
    May 14, 2015 at 13:48
  • 3
    $\begingroup$ This is actually not stupid, I remember myself getting the "mod p"s and the "mod (p-1)"s mixed up when working with powers of primitive elements mod p... (Hence my edit.) $\endgroup$
    – fkraiem
    May 14, 2015 at 13:51

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.