格
这里简单介绍下格规约攻击的原理，写的有些非专业且比较意会，只保留了大致思路以及运作原理，如有出入，就是我太菜了QAQ
简单介绍一下，格规约攻击不是对格密码的攻击，而是借助格对相对“传统”密码的攻击（也不一定是密码体系）
什么是格
我们这里提到的格是这样一个东西：
给定n维空间中一组 线性无关 向量，其 整系数 组合构成的集合称为格
例如有这么一个方程 \[ x*M=b\ \] 其中 \[ \mathbf{x} = \begin{bmatrix}x_1,x_2,x_3,\dots,x_n \end{bmatrix}\\ \mathbf{b} = \begin{bmatrix}b_1,b_2,b_3,\dots,b_n\end{bmatrix}\\ M = \begin{bmatrix}\mathbf{a_1}\\ \mathbf{a_2}\\ \mathbf{a_3}\\ \dots\\ \mathbf{a_n} \end{bmatrix} \] 其中的向量\(x\)中的任意元素\(x_i\in N\)所产生的所有向量\(\mathbf{b}\)的集合，我们把这叫做以为\(M\)基的格\(L(M)\)
格规约原理（应该）
应用前提（部分）
如果我们可以列出这个一个方程 \[ \mathbf{x}*M=\mathbf{b}\ \] 且满足以下条件（当然不只这么一点，但这几个是最重要的）
- \(\mathbf{x}\)中的任意元素是整数
- 矩阵M已知
这种情况下，我们可以尝试用格规约攻击得到目标向量\(\mathbf{b}\)
怎么求\(\mathbf{b}\)
1.存在性证明：这是一个线性方程组，我们也可以把他看成一个坐标转移，把\(M\)看成过渡矩阵，但这里我们的\(\mathbf{x}\)是一个整数向量。\(\mathbf{b}\)是未知的，我们唯一知道的是\(x\)是一个整数向量，对于矩阵\(M\)是已知的。根据上文可知，我们把等式看成坐标转移，也就是说\(\mathbf{b}\)是在空间\(M\)中的，更确切一点的说是\(\mathbf{b}\)在以基为\(M\)的格\(L(M)\)中，其中的基向量是\(M\)中的行向量，我们可以通过用\(M\)中的基向量进行线性组合（其中的系数都为整数，因为格要求是整数的线性组合）后得到\(b\)。
那么问题来了，怎么找到\(\mathbf{b}\)？
2.寻找目标向量
这里提到几个比较重要
SVP问题
一个格中最常见的问题，就是最短向量问题（SVP，Shortest Vector Problem）。问题的定义是这样的：给定一个基为\(B\)的格 \(L(B)\)，找到一个这个格中的一个向量，使得这个向量长度最短。
当格的维数较低是，可以用LLL算法和BKZ算法求出最短向量。
到这，我们已经快要完全掌握了。如果我们要求的向量\(b\)是格中的最短向量，是不是就可以通过LLL或者BKZ求出向量\(b\)，那么怎么确保\(b\)是最短向量？
高斯期望（高斯启发式）
高斯期望（高斯启发式）可以求出最短向量问题，具体证明可以自行查找，结论如下：
假设L是n维格，高斯所期望的最短的长度是 \[ \sigma(L) = \sqrt{\frac{n}{2\pi e}}(Det(L))^{\frac{1}{n}} \] 如果我们能够让格的期望最短长度大于或者远大于我们的目标向量，我们就可以用算法得到最短向量即我们的目标向量\(\mathbf{b}\)。
我们来总结下应用前提：
1.存在方程\(\mathbf{x}*M=\mathbf{b}\),且向量\(\mathbf{x}\)中的元素为整数，矩阵\(M\)已知。
2.矩阵\(M\)的维度较小（一般在几十维到几百维）。
3.矩阵\(M\)的高斯期望大于目标向量\(\mathbf{b}\)，即\(\sigma(M) \gtrsim |\mathbf{b}|\)。
配平技巧及攻击示例
以下展示了一个格规约攻击的示例，包含了构造、配平。如有出入，就是我太菜了QAQ。
拿我最近打的比赛举例：
nctf-绮云
我们可以得到多组相同私钥的rsa。n,e是2048位，d是928位且是复用的，题目就不详细说了，我们这里只举例
对于一组RSA,有 \[ e*d = 1 + k*\phi(n)=1-k*(p-1)*(q-1)=1-k*(N-(p+q)+1)=1-k*N+k*(p+q-1)=-k*N+(k*c+1) = -k*N +c \]
化简成 \[ k_i*N_i+e*d = C_i \] （反正k是整数就对了，不用在意正负）
其中，C的位数大概是 \[ \log_2{k}+\log_2(p+q)=\log_2(o+q)+log_2(d) \approx 1952 \] 我们可以反复退出进入得到多组N,e
然后得到这样一个格，其中系数\(K\)是我们自己决定的 \[ \begin{bmatrix} k_{1} & k_{2} & \cdots & k_{n} & d\end{bmatrix} \cdot \begin{bmatrix} N_{1} \\&N_{2} \\ && \ddots \\ &&& N_{n} \\ e_{1} & e_{2} & \cdots & e_{n} & K \end{bmatrix} = \begin{bmatrix} C_{1} & C_{2} & \cdots & C_{n} & Kd \end{bmatrix} \]
思考，我们要让格的期望最短向量尽可能大，同时让目标向量尽可能小，就需要取一个合理的\(K\)。
我们发现，当\(logKd\lesssim logC_i\)时，\(Kd\)项对目标向量长度的大小影响极小，但能够显著增加格的高斯期望。
但当\(logKd \gg logC_i\)时，\(Kd\)项对目标向量长度的大小起主导作用，即\(|\mathbf{b}| \approx K*d\)，此时增加\(K\)，目标向量长度增长速度就会快于高斯期望增长的速度。
所以当\(Kd \approx C_i\)时是最合适的
再拓展一下就是
目标向量中的每一项大小接近是最合适的（偷懒不证明，嘻嘻）
在这题中，我们让最后一项与前项接近，右边目标向量的长度大概是1952位,格的期望长度是\(\frac{n*2048+1024}{n+1}\)
所以有不等式 \[ \frac{n*2048+1024}{n+1} \gtrsim 1952 \] 解得\(n \geq 10\),所以我们取出10组数据构造格即可得到d，当然n取得越多正确率越高吧
总结
- 这个格构造的时候，我们让目标向量的最后一项的位数尽可能接近\(C_i\)（因为\(K\)是我们自己取的参数）,当最后一项远小于前面项时，他的变化对向量长度影响是极小的，但当它接近或是超过时，就会对目标向量的长度起主导作用。所以在构造格时，我们会尽可能的让目标向量内的元素处在同一数量级，我们把这个技巧叫做配平。（上述提到的只是其中一种配平操作）
- 补充：对于没有K时，我们可以参考：https://ctf-wiki.org/crypto/asymmetric/rsa/d_attacks/rsa_extending_wiener/，给格右乘一个配平矩阵，对得到的新矩阵做运算，然后对得到的向量乘配平矩阵的逆得到真正的目标向量。
