Skip to content
Tutorials Center
My learning

Topics

Lesson 25 of 40 ยท Public-Key Cryptography

RSA Padding and Common Pitfalls

See why textbook RSA is malleable and deterministic, break small exponents and shared primes in Python, then add OAEP padding and learn why PSS is used for signatures.

The RSA you built in the previous lesson is correct mathematics and unsafe cryptography. It is textbook RSA: the same message always produces the same ciphertext, ciphertexts can be combined and edited to change the plaintext predictably, and short messages with small exponents leak completely. None of this contradicts the claim that factoring is hard; it shows that "hard to invert" is not the same as "secure to use".

This lesson attacks textbook RSA in five ways, all runnable, and then repairs it with padding: a randomized, structured encoding applied before the number is exponentiated. For encryption the standard is OAEP; for signatures it is PSS. You will implement OAEP yourself and watch the attacks stop working.

Attack 1: determinism and malleability

Because c = m^e mod n has no randomness, an attacker who can guess the plaintext can simply encrypt every guess with the public key and compare. For short or predictable messages ("YES" or "NO", a salary, a PIN) that is a complete break.

RSA is also multiplicatively homomorphic: (m1^e)(m2^e) = (m1*m2)^e mod n. An attacker can therefore multiply a ciphertext by 2^e and the receiver will decrypt 2m, without anyone learning m. Imagine an encrypted bid in a sealed auction. The same algebra forges signatures on textbook RSA: given valid signatures on m1 and m2, their product is a valid signature on m1*m2.

Python Guessing, tampering and forging with textbook RSA

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.

Attack 2: small exponents and short messages

Using e = 3 makes encryption cheap, but if the message is short, m^3 can be smaller than n. Then the modular reduction never happens: c = m^3 as ordinary integers, and the attacker simply takes the integer cube root. No key is needed.

A related attack, Hรฅstad's broadcast attack, works even for longer messages: if the same message is sent to three recipients with e = 3 and different moduli, the Chinese Remainder Theorem combines the three ciphertexts into m^3 modulo n1*n2*n3. Because m < n_i, that product is larger than m^3, so again no reduction occurs and a cube root recovers m.

Python Cube-root and broadcast attacks on e = 3

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 cure is the same for both: use e = 65537, and always pad, so that the number being exponentiated is full-length and random-looking.

Attack 3: shared primes

RSA moduli are meant to be unique products of two secret primes. If two keys share a prime, gcd(n1, n2) reveals it instantly, and gcd is cheap even for 4096-bit numbers. This is not just theoretical: surveys of internet-facing keys in 2012 found a noticeable fraction sharing factors, because embedded devices generated keys right after boot, when their random number generators had little entropy (see randomness). Anyone who collects many public keys can compare all pairs.

Python Factoring two 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.

The prevention is not mathematical but operational: generate keys only after the system has real entropy, using the operating system's CSPRNG.

The fix for encryption: OAEP

Optimal Asymmetric Encryption Padding (OAEP, defined in PKCS #1 and RFC 8017) wraps the message in a randomized structure before the RSA operation:

  1. Build a data block: a hash of an optional label, a run of zero bytes, a 0x01 marker and the message.
  2. Pick a fresh random seed the size of the hash.
  3. Mask the data block with a mask generated from the seed (the mask function MGF1 is built from the hash), then mask the seed with a hash of the masked block. Two interlocked masks mean that you need every bit of the result to recover any of it.
  4. Encode as 0x00 || masked_seed || masked_block, a number just below n, and apply m^e mod n.

Decryption inverts the steps and checks the structure; any inconsistency produces a single generic error, so the receiver does not reveal which check failed. (Different error messages from older PKCS #1 v1.5 padding enabled Bleichenbacher's 1998 attack, and variants of it still turn up today.)

flowchart TD
    M["Message"] --> DB["Data block:<br/>hash(label) + zeros + 0x01 + message"]
    S["Random seed"] --> G1["MGF1(seed)"]
    G1 --> X1["XOR"]
    DB --> X1
    X1 --> MDB["Masked block"]
    MDB --> G2["MGF1(masked block)"]
    G2 --> X2["XOR"]
    S --> X2
    X2 --> MS["Masked seed"]
    MS --> EM["0x00 + masked seed + masked block"]
    MDB --> EM
    EM --> RSA["RSA: em ^ e mod n"]

OAEP randomizes the input with a seed and spreads every bit across the whole block before RSA is applied.

The cost is capacity: with SHA-256 the message must be at least 66 bytes shorter than the modulus. A 2048-bit key (256 bytes) carries up to 190 bytes, which is plenty for a session key in a hybrid scheme. Here is a working OAEP using only hashlib.

Python RSA-OAEP: randomized and tamper-evident

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.

In production, take rsa.OAEP from a vetted library: this version is not constant-time, and the timing behaviour of the final checks matters.

The fix for signatures: PSS

Signing has the same problem in a different shape: the plain sign = h^d mod n is deterministic and multiplicative, as the forgery above showed. RSASSA-PSS hashes the message, mixes in a random salt, runs the result through a mask-generation function with a fixed structure, and only then applies the private exponent. Verification recomputes the structure and checks it. PSS has a security proof and is the recommended RSA signature scheme; the older PKCS #1 v1.5 signature padding is still widely used and is acceptable when implemented carefully. See Digital Signatures for the sign-and-verify workflow.

A checklist for RSA in practice

  • Never use raw pow(m, e, n) on user data: use OAEP for encryption and PSS (or PKCS #1 v1.5 signatures) for signing.
  • Use e = 65537, and keys of at least 2048 bits (3072 for long-lived data).
  • Prefer encrypting a random session key with RSA and the data with an AEAD cipher.
  • Generate keys only with the OS CSPRNG, and never share primes between keys.
  • Return one generic error for every decryption failure, and take care with timing.
  • Prefer a high-level library, and consider elliptic-curve alternatives for new designs.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why is textbook RSA vulnerable to a guess-and-check attack on short messages?

    Anyone can encrypt guesses with the public key and compare. Randomized padding such as OAEP makes every encryption of the same message different.
  2. 2. If c = m^e mod n, what does c * 2^e mod n decrypt to in textbook RSA?

    RSA is multiplicatively homomorphic: (m^e)(2^e) = (2m)^e. This malleability is why unpadded RSA must never be used.
  3. 3. Why is e = 3 dangerous with short, unpadded messages?

    When no modular reduction occurs, c is just m cubed. Padding makes the encoded message about as large as n, so the cube is always reduced.
  4. 4. How can an attacker recover the private keys of two devices that used a weak random number generator?

    If n1 and n2 share a prime p, gcd(n1, n2) = p, and both keys are factored in microseconds.
  5. 5. What is the purpose of the random seed in OAEP?

    The seed is masked with hash output of the data block and vice versa, so the encoding is randomized and cannot be tampered with in a controlled way.

Summary

  • Textbook RSA is deterministic and malleable: attackers can guess plaintexts, double bids and forge signatures from public data.
  • Small exponents with short messages, or broadcasts to several recipients, are broken by integer cube roots and the CRT.
  • Keys that share a prime fall to a single gcd; generate keys only from a strong CSPRNG.
  • OAEP (encryption) and PSS (signatures) add randomness and structure; decryption errors must be uniform.
  • In real code use a vetted library, e = 65537, 2048+ bit keys, and hybrid encryption.

Next: Elliptic Curve Cryptography, a different trapdoor that reaches the same security with much smaller keys.