I read an article about the RSA cryptosystem and I find the way of encryption a bit confusing. This is the part that I do not understand:

Let's say that we choose these prime numbers: $p = 17$ and $q = 23$, hence $n = pq = 391$. Also, the totient function: $\varphi(17 \cdot 21) = 320 $.

Now, we choose our public and private key integers - the first one, $e$, should be coprime with $320$, so let's pick $169$. which yields that $d = 89$.

Now, we know that $ed = 1 \mod 320$. However, in the algorithm itself, we perform operations $\mod 391$, and yet $(\mbox{message})^{ed}=\mbox{message} \mod 391$. How can we know that $ed = 1\mod 391$ given $md = 1 \mod 320$?

  • $\begingroup$ The exponents operate in a different modulus than the base. This is responsible for the change. For the precise reason, see Euler's Theorem on congruences mod $n$. $\endgroup$ – Randall Apr 20 '18 at 17:22

Euler's Theorem asserts that when $x$ is relatively prime to $n$ then $x^{\varphi(n)} \equiv 1 \bmod n$. Note that it does not say that $x^n \equiv 1 \bmod n$: just because $n \equiv 0 \bmod n$ does NOT mean that you can replace the $n$ in the exponent this way. In fact, you definitely cannot/should not, and Euler's Theorem shows you the right path.

Now, if $x$ is relatively prime to $n$ then it is easy to show that RSA decryption always works. The whole point is that you've chosen $e$ and $d$ so that $ed \equiv 1 \bmod \varphi({n})$, hence $ed = 1 + k\varphi(n)$ for some integer $k$. After encrypting by $x \mapsto x^e \bmod n$ we decrypt by $x^e \mapsto (x^e)^d = x^{ed} \bmod n$. Why is this $x$ again? It's Euler's Theorem:

$$ x^{ed} = x^{1+k\varphi(n)} = x \cdot (x^{\varphi(n)})^k = x \cdot 1^k =x $$ where all computations happened mod $n$.

The case when $x$ is not relatively prime to $n$ is proven by a slightly different argument, but in the same spirit. In all cases, $x^d$ always decrypts correctly.


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.