# Why doesn't this defeat RSA?

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$?

• 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)}$) May 14, 2015 at 13:29
• In the example you cited $8^{26} = 47 \bmod 187$, and not $2$ May 14, 2015 at 13:30
• Why doesn't $M^{ed'}=M^{1} \mod n$ (because $ed' = 1 \mod n)$? May 14, 2015 at 13:32
• Becsuse $ed'-1$ is (in general) not a multiple of the order of the group, which is $lcm(p-1,q-1)$ May 14, 2015 at 13:33
• Also, the private key is $(n,d)$, not $(\varphi(n),d)$. Jan 30, 2017 at 3:06

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.