06.格相关的初步理解

从此处开始，为了表述清晰，我们有必要进行符号的约定：

• 数域，用黑板体表示，如“$\mathbb{N},{\mathbb{Z}}^{+}$”等
• 向量，要么是$\overrightarrow{v}$，要么是$\mathbf{v}$​
• 矩阵，粗体，正的字体，比如“$\mathbf{M}$”，通常是大写字母，小写字母通常表示退化成行列向量的矩阵
• 变量，斜字体，不加粗，如$x,y,z,a_i$等
• 有非数学含义的量，正着的字体，不加粗，如“$\text{flag}$”，“$\text{ciphertext}$”等
• 微分符号$\mathrm{d}$也是正着写的，但是这里应该不会用到

格与线性代数

通常我们在密码学题中说的“构造格”是构造一个高维的矩阵，矩阵里的行向量线性无关，由这些向量线性组合可以得到这个“格”规定空间中的其他向量，这些向量构成一个“格”。

线性代数只要超过三维就变得非常抽象（笑），我们简单地举个例子：

对于平面向量$\mathbf{i}=(0,1),\mathbf{j}=(1,0)$而言，它们进行线性组合可以得到平面直角坐标系上所有的“整点”，每个整点都对应一个向量，这些向量的集合就是$\mathbf{i},\mathbf{j}$产生的格。

有了这样形象一点的理解，我们可以来点抽象但严谨的定义了：

给定$n$个线性无关的向量${\mathbf{b}}_1,{\mathbf{b}}_2,\cdots ,{\mathbf{b}}_n\in {\mathbb{R}}^m$（$n$个向量，但是每个向量是$m$维，通常我们研究的这些向量只包含整数），由它们产生的格可以定义为：

$$\mathbf{L}=\{\sum _{i=1}^n{x}_i{\mathbf{b}}_i|x_i\in \mathbb{Z}\}$$

并且称$n$个线性无关的向量${\mathbf{b}}_1,{\mathbf{b}}_2,\cdots ,{\mathbf{b}}_n$是格$\mathbf{L}$的一组基向量。

我有时候会把基向量按照行向量的形式写成一个矩阵并管这叫格（有点不严谨，但是人家确实可以确定一个格），比如

$$\mathbf{M}=\left[\begin{array}{cccccc}1& 0& 0& & 0& a_0\\ 0& 1& 0& & 0& a_1\\ 0& 0& 1& & 0& a_2\\ & & & \ddots & & ⋮\\ 0& 0& 0& \cdots & 1& a_{31}\\ 0& 0& 0& \cdots & 0& -{\text{msg}}_i\end{array}\right]$$

这个格的基向量有33个，每一行都是。

常见格基规约可解的问题

格基规约的意思是在格中找到最短正交基，比如假如一个格的某组基向量长这样：

$$\left[\begin{array}{rrrrrrrrrr}8& 8& 8& 9& 6& 7& 10& 10& 8& 10247674\\ 10& 2& 0& 2& 6& 3& 9& 2& 5& 92918291\\ 3& 6& 8& 5& 5& 8& 5& 1& 3& 82556001\\ 3& 0& 9& 8& 3& 9& 10& 0& 5& 2233153\\ 0& 7& 4& 6& 3& 10& 5& 2& 4& 79477919\\ 2& 9& 5& 1& 1& 6& 2& 0& 7& 12524686\\ 8& 0& 7& 8& 7& 8& 9& 1& 6& 43409005\\ 3& 9& 5& 0& 7& 0& 4& 9& 0& 18897075\\ 5& 4& 3& 9& 1& 9& 8& 3& 2& 87982408\\ 4& 0& 0& 7& 5& 9& 1& 7& 4& 42897437\end{array}\right]$$

我们可以看到，受最后一个数的影响，每个向量的长度都很长，进行格基规约后，生成新的一组向量要短于目前看到的向量，人话就是“想找最短的一组基向量”。进行格基规约后，得到这样的矩阵：

$$\left[\begin{array}{rrrrrrrrrr}-8& -8& 2& 13& -6& -11& -1& -11& 8& 10\\ -2& 3& -10& 11& -9& -22& -8& 15& -1& 11\\ -19& -3& -16& -17& 7& 10& 0& -13& -1& 5\\ -5& -13& -14& 8& -17& 13& 11& 11& -19& -10\\ -10& -9& -2& 0& -14& 25& -22& -15& -13& 6\\ -8& 8& 8& 21& -11& -4& -4& -6& -31& -5\\ 18& -5& -10& 1& -13& -5& 9& -23& -18& -14\\ 10& -9& -28& 12& 16& 7& 16& 5& -9& 14\\ 18& 11& 11& -17& 2& 11& 8& 12& 6& 35\\ 0& -24& 14& -4& 21& -8& -12& 4& -14& -11\end{array}\right]$$

新矩阵的这一组行向量通过线性组合，可以得到和原来一组向量线性组合一样的集合，但是新向量的长度明显短于原来的向量。

拿二维向量举个例子：

$$\mathbf{L}=\left[\begin{array}{rr}474059023& 1\\ 474059024& 1\end{array}\right]\Rightarrow {\mathbf{L}}^{\prime }=\left[\begin{array}{rr}1& 0\\ 0& 1\end{array}\right]$$

格$\mathbf{L}$中所有点恰好是平面直角坐标系的所有整点，又因为能生成平面直角坐标系的所有整点中最短的一组基恰好是${\mathbf{L}}^{\prime }$，故$\mathbf{L}$可以约化为${\mathbf{L}}^{\prime }$。

实现这一过程的算法有LLL算法和BKZ算法等，这些算法可以用于解决简单的背包密码问题。

import random

FLAG=b'flag{??????????????}'
A=[]
R=[]

for i in range(len(FLAG)):
    R.append(random.randint(2^255,2^256))
for it in FLAG:
    A.append(it)

print("r=",R)
s=0
for i in range(len(A)):
    s+=A[i]*R[i]
print("s=",s)

#r= [84708427087077223508746288063337494990202308717440648267330272467894135815924, 71870568665949375571123194758721886986214915618119682637155541122724587843538, 100602777684007543774082898599706333986772386698972675235175116918558786391962, 111285051187103927630378256146929087424914433805356274330547725319174973931277, 64578102072561422481461507204980221906000549452073284469375642403915658526944, 86322141979473667695571199744900761415805265093764192361364761268359524886683, 72011676602309218727623614360157790460724328388438553974216685545015819637985, 105078647996919751921291687976259108242130115531722942052727064034794843311713, 103368664162917561456868191521357206960937667181816315755562413488001589478969, 110217494630018693400232569191132571597769888106563150009902908082060581373688, 102102758556529646879850232401420434521525362134114601318994246006859815684022, 59737283987733589757667947492046903632395451150869436838717031849208989232792, 96939253886687385011366188281125159174552069495814805461361873644813397503683, 114641947042791145846017955279259816732740851376806201344445227298400592825026, 61510532473061488409080784977420763480768150226633374205381891642621350872652, 93205406280652930830657724311733637553372165292401644272052908684168046931905, 93263648785956684648159472389804327266831072351824149657922933965632190434279, 89242559636665509154695981891162231039148956916038357675627491174222218950010, 85806148229998038363438926244130009872932303916869110298400507055220763699223, 76194060752187389247644380773496301324990137770378156568752915597166731745582]
#s= 186821937016204430958110742375961411865713279663457753476144741561954080361297505

这一题的意思很简单，就是给定两个向量，其中一个向量数很大很大，另一个向量是flag的ASCii码，两个向量作数量积的结果也告诉我们了，我们要求的是flag的值。

抽象成数学问题就是已知一组数（向量$\mathbf{r}$的各个数），和这一组数的某个线性组合后的值$s$，想要知道它们是如何进行线性组合的。

我们这样构造格：

$$\mathbf{A}=\left[\begin{array}{cccccc}1& 0& 0& & 0& r_1\\ 0& 1& 0& & 0& r_2\\ 0& 0& 1& & 0& r_3\\ & & & \ddots & & ⋮\\ 0& 0& 0& \cdots & 1& r_n\\ 0& 0& 0& \cdots & 0& -s\end{array}\right]$$

为什么要这样构造格呢？

首先，受$\mathbf{r}$的影响，这个格给出的基向量都很长。并且，这些基向量经过线性组合，是可以生成这样一个特殊向量的：

$$\mathbf{y}=(f_1,f_2,\cdots ,f_n,0)$$

其中$f_1,f_2,\cdots ,f_n$是flag的每一位ASCii码。怎么生成呢？在$\mathbf{A}$的左边乘一个向量$\mathbf{f}$即可：

$$\mathbf{f}=(f_1,f_2,\cdots ,f_n,1)$$

虽然$\mathbf{f}$并不就是格$\mathbf{A}$中的向量，但是按照$\mathbf{f}$进行线性组合是可以得到$\mathbf{y}$的。恰好$\mathbf{y}$相对其他向量而言，很有可能是格$\mathbf{A}$中最短的向量了（基向量都是很大很大的数，能生成的短向量肯定屈指可数），我们对$\mathbf{A}$进行格基规约的结果如下：

n=len(R)
A = Matrix(ZZ, n + 1, n + 1)
for i in range(n):
    A[i,i]=1
    A[i,-1]=R[i]

A[-1,-1]=-1*s
LA=A.LLL()
print(LA)

输出比较长，但是我们发现第一个行向量：

[102,108, 97, 103, 123, 116, 104, 105, 115, 95, 105, 115, 95, 97, 95, 102, 108, 97, 103, 125,0]

即：​flag{this_is_a_flag}​

我通常管这种问题叫“寻找线性组合”的问题。

格密码

这部分的内容较为深奥，后续总结题型时会给出一些讲解。

‍