0
$\begingroup$

In RSA, we choose $p,q$ and calculate $\phi(n)=(p-1)(q-1)$. We then choose a public key $e$, and calculate its inverse modulo $\phi(n)$: $d\cdot e=1 \mod(\phi(n))$.

But then, when we decrypt a ciphertext $y=x^e \mod(n)$, we use the different modulus $n$ rather than $\phi(n)$: $x=y^d \mod(n)$. This is equal to $x^{e\cdot d \mod(n)}$, which supposedly equals $x^1$. But I don’t understand this last step, because we chose $d$ such that $e\cdot d=1 \mod (\phi(n))$, not such that $e\cdot d=1 \mod(n)$

Improve this question
$\endgroup$
2
  • $\begingroup$ The question's notation $y=x^e\mod(n)$ and $x=y^d\mod(n)$ is not standard. RSA actually uses $y=x^e\bmod n$ and $x=y^d\bmod n$, with less space on the left of $\bmod$ and customarily no parenthesis around the single variable $n$. In this, $\bmod$ is an operator returning the remainder of the Euclidean division of its left operand by its right operand (like % does in C, Java, Go, at least for non-negative left argument and positive right argument). Also, it is unclear what "is equal to $x^{e\cdot d \mod(n)}$ " and what the later is. $\endgroup$
    – fgrieu ♦
    Sep 13, 2018 at 8:19
  • $\begingroup$ @fgrieu, With "is equal to ..." I meant to say that $y^d \bmod n = (x^e)^d \bmod n = x^{e\cdot d} \bmod n$. $\endgroup$
    – user56834
    Sep 13, 2018 at 10:02

3 Answers 3

Reset to default
3
$\begingroup$

The question assumes, wrongly, that $a^b\bmod n$ is the same as $a^{b\bmod n}$ or $a^{b\bmod n}\bmod n$. In general these are three different quantities, as demonstrated with $a=5$, $b=5$, $n=3$: $$\begin{array}{} a^b\bmod n&=&\left(5^5\right)\bmod 3&=&3125\bmod 3&=&2\\ a^{b\bmod n}&=&5^{(5\bmod 3)}&=&5^2&=&25\\ a^{b\bmod n}\bmod n&=&\left(5^{(5\bmod 3)}\right)\bmod 3&=&25\bmod3&=&1 \end{array} $$ Note: going from the second to third expression of the last line uses the result obtained above.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I still don't understand why $(x^e \bmod n )^d \bmod n = x \bmod n$ $\endgroup$
    – user56834
    Sep 13, 2018 at 10:04
  • $\begingroup$ @Programmer2134: That's asking why textbook RSA works, rather than why an RSA variant does not. We have multiple answers for that, including this which gives a simple proof valid for all messages. If we restrict to $x$ coprime with $n$ (that's most $x$), there's a simpler proof: $\left(x^e\bmod n\right)^d\bmod n$ is $x^{e\,d}\bmod n$, thus (by construction of $d$) is $x^{\phi(n)\,k+1}\bmod n$ for some $k$, thus $\left(x^{\phi(n)}\right)^kx\bmod n$, thus (since $x^{\phi(n)}\bmod n=1$ for any $x$ coprime to $n$) is $1^kx\bmod n$, thus is $x\bmod n$. $\endgroup$
    – fgrieu ♦
    Sep 13, 2018 at 12:53
  • 1
    $\begingroup$ More to the point, $x\equiv y \pmod n$ does not imply $a^x\equiv a^y \pmod n$; this is why we don't take $ed \equiv 1 \pmod n$. $\endgroup$
    – fkraiem
    Sep 13, 2018 at 12:59
0
$\begingroup$

You are correct, $ed=1 \bmod \phi(n)$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Actually, we have $ed \equiv 1 \pmod {\text{lcm}(p-1, q-1)}$ as being the necessary and sufficient condition on $e, d$ $\endgroup$
    – poncho
    Sep 13, 2018 at 14:44
0
$\begingroup$

I think you want to know why we use $\phi(n)$ as a modulus when calculating the keys and $n$ as a modulus when calculating the message/chiphertext. I was wondering the same when studying the RSA cryptosystem for the first time. The following is taken from the book Understanding Cryptography by Chrisoph Paar on page 178.

We have the definition of the RSA keys. $$de \equiv 1 \pmod {\phi(n)}$$

Per definition of the $\phi$ function this means the following: $$de = 1 + t*\phi(n)$$ for any integer $t$.

Edit: We assume that $gcd(x,n)=1$. Now we take a look at the decryption process. $$d(y) \equiv y^d \equiv (x^e)^d \equiv x^{de} \pmod n$$

It follows: $$x^{de} \equiv x^{1+t*\phi(n)} \equiv x^1*x^{t*\phi(n)} \equiv x*(x^{\phi(n)})^t \pmod n$$

Now take a look at Euler's theorem (a generalization of Fermat's little theorem). $$x^{\phi(n)} \equiv 1 \pmod n $$

Now we can substitute and get $$x^{de} \equiv x*1^t \equiv x \pmod n$$

Improve this answer
$\endgroup$
1
  • $\begingroup$ This proof is partial, silently assuming that $\gcd(x,n)=1$. For other $x$, the equality $x^{\phi(n)}\bmod n=1$ does not hold. Example: $x=6$, $n=15=3\cdot5$ with $\phi(n)=2\cdot4=8$, thus $x^{\phi(n)}=1679616$, thus $x^{\phi(n)}\bmod n=1679616\bmod 15=6\ne1$. Yet, such $x$ with $0\le x<n$ and $\gcd(x,n)\ne1$ still meet $x^{e\,d}\bmod n=x$. $\endgroup$
    – fgrieu ♦
    Sep 13, 2018 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.