如何测试随机数（RNG）

RNG 分析的未来

你怎么知道某事是否真的是随机的？在测试随机数生成器 (RNG) 的随机性时，您很快就会陷入“真的是随机的”的困境。作为寻找模式的生物，我们自然会不断地寻找模式。像许多事情一样，随机性各不相同。大多数时候，伪随机数生成器 (PRNG) 基本上是通过大量非随机过程来创建随机性。

你怎么知道某事是随机的？

“111111”是随机的吗？还是“0100100101001011110111010”？很难说。为什么？因为一旦你开始定义随机参数，你就失去了随机性。

科学家和程序员想出的最好方法是创建一系列测试。存在大量测试和许多测试套件。流行的测试包括NIST RNG 测试套件、Dieharder 测试套件 [8]、Knuth 测试、Crypt-x 测试等等。RNG 有各种形状和大小，因此您可以想象为所有不同类型的随机生成器编排测试是很困难的。

有两个阶段来测试随机数生成器过程。首先，您需要一个无法像天气一样猜测的熵源[1]。其次，您需要一种确定性算法来将种子扩展为用于密钥等的大量序列。测试通常从检查熵开始。

初步 RNG 测试

当你试图定义什么是随机的时，你遇到的第一个挑战是几乎任何东西都可以是随机的。

如上所示，几乎不可能准确地证明一个数字序列是随机的。生成具有一百万个“0”的序列可能是非常随机的，但不是很理想。根据逻辑上看起来随机的东西很容易建立相关性，但这真的是随机的吗？很难说。幸运的是，有很多测试可以给你一个很好的随机性估计。

有偏见的测试

您要做的第一件事是通过有偏差的测试对熵的来源进行测试。就像上图一样，您不希望您的数字偏向或偏向 0 或 1。因此，为了解决这个问题，一位名叫 John von Neumann 的非常著名的数学家设计了一种偏斜校正算法。这种歪斜校正过程非常简单，但也非常有效。

它基于抛硬币，因为只有两个变量“1”和“0”。总输出应该大致相等的数量 1 和 0。为了保持这个相等的比率，歪斜校正算法每两次投掷并比较它们。如果这对中的两位相同（即 00 或 11），则丢弃这两位。如果这两个位不同（即 01 或 10），则第一个位被添加到已处理的位流中。

不利的一面是您会丢失大量随机数据 [8]。当源已经不偏斜时，校正也将采用随机数据。但话又说回来，这只是分析熵来源的基本测试。下一步是评估确定性随机数生成器，它将放大大量数字中的种子数。

视觉测试

确定随机数生成器质量的一种快速简便的方法是创建一个快速的视觉测试。人脑非常擅长识别模式。视觉效果可以为您提供出色的快照测试，以查看您在通过电子表格和数字挖掘时可能会错过的一般模式。“随机游走”是一种用于可视化随机性和模拟的常用技术。使用位生成也是另一种发现模式的方法，这些模式通过简单地查看数字序列是看不到的。

信息熵测试

随机数生成器非常注重产生大的可能结果。这就是信息熵发挥作用的地方。在随机性中，结果的数量是固定的，信息熵是每个单独结果的概率[7]。每一位信息中可能存在的变量越多，根据您已经看到的位来预测下一位将是什么就越困难。

上图显示了数据中的低信息熵水平占理论最大值的百分比。当您真正想要的是等概率时（见下图），您不希望某些值有更多可能的结果，例如“A”50%，概率。在大多数情况下，高水平的信息熵表明数据是随机的，而低水平的信息熵表明数据不是。

在考虑所有结果时，信息熵不仅仅是事件所涵盖的平均信息量。这也是您可以将多少信息打包成比特。你想创造一个所有结果都同样可能的环境。

Linux 甚至有一条错误消息告诉您，如果不按一堆键来创建更多熵，您的计算机将无法继续运行 [7]。上图中描述的消息是程序收集熵的一种非常常见的方式。熵的来源并不是唯一重要的因素——值的大小和范围也是重要的考虑因素。这一切都归结为同一个概念，即需要一个熵阈值才能产生真正的随机性。

NIST 测试套件

您可以在 RNG 上运行几乎无限数量的统计测试。每个测试都侧重于检测不被认为是随机的或从随机数字序列中预期的东西。由于非随机性的定义是检测模式，并且模式可以以无数种方式变化和不同，因此没有确定的方法可以考虑一组测试来证明随机性。

美国国家标准与技术研究院 (NIST)为测试 RNG 提供了非常有用的指南。NIST 测试是最流行和范围最广的。

频率（单比特）统计

当生成 0 和 1 的随机数位时，对于真正的随机序列，它们之间的比率通常是 1:1。为了复制这个过程，我们需要检查作为块的数字流。

对于每个块，计算以查看 1 和 0 的比率是否与真正随机序列一样接近 0.5。如果比率太小，则意味着比率关闭（1 太多）。非常基本的测试，如果该块容易失败，那么它可能会失败许多其他测试。

频率（块）统计

就像频率（单比特）测试一样，该测试旨在查看生成的 0 和 1 的数量是否与从真正随机源生成的数量相同 [5]。它的工作方式虽然不同。该测试将数字流作为一系列块。然后将每个块划分为子块。然后分析每个子块的最佳 1 和 0 比率，该比率接近预期的真正随机的 1 和 0 比率。

如果您问自己真正的随机数生成器是什么样的，那就别无所求。这是一个基于放射性衰变的真正随机数生成器[4]。

分析子块后，计算比率值，如果比率低于 0.5，则该块未通过测试。这是一种对您的位进行微扫描以查找差异的方法。请记住，一个好的随机数生成器也会生成看起来不随机的块，因此我们预计某些块会通过测试。（事实上​​，如果所有块都通过了测试，我们应该怀疑。

测试“运行”

RNG 产生一个比特流（1 和 0）。“运行测试”将流分解为可识别的模式，并计算它是否类似于真正随机的比特流。运行由流中的相同位组成，例如 0000 或 111111111。

此测试的重点是总结序列中的总运行次数。该测试检查从 0→1 或 1→0 转换的位数。这些是序列中的“运行”。运行用于评估“P 值”。

这个 P 值是一个块中预期的运行次数。当 P 值太小时，块无法通过测试，这意味着与真正随机“运行”数的结果相比，块中的运行次数更少（或更多）。

这个测试需要一个频率测试来计算初始变量，这对于许多其他测试也是如此。没有一种 RNG 测试适合所有测试，这就是为什么大多数测试都包含在套件中的原因。它们通常耦合在一起以最大限度地保证随机性。

块测试中最长的一次运行

该测试侧重于 M 位块。正如上面所见，这个测试计算最长运行的长度，然后将其与您对真正随机生成器最长运行的期望进行比较 [5]。

二元矩阵秩检验

二进制测试用于分析随机数流矩阵中的向量模式。让我把它分解成更容易理解的术语。该测试的目的是在随机比特流的片段中找到线性相关性 [5]。它们是您在没有矩阵的情况下无法看到的模式。

线性相关意味着输出在同一条线上。有一个线性模式。二进制矩阵使用二进制矩阵执行此操作。这基本上是随机比特流的混合，看看是否有任何特定的模式。

非重叠模板匹配测试

该测试对寻找非周期性模式感兴趣 [5]。那是一种非周期性的模式。简而言之，这个测试基本上是在寻找可能以有趣的方式重叠的模式，如下图：

非周期性的原型集（来源 Wikipedia）

测试过程基本上是通过一个 m 位窗口并试图找到模式 [5]。如果没有找到模式，它会移动到下一位并重复。如果找到了一个模式，那么如果在找到的模式之后继续测试该位。

可证明真实的未来 RNG 测试

NIST 概述了多种不同的测试，实际上它们概述了超过 14 种，您可以在此处阅读更多信息。我们只介绍了其中的 6 个，作者认为它们特别有趣。RNG，即使是真正的 RNG，也不太可能通过所有测试。事实上，如果他们能够通过所有测试，那可能会有点可疑，因为 NIST 测试旨在分析多个向量中的输出，其中许多向量重叠。

这些类型的随机性测试的下一代形式是什么？进入机器学习 (ML)。机器学习正在改变我们现在所做的几乎所有事情。它可以了解您喜欢什么以及何时需要某些东西——机器学习可以在多大程度上渗透到我们的生活中仍然是未知数。我认为机器学习非常适合随机性分析，毕竟机器学习就是检测模式，高质量的 RNG 不应该有任何明显的模式。

这就是我们使用机器学习分析变形算法的 RNG 输出的原因。理论上，高质量的 RNG 不会生成模式。因此，我们能够检测到异常或明显模式的越少，我们的 RNG 性能就越好。现在判断这种方法是否会优于 NIST 测试还为时过早，但如果确实如此，您肯定会从我们这里看到更多关于它的信息。