实现具备 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。
stdbuiltintestingassertcryptoerrorsmathmemsha3RndGenQRNeta2Paramsd00nistmodesh_lengthinner_seed_lengthcommon_encaps_seed_lengthcommon_shared_key_sizeKyberr_mod_qr2_mod_qzetar2_over_128zetasinv_ntt_reductionsinvertModmodQ32montReducefeToMontfeBarrettReducecsubqcomputeZetasPolyPolyVecMatctneqcmovrandPolyAbsLeqQrandPolyNormalizedtestNistKatNistDRBGextendedEuclideanmodularInversemodularPowbitMasksignMaskmontgomeryReducesampleUniformRejection
std.crypto.ml_kem.assert
别名
别名目标 std.debug.assert
std.crypto.ml_kem.bitMask
函数
根据单个位值创建全一或全零掩码。 若 bit == 1,则返回全一(0xFF...FF);若 bit == 0,则返回全零。
fn bitMask(comptime T: type, bit: T) T
参数
T: type
bit: T
std.crypto.ml_kem.builtin
常量
std.crypto.ml_kem.cmov
函数
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
常量
usize
std.crypto.ml_kem.computeZetas
函数
fn computeZetas() [128]i16
std.crypto.ml_kem.crypto
别名
别名目标 std.crypto
std.crypto.ml_kem.csubq
函数
fn csubq(x: i16) i16
参数
x: i16
std.crypto.ml_kem.ctneq
函数
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
命名空间
std.crypto.ml_kem.d00.Kyber1024
类型
std.crypto.ml_kem.d00.Kyber512
类型
std.crypto.ml_kem.d00.Kyber768
类型
std.crypto.ml_kem.errors
别名
别名目标 std.crypto.errors
std.crypto.ml_kem.eta2
常量
u8
std.crypto.ml_kem.extendedEuclidean
类型函数
扩展欧几里得算法。 仅用于编译期值;重视正确性,不重视性能。
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
函数
fn feBarrettReduce(x: i16) i16
参数
x: i16
std.crypto.ml_kem.feToMont
函数
fn feToMont(x: i16) i16
参数
x: i16
std.crypto.ml_kem.h_length
常量
usize
std.crypto.ml_kem.inner_seed_length
常量
usize
std.crypto.ml_kem.inv_ntt_reductions
常量
std.crypto.ml_kem.invertMod
函数
fn invertMod(a: anytype, p: @TypeOf(a)) @TypeOf(a)
参数
p: @TypeOf(a)
std.crypto.ml_kem.Kyber
类型函数
fn Kyber(comptime p: Params) type
参数
p: Params
std.crypto.ml_kem.Kyber.ciphertext_length
常量
std.crypto.ml_kem.Kyber.encaps_seed_length
别名
确定性封装所用种子的长度(字节)。
std.crypto.ml_kem.Kyber.EncapsulatedSecret
容器
共享秘密及其封装(加密)表示。
字段
shared_secret: [shared_length]u8
ciphertext: [ciphertext_length]u8
std.crypto.ml_kem.Kyber.inner_plaintext_length
常量
usize
std.crypto.ml_kem.Kyber.innerKeyFromSeed
函数
fn innerKeyFromSeed(seed: [inner_seed_length]u8, pk: *InnerPk, sk: *InnerSk) void
参数
std.crypto.ml_kem.Kyber.InnerPk
容器
字段
std.crypto.ml_kem.Kyber.InnerPk.encoded_length
常量
std.crypto.ml_kem.Kyber.InnerPk.encrypt
函数
fn encrypt( pk: InnerPk, pt: *const [inner_plaintext_length]u8, seed: *const [32]u8, ) [ciphertext_length]u8
参数
std.crypto.ml_kem.Kyber.InnerPk.fromBytes
函数
fn fromBytes(buf: *const [encoded_length]u8) errors.NonCanonicalError!InnerPk
参数
buf: *const [encoded_length]u8
错误
- NonCanonical
std.crypto.ml_kem.Kyber.InnerPk.toBytes
函数
fn toBytes(pk: InnerPk) [encoded_length]u8
参数
pk: InnerPk
std.crypto.ml_kem.Kyber.InnerSk
容器
字段
sh: V
std.crypto.ml_kem.Kyber.InnerSk.decrypt
函数
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
常量
std.crypto.ml_kem.Kyber.InnerSk.fromBytes
函数
fn fromBytes(buf: *const [encoded_length]u8) InnerSk
参数
buf: *const [encoded_length]u8
std.crypto.ml_kem.Kyber.InnerSk.toBytes
函数
fn toBytes(sk: InnerSk) [encoded_length]u8
参数
sk: InnerSk
std.crypto.ml_kem.Kyber.KeyPair
容器
Kyber 密钥对。
字段
std.crypto.ml_kem.Kyber.KeyPair.generate
函数
生成新的随机密钥对。
pub fn generate(io: std.Io) KeyPair
参数
std.crypto.ml_kem.Kyber.KeyPair.generateDeterministic
函数
从密码学安全的秘密种子确定性地派生密钥对。
除测试外,应用程序通常应调用 generate(),而非此函数。
pub fn generateDeterministic(seed: [seed_length]u8) !KeyPair
参数
seed: [seed_length]u8
std.crypto.ml_kem.Kyber.M
类型
std.crypto.ml_kem.Kyber.name
常量
算法名称。
std.crypto.ml_kem.Kyber.PublicKey
容器
Kyber 公钥。
字段
std.crypto.ml_kem.Kyber.PublicKey.encaps
函数
使用随机字节生成封装给该公钥的共享秘密。
建议使用此函数,而非 encapsDeterministic。
pub fn encaps(pk: PublicKey, io: std.Io) EncapsulatedSecret
参数
std.crypto.ml_kem.Kyber.PublicKey.encapsDeterministic
函数
使用所提供的种子,生成针对公钥封装的共享秘密。
建议改为调用 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
函数
fn encapsInner(pk: PublicKey, m: *[inner_plaintext_length]u8) EncapsulatedSecret
参数
pk: PublicKey
m: *[inner_plaintext_length]u8
std.crypto.ml_kem.Kyber.PublicKey.encoded_length
别名
密钥序列化表示的大小,单位为字节。
std.crypto.ml_kem.Kyber.PublicKey.fromBytes
函数
从字节数组反序列化密钥。
pub fn fromBytes(buf: *const [encoded_length]u8) errors.NonCanonicalError!PublicKey
参数
buf: *const [encoded_length]u8
错误
- NonCanonical
std.crypto.ml_kem.Kyber.PublicKey.toBytes
函数
将密钥序列化为字节数组。
pub fn toBytes(pk: PublicKey) [encoded_length]u8
参数
pk: PublicKey
std.crypto.ml_kem.Kyber.SecretKey
容器
Kyber 秘密密钥。
字段
std.crypto.ml_kem.Kyber.SecretKey.decaps
函数
使用私钥解封装 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
常量
密钥序列化表示的大小,单位为字节。
usize
std.crypto.ml_kem.Kyber.SecretKey.fromBytes
函数
从字节数组反序列化密钥。
pub fn fromBytes(buf: *const [encoded_length]u8) errors.NonCanonicalError!SecretKey
参数
buf: *const [encoded_length]u8
错误
- NonCanonical
std.crypto.ml_kem.Kyber.SecretKey.toBytes
函数
将密钥序列化为字节数组。
pub fn toBytes(sk: SecretKey) [encoded_length]u8
参数
sk: SecretKey
std.crypto.ml_kem.Kyber.seed_length
常量
密钥生成种子的长度(字节)。
usize
std.crypto.ml_kem.Kyber.Self
别名
std.crypto.ml_kem.Kyber.V
类型
std.crypto.ml_kem.Mat
类型函数
fn Mat(comptime k: u8) type
参数
k: u8
字段
rows: [k]PolyVec(k)
std.crypto.ml_kem.Mat.Self
别名
std.crypto.ml_kem.Mat.transpose
函数
fn transpose(m: Self) Self
参数
m: Self
std.crypto.ml_kem.Mat.uniform
函数
fn uniform(seed: [32]u8, comptime transposed: bool) Self
参数
seed: [32]u8
transposed: bool
std.crypto.ml_kem.math
别名
别名目标 std.math
std.crypto.ml_kem.mem
别名
别名目标 std.mem
std.crypto.ml_kem.modes
常量
std.crypto.ml_kem.modQ32
函数
fn modQ32(x: i32) i16
参数
x: i32
std.crypto.ml_kem.modularInverse
函数
模逆:计算 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
函数
模幂:使用平方乘算法计算 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
函数
蒙哥马利约减:对于输入 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
函数
fn montReduce(x: i32) i16
参数
x: i32
std.crypto.ml_kem.N
常量
usize
std.crypto.ml_kem.nist
命名空间
std.crypto.ml_kem.nist.MLKem1024
类型
std.crypto.ml_kem.nist.MLKem512
类型
std.crypto.ml_kem.nist.MLKem768
类型
std.crypto.ml_kem.NistDRBG
容器
字段
key: [32]u8
v: [16]u8
std.crypto.ml_kem.NistDRBG.fill
函数
fn fill(g: *NistDRBG, out: []u8) void
参数
g: *NistDRBG
out: []u8
std.crypto.ml_kem.NistDRBG.incV
函数
fn incV(g: *NistDRBG) void
参数
g: *NistDRBG
std.crypto.ml_kem.NistDRBG.init
函数
fn init(seed: [48]u8) NistDRBG
参数
seed: [48]u8
std.crypto.ml_kem.NistDRBG.update
函数
fn update(g: *NistDRBG, pd: ?[48]u8) void
参数
g: *NistDRBG
pd: ?[48]u8
std.crypto.ml_kem.Params
容器
字段
name: []const u8
ml_kem: bool = false
k: u8
eta1: u8
du: u8
dv: u8
std.crypto.ml_kem.Poly
容器
字段
cs: [N]i16
std.crypto.ml_kem.Poly.add
函数
fn add(a: Poly, b: Poly) Poly
参数
std.crypto.ml_kem.Poly.barrettReduce
函数
fn barrettReduce(a: Poly) Poly
参数
a: Poly
std.crypto.ml_kem.Poly.compress
函数
fn compress(p: Poly, comptime d: u8) [compressedSize(d)]u8
参数
p: Poly
d: u8
std.crypto.ml_kem.Poly.compressedSize
函数
fn compressedSize(comptime d: u8) usize
参数
d: u8
std.crypto.ml_kem.Poly.decompress
函数
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
常量
std.crypto.ml_kem.Poly.fromBytes
函数
fn fromBytes(buf: *const [encoded_length]u8) Poly
参数
buf: *const [encoded_length]u8
std.crypto.ml_kem.Poly.invNTT
函数
fn invNTT(a: Poly) Poly
参数
a: Poly
std.crypto.ml_kem.Poly.mulHat
函数
fn mulHat(a: Poly, b: Poly) Poly
参数
std.crypto.ml_kem.Poly.noise
函数
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
函数
fn normalize(a: Poly) Poly
参数
a: Poly
std.crypto.ml_kem.Poly.ntt
函数
fn ntt(a: Poly) Poly
参数
a: Poly
std.crypto.ml_kem.Poly.sub
函数
fn sub(a: Poly, b: Poly) Poly
参数
std.crypto.ml_kem.Poly.toBytes
函数
fn toBytes(p: Poly) [encoded_length]u8
参数
p: Poly
std.crypto.ml_kem.Poly.toMont
函数
fn toMont(a: Poly) Poly
参数
a: Poly
std.crypto.ml_kem.Poly.uniform
函数
fn uniform(seed: [32]u8, x: u8, y: u8) Poly
参数
seed: [32]u8
x: u8
y: u8
std.crypto.ml_kem.Poly.zero
常量
Poly
std.crypto.ml_kem.PolyVec
类型函数
fn PolyVec(comptime k: u8) type
参数
k: u8
字段
ps: [k]Poly
std.crypto.ml_kem.PolyVec.add
函数
fn add(a: Self, b: Self) Self
参数
std.crypto.ml_kem.PolyVec.barrettReduce
函数
fn barrettReduce(v: Self) Self
参数
v: Self
std.crypto.ml_kem.PolyVec.compress
函数
fn compress(v: Self, comptime d: u8) [compressedSize(d)]u8
参数
v: Self
d: u8
std.crypto.ml_kem.PolyVec.compressedSize
函数
fn compressedSize(comptime d: u8) usize
参数
d: u8
std.crypto.ml_kem.PolyVec.decompress
函数
fn decompress(comptime d: u8, buf: *const [compressedSize(d)]u8) Self
参数
d: u8
buf: *const [compressedSize(d)]u8
std.crypto.ml_kem.PolyVec.dotHat
函数
fn dotHat(a: Self, b: Self) Poly
参数
std.crypto.ml_kem.PolyVec.encoded_length
常量
std.crypto.ml_kem.PolyVec.fromBytes
函数
从字节数组反序列化密钥。
fn fromBytes(buf: *const [encoded_length]u8) Self
参数
buf: *const [encoded_length]u8
std.crypto.ml_kem.PolyVec.invNTT
函数
fn invNTT(v: Self) Self
参数
v: Self
std.crypto.ml_kem.PolyVec.map
函数
对每个多项式应用一元运算
fn map(v: Self, comptime op: fn (Poly) Poly) Self
参数
std.crypto.ml_kem.PolyVec.mapBinary
函数
逐对应用二元运算
fn mapBinary(a: Self, b: Self, comptime op: fn (Poly, Poly) Poly) Self
参数
std.crypto.ml_kem.PolyVec.noise
函数
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
函数
fn normalize(v: Self) Self
参数
v: Self
std.crypto.ml_kem.PolyVec.ntt
函数
fn ntt(v: Self) Self
参数
v: Self
std.crypto.ml_kem.PolyVec.Self
别名
std.crypto.ml_kem.PolyVec.sub
函数
fn sub(a: Self, b: Self) Self
参数
std.crypto.ml_kem.PolyVec.toBytes
函数
将密钥序列化为字节数组。
fn toBytes(v: Self) [encoded_length]u8
参数
v: Self
std.crypto.ml_kem.Q
常量
i16
std.crypto.ml_kem.R
常量
i32
std.crypto.ml_kem.r_mod_q
常量
i32
std.crypto.ml_kem.r2_mod_q
常量
i32
std.crypto.ml_kem.r2_over_128
常量
i32
std.crypto.ml_kem.randPolyAbsLeqQ
函数
fn randPolyAbsLeqQ(rnd: anytype) Poly
std.crypto.ml_kem.randPolyNormalized
函数
fn randPolyNormalized(rnd: anytype) Poly
std.crypto.ml_kem.RndGen
别名
std.crypto.ml_kem.sampleUniformRejection
函数
使用 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
别名
别名目标 std.crypto.hash.sha3
std.crypto.ml_kem.signMask
函数
由有符号整数的符号位创建掩码。 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
别名
别名目标 std
std.crypto.ml_kem.testing
别名
别名目标 std.testing
std.crypto.ml_kem.testNistKat
函数
fn testNistKat(mode: type, hash: []const u8) !void
参数
mode: type
hash: []const u8
std.crypto.ml_kem.zeta
常量
i16
std.crypto.ml_kem.zetas
常量
源码
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;
}