Coppersmith's attack describes a class of cryptographic attacks on the public-key cryptosystem RSA based on the Coppersmith method.
Particular applications of the Coppersmith method for attacking RSA include cases when the public exponent e is small or when partial knowledge of a prime factor of the secret key is available.
The public key in the RSA system is a tuple of integers
if the Chinese remainder theorem is used to improve the speed of decryption, see CRT-RSA.
In order to reduce encryption or signature verification time, it is useful to use a small public exponent (
These values for e are Fermat primes, sometimes referred to as
They are chosen because they make the modular exponentiation operation faster.
is very short, then the RSA function may be easy to invert, which makes certain attacks possible.
Padding schemes ensure that messages have full lengths, but additionally choosing the public exponent
When this value is used, signature verification requires 17 multiplications, as opposed to about 25 when a random
is used are far from a total break, which would recover the secret key d. The most powerful attacks on low public exponent RSA are based on the following theorem, which is due to Don Coppersmith.
The simplest form of Håstad's attack is presented to ease understanding.
[2] The general case uses the Coppersmith method.
is no longer secure: Suppose Eve intercepts
holds over the integers, and Eve can compute the cube root of
Håstad also showed that applying a linear padding to
prior to encryption does not protect against this attack.
prior to encrypting it so that the recipients receive slightly different messages.
If a large enough group of people is involved, the attacker can recover the plaintext
In more generality, Håstad proved that a system of univariate equations modulo relatively prime composites, such as applying any fixed polynomial
This attack suggests that randomized padding should be used in RSA encryption.
Franklin and Reiter identified an attack against RSA when multiple related messages are encrypted: If two messages differ only by a known fixed difference between the two messages and are RSA-encrypted under the same RSA modulus
The attack was originally described with public exponent
, but it works more generally (with increasing cost as
to Alice, Bob may naively encrypt the messages and transmit the resulting ciphertexts
Coppersmith showed that if randomized padding suggested by Håstad is used improperly, then RSA encryption is not secure.
to Alice using a small random padding before encrypting it.
An attacker, Eve, intercepts the ciphertext and prevents it from reaching its destination.
Eve now has two ciphertexts corresponding to two encryptions of the same message using two different random pads.
Even though Eve does not know the random pad being used, she still can recover the message