關于 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逆向、種子分析、內存提取