Score:1

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

cn flag

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 ?

fgrieu avatar
ng flag
[updated] Q2 is answered [there](https://crypto.stackexchange.com/q/1004/555). In a nutshell: as long as $p\ne q$, the decryption is OK. This makes Q3 moot.
Score:1
ng flag

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.


Addition following comment

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}$$

Eric avatar
cn flag
According to https://en.wikipedia.org/wiki/Carmichael_function#Computing_%CE%BB(n)_with_Carmichael's_theorem, 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 avatar
cn flag
I think the above is true, since `λ(21)` = 6, `λ(3)` = 2, `λ(7)` = 6, thus `λ(21)` != `λ(3)` * `λ(7)`.
fgrieu avatar
ng flag
@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)$.
Eric avatar
cn flag
Ok, `λ(n)=φ(n)/gcd(p−1,q−1)` works for `n` = `21`.
Eric avatar
cn flag
I know `m ^ λ(n) % n == 1` is a property of `λ(n)`, but where does `m ^ φ(n) % n == 1` come from, since `λ(n)` is not necessary equals to `φ(n)`? In RSA's case they never equal, since `gcd(p-1, q-1)` is at least 2, I guess.
fgrieu avatar
ng flag
@Eric: see final section.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.