44
$\begingroup$

I decided to read the original RSA paper A Method for Obtaining Digital Signatures and Public-Key Cryptosystem because of a question I had about RSA (which is not the question I'm about to ask, but may be a question on here at some time) and came across something I had never seen before in any textbook description of RSA (Note: this comes from the beginning of Section VI of the paper).

for any integer (message) $M$ which is relatively prime to $n$, $M^{\phi(n)} \equiv 1\pmod{n}$

The part I don't recall ever hearing in class, or coming across in a text book, or seeing in any description of RSA I've ever read is that $M$ and $n$ must be relatively prime.

So, I decided to play around with a toy example of RSA to see what would happen. I use $p=13$, $q=31$, $e=7$ and $M=2p=26$ (for completeness: $d=103$, $\phi(n)=360$, $n=403$).

I observed the following using my toy instance of RSA: $M^e\equiv M\pmod{n}$, $M^e\equiv 0\pmod{p}$ and $M^e\equiv M\pmod{q}$.

Do these equivalences hold for all $M,p,q$ when $M$ and $n$ are not relatively prime? How would I prove this? What is the real-world effect of this?

$\endgroup$
2
  • 1
    $\begingroup$ And an interesting one for you Can RSA be used to encrypt p? $\endgroup$
    – kelalaka
    Feb 8, 2022 at 22:30
  • 1
    $\begingroup$ Consider that the security of RSA holds under the assumption that the message is random in whatever the message space is, ask yourself the probability that a random message in $[0,n)$ is not in $\mathbb Z_n^*$, and you'll see why we live with this ambiguity in the definition of RSA. $\endgroup$ Feb 9, 2022 at 6:53

6 Answers 6

43
$\begingroup$

Yes, (textbook) RSA works for any message $M \in \{0\dots n-1\}$, in the sense that the decryption procedure recovers the original message; that is $\left((M^e\bmod n)^d\bmod n\right)=M$. For this to hold, we need to assume $p\ne q$, a requirement not formally stated in R.L. Rivest, A. Shamir, and L. Adleman's A Method for Obtaining Digital Signatures and Public-Key Cryptosystem, but true with overwhelming odds given the method suggested to generate $p$ and $q$, and always true when following the recommendation given that $p$ and $q$ differ in length by a few digits.

An easy proof is to consider $Z=\left(M^e\right )^d-M$; show $Z\equiv 0\pmod p$ and $Z\equiv 0\pmod{q}$, by using Fermat's Little Theorem and the assumed relation between $e,d,p,q$ (see detailed proof below); then, since $p$ and $q$ are distinct and prime, and divide $Z$, their product $n$ divides $Z$; thus $Z\equiv 0\pmod{n}$. Q.E.D., thanks K.G.

Note: in general, $M^e\equiv M\pmod{n}$ does not hold.

Note: if $p=q$, the cryptosystem is totally unsafe. Independently, those rare $M$ that are a non-zero multiple of $p$ are modified by encryption followed by decryption.


Detailed proof (following another question): we want to show that $Z=\left(M^e\right )^d-M$ verifies $Z\equiv0\pmod p$, that is $\left(M^e\right )^d-M\equiv 0\pmod p$, that is $M^{e\cdot d}\equiv M\pmod p$. Since $d$ and $e$ are integers greater than $1$, this holds if $M\equiv0\pmod p$; it remains to prove it only when $M\not\equiv0\pmod p$, which we assume in the following.

The original RSA article constructs $d$ and $e$ with $e\cdot d\equiv1\pmod{\phi(n)}$, where $\phi$ is the Euler totient, also noted $\varphi$; while modern expositions of RSA, including PKCS#1 of RSA Security, often use $e\cdot d\equiv1\pmod{\lambda(n)}$, where $\lambda$ is the Carmichael function. We hypothesized that $p$ and $q$ are distinct primes, thus $\phi(n)=(p-1)\cdot(q-1)$, and $\lambda(n)=\operatorname{lcm}(p-1,q-1)$. Thus $p-1$ divides $\phi(n)$ and $\lambda(n)$, and for either construction of $d$ and $e$ it holds that $e\cdot d\equiv1\pmod{(p-1)}$. Since $e$ and $d$ are integers greater than $1$, it therefore exists a positive integer $k$ with $e\cdot d=k\cdot(p-1)+1$.

We can thus write $M^{e\cdot d}$ as $M^{k\cdot(p-1)+1}=\left(M^{p-1}\right)^k\cdot M$. By Fermat's Little Therorem, since $p$ is prime and $M\not\equiv0\pmod p$, it holds that $M^{p-1}\equiv1\pmod p$. It follows that $M^{e\cdot d}\equiv M\pmod p$.


Addition following comment: RSA is sometimes presented in $\Bbb{Z}_n^*$ because:

  1. The early version of Rivest, Shamir, and Adleman's paper did.
  2. As pointed there, that's not a serious practical limitation because so few messages are excluded.
  3. That removes any hypothesis on $n$ and thus makes the proof simpler; by contrast, we need a square-free $n$ in order for RSA to work in $\Bbb{Z}_n$.
$\endgroup$
4
  • 3
    $\begingroup$ One really minor nitpick: Don't use CRT. It is sufficient to note that if $p$ and $q$ both divide $Z$, then $pq$ divides $Z$. $\endgroup$
    – K.G.
    Feb 14, 2014 at 9:55
  • $\begingroup$ my question is, why is RSA presented sometimes in $\mathbb{Z}_n^*$? $\endgroup$ Jan 28, 2019 at 22:53
  • $\begingroup$ In the case in which $M \equiv 0 \pmod p$, from $M^{ed} \equiv M \pmod p$ (which is basically saying $0 \equiv 0$, if I understand correctly), how do we conclude $M^{ed} \equiv M \pmod n$? Don't we also need $M \equiv 0 \pmod q$ for that? $\endgroup$
    – Anakhand
    Jan 23, 2021 at 19:13
  • 1
    $\begingroup$ @Anakhand: No we don't also need $M\equiv0\pmod q$. The proof considers $Z=\left(M^e\right )^d-M$; proves (using two branches, depending on if $M\equiv0\pmod p$ or not) that $Z\equiv0\pmod p$, that is $p$ divides $Z$; similarly proves (using two branches, depending on if $M\equiv0\pmod q$ or not) that $q$ divides $Z$; then since $p$ and $q$ are coprime, concludes that $n=p\,q$ divides $Z$. $\endgroup$ Jan 23, 2021 at 20:29
17
$\begingroup$

By the Chinese Remainder Theorem, RSA "works" as long as it works modulo $p$ and modulo $q$; i.e. that $(M^e)^d = M$ modulo $p$ and modulo $q$. If $M$ is not relatively prime to $p$ then $p$ divides $M$ (because $p$ is prime); in that situation, that equation becomes $0 = 0$, which holds.

Even if it did not work for any $M$, it would not be a problem, because finding a $M$ between 1 and $n-1$ and not relatively prime to $n$ is equivalent to factoring $n$, and factoring $n$ is meant to be very hard. But anyway, RSA still works for those integers.

$\endgroup$
3
  • $\begingroup$ Do you know where I can find the reductions between finding $M$ not relatively prime to $n$ and factoring? $\endgroup$
    – mikeazo
    Oct 20, 2011 at 22:12
  • 3
    $\begingroup$ @mikeazo: that's easy: if $M$ is not relatively prime to $n$, then a simple GCD between $M$ and $n$ reveals a factor of $n$. In the other direction, if you can factor $n = pq$ then $M = xp$ for any $1 < x < q$ is an integer which is smaller than $n$ but not relatively prime to $n$. $\endgroup$ Oct 20, 2011 at 22:22
  • $\begingroup$ yeah that was easy and once I read it I thought "Yeah I should have known that!" Thanks. $\endgroup$
    – mikeazo
    Oct 20, 2011 at 22:26
10
$\begingroup$

Yes, RSA works for every M. Remember Fermat's Little Theorem:

$x ^ p = x \mod p$ (for all $x$, and all prime $p$).

A bit of induction gives this simple extension:

$a = 1 \mod p-1$ implies $x ^ a = x \mod p$ (for all $x$ and all prime $p$).

Now, we know that $d$ and $e$ are related by:

$d·e = 1 \mod lcm(p-1,q-1)$

Because $p-1$ is a factor of $lcm(p-1, q-1)$ this implies

$d·e = 1 \mod p-1$

and hence

$M ^ {d·e} = M \mod p$

By symmetry, this also implies

$M ^ {d·e} = M \mod q$

and so, by the Chinese Remainder Theorem (and because $p$ and $q$ are relatively prime):

$M ^ {d·e} = M \mod p·q$

$\blacksquare$

$\endgroup$
2
  • $\begingroup$ Could you justify why $p-1$ dividing $lcm(p-1,q-1)$ and $d \cdot e \equiv 1 \mod lcm(p-1,q-1)$ implies $d \cdot e \equiv 1 \mod p-1$? We cannot apply the chinese remainder theorem, since if both primes are greater than 2, $p-1$ and $q-1$ are even, and thus $p-1$ and $q-1$ aren't coprime. Am I missing something? $\endgroup$
    – ambiso
    Jan 5, 2019 at 18:43
  • 1
    $\begingroup$ @ambiso: the statement $x \equiv y \pmod z$ is equivalent to the statement that there exists an integer $k$ such that $x - y = zk$. Hence, $de \equiv 1 \pmod{lcm(p-1,q-1)}$ implies there exists a $k$ s.t. $de - 1 = k \cdot lcm(p-1,q-1)$, and because $lcm(p-1, q-1) = (p-1) k'$ (where $k'$ is the integer $(q-1) / \gcd(p-1,q-1)$, we have $de -1 = (k k')(p-1)$, as $k k'$ is an integer, this means that $de \equiv 1 \pmod{p-1}$ $\endgroup$
    – poncho
    Jan 5, 2019 at 20:11
6
$\begingroup$

I've found an nice explanation with example on Udacity so I will copy the post a bit modified and formatted.

Taking an example of RSA with numbers small enough to reason with:

primes $p_1=11$, $p_2=13$ $N = p_1 \times p_2 = 143$
$\phi(N) = (p_1-1) \times (p_2-1) = 120$
$e = 7$ // chosen to be relatively prime to $\phi(N)$ so it has an inverse
$d = 103$ // derived from $e$ and $\phi(N)$ by extended Euclidean algorithm
$e \times d = 721 = 6 \times \phi(N) + 1 = 1 \pmod{\phi(N)}$

As it happens, for any $i \in [0,142]$, $i^{721} \pmod{143} = i$. That's a good thing, because decryption wouldn't work otherwise.

For a number that's relatively prime to the modulus, that's explainable by Euler's theorem -$x^{\phi(N)}= 1 \pmod{N}$ - and taking those powers out of the equation leaves you with $x$ by itself.

For a number like $26$ that has a common factor with the modulus, the encryption/decryption happens to work in this example: $26^{721} \pmod{143} = 26 \pmod{143}$. But it's not explainable by the Euler's theorem, since $gcd(26,143)=13$.

So why does this work? Should it work? Does RSA require it to work?

Forget about Euler's theorem - it looks promising but it's a dead end in this case.
We'll use Fermat's little theorem.
We also need to use the following fact
$a \equiv b \pmod{p_1}$ and $a \equiv b \pmod{p_2} \Rightarrow a \equiv b \pmod{p_1\times p_2}$. Let's call that FACT X.
Remember that $e\times d = 1 \pmod{\phi{N}} \Leftrightarrow e\times d - 1 = k\times(p_1-1)\times(p_2-1) \Leftrightarrow e\times d -1 = 6(11-1)(13-1)$.
The $(p_1-1)$ and $(p_2-1)$ parts of the equation will be eaten by Fermat's theorem.

$m^{ed}=m^{ed−1} \times m=m^{k(p1−1)(p2−1)}\times m$
If $m \equiv 0 \pmod{p_1}$, then Fermat's little theorem doesn't apply. But $m ^{ed} \equiv 0 \pmod{p_1}$.
Example: $22 \equiv 0 \pmod{11}$. $22^{721} \equiv 0 \pmod{11}$.
If $m \neq 0 \pmod{p_1}$, then Fermat does apply (we're working in $\pmod{p_1}$ here): $m^{ed}=m^{k(p_1−1)(p_2−1)}\times m=(m^{(p_1−1)})^{k(p_2−1)}\times m=1^{k(p_2−1)}m=m$.
The two cases above give us the result that $m^{ed} \equiv m \pmod{p_1}$.
Apply the same reasoning for $p_2$.
Then use FACT X above to show that $m^{ed} \equiv m \pmod{p_1 \times p_2}$.

Back to the example:

$m^{ed}=m\times m^{ed−1}= m\times m^{720}=m\times m^{6\times 10\times 12}=m\times(m^{10})^{72}=m\times(m^{12})^{60}$. So if $gcd(m,11)=1$, then Fermat shows that taking $m^{ed} \pmod{11}$ is like multiplying by $1$. If $gcd(m,11)\neq 1$, then you're multiplying $0 \pmod{11}$ and end up with zero.

Similarly for mod 13.

And then FACT X combines the two and shows that taking $m^{ed}$ leaves the message unchanged $\pmod{11\times 13}$.

$\endgroup$
2
  • $\begingroup$ It's nice that you care and downvote when someone does not comply the rules, but when I update my answer you should remove the punishment. $\endgroup$
    – Pio
    Nov 9, 2013 at 11:30
  • 5
    $\begingroup$ I agree. That said, just wanted to make you aware that SE does not notify downvoters when you edit. I'm assuming that is the reason why some have not changed their vote. Could be a nice feature though. $\endgroup$
    – mikeazo
    Nov 12, 2013 at 13:52
3
$\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.

$\endgroup$
0
2
$\begingroup$

The RSA cryptosystem will still work if $m$ shares a common factor with $n$.

To see this, suppose that $p|m$. Then $c\equiv m^e\equiv 0\pmod p$ and $c^d\equiv 0\equiv m\pmod p$. We see that the $(m^d)^e\equiv m$ property holds for all prime factors of $n$ irrespective of whether or not they divide $m$ and hence $(m^d)^e\mod n$ holds irrespective of whether or not $m$ is coprime to $n$. For cryptographic $n$ it is of course highly unlikely that $m$ is not coprime to $n$.

$\endgroup$
0

Your Answer

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

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