14
$\begingroup$

I'm trying to understand the working of RSA algorithm. I am getting confused in the decryption part. I'm assuming

$$n = pq$$ $$m = \phi(n) = (p - 1)(q - 1)$$

E is the encryption key $\gcd(\phi(n), E) = 1$

D is the decryption key, and $DE = 1 \mod \phi(n)$

$x$ is the plain text

Encryption works as ($y = x^E \mod n$) and decryption works as ($x = y^D \mod n$)

The explanation for why the decryption works is that since $DE = 1 + k\phi(n)$,

$$y^D = x^{ED} = x^{1 + k \phi(n)} = x(x^{\phi(n)})^k = x \mod n$$

The reason why last expression works is $x^{\phi(n)} = 1 \mod n$ ? According to Eulers theorem this is true only if $x \text{ and }\phi(n)$ are coprimes. But $x$ is only restricted to be $0 < x < n$ and $\phi(n) < n$. So $x$ should be chosen to be coprime with $\phi(n)$?

Help me clear out the confusion!

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ It is frustrating that many references (not just the OP's question) claim that RSA uses Euler's theorem and the possibility that x and n have a common factor is treated as a separate case. As user996522 shows in an answer below (not the accepted answer, unfortunately), it is irrelevant that x could have a factor in common with n, and in fact RSA goes through with n being any squarefree number with no exceptions on x whatsoever. That RSA works depends on Fermat's little theorem, not Euler's theorem. Look at the original RSA paper: they use Fermat's little theorem, not Euler's theorem. $\endgroup$ – KCd Dec 27 '11 at 16:50
  • $\begingroup$ @KCd I went through the original paper on RSA and indeed the explanation for decryption is based on Fermats Little theorem ( special case of Euler's theorem ) and the Chinese remainder theorem. $\endgroup$ – sauravrt Dec 27 '11 at 21:11
  • $\begingroup$ Can you tell me how you arrived at the answer: \begin{align*} &\equiv x^1 \cdot x^{\phi(q) \phi(p) z} \\ &\equiv x \pmod q \end{align*} $\endgroup$ – RVM Dec 29 '11 at 0:54
  • $\begingroup$ The above relation works out because $\phi(q) = q - 1$ and from Fermat's Little Theorem, $x^{q-1} \equiv 1 (\text{mod q}) $ $\endgroup$ – sauravrt Dec 29 '11 at 2:40
5
$\begingroup$

Even if the plaintext $x$ is not pairwise coprime with $p$ or $q$, RSA still works as advertised. Here is why:

$p$ and $q$ are prime, so $x$ is a multiple of either $p$ or $q$, given the restriction that $x < pq$.

Assume that $x \equiv 0 \pmod p$. If it is congruent to $0$ mod $q$ the below still applies, just switch the name assigned to the two primes.

$x^k \equiv 0 \pmod p$ for all $k > 0$, i.e $x^k \equiv x \pmod p$.

$$ \begin{align*} x^{1+ z \phi(n)} & \equiv x^{1+ z \phi(p) \phi(q) } \\ &\equiv x^1 \cdot x^{\phi(q) \phi(p) z} \\ &\equiv x \pmod q \end{align*} $$

Combining both equations with the Chinese Remainder Theorem yields $x$, the plaintext.

|cite|improve this answer
$\endgroup$
5
$\begingroup$

First, the statement should read $x^{\phi(n)}\equiv1\pmod{n}$, not modulo $\phi(n)$. You are right that this assumes that $x$ and $n$ are coprime. Given that $p,q$ are very large primes, the fraction of possible $x$ that is not coprime with $n$ is exceedingly small: $\frac1p+\frac1q-\frac1n$. In fact the security of the method is based on the smallness of this number: if there were any reasonable chance of finding a number $m$ not coprime with $n$ by picking a random number between $0$ and $n$, then one could compute $\gcd(m,n)\in\{p,q\}$ using it, and factor $n$. But formally, the test of coprimality of the plain text $x$ with $n$ should be done by the encoder, just like the test you already assumed that $x\neq0$. In the very unlikely event that coprimality fails, one must add some noise to the plain text.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thank. That clears the doubt that I had. And yes you are right about the modulo being mod n, I'll edit the question. $\endgroup$ – sauravrt Dec 2 '11 at 13:20
4
$\begingroup$

Aside from it being unlikely that $\gcd(x,n) \neq 1$, note that the only possibilities are $\gcd(x,n) \in \{1,p,q,n\}$. Therefore, if $x$ and $n$ are not coprime, the one can decipher the text anyways (since one then knows either $p$ or $q$ and can easily find the other factor, and hence $n$).

In other words, if $x \in \mathbb{Z}/ n \mathbb{Z}$ is not a unit, we know that $$ x^{ED} \equiv x \pmod{n} \Longleftrightarrow \left\{\begin{array}{ccc} x^{ED} \equiv x \pmod{p} \\ x^{ED} \equiv x \pmod{q} \end{array} \right\}. $$

Hope this helps.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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