安全随机数生成器

安全随机数生成器、PRNG 与 CSPRNG

在密码学中，随机性（熵）具有非常重要的作用。许多算法都需要随机的、即不可预测的数值。如果这些数值可以预测，算法的安全性就会遭到破坏。

例如，假设我们需要一个用来保护金融资产的秘密密钥。这个秘密密钥应当以随机方式生成，确保其他任何人都无法生成或持有相同的密钥。如果使用安全随机数生成器生成密钥，密钥就会不可预测，系统也会保持安全。因此，“安全随机”简单来说就是“不可预测的随机”。

下面更详细地讨论计算机科学中的随机数及其在密码学中的作用，同时介绍伪随机数生成器（PRNG）、安全伪随机数生成器（CSPRNG），以及开发者在代码中生成和使用随机数时应遵循的一些准则。

随机数生成器

在计算机科学中，随机数通常来自伪随机数生成器（PRNG），后者由某些不可预测的初始随机性（熵）进行初始化。密码学使用称为 CSPRNG 的安全 PRNG，它通常将熵、PRNG 和其他技术结合起来，使生成的随机性不可预测。

伪随机数生成器（PRNG）

伪随机数生成器（PRNG）用于将少量初始随机性扩展为大量伪随机性，通常供密码系统使用。请注意，PRNG 并不具备密码学安全性，而且不同于 CSPRNG。

PRNG 是一种函数：它从某个初始熵（种子）开始，通过某种计算得出下一个随机数；如果不知道种子，这种计算的结果就不可预测。这类计算称为伪随机函数。

不适用于密码学的伪随机函数通常会维护一个内部状态。启动时，使用初始种子初始化状态。生成下一个随机数时，先根据内部状态进行某种计算或套用某个公式，随后再通过某种计算或公式改变伪随机函数的内部状态。生成再下一个随机数时，又以函数当前的内部状态为基础计算，并再次改变状态，如此不断重复。

这一过程最简单的实现形式如下：

init(entropy):
  state = entropy, counter = 0
netNum():
  state = HMAC(state, ++counter)
  return state

当然，HMAC 函数可以替换为某种密码学哈希函数，或 Mersenne Twister 这样的其他数学变换；后者并不具备密码学安全性。不过，核心思路保持不变：伪随机数生成器具有内部状态，由某些初始随机性进行初始化，并随时间推移不断改变内部状态，再根据当前状态生成伪随机数。

优秀的随机数生成器应当快速，并产生统计意义上的随机性（参见 Diehard 测试），也就是长期来看所有数值被生成的概率都相同。但这对于密码学而言仍不充分，因此 CSPRNG 还必须满足更高要求。

上述基于 HMAC(key + counter) 生成伪随机数的思路，在加入一些复杂设计后，被称为 HMAC_DRBG 算法，并在安全标准 NIST 800-90A 中有所说明。

初始熵（种子）

为了保证安全，一个在统计意义上随机的 PRNG 应当以真正随机的初始种子启动，并且该种子必须完全不可预测。如果种子可预测，它就会生成可预测的随机数序列，使整个随机数生成过程变得不安全。因此，启动时拥有不可预测的随机性，也就是安全种子，至关重要。

如何以安全方式初始化伪随机数生成器？答案很简单：收集随机性（熵）。

熵

在计算机科学中，“熵”是指不可预测的随机性，通常以位为单位度量。例如，移动计算机鼠标会产生一些难以预测的事件，如鼠标指针的起始位置和结束位置。假设鼠标位置的变化范围为 [0...255] 像素，那么这次鼠标移动收集到的熵约为 8 位，因为 2^8 = 256。再举一例：如果要求用户在 [0...1000] 范围内想一个数，这个数会包含约 9～10 位熵，因为 2^10 = 1024。要收集 256 位熵，例如安全生成一个 256 位整数，就必须综合一系列此类事件，如用户的鼠标移动和键盘交互。

收集熵

可以从计算机中的许多难以预测的事件收集熵，例如键盘按键、鼠标移动、网络活动、摄像头活动、麦克风活动等，并结合这些事件发生的时间。这种初始随机性的收集通常由操作系统（OS）在内部完成，操作系统会提供标准 API 来访问它，例如在 Linux 中读取 /dev/random 文件。台式机、笔记本电脑或手机通常很容易收集熵，而某些资源受限的硬件设备（如简单的微控制器）则很难甚至无法收集熵。

应用软件也可以显式收集熵，例如要求用户移动一段时间的鼠标、在键盘上输入内容、对着麦克风说话，或在摄像头前移动。bitaddress.org 钱包应用就是一个很好的例子，它将鼠标移动与键盘事件结合起来收集熵：

收集到足够的熵后，就用它初始化随机数生成器。

不安全的随机性

不安全或已被攻破的随机性会破坏密码学安全。一个值得借鉴的案例是：Android 中的随机数生成器存在缺陷，导致 Bitcoin 被盗：https://goo.gl/PFE1kr。因此，开发者使用密码学时必须重视随机性，确保所用的随机数生成器安全可靠。

不安全随机性的示例

为了说明在旧版 Python 中破坏随机数安全性有多么容易，来看下面的代码示例：

import random
print(random.randrange(1000000, 9999999))

运行上述代码示例：https://repl.it/@nakov/Random-in-Python。

上述代码看起来会生成一个随机数，但这个数可能是可预测的。这是因为旧版 Python 的 random 库使用当前时间初始化随机数生成器的种子。因此，只要知道生成随机数的计算机的当前时间——显然可以大致推测——就能够预测随机种子，进而预测所生成的随机数。

为了更直观地说明这一点，来看下面这个生成两个 50 位随机整数的示例：

import random, time

random.seed(time.time())
r1 = random.randrange(1e49, 1e50-1)

random.seed(time.time())
r2 = random.randrange(1e49, 1e50-1)

print(r1)
print(r2)

运行上述代码示例：https://repl.it/@nakov/Random-with-seed-in-Python。

上述代码会打印两个相同的数，两者都取决于当前时间。显然，使用相同时间作为初始种子，会在输出中生成相同且可预测的伪随机数。下面是该代码的一次输出示例：

53285353661739398833155340591358345604323255820576
53285353661739398833155340591358345604323255820576

如果通过调试器或在较慢的环境中运行这段代码，由于两次随机数生成之间的时间发生了变化，生成的数可能会不同。Python 解释器在交互式控制台中通常也会生成两个不同的数。要获得与上面类似的结果，应先把代码保存到脚本文件中，例如 insecure-rnd.py，然后执行该 Python 脚本文件：

本质上，如果使用当前时间这样的可预测数值初始化随机种子，攻击者就可以尝试前后 5 秒范围内的所有可能值，找出确切的初始种子，进而破坏系统安全。

随机性与密码学

请记住：密码学离不开不可预测的随机性！随机数生成器一旦被攻破，就会生成可预测的数值，攻击者可能因此解密通信、泄露私钥、篡改数字签名等。作为开发者，你应当始终关注所用密码学库如何生成随机数。

CSPRNG（密码学安全伪随机数生成器）

按照定义，CSPRNG（密码学安全伪随机数生成器）是具有适合密码学用途之性质的伪随机数生成器（PRNG）。一个 PRNG 要成为 CSPRNG，必须满足两项主要要求：

通过下一位测试：即使某人知道 PRNG 开头的全部 k 位，也无法使用合理的计算资源预测第 k+1 位。
能够抵抗状态泄露扩展攻击：即使攻击者猜到 PRNG 的内部状态，或该状态以某种方式泄露，也无法重建泄露之前生成的全部随机数。

操作系统中的熵通常数量有限，等待更多熵既缓慢又不切实际。大多数密码学应用使用 CSPRNG，将操作系统提供的熵“扩展”为密码学用途所需的更多位数，同时满足上述 CSPRNG 要求。

人们已经提出了许多 CSPRNG 算法的构造方案：

基于计数器模式下的安全分组密码、流密码或安全哈希函数构造 CSPRNG。
基于数论构造 CSPRNG，依赖整数分解问题（IFP）、离散对数问题（DLP）或椭圆曲线离散对数问题（ECDLP）的计算困难性。
采用专门面向密码学安全随机性设计的 CSPRNG，例如曾用于 MacOS 和 FreeBSD 的 Yarrow 算法与 Fortuna)。

大多数 CSPRNG 会结合来自操作系统的熵和高质量 PRNG，并且经常进行“重新播种”。这意味着，当操作系统获得新的熵时，例如来自用户输入、系统中断、磁盘 I/O 或硬件随机数生成器，底层 PRNG 会根据新获得的熵位改变内部状态。随时间持续重新播种，使 CSPRNG 极难预测和分析。

结论：使用安全随机数生成器

始终使用密码学安全的随机数生成库，例如 Java 中的 java.security.SecureRandom 和 Python 中的 secrets 库：

import secrets
print(secrets.randbelow(int(1e50)))

运行上述代码示例：https://repl.it/@nakov/Secrets-in-Python。

上述代码不依赖当前时间，而是根据操作系统收集的熵生成一个本质上不可预测的随机数。

安全随机数生成器

安全随机数生成器