Coppersmith’s Method (Part I): Introduction
The Coppersmith’s method is an application of lattice basis reduction algorithms (like LLL) to find small solutions to polynomials modulo \(N\). The application of this method ranges from several attacks on RSA, to solving the hidden number problem (for Diffie-Hellman key exchange or (EC)DSA).
You can find (sage) code that implements the below-mentioned attack on https://github.com/mimoo/RSA-and-LLL-attacks, although they used a weaker (read: more flexible) version of the statements.
Prerequisite: Lattice-based Cryptography basics
Introduction: Polynomial mod \(N\)
Let’s say we have a polynomial \(f(x) = \sum_{i=0}^n a_i x^i\) where \(a_n\neq 0\). Then \(n\) is called the degree of \(f\). We can restrict the domain of \(x\) and the coefficient1 to integers mod \(n\), so we can talk about the roots of a polynomial \(f(x)\equiv 0\pmod{n}\).
- Without the modulo \(n\), we know that no general solutions with elementary operations exists for quintic polynomial or above. However, for integer solutions, we can always use Newton’s method to approximate a root then round off.
- For \(n\) prime, the problem of finding roots of \(f(x)\pmod{n}\) is well-known and we have some fast algorithms to recover all the roots.
- For \(n=p^n\), we can first find the roots of \(f(x)\equiv 0\pmod{p}\), then lift the solutions up to mod \(p^n\) by Hensel’s Lifting Lemma.
- For general composites \(n=\prod p_i^{n_i}\), we can use Chinese Remainder Theorem to combine all the roots mod the individual \(p_i^{n_i}\) to get the desired root.
But how about if we do not know the factorization? The answer is that in general it is hard to solve polynomials if we do not have the factorization. To see why, we note that
has 4 solutions (\(p\) and \(q\) are primes). If \(a\) is a solution to \(f(x)=x^2-1\) mod \(pq\), then \((a-1)(a+1)\equiv 0\pmod{pq}\), so \(a-1\) is divisible by either \(p\) or \(q\) (but not both), then we can factor \(pq\). This shows that solving polynomials mod \(N\) with unknown factorization in general is as hard as factorizing large integers, which we also do not have a fast algorithm for. However, as always, if we can relax our conditions, we may be able to find some solutions.
In the coppersmith method case, we are restricted to finding small roots to a polynomial.
Exercise
- Show that if \(p\) is a prime, then \(x^2-1\equiv 0\pmod{p}\) has exactly 2 solutions (name \(1\) and \(-1\)).
- Use the above to proof that if \(n=pq\) is a product of 2 primes, then \(x^2-1\equiv 0\pmod{n}\) has 4 solutions.
Coppersmith’s Theorem
Most specifically, let \(F(x)\) have integer coefficients be monic and irreducible. And we want to examine the equation
Definition (Monic) A monic polynomial has the leading coefficient (the coefficient corresponding to the largest term) to be 1.
Actually if the leading coefficient is not 1, we can just multiply the whole function by the inverse of that coefficient, and the polynomial will have the same root (if the gcd of it and \(N\) is 1). If the gcd is not 1 then we just found a factor of \(N\).
Definition (Irreducible) A polynomial \(F(x)\) (with integer coefficients) is irreducible if whenever \(F(x)=g(x)h(x)\), one of \(g(x)\) or \(h(x)\) must be the constant polynomial.
This looks like the usual prime number definition, because in the case of integers, prime and irreducible are the same. Here we make the distinction.
Then we can formulate the main result of Coppersmith.
Theorem (Coppersmith) Let \(0<\varepsilon < \min\{0.18,\frac 1d\}\). Let \(F(x)\) be a monic irreducible polynomial of degree \(d\) with root(s) \(x_0\) modulo \(N\) such that \(\lvert x_0\rvert < \frac 1 2 N^{\frac 1 d - \varepsilon}\). Then such root(s) can be found in polynomial time of \(d\), \(\frac 1 \varepsilon\) and \(\log N\).
Application
RSA: Stereotyped Message
Let’s use the RSA setup (\(n=pq\), \(de\equiv 1\pmod{\phi(n)}\), \(E_k(m)=m^e\pmod{N}\), and let the public exponent \(e=3\). Say we have a small message \(m\) to encrypt, and \(m < N^{\frac{1}{3}}\).
If we use textbook RSA, the plaintext can be directly recovered by taking cube root. Suppose we pad the message with ‘1’ bits on the left until the padded message has about the same size as \(N\). Then we have the equation
where we use \(P\) to denote the padding, so
Rearrange to get
which is a cubic polynomial! Check to see the condition of Coppersmith’s theorem is satisfied, so we can apply that to recover the plaintext.
Håstad’s broadcast attack
How about when the message is large? If the padding is linear (perhaps just append or prepend known bits), given at least \(e\) ciphertexts from the same plaintext, we can still recover the message.
Theorem Given \(N_1,\cdots N_k\) are pairwise coprime integers, and \(g_i(x)\) be polynomials of degree at most \(q\). If \(M<\min\{N_1,\cdots,N_k\}\) and \(g_i(M)\equiv 0\pmod{N_i}\) for each i, and \(k>q\), then there exists an efficient algorithm to compute \(M\).
Proof Use Chinese remainder theorem to construct \(g(x)\) such that \(g(M)\equiv 0\pmod{N_1 N_2\cdots N_k}\), then \(M\) and \(g\) satisfies the requirement of Coppersmith’s theorem. Use Coppersmith’s method to recover \(M\).
Bivariate Coppersmith’s Theorem
Another version of Coppersmith’s theorem concerns small roots to bivariate polynomials mod \(N\). Here we have \(F(x,y)\) with integer coefficients again. We can again find small roots for the polynomial mod \(N\).
Theorem (Coppersmith)
Let \(F(x,y)\) be polynomial with integer coefficients and \(d\) natural number such that both \(\deg_x F, \deg_y F \leq d\). Write \(F(x,y)=\sum_{0\leq i,j\leq d} F_{i,j} x^i y^j\) and define \(W=\max\limits_{0\leq i,j\leq d} \vert F_{i,j}\vert X^i Y^j\) for each \(X\) and \(Y\) natural numbers.
If \(XY<W^{\frac{2}{3d}}\) then we can find roots of \(F\) mod \(N\) such that the roots \((x_0,y_0)\) satisfies \(\vert x_0\vert \leq X\) and \(\vert y_0\vert \leq Y\) that runs in polynomial time of \(\log W\) and \(2^d\).
Boneh-Durfee Attack
Recall \(de = 1 + k\phi(n)\). Since \(\phi(n)=n-p-q+1\) we get \(de = 1+ k(n-p-q+1)\).Now reduce modulo $e$ and rearrange to get \(2k(\frac{n+1}{2} - \frac{p+q}{2})+1\equiv 0\pmod{e}\). This way we get a bivariate polynomial \(f(x,y)=2x(A+y)+1\pmod{e}\) with small roots \((x_0,y_0)=\left(k,-\frac{p+q}{2}\right)\). We can use Coppersmith’s method (provided that \(d<N^{0.292}\)) to recover the small root and recover \(d\).
Exercise Explain how to recover \(d\) given the small roots \(\left(k,-\frac{p+q}{2}\right)\).
Howgrave-Graham’s Theorem
Another theorem related to the Coppersmith’s theorem is the Howgrave-Graham’s2 theorem. It allows for an easier proof and better results for Coppersmith’s theorem.
Let’s use the convention that \(F(x)=\sum\limits_{i=0}^d a_i x^i\) be polynomial with integer coefficients with degree \(d\) (so \(a_d\neq 0\)). Let \(x_0\) be a root of \(F(x)\equiv 0\pmod{N}\) such that \(\lvert x_0\rvert < X\) for some integer \(X\). For that \(X\), we associate the polynomial \(F\) with the vector \(b_F = (a_0, a_1X, a_2X^2, \cdots, a_d X^d)\). The norm of a vector \(v=(v_1,\cdots v_n)\) is denoted \(\vert\vert v\rvert\rvert = \sqrt{\sum\limits_{i=1}^n v_i^2}\).
Theorem (Howgrave-Graham) If \(\lvert\lvert b_F\rvert\rvert < \frac{N}{\sqrt{d+1}}\), then \(F(x_0)=0\) over the integers (instead of mod \(N\) only).
Proof First we note that \(\sum\limits_{i=1}^n x_i \leq \sqrt{n \cdot \sum\limits_{i=1}^n x_i^2}\) by Cauchy-Schawarz inequality. Then
\[\begin{align*} \lvert F(x_0)\rvert =& \left\lvert \sum\limits_{i=0}^d a_i x_0^i\right\rvert\\ \leq& \sum\limits_{i=0}^d \lvert a_i\rvert\ \lvert x_0^i\rvert\\ < &\sum\limits_{i=0}^d \lvert a_i\rvert X^i\\ \leq &\sqrt{d+1} \lvert\lvert b_F\rvert\rvert\text{ (By the above lemma)}\\ \leq &\sqrt{d+1}\frac{N}{\sqrt{d+1}}\\ =& N \end{align*}\]So \(-N < F(x_0) < N\). Since \(F(x) \equiv 0\pmod{N}\) this means \(F(x_0) = 0\) (without mod).
Factor \(N=pq\) with partial knowledge of \(p\)
Assume we have an approximation \(\hat{p}\) of \(p\) such that \(p = \hat{p} + x_0\) with \(\lvert x_0\rvert < X\). For example, \(p\) is a \(2k-\)bit integer and \(\hat{p}\) has the same \(k\) MSB as \(p\) (so we know the first half bits of \(p\)), so \(\left\lvert p-\hat{p}\right\rvert < 2^k\). Then we can actually factor the \(4k\)-bit integer \(N=pq\).
We can define the (degree-1) polynomial \(f(x) = \hat{p} + x\), then recovering the small roots of \(f(x)\) mod \(p\) allows us to recover \(p\)! Of course, we do not know \(p\) (that’s the whole point).
However, if we can lift this polynomial to another polynomial \(G\) (with small roots modulo \(p^h\) for some integer \(h\)), such that it satisfies the condition in Howgrave-Graham’s theorem, then we can directly find the the root \(x_0\) with \(G(x_0) = 0\) (and \(f(x_0)\equiv 0\pmod{p^h}\) as well), so we can get \(p\) by doing \(p=\gcd(N, f(x_0))\). Thus we have a similar-looking theorem (originally proved by Coppersmith’s theorem, later improved by Howgrave-Graham):
Theorem Let \(N=pq\), and \(p<q<2p\). Let \(0<\varepsilon < \frac 14\), and \(\hat{p}\) a natural number such that \(\left\lvert p-\hat{p}\right\rvert < \frac{1}{2\sqrt 2} N^{\frac 14 - \varepsilon}\). Then \(N\) can be factored in polynomial time of \(\log N\) and \(\frac 1\varepsilon\).
We will delay the discussion of the derivations for the second part.
Reference
Galbraith, S. D. (2012). Mathematics of public key cryptography. Cambridge University Press.
-
We only study polynomials with integer coefficients, and if the input are integer, the output are also integers. However some other polynomials (with rational coefficients) can also give integer ouputs. Those polynomials (called integer-valued polynomials), while interesting on its own (see: Hilbert polynomial), are not the focus today. ↩
-
Howgrave-Graham is one person, not two person named Howgrave and Graham. ↩