I'm trying to understand the RSA cryptosystem, these are the steps:
- Generate two large different prime numbers $p$ and $q$.
- Calculate modulus $n$ ($n=pq$)
- Calculate: $λ(n) = \operatorname{lcm}(λ(p), λ(q))$
I'm trying to understand the step 3. As we know, the original RSA document uses Euler's Totient Function - $\phi(n) = (p-1) \cdot (q-1)$ (which outputs the amount of numbers that are coprime to $n$).
But, Carmichael's function is smallest positive integer $m$ such that: $$a^m \equiv 1 \pmod n.$$
From my knowledge, $λ(n) \mid \phi(n)$ according to Lagrange's theorem (abstract algebra group theory). Thus that seems to be the only reason why Euler's Totient Function was used in the past, making Carmichael's function more appropriate?
The fourth and fifth step is to create public exponent and modular multiplicative inverse of modulus n as decryption key.
The public exponent must be $e$ such that: $$1 < e < λ(n) \quad\text{and}\quad \gcd(e, λ(n)) = 1.$$
Is the "rule" above necessary? I think I've seen different versions of RSA cryptosystem where large exponents are randomly generated (exceeding output of $λ(n)$).
The private key is found by this congruence: $$d ≡ e^{−1} \pmod{λ(n)}.$$
Meaning, utilization of Extended Euclidean Algorithm is not necessary?
I understand Bézout's identity, Euclid's lemma, Euler's totient function, and multiplicative group of integers modulo $n$ (a little). But what is the easiest explanation for the purpose of Carmichael's function in RSA algorithm?
Thank you!