再论格密码

过了一年，在学完了高等代数的情况下再回来看曾经学的知识，已经轻松了不少。

这是在山石夏令营里面听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
$$
我们再补上一个事实f=f，使得已知的向量变成一个2×2的矩阵
$$
(f,-k)*
\left[
\begin{matrix}
1 & h\
0 & q
\end{matrix}
\right]
=(f,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)