格攻击

SageMath 🔧 一个非常好用的工具

扩展维纳攻击

当私钥过小时，能够对 \(N\) 进行分解。维纳证明了：

\[ d\lt\frac{1}{3}N^{1\over 4}\\ (q\lt p\lt 2q) \]

的时候，一定能够对 \(N\) 进行分解。

格规约

LLL

Lenstra–Lenstra–Lovász

基于格的约简算法，它将输入矩阵转换为其最简形式。

使用 LLL 或类似的格规约算法找到格中近似最短的非零向量

BKZ

Block Korkine-Zolotarev

是 LLL 算法的一种改进版本，能够更有效地处理高维格。BKZ 算法的基本思想是通过逐步降低格的基向量长度，将原始格转化为一个更紧密的格。这样做可以使格的基向量更加正交，并且可能使格的基向量更接近标准正交基。BKZ 算法通过多次应用基向量间的 Gram-Schmidt 正交化过程和基向量的坐标变换来实现这一点。

一般用 BKZ 效果会比 LLL 好，其中的 block_size 设置越大效果越好，但算得越慢，最大取值是格的维度。

格攻击

格攻击其实是一个启发式算法

基本域

需要用到它的容积

设矩阵 \(B=[b_0,b_1,\cdots,b_{n-1}]\) 为一组格基，则这组格基的基本域为：

\[ \mathscr{F}(b_0,\cdots,b_{n-1}):=\{t_0b_0+\cdots+t_{n-1}b_{n-1}|0≤t_i<1\} \]

基本域的容积等于格基的行列式（的绝对值）:

\[ \text{Vol}(\mathscr{F})=\det(\mathscr{L}(B)) \]

超球体

高维空间的球体，也需要用到它的容积

设 \(\mathbb{B}_R(a)\) 为一个以点 \(a\) 为圆心，半径为 \(R\) 的 \(n\) 维球体，那么 \(\mathbb{B}_R(a)\) 的容积（或者说体积）为：

\[ \text{Vol}(\mathbb{B}_R(a))={\pi^{\frac{n}{2}}R^n\over\Gamma(1+\frac{n}{2})} \]

长度短于 \(\sigma(L)\) 的格向量（约）只有一个，所以如果我们通过计算得到一个向量长度（约）小于 \(\sigma(L)\) ，那么大概率可以确定它是一个最短向量，在维度不高的情况下，可以用 LLL 把他求出来：

\[ \sigma(L)=\sqrt[2]{n\over2\pi e}(\det L)^{1\over n} \]

高斯说，一个以零点为圆心的超球体中格点的数量可以用格的基本域的容积估算。实际上做题常用的 \(\sigma(L)\) 是：

\[ \sigma(L)\approx\sqrt{\det(L)} \]

构造格攻击

需要满足：

\[ ||\vec{w}||\lt(or\approx)\sqrt{\det(L)}\\ ||\vec{w}||^2\lt(or\approx)\det(L) \]

配平

\(\vec{w}\) 的各个参数需要尽量平衡，构造一些 \(D\) 乘在 \(\vec{w}\) 的参数上