# In RSA, what if the message 'm' to be sent equals to one of the 2 prime numbers 'p' and 'q'?

In RSA, one of the math background is:

m ^ φ(n) % n == 1, where m is the message to be sent, n = p * q.

The equation is from λ(n) (Carmichael function), which requires m and n are co-primes.
And, since n = p * q, thus φ(n) = λ(n), I guess. Question 1: is this correct?

Question 2: If m equals p or q, then m and n are not co-primes, in this case, does that means decryption will be wrong, aka. the private key owner can't correctly get original m?

Question 3: But in practice, p and q are very large prime numbers, thus m is very unlikely to be p or q, thus it's fine ?

• [updated] Q2 is answered there. In a nutshell: as long as $p\ne q$, the decryption is OK. This makes Q3 moot.
– fgrieu
Commented Jan 10, 2023 at 9:34

In RSA, one of the math background is:

$$m^{φ(n)}\bmod n = 1$$, where $$m$$ is the message to be sent, $$n=p*q$$.

Yes. More precisely: if $$m$$ and $$n$$ are integers with $$n>1$$ and $$\gcd(m,n)=1$$, then $$m^{φ(n)}\bmod n=1$$, where $$φ$$ is Euler's totient. That's commonly invoked in proof of RSA, including the original RSA article: R.L. Rivest, A. Shamir, and L. Adleman's A Method for Obtaining Digital Signatures and Public-Key Cryptosystem.

The equation is from $$λ(n)$$ (Carmichael function), which requires $$m$$ and $$n$$ are co-primes.

More precisely: $$λ(n)$$ is the smallest positive integer such that if $$m$$ and $$n$$ are integers with $$n>1$$ and $$\gcd(m,n)=1$$, then $$m^{λ(n)}\bmod n=1$$.

since $$n=p*q$$, thus $$φ(n)=λ(n)$$, I guess.

No, that's an incorrect conclusion by analogy. If $$n$$ is an odd composite (as in practice) and not a prime power, then $$φ(n)\neλ(n)$$, and $$φ(n)\,=\,2\,k\,λ(n)$$ for some integer $$k\ge1$$. Many proofs and statements about RSA, including methods for computing a working $$d$$ or $$e$$, can use either $$φ$$ or $$λ$$; the results ($$d$$ or $$e$$) often differ, but remain correct in the sense of allowing decryption. Using $$λ$$ yields a condition on $$(n,e,d)$$ that's necessary, on top of sufficient. The original article uses $$φ$$. Modern standards tend to use $$λ$$ (PKCS#1 allows it, FIPS 186-4 requires it).

If $$m$$ equals $$p$$ or $$q$$, then $$m$$ and $$n$$ are not co-primes, in this case, does that means decryption will be wrong ?

No, unless $$n$$ is divisible by the square of a prime (that is when $$p=q$$ if $$n$$ is the product of primes $$p$$ and $$q$$, as is often considered in RSA). See one of these two questions.

where does $$m^{φ(n)}\bmod n=1$$ come from?

Consider a finite group with group law $$\cdot$$ (multiplicative notation). For any of it's element $$m$$, we can define the order $$\operatorname{ord}(m)$$ of element $$m$$ as the smallest strictly positive integer such that $$\underbrace{m\cdot m\cdot\ldots\cdot m}_{\operatorname{ord}(m)\text{ terms}}$$ is the neutral of the group. By a fundamental theorem due to Lagrange, the order $$\operatorname{ord}(m)$$ of any element $$m$$ in a finite group divides the number of elements in the finite group.

The integers $$m\in[0,n)$$ with $$\gcd(m,n)=1$$ form a finite group under multiplication modulo $$n$$ (that's the multiplicative subgroup $$\mathbb Z_n^*$$ of the finite ring $$\mathbb Z_n$$, which neutral is $$1$$). $$φ(n)$$ is, by definition, the number of such integers $$m$$, thus the number of elements in that finite group. Thus for all $$m$$ in that group, it's defined $$\operatorname{ord}(m)$$ such that $$m^{\operatorname{ord}(m)}\bmod n=1$$, and exist some integer $$\ell$$ (dependent on $$m$$) with $$φ(n)=\operatorname{ord}(m)\,\ell$$. It follows \begin{align} m^{φ(n)}\bmod n&=m^{\operatorname{ord}(m)\,\ell}\bmod n\\ &=\left(m^{\operatorname{ord}(m)}\right)^\ell\bmod n\\ &=1^\ell\bmod n\\\ &=1 \end{align}

• According to en.wikipedia.org/wiki/…, when p != 2 or r >= 3, then λ(p^r) = φ(p^r), make r = 1 then λ(p) = φ(p), [1] I think it's correct until here. Since n = p * q, thus φ(n) = φ(p) * φ(q), but since p != q, thus can't say λ(n) = φ(n), [2] because λ(n) doesn't support multiplication rule, aka. λ(p * q) != λ(p) * λ(q), which I though is true when asking the question. So, can u confirm the [1] and [2] above?
– Eric
Commented Jan 10, 2023 at 17:29
• I think the above is true, since λ(21) = 6, λ(3) = 2, λ(7) = 6, thus λ(21) != λ(3) * λ(7).
– Eric
Commented Jan 10, 2023 at 17:35
• @Eric: One of my statement was wrong in the case of prime powers, thanks for pointing that. It's hopefully fixed. Yes $λ(p^r)=φ(p^r)$ for $p\in\mathbb P$ and $r\in\mathbb N$. Yes if $p$ and $q$ are distinct primes, then $φ(n)=φ(p)\,φ(q)=(p-1)(q-1)$ , and $λ(n)=φ(n)/\gcd(p-1,q-1)$.
– fgrieu
Commented Jan 10, 2023 at 18:02
• Ok, λ(n)=φ(n)/gcd(p−1,q−1) works for n = 21.
– Eric
Commented Jan 10, 2023 at 18:59
• @Eric: see final section.
– fgrieu
Commented Jan 11, 2023 at 10:26