Low-Exponent Attacks 관련

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...

Beyond determinism and malleability exploits, textbook RSA is also vulnerable to Low-Exponent Attacks. Using a small public exponent like $e=3$ (or sometimes $17$) was popular because it used to speed up encryption and signature verification. But this soon turned out to be a security concern.

When RSA uses a small public exponent (say, $e=3$) and the plaintext is very short (so that $M^{3}$ is smaller than the modulus $n$), the encryption does not “wrap around” modulo $n$. Mathematically:

$$\begin{align*} c=M^{3}\:\text{mod}\:n&=M^{3}&&\left(\text{if }M^{3}\lt{n}\right) \end{align*}$$

Let’s understand this with an easy example:

Consider our plaintext to be: $M=5$. We compute $M^{3}$ as $M^{3}=5^{3}=125$. Now assume n is a 4096‑bit number which is large compared to $125$. In this case, the ciphertext is simply $c=125$. Eve intercepting $c=125$ can compute the cube root of $125$ to get the plaintext: $\sqrt[3]{125}=5$ thus recovering $M$ directly.

This shows that if $M$ is small enough, the ciphertext leaks the plaintext when $e$ is low.