通过TestU01的BigCrush测试的PRNG是否具备密码学安全性？

问题描述 #

我在阅读O'Neill关于置换同余生成器（Permuted Congruential Generators）系列的论文时了解到，输入状态为88位的LCG可通过TestU01中严格的BigCrush测试套件。我想询问：如果这类LCG通过了BigCrush测试，为什么不适合用于密码学场景？泛化来说，是否所有通过BigCrush测试的伪随机数生成器（PRNG）都可适用于密码学领域？

为什么通过BigCrush的LCG不适合密码学场景 #

首先要明确TestU01套件的BigCrush测试的核心定位：它仅验证PRNG输出序列的统计随机性，只会检测序列是否存在分布不均、局部相关性、模式重复等统计学层面的偏差，完全不覆盖密码学场景要求的核心属性——不可预测性。
88位状态的LCG（线性同余生成器）本身构造极其简单，迭代公式为next_state = (multiplier * current_state + increment) mod modulus，这类生成器没有任何抵御状态还原攻击的设计：攻击者只需要拿到少量连续的LCG输出值，就能通过数学推导直接反推出完整的内部状态，之后的所有输出都可以被100%准确预测。这种可被完全预测的特性，直接不符合密码学场景对随机数的基本安全要求。

是否所有通过BigCrush的PRNG都可用于密码学领域 #

答案是否定的，通过BigCrush远不能作为PRNG可用于密码学场景的判断标准，核心原因如下：

• 统计无偏只是密码学安全伪随机数生成器（CSPRNG）的必要非充分条件。CSPRNG除了要满足统计随机性外，还需要满足不可预测性、前向保密性、抵御状态泄露攻击等多重安全属性，这些都不在BigCrush的测试范围内。
• 绝大多数非密码学PRNG的设计目标是高吞吐、低延迟，为了性能会大幅简化内部结构，哪怕能通过所有统计随机性测试，也普遍存在可被逆向还原状态的问题。比如广泛使用的梅森旋转算法MT19937同样可以轻松通过BigCrush测试，但攻击者只要拿到624个连续的32位输出，就能完整还原其内部状态，完全不满足密码学安全要求。

内容的提问来源于stack exchange，提问作者Assassinos