扩展阅读：有关$Ax\equiv y\pmod P$

文章：Wiener’s v.s Lattices —— Ax≡y(mod P)的方程解法笔记 | Tover’ Blog

对于方程$Ax\equiv y\pmod P$，$P$通常为素数，$A$为大数，$x,y$是较小的数，上述方程可以写为：

对于几个参数，有如下大小关系：

$A = Θ(P)$表示上限，也称为渐进紧确界。符号$Θ$表示”渐进紧确界”，表示函数的增长率上下界相当。

$x = O(P^\frac 12)$表示渐进上界，下界不确定。

易得到$k$的量级也在$k≤P^{\frac 12}$上，现在知道$A,P$，需要求解$x,y$，同时我们也不知道$k$，一个方程有三个未知数是不能解的，但是通过知道大小关系，就可以进行求解。

Wiener’s Attack

对于一个连分数展开（$a_0$为整数，$a_1,…,a_n$都是正整数）：

连分数展开通常可以写成简单的数组形式，通常可以使用欧几里得算法进行求解连分数：

收敛：定义$c_i$为连分数每一次分式展开的收敛：

对于每一个$c_i$的结果$\frac {p_i}{q_i}$，都是对连分数不断逼近收敛的近似值。

Legendre’s theorem：对于$a\in Q$，$c,d\in Z$，满足：

$\frac cd$就是$a$的连分数收敛。

对于$Ax-kP=y$，左右同时除$xP$：

根据$x,y≤P^\frac 12$，得到：

进而得到：

所以，根据上面的理论，就可以使用连分数的方法用$\frac AP$的连分数逼近求出$\frac kx$，进而求出$y$。例如RSA中经典的维纳攻击分解$p,q$：

设$\lambda(n)=lcm(p-1,q-1)=\frac{(p-1)(q-1)}G=\frac{\phi(N)}G$，$G=\gcd(p-1,q-1)$。

在RSA中有$ed\equiv 1\pmod {\lambda(n)}$，存在$K\in Z$：

令$k=\frac K{\gcd(K,G)},g=\frac G{\gcd(K,G)}$，得到：

同时除以$dn$，得到：

由于$p,q$为大素数，所以可以认为$\phi(n)≈n,\frac 1{dn}≈0$，得到：

连分数展开，可以求得$k,dg$，代入$①$可以求得$\phi(n)$，使用韦达定理可以求得$p,q$。提供一个sagemath的脚本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import gmpy2

n=10117654819914858266933329374955416887632623769133893090370644563766857602175135282123557069130319485164837923640109707980173187311717714731455048711732890650502393864146567993461691536083330111489342144526034765633893707639465391971659424271400604010051260552831236934617979897198594708643604050329358522040572553492557329327193918343289526476096522685686128709365882540965089876020772451339243051387630968483513100881164719486794479191020450727996212211201807165531274853014517030221518336293845148545671493267736094904720639061287350709209363413742534108909427583009442175135992281621755221466312230819838164838443
e=9821176723459156737162590528498355378679103255669217165700920581299681706733929195884953659518540987340485400582895899813962495604183457377106880733695051072483080763292039235986138262683331839202120494074112671026731661652894069539798773005571447249078493499067926710777981456836165288713067372341722891618455469381820299718375899142104630769808052209736800306823537530231432735329122809506084509365041929994661643608897946882821172042151091436805833261237973879388223150132281413026451714557979869417700194664385291198650864896408143681530963859508908402067374010247738488460155501935400209160082801993945408813513
c=838279327100183842450828959704405383407020841408916285706333834213457887909003957632210005175559669378601653437817015283864372967567045814324446631403131762020243676699045950634510503063630325940620012467503745448306616066932850616255337850567483377961974904557893440882626053258665407295455129124436515237709284339335286446533668177967589716697626618148973094630870394728363810896842456940427809475399274556698585866672673971202275767545143765482579343055060966723452080734906835537296838390574697520016738791840483248208135607782781572593502322902003706653541803004568389346187087997006034664608287414331955367370

convergents = continued_fraction(ZZ(e)/ZZ(n)).convergents()
for c in convergents:
    k = c.numerator()
    d = c.denominator()
    if k!=0 and d!=0:
        phi=(e*d-1)//k
        paddq=n-phi+1  #p+q=n-p*q+(p+q)-1+1
        psubq=gmpy2.iroot(paddq*paddq-4*n,2)[0]  #(p-q)^2=(p+q)^2-4n
        q=(paddq+psubq)//2
        p=(paddq-psubq)//2
        if p*q==n:
          print(p,q)
          break

Lattices

通常方式

对于方程：

如果添加一个恒等的式子：

可以构造出：

记为$vM=w$，推算出$||w||=\sqrt{x^2+y^2}≤\sqrt 2P^\frac 12=\sqrt 2\det(M)^\frac 12≈\sigma(M)$，使用LLL算法可以求出最短向量，求解出$w$。

更紧的界

上述都是考虑$x=\Theta(y)$，如果$x=\omicron(y)$或者$y=\omicron(x)$， 假设：

同样是构造格和方程$vM=w$：

可以得到$w≈(P^\alpha,P^\beta)$，易知$w$的长度由最大的元素决定，因为当出现$\alpha＞\beta$时，$w$的两个元素相差会非常大：

对于$w,M$的第二列同时乘以一个$c$，使得$\alpha=\Theta(c\beta)$，$w$长度不会变化， 但是$\det(M)$会明显变化，即为$\sigma(M)$变大了，大概是$c≈P^{\alpha-\beta}$，构造对角矩阵：

计算得到$||wD||≈\sqrt 2P^\alpha$，有：

想要计算出最短向量，需要：$\alpha＜\frac {1+\alpha-\beta}2$，$\alpha+\beta＜1$，即为$xy≤\Theta(P)$。