2.1 基于格的密码
2.1 基于格的密码
本节摘要：SOURCE 2.1：格密码基于 LWE/Ring-LWE/Module-LWE 等难题，NIST 选中 CRYSTALS-Kyber（KEM）与 CRYSTALS-Dilithium（签名）。本节对比格方案与 RSA 的密钥尺寸与性能。
先说结论
- 解释 LWE 问题的直觉难度
- 区分 Kyber（KEM）与 Dilithium（签名）用途
- 列出 Falcon 作为紧凑签名的备选特点
一、格密码基础（SOURCE 2.1）
在 n 维格中寻找最短向量（SVP）或带误差向量（LWE）在量子与经典下均难解。
| 算法 | 类型 | NIST 状态 | 典型用途 |
|---|---|---|---|
| Kyber | KEM | 标准（2022） | TLS 密钥封装 |
| Dilithium | 签名 | 标准（2022） | 证书、代码签名 |
| Falcon | 签名 | 标准（2022） | 更小签名尺寸 |
二、与 RSA 对比
| 指标 | RSA-2048 | Kyber-768 |
|---|---|---|
| 公钥 | ~256 B | ~1184 B |
| 密文 | — | ~1088 B |
| 量子安全 | 否 | 是（假设下） |
⚠️ 常见坑：混淆 KEM 与公钥加密——Kyber 封装对称密钥，不直接加密长消息。
💡 关键直觉：格家族是 NIST 主航道，工程资源优先投这里。
重点提炼
- LWE/Module-LWE 是 Kyber/Dilithium 基础
- Kyber=KEM，Dilithium/Falcon=签名
- 密钥比 RSA 大但可接受
- NIST 首选家族
深入讨论：从 LWE 到 Kyber/Dilithium 的工程化路径
LWE 问题的直观困难在于：给定一个公开矩阵与一段含噪声的线性方程，恢复未知向量在计算上非常困难。把这个抽象问题落到实际算法时，纯粹的 LWE 密钥太庞大，于是密码学家引入结构化——把向量换成多项式环上的乘法，得到 Ring-LWE；再折中为若干小维度的模块结构，得到 Module-LWE。Kyber 与 Dilithium 都以 Module-LWE 为基础，既比纯 LWE 紧凑，又比 Ring-LWE 保留了更可信的安全归约，这是它们能成为标准的重要工程原因。
Kyber 的定位是 KEM，它解决的是「双方如何安全地商定一个对称密钥」。封装过程把随机秘密编码进密文，解封装通过解密噪声获得共享秘密。Dilithium 的定位是签名，它利用 Fiat-Shamir 变换把交互式协议变成一次性签名，安全性同样落在格问题上。两者共享大量数学结构，因此在实现上可以复用数论变换 NTT 与多项式的快速运算代码，这也是 4.2 硬件加速一章讨论 FPGA 加速的出发点。
# Kyber-768 与 Dilithium3 的核心参数（用于选型参考） 算法 类型 公钥 密文/签名 安全级别 典型用途 Kyber-768 KEM 1184 B 1088 B Level 3 TLS 密钥封装 Dilithium3 签名 1952 B 3293 B Level 3 证书、代码签名 Falcon-512 签名 897 B 690 B Level 1 带宽敏感签名 SPHINCS+-128s 签名 32 B ~7856 B Level 1 哈希保守备份
选型时一个常被忽略的细节是公钥与密文的尺寸差异会直接影响协议层设计：TLS 握手要求密钥份额能装进 ClientHello 扩展，Kyber 的 1184 B 公钥与 1088 B 密文在多数网络下没有问题，而某些签名算法的超大签名则可能超过 UDP 包上限，这对 VPN 与固件更新场景影响很大。因此本章对比表的最后一行往往决定某个算法能不能进某个协议，而不是单纯比数学上的安全强度。
工程实践扩展：Kyber 与 Dilithium 的常见实现误区
实现格密码时，最常见的误区是把 KEM 当成公钥加密来用。Kyber 的封装只能携带一个对称密钥，不能直接加密任意长度的消息；如果业务里需要「加密一段数据」，正确做法是先封装出会话密钥，再用 AES-GCM 加密数据，而不是试图让 Kyber 直接吃长消息。第二个误区是忽略公钥与密文的尺寸在握手中的真实开销：一次 TLS 握手要同时传输证书链与密钥份额，公钥变大意味着握手包变大，对移动网络与低带宽链路影响明显。
第三个误区集中在签名侧的参数选择。Dilithium 的不同参数集签名尺寸差异很大，Dilithium3 签名约 3293 B，而 Falcon-512 只有约 690 B；在 MTU 受限的 IoT 更新场景，选错参数可能导致签名需要分片传输，增加复杂度。性能数据也值得实测而非只看文档：不同 CPU 上 NTT 实现的差距可达数倍，正式选型前应在目标硬件上跑基准。
# 格密码实现自检清单 1. 确认 Kyber 只做密钥封装，长消息走对称加密 2. 核对握手包总长：证书 + 公钥 + 密文 vs MTU 3. 在目标 CPU 上实测封装/签名耗时，不沿用文档值 4. 确认随机源质量，防止封装与签名随机数可预测 5. 统一安全级别：KEM 与签名用同 Level 参数 6. 与 liboqs KAT 向量比对后再进入性能调优
最后一条尤其重要：性能优化必须在 KAT 验证通过之后进行。先证明实现正确，再优化速度，顺序颠倒的团队往往在排错上耗费数倍于优化省下的时间。本章的格密码知识配合 4.1 软件实现，能让你走通「正确性验证—性能基准—生产集成」的完整链条。