0
$\begingroup$

Coming from the Wikipedia page on RSA, I think I understand the following:

RSA is based on generating an integer $n$ as the product of two large primes, $p$ and $q$, and encryption/decryption exponents $e$ and $d$ such that for any given plaintext $m$, $$(m^e)^d \equiv (m^d)^e \equiv m^{ed} \equiv m \mod n\,,$$ i.e. such that modular exponentiation with $e$ (encryption) composed in any order with exponentiation with $d$ (decryption) is the identity mapping on the plaintext.

This works because $e$ and $d$ are chosen such that $$ed \equiv 1 \mod{|m|}$$ for any plaintext $m$, where $|m|$ denotes the order of $m$ in $\mathbb{Z}/n\mathbb{Z}$. This is done by selecting a multiplicative inverse pair $e$, $d$ in the ring of integers mod $\lambda(n)$, where $\lambda$ is Carmichael's totient function; and if I understand correctly the latter is essentially the least common multiple of the orders of all positive integers less than $n$ that are coprime to $n$, so that if $ed \equiv 1 \mod \lambda(n)$ is true then $ed \equiv 1 \mod |m|$ is too for all $m$ coprime to $n$, since $|m| \mid \lambda(n)$.

But what happens if $m$ happens not to be coprime to $n$, i.e. if $m$ is either a multiple of $p$ or of $q$? What guarantees that in this case too the first identity shown above (the encryption-decryption identity) still holds?

I thought along the lines of using Fermat's Little Theorem, i.e. if I could prove that $ed$ was congruent to $p$ mod $\lambda(n)$, then $m^{ed} \equiv m \mod p$. But after some thought, this doesn't seem to lead anywhere.

$\endgroup$
4
  • $\begingroup$ Two dupliactes: 1. Can RSA be used to encrypt p? 2. Does RSA work for any message M? $\endgroup$
    – kelalaka
    Jan 23 '21 at 18:38
  • $\begingroup$ Does something remain unclear after reading this, including the second note? $\endgroup$
    – fgrieu
    Jan 23 '21 at 18:38
  • $\begingroup$ Ah, thanks @fgrieu, I just found that one myself too. This can be closed as duplicate of that. There's just one thing, I don't yet understand how they conclude that. $\endgroup$
    – Anakhand
    Jan 23 '21 at 18:44
  • $\begingroup$ Leave a note (e.g. here or in the other answer) if you don't understand something. Basically, as long as $p\ne q$, nothing special happens from the standpoint of encryption or decryption yielding consistent results if the plaintext $m$ is not coprime to $n$. The proof just needs to consider this special case. Also, it becomes trivial to factor $n$ and decipher for one who realize the plaintext or ciphertext is not coprime to $n$, except if that plaintext or ciphertext is $0$,$1$ or $n-1$. $\endgroup$
    – fgrieu
    Jan 23 '21 at 19:00