关于 Kyber：抗量子密码算法 Kyber 详解
一、基本概念
后量子密码学（PQC）
│
├──> 是一个领域（研究如何在“量子时代”保护数据安全）
│
└──> Kyber 是这个领域中设计出来的一个“抗量子密码算法”└──> Kyber 是用于加密密钥交换的算法（叫 KEM）
>后量子密码学（Post-Quantum Cryptography, PQC）
这是一个“研究领域/学科”，目标是：设计在“未来量子计算机”也无法破解的密码算法。
因为像 RSA、ECC（椭圆曲线加密）这类传统算法，如果未来有量子计算机，会被很快破解（因为 Shor 算法可以高效分解大数）。
所以现在提前研究“后量子密码学”，防止将来量子计算一来，所有通信瞬间不安全。
>抗量子密码算法（Post-Quantum Algorithms）
是后量子密码学这个领域研究出来的“成果”之一，也叫：
-
抗量子密码算法
-
后量子密码算法
-
有时简称“PQC算法”
它是具体的算法，用来实现：
-
密钥交换
-
数字签名
-
加密传输
而这些算法的设计目标就是：在量子计算机出现后依然安全。
常见的有：
| 算法类型 | 算法名称 |
|---|---|
| 密钥交换 / 加密 | Kyber, NTRU, FrodoKEM |
| 签名算法 | Dilithium, Falcon, SPHINCS+ |
>Kyber 是什么？
Kyber 属于后量子密码算法，一种基于格（lattice）密码学的密钥封装机制（KEM），由 NIST 选为后量子密码标准，用于安全密钥交换。
你可以把它当成是“后量子密码学”这个领域里的一种技术实现，目标是：
- 在量子时代 安全地协商出对称密钥（例如 HTTPS 用的 AES 密钥）
Kyber 有以下几个等级：
| 名称 | 安全级别（对抗强度） |
|---|---|
| Kyber512 | 轻量级安全（类比 AES-128） |
| Kyber768 | 中等安全 |
| Kyber1024 | 高强度安全（类比 AES-256） |
-
不是加密消息，而是用于共享对称密钥（适合 TLS、VPN、SSH 等应用）
-
安全性基于数学难题：学习带噪声问题（LWE） 的模块变种
-
实现快速、高效、参数可扩展
二、Kyber 使用流程（API）
Kyber 的典型使用涉及三个 API：
int crypto_kem_keypair(unsigned char *pk, unsigned char *sk);
int crypto_kem_enc(unsigned char *ct, unsigned char *ss, const unsigned char *pk);
int crypto_kem_dec(unsigned char *ss, const unsigned char *ct, const unsigned char *sk);
| 步骤 | 函数 | 说明 |
|---|---|---|
| 1 | crypto_kem_keypair() | 生成公钥 + 私钥 |
| 2 | crypto_kem_enc() | 封装密钥：用公钥生成密文 ct + 对称密钥 ss |
| 3 | crypto_kem_dec() | 解封装密钥：用私钥解密 ct 得到密钥 ss |
三、数学原理
Kyber 的加密基于以下数学结构：
1）模数与多项式
-
所有计算都在有限环中进行：
$Z_q[X]/(X^n + 1)$ -
常用参数：$q = 3329$，$n = 256$，即多项式系数范围 [0, 3328]
2）模式（Module）LWE
Kyber 不是普通 LWE，而是模块化版本：Module-LWE（模块学习带噪声）
-
模块结构：A 是 $k \times k$ 多项式矩阵，s 是多项式向量
-
密文结构：一对多项式向量（u, v）
四、核心结构与流程详解
我们用 Kyber768 为例。
1）crypto_kem_keypair
步骤：
-
随机生成种子
seed -
生成公共矩阵 $A$，秘密向量 $s$ 和错误向量 $e$
-
计算公钥：$pk = A·s + e$
-
私钥保留原始 $s$，并包含 $pk$、哈希(pk)、随机值 z
对应代码：
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>#define KYBER_K 2 // 向量维度（Kyber512=2，Kyber768=3，Kyber1024=4）
#define N 256 // 多项式长度（固定为 256）
#define Q 3329 // Kyber 模数// --------- 多项式与多项式向量结构定义 ---------
typedef struct {int16_t coeffs[N]; // 多项式系数
} poly;typedef struct {poly vec[KYBER_K]; // 多项式向量
} polyvec;// --------- 简化的随机数与噪声生成 ---------
void get_noise(poly *r) {for (int i = 0; i < N; i++) {r->coeffs[i] = rand() % 10 - 5; // 简化为 [-5, 4] 区间的噪声}
}void polyvec_getnoise(polyvec *v) {for (int i = 0; i < KYBER_K; i++) {get_noise(&v->vec[i]);}
}// --------- 简化的矩阵 A 生成 ---------
void gen_matrix(polyvec A[KYBER_K], const uint8_t *seed) {srand(seed[0]); // 简化用种子第一个字节设置随机种子for (int i = 0; i < KYBER_K; i++) {for (int j = 0; j < KYBER_K; j++) {get_noise(&A[i].vec[j]); // 用噪声函数代替真实伪随机生成}}
}// --------- 多项式乘加运算：N = A * s + e ---------
void poly_muladd(polyvec *res, polyvec A[KYBER_K], polyvec *s, polyvec *e) {for (int i = 0; i < KYBER_K; i++) {for (int j = 0; j < N; j++) {res->vec[i].coeffs[j] = e->vec[i].coeffs[j];for (int k = 0; k < KYBER_K; k++) {res->vec[i].coeffs[j] += A[i].vec[k].coeffs[j] * s->vec[k].coeffs[j];res->vec[i].coeffs[j] %= Q;}}}
}// --------- 打包函数（这里只做打印模拟） ---------
void pack(polyvec *pk) {printf("Public Key:\n");for (int i = 0; i < KYBER_K; i++) {for (int j = 0; j < 8; j++) { // 只打印前8个系数printf("%d ", pk->vec[i].coeffs[j]);}printf("...\n");}
}// --------- 存储函数（这里也做打印） ---------
void store(polyvec *s, const char *name) {printf("Stored %s (first 8 coeffs):\n", name);for (int j = 0; j < 8; j++) {printf("%d ", s->vec[0].coeffs[j]);}printf("...\n");
}// --------- 主函数：执行密钥生成 ---------
int main() {polyvec s, e, pk;polyvec A[KYBER_K];uint8_t seed[32] = {42}; // 模拟种子值gen_matrix(A, seed); // 生成公共矩阵 Apolyvec_getnoise(&s); // 私钥 s 加噪声polyvec_getnoise(&e); // 误差项 e 加噪声poly_muladd(&pk, A, &s, &e); // pk = A * s + epack(&pk); // 打包公钥（这里只是打印）store(&s, "sk"); // 存储私钥（这里只是打印）return 0;
}
2）crypto_kem_enc
-
输入公钥 pk
-
生成临时随机密钥
m -
哈希 m 与 pk 得种子
-
生成 ephemerals：
sp,e1,e2 -
计算密文：
-
$u = A^T · sp + e1$
-
$v = pk^T · sp + e2 + m·(q/2)$
-
-
输出密文 + 哈希(m)
crypto_kem_enc 核心实现（对应 Kyber 规范）：
#include <stdint.h>
#include <string.h>
#include <stdio.h>
#include "params.h"
#include "poly.h"
#include "polyvec.h"
#include "indcpa.h"
#include "symmetric.h"
#include "randombytes.h"
#include "hash.h"// 输出：ct = 密文，ss = 会话密钥，输入 pk
void crypto_kem_enc(uint8_t *ct, uint8_t *ss, const uint8_t *pk) {uint8_t buf[2 * KYBER_SYMB]; // 存放 m || H(pk)uint8_t kr[2 * KYBER_SYMB]; // 存放 H(m||pk) → kr[0:32]=K, kr[32:64]=coinspolyvec sp, pkpv, e1, at[KYBER_K];poly v, e2, m;uint8_t seed[KYBER_SYMB];// 1）生成临时密钥 mrandombytes(buf, KYBER_SYMB); // 生成随机 m（长度32字节）hash_h(buf, buf, KYBER_SYMB); // m ← H(m) 做 domain separation// 2）拼接 m || H(pk)，用于生成加密种子 coinshash_h(buf + KYBER_SYMB, pk, KYBER_INDCPA_PUBLICKEYBYTES); hash_g(kr, buf, 2 * KYBER_SYMB); // kr ← H(m || H(pk))// 3）解包公钥（提取多项式向量 pkpv）unpack_pk(&pkpv, seed, pk); // pk ← 多项式 pkpv + seed// 4）生成矩阵 A^Tgen_matrix(at, seed, 1); // A^T ← transpose(A)// 5）用 kr[32:64] 生成临时私钥 sp 与误差项 e1, e2polyvec_getnoise_eta1(&sp, kr + KYBER_SYMB, 0);polyvec_getnoise_eta1(&e1, kr + KYBER_SYMB, KYBER_K);get_noise_eta2(&e2, kr + KYBER_SYMB, 2 * KYBER_K);// NTT 变换polyvec_ntt(&sp);polyvec_ntt(&pkpv);// 6）计算 u = A^T · sp + e1polyvec_pointwise_acc_montgomery(&v, &pkpv, &sp); // v = pk^T * sppolyvec_frommont(&e1);polyvec_add(&e1, &e1, &at[0]); // 实际实现是循环内完成 A^T·sp + e1polyvec_reduce(&e1); // 模 Q 归约pack_ciphertext(ct, &e1, &v); // u 部分// 7）v = pk^T·sp + e2 + m*(q/2)poly_frommsg(&m, buf); // m → 多项式 m（位乘 q/2）poly_add(&v, &v, &e2); // v += e2poly_add(&v, &v, &m); // v += m·(q/2)poly_reduce(&v);pack_ciphertext(ct, &e1, &v); // v 部分合并进 ct// 8）会话密钥 ss = H(K || H(ciphertext))hash_h(kr + KYBER_SYMB, ct, KYBER_CIPHERTEXTBYTES); // kr[32:64] = H(ct)kdf(ss, kr, 2 * KYBER_SYMB); // ss = KDF(K || H(ct))
}
3）crypto_kem_dec
-
输入密文 + sk，恢复 s
-
解密计算：
-
计算 $m' = v - u·s$
-
-
从 $m'$ 派生共享密钥 ss'
crypto_kem_dec() 的核心解密代码：
void crypto_kem_dec(uint8_t *ss, const uint8_t *ct, const uint8_t *sk) {uint8_t buf[2 * KYBER_SYMB]; // 临时缓冲区，存储 m' || H(c)uint8_t kr[2 * KYBER_SYMB]; // kr = K || H(c)polyvec sp, bp, skpv;poly v, mp;const uint8_t *pk = sk + KYBER_INDCPA_SECRETKEYBYTES; // 从 sk 中提取出 pkconst uint8_t *hpk = pk + KYBER_INDCPA_PUBLICKEYBYTES;// 1）从 sk 解包私钥 s 向量unpack_sk(&skpv, sk); // 恢复 polyvec s ← sk// 2）解包密文 ct 得到 u、vunpack_ciphertext(&bp, &v, ct); // u = bp, v = v// 3）NTT 变换polyvec_ntt(&bp);// 4）m' = v - (u ⋅ s)polyvec_pointwise_acc_montgomery(&mp, &skpv, &bp); // mp = u ⋅ spoly_invntt_tomont(&mp); // 逆NTTpoly_sub(&mp, &v, &mp); // m' = v - u·spoly_reduce(&mp); // 模Q规约poly_tomsg(buf, &mp); // 提取消息 m' → buf[0:32]// 5）拼接 m' || H(pk)memcpy(buf + KYBER_SYMB, hpk, KYBER_SYMB); // 拼接 H(pk)// 6）哈希派生 kr = H(m' || H(pk))hash_g(kr, buf, 2 * KYBER_SYMB); // kr = K || coins// 7）计算 H(ct) 加入 kr 中hash_h(kr + KYBER_SYMB, ct, KYBER_CIPHERTEXTBYTES); // kr[32:64] = H(c)// 8）派生共享密钥 ss = KDF(kr)kdf(ss, kr, 2 * KYBER_SYMB); // ss ← H(K || H(c))
}
五、源码结构分析（以 PQClean 为例）
路径
PQClean/crypto_kem/kyber768/clean/
├── api.h // 接口声明
├── kem.c // 封装主流程（keypair, enc, dec）
├── indcpa.c / .h // CPA-secure加密流程（核心）
├── poly.c / .h // 多项式运算实现
├── ntt.c // 快速傅里叶变换（NTT）
├── randombytes.c // 随机数生成
├── verify.c // 常量时间比较等
六、逆向分析建议
目标识别
| 项目 | 逆向技巧 |
|---|---|
crypto_kem_keypair | Ghidra 查找调用伪随机函数，识别 s 和 pk 生成 |
crypto_kem_enc | 重点分析 polyvec 结构、模运算、hash 种子生成 |
crypto_kem_dec | 跟踪 v - u·s 运算，是否有解密中间态泄露 |
| 随机数源 | Hook randombytes，可伪造 predictable key |
Frida 示例：Hook 密钥生成
Interceptor.attach(Module.findExportByName(null, "crypto_kem_keypair"), { // Hook 到导出函数 crypto_kem_keypair 的地址onEnter(args) { // 函数执行前触发，args 是参数数组console.log("keypair called"); // 输出日志，表示函数开始执行},onLeave(retval) { // 函数执行结束后触发，retval 是返回值console.log("keypair done"); // 输出日志，表示函数执行完毕}
});
IDA/Ghidra 静态分析：
-
搜索
CRYPTO_PUBLICKEYBYTES，定位缓冲区分配 -
查找 NTT 函数（多使用查表或优化运算）
七、实现中可能存在的风险点
| 风险类型 | 描述 |
|---|---|
| 随机数问题 | 伪随机数不安全可被预测 |
| 缓冲区未擦除 | 私钥残留在内存中 |
| 错误信息可侧信道攻击 | 不同错误路径返回不同信息量 |
| 非常量时间操作 | 对输入密文不同响应时间，导致 side-channel 攻击 |
| 缓存攻击 | 模式化访存、FFT变换泄露私钥结构 |
八、总结重点
| 点 | 解释 |
|---|---|
| 算法分类 | Kyber 是 lattice-based，加密目标是密钥，不是数据 |
| 模数操作 | 所有乘法/加法在模 q = 3329 上进行 |
| 多项式向量 | 核心运算单位是 polyvec，即多个多项式组成的向量 |
| 安全来源 | 基于 Module-LWE 难题，不怕量子算法（Shor/Grover） |
| 实战方向 | TLS握手、Frida hook、NTT逆向、种子分析、内存提取 |