Coppersmith算法及其应用

发表于 更新于 分类于

速查

LLL算法

\[ ||v_1|| ≤ ||v_2|| ≤ ... ≤ ||v_i|| ≤ 2^{ \frac{n(n−1)}{4(n+1−i)}}det(L)^{\frac{1}{n+1−i}}\\ ||v_1|| ≤ 2^{ \frac{n−1}{4}}det(L)^{\frac{1}{n}} \] #### Minkowski定理

格子L存在向量 \(v\) ，满足 \(||v||\le \sqrt{n}\ det(L)^\frac{1}{n}\)

CopperSmith算法

sage自带

1
2
3
4
n=10001
P.<x> = PolynomialRing(Zmod(n))
f=x^3 + 10*x^2 + 5000*x - 222
f.small_roots(X=10)

参数见 sage doc

多元coppersmith脚本

脚本参考 coppersmith 参数：

  • f 函数
  • bounds 各变量的上界X组成的元组tuple
  • m 模的幂
  • d variable shifts（多元时要手动设置为f的项的个数） #### 定理

\[ 设\ 0 < \epsilon < min\{0.18, \frac{1}{d}\}.\ 设\ F(x)\ 是模M的d阶首一多项式，且拥有小根x_0，满足\ |x0| <\frac{1}{2}M^{1/d−\epsilon}.\\\ 则x_0可以在\ d,\ \frac{1}{\epsilon},\ log(M)的多项式时间内找到. \] 参考 Coppersmith’s Method and Related Applications

算法细节

设多项式为 \[ F(x) = \sum^d_{i=0} a_ix^i \in Z[x] \] 设 \[ x_0\in Z,\ F(x_0)\equiv0\ mod\ M,\ |x_0|<X \] 把多项式F用一个行向量表示为 \[ b_F=(a_0,a_1X,a_2X^2,...,a_dX^d) \]

Howgrave-Graham定理

\[ ||b_F||<\frac{M}{\sqrt{d+1}}\Rightarrow F(x_0)=0 \]

证明

由Cauchy-Schwarz不等式，有 \[ (\sum^n_{i=1}x_iy_i)^2\le (\sum^n_{i=1}x_i^2)(\sum^n_{i=1}y_i^2)\ and\ let\ y_i=1\Rightarrow \sum^n_{i=1}x_i\le \sqrt{n\sum^n_{i=1}x_i^2} \] 所以 \[ |F(x_0)|=|\sum^d_{i=0}a_ix^i|\le\sum^d_{i=0}|a_i||x^i|\le\sum^d_{i=0}|a_i|X^i\le\sqrt{d+1}||b_F||<\sqrt{d+1}\frac{M}{\sqrt{d+1}}=M\ \Rightarrow\ F(x_0)\in(-M,M) \] 所以 \[ F(x_0)\equiv 0\ mod\ M\ \Rightarrow \ F(x_0) \] 考虑这样一个格子 \[ L=\begin{pmatrix} M&0&...&0&0\\\\ 0&MX&...&0&0\\\\ \vdots&&&\vdots&\vdots\\\\ 0&0&\dots&MX^{d-1}&0\\\\ a_0&a_1X&\dots&d_{d-1}X^{d-1}&X^d \end{pmatrix} \] 格子行向量的线性组合与\(F(x_0)\equiv0\ mod\ M\)同解，\(det(L)=M^dX^\frac{d(d+1)}{2}\)

运用LLL算法，可以得到约束 \[ ||b_1||\le2^\frac{n-1}{4}det(L)^\frac{1}{n}=2^\frac{d}{4}M^\frac{d}{d+1}X^\frac{d}{2} \] 再结合一下Howgrave-Graham定理，有 \[ 2^\frac{d}{4}M^\frac{d}{d+1}X^\frac{d}{2}<\frac{M}{\sqrt{d+1}} \] 改写一下 \[ X<c(d)M^\frac{2}{d(d+1)},\ c(d)=(d+1)^{-\frac{1}{d}}2^{-\frac{1}{2}} \] 上界\(M^\frac{2}{d(d+1)}\)还是太小了，可以通过x-shift多项式和\(F(x)\)的幂扩大上界

x-shift多项式：\(xF(x), x^2F(x), ... , x^kF(x)\)

最终版本

\[ 设\ 0 < \epsilon < min\{0.18, \frac{1}{d}\}.\ 设\ F(x)\ 是模M的d阶首一多项式，且拥有小根x_0，满足\ |x0| <\frac{1}{2}M^{1/d−\epsilon}.\\\ 则x_0可以在\ d,\ \frac{1}{\epsilon}和\ log(M)的多项式时间内找到. \]

证明

设\(h>1\)，多项式\(G_{i,j}(x) = M^{h−1−j}F(x)^jx^i\)对于$ 0 ≤ i < d, 0 ≤ j < h$。

构造格子 \[ L=\begin{pmatrix} G_{0,0}(X)\\\\ G_{1,0}(X)\\\\ \vdots\\\\ G_{d-1,0}(X)\\\\ G_{0,1}(X)\\\\ \vdots\\\\ G_{d-1,h-1}(X)\\\\ \end{pmatrix} \] 该格子为下三角矩阵，对角线的元素为\(M^{h−1−j}X^{jd+i}\)，所以 \[ det(L) = M^\frac{(h−1)hd}{2}X^\frac{(dh−1)dh}{2} \] 附上LLL的最短向量条件 \[ ||b_1||\le 2^\frac{dh-1}{2}det(L)^\frac{1}{dh}=2^\frac{dh-1}{4}M^\frac{h-1}{2}X^\frac{dh-1}{2} \] 再附上Howgrave-Graham定理的约束条件 \[ 2^\frac{dh-1}{4}M^\frac{h-1}{2}X^\frac{dh-1}{2}<\frac{M^{h-1}}{\sqrt{dh}} \]

\[ \sqrt{dh}2^\frac{dh−1}{4}X^\frac{dh−1}{2} < M^\frac{h−1}{2} \]

令\(c(d,h)=(\sqrt{dh}2^\frac{dh−1}{4})^\frac{2}{dh=1}=\sqrt{2}(dh)^\frac{1}{dh−1}\)，有\(c(d,h)X<M^\frac{h-1}{dh-1}\)

令\(\epsilon =\frac{d-1}{d(dh-1)}\)，有\(\frac{h-1}{dh-1}=\frac{1}{d}-\frac{d-1}{d(dh-1)}=\frac{1}{d}-\epsilon,\ dh=1+\frac{d-1}{d\epsilon}\)

所以\(c(d,h)=\sqrt{2}(1+\frac{d-1}{d\epsilon})^\frac{d\epsilon}{d-1}\) \[ X<\frac{1}{2}M^{\frac{1}{d}-\epsilon}\Leftarrow\frac{1}{2}\le\frac{1}{c(d,h)}\Leftarrow\frac{d\epsilon}{d-1}\in[0,0.18] \] 所以\(\epsilon\le 0.18\frac{d-1}{d}<0.18\)

注意到，\(dh\approx 1/\epsilon\)，所以当要求更小的\(\epsilon\)时，h要更大，也就是要增加格子L的维度，LLL运算量也会相应增大