跳转到内容

std.crypto.ml_kem

标准库Zig 0.17.0官方原文
源码std/crypto/ml_kem.zig

第 1 行

实现具备 IND-CCA2 后量子安全性的密钥封装机制(KEM): ML-KEM(NIST FIPS-203 正式标准)和 CRYSTALS-Kyber(v3.02/"draft00" CFRG 草案)。

命名空间 d00 表示当前依据 CFRG 草案实现的版本。 命名空间 nist 表示 FIPS-203 正式标准。

以下内容引自 CFRG 互联网草案:

Kyber 并非 Diffie-Hellman(DH)式的非交互密钥 协商机制,而是一种密钥封装方法(KEM)。 本质上,KEM 是一种公钥加密(PKE)方案,其中的 明文不能由调用方指定,而是在加密过程中 生成的随机密钥。借助 HPKE(RFC9180),KEM 可以转换为不受此限制的 PKE 方案。KEM 本身也可以在 TLS 中用作 密钥协商方法。

Kyber 是一种具备 IND-CCA2 安全性的 KEM。其构造方式是将 Fujisaki--Okamato 式变换应用于 InnerPKE;后者是底层 具备 IND-CPA 安全性的公钥加密方案。不能 直接使用 InnerPKE,因为其密文具有可塑性。

                    F.O. transform
    InnerPKE   ---------------------->   Kyber
    IND-CPA                              IND-CCA2

Kyber 是基于格的方案。更准确地说,其安全性 基于模格上的带误差和舍入的学习问题 (MLWER)。底层多项式环 R(定义见 第 5 节)的选择使得利用数论变换 (NTT,见第 5.1.3 节)进行乘法运算非常高效。

InnerPKE 私钥是 R 上长度为 k 的向量 _s_,它在 特定意义下是 _小的_。此处 k 是类似于 素数模数大小的安全参数。对于以 AES-128 安全级别为目标的 Kyber512,k 的值为 2。

公钥由两个值组成:

  • A_:在 R 上均匀采样的 k × k 矩阵;_以及

  • _t = A s + e_,其中 e 是适当小的掩蔽向量。

区分这样的 A s + e 与均匀采样的 t,就是 模带误差学习(MLWE)问题。若此问题困难, 则从公钥恢复私钥也同样困难, 因为恢复私钥便可以区分两者。

为节省公钥空间,A 会根据种子 rho 以确定性方式重新计算。

使用此公钥对消息 m 加密得到的密文是二元组 (c_1, c_2),其计算方式大致如下:

c_1 = Compress(A^T r + e_1, d_u) c_2 = Compress(t^T r + e_2 + Decompress(m, 1), d_v)

其中:

  • e_1、e_2 和 r 是小的随机掩蔽量;

  • Compress(-, d) 丢弃部分信息,为每个系数保留 d 位; Decompress 则满足先解压再压缩 不改变结果的性质;

  • d_u 和 d_v 是方案参数。

区分这种密文与均匀采样的 (c_1, c_2),是 完整 MLWER 问题的一个实例,参见 [KyberV302] 第 4.4 节。

解密密文时,计算:

m = Compress(Decompress(c_2, d_v) - s^T Decompress(c_1, d_u), 1).

此公式的正确性并不显然。实际上, 密文解密错误的概率可以忽略,但并不为零; 表 4 中的 DFP 列给出了该概率。可以通过 对相关概率进行严密的自动化分析来计算 此失败概率,参见 [SecEst] 中的 kyber_failure.py。

KyberV302 I-D SecEst

std.crypto.ml_kem.assert

别名

第 103 行

别名目标 std.debug.assert

std.crypto.ml_kem.bitMask

函数

第 1839 行

根据单个位值创建全一或全零掩码。 若 bit == 1,则返回全一(0xFF...FF);若 bit == 0,则返回全零。

fn bitMask(comptime T: type, bit: T) T

参数

T: type
bit: T

std.crypto.ml_kem.builtin

常量

第 100 行

std.crypto.ml_kem.cmov

函数

第 1433 行

fn cmov(comptime len: usize, dst: *[len]u8, src: [len]u8, b: u1) void

参数

len: usize
dst: *[len]u8
src: [len]u8
b: u1

std.crypto.ml_kem.common_encaps_seed_length

常量

第 210 行

usize

std.crypto.ml_kem.common_shared_key_size

常量

第 211 行

usize

std.crypto.ml_kem.computeZetas

函数

第 779 行

fn computeZetas() [128]i16

std.crypto.ml_kem.crypto

别名

第 104 行

别名目标 std.crypto

std.crypto.ml_kem.csubq

函数

第 759 行

fn csubq(x: i16) i16

参数

x: i16

std.crypto.ml_kem.ctneq

函数

第 1428 行

fn ctneq(comptime len: usize, a: [len]u8, b: [len]u8) u1

参数

len: usize
a: [len]u8
b: [len]u8

std.crypto.ml_kem.d00

命名空间

第 145 行

std.crypto.ml_kem.d00.Kyber1024

类型

第 162 行

std.crypto.ml_kem.d00.Kyber512

类型

第 146 行

std.crypto.ml_kem.d00.Kyber768

类型

第 154 行

std.crypto.ml_kem.errors

别名

第 105 行

别名目标 std.crypto.errors

std.crypto.ml_kem.eta2

常量

第 122 行

u8

std.crypto.ml_kem.extendedEuclidean

类型函数

第 1765 行

扩展欧几里得算法。 仅用于编译期值;重视正确性,不重视性能。

fn extendedEuclidean(comptime T: type, comptime a_: T, comptime b_: T) struct { gcd: T, x: T, y: T }

参数

T: type
a_: T
b_: T

std.crypto.ml_kem.feBarrettReduce

函数

第 725 行

fn feBarrettReduce(x: i16) i16

参数

x: i16

std.crypto.ml_kem.feToMont

函数

第 707 行

fn feToMont(x: i16) i16

参数

x: i16

std.crypto.ml_kem.h_length

常量

第 208 行

usize

std.crypto.ml_kem.inner_seed_length

常量

第 209 行

usize

std.crypto.ml_kem.inv_ntt_reductions

常量

第 579 行

std.crypto.ml_kem.invertMod

函数

第 647 行

fn invertMod(a: anytype, p: @TypeOf(a)) @TypeOf(a)

参数

p: @TypeOf(a)

std.crypto.ml_kem.Kyber

类型函数

第 213 行

fn Kyber(comptime p: Params) type

参数

p: Params

std.crypto.ml_kem.Kyber.ciphertext_length

常量

第 216 行

std.crypto.ml_kem.Kyber.encaps_seed_length

别名

第 225 行

确定性封装所用种子的长度(字节)。

别名目标 std.crypto.ml_kem.common_encaps_seed_length

std.crypto.ml_kem.Kyber.EncapsulatedSecret

容器

第 232 行

共享秘密及其封装(加密)表示。

字段

shared_secret: [shared_length]u8
ciphertext: [ciphertext_length]u8

std.crypto.ml_kem.Kyber.inner_plaintext_length

常量

第 423 行

usize

std.crypto.ml_kem.Kyber.innerKeyFromSeed

函数

第 517 行

fn innerKeyFromSeed(seed: [inner_seed_length]u8, pk: *InnerPk, sk: *InnerSk) void

参数

seed: [inner_seed_length]u8
pk: *InnerPk
sk: *InnerSk

std.crypto.ml_kem.Kyber.InnerPk

容器

第 425 行

字段

rho: [32]u8
th: V
aT: M

std.crypto.ml_kem.Kyber.InnerPk.encoded_length

常量

第 432 行

std.crypto.ml_kem.Kyber.InnerPk.encrypt

函数

第 434 行

fn encrypt( pk: InnerPk, pt: *const [inner_plaintext_length]u8, seed: *const [32]u8, ) [ciphertext_length]u8

参数

pk: InnerPk
pt: *const [inner_plaintext_length]u8
seed: *const [32]u8

std.crypto.ml_kem.Kyber.InnerPk.fromBytes

函数

第 469 行

fn fromBytes(buf: *const [encoded_length]u8) errors.NonCanonicalError!InnerPk

参数

buf: *const [encoded_length]u8

错误

NonCanonical

std.crypto.ml_kem.Kyber.InnerPk.toBytes

函数

第 465 行

fn toBytes(pk: InnerPk) [encoded_length]u8

参数

pk: InnerPk

std.crypto.ml_kem.Kyber.InnerSk

容器

第 489 行

字段

sh: V

std.crypto.ml_kem.Kyber.InnerSk.decrypt

函数

第 493 行

fn decrypt(sk: InnerSk, ct: *const [ciphertext_length]u8) [inner_plaintext_length]u8

参数

sk: InnerSk
ct: *const [ciphertext_length]u8

std.crypto.ml_kem.Kyber.InnerSk.encoded_length

常量

第 491 行

std.crypto.ml_kem.Kyber.InnerSk.fromBytes

函数

第 509 行

fn fromBytes(buf: *const [encoded_length]u8) InnerSk

参数

buf: *const [encoded_length]u8

std.crypto.ml_kem.Kyber.InnerSk.toBytes

函数

第 505 行

fn toBytes(sk: InnerSk) [encoded_length]u8

参数

sk: InnerSk

std.crypto.ml_kem.Kyber.KeyPair

容器

第 381 行

Kyber 密钥对。

字段

secret_key: SecretKey
public_key: PublicKey

std.crypto.ml_kem.Kyber.KeyPair.generate

函数

第 410 行

生成新的随机密钥对。

pub fn generate(io: std.Io) KeyPair

参数

io: std.Io

std.crypto.ml_kem.Kyber.KeyPair.generateDeterministic

函数

第 388 行

从密码学安全的秘密种子确定性地派生密钥对。

除测试外,应用程序通常应调用 generate(),而非此函数。

pub fn generateDeterministic(seed: [seed_length]u8) !KeyPair

参数

seed: [seed_length]u8

std.crypto.ml_kem.Kyber.M

类型

第 220 行

std.crypto.ml_kem.Kyber.name

常量

第 229 行

算法名称。

std.crypto.ml_kem.Kyber.PublicKey

容器

第 238 行

Kyber 公钥。

字段

pk: InnerPk
hpk: [h_length]u8

std.crypto.ml_kem.Kyber.PublicKey.encaps

函数

第 251 行

使用随机字节生成封装给该公钥的共享秘密。

建议使用此函数,而非 encapsDeterministic。

pub fn encaps(pk: PublicKey, io: std.Io) EncapsulatedSecret

参数

pk: PublicKey
io: std.Io

std.crypto.ml_kem.Kyber.PublicKey.encapsDeterministic

函数

第 261 行

使用所提供的种子,生成针对公钥封装的共享秘密。

建议改为调用 encaps。

pub fn encapsDeterministic(pk: PublicKey, seed: *const [encaps_seed_length]u8) EncapsulatedSecret

参数

pk: PublicKey
seed: *const [encaps_seed_length]u8

std.crypto.ml_kem.Kyber.PublicKey.encapsInner

函数

第 272 行

fn encapsInner(pk: PublicKey, m: *[inner_plaintext_length]u8) EncapsulatedSecret

参数

std.crypto.ml_kem.Kyber.PublicKey.encoded_length

别名

第 245 行

密钥序列化表示的大小,单位为字节。

别名目标 std.crypto.ml_kem.Kyber.InnerPk.encoded_length

std.crypto.ml_kem.Kyber.PublicKey.fromBytes

函数

第 307 行

从字节数组反序列化密钥。

pub fn fromBytes(buf: *const [encoded_length]u8) errors.NonCanonicalError!PublicKey

参数

buf: *const [encoded_length]u8

错误

NonCanonical

std.crypto.ml_kem.Kyber.PublicKey.toBytes

函数

第 302 行

将密钥序列化为字节数组。

pub fn toBytes(pk: PublicKey) [encoded_length]u8

参数

pk: PublicKey

std.crypto.ml_kem.Kyber.SecretKey

容器

第 316 行

Kyber 秘密密钥。

字段

sk: InnerSk
pk: InnerPk
hpk: [h_length]u8
z: [shared_length]u8

std.crypto.ml_kem.Kyber.SecretKey.decaps

函数

第 327 行

使用私钥解封装 ct 中的共享秘密。

pub fn decaps(sk: SecretKey, ct: *const [ciphertext_length]u8) ![shared_length]u8

参数

sk: SecretKey
ct: *const [ciphertext_length]u8

std.crypto.ml_kem.Kyber.SecretKey.encoded_length

常量

第 323 行

密钥序列化表示的大小,单位为字节。

usize

std.crypto.ml_kem.Kyber.SecretKey.fromBytes

函数

第 366 行

从字节数组反序列化密钥。

pub fn fromBytes(buf: *const [encoded_length]u8) errors.NonCanonicalError!SecretKey

参数

buf: *const [encoded_length]u8

错误

NonCanonical

std.crypto.ml_kem.Kyber.SecretKey.toBytes

函数

第 361 行

将密钥序列化为字节数组。

pub fn toBytes(sk: SecretKey) [encoded_length]u8

参数

sk: SecretKey

std.crypto.ml_kem.Kyber.seed_length

常量

第 227 行

密钥生成种子的长度(字节)。

usize

std.crypto.ml_kem.Kyber.Self

别名

第 218 行

别名目标 std.crypto.ml_kem.Kyber

std.crypto.ml_kem.Kyber.shared_length

别名

第 223 行

共享秘密的长度(字节)。

别名目标 std.crypto.ml_kem.common_shared_key_size

std.crypto.ml_kem.Kyber.V

类型

第 219 行

std.crypto.ml_kem.Mat

类型函数

第 1393 行

fn Mat(comptime k: u8) type

参数

k: u8

字段

rows: [k]PolyVec(k)

std.crypto.ml_kem.Mat.Self

别名

第 1395 行

别名目标 std.crypto.ml_kem.Mat

std.crypto.ml_kem.Mat.transpose

函数

第 1415 行

fn transpose(m: Self) Self

参数

m: Self

std.crypto.ml_kem.Mat.uniform

函数

第 1398 行

fn uniform(seed: [32]u8, comptime transposed: bool) Self

参数

seed: [32]u8
transposed: bool

std.crypto.ml_kem.math

别名

第 106 行

别名目标 std.math

std.crypto.ml_kem.mem

别名

第 107 行

别名目标 std.mem

std.crypto.ml_kem.modes

常量

第 200 行

std.crypto.ml_kem.modQ32

函数

第 654 行

fn modQ32(x: i32) i16

参数

x: i32

std.crypto.ml_kem.modularInverse

函数

第 1793 行

模逆:计算 a^(-1) mod p 要求 gcd(a,p) = 1。结果规范化到范围 [0, p)。

fn modularInverse(comptime T: type, comptime a: T, comptime p: T) T

参数

T: type
a: T
p: T

std.crypto.ml_kem.modularPow

函数

第 1817 行

模幂:使用平方乘算法计算 a^s mod p。

fn modularPow(comptime T: type, comptime a: T, s: T, comptime p: T) T

参数

T: type
a: T
s: T
p: T

std.crypto.ml_kem.montgomeryReduce

函数

第 1888 行

蒙哥马利约减:对于输入 x,返回满足 y ≡ x*R^(-1) (mod q) 的 y。 此通用实现由模数 q、其逆元 qInv、 蒙哥马利常量 R 及结果边界参数化。

对于 ML-DSA:R = 2^32,返回 y < 2q。 对于 ML-KEM:R = 2^16,返回范围为 (-q, q) 的 y。

fn montgomeryReduce( comptime InT: type, comptime OutT: type, comptime q: comptime_int, comptime qInv: comptime_int, comptime r_bits: comptime_int, x: InT, ) OutT

参数

InT: type
OutT: type
q: comptime_int
qInv: comptime_int
r_bits: comptime_int
x: InT

std.crypto.ml_kem.montReduce

函数

第 663 行

fn montReduce(x: i32) i16

参数

x: i32

std.crypto.ml_kem.N

常量

第 119 行

usize

std.crypto.ml_kem.nist

命名空间

第 171 行

std.crypto.ml_kem.nist.MLKem1024

类型

第 190 行

std.crypto.ml_kem.nist.MLKem512

类型

第 172 行

std.crypto.ml_kem.nist.MLKem768

类型

第 181 行

std.crypto.ml_kem.NistDRBG

容器

第 1708 行

字段

key: [32]u8
v: [16]u8

std.crypto.ml_kem.NistDRBG.fill

函数

第 1738 行

fn fill(g: *NistDRBG, out: []u8) void

参数

g: *NistDRBG
out: []u8

std.crypto.ml_kem.NistDRBG.incV

函数

第 1712 行

fn incV(g: *NistDRBG) void

参数

g: *NistDRBG

std.crypto.ml_kem.NistDRBG.init

函数

第 1756 行

fn init(seed: [48]u8) NistDRBG

参数

seed: [48]u8

std.crypto.ml_kem.NistDRBG.update

函数

第 1718 行

fn update(g: *NistDRBG, pd: ?[48]u8) void

参数

g: *NistDRBG
pd: ?[48]u8

std.crypto.ml_kem.Params

容器

第 124 行

字段

name: []const u8
ml_kem: bool = false
k: u8
eta1: u8
du: u8
dv: u8

std.crypto.ml_kem.Poly

容器

第 796 行

字段

cs: [N]i16

std.crypto.ml_kem.Poly.add

函数

第 803 行

fn add(a: Poly, b: Poly) Poly

参数

a: Poly
b: Poly

std.crypto.ml_kem.Poly.barrettReduce

函数

第 986 行

fn barrettReduce(a: Poly) Poly

参数

a: Poly

std.crypto.ml_kem.Poly.compress

函数

第 1001 行

fn compress(p: Poly, comptime d: u8) [compressedSize(d)]u8

参数

p: Poly
d: u8

std.crypto.ml_kem.Poly.compressedSize

函数

第 994 行

fn compressedSize(comptime d: u8) usize

参数

d: u8

std.crypto.ml_kem.Poly.decompress

函数

第 1064 行

fn decompress(comptime d: u8, in: *const [compressedSize(d)]u8) Poly

参数

d: u8
in: *const [compressedSize(d)]u8

std.crypto.ml_kem.Poly.encoded_length

常量

第 799 行

std.crypto.ml_kem.Poly.fromBytes

函数

第 1259 行

fn fromBytes(buf: *const [encoded_length]u8) Poly

参数

buf: *const [encoded_length]u8

std.crypto.ml_kem.Poly.invNTT

函数

第 909 行

fn invNTT(a: Poly) Poly

参数

a: Poly

std.crypto.ml_kem.Poly.mulHat

函数

第 1121 行

fn mulHat(a: Poly, b: Poly) Poly

参数

a: Poly
b: Poly

std.crypto.ml_kem.Poly.noise

函数

第 1164 行

fn noise(comptime eta: u8, nonce: u8, seed: *const [32]u8) Poly

参数

eta: u8
nonce: u8
seed: *const [32]u8

std.crypto.ml_kem.Poly.normalize

函数

第 966 行

fn normalize(a: Poly) Poly

参数

a: Poly

std.crypto.ml_kem.Poly.ntt

函数

第 826 行

fn ntt(a: Poly) Poly

参数

a: Poly

std.crypto.ml_kem.Poly.sub

函数

第 812 行

fn sub(a: Poly, b: Poly) Poly

参数

a: Poly
b: Poly

std.crypto.ml_kem.Poly.toBytes

函数

第 1244 行

fn toBytes(p: Poly) [encoded_length]u8

参数

p: Poly

std.crypto.ml_kem.Poly.toMont

函数

第 975 行

fn toMont(a: Poly) Poly

参数

a: Poly

std.crypto.ml_kem.Poly.uniform

函数

第 1229 行

fn uniform(seed: [32]u8, x: u8, y: u8) Poly

参数

seed: [32]u8
x: u8
y: u8

std.crypto.ml_kem.Poly.zero

常量

第 800 行

Poly

std.crypto.ml_kem.PolyVec

类型函数

第 1273 行

fn PolyVec(comptime k: u8) type

参数

k: u8

字段

ps: [k]Poly

std.crypto.ml_kem.PolyVec.add

函数

第 1318 行

fn add(a: Self, b: Self) Self

参数

a: Self
b: Self

std.crypto.ml_kem.PolyVec.barrettReduce

函数

第 1314 行

fn barrettReduce(v: Self) Self

参数

v: Self

std.crypto.ml_kem.PolyVec.compress

函数

第 1352 行

fn compress(v: Self, comptime d: u8) [compressedSize(d)]u8

参数

v: Self
d: u8

std.crypto.ml_kem.PolyVec.compressedSize

函数

第 1280 行

fn compressedSize(comptime d: u8) usize

参数

d: u8

std.crypto.ml_kem.PolyVec.decompress

函数

第 1361 行

fn decompress(comptime d: u8, buf: *const [compressedSize(d)]u8) Self

参数

d: u8
buf: *const [compressedSize(d)]u8

std.crypto.ml_kem.PolyVec.dotHat

函数

第 1344 行

fn dotHat(a: Self, b: Self) Poly

参数

a: Self
b: Self

std.crypto.ml_kem.PolyVec.encoded_length

常量

第 1278 行

std.crypto.ml_kem.PolyVec.fromBytes

函数

第 1380 行

从字节数组反序列化密钥。

fn fromBytes(buf: *const [encoded_length]u8) Self

参数

buf: *const [encoded_length]u8

std.crypto.ml_kem.PolyVec.invNTT

函数

第 1306 行

fn invNTT(v: Self) Self

参数

v: Self

std.crypto.ml_kem.PolyVec.map

函数

第 1285 行

对每个多项式应用一元运算

fn map(v: Self, comptime op: fn (Poly) Poly) Self

参数

v: Self
op: fn (Poly) Poly

std.crypto.ml_kem.PolyVec.mapBinary

函数

第 1294 行

逐对应用二元运算

fn mapBinary(a: Self, b: Self, comptime op: fn (Poly, Poly) Poly) Self

参数

a: Self
b: Self
op: fn (Poly, Poly) Poly

std.crypto.ml_kem.PolyVec.noise

函数

第 1328 行

fn noise(comptime eta: u8, nonce: u8, seed: *const [32]u8) Self

参数

eta: u8
nonce: u8
seed: *const [32]u8

std.crypto.ml_kem.PolyVec.normalize

函数

第 1310 行

fn normalize(v: Self) Self

参数

v: Self

std.crypto.ml_kem.PolyVec.ntt

函数

第 1302 行

fn ntt(v: Self) Self

参数

v: Self

std.crypto.ml_kem.PolyVec.Self

别名

第 1277 行

别名目标 std.crypto.ml_kem.PolyVec

std.crypto.ml_kem.PolyVec.sub

函数

第 1322 行

fn sub(a: Self, b: Self) Self

参数

a: Self
b: Self

std.crypto.ml_kem.PolyVec.toBytes

函数

第 1371 行

将密钥序列化为字节数组。

fn toBytes(v: Self) [encoded_length]u8

参数

v: Self

std.crypto.ml_kem.Q

常量

第 113 行

i16

std.crypto.ml_kem.R

常量

第 116 行

i32

std.crypto.ml_kem.r_mod_q

常量

第 552 行

i32

std.crypto.ml_kem.r2_mod_q

常量

第 555 行

i32

std.crypto.ml_kem.r2_over_128

常量

第 561 行

i32

std.crypto.ml_kem.randPolyAbsLeqQ

函数

第 1441 行

fn randPolyAbsLeqQ(rnd: anytype) Poly

std.crypto.ml_kem.randPolyNormalized

函数

第 1450 行

fn randPolyNormalized(rnd: anytype) Poly

std.crypto.ml_kem.RndGen

别名

第 110 行

别名目标 std.Random.DefaultPrng

std.crypto.ml_kem.sampleUniformRejection

函数

第 1915 行

使用 SHAKE-128 和拒绝采样进行均匀采样。 通过拒绝采样,从 [0, q) 中均匀采样多项式系数。

参数:

  • PolyType:要返回的多项式类型
  • q:模数
  • bits_per_coef:每个系数的位数,12 或 23
  • n:系数数量
  • seed:随机种子
  • domain_sep:域分离字节,追加到种子之后
fn sampleUniformRejection( comptime PolyType: type, comptime q: comptime_int, comptime bits_per_coef: comptime_int, comptime n: comptime_int, seed: []const u8, domain_sep: []const u8, ) PolyType

参数

PolyType: type
q: comptime_int
bits_per_coef: comptime_int
n: comptime_int
seed: []const u8
domain_sep: []const u8

std.crypto.ml_kem.sha3

别名

第 108 行

别名目标 std.crypto.hash.sha3

std.crypto.ml_kem.signMask

函数

第 1849 行

由有符号整数的符号位创建掩码。 x < 0 时返回全 1(0xFF...FF),x >= 0 时返回全 0。

fn signMask(comptime T: type, x: T) @Int(.unsigned, @typeInfo(T).int.bits)

参数

T: type
x: T

std.crypto.ml_kem.std

别名

第 99 行

别名目标 std

std.crypto.ml_kem.testing

别名

第 102 行

别名目标 std.testing

std.crypto.ml_kem.testNistKat

函数

第 1669 行

fn testNistKat(mode: type, hash: []const u8) !void

参数

mode: type
hash: []const u8

std.crypto.ml_kem.zeta

常量

第 558 行

i16

std.crypto.ml_kem.zetas

常量

第 569 行

源码

std/crypto/ml_kem.zig

//! 实现具备 IND-CCA2 后量子安全性的密钥封装机制(KEM):
//! ML-KEM(NIST FIPS-203 正式标准)和 CRYSTALS-Kyber(v3.02/"draft00" CFRG 草案)。
//!
//! 命名空间 `d00` 表示当前依据 CFRG 草案实现的版本。
//! 命名空间 `nist` 表示 FIPS-203 正式标准。
//!
//! 以下内容引自 CFRG 互联网草案:
//!
//! Kyber 并非 Diffie-Hellman(DH)式的非交互密钥
//! 协商机制,而是一种密钥封装方法(KEM)。
//! 本质上,KEM 是一种公钥加密(PKE)方案,其中的
//! 明文不能由调用方指定,而是在加密过程中
//! 生成的随机密钥。借助 HPKE(RFC9180),KEM 可以转换为不受此限制的
//! PKE 方案。KEM 本身也可以在 TLS 中用作
//! 密钥协商方法。
//!
//! Kyber 是一种具备 IND-CCA2 安全性的 KEM。其构造方式是将
//! Fujisaki--Okamato 式变换应用于 InnerPKE;后者是底层
//! 具备 IND-CPA 安全性的公钥加密方案。不能
//! 直接使用 InnerPKE,因为其密文具有可塑性。
//!
//! ```
//!                     F.O. transform
//!     InnerPKE   ---------------------->   Kyber
//!     IND-CPA                              IND-CCA2
//! ```
//!
//! Kyber 是基于格的方案。更准确地说,其安全性
//! 基于模格上的带误差和舍入的学习问题
//! (MLWER)。底层多项式环 R(定义见
//! 第 5 节)的选择使得利用数论变换
//! (NTT,见第 5.1.3 节)进行乘法运算非常高效。
//!
//! InnerPKE 私钥是 R 上长度为 k 的向量 _s_,它在
//! 特定意义下是 _小的_。此处 k 是类似于
//! 素数模数大小的安全参数。对于以 AES-128 安全级别为目标的
//! Kyber512,k 的值为 2。
//!
//! 公钥由两个值组成:
//!
//! * _A_:在 R 上均匀采样的 k × k 矩阵;_以及_
//!
//! * _t = A s + e_,其中 e 是适当小的掩蔽向量。
//!
//! 区分这样的 A s + e 与均匀采样的 t,就是
//! 模带误差学习(MLWE)问题。若此问题困难,
//! 则从公钥恢复私钥也同样困难,
//! 因为恢复私钥便可以区分两者。
//!
//! 为节省公钥空间,A 会根据种子 _rho_
//! 以确定性方式重新计算。
//!
//! 使用此公钥对消息 m 加密得到的密文是二元组 (c_1,
//! c_2),其计算方式大致如下:
//!
//! c_1 = Compress(A^T r + e_1, d_u)
//! c_2 = Compress(t^T r + e_2 + Decompress(m, 1), d_v)
//!
//! 其中:
//!
//! * e_1、e_2 和 r 是小的随机掩蔽量;
//!
//! * Compress(-, d) 丢弃部分信息,为每个系数保留 d 位;
//!   Decompress 则满足先解压再压缩
//!   不改变结果的性质;
//!
//! * d_u 和 d_v 是方案参数。
//!
//! 区分这种密文与均匀采样的 (c_1, c_2),是
//! 完整 MLWER 问题的一个实例,参见 [KyberV302] 第 4.4 节。
//!
//! 解密密文时,计算:
//!
//! m = Compress(Decompress(c_2, d_v) - s^T Decompress(c_1, d_u), 1).
//!
//! 此公式的正确性并不显然。实际上,
//! 密文解密错误的概率可以忽略,但并不为零;
//! 表 4 中的 DFP 列给出了该概率。可以通过
//! 对相关概率进行严密的自动化分析来计算
//! 此失败概率,参见 [SecEst] 中的 kyber_failure.py。
//!
//! [KyberV302](https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf)
//! [I-D](https://github.com/bwesterb/draft-schwabe-cfrg-kyber)
//! [SecEst](https://github.com/pq-crystals/security-estimates)

// TODO
//
// - Kyber 的瓶颈是各种 hash/XOF 调用:
//    - 优化 Zig 的 keccak 实现。
//    - 使用 SIMD 并行计算 keccak。
// - 能否使用编译期类型跟踪系数范围,
//   同时避免重复代码?
// - 让测试更接近被测内容会更整洁。
// - 生成密钥对时,公钥和私钥中都复制了
//   内部公钥及其很大的矩阵 A。在 Go 中,
//   可以只在私钥中保存指向公钥的指针,
//   但如何在 Zig 中优雅地实现?

const std = @import("std");
const builtin = @import("builtin");

const testing = std.testing;
const assert = std.debug.assert;
const crypto = std.crypto;
const errors = std.crypto.errors;
const math = std.math;
const mem = std.mem;
const sha3 = crypto.hash.sha3;

const RndGen = std.Random.DefaultPrng;

// Q 为模数 q ≡ 3329 = 2¹¹ + 2¹⁰ + 2⁸ + 1
const Q: i16 = 3329;

// Montgomery R = 2^16 mod Q(用于 Montgomery 乘法)。
const R: i32 = 1 << 16;

// N 是多项式的次数(多项式环维度)
const N: usize = 256;

// eta2 是加密盲化所用"小"向量的大小
const eta2: u8 = 2;

const Params = struct {
    name: []const u8,

    // 使用 NIST ML-KEM 变体,而非最初提交的 Kyber。
    ml_kem: bool = false,

    // 矩阵 A 的宽度和高度。
    k: u8,

    // 私钥和加密盲化中使用的“小”向量大小。
    eta1: u8,

    // 密文中与私钥无关的部分 u
    // 要保留的位数。
    du: u8,

    // 密文中依赖私钥的部分 v
    // 需要保留的位数。
    dv: u8,
};

pub const d00 = struct {
    pub const Kyber512 = Kyber(.{
        .name = "Kyber512",
        .k = 2,
        .eta1 = 3,
        .du = 10,
        .dv = 4,
    });

    pub const Kyber768 = Kyber(.{
        .name = "Kyber768",
        .k = 3,
        .eta1 = 2,
        .du = 10,
        .dv = 4,
    });

    pub const Kyber1024 = Kyber(.{
        .name = "Kyber1024",
        .k = 4,
        .eta1 = 2,
        .du = 11,
        .dv = 5,
    });
};

pub const nist = struct {
    pub const MLKem512 = Kyber(.{
        .name = "ML-KEM-512",
        .ml_kem = true,
        .k = 2,
        .eta1 = 3,
        .du = 10,
        .dv = 4,
    });

    pub const MLKem768 = Kyber(.{
        .name = "ML-KEM-768",
        .ml_kem = true,
        .k = 3,
        .eta1 = 2,
        .du = 10,
        .dv = 4,
    });

    pub const MLKem1024 = Kyber(.{
        .name = "ML-KEM-1024",
        .ml_kem = true,
        .k = 4,
        .eta1 = 2,
        .du = 11,
        .dv = 5,
    });
};

const modes = [_]type{
    d00.Kyber512,
    d00.Kyber768,
    d00.Kyber1024,
    nist.MLKem512,
    nist.MLKem768,
    nist.MLKem1024,
};
const h_length: usize = 32;
const inner_seed_length: usize = 32;
const common_encaps_seed_length: usize = 32;
const common_shared_key_size: usize = 32;

fn Kyber(comptime p: Params) type {
    return struct {
        // 密文大小,单位为字节。
        pub const ciphertext_length = Poly.compressedSize(p.du) * p.k + Poly.compressedSize(p.dv);

        const Self = @This();
        const V = PolyVec(p.k);
        const M = Mat(p.k);

        /// 共享秘密的长度(字节)。
        pub const shared_length = common_shared_key_size;
        /// 确定性封装所用种子的长度(字节)。
        pub const encaps_seed_length = common_encaps_seed_length;
        /// 密钥生成种子的长度(字节)。
        pub const seed_length: usize = inner_seed_length + shared_length;
        /// 算法名称。
        pub const name = p.name;

        /// 共享秘密及其封装(加密)表示。
        pub const EncapsulatedSecret = struct {
            shared_secret: [shared_length]u8,
            ciphertext: [ciphertext_length]u8,
        };

        /// Kyber 公钥。
        pub const PublicKey = struct {
            pk: InnerPk,

            // 已缓存
            hpk: [h_length]u8, // H(pk)

            /// 密钥序列化表示的大小,单位为字节。
            pub const encoded_length = InnerPk.encoded_length;

            /// 使用随机字节生成封装给该公钥的共享秘密。
            ///
            /// 建议使用此函数,而非 `encapsDeterministic`。
            ///
            pub fn encaps(pk: PublicKey, io: std.Io) EncapsulatedSecret {
                var m: [inner_plaintext_length]u8 = undefined;
                io.random(&m);
                return encapsInner(pk, &m);
            }

            /// 使用所提供的种子,生成针对公钥封装的共享秘密。
            ///
            /// 建议改为调用 `encaps`。
            ///
            pub fn encapsDeterministic(pk: PublicKey, seed: *const [encaps_seed_length]u8) EncapsulatedSecret {
                var m: [inner_plaintext_length]u8 = undefined;
                if (p.ml_kem) {
                    @memcpy(&m, seed);
                } else {
                    // m = H(seed)
                    sha3.Sha3_256.hash(seed, &m, .{});
                }
                return encapsInner(pk, &m);
            }

            fn encapsInner(pk: PublicKey, m: *[inner_plaintext_length]u8) EncapsulatedSecret {
                // (K', r) = G(m ‖ H(pk))
                var kr: [inner_plaintext_length + h_length]u8 = undefined;
                var g = sha3.Sha3_512.init(.{});
                g.update(m);
                g.update(&pk.hpk);
                g.final(&kr);

                // c = innerEncrypt(pk, m, r)
                const ct = pk.pk.encrypt(m, kr[32..64]);

                if (p.ml_kem) {
                    return EncapsulatedSecret{
                        .shared_secret = kr[0..shared_length].*, // ML-KEM: K = K'
                        .ciphertext = ct,
                    };
                } else {
                    // 计算 H(c) 并放入 kr 的第二个槽位,使其成为 (K', H(c))。
                    sha3.Sha3_256.hash(&ct, kr[32..], .{});

                    var ss: [shared_length]u8 = undefined;
                    sha3.Shake256.hash(&kr, &ss, .{});
                    return EncapsulatedSecret{
                        .shared_secret = ss, // Kyber: K = KDF(K' ‖ H(c))
                        .ciphertext = ct,
                    };
                }
            }

            /// 将密钥序列化为字节数组。
            pub fn toBytes(pk: PublicKey) [encoded_length]u8 {
                return pk.pk.toBytes();
            }

            /// 从字节数组反序列化密钥。
            pub fn fromBytes(buf: *const [encoded_length]u8) errors.NonCanonicalError!PublicKey {
                var ret: PublicKey = undefined;
                ret.pk = try InnerPk.fromBytes(buf[0..InnerPk.encoded_length]);
                sha3.Sha3_256.hash(buf, &ret.hpk, .{});
                return ret;
            }
        };

        /// Kyber 秘密密钥。
        pub const SecretKey = struct {
            sk: InnerSk,
            pk: InnerPk,
            hpk: [h_length]u8, // H(pk)
            z: [shared_length]u8,

            /// 密钥序列化表示的大小,单位为字节。
            pub const encoded_length: usize =
                InnerSk.encoded_length + InnerPk.encoded_length + h_length + shared_length;

            /// 使用私钥解封装 ct 中的共享秘密。
            pub fn decaps(sk: SecretKey, ct: *const [ciphertext_length]u8) ![shared_length]u8 {
                // m' = innerDec(ct)
                const m2 = sk.sk.decrypt(ct);

                // (K'', r') = G(m' ‖ H(pk))
                var kr2: [64]u8 = undefined;
                var g = sha3.Sha3_512.init(.{});
                g.update(&m2);
                g.update(&sk.hpk);
                g.final(&kr2);

                // ct' = innerEnc(pk, m', r')
                const ct2 = sk.pk.encrypt(&m2, kr2[32..64]);

                if (p.ml_kem) {
                    // ML-KEM:依据 FIPS 203,ct == ct' 时 K = K'',否则 K = J(z || c)。
                    var k_bar: [shared_length]u8 = undefined;
                    var j = sha3.Shake256.init(.{});
                    j.update(&sk.z);
                    j.update(ct);
                    j.squeeze(&k_bar);
                    cmov(shared_length, kr2[0..shared_length], k_bar, ctneq(ciphertext_length, ct.*, ct2));
                    return kr2[0..shared_length].*;
                } else {
                    // Kyber: K = KDF(K''/z ‖ H(c))
                    sha3.Sha3_256.hash(ct, kr2[32..], .{});
                    cmov(32, kr2[0..32], sk.z, ctneq(ciphertext_length, ct.*, ct2));
                    var ss: [shared_length]u8 = undefined;
                    sha3.Shake256.hash(&kr2, &ss, .{});
                    return ss;
                }
            }

            /// 将密钥序列化为字节数组。
            pub fn toBytes(sk: SecretKey) [encoded_length]u8 {
                return sk.sk.toBytes() ++ sk.pk.toBytes() ++ sk.hpk ++ sk.z;
            }

            /// 从字节数组反序列化密钥。
            pub fn fromBytes(buf: *const [encoded_length]u8) errors.NonCanonicalError!SecretKey {
                var ret: SecretKey = undefined;
                comptime var s: usize = 0;
                ret.sk = InnerSk.fromBytes(buf[s .. s + InnerSk.encoded_length]);
                s += InnerSk.encoded_length;
                ret.pk = try InnerPk.fromBytes(buf[s .. s + InnerPk.encoded_length]);
                s += InnerPk.encoded_length;
                ret.hpk = buf[s..][0..h_length].*;
                s += h_length;
                ret.z = buf[s..][0..shared_length].*;
                return ret;
            }
        };

        /// Kyber 密钥对。
        pub const KeyPair = struct {
            secret_key: SecretKey,
            public_key: PublicKey,

            /// 从密码学安全的秘密种子确定性地派生密钥对。
            ///
            /// 除测试外,应用程序通常应调用 `generate()`,而非此函数。
            pub fn generateDeterministic(seed: [seed_length]u8) !KeyPair {
                var ret: KeyPair = undefined;

                // 生成内部密钥
                innerKeyFromSeed(
                    seed[0..inner_seed_length].*,
                    &ret.public_key.pk,
                    &ret.secret_key.sk,
                );
                ret.secret_key.pk = ret.public_key.pk;

                // 从种子复制 z。
                ret.secret_key.z = seed[inner_seed_length..seed_length].*;

                // 计算 H(pk)
                sha3.Sha3_256.hash(&ret.public_key.pk.toBytes(), &ret.secret_key.hpk, .{});
                ret.public_key.hpk = ret.secret_key.hpk;

                return ret;
            }

            /// 生成新的随机密钥对。
            pub fn generate(io: std.Io) KeyPair {
                var random_seed: [seed_length]u8 = undefined;
                while (true) {
                    io.random(&random_seed);
                    return generateDeterministic(random_seed) catch {
                        @branchHint(.unlikely);
                        continue;
                    };
                }
            }
        };

        // 输入明文的大小
        const inner_plaintext_length: usize = Poly.compressedSize(1);

        const InnerPk = struct {
            rho: [32]u8, // ρ,矩阵 A 的种子
            th: V, // NTT(t),已规范化

            // 缓存值
            aT: M,

            const encoded_length = V.encoded_length + 32;

            fn encrypt(
                pk: InnerPk,
                pt: *const [inner_plaintext_length]u8,
                seed: *const [32]u8,
            ) [ciphertext_length]u8 {
                // 适当地采样 r、e₁ 和 e₂
                const rh = V.noise(p.eta1, 0, seed).ntt().barrettReduce();
                const e1 = V.noise(eta2, p.k, seed);
                const e2 = Poly.noise(eta2, 2 * p.k, seed);

                // 接下来计算 u = Aᵀ r + e₁。先计算 Aᵀ。
                var u: V = undefined;
                for (0..p.k) |i| {
                    // 注意,r 的系数以 q 为界,Aᵀ 的系数以 4.5q 为界,因此二者乘积以 2¹⁵q 为界,满足乘法所需条件。
                    //
                    //
                    u.ps[i] = pk.aT.rows[i].dotHat(rh);
                }

                // Aᵀ 和 r 不采用 Montgomery 表示,因此内积中的
                // Montgomery 乘法引入了一个 R⁻¹ 因子,
                // InvNTT 会消去该因子。
                u = u.barrettReduce().invNTT().add(e1).normalize();

                // 接着计算 v = <t, r> + e₂ + Decompress_q(m, 1)
                const v = pk.th.dotHat(rh).barrettReduce().invNTT()
                    .add(Poly.decompress(1, pt)).add(e2).normalize();

                return u.compress(p.du) ++ v.compress(p.dv);
            }

            fn toBytes(pk: InnerPk) [encoded_length]u8 {
                return pk.th.toBytes() ++ pk.rho;
            }

            fn fromBytes(buf: *const [encoded_length]u8) errors.NonCanonicalError!InnerPk {
                var ret: InnerPk = undefined;

                const th_bytes = buf[0..V.encoded_length];
                ret.th = V.fromBytes(th_bytes).normalize();

                if (p.ml_kem) {
                    // 验证系数采用规范表示。
                    if (!mem.eql(u8, &ret.th.toBytes(), th_bytes)) {
                        return error.NonCanonical;
                    }
                }

                ret.rho = buf[V.encoded_length..encoded_length].*;
                ret.aT = M.uniform(ret.rho, true);
                return ret;
            }
        };

        // 内部 PKE 的私钥
        const InnerSk = struct {
            sh: V, // NTT(s),已正规化
            const encoded_length = V.encoded_length;

            fn decrypt(sk: InnerSk, ct: *const [ciphertext_length]u8) [inner_plaintext_length]u8 {
                const u = V.decompress(p.du, ct[0..comptime V.compressedSize(p.du)]);
                const v = Poly.decompress(
                    p.dv,
                    ct[comptime V.compressedSize(p.du)..ciphertext_length],
                );

                // 计算 m = v - <s, u>
                return v.sub(sk.sh.dotHat(u.ntt()).barrettReduce().invNTT())
                    .normalize().compress(1);
            }

            fn toBytes(sk: InnerSk) [encoded_length]u8 {
                return sk.sh.toBytes();
            }

            fn fromBytes(buf: *const [encoded_length]u8) InnerSk {
                var ret: InnerSk = undefined;
                ret.sh = V.fromBytes(buf).normalize();
                return ret;
            }
        };

        // 从给定种子派生内部 PKE 密钥对。
        fn innerKeyFromSeed(seed: [inner_seed_length]u8, pk: *InnerPk, sk: *InnerSk) void {
            var expanded_seed: [64]u8 = undefined;
            var h = sha3.Sha3_512.init(.{});
            h.update(&seed);
            if (p.ml_kem) h.update(&[1]u8{p.k});
            h.final(&expanded_seed);
            pk.rho = expanded_seed[0..32].*;
            const sigma = expanded_seed[32..64];
            pk.aT = M.uniform(pk.rho, false); // 将 ρ 扩展为 A,稍后再进行转置

            // 采样秘密向量 s。
            sk.sh = V.noise(p.eta1, 0, sigma).ntt().normalize();

            const eh = PolyVec(p.k).noise(p.eta1, p.k, sigma).ntt(); // 采样盲化值 e。
            var th: V = undefined;

            // 接下来计算 t = A s + e。
            for (0..p.k) |i| {
                // 注意,s 的系数以 q 为界,A 的系数以 4.5q 为界,因此乘积以 2¹⁵q 为界,满足乘法要求。
                // A 和 s 原先不是 Montgomery 形式,因此内积中的 Montgomery 乘法引入了 R⁻¹ 因子,随后通过 toMont() 抵消。这也保证 th 的系数绝对值以 q 为界。
                //
                //
                //
                //
                //
                th.ps[i] = pk.aT.rows[i].dotHat(sk.sh).toMont();
            }

            pk.th = th.add(eh).normalize(); // 以 8q 为界
            pk.aT = pk.aT.transpose();
        }
    };
}

// R mod q
const r_mod_q: i32 = @rem(@as(i32, R), Q);

// R² mod q
const r2_mod_q: i32 = @rem(r_mod_q * r_mod_q, Q);

// ζ 是 NTT 使用的 256 次本原单位根。
const zeta: i16 = 17;

// (128)⁻¹ R²。用于逆 NTT。
const r2_over_128: i32 = @mod(invertMod(128, Q) * r2_mod_q, Q);

// zetas 列出 NTT 所用的、本原单位根的幂的
// 蒙哥马利表示预计算值:
//
//  zetas[i] = ζᵇʳᵛ⁽ⁱ⁾ R mod q
//
// 其中 ζ = 17,brv(i) 是 7 位数的位反转,R=2¹⁶ mod q。
const zetas = computeZetas();

// invNTTReductions 跟踪在 Poly.invNTT() 中应对哪些系数执行 Barrett 约减。
//
// 采用惰性生成:每计算一次蝶形运算,若即将使 i16 溢出,则约减最大的系数。若仍不足以避免溢出,也约减另一个系数。
//
// 这一方式实际上是最优的,证明见 https://eprint.iacr.org/2020/1377.pdf
//
//
//
const inv_ntt_reductions = [_]i16{
    -1, // 第 1 层之后
    -1, // 第 2 层之后
    16,
    17,
    48,
    49,
    80,
    81,
    112,
    113,
    144,
    145,
    176,
    177,
    208,
    209,
    240, 241, -1, // 第 3 层之后
    0,   1,   32,
    33,  34,  35,
    64,  65,  96,
    97,  98,  99,
    128, 129,
    160, 161, 162, 163, 192, 193, 224, 225, 226, 227, -1, // 第 4 层之后
    2,   3,   66,  67,  68,  69,  70,  71,  130, 131, 194,
    195, 196, 197,
    198, 199, -1, // 第 5 层之后
    4,   5,   6,
    7,   132, 133,
    134, 135, 136,
    137, 138, 139,
    140, 141,
    142, 143, -1, // 第 6 层之后
    -1, // 第 7 层之后
};

test "invNTTReductions bounds" {
    // 检查 invNTTReductions 建议的约减
    // 是否不会在 invNTT() 中溢出。
    var xs: [256]i32 = @splat(1); // 从 |x| ≤ q 开始

    var r: usize = 0;
    var layer: math.Log2Int(usize) = 1;
    while (layer < 8) : (layer += 1) {
        const w = @as(usize, 1) << layer;
        var i: usize = 0;

        while (i + w < 256) {
            xs[i] = xs[i] + xs[i + w];
            try testing.expect(xs[i] <= 9); // 不能超过 9q
            xs[i + w] = 1;
            i += 1;
            if (@mod(i, w) == 0) {
                i += w;
            }
        }

        while (true) {
            const j = inv_ntt_reductions[r];
            r += 1;
            if (j < 0) {
                break;
            }
            xs[@as(usize, @intCast(j))] = 1;
        }
    }
}

fn invertMod(a: anytype, p: @TypeOf(a)) @TypeOf(a) {
    const r = extendedEuclidean(@TypeOf(a), a, p);
    assert(r.gcd == 1);
    return r.x;
}

// 对 q 取模以便测试。
fn modQ32(x: i32) i16 {
    var y = @as(i16, @intCast(@rem(x, @as(i32, Q))));
    if (y < 0) {
        y += Q;
    }
    return y;
}

// 给定 -2¹⁵ q ≤ x < 2¹⁵ q,返回满足 -q < y < q 且 x 2⁻¹⁶ = y (mod q) 的 y。
fn montReduce(x: i32) i16 {
    const qInv = comptime invertMod(@as(i32, Q), R);
    // 这是 R=2¹⁶ 的 Montgomery 约减。
    //
    // 由于 q 为素数,有 gcd(2¹⁶, q) = 1。记 q' := 62209 = q⁻¹ mod R。
    // 首先计算:
    //
    // m := ((x mod R) q') mod R
    //         = x q' mod R
    //    = int16(x q')
    //    = int16(int32(x) * int32(q'))
    //
    // 注意,x q' 可能达到 2³²,因此最后一行的 int32
    // 乘法可能溢出。但对任意 int32 值 a 和 b,
    // 均有 int32(int64(a)*int64(b)) = int32(a*b),因此结果正确。
    const m: i16 = @truncate(@as(i32, @truncate(x *% qInv)));

    // 注意,x - m q 能被 R 整除;事实上,在模 R 意义下:
    //
    //  x - m q ≡ x - x q' q ≡ x - x q⁻¹ q ≡ x - x = 0.
    //
    // 返回 y := (x - m q) / R。此 y 确实正确,因为在模 q 意义下:
    //
    //  y ≡ x R⁻¹ - m q R⁻¹ = x R⁻¹
    //
    // 且由于 2¹⁵ q ≤ m q, x < 2¹⁵ q,可得
    // 2¹⁶ q ≤ x - m q < 2¹⁶,因此 q ≤ (x - m q) / R < q,正如所需。
    //
    const yR = x - @as(i32, m) * @as(i32, Q);
    return @bitCast(@as(u16, @truncate(@as(u32, @bitCast(yR)) >> 16)));
}

test "Test montReduce" {
    var rnd = RndGen.init(0);
    for (0..1000) |_| {
        const bound = comptime @as(i32, Q) * (1 << 15);
        const x = rnd.random().intRangeLessThan(i32, -bound, bound);
        const y = montReduce(x);
        try testing.expect(-Q < y and y < Q);
        try testing.expectEqual(modQ32(x), modQ32(@as(i32, y) * R));
    }
}

// 给定任意 x,返回 x R mod q,其中 R=2¹⁶。
fn feToMont(x: i16) i16 {
    // 注意 |1353 x| ≤ 1353 2¹⁵ ≤ 13318 q ≤ 2¹⁵ q,
    // 因此处于 montReduce 的范围内。
    return montReduce(@as(i32, x) * r2_mod_q);
}

test "Test feToMont" {
    var x: i32 = -(1 << 15);
    while (x < 1 << 15) : (x += 1) {
        const y = feToMont(@as(i16, @intCast(x)));
        try testing.expectEqual(modQ32(@as(i32, y)), modQ32(x * r_mod_q));
    }
}

// 给定任意 x,计算满足 x = y (mod q) 的 0 ≤ y ≤ q。
//
// 注意:对某些 x,可能有 feBarrettReduce(x) = q ≠ 0。事实上,
// 当且仅当存在正整数 n 使 x = -nq 时,会出现此情况。
fn feBarrettReduce(x: i16) i16 {
    // 这是标准 Barrett 约减。
    //
    // 对任意 x,有 x mod q = x - ⌊x/q⌋ q。使用 20159/2²⁶
    // 近似 1/q。注意 0 ≤ 20159/2²⁶ - 1/q ≤ 0.135/2²⁶,
    // 因此当 |x| ≤ 2¹⁶ 时,| x 20156/2²⁶ - x/q | ≤ 2⁻¹⁰。对于所有
    // 不是 q 倍数的 x,x/q 与任意整数的距离都大于 1/q,
    // 因此 ⌊x 20156/2²⁶⌋ = ⌊x/q⌋。若 x 是 q 的正倍数,
    // 则 x 20156/2²⁶ 大于 x/q,因此同样有 ⌊x 20156/2²⁶⌋ = ⌊x/q⌋。
    // 最后,若 x 是 q 的负倍数,则 ⌊x 20156/2²⁶⌋ = ⌊x/q⌋-1。
    // 于是:
    //                        [ q        当 x=-nq,n 为正整数
    //  x - ⌊x 20156/2²⁶⌋ q = [
    //                        [ x mod q  其他情况
    //
    // 实际计算时,注意:
    //
    //  ⌊x 20156/2²⁶⌋ = (20159 x) >> 26.
    return x -% @as(i16, @intCast((@as(i32, x) * 20159) >> 26)) *% Q;
}

test "Test Barrett reduction" {
    var x: i32 = -(1 << 15);
    while (x < 1 << 15) : (x += 1) {
        var y1 = feBarrettReduce(@as(i16, @intCast(x)));
        const y2 = @mod(@as(i16, @intCast(x)), Q);
        if (x < 0 and @rem(-x, Q) == 0) {
            y1 -= Q;
        }
        try testing.expectEqual(y1, y2);
    }
}

// 若 x < q 则返回 x,否则返回 x - q。假定 x ≥ -29439。
fn csubq(x: i16) i16 {
    var r = x;
    r -= Q;
    r += (r >> 15) & Q;
    return r;
}

test "Test csubq" {
    var x: i32 = -29439;
    while (x < 1 << 15) : (x += 1) {
        const y1 = csubq(@as(i16, @intCast(x)));
        var y2 = @as(i16, @intCast(x));
        if (@as(i16, @intCast(x)) >= Q) {
            y2 -= Q;
        }
        try testing.expectEqual(y1, y2);
    }
}

// 计算 ntt 和 invNTT 使用的 zetas 表。
fn computeZetas() [128]i16 {
    @setEvalBranchQuota(10000);
    var ret: [128]i16 = undefined;
    for (&ret, 0..) |*r, i| {
        const t = @as(i16, @intCast(modularPow(i32, zeta, @bitReverse(@as(u7, @intCast(i))), Q)));
        r.* = csubq(feBarrettReduce(feToMont(t)));
    }
    return ret;
}

// 基环 R 的一个元素,其中包含 ℤ_q 上的多项式,
// 模方程 Xᴺ = -1,其中 q=3329 且 N=256。
//
// 此类型也用于存储经过 NTT 变换的多项式,
// 参见 Poly.NTT()。
// 系数不一定已约简。参见 Normalize()。
//
const Poly = struct {
    cs: [N]i16,

    const encoded_length = N / 2 * 3;
    const zero: Poly = .{ .cs = @splat(0) };

    // 相加两个多项式(系数不规范化)。
    fn add(a: Poly, b: Poly) Poly {
        var ret: Poly = undefined;
        for (0..N) |i| {
            ret.cs[i] = a.cs[i] + b.cs[i];
        }
        return ret;
    }

    // 两个多项式相减(系数未规范化)
    fn sub(a: Poly, b: Poly) Poly {
        var ret: Poly = undefined;
        for (0..N) |i| {
            ret.cs[i] = a.cs[i] - b.cs[i];
        }
        return ret;
    }

    // 对 p 执行正向 NTT。
    //
    // 假定系数绝对值 ≤q。所得
    // 系数绝对值 ≤7q。如果输入采用蒙哥马利
    // 形式,则结果也采用蒙哥马利形式;由 NTT 的线性性可知,
    // 如果输入采用普通形式,则结果也采用普通形式。
    fn ntt(a: Poly) Poly {
        // 注意,ℤ_q 中不存在本原 512 次单位根,因为 512 不能整除 q-1,因此不能执行常规 NTT。ℤ_q 中存在本原 256 次单位根,其中最小者为 ζ := 17。
        //
        // 回顾基环 R := ℤ_q[x] / (x²⁵⁶ + 1)。多项式 x²⁵⁶+1 不能完全分裂,因为它的根应当是 512 次单位根。不过,利用 ζ¹²⁸ = -1,可以将其几乎完全分解:
        //
        // x²⁵⁶ + 1 = (x²)¹²⁸ - ζ¹²⁸
        //          = ((x²)⁶⁴ - ζ⁶⁴)((x²)⁶⁴ + ζ⁶⁴)
        //          = ((x²)³² - ζ³²)((x²)³² + ζ³²)((x²)³² - ζ⁹⁶)((x²)³² + ζ⁹⁶)
        //          ⋮
        //          = (x² - ζ)(x² + ζ)(x² - ζ⁶⁵)(x² + ζ⁶⁵) … (x² + ζ¹²⁷)
        //
        // 注意,从第二行开始出现的 ζ 的指数,其二进制形式为:
        //
        // 0100000 1100000
        // 0010000 1010000 0110000 1110000
        // 0001000 1001000 0101000 1101000 0011000 1011000 0111000 1111000
        //         …
        //
        // 也就是 brv(2)、brv(3)、brv(4) 等,其中 brv(x) 表示 x 的 7 位二进制位反转。这些 ζ 的幂由 Zetas 数组给出。
        //
        // 多项式 x² ± ζⁱ 不可约且互素,因此由中国剩余定理可知,以下映射:
        //
        //  ℤ_q[x]/(x²⁵⁶+1) → ℤ_q[x]/(x²-ζ) x … x  ℤ_q[x]/(x²+ζ¹²⁷)
        //
        // 由 a ↦ ( a mod x²-ζ, …, a mod x²+ζ¹²⁷ ) 给出,是一个同构,即这里的“NTT”。可以通过以下步骤高效计算:
        //
        //  a ↦ ( a mod (x²)⁶⁴ - ζ⁶⁴, a mod (x²)⁶⁴ + ζ⁶⁴ )
        //    ↦ ( a mod (x²)³² - ζ³², a mod (x²)³² + ζ³²,
        //        a mod (x²)⁹⁶ - ζ⁹⁶, a mod (x²)⁹⁶ + ζ⁹⁶ )
        //
        // 依此类推。
        // 若 N 为 8,可用下图表示:
        //
        //  https://cnx.org/resources/17ee4dfe517a6adda05377b25a00bf6e6c93c334/File0026.png
        //
        // 每个交叉点都是一个 Cooley-Tukey 蝶形运算,即映射:
        //
        //  (a, b) ↦ (a + ζb, a - ζb)
        //
        // 其中 ζ 取该列及该行组所对应的幂。
        //
        //
        //
        //
        //
        //
        //
        //
        //
        //
        var p = a;
        var k: usize = 0; // zetas 中的索引

        var l = N >> 1;
        while (l > 1) : (l >>= 1) {
            // 在 l 循环的第 n 次迭代中,系数的绝对值
            // 以 nq 为界。

            // offset 实际上用于遍历此列的行组;
            // 它是行组的第一行。
            var offset: usize = 0;
            while (offset < N - l) : (offset += 2 * l) {
                k += 1;
                const z = @as(i32, zetas[k]);

                // j 遍历行组中的各个蝶形操作。
                for (offset..offset + l) |j| {
                    const t = montReduce(z * @as(i32, p.cs[j + l]));
                    p.cs[j + l] = p.cs[j] - t;
                    p.cs[j] += t;
                }
            }
        }

        return p;
    }

    // 对 p 执行逆“NTT”,并乘以蒙哥马利因子 R。
    //
    // 假定系数的绝对值 ≤q。结果系数的绝对值
    // 也 ≤q。如果输入采用蒙哥马利表示,则结果也采用蒙哥马利
    // 表示;由线性性质可知,
    // 如果输入采用普通表示,则结果也采用普通表示。
    fn invNTT(a: Poly) Poly {
        var k: usize = 127; // zetas 中的索引
        var r: usize = 0; // invNTTReductions 的索引
        var p = a;

        // 基本上执行 NTT 的逆过程,但将 Cooley-Tukey 蝶形运算
        // 逆变换中的除以 2 延后,累计到最后一次
        // 除以 2⁷。参见 ntt() 函数中的注释。

        var l: usize = 2;
        while (l < N) : (l <<= 1) {
            var offset: usize = 0;
            while (offset < N - l) : (offset += 2 * l) {
                // 由于正在执行逆变换,需要 ζ⁻¹ 的幂,而非 ζ 的幂。
                // 准确地说,需要 ζᵇʳᵛ⁽ᵏ⁾⁻¹²⁸。但由于 ζ⁻¹²⁸ = -1,
                // 可以直接使用已有的 zetas 表,
                // 无需像 Dilithium 那样另存 invZetas 表。

                const minZeta = @as(i32, zetas[k]);
                k -= 1;

                for (offset..offset + l) |j| {
                    // Gentleman-Sande 蝶形运算:(a, b) ↦ (a + b, ζ(a-b))
                    const t = p.cs[j + l] - p.cs[j];
                    p.cs[j] += p.cs[j + l];
                    p.cs[j + l] = montReduce(minZeta * @as(i32, t));

                    // 注意,若蝶形运算前 |a| < αq 且 |b| < βq,
                    // 则此时 |a| < (α+β)q 且 |b| < q。
                }
            }

            // 让 invNTTReductions 指示哪些系数需要
            // 进行 Barrett 约减。
            while (true) {
                const i = inv_ntt_reductions[r];
                r += 1;
                if (i < 0) {
                    break;
                }
                p.cs[@as(usize, @intCast(i))] = feBarrettReduce(p.cs[@as(usize, @intCast(i))]);
            }
        }

        for (0..N) |j| {
            // 注意 1441 = (128)⁻¹ R²。系数以 9q 为界,
            // 由于 1441 * 9 ≈ 2¹⁴ < 2¹⁵,因此满足
            // montReduce() 所需的边界。
            p.cs[j] = montReduce(r2_over_128 * @as(i32, p.cs[j]));
        }

        return p;
    }

    // 归一化系数。
    //
    // 确保每个系数位于 {0, …, q-1} 中。
    fn normalize(a: Poly) Poly {
        var ret: Poly = undefined;
        for (0..N) |i| {
            ret.cs[i] = csubq(feBarrettReduce(a.cs[i]));
        }
        return ret;
    }

    // 将 p 转换为蒙哥马利形式。
    fn toMont(a: Poly) Poly {
        var ret: Poly = undefined;
        for (0..N) |i| {
            ret.cs[i] = feToMont(a.cs[i]);
        }
        return ret;
    }

    // 对系数进行 Barrett 约减。
    //
    // 注意,这不会完全规范化系数。
    fn barrettReduce(a: Poly) Poly {
        var ret: Poly = undefined;
        for (0..N) |i| {
            ret.cs[i] = feBarrettReduce(a.cs[i]);
        }
        return ret;
    }

    fn compressedSize(comptime d: u8) usize {
        return @divTrunc(N * d, 8);
    }

    // 返回打包后的 Compress_q(p, d)。
    //
    // 假定 p 已归一化。
    fn compress(p: Poly, comptime d: u8) [compressedSize(d)]u8 {
        @setEvalBranchQuota(10000);
        const q_over_2: u32 = comptime @divTrunc(Q, 2); // (q-1)/2
        const two_d_min_1: u32 = comptime (1 << d) - 1; // 2ᵈ-1
        var in_off: usize = 0;
        var out_off: usize = 0;

        const batch_size: usize = comptime math.lcm(d, 8);
        const in_batch_size: usize = comptime batch_size / d;
        const out_batch_size: usize = comptime batch_size / 8;

        const out_length: usize = comptime @divTrunc(N * d, 8);
        comptime assert(out_length * 8 == d * N);
        var out: [out_length]u8 = @splat(0);

        while (in_off < N) {
            // 首先压缩到 in 中。
            var in: [in_batch_size]u16 = undefined;
            inline for (0..in_batch_size) |i| {
                // Compress_q(x, d) = ⌈(2ᵈ/q)x⌋ mod⁺ 2ᵈ
                //                  = ⌊(2ᵈ/q)x+½⌋ mod⁺ 2ᵈ
                //                  = ⌊((x << d) + q/2) / q⌋ mod⁺ 2ᵈ
                //                  = DIV((x << d) + q/2, q) & ((1<<d) - 1)
                const t = @as(u24, @intCast(p.cs[in_off + i])) << d;
                // 通过不变量乘法实现除法,等同于 DIV(t + q/2, q)。
                // 即使分母为常量,除法也可能不是常量时间操作。
                // 此处的侧信道会泄漏共享秘密的信息,参见 https://kyberslash.cr.yp.to
                // 而在当前支持的 CPU 上,乘法是常量时间操作。
                comptime assert(d <= 11);
                comptime assert(((20642679 * @as(u64, Q)) >> 36) == 1);
                const u: u32 = @intCast((@as(u64, t + q_over_2) * 20642679) >> 36);
                in[i] = @intCast(u & two_d_min_1);
            }

            // 现在将 `in' 中的 d 位整数按字节打包到 out。
            comptime var in_shift: usize = 0;
            comptime var j: usize = 0;
            comptime var i: usize = 0;
            inline while (i < in_batch_size) : (j += 1) {
                comptime var todo: usize = 8;
                inline while (todo > 0) {
                    const out_shift = comptime 8 - todo;
                    out[out_off + j] |= @as(u8, @truncate((in[i] >> in_shift) << out_shift));

                    const done = comptime @min(@min(d, todo), d - in_shift);
                    todo -= done;
                    in_shift += done;

                    if (in_shift == d) {
                        in_shift = 0;
                        i += 1;
                    }
                }
            }

            in_off += in_batch_size;
            out_off += out_batch_size;
        }

        return out;
    }

    // 将 p 设置为 Decompress_q(m, d)。
    fn decompress(comptime d: u8, in: *const [compressedSize(d)]u8) Poly {
        @setEvalBranchQuota(10000);
        const in_len = comptime @divTrunc(N * d, 8);
        comptime assert(in_len * 8 == d * N);
        var ret: Poly = undefined;
        var in_off: usize = 0;
        var out_off: usize = 0;

        const batch_size: usize = comptime math.lcm(d, 8);
        const in_batch_size: usize = comptime batch_size / 8;
        const out_batch_size: usize = comptime batch_size / d;

        while (out_off < N) {
            comptime var in_shift: usize = 0;
            comptime var j: usize = 0;
            comptime var i: usize = 0;
            inline while (i < out_batch_size) : (i += 1) {
                // 首先解包下一个系数。
                comptime var todo = d;
                var out: u16 = 0;

                inline while (todo > 0) {
                    const out_shift = comptime d - todo;
                    const m = comptime (1 << d) - 1;
                    out |= (@as(u16, in[in_off + j] >> in_shift) << out_shift) & m;

                    const done = comptime @min(@min(8, todo), 8 - in_shift);
                    todo -= done;
                    in_shift += done;

                    if (in_shift == 8) {
                        in_shift = 0;
                        j += 1;
                    }
                }

                // Decompress_q(x, d) = ⌈(q/2ᵈ)x⌋
                //                    = ⌊(q/2ᵈ)x+½⌋
                //                    = ⌊(qx + 2ᵈ⁻¹)/2ᵈ⌋
                //                    = (qx + (1<<(d-1))) >> d
                const qx = @as(u32, out) * @as(u32, Q);
                ret.cs[out_off + i] = @as(i16, @intCast((qx + (1 << (d - 1))) >> d));
            }

            in_off += in_batch_size;
            out_off += out_batch_size;
        }

        return ret;
    }

    // 返回逐点乘积 a o b。
    //
    // 即 invNTT(a o b) = invNTT(a) * invNTT(b)。假定 a 和 b 采用
    // 蒙哥马利形式。a 和 b 的系数乘积的绝对值必须
    // 严格小于 2¹⁵q。a o b 将采用蒙哥马利形式,且
    // 绝对值以 2q 为界。
    fn mulHat(a: Poly, b: Poly) Poly {
        // 回顾 ntt() 中的讨论,变换后的多项式是 ℤ_q[x]/(x²-ζ) x … x  ℤ_q[x]/(x²+ζ¹²⁷) 的元素,也就是 128 个一次多项式,而不是常规 NTT 中简单的 256 个 ℤ_q 元素。
        // 因此不执行逐点乘法,而是在相应等式的模意义下,对 128 对一次多项式相乘:
        //
        //  (a₁ + a₂x)(b₁ + b₂x) = a₁b₁ + a₂b₂ζ' + (a₁b₂ + a₂b₁)x,
        //
        // 其中 ζ' 是 ζ 的适当次幂。
        //
        //
        //
        //

        var p: Poly = undefined;
        var k: usize = 64;
        var i: usize = 0;
        while (i < N) : (i += 4) {
            const z = @as(i32, zetas[k]);
            k += 1;

            const a1b1 = montReduce(@as(i32, a.cs[i + 1]) * @as(i32, b.cs[i + 1]));
            const a0b0 = montReduce(@as(i32, a.cs[i]) * @as(i32, b.cs[i]));
            const a1b0 = montReduce(@as(i32, a.cs[i + 1]) * @as(i32, b.cs[i]));
            const a0b1 = montReduce(@as(i32, a.cs[i]) * @as(i32, b.cs[i + 1]));

            p.cs[i] = montReduce(a1b1 * z) + a0b0;
            p.cs[i + 1] = a0b1 + a1b0;

            const a3b3 = montReduce(@as(i32, a.cs[i + 3]) * @as(i32, b.cs[i + 3]));
            const a2b2 = montReduce(@as(i32, a.cs[i + 2]) * @as(i32, b.cs[i + 2]));
            const a3b2 = montReduce(@as(i32, a.cs[i + 3]) * @as(i32, b.cs[i + 2]));
            const a2b3 = montReduce(@as(i32, a.cs[i + 2]) * @as(i32, b.cs[i + 3]));

            p.cs[i + 2] = a2b2 - montReduce(a3b3 * z);
            p.cs[i + 3] = a2b3 + a3b2;
        }

        return p;
    }

    // 从 n=2η、p=½ 的中心二项分布采样 p,即:
    // 系数位于 {-η, …, η},概率分别为
    //
    //  {ncr(0, 2η)/2^2η, ncr(1, 2η)/2^2η, …, ncr(2η,2η)/2^2η}
    fn noise(comptime eta: u8, nonce: u8, seed: *const [32]u8) Poly {
        var h = sha3.Shake256.init(.{});
        const suffix: [1]u8 = .{nonce};
        h.update(seed);
        h.update(&suffix);

        // 这里的分布与 (a₁ + a₂ + … + a_η) - (b₁ + … + b_η) 完全相同,其中 a_i,b_i~U(1)。
        // 因此每个系数需要 2η 位。
        //
        const buf_len = comptime 2 * eta * N / 8;
        var buf: [buf_len]u8 = undefined;
        h.squeeze(&buf);

        // buf 解释为 a₁…a_ηb₁…b_ηa₁…a_ηb₁…b_η…。每批处理
        // 多个系数。

        const T = switch (builtin.target.cpu.arch) {
            .x86_64, .x86 => u32, // 在 Intel CPU 上生成更好的代码
            else => u64, // 在某些其他 CPU 上 u128 可能更快。
        };

        comptime var batch_count: usize = undefined;
        comptime var batch_bytes: usize = undefined;
        comptime var mask: T = 0;
        comptime {
            batch_count = @bitSizeOf(T) / @as(usize, 2 * eta);
            while (@rem(N, batch_count) != 0 and batch_count > 0) : (batch_count -= 1) {}
            assert(batch_count > 0);
            assert(@rem(2 * eta * batch_count, 8) == 0);
            batch_bytes = 2 * eta * batch_count / 8;

            for (0..2 * eta * batch_count) |_| {
                mask <<= eta;
                mask |= 1;
            }
        }

        var ret: Poly = undefined;
        for (0..comptime N / batch_count) |i| {
            // 将系数读入 t。当 η=3 时,
            // t = a₁ + 2a₂ + 4a₃ + 8b₁ + 16b₂ + …
            var t: T = 0;
            inline for (0..batch_bytes) |j| {
                t |= @as(T, buf[batch_bytes * i + j]) << (8 * j);
            }

            // 通过掩码提取、移位和相加,分别累加 `a` 和 `b`。
            // 当 η=3 时,d = a₁ + a₂ + a₃ + 8(b₁ + b₂ + b₃) + …
            var d: T = 0;
            inline for (0..eta) |j| {
                d += (t >> j) & mask;
            }

            // 分别提取每个 a 和 b,并设置多项式中的系数。
            inline for (0..batch_count) |j| {
                const mask2 = comptime (1 << eta) - 1;
                const a = @as(i16, @intCast((d >> (comptime (2 * j * eta))) & mask2));
                const b = @as(i16, @intCast((d >> (comptime ((2 * j + 1) * eta))) & mask2));
                ret.cs[batch_count * i + j] = a - b;
            }
        }

        return ret;
    }

    fn uniform(seed: [32]u8, x: u8, y: u8) Poly {
        const domain_sep: [2]u8 = .{ x, y };
        return sampleUniformRejection(
            Poly,
            Q,
            12,
            N,
            &seed,
            &domain_sep,
        );
    }

    // 打包 p。
    //
    // 假定 p 已归一化,而不只是经过 Barrett 约减。
    fn toBytes(p: Poly) [encoded_length]u8 {
        var ret: [encoded_length]u8 = undefined;
        for (0..comptime N / 2) |i| {
            const t0 = @as(u16, @intCast(p.cs[2 * i]));
            const t1 = @as(u16, @intCast(p.cs[2 * i + 1]));
            ret[3 * i] = @as(u8, @truncate(t0));
            ret[3 * i + 1] = @as(u8, @truncate((t0 >> 8) | (t1 << 4)));
            ret[3 * i + 2] = @as(u8, @truncate(t1 >> 4));
        }
        return ret;
    }

    // 从 buf 解包一个 Poly。
    //
    // p 不会被规范化,而是满足 0 ≤ p[i] < 4096。
    fn fromBytes(buf: *const [encoded_length]u8) Poly {
        var ret: Poly = undefined;
        for (0..comptime N / 2) |i| {
            const b0 = @as(i16, buf[3 * i]);
            const b1 = @as(i16, buf[3 * i + 1]);
            const b2 = @as(i16, buf[3 * i + 2]);
            ret.cs[2 * i] = b0 | ((b1 & 0xf) << 8);
            ret.cs[2 * i + 1] = (b1 >> 4) | b2 << 4;
        }
        return ret;
    }
};

// 由 k 个多项式组成的向量。
fn PolyVec(comptime k: u8) type {
    return struct {
        ps: [k]Poly,

        const Self = @This();
        const encoded_length = k * Poly.encoded_length;

        fn compressedSize(comptime d: u8) usize {
            return Poly.compressedSize(d) * k;
        }

        /// 对每个多项式应用一元运算
        fn map(v: Self, comptime op: fn (Poly) Poly) Self {
            var ret: Self = undefined;
            inline for (0..k) |i| {
                ret.ps[i] = op(v.ps[i]);
            }
            return ret;
        }

        /// 逐对应用二元运算
        fn mapBinary(a: Self, b: Self, comptime op: fn (Poly, Poly) Poly) Self {
            var ret: Self = undefined;
            inline for (0..k) |i| {
                ret.ps[i] = op(a.ps[i], b.ps[i]);
            }
            return ret;
        }

        fn ntt(v: Self) Self {
            return map(v, Poly.ntt);
        }

        fn invNTT(v: Self) Self {
            return map(v, Poly.invNTT);
        }

        fn normalize(v: Self) Self {
            return map(v, Poly.normalize);
        }

        fn barrettReduce(v: Self) Self {
            return map(v, Poly.barrettReduce);
        }

        fn add(a: Self, b: Self) Self {
            return mapBinary(a, b, Poly.add);
        }

        fn sub(a: Self, b: Self) Self {
            return mapBinary(a, b, Poly.sub);
        }

        // 使用给定 η、seed 和 nonce+i,从中心二项分布中
        // 采样 v[i]。
        fn noise(comptime eta: u8, nonce: u8, seed: *const [32]u8) Self {
            var ret: Self = undefined;
            for (0..k) |i| {
                ret.ps[i] = Poly.noise(eta, nonce + @as(u8, @intCast(i)), seed);
            }
            return ret;
        }

        // 使用“逐点”乘法,将 p 设为 a 和 b 的内积。
        //
        // 乘法的说明参见 MulHat() 和 NTT()。
        // 假定 a 和 b 采用蒙哥马利形式。p 也将采用蒙哥马利形式,
        // 其系数绝对值以 2kq 为界。
        // 如果 a 和 b 不是蒙哥马利形式,则此操作等同于
        // 逐点相乘后再乘以 R⁻¹,即蒙哥马利因子的
        // 逆元。
        fn dotHat(a: Self, b: Self) Poly {
            var ret: Poly = Poly.zero;
            for (0..k) |i| {
                ret = ret.add(a.ps[i].mulHat(b.ps[i]));
            }
            return ret;
        }

        fn compress(v: Self, comptime d: u8) [compressedSize(d)]u8 {
            const cs = comptime Poly.compressedSize(d);
            var ret: [compressedSize(d)]u8 = undefined;
            inline for (0..k) |i| {
                ret[i * cs .. (i + 1) * cs].* = v.ps[i].compress(d);
            }
            return ret;
        }

        fn decompress(comptime d: u8, buf: *const [compressedSize(d)]u8) Self {
            const cs = comptime Poly.compressedSize(d);
            var ret: Self = undefined;
            inline for (0..k) |i| {
                ret.ps[i] = Poly.decompress(d, buf[i * cs .. (i + 1) * cs]);
            }
            return ret;
        }

        /// 将密钥序列化为字节数组。
        fn toBytes(v: Self) [encoded_length]u8 {
            var ret: [encoded_length]u8 = undefined;
            inline for (0..k) |i| {
                ret[i * Poly.encoded_length .. (i + 1) * Poly.encoded_length].* = v.ps[i].toBytes();
            }
            return ret;
        }

        /// 从字节数组反序列化密钥。
        fn fromBytes(buf: *const [encoded_length]u8) Self {
            var ret: Self = undefined;
            inline for (0..k) |i| {
                ret.ps[i] = Poly.fromBytes(
                    buf[i * Poly.encoded_length .. (i + 1) * Poly.encoded_length],
                );
            }
            return ret;
        }
    };
}

// 由 k 个向量构成的矩阵
fn Mat(comptime k: u8) type {
    return struct {
        const Self = @This();
        rows: [k]PolyVec(k),

        fn uniform(seed: [32]u8, comptime transposed: bool) Self {
            var ret: Self = undefined;
            var i: u8 = 0;
            while (i < k) : (i += 1) {
                var j: u8 = 0;
                while (j < k) : (j += 1) {
                    ret.rows[i].ps[j] = Poly.uniform(
                        seed,
                        if (transposed) i else j,
                        if (transposed) j else i,
                    );
                }
            }
            return ret;
        }

        // 返回 A 的转置
        fn transpose(m: Self) Self {
            var ret: Self = undefined;
            for (0..k) |i| {
                for (0..k) |j| {
                    ret.rows[i].ps[j] = m.rows[j].ps[i];
                }
            }
            return ret;
        }
    };
}

// 若 a ≠ b 则返回 `true`。
fn ctneq(comptime len: usize, a: [len]u8, b: [len]u8) u1 {
    return 1 - @intFromBool(crypto.timing_safe.eql([len]u8, a, b));
}

// b = 1 时将 src 复制到 dst。
fn cmov(comptime len: usize, dst: *[len]u8, src: [len]u8, b: u1) void {
    const mask = @as(u8, 0) -% b;
    for (0..len) |i| {
        dst[i] ^= mask & (dst[i] ^ src[i]);
    }
}

// 测试辅助函数:生成每个系数均满足 |x| ≤ q 的随机多项式
fn randPolyAbsLeqQ(rnd: anytype) Poly {
    var ret: Poly = undefined;
    for (0..N) |i| {
        ret.cs[i] = rnd.random().intRangeAtMost(i16, -Q, Q);
    }
    return ret;
}

// 测试辅助函数:生成随机的规范化多项式。
fn randPolyNormalized(rnd: anytype) Poly {
    var ret: Poly = undefined;
    for (0..N) |i| {
        ret.cs[i] = rnd.random().intRangeLessThan(i16, 0, Q);
    }
    return ret;
}

test "MulHat" {
    var rnd = RndGen.init(0);

    for (0..100) |_| {
        const a = randPolyAbsLeqQ(&rnd);
        const b = randPolyAbsLeqQ(&rnd);

        const p2 = a.ntt().mulHat(b.ntt()).barrettReduce().invNTT().normalize();
        var p: Poly = undefined;

        @memset(&p.cs, 0);

        for (0..N) |i| {
            for (0..N) |j| {
                var v = montReduce(@as(i32, a.cs[i]) * @as(i32, b.cs[j]));
                var k = i + j;
                if (k >= N) {
                    // 回顾 Xᴺ = -1。
                    k -= N;
                    v = -v;
                }
                p.cs[k] = feBarrettReduce(v + p.cs[k]);
            }
        }

        p = p.toMont().normalize();

        try testing.expectEqual(p, p2);
    }
}

test "NTT" {
    var rnd = RndGen.init(0);

    for (0..1000) |_| {
        var p = randPolyAbsLeqQ(&rnd);
        const q = p.toMont().normalize();
        p = p.ntt();

        for (0..N) |i| {
            try testing.expect(p.cs[i] <= 7 * Q and -7 * Q <= p.cs[i]);
        }

        p = p.normalize().invNTT();
        for (0..N) |i| {
            try testing.expect(p.cs[i] <= Q and -Q <= p.cs[i]);
        }

        p = p.normalize();

        try testing.expectEqual(p, q);
    }
}

test "Compression" {
    var rnd = RndGen.init(0);
    inline for (.{ 1, 4, 5, 10, 11 }) |d| {
        for (0..1000) |_| {
            const p = randPolyNormalized(&rnd);
            const pp = p.compress(d);
            const pq = Poly.decompress(d, &pp).compress(d);
            try testing.expectEqual(pp, pq);
        }
    }
}

test "noise" {
    var seed: [32]u8 = undefined;
    for (&seed, 0..) |*s, i| {
        s.* = @as(u8, @intCast(i));
    }
    try testing.expectEqual(Poly.noise(3, 37, &seed).cs, .{
        0,  0,  1,  -1, 0,  2,  0,  -1, -1, 3,  0,  1,  -2, -2, 0,  1,  -2,
        1,  0,  -2, 3,  0,  0,  0,  1,  3,  1,  1,  2,  1,  -1, -1, -1, 0,
        1,  0,  1,  0,  2,  0,  1,  -2, 0,  -1, -1, -2, 1,  -1, -1, 2,  -1,
        1,  1,  2,  -3, -1, -1, 0,  0,  0,  0,  1,  -1, -2, -2, 0,  -2, 0,
        0,  0,  1,  0,  -1, -1, 1,  -2, 2,  0,  0,  2,  -2, 0,  1,  0,  1,
        1,  1,  0,  1,  -2, -1, -2, -1, 1,  0,  0,  0,  0,  0,  1,  0,  -1,
        -1, 0,  -1, 1,  0,  1,  0,  -1, -1, 0,  -2, 2,  0,  -2, 1,  -1, 0,
        1,  -1, -1, 2,  1,  0,  0,  -2, -1, 2,  0,  0,  0,  -1, -1, 3,  1,
        0,  1,  0,  1,  0,  2,  1,  0,  0,  1,  0,  1,  0,  0,  -1, -1, -1,
        0,  1,  3,  1,  0,  1,  0,  1,  -1, -1, -1, -1, 0,  0,  -2, -1, -1,
        2,  0,  1,  0,  1,  0,  2,  -2, 0,  1,  1,  -3, -1, -2, -1, 0,  1,
        0,  1,  -2, 2,  2,  1,  1,  0,  -1, 0,  -1, -1, 1,  0,  -1, 2,  1,
        -1, 1,  2,  -2, 1,  2,  0,  1,  2,  1,  0,  0,  2,  1,  2,  1,  0,
        2,  1,  0,  0,  -1, -1, 1,  -1, 0,  1,  -1, 2,  2,  0,  0,  -1, 1,
        1,  1,  1,  0,  0,  -2, 0,  -1, 1,  2,  0,  0,  1,  1,  -1, 1,  0,
        1,
    });
    try testing.expectEqual(Poly.noise(2, 37, &seed).cs, .{
        1,  0,  1,  -1, -1, -2, -1, -1, 2,  0,  -1, 0,  0,  -1,
        1,  1,  -1, 1,  0,  2,  -2, 0,  1,  2,  0,  0,  -1, 1,
        0,  -1, 1,  -1, 1,  2,  1,  1,  0,  -1, 1,  -1, -2, -1,
        1,  -1, -1, -1, 2,  -1, -1, 0,  0,  1,  1,  -1, 1,  1,
        1,  1,  -1, -2, 0,  1,  0,  0,  2,  1,  -1, 2,  0,  0,
        1,  1,  0,  -1, 0,  0,  -1, -1, 2,  0,  1,  -1, 2,  -1,
        -1, -1, -1, 0,  -2, 0,  2,  1,  0,  0,  0,  -1, 0,  0,
        0,  -1, -1, 0,  -1, -1, 0,  -1, 0,  0,  -2, 1,  1,  0,
        1,  0,  1,  0,  1,  1,  -1, 2,  0,  1,  -1, 1,  2,  0,
        0,  0,  0,  -1, -1, -1, 0,  1,  0,  -1, 2,  0,  0,  1,
        1,  1,  0,  1,  -1, 1,  2,  1,  0,  2,  -1, 1,  -1, -2,
        -1, -2, -1, 1,  0,  -2, -2, -1, 1,  0,  0,  0,  0,  1,
        0,  0,  0,  2,  2,  0,  1,  0,  -1, -1, 0,  2,  0,  0,
        -2, 1,  0,  2,  1,  -1, -2, 0,  0,  -1, 1,  1,  0,  0,
        2,  0,  1,  1,  -2, 1,  -2, 1,  1,  0,  2,  0,  -1, 0,
        -1, 0,  1,  2,  0,  1,  0,  -2, 1,  -2, -2, 1,  -1, 0,
        -1, 1,  1,  0,  0,  0,  1,  0,  -1, 1,  1,  0,  0,  0,
        0,  1,  0,  1,  -1, 0,  1,  -1, -1, 2,  0,  0,  1,  -1,
        0,  1,  -1, 0,
    });
}

test "uniform sampling" {
    var seed: [32]u8 = undefined;
    for (&seed, 0..) |*s, i| {
        s.* = @as(u8, @intCast(i));
    }
    try testing.expectEqual(Poly.uniform(seed, 1, 0).cs, .{
        797,  993,  161,  6,    2608, 2385, 2096, 2661, 1676, 247,  2440,
        342,  634,  194,  1570, 2848, 986,  684,  3148, 3208, 2018, 351,
        2288, 612,  1394, 170,  1521, 3119, 58,   596,  2093, 1549, 409,
        2156, 1934, 1730, 1324, 388,  446,  418,  1719, 2202, 1812, 98,
        1019, 2369, 214,  2699, 28,   1523, 2824, 273,  402,  2899, 246,
        210,  1288, 863,  2708, 177,  3076, 349,  44,   949,  854,  1371,
        957,  292,  2502, 1617, 1501, 254,  7,    1761, 2581, 2206, 2655,
        1211, 629,  1274, 2358, 816,  2766, 2115, 2985, 1006, 2433, 856,
        2596, 3192, 1,    1378, 2345, 707,  1891, 1669, 536,  1221, 710,
        2511, 120,  1176, 322,  1897, 2309, 595,  2950, 1171, 801,  1848,
        695,  2912, 1396, 1931, 1775, 2904, 893,  2507, 1810, 2873, 253,
        1529, 1047, 2615, 1687, 831,  1414, 965,  3169, 1887, 753,  3246,
        1937, 115,  2953, 586,  545,  1621, 1667, 3187, 1654, 1988, 1857,
        512,  1239, 1219, 898,  3106, 391,  1331, 2228, 3169, 586,  2412,
        845,  768,  156,  662,  478,  1693, 2632, 573,  2434, 1671, 173,
        969,  364,  1663, 2701, 2169, 813,  1000, 1471, 720,  2431, 2530,
        3161, 733,  1691, 527,  2634, 335,  26,   2377, 1707, 767,  3020,
        950,  502,  426,  1138, 3208, 2607, 2389, 44,   1358, 1392, 2334,
        875,  2097, 173,  1697, 2578, 942,  1817, 974,  1165, 2853, 1958,
        2973, 3282, 271,  1236, 1677, 2230, 673,  1554, 96,   242,  1729,
        2518, 1884, 2272, 71,   1382, 924,  1807, 1610, 456,  1148, 2479,
        2152, 238,  2208, 2329, 713,  1175, 1196, 757,  1078, 3190, 3169,
        708,  3117, 154,  1751, 3225, 1364, 154,  23,   2842, 1105, 1419,
        79,   5,    2013,
    });
}

test "Polynomial packing" {
    var rnd = RndGen.init(0);

    for (0..1000) |_| {
        const p = randPolyNormalized(&rnd);
        try testing.expectEqual(Poly.fromBytes(&p.toBytes()), p);
    }
}

test "Test inner PKE" {
    var seed: [32]u8 = undefined;
    var pt: [32]u8 = undefined;
    for (&seed, &pt, 0..) |*s, *p, i| {
        s.* = @as(u8, @intCast(i));
        p.* = @as(u8, @intCast(i + 32));
    }
    inline for (modes) |mode| {
        for (0..10) |i| {
            var pk: mode.InnerPk = undefined;
            var sk: mode.InnerSk = undefined;
            seed[0] = @as(u8, @intCast(i));
            mode.innerKeyFromSeed(seed, &pk, &sk);
            for (0..10) |j| {
                seed[1] = @as(u8, @intCast(j));
                try testing.expectEqual(sk.decrypt(&pk.encrypt(&pt, &seed)), pt);
            }
        }
    }
}

test "Test happy flow" {
    var seed: [64]u8 = undefined;
    for (&seed, 0..) |*s, i| {
        s.* = @as(u8, @intCast(i));
    }
    inline for (modes) |mode| {
        for (0..10) |i| {
            seed[0] = @intCast(i);
            const kp = try mode.KeyPair.generateDeterministic(seed);
            const sk = try mode.SecretKey.fromBytes(&kp.secret_key.toBytes());
            try testing.expectEqual(sk, kp.secret_key);
            const pk = try mode.PublicKey.fromBytes(&kp.public_key.toBytes());
            try testing.expectEqual(pk, kp.public_key);
            for (0..10) |j| {
                seed[1] = @intCast(j);
                const e = pk.encapsDeterministic(seed[0..32]);
                try testing.expectEqual(e.shared_secret, try sk.decaps(&e.ciphertext));
            }
        }
    }
}

// 用于执行 NIST 已知答案测试(KAT)的代码,参见 PQCgenKAT.c。

test "NIST KAT test d00.Kyber512" {
    try testNistKat(d00.Kyber512, "e9c2bd37133fcb40772f81559f14b1f58dccd1c816701be9ba6214d43baf4547");
}

test "NIST KAT test d00.Kyber1024" {
    try testNistKat(d00.Kyber1024, "89248f2f33f7f4f7051729111f3049c409a933ec904aedadf035f30fa5646cd5");
}

test "NIST KAT test d00.Kyber768" {
    try testNistKat(d00.Kyber768, "a1e122cad3c24bc51622e4c242d8b8acbcd3f618fee4220400605ca8f9ea02c2");
}

fn testNistKat(mode: type, hash: []const u8) !void {
    var seed: [48]u8 = undefined;
    for (&seed, 0..) |*s, i| {
        s.* = @as(u8, @intCast(i));
    }
    var fw: std.Io.Writer.Hashing(crypto.hash.sha2.Sha256) = .init(&.{});
    var g = NistDRBG.init(seed);
    try fw.writer.print("# {s}\n\n", .{mode.name});
    for (0..100) |i| {
        g.fill(&seed);
        try fw.writer.print("count = {}\n", .{i});
        try fw.writer.print("seed = {X}\n", .{&seed});
        var g2 = NistDRBG.init(seed);

        // 这不等价于 g2.fill(kseed[:])。由于参考实现
        // 生成密钥对时调用 randombytes 两次,
        // 这里也必须如此。
        var kseed: [64]u8 = undefined;
        var eseed: [32]u8 = undefined;
        g2.fill(kseed[0..32]);
        g2.fill(kseed[32..64]);
        g2.fill(&eseed);
        const kp = try mode.KeyPair.generateDeterministic(kseed);
        const e = kp.public_key.encapsDeterministic(&eseed);
        const ss2 = try kp.secret_key.decaps(&e.ciphertext);
        try testing.expectEqual(ss2, e.shared_secret);
        try fw.writer.print("pk = {X}\n", .{&kp.public_key.toBytes()});
        try fw.writer.print("sk = {X}\n", .{&kp.secret_key.toBytes()});
        try fw.writer.print("ct = {X}\n", .{&e.ciphertext});
        try fw.writer.print("ss = {X}\n\n", .{&e.shared_secret});
    }

    var out: [32]u8 = undefined;
    fw.hasher.final(&out);
    var outHex: [64]u8 = undefined;
    _ = try std.mem.print(&outHex, "{x}", .{&out});
    try testing.expectEqualStrings(&outHex, hash);
}

const NistDRBG = struct {
    key: [32]u8,
    v: [16]u8,

    fn incV(g: *NistDRBG) void {
        const val = std.mem.readInt(u128, &g.v, .big);
        std.mem.writeInt(u128, &g.v, val +% 1, .big);
    }

    // AES256_CTR_DRBG_Update(pd, &g.key, &g.v).
    fn update(g: *NistDRBG, pd: ?[48]u8) void {
        var buf: [48]u8 = undefined;
        const ctx = crypto.core.aes.Aes256.initEnc(g.key);
        var i: usize = 0;
        while (i < 3) : (i += 1) {
            g.incV();
            var block: [16]u8 = undefined;
            ctx.encrypt(&block, &g.v);
            buf[i * 16 ..][0..16].* = block;
        }
        if (pd) |p| {
            for (&buf, p) |*b, x| {
                b.* ^= x;
            }
        }
        g.key = buf[0..32].*;
        g.v = buf[32..48].*;
    }

    // randombytes.
    fn fill(g: *NistDRBG, out: []u8) void {
        var block: [16]u8 = undefined;
        var dst = out;

        const ctx = crypto.core.aes.Aes256.initEnc(g.key);
        while (dst.len > 0) {
            g.incV();
            ctx.encrypt(&block, &g.v);
            if (dst.len < 16) {
                @memcpy(dst, block[0..dst.len]);
                break;
            }
            dst[0..block.len].* = block;
            dst = dst[16..dst.len];
        }
        g.update(null);
    }

    fn init(seed: [48]u8) NistDRBG {
        var ret: NistDRBG = .{ .key = @splat(0), .v = @splat(0) };
        ret.update(seed);
        return ret;
    }
};

/// 扩展欧几里得算法。
/// 仅用于编译期值;重视正确性,不重视性能。
fn extendedEuclidean(comptime T: type, comptime a_: T, comptime b_: T) struct { gcd: T, x: T, y: T } {
    var a = a_;
    var b = b_;
    var x0: T = 1;
    var x1: T = 0;
    var y0: T = 0;
    var y1: T = 1;

    while (b != 0) {
        const q = @divTrunc(a, b);
        const temp_a = a;
        a = b;
        b = temp_a - q * b;

        const temp_x = x0;
        x0 = x1;
        x1 = temp_x - q * x1;

        const temp_y = y0;
        y0 = y1;
        y1 = temp_y - q * y1;
    }

    return .{ .gcd = a, .x = x0, .y = y0 };
}

/// 模逆:计算 a^(-1) mod p
/// 要求 gcd(a,p) = 1。结果规范化到范围 [0, p)。
fn modularInverse(comptime T: type, comptime a: T, comptime p: T) T {
    // 使用有符号类型计算 EEA
    const type_info = @typeInfo(T);
    const SignedT = if (type_info == .int and type_info.int.signedness == .unsigned)
        @Int(.signed, type_info.int.bits)
    else
        T;

    const a_signed = @as(SignedT, @intCast(a));
    const p_signed = @as(SignedT, @intCast(p));

    const r = extendedEuclidean(SignedT, a_signed, p_signed);
    assert(r.gcd == 1);

    // 将结果规范化至 [0, p)
    var result = r.x;
    while (result < 0) {
        result += p_signed;
    }

    return @intCast(result);
}

/// 模幂:使用平方乘算法计算 a^s mod p。
fn modularPow(comptime T: type, comptime a: T, s: T, comptime p: T) T {
    const type_info = @typeInfo(T);
    const bits = type_info.int.bits;
    const WideT = @Int(.unsigned, bits * 2);

    var ret: T = 1;
    var base: T = a;
    var exp = s;

    while (exp > 0) {
        if (exp & 1 == 1) {
            ret = @intCast((@as(WideT, ret) * @as(WideT, base)) % p);
        }
        base = @intCast((@as(WideT, base) * @as(WideT, base)) % p);
        exp >>= 1;
    }

    return ret;
}

/// 根据单个位值创建全一或全零掩码。
/// 若 bit == 1,则返回全一(0xFF...FF);若 bit == 0,则返回全零。
fn bitMask(comptime T: type, bit: T) T {
    const type_info = @typeInfo(T);
    if (type_info != .int or type_info.int.signedness != .unsigned) {
        @compileError("bitMask requires an unsigned integer type");
    }
    return -%bit;
}

/// 由有符号整数的符号位创建掩码。
/// x < 0 时返回全 1(0xFF...FF),x >= 0 时返回全 0。
fn signMask(comptime T: type, x: T) @Int(.unsigned, @typeInfo(T).int.bits) {
    const type_info = @typeInfo(T);
    if (type_info != .int) {
        @compileError("signMask requires an integer type");
    }

    const bits = type_info.int.bits;
    const SignedT = @Int(.signed, bits);

    // 必要时转换为有符号类型,通过算术右移传播符号位
    const x_signed: SignedT = if (type_info.int.signedness == .signed) x else @bitCast(x);
    const shifted = x_signed >> (bits - 1);
    return @bitCast(shifted);
}

test "bitMask and signMask helpers" {
    try testing.expectEqual(@as(u32, 0x00000000), bitMask(u32, 0));
    try testing.expectEqual(@as(u32, 0xFFFFFFFF), bitMask(u32, 1));
    try testing.expectEqual(@as(u8, 0x00), bitMask(u8, 0));
    try testing.expectEqual(@as(u8, 0xFF), bitMask(u8, 1));
    try testing.expectEqual(@as(u64, 0x0000000000000000), bitMask(u64, 0));
    try testing.expectEqual(@as(u64, 0xFFFFFFFFFFFFFFFF), bitMask(u64, 1));

    try testing.expectEqual(@as(u32, 0xFFFFFFFF), signMask(i32, -1));
    try testing.expectEqual(@as(u32, 0xFFFFFFFF), signMask(i32, -100));
    try testing.expectEqual(@as(u32, 0x00000000), signMask(i32, 0));
    try testing.expectEqual(@as(u32, 0x00000000), signMask(i32, 1));
    try testing.expectEqual(@as(u32, 0x00000000), signMask(i32, 100));

    try testing.expectEqual(@as(u32, 0xFFFFFFFF), signMask(u32, 0x80000000)); // 最高有效位已设置
    try testing.expectEqual(@as(u32, 0x00000000), signMask(u32, 0x7FFFFFFF)); // 最高有效位清零
}

/// 蒙哥马利约减:对于输入 x,返回满足 y ≡ x*R^(-1) (mod q) 的 y。
/// 此通用实现由模数 q、其逆元 qInv、
/// 蒙哥马利常量 R 及结果边界参数化。
///
/// 对于 ML-DSA:R = 2^32,返回 y < 2q。
/// 对于 ML-KEM:R = 2^16,返回范围为 (-q, q) 的 y。
fn montgomeryReduce(
    comptime InT: type,
    comptime OutT: type,
    comptime q: comptime_int,
    comptime qInv: comptime_int,
    comptime r_bits: comptime_int,
    x: InT,
) OutT {
    const mask = (@as(InT, 1) << r_bits) - 1;
    const m_full = (x *% qInv) & mask;
    const m: OutT = @truncate(m_full);

    const yR = x -% @as(InT, m) * @as(InT, q);
    const y_shifted = @as(@Int(.unsigned, @typeInfo(InT).Int.bits), @bitCast(yR)) >> r_bits;
    return @bitCast(@as(@Int(.unsigned, @typeInfo(OutT).Int.bits), @truncate(y_shifted)));
}

/// 使用 SHAKE-128 和拒绝采样进行均匀采样。
/// 通过拒绝采样,从 [0, q) 中均匀采样多项式系数。
///
/// 参数:
/// - PolyType:要返回的多项式类型
/// - q:模数
/// - bits_per_coef:每个系数的位数,12 或 23
/// - n:系数数量
/// - seed:随机种子
/// - domain_sep:域分离字节,追加到种子之后
fn sampleUniformRejection(
    comptime PolyType: type,
    comptime q: comptime_int,
    comptime bits_per_coef: comptime_int,
    comptime n: comptime_int,
    seed: []const u8,
    domain_sep: []const u8,
) PolyType {
    var h = sha3.Shake128.init(.{});
    h.update(seed);
    h.update(domain_sep);

    const buf_len = sha3.Shake128.block_length; // 168 字节
    var buf: [buf_len]u8 = undefined;

    var ret: PolyType = undefined;
    var coef_idx: usize = 0;

    if (bits_per_coef == 12) {
        // ML-KEM 路径:每 3 字节打包 2 个系数(各 12 位)
        outer: while (true) {
            h.squeeze(&buf);

            var j: usize = 0;
            while (j < buf_len) : (j += 3) {
                const b0 = @as(u16, buf[j]);
                const b1 = @as(u16, buf[j + 1]);
                const b2 = @as(u16, buf[j + 2]);

                const ts: [2]u16 = .{
                    b0 | ((b1 & 0xf) << 8),
                    (b1 >> 4) | (b2 << 4),
                };

                inline for (ts) |t| {
                    if (t < q) {
                        ret.cs[coef_idx] = @intCast(t);
                        coef_idx += 1;
                        if (coef_idx == n) break :outer;
                    }
                }
            }
        }
    } else if (bits_per_coef == 23) {
        // ML-DSA 路径:每 3 字节存储 1 个系数(23 位)
        while (coef_idx < n) {
            h.squeeze(&buf);

            var j: usize = 0;
            while (j < buf_len and coef_idx < n) : (j += 3) {
                const t = (@as(u32, buf[j]) |
                    (@as(u32, buf[j + 1]) << 8) |
                    (@as(u32, buf[j + 2]) << 16)) & 0x7fffff;

                if (t < q) {
                    ret.cs[coef_idx] = @intCast(t);
                    coef_idx += 1;
                }
            }
        }
    } else {
        @compileError("bits_per_coef must be 12 or 23");
    }

    return ret;
}