What are the minimum constraints on RSA parameters and why?

Question

The RSA cryptosystem only works if certain constraints are applied to its input parameters. Some of those constraints are made to make it "hard" to determine the private key whereas other constraints are there to make the mathematics work. I want to understand the latter category of constraints and why they exist.

Here is what I have so far....

• The public exponent $e$ and the modulus $n$ should be $e<\phi(n)$. It can be larger but there is no benefit because $e$ is congruent $\mod\phi(n)$.
• There are no other restrictions on $n$ (the use of $n$ with prime factors $p$ and $q$ is just to make the problem "hard").
• The public exponent $e$ must be $0<e<n$.
• In practice and because of the above, $n>1$.
• $e$ does not need to be prime but it should be coprime with $\phi(n)$ (see next point). It does not need to be coprime with $n$ but it doesn't matter if it is. It is usual for $e$ to be chosen from the Fermat Primes, usually $65537$ in real applications.
• $e$ and $\phi(n)$ must be coprime to satisfy, for the private key $d$, that $ed\equiv 1\pmod{\phi(n)}$ if, by Euler's Totient Theorem and Bezout's Identity, $ed+k\phi(n)=1$ (where $k$ is a quotient of no relevance and can be any integer; $k$ and $d$ are computed from $e$ and $\phi(n)$ by the Extended Euclidean Algorithm).
• The message $m$ (both the plaintext and the ciphertext) must be coprime with $n$ so that, by Euler's Totient Theorem, $m^{\phi(n)}\equiv 1\pmod n$. However, $m$ does not need to be coprime with $\phi(n)$ but it doesn't matter if it is.

I have read elsewhere that any $m$ should work, like this question explains, but that contradicts the last constraint and I've experienced that the algorithm somtimes fails without this.

I have a little program that evaluates the algorithm with some small numbers ($n$ < 20 bits). I find it breaks occasionally and, when it does, I find that $m$ and $n$ are not coprime.

I believe the minimum constraints are those that I've listed above. I'd like to understand whether I have it right or if I'm missing anything. If it should work for all $m$ there must be a reason why I find to the contrary.

Update

$m$ does not need to be coprime with $n$ but $gcd(m,n)$ must be coprime with $n/(gcd(m,n)$ but I don't understand why this is the case.

Optimisations can be performed if the factors, $p$ and $q$, of $n$ are known. They aren't necessary but can help improve decryption performance where $d$ is large. They are:

• The reduced totient $\lambda(n)$, or Carmichael Function, can be used instead of Euler's Totient so, in the above, $\phi(n)$ can be replaced with $\lambda(p,q)$. This gives a smaller value for $d$ (and demonstrates that there are multiple $d$ values for a given $e$).

• It's possible to use the Chinese Remainder Theorem (CRT) to break the ciphertext into two smaller parts so that two smaller exponents can be computed instead of one based on a large $d$. A good explanation of this technique is here.

When generating the private key, the CRT coefficients $dp$, $dq$ and $qinv$ (the inverse of $q\mod p$) can be precomputed and would form part of the private key. They are then used in decryption instead of $d$.

I don't understand why $\lambda(p,q)$ works and I've found that CRT only works when $p>2$ and $q>2$. The reason for this isn't clear but I think it is because a CRT coefficients when $p$ or $q$ is 2 will be taken modulo 1 which is always zero.

Answer 1

One does not need ​ e < n .
One does not need $\;\; e\hspace{-0.03 in}\cdot \hspace{-0.03 in}d \: \equiv \: 1 \;\; \pmod{\phi(n)} \;\;\;\;\;$;
one just needs that congruence modulo λ(n).
(Being coprime with $\phi$(n) is equivalent to being coprime with λ(n).)
Neither the plaintext nor the ciphertext need to be coprime with n.
gcd(m,n) must be coprime with n/(gcd(m,n)).

That last condition will be automatic when n is square-free, since it's equivalent to
"If m≠0 then for every prime factor p of n, p's multiplicity as a
factor of m is either 0 or equal to p's multiplicity as a factor n.".
When the quote holds, for each maximal-prime-power factor q of n,
m's remainder mod q will be either 0 or a coprime to q.
When the former case applies, it will continue applying to all positive powers of m.
When the latter case applies:

By Fermat's Little Theorem, $\;\;\; m^{\hspace{.02 in}\phi(q)} \equiv 1 \: \pmod{q} \:\:\:\:$.
For all non-negative integers k,
$m^{(k\cdot \phi(q))\hspace{.02 in}+1} \: \equiv \: m^{\hspace{.02 in}k\cdot \phi(q)} \cdot m^1 \: = \: m^{\hspace{.02 in}\phi(q) \cdot k} \cdot m \: =$
$\left(\hspace{-0.03 in}m^{\hspace{.02 in}\phi(q)}\hspace{-0.06 in}\right)^k \cdot m \: \equiv \: 1^k \cdot m \: = \: 1\cdot m \: = \: m \;\;\; \pmod{q} \;\;\;\;\;\;\;\;$.
λ(n) is a positive integers multiple of $\phi$(q), so for all
non-negative integers $k$, $\;\;\; m^{(k\cdot \lambda(n))\hspace{.02 in}+1} \equiv m \: \pmod{q} \:\:\:\:$.


Thus, when the quote holds, one will have $\;\;\; m^{(k\cdot \lambda(n))\hspace{.02 in}+1} \equiv m \: \pmod{q}$
for each maximal-prime-power factor q of n and each non-negative integer k.
Therefore, by the Chinese Remainder Theorem, when the quote holds one
will have $\;\;\; m^{(k\cdot \lambda(n))\hspace{.02 in}+1} \equiv m \: \pmod{n} \;\;\;$ for all non-negative integers k.