伪随机数和真正随机数有何不同以及这为什么重要？

Question 1

让我们玩一些计算机扑克游戏，只有你、我和一个我们都信任的服务器。服务器使用伪随机数生成器，在我们玩之前用 32 位种子初始化该生成器。因此，大约有 40 亿种可能的牌组。

我手里有五张牌——显然我们不是在玩德州扑克。假设发牌时，一张给我，一张给你，一张给我，一张给你，依此类推。所以我有第一、第三、第五、第七和第九张牌。

之前，我运行了伪随机数生成器四十亿次，每个种子运行一次，并将为每个种子生成的第一张牌写进数据库。假设我的第一张牌是黑桃皇后。在每 52 副可能的牌中，只有一副会以黑桃皇后作为第一张牌，所以我们将可能的牌组从四十亿减少到大约 8000 万副左右。

假设我的第二张牌是红桃三。现在我使用产生黑桃皇后的 8000 万个种子作为第一个数字，再运行我的 RNG 8000 万次。这需要我几秒钟的时间。我记下所有产生红桃三作为第三张牌（我手中的第二张牌）的牌组。这又只占牌组的 2% 左右，所以现在我们只剩下 200 万副牌了。

假设我手中的第三张牌是梅花 7。我的数据库里有 200 万个种子，它们会发出我的两张牌；我又运行了 RNG 200 万次，找出了 2% 的牌组，它们会发出梅花 7 作为第三张牌，这样我们就只剩下 4 万副牌组了。

你看这是怎么回事。我再运行 RNG 40000 次，找到产生第四张牌的所有种子，这样我们就得到了 800 副牌，然后再运行 800 次，得到产生第五张牌的约 20 副种子，现在我只需生成这 20 副牌，我就知道你手中有 20 种可能的手牌之一。此外，我对接下来要抽什么牌有了很好的了解。

现在你明白为什么真正的随机性很重要了吗？你描述它的方式是，你认为分配很重要，但是分布并不能使过程随机化。 不可预测性是什么让过程变得随机。

更新

根据这些评论（由于其不具建设性，现已被删除），至少有 0.3% 的读者对我的观点感到困惑。当人们反驳我没有提出的观点，或者更糟的是，争论为了我指出做过假设我没有犯这些错误，那么我知道我需要更清楚、更仔细地解释。

这个词似乎特别容易让人混淆分配所以我想仔细地指出用法。

当前的问题是：

伪随机数和真正随机数有何不同？
为什么这种差异很重要？
这些差异是否与 PRNG 的输出分布有关？

让我们首先考虑完美的生成一副随机扑克牌的方法。然后我们将看到生成扑克牌的其他技术有何不同，以及是否可以利用这种差异。

首先假设我们有一个标记为的魔盒TRNG。我们给它的输入是一个大于或等于 1 的整数 n，它的输出是一个介于 1 和 n 之间的真正随机数（包括 1 和 n）。魔盒的输出是完全不可预测（当给定一个非 1 的数字时）并且 1 到 n 之间的任何数字都与另一个数字一样可能；也就是说分配是制服（我们还可以执行其他更高级的随机性统计检查；我忽略了这一点，因为它与我的论点无关。根据假设，TRNG 在统计上是完全随机的。）

我们从一副未洗过的牌开始。我们要求盒子给出一个介于 1 到 52 之间的数字——也就是TRNG(52)。无论它给出什么数字，我们都从已排序的牌堆中数出那么多张牌并取出那张牌。它将成为洗过的牌堆中的第一张牌。然后我们要求TRNG(51)并执行相同操作以选择第二张牌，依此类推。

另一种看待它的方式是：有 52！= 52 x 51 x 50 ... x 2 x 1 个可能的牌组，大约是 2 ²²⁶。我们完全随机地选择了其中之一。

现在我们发牌。当我看我的牌时，我有完全不知道你有什么牌。（除了你没有我拥有的任何牌这一明显事实之外。）它们可以是任何牌，概率相同。

所以，让我确保我解释清楚了这一点。我们有均匀分布每个输出的TRNG(n)概率为 1/n，每个输出都从 1 到 n 中选择一个数字。此外，这个过程的结果是我们以 1/52! 的概率从 52! 副牌中选择了一副，因此分布一组可能的牌组是还制服。

好的。

现在假设我们有一个较小的魔盒，标记为PRNG。在使用它之前，它必须是播种具有 32 位无符号数。

在旁边：为什么是 32？难道不能用 64 位、256 位或 10000 位数字作为种子吗？当然。但 (1) 实际上，大多数现成的 PRNG 都用 32 位数字作为种子，并且 (2) 如果您有 10000 位随机性来制作种子，那您为什么还要使用 PRNG？您已经有 10000 位随机性的来源了！

无论如何，回到 PRNG 的工作原理：在播种之后，你可以像使用一样使用它TRNG。也就是说，你给它传递一个数字 n，它会返回一个介于 1 和 n 之间的数字（包括 1 和 n）。此外，产出的分布大致均匀也就是说，当我们要求PRNG一个 1 到 6 之间的数字时，无论种子是什么，我们大约有六分之一的概率得到 1、2、3、4、5 或 6 。

我想强调这一点几次，因为这似乎是让某些评论者感到困惑的一点。PRNG 的分布至少在两个方面是均匀的。首先，假设我们选择任何特定的种子。我们预计该序列PRNG(6), PRNG(6), PRNG(6)...一百万次会产生 1 到 6 之间的均匀分布数字。其次，如果我们选择一百万个不同的种子并调用PRNG(6) 一次对于每个种子，我们再次期望数字从 1 到 6 均匀分布。PRNG 在这两种操作中的一致性与我所描述的攻击无关。

这个过程被称为伪随机因为盒子的行为实际上是完全确定的；它根据种子从 2 ³²种可能的行为中选择一个。也就是说，一旦播种，PRNG(6), PRNG(6), PRNG(6), ... 就会产生一个顺序具有均匀分布的数字，但该序列是完全由种子决定。对于给定的调用序列，例如 PRNG(52)、PRNG(51) 等，只有 2 ³²个可能的序列。种子基本上会选择我们得到哪一个。

为了生成一副牌，服务器现在会生成一个种子。（怎么做？我们会回到这一点。）然后他们调用PRNG(52)，PRNG(51)依此类推来生成一副牌，与之前类似。

该系统很容易受到我所描述的攻击。要攻击服务器，我们首先要提前用 0 播种我们自己的盒子副本，然后要求PRNG(52)并记下它。然后我们用 1 重新播种，要求PRNG(52)，并记下它，一直到 2 ³² -1。

现在，使用 PRNG 生成牌组的扑克服务器必须以某种方式生成种子。他们如何做并不重要。他们可以打电话TRNG(2^32)来获得一个真正随机的种子。或者他们可以把当前时间作为种子，这几乎根本不是随机的；我知道现在几点，你也知道。我攻击的重点是，这并不重要，因为我有我的数据库。当我看到第一张牌时，我可以排除 98% 的可能种子。当我看到第二张牌时，我可以再排除 98%，依此类推，直到最后我可以确定少数可能的种子，并且很有可能知道你手中有什么。

现在，我想再次强调，这里的假设是如果我们拨打PRNG(6)一百万次电话，我们大约有六分之一的概率能接到每个号码. 该分布（或多或少）制服，和如果你只关心分布的均匀性，没关系。这个问题的重点是除了分布以外PRNG(6)我们还关心其他的事情吗？答案是是的.我们关心不可预测性也一样。

另一个看待这个问题的方式是，尽管一百万次呼叫的分配PRNG(6)可能没问题，因为 PRNG 仅从 2 ^{32 种}可能的行为中进行选择，所以它无法生成所有可能的牌组。 它只能生成2 ^{226个可能牌组中的 2}^{32 个}，这是很小的一部分。因此分布在所有牌组上非常糟糕。但同样，这里的基本攻击是基于我们能够成功预测PRNG从其输出的一小部分样本中可以预测其过去和未来的行为。

让我再说三四遍，确保大家能理解。这里有三个分布。首先，产生随机 32 位种子的过程的分布。它可以是完全随机的、不可预测的和均匀的，攻击仍将有效。第二，一百万次调用的分布PRNG(6)。这可以完全均匀，攻击仍然有效。第三，我描述的伪随机过程选择的牌组分布。这种分布非常差；只有一小部分 IRL 可能的牌组可能被选中。攻击取决于可预测性PRNG 的行为基于其输出的部分知识。

补充：这种攻击要求攻击者知道或能够猜测 PRNG 使用的确切算法。这是否现实是一个悬而未决的问题。然而，在设计安全系统时，你必须将其设计为能够抵御攻击，即使攻击者知道程序中的所有算法换句话说：安全系统中必须保密才能保证系统安全的部分称为“密钥”。如果您的系统安全性依赖于您使用的算法是否保密，那么你的密钥包含这些算法. 这是一个极其处于弱势地位！

继续。

现在让我们假设我们有第三个魔盒，标记为CPRNG。它是的加密强度版本PRNG。它需要 256 位种子，而不是 32 位种子。它与共享PRNG属性，即种子从 2 ²⁵⁶种可能的行为中选择一种。与我们的其他机器一样，它具有大量调用以CPRNG(n)产生 1 到 n 之间均匀分布结果的属性：每个调用发生 1/n 次。我们可以对它进行攻击吗？

我们最初的攻击需要我们存储从种子到的2 ^{32 个}PRNG(52)映射。但 2 ²⁵⁶是一个大得多的数字；运行CPRNG(52)这么多次并存储结果是完全不可行的。

但假设有一些其他有没有办法获取值CPRNG(52)并从中推断出有关种子的事实？到目前为止，我们一直很笨，只是强行计算所有可能的组合。我们能否查看魔盒内部，弄清楚它的工作原理，并根据输出推断出有关种子的事实？

不是。细节太复杂，无法解释，但 CPRNG 设计得很巧妙，无法推断任何CPRNG(52)关于来自第一个输出的种子的有用事实任何输出的子集，无论多大。

好的，现在让我们假设服务器正在使用CPRNG来生成牌组。它需要一个 256 位种子。它如何选择这个种子？如果它选择攻击者可以预测的任何值然后突然攻击又变得可行。如果我们能确定在²²⁵⁶个可能的种子中，只有 40 亿个可能被服务器选中，那么我们恢复营业我们可以再次发起这种攻击，只需关注可能生成的少量种子。

因此，服务器应该做一些工作来确保 256 位数字均匀分布——也就是说，每个可能的种子都以 1/2 ²⁵⁶的概率被选中。基本上，服务器应该调用TRNG(2^256)-1来生成种子CPRNG。

如果我可以入侵服务器并查看选择了什么种子，结果会怎样？在这种情况下，攻击者知道 CPRNG 的完整过去和未来。服务器的作者需要警惕这种攻击！（当然，如果我能成功发动这种攻击，那么我可能也可以直接将钱转入我的银行账户，所以这可能没那么有趣。重点是：种子必须是一个难以猜测的秘密，而一个真正随机的 256 位数字是很难猜到的。）

回到我之前关于纵深防御的观点：256 位种子是钥匙到这个安全系统。CPRNG 的理念是系统是安全的只要密钥是安全的；即使算法的所有其他事实都已知，只要你能保守密钥的秘密，对手的牌就是不可预测的。

好的，所以种子应该是秘密的并且分布均匀，因为如果不是，我们就可以发起攻击。我们假设的输出分布CPRNG(n)是均匀的。所有可能的牌组的分布情况如何？

您可能会说：CPRNG 输出的可能序列有 2 ²⁵⁶个，但可能的牌组只有 2 ²²⁶个。因此，可能的序列比牌组多，所以我们没问题；现在，在这个系统中，每个可能的 IRL 牌组都是（有很大的概率）可能的。这是一个很好的论点，除了……

2 ²²⁶只是一个近似52！。除以它。2 ²⁵⁶ /52！不可能是整数，因为首先，52！可以被3整除，但2的幂不能！由于这不是整数，因此我们遇到的情况是所有牌组都是可能的，但有些牌组比其他牌组更有可能。

如果不清楚，请考虑数字较小的情况。假设我们有三张卡，A、B 和 C。假设我们使用带有 8 位种子的 PRNG，那么就有 256 个可能的种子。PRNG(3)根据种子的不同，有 256 个可能的输出；不可能让其中三分之一是 A，三分之一是 B，三分之一是 C，因为 256 不能被 3 整除。必须对其中一个有轻微的偏差。

^{类似地，52 也不能被2256}整除，因此必然存在偏向于将某些牌作为第一张牌进行选择，而对其他牌则存在偏向于不选择。

在我们最初的 32 位种子系统中，存在巨大的偏差，绝大多数可能的牌组都没有产生。在这个系统中，所有牌组都可以产生，但是牌组分配仍然存在缺陷. 有些套牌非常轻微比其他的更有可能。

现在的问题是：我们是否会利用这个缺陷发起攻击？答案是实际上，可能并非如此. CPRNG 的设计使得如果种子是真正随机的然后从计算上来说，区分CPRNG和是不可行的TRNG。

好的，我们总结一下。

伪随机数和真正随机数有何不同？

它们所表现出的可预测性水平有所不同。

真正的随机数是不可预测的。
如果种子可以确定或猜测，则所有伪随机数都是可预测的。

为什么这种差异很重要？

因为有些应用程序的系统安全性依赖于不可预测性。

如果使用 TRNG 来选择每张卡，那么系统就是牢不可破的。
如果使用 CPRNG 来选择每张卡，则当种子不可预测且未知时，系统是安全的。
如果使用具有较小种子空间的普通 PRNG，那么无论种子是否不可预测或未知，系统都不安全；足够小的种子空间容易受到我所描述的那种暴力攻击。

这种差异是否与 PRNG 的输出分布有关？

分布不均匀或缺乏个人通话与RNG(n)我所描述的攻击无关。

正如我们所见，aPRNG和CPRNG都会产生从所有可能的牌组中选择任何一副牌的概率分布不佳。的情况PRNG要糟糕得多，但两者都存在问题。

还有一个问题：

如果 TRNG 比 CPRNG 好很多，而 CPRNG 又比 PRNG 好很多，那么为什么还有人使用 CPRNG 或 PRNG 呢？

两个原因。

第一：费用。TRNG 是昂贵的生成真正的随机数很困难。CPRNG 只需一调用 TRNG 获取种子。缺点当然是你必须保守这个种子的秘密。

第二：有时我们想可预测性，我们关心的只是良好的分布。如果您生成“随机”数据作为测试套件的程序输入，并且它显示了一个错误，那么再次运行测试套件再次产生错误将是件好事！

我希望现在这一点更加清楚了。

最后，如果你喜欢这篇文章，那么你可能会喜欢阅读一些关于随机性和排列主题的文章：

Answer