如何检查随机数发生器的随机性？

Question

假设我有一张智能卡，它在接收命令时返回一个8字节(例如)随机值。问题是：

如何检查这个值是否真的是随机的？(我没有任何途径获得实施和机制。我只看到一个8字节的十六进制数。)

在另一个世界里，有没有办法根据输出来检查随机发电机输出的随机性？或者，唯一的方法是分析生成器的实现和机制。

Answer 1

NIST在NIST特别出版物.800-22中定义了一组广泛的统计测试，用于验证随机性的来源。

然而，虽然这足以断言RNG没有明显损坏，但仅仅断言RNG是“好的”是不够的。正是由于RNGs的本质，非常微妙的缺陷才会导致它的破坏。检查RNG的健壮性的唯一正确方法是查看实现。

Answer 2

真正的“随机性”可以归结为样本中的熵量。正如其他人所指出的，在黑匣子测试中，熵多少是不可能的。一个良好的调节功能和一个简单的输入，很少的信息，可以通过统计检验。因此，测试只能指出，在产生数据的方式上，是否存在一些固有的统计缺陷，它们不能真正证实它们是不可预测的。

在评估RNG的随机性、不可预测性或熵时，有几个要素是重要的：

1. 您需要确定是使用活熵源的真正的RNG，还是具有初始种子的DRNG (或两者的组合)。
2. 如果有活噪声源，您肯定需要检查噪声(熵)源的实现，以及底层理论。对此采用了物理或随机模型。
3. 当您对上述RNG生成的输出进行统计测试时，需要对在应用条件/压缩函数之前收集的数据进行测试，以便清楚地了解您正在处理的熵的真实数量。
4. 如果RNG不是真正的RNG，这意味着您正在查看确定性RNG，则需要对DRNG算法实现进行验证。这一项可以用测试向量来完成。
5. 最后，对于没有活熵源的DRNG，需要对初始种子质量进行评估。如果种子来自真正的RNG，那么上面的1-3就适用了.

RNG评价近年来受到越来越多的关注，标准也越来越严格。您可以查看NISTSP800-90A/B/C系列，以便很好地概述RNG设计，特别是SP800-90B (仍在起草)用于熵源评估。BSI在has 20/31中也有指导方针，说明如何评估RNGs。

最后，正如已经指出的，NIST的STS800-22a是一个很好的测试套件。还有BSI的as 20/31测试套件，以及Dieharder测试套件。

Answer 3

这是不可能的。这是不可能的，以验证一个所谓的随机生成器的输出是足够随机的密码学。(可以验证它对于诸如Monte数值方法之类的应用来说是足够随机的，但是不能，比如说，生成一个密码密钥。)

存在密码安全伪随机数发生器，即具有确定性但与真正随机序列无法区分的随机数生成器。我们不知道如何区分CSPRNG的输出和真正的随机序列:给定CSPRNG输出的一部分，我们不知道如何重建我们没有得到的输出。

(我们实际上不能从数学上证明CSPRNG的存在，但是有一些CSPRNG是建立在密码原语(如AES和SHA-2 )上的，它们是CSPRNG，假设AES适合从加密算法中导出加密算法，而SHA-2是一个密码散列函数。)

因为CSPRNG是确定性的，所以如果您知道它的初始状态，就知道它的输出；更普遍地说，如果您知道它的内部状态，那么您就知道所有后续的输出。因此，只有当对手不知道内部状态时，CSPRNG才是生成密码密钥和其他随机值的合适方法。

其内部状态为敌手所知的CSPRNG (不适用于密码学)与CSPRNG的内部状态在智能卡外不为已知的CSPRNG(适用于加密)是不可区分的。因此，仅从输出中测试RNG的质量是不可能的。从输出中你能看到的就是发现一些严重的缺陷，但并不是所有严重的缺陷。

为了验证RNG是否完成了它的工作，有必要查看内部。这分为两部分：

• 验证CSPRNG使用适当的算法并正确实现。
• 验证CSPRNG是从对手不知道的材料中播种的。

(仅基于物理过程的RNG几乎总是具有可检测的偏差，因此物理RNG不是直接使用，而是作为熵输入(即种子)输入CSPRNG)。

CSPRNG实现通过检查源代码、检查该算法是否是一个好的算法( NIST SP 800-90A等标准中的算法通常更受欢迎，甚至强制执行)，并进行一些测试来检测实现错误，例如将结果存储在错误的地址。

RNG的种子是更微妙的验证。有些系统包括“真正的随机数发生器”，即基于不可预测的物理过程(如放射性衰变或混沌振荡器)返回不可预测比特的硬件。通过统计测试验证这些结果，这些测试表明TRNG的输出具有足够的熵熵。

请注意，TRNG实际上可能不是“真正的随机”：它可能有偏见。重要的是，它具有足够的随机性，以便正确预测其下一个输出的概率是如此之低，以至于对手将无法作出明智的猜测。这些偏差是将CSPRNG应用于TRNG输出的原因:使用密码“混合”函数将可观察的相关性(例如，如果位为0，则下一个比特也有52%的可能性也为0)转换为无法计算的关联。

还可以通过使用一个秘密值来一劳永逸地播种CSPRNG来生成RNG。这是可行的，只有您确信PRNG的内部状态不会泄漏。种子值本身必须是随机生成的，最终来自某种形式的TRNG；但是这样，TRNG可以在工厂中，而不是在运行RNG的设备中。

作为智能卡的购买者，您无法查看智能卡的内部功能。(无法查看内部是智能卡的一个重要属性。)然而，您使用的卡可能已由安全实验室评估。有一些标准可以评估智能卡的安全性，比如共同标准 保护剖面。您可以检查您的卡是否是认证。CC并不是唯一这样的认证；信用卡公司，如Visa和Mastercard都有自己的认证流程。如果这张卡已经被评估过，你的供应商应该指向你的证书-这是一个营销论点。有许多智能卡认证，它们测试不同的东西，所以准确地检查证书的保证。您不会确切地了解RNG是如何工作的(这通常是一个交易回路)，但是您会知道，一个安全实验室对它进行了调查，没有发现任何缺陷。