1
$\begingroup$

I'm a high school student taking IB and I'm doing my EE on Maths, more specifically on the effectiveness of Euler's totient function and Carmichael's totient function in RSA.

  1. Am I right in thinking that Euler's and Carmichael's can be used interchangeably to generate the public key in RSA?
  2. To compare their 'effectiveness' I will first compare the amount of time it takes to generate a public key using each function based on time complexity. Secondly, I want to compare the security of the public key (meaning 'how difficult it is to guess the private key given the public key'). But how? Is there an algorithm to use to test the security of an encryption key?

Many thanks!

$\endgroup$
2

1 Answer 1

5
$\begingroup$
  1. Am I right in thinking that Euler's and Carmichael's can be used interchangeably to generate the public key in RSA?

Yes. The requirement is that the public exponent $e$ have an inverse modulo $\phi(n)$ or $\lambda(n)$, whichever you use—and the two numbers share prime factorization, differing only in multiplicity, so $e$ is coprime with $\phi(n)$ iff $e$ is coprime with $\lambda(n)$.

  1. To compare their 'effectiveness' I will first compare the amount of time it takes to generate a public key using each function based on time complexity. Secondly, I want to compare the security of the public key (meaning 'how difficult it is to guess the private key given the public key'). But how? Is there an algorithm to use to test the security of an encryption key?

There is no algorithm to test the security of a particular key. There is literature on the security of systems for generating keys, though—and for RSA keys there are many such systems[1], with some pitfalls if you're not careful about using the fancy ones[2].

However, this is all about generation of the prime factors. The public exponent $e$ should be a fixed constant like 3 or 65537; then the private exponent $d$ solves either $e\cdot d \equiv 1 \pmod{\phi(n)}$ or $e\cdot d \equiv 1 \pmod{\lambda(n)}$. If you use $\phi(n)$, $d$ might be larger, so the private key operation costs more to do the same thing. That is, the only difference the choice of $\phi(n)$ vs. $\lambda(n)$ makes is efficiency of the private key operation.

$\endgroup$
2
  • $\begingroup$ I'm noticing the use of the word 'cost' in many tech-y writings... What does that mean? $\endgroup$
    – dkssud10
    May 19, 2019 at 5:28
  • $\begingroup$ "e is coprime with ϕ(n) iff e is coprime with λ(n)." Not sure this is true. ϕ(n) is a multiple of λ(n), so it could have factors that λ(n) doesn't. If those are factors of e as well, then e is coprime to λ(n) but not to ϕ(n). $\endgroup$
    – nog642
    Nov 21, 2021 at 20:36

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