前言
填一下以前的坑，补习了一下Wiener's attack和格密码攻击的内容，找到了其中一些共通之处，在这记个笔记（主要做题被暴打了- -
正文
About aX=b%p
设有：
aX≡b\ mod\ p
其中，p是素数（当然不是素数应该也可以？不过为了方便一些条件的讨论，比如求逆，还是假设素数），X是大的数，a和b是小的数，这里说的大小关系是指（特殊情况下a或b还可以大一点？）：
X = \Theta(p)\\
a, b ≤ O(p^{1/2})
根据aX=b%p，可以写成aX+kp=b或aX-kp=b，易得k ≤ O(p^{1/2})（aX=b+kp的话，左右都是≤O(p^{3/2})的量级，p是Ⲑ(p)的，除一下就好了）。
现在假设X和p已知，需要求a和b，那么根据以往的经验，一条方程中有三个未知数是不可解的，但现在有了大小关系的条件，就有两种方法可以解：
Wiener's
现有：
aX-kp=b
左右同除ap：
\frac{X}{p}-\frac{k}{a}=\frac{b}{ap}
由于有a, b ≤ O(p^{1/2})，即有：
\frac{b}{ap} = \frac{1}{ap/b} ≤ \frac{1}{2*a^2}
于是就有了：
|\frac{X}{p}-\frac{k}{a}| ≤ \frac{1}{2*a^2}
就可以用连分数的方法（好像是Legendre’s theorem？），用X/p求出k和a，进而也解出b。（到这步看不懂的话可以翻下面看Wiener's扩展，逃
Lattices
现有：
aX+kp=b
如果增加一个恒等的式子：
a*1+k*0=a\\
aX+kp=b
就可以构造出：
(a, k)*\begin{bmatrix} 1 & X \\ 0 & p \\ \end{bmatrix} = (a, b)
令上面的东西记为：
A*M=B
还记得有a, b ≤ O(p^{1/2})，即可以算出：
||B|| = (a^2+b^2)^{1/2} ≤ O(p^{1/2}) = \sqrt{2}p^{1/2} = \sqrt{2}det(M)^{1/2} ≈ \sigma(M)
所以B有很大概率为M里的最短向量，使用LLL算法reduce后可求出最短向量，即解出B=(a, b) 。（到这步看不懂的话可以翻下面看Latticces扩展，逃
更紧的界
上面考虑的都是a=\Theta (b)的情况，如果 a=o(b) 或者 b=o(a) 呢。首先假设：
a = \Theta(p^\alpha) \\
b = \Theta(p^\beta)
根据上面构造出的A*M=B：
(a, k)*\begin{bmatrix} 1 & X \\ 0 & p \\ \end{bmatrix} = (a, b)
有：
B ≈ (p^\alpha, p^\beta)
推算一下的话可知道，B的长度其实是由“最大”的元素决定的，就是说假设 \alpha>\beta的话，有：
\|B\| ≈ \sqrt{2}\ p^\alpha
也就是如果对M的第二列同乘一个c，使得a=\Theta(cb)的话，B的长度不会变，但det(M)会变大，即\sigma会变大。根据这个思路，可构造对角矩阵D：
D = \begin{bmatrix} 1 & 0 \\ 0 & p^{\alpha-\beta} \\ \end{bmatrix}
然后计算得到：
\|BD\| ≈ \sqrt{2}\ p^\alpha \\
\sigma(MD) ≈ \sqrt{2}\ p^{1/2+\frac{\alpha-\beta}{2}}
要能用Lattices的方法算的话，即：
\alpha < \frac{1}{2}+\frac{\alpha-\beta}{2} \\
\alpha+\beta < 1
也就是 ab≤\Theta(p)即可，也就是a和b一个小一点的话，另一个就可以大一点。 \alpha<\beta的情况也一样。
例题
这里用[IMC]7.1节的NTRU toy scheme来作例子：
根据题目的信息可以推出：
fh≡g\ mod\ p\\
h = \Theta(q)\\
f, g ≤ O(q^{1/2})
Wiener's做法：
#!/usr/bin/env sage
from Crypto.Util import number
BITS = 128
q = number.getPrime(BITS)
#f = number.getRandomRange(2, floor((q//2)^(1/2)))
#g = number.getRandomRange(2, floor((q//2)^(1/2)))
f = Integer(randint(2, floor((q//2)^(1/2))))
g = Integer(randint(2, floor((q//2)^(1/2))))
h = (f.inverse_mod(q)*g) % q
print('q = %s' % q)
print('f = %s' % f)
print('g = %s' % g)
print('h = %s' % h)
# debug
k = (f*h-g)//q
assert (f*h)%q == f*h-k*q
print((h/q-k/f) < 1/(2*f^2))
# end debug
f2 = f
g2 = g
N = 20000
fra = (h/q).n(N).exact_rational().continued_fraction()
for i in range(len(fra)):
k = fra.numerator(i)
f = fra.denominator(i)
if f<=floor((q//2)^(1/2)) and f*h-k*q==(f*h)%q:
g = f*h-k*q
if g <= floor((q//2)^(1/2)):
print(f2==f and g2==g, f, g)
在实践时搞出来的f和g有时会是原f和g的某个倍数（或整除），虽然还是符合fh≡g\ mod\ p
Lattices做法：
#!/usr/bin/env sage
from Crypto.Util import number
BITS = 128
q = number.getPrime(BITS)
#f = number.getRandomRange(2, floor((q//2)^(1/2)))
#g = number.getRandomRange(2, floor((q//2)^(1/2)))
f = Integer(randint(2, floor((q//2)^(1/2))))
g = Integer(randint(2, floor((q//2)^(1/2))))
h = (f.inverse_mod(q)*g) % q
print('q = %s' % q)
print('f = %s' % f)
print('g = %s' % g)
print('h = %s' % h)
M = matrix([
[1, h],
[0, q]
])
# debug
k = -(f*h-g)//q
assert (f*h)%q == f*h+k*q
a = vector(ZZ, [f, k])
b = vector(ZZ, [f, g])
assert a*M == b
lenB = (b*b)^(1/2)
detM = M.det()
print(lenB.n(10) <= ((detM)^(1/2)).n(10))
# end debug
f2 = f
g2 = g
L = M.LLL()
b = vector(ZZ, L[0])
f = abs(b[0])
g = abs(b[1])
print(f2==f and g2==g, f, g)
同样还是会有倍数的问题，但其实两个方法的倍数都很小，还是可以爆破出来（如果有条件爆破的话-
What about a_iX_i=B\ \%\ p ？
(前两天被吊打的hws)
如果是B是未知大数的情况怎么样呢，即：
a_iX_i≡B\ mod\ p \\
X_i, B = \Theta(p)\\
a_i ≤ O(p^{1/2})
知道X和p，求a和B。如果有多组这样的式子的话是可以转化成aX=b%p的情况的。
先来看一下a_iB=X_i\ \%\ p的情况：
a_1B≡X_1\ mod\ p \\
a_2B≡X_2\ mod\ p
可以推出（不排版了，能看懂就好-）：
a' = (X_1B^{-1}≡a_1\ mod\ p)\ \ \ \ \ \ ≤ O(p^{1/2}) \\
b' = (X_2B^{-1}≡a_2\ mod\ p)\ \ \ \ \ \ ≤ O(p^{1/2})\\
X' = ({X_1}^{-1}X_2≡{a_1}^{-1}a_2 \ mod\ p)\ \ \ \ \ \ \ \ =\Theta(p)
即可消去未知大数B：
a'X' ≡ b' \ mod\ p
再来看回a_iX_i=B\ \%\ p，其实只要稍微转化成：
a_iB^{-1}=X_i^{-1}\ \%\ p
就是上面的情况。
What about a_iX_i=B_i\ \%\ p ？
按照上面的经验，要解这东西，就要消去B_i，但我目前没有找到消去的方法，所以暂时不会解（？？？
What about \sum_{i=1}^{n} a_iX_i ≡ b \ mod\ p
\sum_{i=1}^{n} a_iX_i ≡ b \ mod\ p \\
\sum_{i=1}^{n} a_iX_i +kp = b \\
\ \\
(a_1, a_2, ..., a_n, k)
\begin{pmatrix}
1 & 0 & \cdots & 0 & X_1 \\
0 & 1 & \cdots & 0 & X_2 \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & \cdots & 1 & X_n \\
0 & 0 & \cdots & 0 & p \\
\end{pmatrix}
= (a_1, a_2, ..., a_n, b)\\
\ \\
记为 A*M=B
记a = max(a_i)，有：
\sigma(M) ≈ \sqrt{n+1}\ p^{1/(n+1)} \\
||B|| ≈ \sqrt{n+1}\ a
所以只要有 a≤O(p^{1/(n+1)}) 就可解 a_i 。
PS：这个矩阵跟解背包密码（Knapsacks）的那个矩阵有点像，但又不完全像，因为两个问题其实就有点像，但又不完全像（逃
What about \sum_{i=1}^{n} a_iX_i ≡ Y \ mod\ p
如果现在等式右边是大数Y，而且Y已知的话，就是背包密码（Knapsacks）的解法了：
\sum_{i=1}^{n} a_iX_i ≡ Y \ mod\ p \\
\sum_{i=1}^{n} a_iX_i +kp - Y = 0 \\
\ \\
(a_1, a_2, ..., a_n, k， -1)
\begin{pmatrix}
1 & 0 & 0 & \cdots & 0 & 0 & X_1 \\
0 & 1 & 0 & \cdots & 0 & 0 & X_2 \\
0 & 0 & 1 & \cdots & 0 & 0 & X_3 \\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\
0 & 0 & 0 & \cdots & 1 & 0 & X_n \\
0 & 0 & 0 & \cdots & 0 & 1 & p \\
1 & 1 & 1 & \cdots & 1 & 1 & Y \\
\end{pmatrix}
= (a_1-1, a_2-1, ..., a_n-1, k-1, 0)\\
\ \\
记为 A*M=B
记a = max(a_i)，有：
\sigma(M) ≈ \sqrt{n+2}\ Y^{1/(n+2)} \\
||B|| ≈ \sqrt{n+2}\ a
注意到这里其实B的最后一个元素是0，所以如果M的最后一列和B的最后一个元素同乘一个超大的C的话（即M和B同乘一个对角阵D，D的对角线上的最右下一个是C，其他是1），det(M)会变大，而B则不变，可以得到：
\sigma(MD) ≈ \sqrt{n+2}\ (CY)^{1/(n+2)} \\
||BD|| ≈ \sqrt{n+2}\ a
所以如果C足够大的话，就会有\|BD\| ≤ \sigma(MD)，即可解 a_i
What about a_iX_i ≡ b_i \ mod\ (P+s)
现在假设原来的p可以拆成(P+s)，P已知，s未知但一定会存在：
X_i = \Theta(P) \\
a_i ≤ O(P^\alpha) \\
b_i ≤ O(P^\beta) \\
s ≤ O(P^\gamma)
有时(P+s)的值并不知道，但会知道P的值，比如RSA中，\phi(N)并不知道，但会知道 N=\phi(N)+(1-(p+q))，用类似 扩展维纳攻击[HS99] 的方法可以用(P+s)代替P，然后用格的方法做，但需要的a和b要更小。（其实这部分就是在讲扩展维纳攻击）
假设现在是有两组的情况：
a_1X_1 ≡ b_1 \ mod\ (P+s) \\
a_2X_2 ≡ b_2 \ mod\ (P+s)
拆开：
a_1X_1+k_1P = b_1-k_1s \ \ \ \ \ \ \ \ ① \\
a_2X_2+k_2P = b_2-k_2s \ \ \ \ \ \ \ \ ②
可以看到①和②两个方程的未知数很不一样，即很难构造像之前的线性方程，但是看一下①*②的式子：
①*② = (a_1X_1+k_1P)(a_2X_2+k_2P) = X_1X_2a_1a_2+X_1Pa_1k_2+X_2Pa_2k_1+P^2k_1k_2
通过①*k_2和②*k_1的方式，构造出来的未知数不会比①*②中的多，于是就可以构造出下面四条方程（构造时尽量弄成上三角的矩阵）：
恒等式引入k_1k_2
k_1k_2 = k_1k_2
①*k_2
X_1a_1k_2+Pk_1k_2 = k_2(b_1-sk_1)
①*k_2-②*k_1
X_1a_1k_2-X_2a_2k_1 = b_1k_2-sk_1k_2-(b_2k_1-sk_1k_2) = b_1k_2-b_2k_1
①*②
X_1X_2a_1a_2+X_1Pa_1k_2+X_2Pa_2k_1+P^2k_1k_2 = (b_1-k_1s)(b_2-k_2s)
重点关注第3条，很巧妙地把右边的sk_1k_2消去了，使得\alpha或\beta可以更大一点，这也是扩展维纳攻击d的大小比普通维纳攻击d的大小大一点的原因（吗？
于是就有：
(k_1k_2, a_1k_2, a_2k_1, a_1a_2)
\begin{pmatrix}
1 & P & 0 & P^2 \\
0 & X_1 & X_1 & X_1P \\
0 & 0 & -X_2 & X_2P \\
0 & 0 & 0 & X_1X_2
\end{pmatrix} \\
=(k_1k_2, k_2(b_1-sk_1), b_1k_2-b_2k_1, (b_1-k_1s)(b_2-k_2s))
记作A*M=B，跟之前同样的方法构造D把B弄齐次（这里先假设 \alpha+\gamma \ge \beta）：
B ≈ (P^{2\alpha}, P^{2\alpha+\gamma}, P^{\alpha+\beta}, P^{2\alpha+2\gamma}) \\
D =
\begin{pmatrix}
P^{2\gamma} & 0 & 0 & 0 \\
0 & P^{\gamma} & 0 & 0 \\
0 & 0 & P^{\alpha-\beta+2\gamma} & 0 \\
0 & 0 & 0 & 1
\end{pmatrix} \\
可以计算：
\sigma(MD) ≈ 2P^{1+\frac{5\gamma+\alpha-\beta}{4}} \\
\|BD\| ≈ 2P^{2\alpha+2\gamma}
要最短向量为B即：
\|BD\| ≤ \sigma(MD) \\
2\alpha+2\gamma ≤ 1+\frac{5\gamma+\alpha-\beta}{4} \\
7\alpha+\beta+3\gamma ≤ 4
在扩展维纳攻击中是\beta=0，\gamma=1/2，所以算出\alpha≤5/14。
另外，在假设 \alpha+\gamma<\beta 的情况下，推出：\alpha+\beta ≤ 1，即和之前一样 。
可以看出上面的情况\alpha和\beta的系数和都是右边的两倍，而且还引入了\gamma，所以在\alpha≈\beta的情况下，\alpha和\beta都需要更小（不会比已知(P+s)的解法更优）。
What about x_i=pq_i+r_i
其实这是ACD问题，参考[GGM16]，和21wmctf的easylsb。
现有（个人更喜欢加的，所以把论文的符号换了一下。。。）：
p = \Theta(2^\alpha)\\
q_i = \Theta(2^\beta)\\
r_i = \Theta(2^\rho)\\
\rho<\alpha\\
\rho<\beta\\
↓\\
x_i = \Theta(2^{\alpha+\beta})
其中[GGM16]第三章中提到一个技巧，x是很大的，但是q_0x_i-q_ix_0可以减少规模：
q_0x_i-q_ix_0=q_0(pq_i+r_i)-q_i(pq_0+r_0)=q_0r_i-q_i-r_0\\
2^{\alpha+2\beta} → 2^{\beta+\rho}
于是构造：
(q_0, q_1, ..., q_t)
\begin{pmatrix}
R & x_1 & x_2 & \cdots & x_t \\
0 & -x_0 & 0 & \cdots & 0 \\
0 & 0 & -x_0 & \cdots & 0 \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & 0 & \cdots & -x_0 \\
\end{pmatrix} _{(t+1)*(t+1)} \\
=(q_0R, q_0x_1-q_1x_0, ..., q_0x_t-q_tx_0)\\
=(q_0R, q_0r_1-q_1r_0, ..., q_0r_t-q_tr_0)
记上式为vL=w，其中设R=2^\rho，这里的R的作用其实是上面“更紧的界”里说的要把w配齐次。可以算出：
\sigma(L) ≈ \sqrt{t+1}\ 2^{(t(\alpha+\beta)+\rho)/(t+1)} \\
\|w\| ≈ \sqrt{t+1}\ 2^{\beta+\rho}
要能用格解，则：
\beta+\rho \le (t(\alpha+\beta)+\rho)/(t+1)\\
\beta \le t(\alpha-rho)
在“easylsb”中是t=4, \beta=\alpha=512, \rho=368，512 \le 4(512-368) = 4*144=576
(PS：瞎写的，待验证)
Wiener's 扩展
现在说的Wiener's attack指Wiener在[Wiener90]提出的针对RSA的攻击，但其实更多时候说的是他用到的方法，即Legendre’s theorem（其实这里说的也是，也许只是Wiener当时的攻击比较出名？）：
就是说如果能找到\alpha符合上面的关系的话，那p/q就是\alpha那堆连分数里的其中一个，\alpha是知道的，所以\alpha的连分数可以求出来，p和q就是\alpha某一个连分数的分子和分母（当然也可能会是某个倍数）。
Wiener's attack说的是在RSA中，当d很小时（d<\frac{1}{3}N^(1/4)），可以通过连分数的方法解出d。先来看看RSA的密钥生成，ed ≡ 1 \ mod\ \phi(N)，e是大的，d是小的，1是小的，刚好符合上面说的方程大小关系，于是可以：
ed ≡ 1 \ mod\ \phi(N) \\
ed-k\phi(N) = 1 \\
|\frac{e}{\phi(N)}-\frac{k}{d}| = \frac{1}{d\phi(N)} < \frac{1}{2d^2}
好像可以解，但问题在于\phi(N)是不知道的，于是需要一些“近似替换”的方法。由于p, q ≈ O(N^{1/2})，所以：
\phi(N) = (p-1)(q-1) = N-p-q+1 ≈ N
于是就可以用N来近似\phi(N)，由于N是知道的就可以求k和d，但需要一个证明[Bon99 Th.2]：
然后就可以愉快地用e和N计算k和d了。
Wiener's attack是1990提出来的东西了，所以后来也有了很多改进的版本，用其他的东西近似替换\phi(N)，而不是用N，比如
上面那个是[OP12]里的一个定理：
2020的湖湘杯的crypto4就照搬了这个定理（网上找不到writeup，最近拿出来鞭尸x）（原题忘了，只剩个图）
wp：https://paste.ubuntu.com/p/DBmB5RntqB/
Lattices 扩展
格（Lattices）的话可以看成是一个向量空间里的一堆点，就是一组基通过“整数”的线性组合“张成”的空间（具体可以看[IMC]的7.4，那里会说得更详细）。
这里主要说一下用格解方程的方法和原理。主要用到一个叫Gaussian expected shortest length的东西：
就是说，在格L中的最短非零向量的长度大概有\sigma(L)那么长，如果可以构造出整数向量A、B和格L（其中A、B未知，L已知），使得：
A*L = B \\
||B|| ≤ \sigma(L)
的话，B就大概率是L的最短向量（第一个式子说明向量B在格L中，第二个式子说明B大概率是L的最短向量），通过找L的最短向量可解出B，通过B*L^{-1}可解A。在L的维度不大的情况下，用LLL算法可以找到L的最短向量（Sage中可以直接调用，详细原理可以看[IMC]的7.13），LLL算法主要用于把“垂直程度低”的格“reduce”成“垂直程度高”的格，而且reduce后的第一个基即是L的最短向量（见下图性质）。另外格很“垂直”的话，就可以用Babai的算法解CVP问题（略）。
总结来说，只要构造出L和A*L = B并且符合||B|| ≤ \sigma(L)的关系的话就可以解出A和B，然后利用A和B中的元素解决其他的问题。在用格攻击密码算法时基本都是这个套路，（所以略了）
另外有个叫扩展维纳的攻击也用到这个套路，这里引一下[Gm1y]大佬的博客，里面基本说的很清楚了，里面一个“通过对矩阵的列乘上一个倍数”的方法也非常有用（但里面没详说hhh）：
由于有下面的关系：
就有：
B ≈ (N^{2\alpha}, N^{2\alpha+1/2}, N^{\alpha}, N^{2\alpha+1})
B的长度其实由最大的元素决定的，即现在是：
||B|| ≈ \sqrt{2}*N^{2\alpha+1}
如果A*L=B左右同乘对角阵D，使得B的元素“齐次”（即每个元素指数规模一样，为2\alpha+1），那么B的长度几乎不变，但L的行列式会变大，即\sigma(L)变大，通过计算（就是2\alpha+1减去原指数的值）可得对角阵每个元素为：
D → (N^1, N^{1/2}, N^{\alpha+1}, 1)
即[Gm1y]博客里的值。
总结
一个方程里如果知道所有的“大数”（包括未知的“大数”可以消去的情况），可以用Wiener's（Legendre’s theorem）或格（Lattices）的方法解出未知的“小数”。这里的具体大小关系可能需要计算一下，一般会是 小数≤O((最大数)^{1/小未知数的数量}) （当然，只是一般，-
我个人比较偏向用格的方法（很明显上面写的几乎都是用格的-），感觉格的话会更通用（特别高维的情况），但也不排除自己对Legendre’s theorem那堆东西不是很熟了（逃
另外，遇到不等式的关系时可以多考虑Wiener's的方法；遇到等式时可以考虑Lattices的方法。
引用
[IMC] Hoffstein J, Pipher J, Silverman J H, et al. An introduction to mathematical cryptography[M]. New York: Springer, 2008.
[Wiener90] M. J. Wiener, Cryptanalysis of short RSA secret exponents", IEEE Transactions on Information Theory, vol. IT(36), pp. 553-558, 1990.
[Bon99] Boneh D. Twenty years of attacks on the RSA cryptosystem[J]. Notices of the AMS, 1999, 46(2): 203-213.
[OP12] Ojha N, Padhye S. Weak Keys in RSA over The Work of Blomer & May[J]. Int. J. Netw. Secur., 2012, 14(2): 80-85.
[HS99] Howgrave-Graham N, Seifert J P. Extending Wiener’s attack in the presence of many decrypting exponents[C]//International Exhibition and Congress on Network Security. Springer, Berlin, Heidelberg, 1999: 153-166.
[GGM16] Galbraith S D, Gebregiyorgis S W, Murphy S. Algorithms for the approximate common divisor problem[J]. LMS Journal of Computation and Mathematics, 2016, 19(A): 58-72.
[Gm1y] 密码学硬核笔记——扩展维纳攻击
PS：其实后来我在博客上改/加了挺多东西的，后来想merge到论坛的时候嫌太太太太太多公式要改了就算了（懒），所以可以直接访问https://tover.xyz/p/wieners-lattices-equations/；不过原则性的错误这里都有修改（逃