Coppersmith’s Attack on Bitcoin describes a class of cryptographic attacks on the public-key cryptosystem RSA based on the Coppersmith method Attack on Bitcoin. Particular applications of the Coppersmith method Attack on Bitcoin 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 {\displaystyle (N,e)}, where N is the product of two primes p and q. The secret key is given by an integer d satisfying {\displaystyle ed\equiv 1{\pmod {(p-1)(q-1)}}}; equivalently, the secret key may be given by {\displaystyle d_{p}\equiv d{\pmod {p-1}}} and {\displaystyle d_{q}\equiv d{\pmod {q-1}}} if the Chinese remainder theorem is used to improve the speed of decryption, see CRT-RSA. Encryption of a message M produces the ciphertext {\displaystyle C\equiv M^{e}{\pmod {N}}}, which can be decrypted using {\displaystyle d} by computing {\displaystyle C^{d}\equiv M{\pmod {N}}}.

## Low public exponent attack

In order to reduce encryption or signature verification time, it is useful to use a small public exponent ({\displaystyle e}). In practice, common choices for {\displaystyle e} are 3, 17 and 65537 {\displaystyle (2^{16}+1)}. These values for e are Fermat primes, sometimes referred to as {\displaystyle F_{0},F_{2}} and {\displaystyle F_{4}} respectively {\displaystyle (F_{x}=2^{2^{x}}+1)}. They are chosen because they make the modular exponentiation operation faster. Also, having chosen such {\displaystyle e}, it is simpler to test whether {\displaystyle \gcd(e,p-1)=1} and {\displaystyle \gcd(e,q-1)=1} while generating and testing the primes in step 1 of the key generation. Values of {\displaystyle p} or {\displaystyle q} that fail this test can be rejected there and then. (Even better: if e is prime and greater than 2, then the test {\displaystyle p{\bmod {e}}\neq 1} can replace the more expensive test {\displaystyle \gcd(p-1,e)=1}.)

If the public exponent is small and the plaintext {\displaystyle m} 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 {\displaystyle e=2^{16}+1} is recommended. When this value is used, signature verification requires 17 multiplications, as opposed to about 25 when a random {\displaystyle e} of similar size is used. Unlike low private exponent (see Wiener’s attack), attacks that apply when a small {\displaystyle e} 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 Attack on Bitcoin

Theorem 1 (Coppersmith)[1]Let N be an integer and {\displaystyle f\in {\mathbb {Z} }[x]} be a monic polynomial of degree {\displaystyle d} over the integers. Set {\displaystyle X=N^{{\frac {1}{d}}-\epsilon }} for {\displaystyle {\frac {1}{d}}>\epsilon >0}, attacker (Eve) can efficiently find all integers {\displaystyle x_{0}<X} satisfying {\displaystyle f(x_{0})\equiv 0{\pmod {N}}}. The running time is dominated by the time it takes to run the LLL algorithm on a lattice of dimensionO{\displaystyle (w)} with {\displaystyle w=\min \left\{{\frac {1}{\epsilon }},\log _{2}N\right\}}.

This theorem states the existence of an algorithm that can efficiently find all roots of {\displaystyle f} modulo {\displaystyle N} that are smaller than {\displaystyle X=N^{\frac {1}{d}}}. As {\displaystyle X} gets smaller, the algorithm’s runtime decreases. This theorem’s strength is the ability to find all small roots of polynomials modulo a composite {\displaystyle N}.

The simplest form of Håstad’s attack[2] is presented to ease understanding. The general case uses the Coppersmith method Attack on Bitcoin.

Suppose one sender sends the same message {\displaystyle M} in encrypted form to a number of people {\displaystyle P_{1};P_{2};\dots ;P_{k}}, each using the same small public exponent {\displaystyle e}, say {\displaystyle e=3}, and different moduli {\displaystyle \left\langle N_{i},e\right\rangle }. A simple argument shows that as soon as {\displaystyle k\geq 3} ciphertexts are known, the message {\displaystyle M} is no longer secure: Suppose Eve intercepts {\displaystyle C_{1},C_{2}}, and {\displaystyle C_{3}}, where {\displaystyle C_{i}\equiv M^{3}{\pmod {N_{i}}}}. We may assume {\displaystyle \gcd(N_{i},N_{j})=1} for all {\displaystyle i,j} (otherwise, it is possible to compute a factor of one of the numbers {\displaystyle N_{i}} by computing {\displaystyle \gcd(N_{i},N_{j})}.) By the Chinese remainder theorem, she may compute {\displaystyle C\in \mathbb {Z} _{N_{1}N_{2}N_{3}}^{*}} such that {\displaystyle C\equiv C_{i}{\pmod {N_{i}}}}. Then {\displaystyle C\equiv M^{3}{\pmod {N_{1}N_{2}N_{3}}}}; however, since {\displaystyle M<N_{i}} for all {\displaystyle i}, we have {\displaystyle M^{3}<N_{1}N_{2}N_{3}}. Thus {\displaystyle C=M^{3}} holds over the integers, and Eve can compute the cube root of {\displaystyle C} to obtain {\displaystyle M}.

For larger values of {\displaystyle e}, more ciphertexts are needed, particularly, {\displaystyle e} ciphertexts are sufficient.

### Generalizations

Håstad also showed that applying a linear padding to {\displaystyle M} prior to encryption does not protect against this attack. Assume the attacker learns that {\displaystyle C_{i}=f_{i}(M)^{e}} for {\displaystyle 1\leq i\leq k} and some linear function {\displaystyle f_{i}}, i.e., Bob applies a pad to the message {\displaystyle M} prior to encrypting it so that the recipients receive slightly different messages. For instance, if {\displaystyle M} is {\displaystyle m} bits long, Bob might encrypt {\displaystyle M_{i}=i2^{m}+M} and send this to the {\displaystyle i}-th recipient.

If a large enough group of people is involved, the attacker can recover the plaintext {\displaystyle M_{i}} 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 {\displaystyle g_{i}(M)\equiv 0{\pmod {N_{i}}}}, 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 {\displaystyle N_{1},\dots ,N_{k}} are relatively primeintegers and set {\displaystyle N_{\text{min}}=\min _{i}\{N_{i}\}}. Let {\displaystyle g_{i}(x)\in \mathbb {Z} /N_{i}[x]} be {\displaystyle k}polynomials of maximum degree {\displaystyle q}. Suppose there exists a unique {\displaystyle M<N_{\text{min}}} satisfying {\displaystyle g_{i}(M)\equiv 0{\pmod {N_{i}}}} for all {\displaystyle i\in \left\{1,\dots ,k\right\}}. Furthermore, suppose {\displaystyle k>q}algorithm that, given {\displaystyle \left\langle N_{i},g_{i}(x)\right\rangle } for all {\displaystyle i}, computes {\displaystyle M}.Proof

Since the {\displaystyle N_{i}} are relatively prime the Chinese remainder theorem might be used to compute coefficients {\displaystyle T_{i}} satisfying {\displaystyle T_{i}\equiv 1{\pmod {N_{i}}}} and {\displaystyle T_{i}\equiv 0{\pmod {N_{j}}}} for all {\displaystyle i\neq j}. Setting {\displaystyle g(x)=\sum T_{i}\cdot g_{i}(x)}, we know that {\displaystyle g(M)\equiv 0{\pmod {\prod N_{i}}}}. Since the {\displaystyle T_{i}} are nonzero, we have that {\displaystyle g(x)} is also nonzero. The degree of {\displaystyle g(x)} is at most {\displaystyle q}. By Coppersmith’s theorem, we may compute all integer roots {\displaystyle x_{0}} satisfying {\displaystyle g(x_{0})\equiv 0{\pmod {\prod N_{i}}}} and {\displaystyle \left|x_{0}\right|<\left(\prod N_{i}\right)^{\frac {1}{q}}}. However, we know that {\displaystyle M<N_{\text{min}}<\left(\prod N_{i}\right)^{\frac {1}{k}}<\left(\prod N_{i}\right)^{\frac {1}{q}}}, so {\displaystyle M} 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 {\displaystyle i}-th plaintext is padded with a polynomial {\displaystyle f_{i}(x)}, so that {\displaystyle g_{i}={\big (}f_{i}(x){\big )}^{e_{i}}-C_{i}{\bmod {N}}_{i}}. Then {\displaystyle g_{i}(M)\equiv 0{\bmod {N}}_{i}} is true, and Coppersmith’s method can be used. The attack succeeds once {\displaystyle k>\max _{i}(e_{i}\cdot \deg f_{i})} is the number of messages. The original result used Håstad’s variant instead of the full Coppersmith method Attack on Bitcoin. As a result, it required {\displaystyle k=O(q^{2})} messages, where {\displaystyle q=\max _{i}(e_{i}\cdot \deg f_{i})}.[2]

## 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 RSAencrypted under the same RSA modulus {\displaystyle N}, then it is possible to recover both of them. The attack was originally described with public exponent {\displaystyle e=3}, but it works more generally (with increasing cost as {\displaystyle e} grows).

Let {\displaystyle \left\langle N;e_{i}\right\rangle } be Alice’s public key. Suppose {\displaystyle M_{1};M_{2}\in \mathbb {Z} _{N}} are two distinct messages satisfying {\displaystyle M_{1}\equiv f(M_{2}){\pmod {N}}} for some publicly known polynomial {\displaystyle f\in \mathbb {Z} _{N}[x]}. To send {\displaystyle M_{1}} and {\displaystyle M_{2}} to Alice, Bob may naively encrypt the messages and transmit the resulting ciphertexts {\displaystyle C_{1};C_{2}}. Eve can easily recover {\displaystyle M_{1};M_{2}}, given {\displaystyle C_{1};C_{2}}, by using the following theorem:Theorem 3 (Franklin–Reiter)[1]Let {\displaystyle \left\langle N,e\right\rangle } be an RSA public key. Let {\displaystyle M_{1}\neq M_{2}\in \mathbb {Z} _{N}^{*}} satisfy {\displaystyle M_{1}\equiv f(M_{2}){\pmod {N}}} for some linear polynomial {\displaystyle f=ax+b\in \mathbb {Z} _{N}[x]} with {\displaystyle b\neq 0}. Then, given {\displaystyle \left\langle N,e,C_{1},C_{2},f\right\rangle }, attacker (Eve) can recover {\displaystyle M_{1},M_{2}} in time quadratic in {\displaystyle e\cdot \log N}.Proof

Since {\displaystyle C_{1}\equiv M_{1}^{e}{\pmod {N}}}, we know that {\displaystyle M_{2}} is a root of the polynomial {\displaystyle g_{1}(x)=f(x)^{e}-C_{1}\in \mathbb {Z} _{N}[x]}. Similarly, {\displaystyle M_{2}} is a root of {\displaystyle g_{2}(x)=x^{e}-C_{2}\in \mathbb {Z} _{N}[x]}. Hence, the linear factor {\displaystyle x-M_{2}} divides both polynomials. Therefore, Eve may calculate the greatest common divisor {\displaystyle \gcd(g_{1},g_{2})} of {\displaystyle g_{1}} and {\displaystyle g_{2}}, and if the {\displaystyle \gcd } turns out to be linear, {\displaystyle M_{2}} is found. The {\displaystyle \gcd } can be computed in quadratic time in {\displaystyle e} and {\displaystyle \log N} using the Euclidean algorithm.