[WP] cryptohack mathematics lattices

格！讨厌而重要的东西（恼）
本节全部代码用 sage 实现 (sagemath 9.0)

以及这节的内容好像比较简单（小声）可能是刚入门的原因？

目录传送门：cryptohack 练习学习汇总(writeup index)

Vectors

使用库里的 vector 进行计算

代码: cryptohack/mathematics lattices Vectors.sage

Size and Basis

计算模长：自乘之后开根

代码: cryptohack/mathematics lattices Size-and-Basis.sage

Gram Schmidt

按照题意模拟计算即可

代码: cryptohack/mathematics lattices Gram-Schmidt.sage

What's a Lattice?

按照题意模拟计算即可

可以使用 det 函数计算 Matrix 对象的行列式

代码: cryptohack/mathematics lattices Whats-a-Lattice.sage

Gaussian Reduction

代码: cryptohack/mathematics lattices Gaussian-Reduction.sage

Modular Square Root

一句话题解：利用上题的代码，求 $\{(1,h),(0,q)\}$ 的小的基向量，对应第一个基向量即为 SVP，两个坐标分别对应 f, g

原理：首先我们来看是什么导致了解密过程的正确性

首先，我们有

$$e=rh+m\pmod q$$

解密过程中，我们首先计算

$$a=fe$$

注意到

$$a=fe=frh+fm=rg+fm\pmod q$$

且有

$$rg+fm=\Theta(\sqrt{n})\cdot\Theta(\sqrt{n})+\Theta(\sqrt{n})\cdot\Theta(\sqrt{n})=\Theta(n)$$

换而言之, $a$ 的真实值就是 $rg+fm$！
最后一步

$$m=\frac{a}{f}=\frac{r}{f}g+m=m\pmod g$$

正确性得证

纵观下来，关键点在于发现 $a$ 的真实值就是 $rg+fm$。要满足这个条件，必须有 $g, f$ 都是 $\Theta(\sqrt{n})$ 级别。从某种角度来说，即：只要找到符合 $g',f'<\sqrt{n}$ 且 $f'h=g'\pmod q$ 的 $g',f'$，即可攻破这个体系。

$$f'h=g'\pmod q\Rightarrow f'h=g'+qR$$

即

$$f'(1,h)-R(0, g)=(f',g')$$

也就是说，我们只需要找出 $\{(1,h),(0,q)\}$ 的满足模长小于 $\sqrt{n}$ 的基向量，那么其中较小的那个即可以当做 $(f,g)$ 用于解密。证毕。

一个注意的点：找出来的向量对应的 g 可能为负，此时需要将 f, g 同时求相反数

代码: cryptohack/mathematics lattices Modular-Square-Root.sage

Backpack Cryptography

喜闻乐见！正式的格密码环节！

采用的格（其中 $P_i, i=1,2,\dots,n$ 表示公钥, $S$ 表示明文）：

$$\left( \begin{matrix} 2&0&0&\cdots&0&P_1\\ 0&2&0&\cdots&0&P_2\\ 0&0&2&\cdots&0&P_3\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&0&\cdots&2&P_n\\ 1&1&1&\cdots&1&S\\ \end{matrix} \right)$$

线性空间内必定包括 $-v_{n+1}+\sum\limits_{i=1}^{n}x_iv_i=(2x_1-1,2x_2-1,\dots,2x_n-1,0)$
易知，该向量的前 $n$ 项均为 $\pm1$ 之一，最后一项为 $0$，模长为 $\sqrt{n}$ 很小
因此可以使用格基规约

注意：规约出来后，想要的向量不一定模长最小（这是由于，前面 $P_i$ 之间有可能线性组合得到一个最后一项为 0 的结果），因此要枚举一下找到符合要求的那一行

代码: cryptohack/mathematics lattices Backpack-Cryptography.sage