1
$\begingroup$

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

$\endgroup$
  • $\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 '15 at 13:29
  • 1
    $\begingroup$ In the example you cited $8^{26} = 47 \bmod 187$, and not $2$ $\endgroup$ – poncho May 14 '15 at 13:30
  • $\begingroup$ Why doesn't $M^{ed'}=M^{1} \mod n$ (because $ed' = 1 \mod n)$? $\endgroup$ – Louise May 14 '15 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 '15 at 13:33
  • $\begingroup$ Also, the private key is $(n,d)$, not $(\varphi(n),d)$. $\endgroup$ – Carl Knox Jan 30 '17 at 3:06
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Makes sense. Apologies for being stupid. $\endgroup$ – Louise May 14 '15 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 '15 at 13:51

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.