3
$\begingroup$

I'm trying to understand the RSA cryptosystem, these are the steps:

  1. Generate two large different prime numbers $p$ and $q$.
  2. Calculate modulus $n$ ($n=pq$)
  3. 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!

$\endgroup$
2
  • 1
    $\begingroup$ A few notes: Assuming $p\ne q,$ the Totient function is $\phi(n) = (p-1) \cdot (q-1)$ and not $\phi(n) = \phi(p-1) \cdot \phi(q-1)$. "...is there a reason for public exponent to be less than and coprime to λ(n)?". This is atwo-part question: First, it is not needed that $e < \lambda(n)$, but why spend more time than necessary? Second: $\gcd(e, \lambda(n))=1$ is indeed necessary, otherwise you cannot compute $e^{-1}\pmod {\lambda(n)}.$ $\endgroup$ Dec 28, 2017 at 16:15

1 Answer 1

6
$\begingroup$

You're have everything basically right. Modern RSA-based cryptosystems, as in PKCS#1, do indeed use the Carmichael function. Usually we pick $e = 3$ or $e = 2^{16} + 1$, try a different modulus if $e$ divides $\lambda(n)$, and otherwise use $d \equiv e^{-1} \pmod{\lambda(n)}$.

I'm not sure how you conclude that the extended Euclidean algorithm is not utilized—usually that is how we compute $d$. The EEA, given $e$ and $\lambda(n)$, computes coefficients $c$ and $d$ satisfying Bézout's identity $c\lambda(n) + d e = \gcd(e, \lambda(n)) = 1$, meaning that $d e \equiv 1 \pmod{\lambda(n)}$, or $d \equiv e^{-1} \pmod{\lambda(n)}$. Of course, we require $\gcd(e, \lambda(n)) = 1$ or else $e$ doesn't have an inverse modulo $\lambda(n)$ or $\phi(n)$ at all.

You can use $e > \lambda(n)$ or $d > \lambda(n)$, but it's no different from using $e \bmod \lambda(n)$ and $d \bmod \lambda(n)$, so there's no sense in wasting space for a larger number except in exotic applications. You can also pick $e$ at random, but it offers no security and only hurts performance: roughly, the Hamming weight of $e$ determines the number of multiplications modulo $n$ to compute the public key operation, and $\lfloor\log_2 e\rfloor$ determines the number of squarings modulo $n$ needed to compute it. (Certain exponents may also admit more efficient Lucas chains than the naive square-and-multiply algorithm.)

You want to minimize these because they make up the bulk of the public key operations. Using the fastest option $e = 3$ is perfectly fine for sane RSA-based cryptosystems like RSA-KEM and RSA-FDH signature, and even the standard and fairly widely used RSAES-OAEP and RSASSA-PSS, but people are terrified of $e = 3$ because there are some ways to use RSA stupidly that enable, e.g., decryption or forgery by computing real number cube roots, so $e = 2^{16} + 1$ is a more popular choice. $e = 2$ brings you into the territory of Rabin cryptosystems, which are qualitatively a little different, but have a neat reduction to factorization.

(If you pick $d$ small to speed up the private key operation instead of picking $e$ small to speed up the public key operation, you expose yourself to Wiener's attack.)

$\endgroup$
7
  • $\begingroup$ Thank you! I just don't understand, is there a reason for public exponent to be less than and coprime to λ(n)? Also, i think that i'm failing to understand how private key is calculated, to get the private key, isn't the congruence d≡e^−1(modλ(n)) necessary? $\endgroup$
    – ShellRox
    Dec 28, 2017 at 15:27
  • 1
    $\begingroup$ @ShellRox: The congruence $e\,d\equiv1\pmod{\lambda(n)}$ is necessary and sufficient for $d$ to be a working secret exponent; when $e\,d\equiv1\pmod{\phi(n)}$ is sufficient, but not necessary. That's a reason to use $\lambda$ rather than $\phi$. Setting $d=e^{-1}\bmod\lambda(n)$ yields the smallest possible non-negative $d$. $\endgroup$
    – fgrieu
    Dec 28, 2017 at 16:12
  • $\begingroup$ Now i understand the purpose of Carmichael's function! Thank you! But, if the congruence is used for generating working secret key, then where do we use Extended Euclidean Algorithm? Thank you again @fgrieu $\endgroup$
    – ShellRox
    Dec 28, 2017 at 16:20
  • $\begingroup$ @ShellRox: The Extended Euclidean Algorithm (or a variant) is typically used when computing $d=e^{-1}\bmod\lambda(n)$. On an earlier point: there's no imperative for to $e$ to be less than $\lambda(n)$; but using $e'=e\bmod\lambda(n)$ is equivalent to using $e$, and that $e'$ is less than $\lambda(n)$; thus choosing a random positive $e$ coprime to and less than $\phi(n)$, or a random positive $e$ coprime to and less than $\lambda(n)$, is exactly equivalent when we look at the effect of raising to the $e$ modulo $n$. $\endgroup$
    – fgrieu
    Dec 28, 2017 at 16:25
  • 2
    $\begingroup$ Note that $e=2$ is not valid for RSA because $\gcd(e, \lambda(n))=2.$ $\endgroup$ Dec 28, 2017 at 16:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.