PRNG下一位测试

Question

我想知道具体的PRNG是否满足下一位测试.

对PRNG的所有NIST统计测试是否都能保证通过下一位测试？或者有一个具体的算法来测试这一点？

Answer 1

我想知道一个特定的PRNG是否满足下位测试。

这就需要分析PRNG的设计。

对PRNG的所有NIST统计测试是否都能保证通过下一位测试？

不是的。NIST统计测试旨在测试RNG的实现。从设计的角度来判断PRNG是好的还是坏的，它们几乎毫无用处。关键的问题是，测试是在(P)RNG的输出上工作，而不是在它的设计上，在密码学中，假定攻击者可以使用它。完全有可能(而且可以是故意的，甚至是偶然的)一个设计或实现极其薄弱的RNG通过了测试。但是，可以得出一个明确的结论:如果RNG反复测试失败:它的设计或实现都是错误的。

是否有特定的算法来测试这一点？

我不知道有什么企图。它可能需要描述每个语法的PRNG，然后由一些复杂的算法来处理。这可以得出一些有用的结论，至少在某些时候是否定的，也许是肯定的，但语法和一些假设的限制很大。

Answer 2

造成混乱的原因可能有以下几点。从理论上讲，自从姚的工作以来，人们就知道下一个比特测试等同于伪随机数。非正式地说，序列发生器是伪随机的当且仅当没有多项式时间概率算法能够用严格大于1/2.的概率预测其下一个比特。

例如，请参见注记。

然而，这也有另一面。在密码，‘99，施瓦谷和沙米尔证明

..。令人惊讶的结果是，下一个比特测试的自然扩展，即使是在最简单的有偏置独立比特的情况下，也不再是通用的:我们构造了一个有偏置比特的源，其比特显然是依赖的，但这些比特中没有一个能以比偏差更大的概率来预测。为了克服这一困难，我们为随机(潜在不完美)随机源的任意模型开发了新的通用测试。