【密码学·采样】均匀模采样与中心二项分布

原创

Litt1eQ
Litt1eQ

Coder小Q

2026年10月16日 08:30
山东

在小说阅读器读本章

去阅读

在公众号小说中沉浸阅读

均匀模采样与中心二项分布

同一串随机比特，两个相反的采样任务

上一篇把安全证明写成了一册误差账本：一次采样离目标多远，要经过条件化、重试和多次查询，才会成为攻击者最终拥有的优势。本篇把视线移回这册账本的源头。程序收到的只是比特，而格密码真正需要的是带有特定概率规律的环元素和小噪声；两者都叫“采样”，要求却几乎相反。

第一条路径要在  中尽可能平坦地取值。没有哪个余数应该比另一个更常出现，因为后续代数通常把这些系数当作均匀元素。第二条路径则故意把概率挤向零：小数值经常出现，靠近边缘的数值越来越稀少。它们会成为秘密、误差或掩蔽量的一部分，宽度和相关性都会进入正确性与安全分析。

下图直接比较两种输入样本空间和对应的输出概率形状。范围拒绝删去不完整的尾段后，每个余数拥有同样多的原像；中心二项采样则把固定的  个比特按计数差聚合，因而在零附近拥有更多原像。输入看起来相同，输出规律却不能混用。

范围截断产生等高的余数概率，而比特计数差产生以零为中心的二项概率质量。

以下精确结论先假定输入是理想、独立的公平比特。这个前提不是措辞上的装饰：如果不同输出复用了同一段比特，即使每个系数单独看都完全正确，整段系数的联合分布仍可能已经改变。

合法余数为什么仍可能来自错误分布

先故意写错一行程序。读取  个比特得到

然后直接输出 。每个结果都落在合法范围  到 ，程序也不会崩溃；问题藏在每个余数拥有多少个原像。

余数  到  各自有两个原像，例如  来自  和 。余数  到  各自只有一个原像。因此前  个余数的单点概率为 ，其余余数的单点概率为 ，而目标均匀概率应当全部等于 。这条“ 比特再取模”的路径是为了暴露机制而故意构造的错误，不是 ML-KEM 的实际算法。

一般地，令比特源大小为 、模数  为正整数，并作带余除法

前  个余数各有  个原像，其余  个余数各有  个原像。直接取模得到的分布  与均匀分布  的统计距离为

附录会展开绝对值逐项求和。现在先看结果的含义：只要 ，偏差就不是“实现噪声”，而是由整数不能平均分组造成的精确概率差。对于 ，距离约为

这不是一个需要几百万样本才勉强看见的尾数。把重余数集合记为 ，直接取模与理想均匀下它的概率分别为

事件“输出落入 ”恰好取得上面的统计距离。攻击者甚至不需要记住每个余数，只要数一数输出落在分界线哪一侧。

一点取模偏差怎样进入整段系数

格密码通常不会只生成一个系数。假设用相互独立的新鲜候选生成  个系数，并令  表示其中落入重余数集合  的个数。在直接取模路径下， 服从参数

的二项分布；在理想均匀路径下，参数则是

两张计数分布的统计距离约为 。下图显示，单点上都合法的余数，放进一段独立系数后会形成明显不同的计数中心。攻击者看到一整段系数时，可以只计算 ，再根据它更靠近哪座峰作判断。

直接取模的单系数偏差在独立生成的系数段中形成可区分的计数分布。

这里必须分清上下两种界。因为  是完整系数向量的确定函数，数据处理性质说明，计数分布距离是完整向量距离的下界：只看这个粗粒度统计量已经能区分到 ，看完整向量不会更差。另一方面，若每个坐标独立，上一篇的逐坐标组合给出线性上界。因此  只是上界，也就是  与 1 取最小；它不是完整联合分布距离的精确等式。

如果坐标并不独立，就连“ 服从二项分布”这句话也失去依据。此时必须写出真实联合律，而不能把一个坐标的概率表机械地乘  次。后文会看到，比特复用正能制造这种边缘正确、联合错误的情形。

越界拒绝恢复了什么，又留下什么

直接取模的问题不是“取模”本身，而是每个余数分到的候选数不同。修复思路因此很直接：只保留一段能够平均分成  组的候选区间。

仍令 ，并要求 ，使接受区间非空。取

每轮使用新鲜独立比特，从  到  均匀抽取 ；若 ，丢掉它并重新抽取；若 ，输出 。在接受区间  中，每个余数恰好拥有  个原像，所以

分布修复是精确的。在上述独立输入前提下，单轮接受率 ，算法以概率  终止，平均需要  个候选；当  时，重试次数没有固定上限， 只是期望值；当  时，一个候选就能完成。若循环次数、时间或功耗暴露在观察面中，输出均匀也不自动抹掉这些痕迹。

高性能实现还会使用乘法缩放、宽字乘法和更精细的范围归约来减少浪费。Lemire 对无偏区间整数生成给出了通用实现背景与算法比较[1]，但“分布无偏”与“特定平台上的恒时、无溢出和无侧信道”仍是不同的证明义务。本篇只保留概率接口：接受区间必须使各目标值获得同样多的候选质量。

上半篇到这里解决了“怎样得到平坦余数”。另一条采样路径反而不想平坦：它要让零附近拥有最多概率。

两组比特相减，概率为什么向零聚集

取  个相互独立的公平比特，分成两组

并输出

每一组的比特计数都落在  到 ，所以  的支撑是  到 。真正解释峰形的办法，不是凭图说它“像钟”，而是把减法改写成一次计数。因为  仍是公平比特，

前两项一共是  个公平比特中 1 的个数。要使 ，这  个位置中必须恰有  个 1；能做到这一点的比特串共有  条，而总比特串数是 。于是

中间位置对应的比特排列最多，边缘位置只由极少数排列产生，概率自然向零聚集。这个分布称为中心二项分布（centered binomial distribution, CBD）；后文再次出现时只写“中心二项”。

支撑、方差与噪声宽度

对称性立即给出 。每个差  的方差为 ，独立相加得到

增大  会扩大支撑，也会把方差线性增大。下图同时画出  与  的精确概率，并与同一支撑上的均匀分布比较。二者都关于零对称、均值也都为零，但同支撑均匀分布的方差是

明显更宽。“范围一样”和“平均值一样”都不足以说明噪声采对了；安全性与失败概率使用的是整张概率表及其尾部，而不是两个摘要数字。

中心二项把更多质量放在零附近，同支撑均匀分布则把质量平均铺开。

还要避免另一个常见偷换：中心二项分布不是离散高斯，二者即使都对称、都在零附近呈峰形，也不能替代彼此。中心二项具有有限支撑，概率来自有限比特串的组合计数；离散高斯通常在所有整数点上都有非零质量，并由指数权重定义。特别是在格密码常见的小  下，不能借一句“中心极限定理”转移另一种分布的证明、参数或尾界。

单个系数正确，整个多项式仍可能错误

现在从一张正确的中心二项概率表生成两个相邻系数。正确做法为两个系数使用彼此独立的新鲜比特。若单系数概率记为 ，联合律是

再看一种有缺陷的实现：为节省读取，两个系数复用同一组  比特，于是 。它的联合律全部压在对角线上，

奇怪之处在于，无论只看  还是只看 ，边缘分布仍然恰好是 。单系数直方图、均值、方差和支撑都能通过检查；错误只在联合分布中出现。下图的左侧把质量铺在整个方格上，右侧则全部落到对角线。

两个系数的边缘分布相同，并不保证它们的联合分布相同。

两份联合律的统计距离可以化成

当  时，概率依次为  除以 ，所以距离为

也就是说，每个系数单独看都完全正确，两个系数放在一起却相差 。采样器的接口因此不能只写“返回一个 CBD 系数”；它还必须说明多次调用使用的新鲜性、独立性或允许的相关结构。

第 11 篇给出另一类、更强的四坐标反例：两条路径的四个单坐标边缘完全相同，联合分布的总变差却为 。那里的原因是使用了错误的代数映射，而不是复用比特；共同教训是，逐坐标检查不能认证联合采样器，也不能决定多坐标可见事件的概率。

展开整张概率表以后

本篇的数值来自有限空间的精确枚举。程序逐个计算  个候选的余数，使用有理数生成两张  二项概率表，按组合数列出  的中心二项概率，再枚举  的两系数联合律。所有归一化、均值、方差和统计距离都以分数检查；小数只用于绘图和阅读。

这种实验的价值是让错误无法藏在“看起来差不多”里。它能证明当前有限模型的概率恒等式，能检验实现是否复现这张有限概率表，也能给正文公式提供逐项核对。它不能凭几张直方图证明真实密码方案安全，更不能穷尽有限精度、溢出、编译器改写、缓存访问或电磁泄漏。

还应区分三种层次。第一层是本篇使用的理想独立均匀比特，它支持信息论上的精确等式。第二层是密码方案从扩展输出函数或伪随机函数得到的字节流，结论依赖计算假设。第三层是设备实际执行时留下的物理观察量，它们不属于输出概率表本身。把三层分开以后，“算法分布正确”和“实现没有泄漏”才不会被误写成同一句承诺。

回到 FIPS 203 的两个采样接口

FIPS 203 的 Algorithm 7 与 Algorithm 8 正好对应本篇两条路径[2]。Algorithm 7 从三个字节拆出两个 12 比特候选，只接受小于  的值，继续读取直到得到  个系数；它没有使用前文故意做错的直接取模。Algorithm 8 则把输入比特按参数  分组，通过两次比特计数之差生成  个中心二项系数。Kyber 3.02 已经给出这两个接口的设计历史[3]，当前规范边界仍以 FIPS 203 为准。

这里的“输入字节”在不同分析中有不同身份。XOF 与 PRF 的输出在相应安全假设下只要求与理想字节计算不可区分，不能因此把它们写成信息论上的独立均匀比特。规范算法说明的是怎样把字节映射成目标对象；方案安全证明还要说明产生这些字节的密码学过程；实现证明则要检查代码是否忠实执行映射。

2025 年 11 月公布的 FIPS 203 勘误规划没有改变 Algorithms 7 和 8 的采样接口。Almeida 等人的形式化工作针对当时的 ML-KEM 草案，分别建立了经典随机预言机模型中的安全论证，以及两个 ML-KEM-768 Jasmin 实现的功能等价与恒时证据[4]。最终 FIPS 203 的附录 C.2 记录了草案之后的密钥生成域分离和矩阵索引调整，因此引用这项工作时还须限定所验证的规范版本。这些证据互相衔接，却不能互相替代。尤其是，输出分布正确不代表物理轨迹消失，时间和功耗仍需在具体设备和攻击模型下单独分析。

Peng 与 Kuhn 对 Cortex-M4 上 Kyber768 二项采样器的自适应模板攻击表明，物理功耗可以成为额外观察面[5]。这项结果针对特定实现、平台和测量条件，不能概括为所有 ML-KEM 实现都存在同一攻击，也不是只看公开协议输出就能完成的攻击。它提醒我们的范围很明确：一张正确的数学概率表是必要条件，不是物理侧信道安全的终点。

结论

随机比特进入格密码以后，不是“足够随机”就可以直接交差。均匀模采样要求每个余数获得同样多的候选质量；若候选空间不能整除模数，直接取模会产生精确可算的偏差，多坐标输出还会把它变成更强的区分信号。范围拒绝通过删去无法平均分组的尾部恢复精确均匀，却同时引入可变候选消耗，输出分布与执行痕迹必须分开分析。

中心二项走的是另一条路：它利用  个比特的组合计数主动制造中心峰。支撑、均值和方差只能描述这张概率表的一部分；更换成同支撑均匀分布会改变噪声宽度，复用比特则能在边缘完全正确时把联合分布推到另一种世界。采样接口真正承诺的是完整目标律以及多次调用之间的关系。

这两条路径都能从公平比特得到精确的目标分布，但消耗比特的方式不同。中心二项使用固定的  个比特，通过组合计数得到目标概率。均匀模采样则在接受区间内保证等量原像，并允许没有固定上限的重试；当  时，单点概率  无法写成 ，所以任何最多读取固定  个公平比特且必定输出的确定性算法都无法精确实现它。下一篇《逆累积分布、CDT 与 Knuth-Yao 决策树》将讨论更一般的目标概率：当没有现成的组合计数公式或范围拒绝结构时，公平比特又该怎样沿着概率边界找到正确出口？

附录：直接取模的距离为什么等于这个分数

设  为正整数，，。直接取模分布记为 ，均匀分布记为 。若 ，每个余数恰有  个原像，故 ，距离为零。以下先考虑 。对 ，

对 ，

因此

重集合  下，

所以  不仅给出一个区分事件，而且恰好取得统计距离。连同  的情形，距离公式对全部  都成立。

附录：中心二项公式怎样从比特计数得到

令  为独立公平比特，并设 。则  仍为独立公平比特，且

记前两个和的总和为 ，则 ，。所以

由二项式定理，

故概率归一化。又因为 、，平移不改变方差，

也可以直接从  看出这些矩：每项均值为零、方差为 ，不同项独立，交叉协方差为零。

附录：复用比特为何不改变边缘却改变联合分布

设单系数概率为 。独立联合律  与复用联合律  分别为

对任意 ，

另一侧边缘同理，因此两份联合律的两个边缘都相同。计算统计距离时，把对角线与非对角线分开。非对角线上 ，绝对差的总和为

对角线上 ，绝对差总和也是

两部分相加后再除以二，得到

这个式子也有直观含义：独立取样恰好落到同一个值的概率是 ；其余原本应该出现在非对角线上的质量，在复用实现中全部被搬到了对角线。

快乐的时光过得特别快，又到了说再见的时候了，咱们下次再见～

参考文献

1. Lemire, Daniel. 2019. “Fast Random Integer Generation in an Interval.” ACM Transactions on Modeling and Computer Simulation, 29 (1), 1–12. https://doi.org/10.1145/3230636.
2. National Institute of Standards and Technology. 2024. Module-Lattice-Based Key-Encapsulation Mechanism Standard. FIPS 203, U.S. Department of Commerce. https://doi.org/10.6028/NIST.FIPS.203.
3. Avanzi, Roberto, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, and Damien Stehlé. 2021. CRYSTALS-Kyber: Algorithm Specifications and Supporting Documentation, Version 3.02. CRYSTALS team. https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf.
4. Almeida, José Bacelar, Santiago Arranz Olmos, Manuel Barbosa, Gilles Barthe, François Dupressoir, Benjamin Grégoire, Vincent Laporte, Jean-Christophe Léchenet, Cameron Low, Tiago Oliveira, Hugo Pacheco, Miguel Quaresma, Peter Schwabe, and Pierre-Yves Strub. 2024. “Formally Verifying Kyber: Episode v: Machine-Checked IND-CCA Security and Correctness of ML-KEM in EasyCrypt.” Advances in Cryptology – CRYPTO 2024, Lecture Notes in Computer Science vol. 14921, 384–421, Springer. https://doi.org/10.1007/978-3-031-68379-4\_12.
5. Peng, Eric Chun-Yu, and Markus G. Kuhn. 2025. “Adaptive Template Attacks on the Kyber Binomial Sampler.” IACR Transactions on Cryptographic Hardware and Embedded Systems, 2025 (3), 470–492. https://doi.org/10.46586/tches.v2025.i3.470-492.