Coppersmith’s Method
首先说说 Coppersmith’s Method 有什么作用。简而言之,就是有一个函数,比如,然后有一个模数,比如 ,然后假设存在一个 满足, 并且如果这个小于某个特定的值,那么就可以用 Coppersmith’s Method 去找到这个。【PS:想要实现这个手法还是需要掌握一点格基规约的相关知识】
总的来说,如果能将 分解,那么找到这个 是容易的,用一个中国剩余定理即可;否则就是困难的。对应的,如果我们能够找到一个解满足 并且这个x不等于,那么我们用一个GCD就能将这个M给分解。具体可参考二十年以来对 RSA 密码系统攻击综述一文。因此,我们并不希冀于有一个有效的算法对于所有这样的同余式都能找到解,否则也就意味着大数分解问题破解了。
既然不能对所有的同余式都能找到解,那能找到解的条件是啥呢?对于度为 的多项式 ,如果 满足 并且,那么这个解 就能在多项式时间内被找到。
First Steps to Coppersmith’s Method
首先我们有在模 下的度为 的并且系数为整数的一个首一多项式:【如果多项式不是首一的,我们整体的系数乘上一个即可,如果在模 下没有逆元,那这条同余式可以拆成同余式组,不过这并不是这一节讨论的重点】假设我们知道存在一个整数 满足 并且 $|x_0|<m^{frac{1}{d}}$,我们的任务就是找到这样的 $x_0$。我们想,如果有这样一条多项式=”” $g(x)$,他的解也是=”” $x_0$。但是他的系数很小,导致$x_0$可以满足$g(x_0)=”0$【注意这里是等式,不是同余式】那么我们是否就可以通过类似牛顿迭代法等算法直接解出方程的解了呢?Coppersmith’s” method=”” 就是想办法去将这个=”” $f(x)$=”” 变形为成为这样的=”” $g(x)$。<=”” p=””>
example 1
假设,,我们想找到一个小根 满足【这里的,但是在整数域下, 】
我们可以找到一个多项式 满足,这个解可以直接用求根公式得到,如果次数比较大,也可以用牛顿迭代法。
这就是一元Coppersmith’s Method核心思路了,其实并不复杂。接下来主要是对这个 的界的一些讨论以及如何尽量的提高这个界的一些手法。
我们定义为这个取值的上界,然后我们将表示为一个行向量
Theorem 1(Howgrave-Graham)
首先我们有这几个上面提到的值
也有
那么,当,则有
proof
首先我们需要知道著名的柯西不等式 ,
设,那么我们有
因而
所以$-M<f(x_0)<m$,又因为$f(x_0)equiv 0=”” pmod{m}$,所以$f(x_0)=”0″ $<=”” p=””>
【这里不等式的第三个就用到了柯西不等式的性质】
这个定理对于确定的边界值很重要。
前面我们找到的 是我们直接给出的,现在开始说这个 该怎么去找,首先我们考虑度为 的多项式 ,还有一个,显然,这里一共 条式子,他们的均有解 ,我们将他们的系数向量组合成一个矩阵
为 的取值上界
显然,这个矩阵的行列式为:
然后我们利用LLL算法做一个格基规约,然后设规约后的矩阵的第一行行向量为 ,这一点需要用到LLL的一个性质就是,
,所以
为了满足Theorem 1,故要求,移项一下可得$2^{frac{d}{4}}sqrt{d+1}X^{frac{d}{2}}<m^{frac{1}{d+1}}$< p=””></m^{frac{1}{d+1}}$<>
如果 ,那么,如果 ,那么。
至此,我们初步的有了一个的取值范围,但这还并未达到的程度。。。
example 2
设 ,多项式,【这里其实我们已经提前知道,所以满足】
这里我们设的上界,所以我们构造格,利用LLL规约后我们可以得到第一行为,所以我们找到多项式,来个牛顿迭代法求根可得
The Full Coppersmith Method
这里回顾一下example 2,即使以 来计算边界也应该是 4.3 左右,那为什么我们设 最终也可以得到正确的结果呢?其实审视一下整个过程,我们最终的目的只是为了获得一组系数,最后规约出来的行向量也都做了相应的”去除X“处理,所以这里对 的取值其实并不用特别严格。
其次,如果不取这个约来的边界,而是直接将 带入$2^{frac{d}{4}}sqrt{d+1}X^{frac{d}{2}}<m^{frac{1}{d+1}}$来计算这个 $x$=”” 的边界,其实边界值应该是=”” $2.07$=”” 左右。嗯?还是那个问题,那为啥我们可以得到正确结果呢?因为其实这个边界值也并不是很严格,在推导得出这个值的时候本身就用了很多次不等式,再者,我们利用的lll中的那个性质,$||b’||≤2^{frac{n-1}{4}}det(l)^{frac{1}{n}}$,我们取的是lll算法规约出来的最坏的情况,而大多数情况得到的结果要比这值小许多。<=”” p=””>
回到这一章的主题,在上面我们对 的取值有不等式:,稍微还原一下是 ,所以想要增加 就有两个思路,一个是往矩阵里多加几行向量来增加格的维度 ,第二个就是增大 了。【这两个方法在公式层面看起来可能不那么直观,公式还需要再变形一下,并且应该也会有一个最优解】
针对第一种方案,我们称这种往格里插入的,增加了格的维度而不增加 的多项式为:“x-shift” polynomial,它们是 ,显然这些多项式在 下的解也为。
针对第二种方案,我们可以利用 的幂来增加,因为,则有
我们继续拿上文中的example 2来举例,之前我们用到的格的维度 ,所以 ,带入那条不等式我们可以得到 ,带入可得,现在我们往格中添加两个多项式,得到
现在我们格的维度为 ,并且行列式为,带入那条不等式可得,现在算出来,可以看到通过添加“x-shift” polynomial,我们确实增大了 。
这里有一个现成的结论就是通过添加“x-shift” polynomial:,我们可以使得,所以当,通过“x-shift” polynomial,我们将 提升为。那么如果在此基础上再增加 呢?
Theorem 2 (Coppersmith)
设$0<epsilon <min{0.18,frac1}{d}} F(x)Mx_0{d}-epsilon}d,frac{1}{epsilon},log(M)$相关的多项式时间内找到它,
proof
设,构造一个格,用过多项式:$G _ {i,j}(x)=M^{h-1-j}F(x)^jx^i,(0≤i<d,0≤j
此时我们运用LLL算法进行规约,我们得到第一行的行向量 ,其满足
由于这里的域M已经提升为,这里我们再用上Theorem 1,从而有$sqrt{dh}2^{frac{dh-1}{4}}M^{frac{h-1}{2}}X^{frac{dh-1}{2}}<m^{h-1}$,< p=””></m^{h-1}$,<>
变形一下为:$sqrt{dh}2^{frac{dh-1}{4}}X^{frac{dh-1}{2}}<m^{frac{h-1}{2}}$< p=””></m^{frac{h-1}{2}}$<>
这里我们换元一下,设,那么我们有$c(d,h)X<m^{frac{h-1}{dh-1}}$< p=””></m^{frac{h-1}{dh-1}}$<>
注意到,我们设,那么有,并且,所以,当 趋向于0时,趋向于,
因为之前我们有 $c(d,h)X<m^{frac{h-1}{dh-1}}$,用上 $epsilon$=”” 就是$c(d,h)x<m^{frac{1}{d}-epsilon}$,所以这里咱如果想要达到coppersmith定理的那个效果,那么我们需要$c(d,h)≤2$,这里我们再次换元,设=”” $alpha=”frac{depsilon}{d-1}$,那么” $c(d,h)=”sqrt2(frac{1}{alpha}+1)^alpha$” ,所以我们要求$(frac{1}{alpha}+1)^alpha≤sqrt2$,因为=”” $epsilon=”frac{d-1}{d(dh-1)}≤” frac{d-1}{d}$,所以$alpha≤1$,所以解得=”” $0≤alpha≤0.18$,<=”” p=””>
结合上面提到的:,由于 ,并且 ,所以当 时,,当$0<d≤5,epsilon<0.18$,< p=””></d≤5,epsilon<0.18$,<>
运行LLL算法用时肯定是跟格的维度,格里面数值大小有关的,又由 ,所以格 的维度,所以时间复杂度与 有关。这里也有一个结论就是,Coppersmith‘s Method的一个大致的时间复杂度为 。
example 3
设
并且我们事先知道根:,所以我们设,注意到。这里我们构造格
注意到,我们这里并没有像 proof 中的那样,加上所有的 ,这里我们只添加量两条 “x-shift” polynomial,额外添加了一条 ,第四行为 。理论上我们还可以针对再添加两条“x-shift” polynomial,但这里并没有这么做,是综合考虑了到的上界 ,和LLL算法运行的时间复杂度。所以这里格的维度是7,行列式 。
这里运行LLL算法,并将第一行的行向量的相应X值去除得到系数向量,可得
小结
原文始发于微信公众号(山石网科安全技术研究院):RSA专题——coppersmith