Coppersmith's Attack

Introduction

Low Public Exponent Attack

In order to reduce encryption or signature-verification time, it is useful to use a small public exponent ($e$). In practice, common choices for $e$ are 3, 17 and 65537 $(2^{16}+1)$.. These are Fermat primes, sometimes referred to as $F_{0},F_{2}$ and $F_{4}$ respectively $(Fx=2^{2^{x}}+1)$. They are chosen because they make the modular exponentiation operation faster. Also, having chosen $e$, it is simpler to test whether $gcd(e,p-1)=1$ and $gcd(e,q-1)=1$ while generating and testing the primes in step 1. Values of $p$ or $q$ that fail this test can be rejected there and then. (Even better: if e is prime and greater than 2 then you can do the less-expensive test $p\,{\bmod {\,}}e=1$ instead of $gcd(p-1,e)=1$.
If the public exponent is small and the plaintext $m$ is very short, then the RSA function may be easy to be inverted. However, it makes certain attacks possible. In order to defeat such attack, the value of public exponent $e=2^{16}+1$ is recommended. When this value is used, signature-verification requires 17 multiplications, as opposed to roughly 1000 when a random is used. Unlike low private exponent (Wiener’s Attack), attacks that apply when a small $e$ is used are far from a total break. The most powerful attacks on low public exponent RSA are based on the following theorem (Coppersmith).

Theorem 1 (Coppersmith)

Let N be an integer and $f\in Z[x]$ be a monic polynomial of degree $d$. Set $X=N^{{\frac {1}{4}}-\epsilon }$ for $\epsilon \leq 0$. then, given $\left\langle N,f\right\rangle$ attacker, Eve, can efficiently find all integers $x_{0}<X$ satisfying $f(x_{0})=0\,{\bmod {\,}}N$. the running time is dominated by the time it takes to run the LLL algorithm on lattice of dimension $O(w)$ with $w=min({\frac {1}{\epsilon }},log_{2}N)$.

This theorem claims the existence of an algorithm which can efficiently find all roots of $f$ modulo $N$ that are less than $X=N^{\frac {1}{\epsilon }}$. As $X$ gets smaller, the algorithm's runtime will decrease. This theorem's strength is the ability to find out all small roots of polynomials modulo a composite $N$.
This theorem has many applications on RSA attack specifically on low public exponent. We will explain some of these attacks and show how they work.

Håstad's Broadcast Attack

At this moment, we will present an improvement to an attack the preceding Coppersmith's attack due to Håstad.
Suppose one sender will send an encrypted message $M$ to a number of group of people $P_{1};P_{2};...;P_{k}$. Each using the same small public exponent $e$, say $e$ = 3 ,$\left\langle N_{i},e_{i}\right\rangle$. Håstad showed that a linear-padding to $M$ prior to encryption is insecure, and the attacker learns that $C_{i}=f_{i}(M)^{e_{1}}$ for $i=1..k.$. If enough group of people are involved, the attacker can recover the plaintext $M_{i}$ from all the ciphertext. Håstad’s discovery is applicable on the equations:$g_{1}(M)=0$ mod $N_{i}$. He proved that a system of univariate equations modulo relatively prime composites, such as $g_{1}(M)=0$ mod $N_{i}$, could be solved if many equations are provided sufficiently. This attack suggests that randomized padding should be used in RSA encryption.

How it works?

suppose all public exponents $e_{i}$ are equal to 3. A simple argument shows that as soon as $k\geq 3$, the message $M$ is no longer secure. Suppose Eve intercepts $C_{1},C_{2}$ , and $C_{3}$ , where $C_{i}=M_{3}\,{\bmod {\,}}N_{i}$0. We may assume $\gcd(N_{i},N_{j})=1$ for all $i,j$ (otherwise, it is possible to compute a factor of one of the Ni’s.) By the Chinese Remainder Theorem, she may compute $C\in \mathbb {(} Z)_{N1N2N3}^{*}$ such that $C=C_{i}\,{\bmod {\,}}N_{i}$. Then $C=M_{3}\,{\bmod {\,}}N_{1}N_{2}N_{3}$ ; however, since $M<N_{i}$ for all $i$', we have $M_{3}<N_{1}N_{2}N_{3}$. Thus $C=M_{3}$ holds over the integers, and Eve can compute the cube root of $C$ to obtain $M$.

Suppose Bob applies a pad to the message $M$ prior to encrypt it so that the recipients receive slightly different messages. For instance, if $M$ is $m$ bits long, Bob might encrypt $M_{i}=i2^{m}+M$ and send this to the i-th recipient.
Unfortunately, Håstad showed that this linear padding is insecure. In fact, he proved that applying any fixed polynomial to the message prior to encryption does not prevent the attack.
Suppose before encrypting $M$ and sending that to party $P_{i}$, Bob applies the polynomial $f_{i}$ to $M$ and encrypts $f_{2}(M)$. Håstad showed that if enough parties are involved, Eve can recover the plaintext $M$ from all the ciphertexts using the following theorem:

Theorem 2 (Håstad)

Suppose $N_{1},...,N_{k}$ are relatively prime integers and set $N_{min}=min_{i}(N_{i})$. Let $g_{1}(x)=\in \mathbb {Z} N_{1}\left[x\right]$ be k polynomials of maximum degree $q$. Suppose there exists a unique $M<N_{min}$ satisfying $gi(M)=0$(mod $N_{i}$) for all $i\in \left\{0,...,k\right\}$. Furthermore suppose $k>q$. There is an efficient algorithm which, given $\left\langle N_{i},g_{i}\left(x\right)\right\rangle$ for all $i$, computes $M$.

Proof:
Since $N_{i}$ are relatively prime, Chinese Remainder Theorem might be used to compute coefficients $T_{i}$ satisfying $T_{i}\equiv 1{\bmod {N}}_{i}(is_{1})$ and $T_{i}\equiv 0$ mod $N_{j}$ for all $i\neq j$. Setting $g(x)=\sum i\cdot T_{i}\cdot g_{i}(x)$ we know that $g(M)\equiv 0$ mod $\prod N_{i}$. Since Ti are nonzero we have that $g\left(x\right)$ is not zero also. The degree of $g\left(x\right)$ is at most $q$. By Coppersmith’s Theorem, we may compute all integer roots $x_{0}$ satisfying $g(x_{0})\equiv 0$ mod $\prod N_{i}$ and $\left|x_{0}\right|<\left(\prod N_{i}\right)^{\frac {1}{q}}$. However, we know that $M<N_{min}<(\prod N_{1})^{\frac {1}{k}}<(\prod N_{1})^{\frac {1}{q}}$, so $M$ is a root.

This theorem can be applied to the problem of broadcast RSA such in the following manner: Suppose the i-th plaintext is padded with a polynomial $f_{i}\left(x\right)$, so that $N_{i}=\left(f_{i}\left(x\right)\right)^{e_{i}}-C_{i}$ mod $N_{i}$. Then the polynomials $g_{i}=\left(f_{i}\left(x\right)\right)^{e_{i}}-C_{i}$ mod $N_{i}$ satisfy that relation. The attack succceeds once $k>max_{i}(e_{i}\cdot degf_{i})$. The original result used the Håstad method instead of the full Coppersmith method. Its result was messages requiring $k=O(q^{2})$ where $q=max_{i}(ei.degf_{i})$.

Franklin-Reiter Related Message Attack

Franklin-Reiter identified a new attack against RSA with public exponent $e$=3. If two messages differ only from a known fixed value of difference between the two messages and are RSA encrypted under the same RSA modulus $N$, then it is possible to recover both of them.

How it works?

Let $\left\langle N;e_{i}\right\rangle$ be Alice's public key. Suppose $M_{1};M_{2}\in \mathbb {Z} _{N}$ are two distinct messages satisfying $M_{1}=f(M_{2})\,{\bmod {\,}}N$ for some publicly known polynomial $f\in \mathbb {Z} _{N}[x]$. To send $M_{1}$ and $M_{2}$ to Alice, Bob may naively encrypt the messages and transmit the resulting ciphertexts $C_{1};C_{2}$. We show that given $C_{1};C_{2}$, Eve can easily recover $M_{1};M_{2}$ by using the following theorem:

Theorem 3 (Franklin-Reiter)

Set $e=3$ and let $\left\langle N,e\right\rangle$ be an RDA public key. Let $M_{1}\neq M_{2}\in \mathbb {Z} _{N}^{*}$ satisfy $M_{1}=f(M_{2})\,{\bmod {\,}}N$ for some linear polynomial $f=ax=b\in \mathbb {Z} _{N}[x]$ with $b\neq 0$. Then, given $\left\langle N,e,C_{1},C_{2},f\right\rangle$, attacker, Eve, can recover $M_{1},M_{2}$ in time quadratic in log $N$.

Proof:
Using an arbitrary $e$ (rather than restricting to $e=3$, time quadratic in $e$ and $logN$). Since $C_{1}=M_{1}^{e}\,{\bmod {\,}}N$, we know that $M_{2}$ is a root of the polynomial $g_{1}(x)=f(x)^{e}-C_{1}\in \mathbb {Z} _{N}[x]$. Similarly, $M_{2}$ is a root of $g_{2}(x)=x^{e}-M_{2}\in \mathbb {Z} _{N}[x]$. The linear factor $x-M_{2}$ divides both polynomials. Therefore, Eve calculates the greatest common divisor (gcd) of $g_{1}$ and $g_{2}$, if the gcd turns out to be linear, $M_{2}$ is found. The gcd can be computed in quadratic time in $e$ and $logN$. $\blacksquare$

Coppersmith’s Short Pad Attack

Like the Hastad’s and Franklin-Reiter’s attack, this attack exploits a weakness of RSA with public exponent $e=3$. Coppersmith showed that if randomized padding suggested by Hastad is used improperly then RSA encryption is not secure.

How it works?

Suppose Bob sends a message $M$ to Alice using a small random padding before encrypting. An attacker, Eve, intercepts the ciphertext and prevents it from reaching its destination. Bob decides to resend $M$ to Alice because Alice did not respond to his message. He randomly pads $M$ 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 $M$ by using the following theorem, if the random paddding are too short.

Theorem 4 (Coppersmith)

Let $\left\langle N,e\right\rangle$ be a public RSA key where $N$ is $n$-bits long. Set $m=\lfloor {\frac {n}{e^{2}}}\rfloor$.Let $M\in \mathbb {Z} _{N}^{*}$ be a message of length at most $n-m$ bits.Define $M_{1}=2^{m}M+r_{1}$ and $M_{2}=2^{m}M+r_{2}$, where $r_{1}$ and $r_{2}$ are distinct integers with $0\leq r_{1},r_{2}<2^{m}$. If Marvin is given $\left\langle N,e\right\rangle$ and the encryptions $C_{1},C_{2}$ of $M_{1},M_{2}$ (but is not given $r_{1}$ or $r_{2}$, he can efficiently recover $M$

Proof
Define $g_{1}(x,y)=x^{e}-C_{1}$ and $g_{2}(x,y)=x^{e}-C_{2}$. We know that when $y=r_{2}-r_{1}$, these polynomials have $M_{1}$ as a common root. In other words, $\vartriangle =r_{2}-r_{1}$ is a root of the “resultant” $h(y)=rest_{x}(g_{1},g_{2})\in \mathbb {Z} _{N\left[y\right]}$. Furthermore, $\left|\vartriangle \right|<2^{m}<N^{\frac {1}{e^{2}}}$. Hence, $\vartriangle$ is a small root of $h$ modulo $N$, and Marvin can efficiently find it using theorem 1 (Coppersmith). once $\vartriangle$ is known, the Franklin-Reiter attack can be used to recover $M_{2}$ and consequently $M$.