• 格理论在密码分析和破解这块是个好工具，而CTF又是偏向解题，在密码学这个方向中其实就是对加密过程和密文以及密钥进行密码分析，发现并破解其中潜在的漏洞。所以对于打CTF来说，格理论是不得不学的一个大方向，使用格能破解一些传统加密。
  • 格理论除了在密码分析和破解这块起妙用之外，还基于格的几个困难问题设计了一些与格相关的加密（目前我还不知道加密的效率怎么样，有听别人说，但是自己没体会到。）
  • 其实大二就很想入门格密码学，但是由于时间都花在pwn上，有的时候不仅内耗，还比较浮躁，就导致效率比较低。不过现在大三感觉已经在密码学和pwn这两个方向上已经快突破我的平台期了。大二暑假的时候将初等数论学了个大概（还有指数与原根、连分数、超越数、丢番图，其实原本暑假还打算把抽象代数能学多少就学多少，可惜可惜）。目前有个这么打算高等代数和抽象代数学完，就来学代数数论和解析数论。

参考资料

  • 对于格理论、格密码来说，国外的资料是一大堆的，国内的资料是真没多少。而国外资料又是英文看一页都老半天了。所以在学习格之前，我就先做了点信息收集。

  • 首先是王小云写的一篇论文：格密码学研究，这篇论文并不是学格相关的理论知识，当做看小说一样看一遍下来，对格的整个发展有一个比较清晰的脉络。还有就是该论文中引用比较多的论文，可以看看这些引用的论文。通过看该论文，可以大致了解一些格理论的一些专有名词，比如格的困难问题CVP、SVP等，以及一些定理还有格与机器学习的交叉LWE问题。

  • 目前找到的一本比较系统的写格理论与格密码的书籍了：格理论与密码学 周福才，徐剑编著，这本数是中文的书籍，字还是可以看得比较顺畅的。

  • 还有一本就是涵盖内容比较多的一本英文教材：《COMPLEXITY OF LATTICE PROBLEMS A Cryptographic Perspective》Daniele Micciancio、Shafi Goldwasser著

  • 国外还有一本书：《AnIntroduction to Mathematical Cryptography》Jeffrey Hoffstein、Jill Pipher、Joseph H. Silverman

  • 接下来就是一些视频了，这个是英文视频：2012年BIU密码学冬令营-04-Basic Cryptanalysis（中文字幕）_哔哩哔哩_bilibili

  • 这个是中文的一些教学视频：全同态加密理论: 格密码的数学基础

  • 这个代数数论的视频也有讲一部分格，在第125个视频中：经典代数数论2021

  • 《数的几何引论》朱尧辰

  • 参考博客：初识格 | DexterJie’Blog

格初步认识

格相关概念

  • 这一部分主要简述一下通过阅读一些资料对格这个概念的一些初步认识。没啥图片都是文字。
  • 格密码的发展大体分为两条主线：
    • 一是从具有悠久历史的格经典数学问题的研究发展到近30多年来高维格困难问题的求解算法以及其计算复杂性理论研究
    • 二是从使用格困难问题的求解算法分析非格公钥密码体制的安全性发展到基于格困难问题的密码体制的设计。
  • 格的研究源于1611年开普勒提出的如下猜想：在一个容器中堆放等半径的小球所能达到的最大密度为π18\frac{\pi}{\sqrt{18}}。
  • 1840年前后，高斯引入了格的概念并证明了：在三维空间中堆球，如果所有的球心构成一个格，那么堆积密度所能达到知道最大值为π18\frac{\pi}{\sqrt{18}}。
  • 之后在过去的一个半世纪中，Minkowski、Hermite、Bourgain、Hlawka、Kabatyansky、Levenstein、Lovasz、Mahler、Rogers等著名数学家系统地发展了一般几何体的格堆积与覆盖理论。在这一发展过程中，确定一个几何体的最大格堆积密度和最小格覆盖密度一直是这一个学科的核心问题。（对与格数学的这个发展过程全部都摘抄自王小云教授）。

首先来了解一下格的定义：格是Rm\R^m中一类具有周期性结构的离散点的集合，严格地来说，格是m维欧式空间Rm\R^m的n(m≥n)n(m\ge n)个线性无关向量组b1,b2,...,bnb_1,b_2,...,b_n的所有整系数线性组合即：

L(B)={∑i=1nxibi:xi∈Z,i=1,...,n}L(\mathbf{B})=\{\sum^{n}_{i=1}x_ib_i:x_i\in Z,i=1,...,n\}

向量组b1,b2,...,bn\mathbf{b_1},\mathbf{b_2},...,\mathbf{b_n}称为格的一组基，同一个格可以用不同的格基表示，即存在yi,ciy_i,\mathbf{c_i}使得L(B)=L(C)L(\mathbf{B})=L(\mathbf{C})，m称为格的维数，n称为格的秩。满足m=nm=n的格称为满秩的。通常研究都是研究满秩的格也就是m=n这一情况。

误区：对于格的定义来说，我们只规定了xix_i必须为整数，而bi\mathbf{b_i}向量中的数可以不是整数。而格点其实是格中的向量，由于基向量进行加加减减运算后还是一个向量，这个向量其实是可以用坐标表示的。其几何意义就是从(0,0)通过这个向量指向坐标的一个点。所以格点其实是格向量

对于格的定义来说，现在感觉还是很抽象，直接上图直接，对于格来说，其几何意义就是平面上、空间上离散而又规律的点。

image-20250913191007867

而在空间中，也是许许多多有规律的点，在高中化学物质结构中的一些晶体是由原子构成的，都是这么画的有固定，规律的原子排布。（这么一想量子计算机也是从原子等微观角度出发，格是从这些散点出发，二者好像似乎有点联系唉？）

image-20250913191251506

这里还需要注意：不同的格基，可能生成的是相同的格

image-20250913191734643

image-20250913191742382

注解1：从格的定义出发，如果认真学过线性代数就会发现，这个其实就是线性代数中向量空间基的表达方式。如果使用高中教材向量那一部分来说明的话那其实格的表达其实就相当于向量的一组基底表达。线性代数和高中所学的基底c⃗=xa⃗+yb⃗\vec{c}=x\vec{a}+y\vec{b}，线性代数的表达就不说了（大一线代没好好学都把时间花在学pwn那边了，所以现在回头再看高等代数。），而线代和高中所学的基底x,y的取值范围都是在实数范围之内的，而格这个定义xi∈Zx_i\in Z，说明向量前面的系数是整数。所以格才会是空间中离散的具有周期性的点的集合。

注解2：从格的引入其实可以知道格与几何关系比较密切；从格的定义来说格又是由向量定义的，向量又与矩阵有关，所以格与线性代数、高等代数关系又非常密切；继续从格的定义来说，基底向量的系数都是整数又彻到整数了，那就和初等数论也扯上关系了。（不知道这算不算强行扯关系，按照自己的理解是这样的）。格与以上的数学分支与基础都有关系，那么绝对与抽象代数也很有关系的。

注解3：既然格与这么多数学分支有联系，那么这些数学分支中的某些定理都可以使用到格上。而从格的定义使用向量定义并且也可以使用矩阵表示，那么其实矩阵、向量、向量空间的一些性质都可以使用到格上。可以毫不客气地说学格之前先把线性代数学好或者高等代数学好。

通过对格的逐步了解，了解到了研究个一般研究满秩的格，这里还要做一点说明研究格的这一数学分支似乎被称为几何数论，数的几何引论，在2025.9.11找到了国内的一本书专门讲几何中的格，也就是传统意义上格用来研究的几何体堆叠问题《数的几何引论》朱尧辰

格的基本体(基胞)：

格的基本体是由格基向量生成、并作为在Rn\R^n中代表每个同余类的一个原胞。若格L\mathbf{L}由线性无关的基向量b1,b2,...,bn\mathbf{b_1},\mathbf{b_2},...,\mathbf{b_n}生成即L(B)={∑i=1nxibi:xi∈Z,i=1,...,n}L(\mathbf{B})=\{\sum^{n}_{i=1}x_ib_i:x_i\in Z,i=1,...,n\}，那么格的基本体则定义为：

P(B)={∑i=1ntibi∣0≤ti<1}\mathbf{P(B)} =\{\sum_{i=1}^{n}t_i\mathbf{b_i}|0≤t_i<1\}

误区：根据基胞的定义，tit_i是在0~1任意取值的，这就说明，基胞是一个连续的区域，在二维上就是一个平面，在三维上其实就是一个立体图形。而格点或落在平面或者是立体图形的顶点上，并且图形内部是没有格点的。

如图所示，基胞其实是平行四边形阴影那部分，而格是平行四边形的四个顶点。

image-20250913200242468

将基胞进行平移整数个单位长度，平行四边形的四个顶点也会被移动到不同的地方，从而构成格。
image-20250913200539519

而到三维或者更高维的立体图形来说，其实可以用化学中物质结构进行类比。晶胞就相当于一个基胞，晶胞顶点上的原子就相当于格点，相同的基胞构成了晶格，而基胞平移会构成格。

image-20250913200716037

由于研究的一般都是满秩格，而满秩格一般都会有行列式，接下来就需要介绍一下行列式对于格基本体来说的几何意义。

格的行列式的几何意义：

格的行列式del(L)del(\mathbf{L})的值定义为格基本体P(B)={∑i=1ntibi∣0≤ti<1}\mathbf{P(B)} =\{\sum_{i=1}^{n}t_i\mathbf{b_i}|0≤t_i<1\}的有向面积或者说是有向体积。就比如下图，下图中L=x1b1+x2b2,x1,x2∈Z\mathbf{L} = x_1b_1+x_2b_2,x_1,x_2\in Z，则del(L)del(\mathbf{L})的几何意义就是图中平行四边形的面积（但是带有正负号，具体正负要通过右手定则来判断。）

image-20250913201336510

优质基与劣质基

  • 给定一组基向量，它可以通过整数倍的加加减减，得到一个格。但是这个基有好坏之分的，如何定义这个基的好坏呢？通过研究就有如下评判基的好坏的标准：

一组基如果很容易能表示出格中所有的点，那么这组基就是优质基。

一组基如果表示出格中所有的点非常困难，那么这组基就是劣质基。

注解：由于格是由基的整数倍加加减减，而不是实数倍加加减减，这就导致了对于有些基来说，表示一个靠近原点的格点，都需要10000000v+20000000u这么大的一个系数，也就是说有些格点非常难表示出来。

  • 我们此时已经给优质基和劣质基下了一个定义，那么就我们就需要研究这两种基有什么特征（这样才能一看图片或者一把这一组基从图中画出来就能判断它是优质基还是劣质基了）。研究优质基和劣质基得到了如下特点：

劣质基具有的特点：

  1. 长度差异非常大：基向量有的长度非常长、有的长度又非常短
  2. 基向量夹角接近共线：基向量之间的夹角接近共线，可以是非常接近0°，也可以是非常接近180°

优质基具有的特点：

  1. 长度差异非常小：基向量的长度都大概差不多
  2. 基向量夹角接近正交：基向量之间的夹角接近90°
  • 给出一个图所示：

image-20250914211846300

  • 优质基生成的格，最典型的优质基其实就是正交向量

image-20250914211917982

格基规约

  • 格基规约其实又被称为格基减约，它的英文称为Lattice Basis Reduction，这里就先简单了解一下格基规约的一个概念。

格基规约，都出现了格基了，那么肯定是对表示格的基向量做的操作。由于之前已经有说明了，一个格可以使用不同的基表示。而基有优质基和劣质基之分。那么给定一个劣质基表示的格，其实可以通过某种方法将该格使用优质基表示。

所以格基规约做了这么一件事情：将劣质基转换为优质基，并且俩个基表示的仍然是同一个格，这个操作就被称为格基规约。

  • 对于格基规约来说，目前有俩个比较著名的算法即：LLL算法 Lenstra–Lenstra–Lovász lattice basis reduction，BKZ算法 Block Korkine-Zolotarev lattice reduction

范数(距离)

  • 范数其实就指的是距离，从初一开始接触绝对值，一直到学了勾股定理之后得到了求平面直角坐标系两点之间的距离的方法。这其实就是最经典的欧几里得距离。对于后面所说的向量长度、距离等指的一般都是欧几里得距离

AB=(xA−xB)2+(yA−yB)2AB = \sqrt{(x_A-x_B)^2+(y_A-y_B)^2}

  • 然后到高中一些奇奇怪怪的题，接触到了曼哈顿距离：

AB=∣xA−xB∣+∣yA−yB∣AB = |x_A-x_B|+|y_A-y_B|

  • 到了大学，在学习线性代数或者高等代数的时候，给距离取了一个新的名称范数英文名称为norm，并且给距离下了一个比较统一的定义：

∥x∥p=(∑i=1nxip)1p\|\mathbf{x}\|_p=(\sum_{i=1}^{n}x^{p}_i)^{\frac{1}{p}}

  • 对于曼哈顿距离，其实就是p=1的情况：

∥x∥1=∑i=1n∣xi∣\|\mathbf{x}\|_1=\sum_{i=1}^{n}|x_i|

  • 对于欧几里得距离欧几里得范数，其实就是p=2的情况：

∥x∥2=<x,x>=∑i=1nxi2\|\mathbf{x}\|_2 = \sqrt{<\mathbf{x},\mathbf{x}>}=\sqrt{\sum^{n}_{i=1}x_i^{2}}

  • 还有一种极限的情况如公式如下所示：

∥x∥∞=lim⁡p→∞∥x∥p=max⁡i=1n∣xi∣\|\mathbf{x}\|_{\infty}=\lim_{p \to \infty}\|\mathbf{x}\|_p=\max^{n}_{i=1}|x_i|

格的基本问题

最短向量问题(SVP)

最短向量问题Short Vector Problem,SVP：给定格L\mathbf{L}，找一个非零格向量v\mathbf{v}，满足对任意非零向量u∈L\mathbf{u}\in \mathbf{L}，有∣∣v∣∣≤∣∣u∣∣||\mathbf{v}||≤||\mathbf{u}||。

注解1：是给定一个格找它的最短向量，而不是给定一组基向量找它的最短向量，只不过我们使用一组基向量来描述整个格。

注解2：最短向量问题所描述的找一个非零格向量，这个向量有特地说明是格向量（格向量其实就是用基表示出来的，在图中其实就是格点）。也就是说，我们需要寻找的就是给定格中的一个点（也就是格向量），使得对于其他格L\mathbf{L}的向量来说满足∣∣v∣∣≤∣∣u∣∣||\mathbf{v}||≤||\mathbf{u}||。

注解3：有时候最短向量不唯一，可能有多个。但是最短向量是成对出现的，因为如果找到了一个最短向量，那么它的相反向量其实也是一个最短向量。

注解4：对于一组优质基，该基向量中的其中一个向量很可能就是一个最短向量。对于一组劣质基，该基向量中的一个向量大概率都不是最短向量

几何理解：这里直接给出二维的平面图来说明，SVP在二维上可以使用几何来理解。其实就是找到一个格点，以该格点与原点的距离为半径，以原点为圆心，画出一个圆。这个圆满足如下两个条件：

  1. 该圆的内部除了原点外，不能有其他格点
  2. 格点要么在该圆的圆外，要么在该圆的圆上，而在圆上的点其实就是我们要找的最短向量。

image-20250914203603318

有的时候一个格的最短向量并不唯一

image-20250914204048964

  • 下面这个是劣质基寻找最短向量的一个例图

image-20250914205647979

类比：个人感觉找最短向量问题有点和寻找模意义下的指数有点像。（好像更准确的来说是寻找模意义下给定一个底数，求这个底数的模幂运算的阶？）

r-近似最短向量问题(r-SVP)

逐次最小长度问题(SMP)

最短线性无关向量问题(SIVP)

唯一最短向量问题(uSVP-r)

最近向量问题(CVP)

有界距离解码问题(BDD-r)

判断版本r-近似最短问题(GapSVP-r)

格相关算法

格密码相关问题

小整数解问题(SIS问题)

隐藏子集问题(HSSP)

容错学习(LWE问题)

RLWE问题

MLWE问题

隐藏数问题(HNP)

NTRU问题

AGCD问题