Coppersmith's attack
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 the secret key is available.
RSA basics
The public key in the RSA system is a tuple of integers , where N is the product of two primes p and q. The secret key is given by an integer d satisfying
; equivalently, the secret key may be given by
and
if the Chinese remainder theorem is used to improve the speed of decryption, see CRT-RSA. Encryption of a message M produces the ciphertext
which can be decrypted using
by computing
.
Low public exponent attack
In order to reduce encryption or signature-verification time, it is useful to use a small public exponent (). In practice, common choices for
are 3, 17 and 65537
.[1] These values for e are Fermat primes, sometimes referred to as
and
respectively
. They are chosen because they make the modular exponentiation operation faster. Also, having chosen such
, it is simpler to test whether
and
while generating and testing the primes in step 1 of the key generation. Values of
or
that fail this test can be rejected there and then. (Even better: if e is prime and greater than 2 then the test
can replace the more expensive test
.)
If the public exponent is small and the plaintext 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 public exponent
is recommended. When this value is used, signature-verification requires 17 multiplications, as opposed to about 25 when a random
of similar size is used. Unlike low private exponent (see Wiener's Attack), attacks that apply when a small
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.
Coppersmith method
- Theorem 1 (Coppersmith)[2]
- Let N be an integer and
be a monic polynomial of degree
over the integers. Set
for
. Then, given
attacker, Eve, can efficiently find all integers
satisfying
. The running time is dominated by the time it takes to run the LLL algorithm on a lattice of dimension O
with
.
This theorem states the existence of an algorithm which can efficiently find all roots of modulo
that are smaller than
. As
gets smaller, the algorithm's runtime will decrease. This theorem's strength is the ability to find all small roots of polynomials modulo a composite
.
Håstad's broadcast attack
The simplest form of Håstad's attack[3] is presented to ease understanding. The general case uses the Coppersmith method.
Suppose one sender sends the same message in encrypted form to a number of people
, each using the same small public exponent
, say
, and different moduli
. A simple argument shows that as soon as
ciphertexts are known, the message
is no longer secure: Suppose Eve intercepts
, and
, where
. We may assume
for all
(otherwise, it is possible to compute a factor of one of the
’s by computing
.) By the Chinese Remainder Theorem, she may compute
such that
. Then
; however, since
for all
', we have
. Thus
holds over the integers, and Eve can compute the cube root of
to obtain
.
For larger values of more ciphertexts are needed, particularly,
ciphertexts are sufficient.
Generalizations
Håstad also showed that applying a linear-padding to prior to encryption does not protect against this attack. Assume the attacker learns that
for
and some linear function
, i.e., Bob applies a pad to the message
prior to encrypting it so that the recipients receive slightly different messages. For instance, if
is
bits long, Bob might encrypt
and send this to the i-th recipient.
If a large enough group of people is involved, the attacker can recover the plaintext from all the ciphertext with similar methods. In more generality, Håstad proved that a system of univariate equations modulo relatively prime composites, such as applying any fixed polynomial
, could be solved if sufficiently many equations are provided. This attack suggests that randomized padding should be used in RSA encryption.
- Theorem 2 (Håstad)
- Suppose
are relatively prime integers and set
. Let
be k polynomials of maximum degree
. Suppose there exists a unique
satisfying
for all
. Furthermore, suppose
. There is an efficient algorithm which, given
for all
, computes
.
- Proof
Since the are relatively prime the Chinese Remainder Theorem might be used to compute coefficients
satisfying
and
for all
. Setting
we know that
. Since the
are nonzero we have that
is also nonzero. The degree of
is at most
. By Coppersmith’s Theorem, we may compute all integer roots
satisfying
and
. However, we know that
, so
is among the roots found by Coppersmith's theorem.
This theorem can be applied to the problem of broadcast RSA in the following manner: Suppose the i-th plaintext is padded with a polynomial , so that
. Then the polynomials
satisfy that relation. The attack succeeds once
. The original result used the Håstad method instead of the full Coppersmith method. Its result was required
messages, where
.[3]
Franklin-Reiter related-message attack
Franklin-Reiter identified a new attack against RSA with public exponent . If two messages differ only by a known fixed difference between the two messages and are RSA encrypted under the same RSA modulus
, then it is possible to recover both of them.
Let be Alice's public key. Suppose
are two distinct messages satisfying
for some publicly known polynomial
. To send
and
to Alice, Bob may naively encrypt the messages and transmit the resulting ciphertexts
. Eve can easily recover
given
, by using the following theorem:
- Theorem 3 (Franklin-Reiter)[2]
- Set
and let
be an RSA public key. Let
satisfy
for some linear polynomial
with
. Then, given
, attacker, Eve, can recover
in time quadratic in
.
For an arbitrary (rather than restricting to
) the time required is quadratic in
and
).
- Proof
Since , we know that
is a root of the polynomial
. Similarly,
is a root of
. The linear factor
divides both polynomials.
Therefore, Eve calculates the greatest common divisor (gcd) of
and
, if the gcd turns out to be linear,
is found. The gcd can be computed in quadratic time in
and
using the Euclidean algorithm.
Coppersmith’s short-pad attack
Like Håstad’s and Franklin-Reiter’s attack, this attack exploits a weakness of RSA with public exponent . Coppersmith showed that if randomized padding suggested by Håstad is used improperly then RSA encryption is not secure.
Suppose Bob sends a message to Alice using a small random padding before encrypting it. An attacker, Eve, intercepts the ciphertext and prevents it from reaching its destination. Bob decides to resend
to Alice because Alice did not respond to his message. He randomly pads
again and transmits the resulting ciphertext. 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 by using the following theorem, if the random padding is too short.
- Theorem 4 (Coppersmith)
- Let
be a public RSA key where
is
-bits long. Set
. Let
be a message of length at most
bits. Define
and
, where
and
are distinct integers with
. If Eve is given
and the encryptions
of
(but is not given
or
), she can efficiently recover
.
- Proof[2]
Define and
. We know that when
, these polynomials have
as a common root. In other words,
is a root of the resultant
. Furthermore,
. Hence,
is a small root of
modulo
, and Eve can efficiently find it using the Coppersmith method. Once
is known, the Franklin-Reiter attack can be used to recover
and consequently
.
See also
References
- ↑ Imad Khaled Salah, Abdullah Darwish, Saleh Oqeili (2006). "Mathematical Attacks on RSA Cryptosystem". Journal of Computer Science 2 (8): 665–671. doi:10.3844/jcssp.2006.665.671.
- 1 2 3 D. Boneh, Twenty years of attacks on the RSA cryptosystem
- 1 2 Glenn Durfee, Cryptanalysis of RSA Using Algebraic and Lattice Methods