格!讨厌而重要的东西(恼)
本节全部代码用 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