再论格密码
过了一年，在学完了高等代数的情况下再回来看曾经学的知识，已经轻松了不少。
这是在山石夏令营里面听Tover讲的格密码入门学习笔记。
引入
起因是一道题目
bits = 512
while True:
q = random_prime(2^bits, lbound = 2^(bits-1))
R = Gf(q)
f = R(random_prime(2^(bits//2-1)))
g = R(random_prime(2^(bits//2-1), lbound = 2^(bits//4-1)))
if gcd(f, q*g) == 1:
h = f^(-1)*g
break
print('q = %d' %q)
print('h = %d' %h)
#Aim: find f and g
这里面包含的题目条件比较特别：
随机选择大的模数q
选择保密的整数f和g。它们满足范围要求和数值要求
$$
f<\sqrt{q/2}\\sqrt{q/4}<g<\sqrt{q/2}\gcd(f,q\times g)=1
$$计算$h\equiv f^{-1}\times g(mod\quad q)$
那么，我们就得到了一条有三个未知数的方程：
$$
fh-kq=g
$$
显然这是一个有无数个整数解的不定方程，我们稍微改变一下这个方程的写法，把方程的左边变成两个向量相乘的形式。
$$
(h, -k)* (f, q)=g
$$
我们再补上一个事实h=h，使得已知的向量变成一个2×2的矩阵
$$
(h,-k)*
\left[
\begin{matrix}
1 & f\
0 & q
\end{matrix}
\right]
=(h,g)
$$
事实上，大多数NTRU的题目中，寻找这个矩阵就是我们要完成是事情，它应当具有以下的性质。
等式右边的向量的长度，应当小于矩阵的行列式开方。
格
我们知道，两个线性无关的向量的线性组合可以表示一个平面。或者说，一个平面可以被该平面上的两个不平行的向量的线性组合表示，这个时候，我们称这两个向量为这个平面的一组基。
但是，我们想要表示这个平面上的任意一点的前提是，线性组合里面的两个系数都可以是任意实数。但是当我们要求向量和系数都是在某个整数域内的时候，两个向量的线性组合就不会覆盖一整个平面，而是会成为一个个格点的形式，如果是三个线性无关的向量，那么它们的线性组合就会是空间上类似晶格的东西。当向量的个数不断增加的时候，就会越来越抽象。但是不管是几维问题，向量都只有一个长度。
我们称这种基底为格基。显然一个格可以由里面各种非线性组合的向量组成格基，那么这组格基一定有一个长度的最小值。或者说，这些格基的线性组合中一定有长度最短的向量。
有一条式子叫做高斯启发式The Gaussian Heuristic
$$
\sigma (L)=\sqrt{\frac{n}{2\pi e}}\times(det\quad L)^{1/n}
$$
它的意义是在一个任意选择的格中，最短的非零向量满足
$$
||v_{shortest}||\approx \sigma(L)
$$
我们对于这条式子的理解就是，长度小于等于$\sigma(L)$的向量很少或者只有一个，那么如果我们能求出最短的向量，而且题目里面的那个所求的向量确实大小相符，那么我们求出来的很可能是正确的结果。
众所周知在位数面前系数的大小显得很苍白，所以我们一般只比较二进制位数的大小，也就是
$$
||v_{shortest}||\approx det(L)
$$
在这条式子的前后还有非常多的相关描述，但是目前来说我们需要暂时把这条结论记住。
构造
关于开头的构造一个矩阵，其本质就是构造出这样的一个格。请注意这里面已知数的位数和未知数应当具有的位数是经过设计的。
我们所求的f和g的长度应当都不到q的一半，它们组成的向量应当也是差不多的长度，而且矩阵
$$
\left[
\begin{matrix}
1 & f\
0 & q
\end{matrix}
\right]
$$
的行列式就是q，它是2阶的，开平方根得到的结果长度也应当在q长度的一半左右。那么我们只需要求这组格基的最短向量，就很可能可以求出$(f,g)$。
基本题解
q =
h =
#hack
M = matrix(ZZ, [[1, h],[0, q]])
L = M.LLL()
f, g = L[0]
f = abs(f)
g = abs(g)
#check
R = GF(q)
assert R(h) == R(f)^(-1)*R(g)
print('f = %d' %f)
print('g = %d' %g)
配平
如果数字大小不对，那么这也可能是设计。我们还有一点机会可以依葫芦画瓢。
补充
高斯启发式的由来
高斯启发式的局限
- 维度不能太高，否则LLL算法可能不能帮你找到最短向量
- 需要格比较随机，否则可能找错。
- 启发式只是估计，并没有什么证明或者保证只有1个。
