Issues with Euler’s Totient Function in RSA 관련

The Cryptography Handbook: Exploring RSA PKCSv1.5, OAEP, and PSS

---

The RSA algorithm was introduced in 1978 in the seminal paper, ”A Method for Obtaining Digital Signatures and Public-Key Cryptosystems”. Over the decades, as RSA became integral to secure communications, various vulnerabilities and attacks have emerg...

---

The Cryptography Handbook: Exploring RSA PKCSv1.5, OAEP, and PSS

The RSA algorithm was introduced in 1978 in the seminal paper, ”A Method for Obtaining Digital Signatures and Public-Key Cryptosystems”. Over the decades, as RSA became integral to secure communications, various vulnerabilities and attacks have emerg...

While using Euler’s Totient Function works well in theory, implementers of the scheme realized its practical downsides. Simply put, the primary issue was that Euler’s Totient Function can lead to a larger private exponent $d$ than what was necessary.

To completely appreciate this fact, let’s take a step back to understand why the size of the private exponent $d$ matters in RSA.

RSA decryption (or signing) involves computing $m^{d}\:\text{mod}\:n$ which is done via modular exponentiation. The time complexity of exponentiation algorithms (like square-and-multiply) grows with the number of bits in $d$. A larger $d$ means more multiplications and squarings, that is slower decryption.

In practice, if using the Euler’s Totient Function makes $d$ roughly twice as large as what is required, then decryption can be almost twice as slow compared to using the minimal $d$. This inefficiency is especially noticeable when $e$ is small (common public exponents like $3$ or $65537$). A small e leads to a very large $d$ under $\phi\left(n\right)$.

Beyond performance, having an unnecessarily large $d$ can increase storage size slightly (a few more bytes for the key). This can also lead to interoperability quirks, which is why standards and protocols such as FIPS 186-4^[1] and RFC 8017^[2] expect $d$ to be below a certain size. We will take a detailed look at this in the next section.

To combat these issues, cryptographers utilized the Carmichael function to generate RSA keys. Before we dive into how the Carmichael function helps our case, let’s quickly understand what the Carmichael function actually is.

---

1. FIPS 186-5: Digital Signature Standard (DSS) ↩︎

2. RFC 8017 PKCS #1: RSA Cryptography Specifications ↩︎