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

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

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Makes sense. Apologies for being stupid. $\endgroup$ Commented 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$ Commented May 14, 2015 at 13:51

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.