[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

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

首先,我们有

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

注意到

且有

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

正确性得证

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

也就是说,我们只需要找出 ${(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$ 表示明文):

线性空间内必定包括 $-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