这次是基于春秋杯和SUCTF都考了RSA的d部分泄露所以想梳理一下LLL算法和coppersmith方法

LLL格基规约算法

首先介绍格，就是假如有一组基向量，可以线性表示(x,y)那就可以表示一整个格空间，基向量不同，格也可以相同，形式化表示格:

由于同一个格也就是L可以由不同的基向量组成，可以通过规约算法得到更好的基向量，新向量的模长比较小

比如，现在要求ar*2+br+c=0的系数，我们可以按下面步骤表达出b1’:
ps:关于b1‘的范围我找了一下似乎是有两个条件，一个是Size条件，一个是Lovász条件
Size:

Lovász:



我们用LLL算法找到一组a，b，c使得ar2+br+c尽量小,所以可为0,从而求出a.b,c

这里要注意基向量属于整数空间，所以还要取整

---

Coppersmith攻击

假设现在有多项式:
f(x0)=kN,k为整数
若f(x0)为0，则x0可以用牛顿迭代法求出，但现在x0不为0，那么我们只要让x0足够小，f(x0)< N,又因为f(x0)模N等于0，那么f(x0)就只能为0
那么现在我们就只需要找到一个系数小的多项式g(x),使得g(x)和f(x)都模N等于0，则g(x)的根就是f(x)的根

例如:

首先用模的特性，将大的系数变成负的

再通过一系列变换，使得系数抵消，绝对值变小

那么coppersmith就延续这个思路，通过乘x的幂和f(x)幂得到一系列h(x)
再通过线性组合得到g(x),再通过LLL格基规约算法来使系数变小，从而变得可以使用牛顿迭代法算出x0

牛顿迭代法

基本思想:设法将一个非线性方程f(x)=0转化为某种方程求解，基于泰勒多项式。
公式:

基本原理：
现在有坐标系x-y，公式的意思可以变为：

画出此坐标系:

由此图可知我们可以借助斜率k,不断作切线，不断向目标x0靠近，从而解出需要的根。
例如:
假设要求X0=1附近的根，由于K非负整数，那么从0开始迭代，求出的X1又代入下一个式子，很快就能求出根