Skip to content
Tutorials Center
My learning

Topics

Lesson 31 of 37 ยท Cryptographic Applications

RSA Attacks and Padding

See how textbook RSA breaks: deterministic and malleable ciphertexts, small exponents, shared primes and Wiener's attack, and why padding is essential.

RSA from scratch is a beautiful piece of number theory, but a few lines of arithmetic do not make a secure system. Textbook RSA, the bare c = m^e mod n, has many structural weaknesses. Most real-world failures are not breakthroughs in factoring; they are small mistakes in how RSA is used: reused primes, small exponents, missing padding, or key sizes chosen too short.

This lesson attacks a toy RSA in five ways. Each attack is a few lines of number theory you already know, which is the point: cryptography is applied number theory, and understanding the maths tells you how it breaks. Never mount these attacks on systems you do not own.

Attack 1: determinism and malleability

Textbook RSA is deterministic: the same message always gives the same ciphertext. An eavesdropper who suspects the message is "YES" or "NO" just encrypts both guesses and compares. It is also malleable: since (mโ‚ยทmโ‚‚)^e = mโ‚^e ยท mโ‚‚^e, an attacker who multiplies a ciphertext by 2^e makes the plaintext double, without knowing the key.

Python Guessing and tampering without the key

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The attacker never touched d, yet changed 1500 into 3000. This is why every real scheme adds randomized padding.

Attack 2: small exponent without padding

If e = 3 and the message is short enough that mยณ < n, then c = mยณ exactly, with no modular wrap-around. The attacker simply takes the integer cube root.

Python Cube root attack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The message is recovered without any factoring. A related attack, Hรฅstad's broadcast attack, recovers a message sent to three recipients with e = 3, using the Chinese remainder theorem to combine the three ciphertexts, then a cube root.

Attack 3: shared primes

Key-generation bugs on devices with poor randomness have produced different public moduli that share one prime. If nโ‚ = pยทqโ‚ and nโ‚‚ = pยทqโ‚‚, then gcd(nโ‚, nโ‚‚) = p, and both keys are broken in microseconds. In 2012 researchers found thousands of real keys this way by running pairwise gcds on millions of public keys.

Python Breaking keys that share a prime

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Keys A and B give a nontrivial gcd, and each is factored at once. Key C shares nothing.

Attack 4: Wiener's small-d attack

Making d small speeds up decryption, but it is a trap. Wiener (1990) showed that if d < n^(1/4)/3, then d appears as the denominator of a continued fraction convergent of e/n. Reason: eยทd - kยทฯ†(n) = 1, so e/ฯ†(n) โ‰ˆ k/d is a very close approximation, and ฯ†(n) โ‰ˆ n. For each convergent k/d we compute a candidate ฯ† = (eยทd - 1)/k and check whether it yields integer primes.

Python Wiener's attack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The attacker only used (n, e) and recovered both d and the factors. The fix is simple: never choose a small d; use the standard e = 65537 and let d be whatever comes out.

Attack 5: factoring a weak modulus

Everything in the factoring chapter applies. A 128-bit modulus falls to the quadratic sieve or even rho in seconds; 512-bit RSA was broken in 1999 with distributed effort. The currently recommended minimum is 2048 bits, with 3072 for long-term protection. A modulus whose primes are close together falls to Fermat's method.

Python Factoring a 128-bit modulus on the spot

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Padding: the cure for malleability

Modern schemes (OAEP for encryption, PSS for signatures) transform m before the exponentiation. OAEP mixes in fresh random bytes and applies a hash-based mask, so equal messages encrypt to different ciphertexts, and any bit flip in the ciphertext makes the unpadding check fail. Below is a deliberately simplified padding, only to demonstrate the effect; it is not secure and must not be used.

Python Toy randomized padding

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Two encryptions of the same message differ, and the multiplication trick from attack 1 is now detected, because the integrity check fails after unpadding. Production code should use a vetted library (OAEP and PSS in OpenSSL or the cryptography package) rather than anything like this sketch.

flowchart TD
    A["Textbook RSA"] --> B["deterministic: guess and compare"]
    A --> C["malleable: multiply ciphertexts"]
    A --> D["small e, short m: cube root"]
    A --> E["bad keys: shared primes, small d, close primes"]
    B --> P["Fix: randomized padding (OAEP, PSS)"]
    C --> P
    D --> P
    E --> K["Fix: good randomness, e = 65537, 2048+ bit n"]

Weaknesses and their standard remedies.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why can an attacker test whether a ciphertext hides the message YES?

    Without randomized padding, equal plaintexts give equal ciphertexts.
  2. 2. What goes wrong with e = 3 and a short unpadded message?

    No modular reduction happens, so the ordinary cube root gives the message.
  3. 3. Two RSA moduli share a prime p. What is the quickest attack?

    A single gcd factors both keys.
  4. 4. Wiener's attack applies when:

    A small d is a convergent denominator of e/n.

Summary

  • Textbook RSA is deterministic and malleable; always use randomized padding (OAEP for encryption, PSS for signatures).
  • Short unpadded messages with tiny e fall to cube roots; broadcast with e = 3 falls to CRT.
  • Shared primes between keys are exposed by gcd; close primes by Fermat's method.
  • A small private exponent is broken by Wiener's continued-fraction attack.
  • Use e = 65537, strong randomness, at least 2048-bit moduli and a vetted library.

Next: Diffie-Hellman and Discrete Logarithms