加密安全的随机数生成器是如何工作的？

小开

每个生成器将使用自己的播种策略，但这里有一点来自关于 CryptGenRandom 的 Windows API 文档

对于 MicrosoftCSP，CryptGenRandom 使用相同的随机数其他安全组件使用的生成器 CryptoAPI 存储一个中间随机种子与每个用户随机数生成器，调用应用程序提供可能的位例如，鼠标或键盘的计时输入结合存储的种子和各种系统数据和用户进程 ID 和线程 ID、系统时钟、系统时间、系统计数器、内存状态、空闲磁盘集群、, 散列用户环境块。此结果用于为伪随机数生成器(PRNG)。

在具有 ServicePack1(SP1)和更高版本的 WindowsVista 中，会出现一个实现了 NIST 规定的基于 PRNG 的 AES 计数模式使用特殊出版物800-90 Server2003和 WindowsXP，即联邦信息中指定的 PRNG 使用处理标准(FIPS)186-2。如果应用程序具有访问权限对于一个好的随机源，它可以在 pbBuffer 缓冲区中填充一些调用 CryptGenRandom 之前的随机数据进一步随机化其内部种子调用前初始化 pbBuffer 缓冲区的步骤 CryptGenRandom.

小开

首先，加密安全的 PRNG 的要点是没有，它可以生成完全不可预测的序列。正如你所指出的，缺乏能够产生大量(或多或少)真实随机性的东西 ¹使得这种情况不可能发生。

所以你只能求助于用力来预测。“困难”在这里的意思是，它需要不可行的时间，无论如何，无论什么是必要的将被淘汰。有许多数学算法在其中发挥了作用ーー如果你看一些著名的 CSPRGs，并研究它们是如何工作的，你就可以得到一些启示。

构建这种 PRNG 的最常见变体是:

使用流密码，它已经输出了一个(据说是安全的)伪随机位流。
在计数器模式下使用分组密码

计数器上的散列函数有时也会被使用。

一般的要求是，从发电机的比特流中确定原始初始向量是不可行的，而且下一个比特也不容易预测。

至于初始化，大多数 CSPRGs 使用系统上可用的各种资源，从真正随机的东西，如线噪声，中断或系统中的其他事件，以及其他东西，如某些内存位置，等等。这种初始向量最好是真正随机的，而不是依赖于数学算法。这个初始化在 Debian 的 OpenSSL 实现中被打破了一段时间，这导致了严重的安全问题。

^{这也有它的问题，人们在消除偏差时必须小心，因为像热噪声这样的东西根据温度的不同有不同的特性ーー你几乎总是有偏差，需要消除它。这本身就不是一件小事。}

小开

最佳答案

一个加密安全的数字随机生成器，正如您可能用于生成加密密钥那样，通过从其他人无法观察到的来源收集熵——也就是不可预测的输入——来工作。

例如，Linux 上的/dev/Random (4)从硬盘返回数据、按键和传入网络数据包等来源收集硬件中断时间变化的信息。这种方法是安全的，只要内核不高估它收集了多少熵。几年前，来自各种不同来源的熵的估计都被降低了，这使得它们更加保守。这是解释 Linux 如何估计熵。

以上这些都不是特别高吞吐量的。Dev/Random (4)可能是安全的，但是它通过在不能确定数据是安全的随机数时拒绝发送数据来维护安全性。例如，如果希望生成一个很多加密密钥和 nonce，那么可能需要使用硬件随机数生成器。

通常，硬件 RNG 的设计是从一对运行速度接近相同的振荡器之间的差异进行采样，但由于热噪声的影响，这些振荡器的频率略有不同。如果我没记错的话，用于英国优质债券彩票的随机数生成器 ERNIE 就是这样工作的。

替代方案包括采样 CCD 上的噪音(见 LavaRND) ，放射性(见辣妹)或大气噪音(见 Org，或者只是把调幅收音机插入你的声卡，而不是一个电台)。或者你可以直接要求计算机的用户到像一只疯狂的黑猩猩一样敲击键盘一分钟，无论什么漂浮你的船。

正如安德拉斯指出的那样，我只想谈谈一些最常见的熵聚集方案。Thomas Pornin 的回答和约翰内斯 · 罗塞尔的回答都很好地解释了为了把聚集的熵再次分发出去，我们可以如何处理聚集的熵。

小开

为了使一个随机数生成器被认为是 加密安全，在需要抵御攻击的安全谁知道的算法和(大量)先前生成的比特。这意味着，有了这些信息的人无法重建任何隐藏的发生器内部状态，并给出下一个比特产生的预测，其准确率将高于50% 。

正常的伪随机数生成器通常不具有密码安全性，因为从先前输出的比特重建内部状态通常是微不足道的(通常，整个内部状态只是直接生成的最后 N 个比特)。任何没有良好统计特性的随机数生成器也不安全，因为它的输出至少是一方可预测的，即使不知道内部状态。

因此，至于它们是如何工作的，任何好的加密系统都可以用作加密安全的随机数生成器——使用加密系统对“正常”随机数生成器的输出进行加密。由于对手不能重建普通随机数生成器的明文输出，所以他不能直接攻击它。这是一个有点循环的定义，它回避了如何键入加密系统以保证其安全的问题，这是另一个完全不同的问题。

小开

出于加密的目的，需要的是流应该“在计算上与均匀随机位无法区分”。“计算性”意味着它不需要真正的随机性，只是对于那些没有使用上帝自己的计算机的人来说是这样的。

在实践中，这意味着系统必须首先采集一系列 N真正的随机位。N应该足够大，以阻止彻底的搜索，也就是说，尝试所有 2 ^ n的 N位组合是不可行的。这是实现的，就目前的技术而言，只要 N大于90左右，但密码学家只需爱的两次幂，所以习惯上使用 N = 128。

这些 N随机位是通过收集“物理事件”获得的，就物理学而言，这些事件应该是不可预测的。通常使用计时: CPU 有一个周期计数器，每秒更新数十亿次，有些事件发生时不可避免地会有抖动(网络数据包传入、鼠标移动、键击... ...)。系统对这些事件进行编码，然后通过应用加密安全的散列函数(如 SHA-256)对它们进行“压缩”(然后截断输出以产生 N位)。这里重要的是，物理事件的编码具有足够的熵: 粗略地说，所述事件可以共同假定至少有 2 ^ n组合。散列函数，根据它的定义，应该能够很好地将熵集中到 N位字符串中。

一旦我们有了 N位，我们使用 PRNG (伪随机数生成器)来生成所需要的位。假设 PRNG 在一个足够宽的未知 N位密钥上运行，其输出在计算上与均匀随机位无法区分，则称 PRNG 是加密安全的。在90年代，一个流行的选择是 RC4，这是非常简单的实现，相当快。然而，事实证明它有可测量的偏差，也就是说，它并不像最初希望的那样难以区分。EStream 计划包括为 PRNG 收集更新的设计(实际上是流密码，因为大多数流密码包含在 PRNG 中，输出是用 XORed 加密的数据) ，记录它们，并促进密码学家的分析。ESTREAM Portfolio 包含7个被认为足够安全的 PRNG 设计(即它们抵制分析，而密码学家往往对它们抵制的 为什么有很好的理解)。其中，四个是“软件优化”。好消息是，虽然这些新的 PRNG 似乎比 RC4安全得多，但它们也明显更快(我们在这里讨论的是每秒几百兆字节)。其中三个是“任何使用免费的”，并提供了源代码。

从设计的角度来看，PRNG 重用了分组密码的大部分元素。同样的概念，雪崩和扩散位到一个广泛的内部状态被使用。或者，可以从块密码构建一个像样的 PRNG: 只需使用 N位序列作为块密码的密钥，并加密计数器的连续值(如果块密码使用我位块，则表示为我位序列)。只要分组密码是安全的，并且产生的数据流不超过 M * 2 ^ (m/2)位(对于 M = 128来说，这意味着大约3000亿 G 字节，所以对于大多数目的来说，这已经足够大了) ，这就产生了一个伪随机数据流，在计算上与随机数据流是无法区分的。这种用法被称为计数器模式(CTR)。

通常，CTR 模式下的分组密码不如专用流密码快(流密码的关键在于，由于丧失了分组密码的灵活性，因此预计性能会更好)。然而，如果你碰巧拥有英特尔最新的带有 AES-NI指令的 CPU (AES-NI指令基本上是硬件上的 AES 实现，集成在 CPU 中) ，那么带有 CTR 模式的 AES 将产生无与伦比的速度(每秒几 GB)。