1
$\begingroup$

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 ?

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

1 Answer 1

1
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – Eric
    Jan 10, 2023 at 17:29
  • $\begingroup$ I think the above is true, since λ(21) = 6, λ(3) = 2, λ(7) = 6, thus λ(21) != λ(3) * λ(7). $\endgroup$
    – Eric
    Jan 10, 2023 at 17:35
  • 1
    $\begingroup$ @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)$. $\endgroup$
    – fgrieu
    Jan 10, 2023 at 18:02
  • $\begingroup$ Ok, λ(n)=φ(n)/gcd(p−1,q−1) works for n = 21. $\endgroup$
    – Eric
    Jan 10, 2023 at 18:59
  • 1
    $\begingroup$ @Eric: see final section. $\endgroup$
    – fgrieu
    Jan 11, 2023 at 10:26

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.