写给开发人员的实用密码学 - 随机数

上一篇文章中介绍了消息验证码，这篇文章咱们来聊聊随机数。随机数看起来是一个很简单的概念，不论哪种编程语言都提供了简单的生成随机数的方法，有必要单独写一篇文章么？

随机数看起来简单，但在密码学中的用途非常大。比如用于加解密的密钥本质上就是一个随机数，密码学算法内部也会用到随机数。从开发者直观的角度看，随机数就是一串杂乱无序的字母、数字、符号组合，但如何生成随机数很重要，也就是说如何正确使用随机数生成算法非常重要。

反映二战期间历史的谍战片中，经常有破译密电的情节。一种常用的手段就是截获密报，从众多密报中找出规律，从而破解密码。这种破解方式在现代计算机面前太容易了。首先，因为信息技术的广泛使用，密文的收集非常容易，其次，计算机运算速度快，遍历、迭代都非常容易做到。所以现代密码学的首要要求是不可预测，这也是随机数为什么如此重要。比如加密密钥，应该是其他任何人都不能生成，或者以相同的密钥生成方式生成。

下面讨论计算机科学中的随机数及其在密码学中的作用，以及伪随机数生成器（Preudo Random Number Generator，PRNG）、密码学伪随机生成器（Cryptography secure Preudo Random Number Generator，CSPRNG）以及开发人员应如何生成和使用随机数的一些准则。

伪随机数生成器（PRNG）

PRNG是从某个初始熵（种子）开始，并通过某种计算来计算下一个随机数的函数，而这些计算在不知道种子的情况下是无法预测的。这种计算称为伪随机函数。

伪随机函数内部会维护一个状态（internal state）。首先，通过初始种子初始化状态。当生成下一个随机数时，它是从内部状态（使用某种计算或公式）计算出来的，然后更改伪随机函数的内部状态（使用某种计算或公式）。当生成下一个随机数时，将再次根据函数的内部状态进行计算，并再次更改此状态，依此类推。以最简单的形式可以执行以下过程：

伪随机数生成

如果每次熵（或种子）是一样的，生成的随机数也是相同的，所以熵（或种子）对于随机数生成器非常重要。

好的随机数生成器应该是快速的，并且应该具有统计随机性（请参阅Diehard测试），即在一段时间内所有数字的生成机会均应相同。而CSPRNG有更高的要求，还要求不可预测性和不可重现性。所谓不可重现性（unrepeat）就是不管经过多长时间，不会产生完全相同的随机数。当然，在软件层面不可能生成完全不一样的随机数，在一定周期内，密码学随机数算法最终会生成两个完全相同的随机数，只是周期长短的问题，在密码学中应该尽量使用周期相对长的随机数。

初始熵（种子）

为了安全起见，PRNG应该从真正随机的初始种子开始，这绝对是不可预测的。如果种子是可预测的，它将生成可预测的随机数序列，并且整个随机生成过程将是不安全的。这就是为什么在开始时拥有不可预测的随机性（安全种子）非常重要的原因。

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

熵

在计算机科学中，“熵”是指不可预测的随机性，通常以位为单位进行度量。例如，如果您移动计算机的鼠标，它将生成一些难以预测的事件，例如鼠标光标的开始位置和结束位置。如果我们假设鼠标在 [0 ... 255] 像素范围内更改了位置，则从此鼠标移动收集的熵应约为8位（因为2 ^ 8 = 255）。另一个示例：如果要求用户考虑一个[0 ... 1000]范围内的数字，则该数字将会是大约 9-10 位的熵（因为 2 ^ 10 = 1024）。为了收集256位的熵（例如安全地生成256位的整数），您将需要考虑一系列此类事件的序列（例如用户的鼠标移动和键盘输入）。

收集熵

我们可以从计算机中许多难以预测的事件中收集熵：键盘点击、鼠标移动、网络活动、相机、麦克风输入等，以及它们发生的时间。初始随机性的收集通常是由操作系统（OS）在内部执行的，操作系统提供了标准 API 来访问它（例如，从 Linux 中的 /dev/random 文件读取）。

应用软件也可以通过要求用户移动鼠标、在键盘上键入内容、在麦克风上说某些内容或在相机前面移动一会儿来明确地收集熵。一个很好的例子是bitaddress.org钱包应用程序，该应用程序将鼠标移动与键盘事件结合在一起以收集熵：

收集熵

另外一个例子就是 openssl 命令行工具，如果生成密钥，会让您敲击键盘，且要敲一定数量的按键，然后才会生成密钥。

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

根据定义，CSPRNG是一种伪随机数发生器（PRNG），要使PRNG成为CSPRNG，有两个主要要求：

• 满足下一个比特测试：如果某人从 PRNG 开始就知道所有k个比特，那么他将无法使用合理的计算资源来预测 k + 1个比特。
• 抗恶意播种：即便某一攻击能获得一段时间上对CSPRNG的输入的完全或部分控制，要预测或再现来自CSPRNG的任何随机输出仍然是不可行的。

操作系统中的熵通常数量有限，并且等待更多的熵是缓慢且不切实际的。大多数密码应用程序使用CSPRNG，CSPRNG会将来自操作系统的可用熵“扩展”到更多位，这是加密目的所必需的，并且符合上述CSPRNG要求。

大多数CSPRNG结合使用来自操作系统和高质量PRNG生成器的熵，它们经常“重置”，这意味着当新的熵来自操作系统时（例如，来自用户输入、系统中断、磁盘 I/O 或硬件随机产生），基础 PRNG 根据即将到来的新熵位来更改其内部状态。随着时间的推移，这种不断的播种使CSPRNG变得非常难以预测和分析。

通常，现代 OS CSPRNG API 将来自环境的不断收集的熵与其内置伪随机算法的内部状态结合起来，并进行连续重新播种，以确保生成的随机性具有最大的不可预测性，同时具有高速和无阻塞行为。

硬件随机发生器

硬件随机发生器，称为真随机数发生器（True Random Number Generator，TRNG），通常捕获物理过程或现象，例如光的可见光谱、环境的热噪声、大气噪声等。物理环境的随机性是通过专门的传感器收集，然后由设备进行放大和处理，最后通过USB、PCI Express或其他标准接口传输到计算机。

现代微处理器（CPU）提供了内置的硬件随机发生器，可通过特殊的CPU指令 RdRand 访问该发生器，该指令将随机整数返回到CPU寄存器之一。

如今，大多数加密应用程序都不需要硬件随机数生成器，因为操作系统中的熵对于常规加密目的而言足够安全。对于具有较高安全性要求的系统（例如银行和金融应用程序、证书颁发机构和大额付款处理等），需要使用TRNG。

开发人员如何正确使用CSPRNG？

通常，开发人员通过加密库访问其操作系统的密码学随机数生成器（CSPRNG）。

• 在 Linux 和 macOS 中，可以认为 /dev/random 和 /dev/urandom 随机性源对于大多数加密目的而言都是足够安全的，并且大多数加密库都在内部访问它们。
• 在 Windows 中，可以使用来自下一代（CNG）的Crypto API或更高级的密码库中的 BCryptGenRandom 函数安全地生成用于加密目的的随机数。
• 在 C＃ 中，使用 .NET Framework 或 .NET Core 中的 System.Security.Cryptography.RandomNumberGenerator.Create()。
• 在 Python 中，请使用 os.urandom() 或 secrets 库。
• 在 Java中，请使用 java.security.SecureRandom 系统类。
• 在 JavaScript 中，将 window.crypto.getRandomValues(Uint8Array) 用于客户端（在Web浏览器中）或 crypto.randomBytes() 用于服务器端（在Node.js中）。

切勿将 Math.random() 或类似的不安全RNG函数用于加密目的！

小结

看到上面的介绍，是否有些晕。其实在开发中我们并不需要理解随机数是如何生成的，但我们需要时刻牢记在心的是，随机数生成非常重要，一定要使用安全的API生成安全的随机数。在大多数情况下，我们只需要掌握系统提供了哪些安全的随机数生成API，知道如何使用即可。

密码学应用中很多场景会涉及随机数，不同的用途有不同的称呼，比如密钥、初始化向量（IV）、nonce、盐（salt）等，目前可以不用关心这些概念，后续用到会进行讲解。

在下一篇文章中，我们将介绍密码学中的对称加密算法，敬请关注！