RSA Attacks: Common Weaknesses

TL;DR

RSA is generally secure, but attacks are possible if certain conditions aren’t met. This guide covers common weaknesses like small exponents, predictable moduli, and related-message attacks. We’ll show you how these work and what to do to prevent them.

1. Small Exponent Attacks (e = 3)

If the public exponent ‘e’ is too small (like e=3), RSA becomes vulnerable. This is because calculating the cube root of a ciphertext can be easier than factoring the modulus, especially if the message ‘m’ is also small.

• How it works: If you know the ciphertext ‘c’, and ‘e’ is 3, then m = c^1/3.
• Prevention: Always use a sufficiently large exponent (e.g., 65537). This makes cube root calculations impractical.

# Example of calculating the cube root in Python (for demonstration only - not secure)
m = round(c**(1/3))

2. Common Modulus Attacks

If multiple parties use the same modulus ‘n’ but different exponents, an attacker can potentially recover messages.

• How it works: If two users share the same modulus ‘n’, and you intercept their ciphertexts (c₁ and c₂) encrypted with exponents e₁ and e₂, you might be able to calculate m = c₁^e₂ * c₂^-e₁ mod n.
• Prevention: Each user must generate their own unique modulus ‘n’. Never reuse moduli.

3. Wiener’s Attack

Wiener’s attack exploits RSA when the private exponent ‘d’ is too small relative to the modulus ‘n’.

• How it works: This involves using continued fractions to find convergents that approximate d/n, and then testing if these approximations are valid.
• Prevention: Ensure ‘d’ is large enough compared to ‘n’. A rule of thumb is d > n^1/4.

# This attack requires specialized libraries and is complex.
# It's not easily demonstrated with a simple code snippet.

4. Related-Message Attacks

If an attacker can get RSA to encrypt related messages (e.g., m and m+1), they can sometimes recover the message.

• How it works: If you know c₁ = m^e mod n and c₂ = (m+1)^e mod n, then you might be able to solve for ‘m’.
• Prevention: Avoid encrypting related messages. Use padding schemes like OAEP (Optimal Asymmetric Encryption Padding) which introduce randomness and prevent these attacks.

# Example of a simple related message attack (for demonstration only - not secure)
# Assuming e=3 and small m values.
c1 = pow(m, 3, n)
c2 = pow(m+1, 3, n)
# From these you can potentially solve for m

5. Low Encryption Exponent Attacks (e < 4)

Using a very small encryption exponent ‘e’ (less than 4) is highly insecure.

• How it works: If e=2, c = m² mod n, so m = sqrt(c) mod n. Even with larger values of e, if the message ‘m’ is small enough that m^e < n, you can directly calculate 'm'.
• Prevention: Always use a sufficiently large exponent (e.g., 65537).

# Example of calculating the square root in Python (for demonstration only - not secure)
m = round(c**(1/2))

6. Hastad’s Broadcast Attack

If RSA is used to encrypt the same message ‘m’ with multiple different moduli ‘n_i‘, an attacker can recover ‘m’.

• How it works: The Chinese Remainder Theorem (CRT) can be used to reconstruct ‘m’ from the set of ciphertexts c_i = m^e mod n_i.
• Prevention: Never encrypt the same message with multiple different moduli. Use padding schemes like OAEP.