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 a prime factor 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 . 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 the 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)
 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 that can efficiently find all roots of  modulo  that are smaller than . As  gets smaller, the algorithm's runtime decreases. 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 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 numbers  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 -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  polynomials of maximum degree . Suppose there exists a unique  satisfying  for all . Furthermore, suppose . There is an efficient algorithm that, 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 -th plaintext is padded with a polynomial , so that . Then  is true, and Coppersmith’s method can be used. The attack succeeds once , where  is the number of messages. The original result used Håstad’s variant instead of the full Coppersmith method. As a result, it required  messages, where . Franklin–Reiter related-message attack

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 , then it is possible to recover both of them. The attack was originally described with public exponent , but it works more generally (with increasing cost as  grows). 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)
 Let  be an RSA public key. Let  satisfy  for some linear polynomial  with . Then, given , attacker (Eve) can recover  in time quadratic in . Proof

Since , we know that  is a root of the polynomial . Similarly,  is a root of . Hence, the linear factor  divides both polynomials. Therefore, Eve may calculate the greatest common divisor  of  and , and if the  turns out to be linear,  is found. The  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 attacks, 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

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
 ROCA attack

References

Cryptographic attacks
Attacks on public-key cryptosystems