Cracking RSA Small Public Exponents: Cube-Root Recovery and Low-Exponent Bias

Why This Matters

In 2012, researchers scanning the public internet discovered that a significant fraction of TLS and SSH public keys shared prime factors due to entropy failures during key generation — but the small-exponent class of attacks predates that finding by decades. The most historically significant demonstration occurred when it became clear that several smart-card and embedded device PKI implementations used e=3 without padding in order to minimise the cost of modular exponentiation on constrained hardware. When RSA with e=3 is used to encrypt short messages without randomised padding, an attacker who intercepts even a single ciphertext can recover the plaintext using nothing more than integer arithmetic. Hastad's 1985 broadcast attack extended this to cases where the plaintext is longer than n^(1/e), requiring only e ciphertexts to the same message under different public keys. CVE-2006-4339 and the PKCS#1 v1.5 signature forgery work by Bleichenbacher (1998) are downstream consequences of the same root cause: insufficient randomness injected before RSA encryption.

Core Concept

RSA encryption computes ciphertext c = m^e mod n, where m is the message, e is the public exponent, and n is the modulus. The security of RSA in the standard model relies on the hardness of the RSA problem (recovering m from c, e, n), which in turn rests on the assumption that m^e mod n wraps around the modulus — i.e., that m^e > n.

When e=3 and m is a short message (for example, a 128-bit session key padded to a 256-bit block inside a 2048-bit modulus), the condition m^3 < n can easily hold. In that case the modular reduction is a no-op: c = m^3 exactly as an integer. An attacker computes the integer cube root of c with gmpy2.iroot(c, 3) and recovers m in O(log n) time. No factoring, no discrete log — just arithmetic.

Hastad's broadcast attack generalises this. Suppose the same plaintext m is encrypted to e=3 distinct recipients, each with a different modulus n_1, n_2, n_3, and each ciphertext c_i = m^3 mod n_i. By the Chinese Remainder Theorem (CRT), given c_1, c_2, c_3 the attacker can reconstruct a unique integer M such that M ≡ c_i (mod n_i) for all i, and M < n_1·n_2·n_3. Because m < each n_i, we have m^3 < n_1·n_2·n_3, so M = m^3 exactly as an integer. Taking the integer cube root of M recovers m. The attack requires exactly e ciphertexts for exponent e (3 for e=3, 5 for e=5, etc.).

The attack precondition is: (1) same message m encrypted under e different keys with the same small e, and (2) no randomised padding (or padding that is identical across recipients, which collapses the security to the same level). OAEP (Optimal Asymmetric Encryption Padding) prevents both attacks by prepending a random seed before encryption, ensuring that two encryptions of the same message produce computationally independent ciphertexts.

Technical Deep-Dive

# RSA small-exponent attack with gmpy2
# Prerequisites: pip install gmpy2 pycryptodome

import gmpy2

# --- Attack 1: Direct cube root (e=3, no padding, m^3 < n) ---
# c = m^3 as a plain integer (no modular reduction occurred)
# n and c are given in the challenge; e = 3

n = int(input("Enter n (hex or dec): "), 0)
c = int(input("Enter c (hex or dec): "), 0)
e = 3

m, exact = gmpy2.iroot(c, e)
if exact:
    print("[+] Cube root is exact — m =", m)
    print("[+] Plaintext bytes:", m.to_bytes((m.bit_length() + 7) // 8, 'big'))
else:
    print("[-] Not exact — message was likely >= n^(1/3); try Hastad broadcast")

# --- Attack 2: Hastad broadcast attack (e=3, three ciphertexts) ---
from sympy.ntheory.modular import crt

# Three (modulus, ciphertext) pairs — same message, same e=3
pairs = [
    (n1, c1),   # fill in actual values
    (n2, c2),
    (n3, c3),
]

moduli    = [p[0] for p in pairs]
residues  = [p[1] for p in pairs]

# CRT: find M such that M ≡ c_i (mod n_i)
# sympy crt returns (remainder, modulus)
M_mod, M_lcm = crt(moduli, residues)
M = int(M_mod)

m_candidate, exact = gmpy2.iroot(M, e)
if exact:
    print("[+] Broadcast attack succeeded — m =", m_candidate)
    raw = m_candidate.to_bytes((m_candidate.bit_length() + 7) // 8, 'big')
    print("[+] Plaintext bytes:", raw)
else:
    print("[-] Cube root not exact — verify all three ciphertexts use same plaintext")

# RsaCtfTool one-liner (handles small_e automatically)
python3 RsaCtfTool.py -n <N> -e 3 --uncipher <C> --attack small_e

# For broadcast attack with RsaCtfTool:
python3 RsaCtfTool.py --publickey key1.pem key2.pem key3.pem 
    --uncipher c1.bin c2.bin c3.bin --attack hastad

Cryptanalysis Methodology

1. Extract public key parameters — Parse the PEM or DER key with openssl rsa -pubin -text -noout -in key.pem. Confirm e=3 (or another small value such as 5, 17, 65537 — only the first three are dangerous without padding).
2. Check for exact integer root — Compute gmpy2.iroot(c, e). If exact=True, the attack is complete immediately. This succeeds when the plaintext is short relative to n.
3. Collect broadcast ciphertexts — If the direct root fails, gather e ciphertexts encrypting the same message under e different moduli. Challenge descriptions typically provide all required pairs.
4. Apply CRT then root — Use sympy.ntheory.modular.crt or SageMath's built-in CRT to compute M mod (n_1·n_2·...·n_e), then call gmpy2.iroot(M, e).
5. Automate with RsaCtfTool — Run --attack small_e and --attack hastad for robustness; RsaCtfTool also handles partial padding recovery via Coppersmith's method for cases where m^e slightly exceeds n.
6. Verify the recovered plaintext — Strip PKCS#1 v1.5 or custom padding bytes (0x00 0x02 ... 0x00 prefix) to isolate the actual message content.

Secure Implementation Note — Always use RSAES-OAEP (RFC 8017) for RSA encryption. OAEP's randomised mask generation function ensures m^e always reduces mod n regardless of message size, and eliminates all known small-exponent attacks. In Python: from Crypto.Cipher import PKCS1_OAEP. Never use textbook (unpadded) RSA in production.

Common Cryptanalysis Errors

• Confusing e=65537 with e=3 — e=65537 (0x10001) is the standard secure choice; attacks here apply only to e=3, e=5, or other small values. Always read the key parameters before attempting.
• Forgetting integer vs modular cube root — pow(c, gmpy2.invert(3, phi_n), n) only works if you know phi(n). The attack uses the integer cube root of c, not the modular inverse.
• Applying CRT to ciphertexts with different plaintexts — Hastad's attack requires the identical plaintext m under all e moduli. Different messages, even slightly different, break the attack completely.
• Overlooking Coppersmith variants — When m^e is only slightly larger than n, the direct integer root will fail (not exact), but Coppersmith's method (lattice-based) can still recover m. RsaCtfTool's --attack coppersmith handles this.
• Not stripping padding before interpreting the result — Raw RSA output may include PKCS#1 padding bytes; the actual plaintext begins after the 0x00 separator byte.
• Assuming the challenge uses e=3 literally — Some challenges obfuscate by encoding e differently or splitting it across multiple fields. Always decode the DER structure directly.

NICE Framework Alignment

Further Reading

• Hastad, J. (1988). Solving simultaneous modular equations of low degree — SIAM Journal on Computing
• Boneh, D. (1999). Twenty Years of Attacks on the RSA Cryptosystem — Notices of the AMS
• RFC 8017: PKCS #1 RSA Cryptography Specifications Version 2.2 — IETF