2024 年下半年网络工程师综合知识卷中出现了一道让不少考生措手不及的题：下列加密算法可以抵抗潜在量子计算攻击的是哪一个，选项依次给出 AES、RSA、同态加密和格密码加密。很多同学凭着对 RSA 的熟悉想当然地选了 RSA，结果失分。这道题背后指向的，是密码学领域正在发生的一次底层重构——后量子密码学，而格密码正是这场重构中最受关注、也最接近落地的一条技术路线。本文从"格"这个数学对象讲起，把量子计算机为什么能击穿 RSA、格密码为什么不怕量子计算机、以及软考命题人会怎么挖坑，一次性讲透。
要理解格密码，必须先理解一个更大的背景概念——后量子密码学。所谓后量子密码学，英文写作 Post-Quantum Cryptography，常缩写为 PQC，指的是这样一类密码算法：它们即使面对一台具备足够多量子比特的量子计算机，其安全性依然不会被破坏。与"量子密码"不同，后量子密码并不依赖量子信道或量子纠缠来传输密钥，它仍然是经典的数学密码，只是把安全性构建在量子计算机难以高效求解的数学难题之上。量子密码解决的是"如何在敌手窃听下分发密钥"的问题，比如量子密钥分发 QKD；而后量子密码解决的是"在量子计算机时代，公钥加密、数字签名这些经典密码功能该用什么算法实现"的问题。两者一字之差，指向却完全不同，这是命题人经常设置的第一层陷阱。
现代公钥密码体系的根基，是一系列在经典计算机上"计算困难"的数学问题。RSA 的安全性建立在大整数分解问题的困难性之上：给定两个大素数的乘积，要想反过来拆出这两个素数因子，经典计算机在现有算法下需要的时间随数位增长呈亚指数级别增长，规模一大就实际上不可行。ECC 椭圆曲线密码的安全性建立在椭圆曲线离散对数问题的困难性之上。正是这种"正着算容易、反着算极难"的不对称性，让公钥加密和数字签名成为可能。然而这种平衡在上世纪九十年代被两篇理论论文打破：1994 年彼得·肖尔提出的 Shor 算法证明，一台足够强的量子计算机可以在多项式时间内完成大整数分解和离散对数求解，这意味着 RSA 与 ECC 赖以生存的困难性，在量子计算面前被彻底抹平。经典计算机上需要宇宙年龄级别的计算量，量子计算机理论上只需数小时甚至更短。公钥密码学因此面临一场结构性的信任危机。
格密码中的"格"，是一个纯粹的数学概念。给定 n 维空间中一组线性无关的向量，把这组向量所有可能的整数系数线性组合全部罗列出来，得到的那个离散而又有规律的点集，就构成一个格。可以把它理解成一张无限延伸、维度任意、每个格点之间距离并不相等的"规则点阵"。一个格可以由不同的基向量生成，同一个格对应的基并不唯一，而且有的基向量彼此接近垂直、规整好用，有的基向量却几乎平行、歪斜难用。正是这种"基的不唯一性"和"从歪基推好基极其困难"的特性，构成了格密码安全性的直觉来源。格上有一个著名的困难问题叫最短向量问题，英文缩写 SVP，要求找到格中除原点外长度最短的那个非零向量。当维度升高时，这个看似朴素的问题在计算上变得异常艰难，至今没有量子算法能在多项式时间内高效求解它。
在量子威胁面前，密码学界并行探索了多条技术路线，目前公认有四大主流方向。第一条是基于格的密码，也是进展最快、标准化最彻底的一条；第二条是基于编码的密码，其代表是 McEliece 密码体制，把安全性建立在一般线性码译码问题的困难性之上；第三条是基于多变量的密码，依赖有限域上多元二次方程组的求解困难性；第四条是基于哈希的签名，代表是 SPHINCS 这类无状态哈希签名方案，只依赖哈希函数的单向性。此外还有基于同源的密码路线，如超奇异椭圆曲线同源密码 SIKE，但这一路线在 2022 年被用一个经典计算机上的攻击彻底击穿后，公信力大幅下降。四条路线中，格密码因为兼具密钥尺寸适中、运算效率较高、功能可扩展性强等优点，成为 NIST 后量子标准化竞赛的最终主力。值得一提的是，基于编码的密码虽然安全性久经考验、抗量子能力同样过硬，但其公钥尺寸动辄以数十万字节计，在实际系统中传输与存储开销过大，制约了大规模推广；基于多变量的密码则在签名效率上有优势，但长期缺乏严格的安全性归约证明。相比之下，格密码在安全强度、密钥尺寸与运算速度三者之间取得了更好的平衡，并且天然支持全同态加密、属性加密、零知识证明等高级密码功能，这是它最终胜出的深层原因。
理解了概念之后，需要回答那个最关键的问题：格密码凭什么敢说自己抗量子。答案不在口号，而在底层困难问题的选择上。密码算法的安全性从来不是"我们猜它安全"，而是"我们找到了一个数学问题，目前所有已知算法——包括量子算法——都无法高效求解它"。格密码正是把安全性锚定在这样一类"量子计算机也无能为力"的格问题上。
要理解格密码的抗量子性，必须先看清楚 Shor 算法的攻击范围到底有多大。Shor 算法本质上是一个强大的"周期查找"工具。大整数分解和离散对数问题，都可以被巧妙地转化为"寻找某个函数的隐藏周期"的问题：只要找到周期，就能用连分数展开等数学手段反推出素因子或离散对数。量子计算机借助量子傅里叶变换，能够在多项式时间内完成这种周期查找，这正是它相对经典计算机的碾压之处。关键在于，Shor 算法只对"具有隐藏周期结构"的一类代数问题有效。大整数分解有周期结构，离散对数有周期结构，所以 RSA 和 ECC 都逃不掉。但格上的最短向量问题、最近向量问题，并不存在这样一个可以利用的隐藏周期结构，Shor 算法的威力在这里使不上劲。这是格密码能抗量子的第一层原因。
格密码依赖的困难问题主要有三个层次。最基础的是最短向量问题 SVP：给定一个格，求出其中长度最短的非零向量。与之并列的是最近向量问题 CVP：给定一个格和空间中的任意一点，求出距离该点最近的格点。这两个问题在高维情形下都被认为是 NP 困难级别的难题，目前既没有高效的经典算法，也没有高效的量子算法。第三个、也是实际方案中最常用的是带误差学习问题，英文缩写 LWE，由雷格夫在 2005 年提出。LWE 可以这样理解：给定一个秘密向量，构造大量"秘密向量与随机向量的内积加上一点人为噪声"的样本，要求从这些被噪声污染的值中恢复出秘密向量。这个"从带噪线性方程组反推秘密"的任务，被证明与最坏情形下的格困难问题一样难，也就是说，只要能高效破解 LWE，就能高效破解格上的最坏困难问题。正是这种"最坏情形归约"给格密码提供了坚实的理论地基。
LWE 之所以能从"困难问题"变成"加密方案"，靠的是一套巧妙的构造逻辑。在加密方向，发送方把要加密的消息比特嵌入到 LWE 样本中去：选择一个公开的随机矩阵和一个秘密向量，计算出带噪声的内积值，再把这个值与消息比特做一个可控的组合。合法接收方因为掌握秘密向量，能够从样本中剥离出噪声、恢复出明文；而攻击者只看到一堆被噪声污染的数值，想恢复秘密向量就撞上了 LWE 难题本身。这个框架之所以优雅，是因为解密时"噪声小到可以容忍"，攻击时"噪声大到足以遮蔽信息"，噪声在同一套方案里扮演了双重角色。加密的密钥是一个从错误分布中采样的小系数向量，解密就是做一次内积并做舍入判断，整体运算以矩阵和向量的线性运算为主，天然适合硬件与并行加速。这套机制构成了现代格密码公钥加密的通用范式，NTRU、Kyber 等方案本质上都是这一范式的不同优化变体。为了控制噪声增长并减小密钥尺寸，实际方案往往在"理想格"或"模格"上工作，也就是把矩阵运算放到一个多项式商环里做，利用环结构把运算复杂度从矩阵级别压到向量级别，这正是 Kyber 名字中"模"字的来历。需要特别强调的一点是，格密码的解密并非百分之百确定，而是存在一个极小的解密失败概率：当采样到的噪声偶然偏大时，接收方可能解出错误的明文。工程上通过精心选择参数，把这一失败概率压到可以忽略的量级，但对于软考考生而言，理解"格密码是一种概率性解密方案、依赖噪声参数调优"这一特性，有助于把握它与其他确定性公钥密码的本质差异。
原理层面讲清楚之后，落到工程与考试层面，需要掌握格密码几个标志性的具体方案，以及它们在标准化进程中的角色。软考的命题趋势正在从"纯概念"走向"方案名与标准的对应关系"，这一节的记忆锚点尤其重要。
在格密码的公钥加密方向上，有两个绕不开的名字。NTRU 是 1996 年由霍夫斯坦、皮弗和西尔弗曼三人提出的基于格的加密体制，也是现存最古老的实用格密码方案之一，其安全性建立在多项式环上带噪声问题的基础上，运算速度快、密钥紧凑，早在二十世纪末就被业界作为抗量子候选方案长期跟踪。Kyber 则是 NIST 后量子标准化竞赛的加密组冠军，其结构可以看作一个经过高度工程化优化的 LWE 型密钥封装机制 KEM。所谓密钥
本篇完！