Small exponent and short messages

Among the flaws of raw RSA, one is spectacular: with a small public exponent, you can sometimes decrypt without any key, just with a calculator.

The public exponent e = 3

To go fast, a small e is often chosen. Historically, e = 3 was very widely used. Encryption becomes:

c = m^3 mod n

Everything rests on the mod n. The modulo only has an effect if m^3 exceeds n. Otherwise, nothing happens.

The cube root attack

Suppose the message is short, to the point that m^3 < n. Then:

c = m^3 mod n = m^3   (pas de réduction !)

The ciphertext is simply the cube of the message. To recover m, the attacker just has to take the integer cube root of c:

m = racine_cubique(c)

No private key, no factorisation. An operation any computer does in a fraction of a second.

Worked example

Take a large modulus n (hundreds of digits) and e = 3. We encrypt the small message m = 42:

c = 42^3 mod n = 74088 mod n = 74088   (car 74088 << n)

The attacker sees c = 74088. They compute:

racine_cubique(74088) = 42      ✔  message retrouvé

The Håstad variant

Even if a message is too large for a single recipient, it remains vulnerable if it is sent to several. Håstad showed that if the same message m is encrypted with e = 3 to three recipients having different moduli n1, n2, n3:

c1 = m^3 mod n1
c2 = m^3 mod n2
c3 = m^3 mod n3

then, by the Chinese remainder theorem, you reconstruct m^3 modulo (n1 × n2 × n3). Since m^3 < n1 × n2 × n3, you obtain the exact m^3, and a cube root gives m. Three intercepted ciphertexts are enough, without breaking any key.

Why padding saves everything

Here again, random padding is the countermeasure. Before encryption, OAEP transforms the small m = 42 into a very large number stuffed with randomness, occupying almost the full width of n. From then on:

• m^3 far exceeds n, the reduction mod n does take place: no more cube root.
• The same message sent to several people gives different blocks each time (distinct randomness): the Håstad attack falls apart.

A small e is therefore not dangerous in itself; it is raw RSA with a small e that is.

In summary

With e = 3 and a message such that m^3 < n, the ciphertext is the cube of the message: a cube root decrypts it without a key. The Håstad variant breaks a single message sent to three recipients via the Chinese remainder theorem. Random padding (OAEP), which inflates the message, neutralises both attacks.