随机数生成器应用建议

Peter Occil

4.91/5 (90投票s)

2016年3月6日

公共领域

44分钟阅读

202333

大多数使用随机数的应用程序都关心不可预测性、高质量或可重复性。本文解释了这三种随机数生成器，并对每一种提出了建议。

引言

许多应用程序依赖随机数生成器（RNG）来生成看似随机的数字序列；然而，仅仅“看起来随机”是不够的。但遗憾的是，当今大多数流行的编程语言——

对其内置RNG（如C语言的 rand）的规定很少且要求很弱，
规定了相对较弱的通用RNG（如Java的java.math.Random），
默认实现了一些有待改进的RNG（如Mersenne Twister），
默认使用时间戳初始化RNG（如.NET Framework的System.Random实现），以及/或
使用默认使用固定值初始化的RNG（例如MATLAB和C⁽¹⁾中的情况），

因此，许多应用程序使用RNG，尤其是内置RNG，其高质量或安全性几乎没有保证。这就是为什么本文档讨论高质量RNG并推荐现有实现。

本文档涵盖

加密RNG⁽²⁾、非加密RNG和手动播种的伪随机数生成器，以及有关其使用和属性的建议。
非确定性源、熵和种子生成。
RNG的现有实现。
为应用程序可重用性设计的RNG实现指南。
有关RNG的洗牌问题。

本文档不涵盖

测试RNG实现的正确性⁽³⁾或统计质量。请参阅我关于PRNG测试的文档。
生成不等概率的数字；我在另一篇文档中讨论了这个问题。
低差异序列（拟随机序列）的生成器，如Sobol序列。它们不是RNG，因为它们生成的数字依赖于先前的结果。
RNG选择受监管要求限制的应用程序。

关于本文档

本文档是开源的；最新版本请参阅 源代码 或其在 GitHub上的渲染图。您可以通过 CodeProject 或 GitHub问题页面 发送您对此文档的评论。

定义

本文档中

随机数生成器（RNG） 指的是旨在生成具有以下特性的数字的软件和/或硬件：每个可能的输出与其他输出一样可能，且不受任何其他因素的影响⁽⁴⁾。
伪随机数生成器（PRNG） 指的是通过算法扩展其输入的生成器。
种子指的是作为PRNG输入的任意数据。
信息安全 指的是保护信息免受可能访问、使用、延迟或操纵该信息的攻击。⁽⁵⁾

摘要

应用程序是否为了信息安全目的（例如，作为密码或其他秘密）使用随机行为的数字？
- 是：使用加密RNG。
否：应用程序是否需要可重复的“随机”数？
- 是：使用手动播种的高质量PRNG。如果已知种子，则使用它。否则，使用加密RNG生成一个新的种子。
  - 应用程序是否运行多个独立的进程，这些进程使用伪随机数？
    - 否：使用上面确定的种子播种一个PRNG。
    - 是：将上面确定的种子传递给每个进程，如“非加密PRNG的种子生成”中所述。
否：加密RNG对应用程序来说太慢了吗？
- 是：使用高质量PRNG，并使用加密RNG生成的种子进行初始化。
- 否：使用加密RNG。

加密RNG

加密RNG（也称为“加密强”或“加密安全”RNG）旨在生成不仅“看起来随机”，而且猜中成本极高的数字。应用程序应在任何需要—

为信息安全目的生成随机行为的数字，或
生成随机行为数字的频率很低，以至于RNG的速度不是问题。

有关要求，请参阅“加密RNG：要求”。
有关现有API，请参阅“编程语言中的现有RNG API”。
对于加密RNG，应用程序应仅为整个应用程序使用一个线程安全的RNG实例。

示例： 建议使用加密RNG—

在生成安全参数时（包括加密密钥、随机密码、随机数、会话标识符、“盐”和秘密值），
为确保计算机之间消息或其他数据的安全传输或接收，或
每当预测未来的随机结果会给玩家或用户带来显著且不公平的优势时（例如在多人网络游戏中）。

非加密PRNG

非加密PRNG在生成的数字的随机性质量方面差异很大。因此，不应使用非加密PRNG—

为信息安全目的（例如，生成随机密码、加密密钥或其他秘密），
如果加密RNG对应用程序来说足够快，或者
如果PRNG不是高质量的（参见“高质量RNG：要求”）。

非加密PRNG可以是自动播种的（在创建PRNG时生成新种子），也可以是手动播种的（PRNG使用预定种子）。

请参阅“何时使用手动播种的PRNG”了解应使用哪种播种方式。
有关如何播种的建议，请参阅“非加密PRNG的种子生成”。
有关现有API，请参阅“编程语言中的现有RNG API”。
对于自动播种的PRNG，应用程序应仅为整个应用程序使用一个线程安全的RNG实例。

手动播种的PRNG

给定的伪随机数生成器（PRNG）为相同的“种子”生成相同的“随机”数字序列。有些应用程序关心可重复的“随机性”，因此可以手动设置PRNG的种子以获得可重复的“随机”数字。

何时使用手动播种的PRNG

通过手动播种PRNG以获得可重复的“随机性”，应用程序将与其PRNG或其实现绑定。因此，应用程序不应使用手动播种的PRNG（而不是加密或自动播种的RNG），除非—

应用程序可能需要多次生成相同的“随机”结果，
应用程序—
- 使种子（或基于种子的“代码”或“密码”）可供用户访问，或
- 发现存储或分发“随机”数字或“随机”内容比存储种子更不切实际（例如，存储这些数字以供以后“重播”，在“保存文件”中存储该内容，或分发该内容而不是种子给网络用户），并且
任何使用此类PRNG生成该“随机”结果的功能都是可重复的，即，只要该功能仍在应用程序中使用，它就会为相同的种子生成相同的“随机”结果。

手动播种的PRNG建议

如果应用程序选择使用手动播种的PRNG来实现可重复的“随机性”，则应用程序—

应选择高质量PRNG，
应选择具有一致行为且将来不会改变的PRNG实现，
应记录所选PRNG以及该PRNG的所有参数，并且
不应使用浮点数播种PRNG，也不应使用该PRNG生成浮点数。

有关生成PRNG种子的建议，请参阅“非加密PRNG的种子生成”）。

示例： 应用程序可以使用一个第三方库实现手动播种的PRNG，该库明确表示它实现了高质量PRNG算法，并可以使用来自加密RNG的比特序列来初始化该PRNG。开发人员还可以提及所选PRNG的使用情况，以提醒其他开发人员该PRNG需要保持不变。

手动播种PRNG的用例

手动播种PRNG的用例包括以下内容

模拟和机器学习。这包括物理模拟和游戏中的人工智能（AI），以及用于重现已发布研究数据的模拟。
蒙特卡洛估计。
过程噪声生成。
生成难以存储的“随机”内容的ご了承。
单元测试，其中“随机性”不应影响其通过或失败。在这里，为了测试的目的，使用具有固定种子的手动播种PRNG代替了另一种RNG，以帮助确保跨被测计算机的一致结果。

游戏中的手动播种PRNG

许多类型的游戏软件会生成看似“随机”的游戏内容，这些内容可能需要反复生成，例如—

角色扮演游戏的程序生成地图，
洗牌纸牌游戏中的虚拟牌堆，或
随机选择的游戏棋盘或拼图棋盘的配置。

通常，“随机”内容越大，使用手动播种PRNG和自定义种子生成该内容的理由就越充分。以下是特殊情况—

如果游戏只需要在游戏开始时生成可重复的“随机”内容（例如，“随机”游戏棋盘或虚拟牌的“随机”顺序），并且该内容很小（例如，不超过一百个数字）
- 游戏不应使用手动播种的PRNG，除非种子是基于用户输入的“代码”或“密码”。这表明游戏应存储“随机”内容而不是种子。
在网络游戏中，多个计算机（例如，多个玩家，或客户端和服务器）共享游戏状态的视图，并且使用RNG或PRNG的数字来更新该游戏状态
- 游戏不应使用手动播种的PRNG，其中预测随机结果可能会给玩家带来显著且不公平的优势（例如，随机结果是骰子掷出的结果，或抽牌堆的顶牌，用于棋盘或纸牌游戏）。游戏可以在其他情况下使用此类PRNG来确保计算机之间的游戏状态一致，包括在物理模拟和AI中。

示例

假设一个游戏生成了一个具有随机地形的地图（这使用了RNG来生成大量数字），并向玩家显示一个用于生成该地图的“代码”（例如条形码或字母数字字符串）。在这种情况下，游戏—

可以更改用于生成随机地图的算法，但是
应使用新的算法，并且“代码”不能与先前算法使用的“代码”混淆，并且
当玩家输入旧“代码”时，即使更改了新算法，也应继续使用该旧“代码”生成相同的随机地图。
假设一个游戏实现了一个章节，涉及在一个随机生成的地下城中导航，其中散布着随机的怪物和物品。如果地下城、怪物和物品的布局对于给定的一周和所有玩家来说都必须相同，则游戏可以将PRNG播种一个从当前周、当前月、当前年以及可选的固定比特序列生成的哈希码。

单一随机值

如果应用程序只需要一个固定位数的随机值，那么应用程序可以将种子传递给哈希函数而不是PRNG。例如，包括以下内容

通过将种子传递给MD5哈希函数来生成随机的颜色，该函数输出一个128位哈希码，并取哈希码的前24位作为随机颜色。
在GLSL（OpenGL着色语言）片段着色器中，通过将片段坐标（对每个片段或“像素”都不同）和种子（对所有片段都相同）传递给Wang哈希来生成伪随机数，该哈希输出一个32位整数。⁽⁶⁾

确保可重复性

为了确保手动播种的PRNG在计算机、运行和应用程序版本之间提供可重复的“随机”数字，应用程序需要特别注意。如果应用程序依赖于应用程序控制之外的功能或行为，包括以下任何一种，可重复性通常是无法实现的—

浮点数是导致结果不一致的主要原因。同一浮点数运算的不同实现即使输入相同，也可能存在细微差别。⁽⁷⁾ 控制所有这些差异并非易事，其中包括—
- 精度差异，例如Java的Math与StrictMath，或x87 FSIN指令与正弦的软件实现。
- 舍入差异。如果应用程序无法控制浮点数的舍入方式，结果可能会有所不同。⁽⁸⁾
- 运算顺序差异。与整数或定点数⁽⁹⁾不同，以不同顺序添加或乘以浮点数会改变结果。例如，这可能发生在并行规约（如并行求和和点积）中，它将计算分散到多个并行任务中，并在最后合并它们的结果。如果程序自动选择是否以及如何使用并行规约，结果可能会有所不同，甚至跨运行。
多线程和动态任务调度可能导致伪随机数生成器的生成顺序不同，或者在不同运行之间由不同线程生成，从而导致结果不一致；即使每个线程本身为相同的输入生成相同的伪随机数，也可能发生这种情况（Leierson等，2012）⁽¹⁰⁾。处理此问题需要使用单线程，或将PRNG分配给单个任务而不是线程或整个应用程序。
非确定性源（在输入和状态相同的情况下输出也可能不同），例如文件系统或系统时钟。
未文档化、未定义或依赖于实现的行为或特性，包括C/C++的int或long的特定哈希表遍历顺序或特定大小。

因此，应用程序应仅在必要时使用手动播种的PRNG，以最大程度地减少对可重复“随机性”的需求。在需要可重复性时，应用程序应避免使用浮点数、非确定性特征和其他超出其控制范围的行为，并应坚持使用相同的算法版本。

至于可重复的PRNG，java.util.Random是具有一致行为的PRNG的一个例子，但以下都不是这种PRNG—

C语言的rand方法，以及C++的<random>中的分布类，如std::uniform_int_distribution，使用依赖于实现的算法进行伪随机数生成。
.NET的System.Random具有可能在未来发生变化的伪随机数生成行为。

非确定性源和种子生成

RNG最终依赖于所谓的非确定性源；没有这样的源，任何计算机都无法随机生成数字。

什么是无确定性源？

非确定性源是指每次输入相同时不产生相同输出的源（例如，一个不总是给出相同时间的时钟）。它们有很多种，但用于随机生成数字的源具有难以猜测的输出（即，它们具有高的熵；请参阅下一节）。它们包括—

中断和磁盘访问的时序，
键盘输入和/或其它输入设备交互的时序，
热噪声，
A. Seznec的“硬件易失性熵收集和扩展”（HAVEGE）技术生成的输出，前提是提供高分辨率计数器，并且
在短时间内两次高分辨率计数器值之间的差异（例如在“Jitter RNG”中；参见（Müller））⁽¹¹⁾。

RFC 4086，“安全性随机性要求”，第3节，包含对非确定性源的调查。

注意： 向应用程序提供随机生成数字的在线服务，以及麦克风和相机录音中注册的噪声（参见RFC 4086 sec. 3.2.1, (Liebow-Feeser 2017a)⁽¹²⁾, and (Liebow-Feeser 2017b)⁽¹³⁾），是额外的非确定性源。但是，在线服务需要Internet或其他网络访问，其中一些需要访问凭据。此外，许多移动操作系统要求应用程序在安装时向用户声明网络、相机和麦克风访问权限。因此，如果其他方法足够，则不推荐这些类型的源。

示例： 一个程序可以要求用户抛硬币或掷骰子并输入其结果。如果用户这样做，输入的结果将来自非确定性源（此处为硬币或骰子）。

什么是熵？

熵是描述猜测非确定性源输出的难易程度的值，与生成独立均匀随机比特的理想过程相比。熵通常是由该理想过程产生的比特数。（例如，具有32位熵的64位输出与猜测32个独立的均匀随机比特一样困难。）NIST SP 800-90B建议使用最小熵作为熵度量。表征非确定性源的熵并非易事，且超出了本文档的范围。另请参阅RFC 4086第2节。

种子生成

通常，生成PRNG的N位种子的步骤有两步⁽¹⁴⁾

从独立的非确定性源收集足够的数据，以达到N位熵或更多。
然后，将数据压缩成一个N位数字，这个过程称为随机性提取。

请参阅我的随机性提取说明。然而，需要指出的是，在信息安全应用中，不应单独使用无密钥的哈希函数进行随机性提取。

非加密PRNG的种子生成

通常，为了生成非加密PRNG允许的种子，应用程序应使用加密RNG或上一节所述的方法。

不建议使用时间戳播种PRNG，因为它们可能带有意外生成相同“随机”数字序列的风险。⁽¹⁵⁾

播种多个进程

某些应用程序要求多个进程（包括线程、任务或子任务）为了相同目的使用可重复的“随机”数字。例如，具有随机起始条件的多个模拟实例。然而，非加密PRNG倾向于产生相互关联的数字序列，这尤其不适用于模拟。

为了降低这种相关性风险，应用程序可以选择一个支持不相关序列流（非重叠序列，其行为类似于独立随机选择的数字序列）的高质量PRNG，并有一种有效的方式为每个进程分配不同的流。例如，在某些PRNG中，这些流可以—

通过使用连续种子初始化PRNG（如“基于计数器”的PRNG（Salmon等人，2011））⁽¹⁶⁾，或
通过以高效的方式丢弃固定但巨大的PRNG输出量（“跳跃向前”）。

可以按照以下方式为多个进程播种伪随机数生成：⁽¹⁷⁾

流案例。 如果PRNG支持如上所述的流：生成一个种子（或使用预定种子），然后
1. 为每个进程创建一个PRNG实例。
2. 对种子和固定标识符进行哈希处理，以生成PRNG允许的新种子。
3. 对于每个进程，将PRNG推进到下一个流（除非是第一个进程），然后将该进程的PRNG当前内部状态的副本交给它。
通用案例。 对于其他PRNG，或者如果每个进程使用不同的PRNG设计，以下是为伪随机数生成播种多个进程的一种方法，但它存在生成导致重叠、相关甚至相同数字序列的种子的风险，尤其是当进程使用相同的PRNG时。⁽¹⁸⁾ 生成一个种子（或使用预定种子），然后
1. 为每个进程创建一个PRNG实例。实例不必都使用相同的PRNG设计或参数；例如，一些可以是SFC64，另一些可以是xoroshiro128**。
2. 对于每个进程，对种子、该进程的唯一编号和一个固定标识符进行哈希处理，以生成进程的PRNG允许的新种子，并用新种子初始化该PRNG。
跳蛙法（Bauke和Mertens，2007）⁽¹⁹⁾。如果进程数量（N）很小，以下是为每个进程初始化PRNG的另一种方法。生成一个种子（或使用预定种子），然后
1. 创建一个PRNG实例。对种子和固定标识符进行哈希处理，以生成PRNG允许的新种子。
2. 将PRNG的状态的副本交给每个进程。然后，对于第二个进程，丢弃其PRNG的1个输出；对于第三个进程，丢弃其PRNG的2个输出；依此类推。
3. 现在，每当这样创建的PRNG产生输出时，它会在完成之前丢弃接下来的N减1个输出。

注意： 上述步骤包括对多个项目进行哈希处理以生成新种子。这必须使用N位或更多位的哈希函数（其中N是PRNG的最大种子大小），或者使用所谓的“种子序列生成器”，如C++的std::seed_seq。⁽²⁰⁾

示例

Philox4×64-7是一种计数器型PRNG，每个种子支持一个流。为了基于种子“seed”和此PRNG播种两个进程，应用程序可以—

将“seed-mysimulation”的SHA2-256哈希值作为新种子，
用新种子和计数器0初始化第一个进程的PRNG，并且
用新种子加1和计数器0初始化第二个进程的PRNG。
一些动态线程（任务并行）平台采用任务调度程序，其中任务或子任务（有时称为strand或fiber）不分配给特定的操作系统进程或线程。为了在这些平台上确保可重复的“随机性”，PRNG必须分配给任务（而不是系统进程或线程），并且不与任务共享，每个任务的PRNG都可以按照“通用情况”步骤（其中任务的唯一编号也称为谱系）进行初始化（Leierson等人，2012）⁽¹⁰⁾。

编程语言中的现有RNG API

尽可能，应用程序应使用现有的库和技术来处理加密和高质量的RNG。下表列出了流行编程语言中此类RNG的应用程序编程接口（API）。

“高质量”列中提到的PRNG需要使用种子进行初始化（参见“非加密PRNG的种子生成”）。
此处提及的第三方库并不意味着该库是特定用途的最佳选择。该列表不详尽。
另请参阅Paragon的博文，讨论现有的加密RNG。

语言	加密	高质量
.NET（包括C#和VB.NET）（H）	`System.Security.Cryptography`命名空间中的`RandomNumberGenerator.Create()`；airbreather/AirBreather.Common库（CryptographicRandomGenerator）	`XoshiroPRNG.Net`包（XoRoShiRo128starstar、XoShiRo256plus、XoShiRo256starstar）；`Data.HashFunction.MurmurHash`或`Data.HashFunction.CityHash`包（哈希字符串`seed + "_" + counter`）
C/C++（G）	（C）	`xoroshiro128plusplus.c`；`xoshiro256starstar.c`
Python（A）	`secrets.SystemRandom`（Python 3.6起）；`os.urandom()`	ihaque/xorshift库（默认种子使用`os.urandom()`）；`numpy.random.Generator`，使用`Philox`或`SFC64`（1.7版本起）；`hashlib.md5(b"%d_%d" % (seed, counter)).digest()`, `hashlib.sha1(b"%d_%d" % (seed, counter)).digest()`
Java（A）（D）	（C）；`java.security.SecureRandom`（F）	`it.unimi.dsi/dsiutils` artifact（XoRoShiRo128PlusPlusRandom, XoRoShiRo128StarStarRandom, XoShiRo256StarStarRandom, XorShift1024StarPhiRandom）；`org.apache.commons/commons-rng-simple` artifact（`RandomSource` of `SFC_64`, `XO_RO_SHI_RO_128_PP`, `XO_RO_SHI_RO_128_SS`, `XO_SHI_RO_256_PP`, or `XO_SHI_RO_256_SS`）
JavaScript（B）	`crypto.randomBytes(byteCount)`（仅node.js）；`random-number-csprng`包（仅node.js）；`crypto.getRandomValues()`（Web）	`xoroshiro128starstar`包；`md5`包（`md5(seed+"_"+counter, {asBytes: true})`）；`murmurhash3js`包（`murmurhash3js.x86.hash32(seed+"_"+counter)`）；`crypto.createHash("sha1")`（仅node.js）
Ruby（A）（E）	（C）；`SecureRandom.rand()`（0或大于0且小于1）（E）；`SecureRandom.rand(N)`（整数）（E）（两者都需要`require 'securerandom'`）；`sysrandom` gem	`Digest::MD5.digest("#{seed}_#{counter}")`, `Digest::SHA1.digest("#{seed}_#{counter}")`（两者都需要`require 'digest'`）
PHP（A）	`random_int()`, `random_bytes()`（两者都自PHP 7起可用）	`md5($seed.'_'.$counter, true)`; `sha1($seed.'_'.$counter, true)`
Go	`crypto/rand`包	`crypto/md5`包中的`md5.Sum`或`crypto/sha1`包中的`sha1.Sum`（两者都需要哈希字节数组`seed + "_" + counter`）
Rust	（C）	`rand_xoshiro` crate（Xoroshiro128PlusPlus, Xoshiro256PlusPlus, Xoshiro256StarStar, Xoshiro512StarStar）
Perl	`Crypt::URandom`模块	`Crypt::Digest::MD5`模块（`md5($seed.'_'.$counter)`）；`Digest::SHA`模块（`sha1($seed.'_'.$counter)`）；`Digest::MurmurHash3`模块（`murmurhash3($seed.'_'.$counter)`）
其他语言	（C）	用MurmurHash3、xxHash64、CityHash、MD5或SHA-1哈希字符串`seed + "_" + counter`

（A）Python和Ruby的最新通用RNG实现是Mersenne Twister，这对于高质量RNG来说不是首选。PHP的mt_rand()实现了或曾经实现了一个有缺陷的Mersenne Twister版本。
（B）JavaScript的Math.random()（范围为0或大于0且小于1）在V8引擎、Firefox和其他一些现代浏览器（截至2017年末）中使用了xorshift128+（或其变体）实现；然而，Math.random()使用的是“依赖于实现的算法或策略”（参见ECMAScript sec. 20.2.2.27）。
（C）加密RNG实现可以—
- 在Windows 7及更高版本上调用BCryptGenRandom API，
并且只有在现有方法不足以满足应用程序需求时才使用其他技术。但遗憾的是，与台式电脑和智能手机等通用计算设备相比，资源受限设备（“嵌入式”设备）不太可能提供加密RNG（Wetzels 2017）⁽²²⁾，尽管存在在Arduino上实现加密RNG的方法（Peng 2017）⁽²³⁾。
（D）Java的java.util.Random类使用48位种子，因此不被认为是高质量RNG。然而，java.util.Random的子类可能被实现为高质量RNG。
（E）Ruby的SecureRandom.rand方法提供了一个漂亮而简单的API来生成随机数，在我看来。即，rand()返回一个0或大于0且小于1的数字，而rand(N)返回一个0或大于0且小于N的整数。
（F）在Java 8及更高版本中，使用SecureRandom.getInstanceStrong()。在8之前的Java版本中，调用SecureRandom.getInstance("NativePRNGNonBlocking")，如果失败，则调用SecureRandom.getInstance("NativePRNG")。对于Android，特别是4.3及更早版本，请参阅（Klyubin 2013）⁽²⁴⁾。不建议使用"SHA1PRNG"作为SecureRandom实现，因为截至2013年，其播种和RNG质量的实现存在弱点（Michaelis等人，2013）⁽²⁵⁾。
（G）C++11引入了std::random_device，但其规范仍有很大改进空间。例如，std::random_device可能在没有太多警告的情况下回退到质量未知的PRNG。充其量，std::random_device不应被用于除补充其他生成随机行为数字的技术之外的任何用途。
（H）.NET Framework的System.Random类使用最多32位的种子，因此不被认为是高质量RNG。然而，System.Random的子类可能被实现为高质量RNG。

哈希函数

哈希函数是一个函数，它接收任意大小的输入（例如，一个8位字节数组或一个字符序列），并返回一个固定位数的输出。该输出也称为哈希码。

为伪随机数生成目的

哈希码的单个比特可以作为伪随机数，或者哈希码可以作为PRNG的种子。
好的哈希函数包括加密哈希函数（例如，SHA2-256，BLAKE2）和其他倾向于为接近的输入生成高度分散的哈希码的哈希函数。
差的哈希函数包括线性PRNG，如LCG和Xorshift系列。

哈希函数用于其他目的（例如，数据查找和数据完整性）的用法超出了本文档的范围。请参阅我关于哈希函数的说明。

过程噪声函数

噪声是图像、声音和其他数据中的随机变化。⁽²⁶⁾

噪声函数类似于哈希函数；它接收一个n维点，以及可选的附加数据，并输出一个伪随机数。⁽²⁷⁾ 噪声函数生成过程噪声，如细胞噪声、值噪声和梯度噪声（包括Perlin噪声）。如果噪声函数接收附加数据，则该数据—

应包括随机生成或伪随机的数字，并且
在使用噪声函数生成特定目的（例如，为给定地图生成地形）时，不应从一次运行到下一次运行而变化。

伪随机函数

伪随机函数是一种哈希函数，它接收—

一个秘密（例如，密码或长期密钥），以及
附加数据，如盐（用于缓解预计算攻击）或随机数，

并输出一个伪随机数。（如果输出是加密密钥，则该函数也称为密钥派生函数；请参阅NIST SP 800-108。）一些伪随机函数故意花费大量时间来计算其输出；这些函数的设计目标是，当秘密是密码或容易猜测时使用——这些函数的例子包括PBKDF2（RFC 2898）、scrypt（RFC 7914）和Ethash。伪随机函数也用于工作量证明，如RFC 8019 sec. 4.4中所述。

RNG主题

本节讨论了使用和选择RNG的几个重要问题，包括洗牌或生成“唯一”随机标识符时需要考虑的事项。

洗牌

在一个包含N个不同项目的列表中，有N的阶乘（即，1 * 2 * ... * N，或N!）种排列方式。这些方式称为排列⁽²⁸⁾。

实际上，应用程序可以通过执行Fisher–Yates洗牌来洗牌列表，不幸的是，这种洗牌很容易出错——参见（Atwood 2007）⁽²⁹⁾——并且在我的另一篇文档中已正确实现。

然而，如果一个PRNG允许的种子数量（因此可以产生的数字序列数量）少于排列的数量，那么某些排列是该PRNG在洗牌该列表时无法选择的。（这与生成列表的所有排列不同，对于足够大的列表，任何计算机都无法在合理的时间内完成。）

另一方面，对于足够大的列表，通常使洗牌行为随机比从所有排列中选择更重要。

洗牌列表的应用程序可以—

使用加密RNG，最好是安全强度为b比特或更高的RNG，或者
如果非加密RNG在其他方面是合适的，使用一个高质量PRNG，它—
- 具有b比特或更大的状态，并且
- 使用源于至少b位熵，“随机性”的数据进行初始化，或者

对于洗牌目的，b通常可以通过取n的阶乘减1（其中n是列表的大小）并计算其比特长度来计算。Python的一个例子是b = (math.factorial(n)-1).bit_length()。另请参阅（van Staveren 2000，“Lack of randomness”）⁽³⁰⁾。对于洗牌目的，在排列多样性不重要的情况下，应用程序可以将b限制为256或更大。对于其他采样任务，以下Python示例显示了如何计算b

从n个不同项目中随机选择k个，并按随机顺序：b = ((math.factorial(n)/math.factorial(n-k))-1).bit_length()。
从n个不同项目中随机选择k个，不关心顺序（RFC 3797，sec. 3.3）：b = ((math.factorial(n)/(math.factorial(k) * math.factorial(n-k)))-1).bit_length()。
洗牌d个相同的包含c个项目的列表：b = ((math.factorial(d*c)/ (math.factorial(d)**c))-1).bit_length()。

唯一随机标识符

一些应用程序需要生成唯一标识符，特别是用于标识数据库记录或其他共享资源。唯一值的示例包括自动增量数字、顺序分配的数字、数据库表的主键以及它们的组合。应用程序也生成了唯一值。

以下是一些在生成唯一标识符时需要考虑的问题

应用程序是否可以轻松地在所需范围和作用域内检查标识符的唯一性（例如，检查具有该标识符的文件或数据库记录是否已存在）⁽³¹⁾？
应用程序是否可以容忍为不同资源生成相同标识符的风险⁽³²⁾？
标识符是否必须难以猜测，仅仅是“看起来随机”，还是两者都不是？
标识符是否必须由最终用户键入或以其他方式中继⁽³³⁾？
标识符所标识的资源是否对任何知道该标识符的人可用（即使未登录或未经任何方式授权）？⁽³⁴⁾
标识符是否必须易于记忆？

一些应用程序也可能关心“唯一随机”值。但通常，兼具唯一和随机的值是不可能的。因此，想要“唯一随机”值的应用程序必须要么接受仅“看起来随机”的数字；要么检查或容忍可能的重复；要么将随机生成的数字与唯一数字配对。

如果应用程序可以接受“看起来随机”的唯一整数

应用程序可以生成一个N位整数，并将其传递给一个将N位整数映射到N位整数且可逆的函数（也称为具有可逆操作的混合函数；参见B. Mulvey的“哈希函数”）。这包括使用唯一整数作为“全周期”线性PRNG的种子，即，一个线性PRNG在重复之前会遍历所有N位整数一次⁽³⁵⁾。
应用程序可以通过以下方式生成大于0且小于K的唯一整数
1. 设置U为0，并选择F，一个前面描述的N位函数，其中N是存储数字K-1所需的位数。
2. 计算F(U)，然后将U加1。如果F的结果小于K，则输出该结果；否则，重复此步骤。
3. 根据需要重复上一步以生成其他唯一整数。

生成唯一标识符的应用程序应如下操作

如果应用程序对上述问题1或2回答“是”
- 并且对问题5回答“是”：使用加密RNG生成一个128位或更长的随机整数。
- 并且对问题5回答“否”：使用加密RNG生成一个32位或更长的随机整数。
否则
- 如果标识符不必难以猜测：使用唯一整数（是自然唯一的，还是经过唯一性检查的随机生成的数字）。
- 如果必须难以猜测：使用唯一整数，后面跟着使用加密RNG生成的随机整数（随机整数的长度取决于上述问题5的答案）。

本节不讨论如何将唯一值格式化为文本字符串（例如，十六进制或字母数字字符串），因为最终，这样做与将唯一值一对一映射到格式化字符串（也将是唯一的）相同。

可验证的随机数

可验证的随机数是随机生成的数字（例如，PRNG的种子），这些数字连同验证其生成所需的所有信息一起被披露。通常，此类信息包括随机生成的数值和/或将来需要确定并公开披露的不确定数据。生成可验证随机数（与单独的加密RNG不同）的技术用于任何一方单独无法被信任来随机生成数字的情况。公开披露的可验证随机数不应用于加密密钥或其他秘密参数。

示例

RFC 3797描述了可验证随机性的生成，其中描述了互联网工程任务组（IETF）提名委员会（NomCom）的选择过程。
可验证延迟函数计算一个输出以及一个证明该输出被正确计算的证明；这些函数故意花费更多时间来计算输出（例如，从公共数据生成随机行为的数字），而不是验证其正确性。⁽³⁶⁾ 在许多情况下，此类函数故意花费的时间超过了为该函数贡献随机性的允许时间。⁽³⁷⁾
在所谓的承诺方案中，一个计算机生成要承诺的数据（例如，随机生成的数字或国际象棋走法），然后公开其哈希码或数字签名（承诺），并仅在稍后向所有参与者公开承诺的数据（以及任何必要的其他信息，以验证数据在此期间未被更改）。承诺方案的例子是基于哈希的承诺。⁽³⁷⁾
所谓的心智纸牌游戏（心智扑克）方案可用于网络游戏中，其中一副牌必须被洗牌并分发给玩家，以便某些牌的身份被一些但不是所有玩家知晓。⁽³⁷⁾

新RNG API的实现指南

本节包含针对那些寻求实现供广泛重用（例如，在编程语言的标准库中）的RNG的指南。如前所述，应用程序应尽可能使用现有的RNG实现。

本节包含对加密和高质量RNG的建议要求，新编程语言可以选择采纳。

加密RNG：要求

加密RNG生成随机比特，这些比特的行为类似于独立的均匀随机比特，以至于外部方在正确猜测该RNG的先前或未来未见输出比特方面，即使知道了RNG的工作原理和/或该RNG的极多输出，或者在安全受到损害后（例如，读取其内部状态）猜测该RNG的先前未见输出比特，也只有微乎其微的优势。⁽³⁸⁾

如果加密RNG实现使用PRNG

让S成为RNG的安全强度。S至少为128位，最好至少为256位。
在RNG生成伪随机数之前，RNG必须已初始化到一个状态，该状态最终来源于数据，这些数据整体上比生成S个独立均匀随机比特的理想过程更难猜测。⁽³⁹⁾

加密RNG不需要重新播种。

示例： 以下是加密RNG的示例—

随机性提取器或加密哈希函数，它们将来自两个或多个非确定性源的难以预测的信号作为输入。
D.J. Bernstein在其博客（Bernstein 2017）⁽⁴⁰⁾中描述的“快速密钥擦除”生成器。
NIST SP 800-90A中指定的Hash_DRBG和HMAC_DRBG生成器。SP 800-90系列更详细地说明了如何构建适合信息安全的RNG，并启发了本节的许多内容。
由两个或多个独立初始化的不同设计的加密RNG组成的RNG。⁽⁴¹⁾
RFC 8937描述了一个RNG，它将另一个加密RNG的输出与从长期密钥派生的秘密值进行哈希处理。

高质量RNG：要求

如果PRNG—

生成行为类似于独立均匀随机比特的比特（至少在信息安全之外的大多数实际用途中），
PRNG允许的不同种子的数量（在不缩短或压缩这些种子的前提下）为2⁶³或更多（即，PRNG可以产生至少2⁶³个不同的数字序列，通常只有当PRNG至少有63位状态时才能做到这一点），并且
它—
- 提供多个序列，这些序列对每个种子都不同，每个序列至少包含2⁶⁴个数字，不重叠，并且其行为类似于独立的数字序列（至少在信息安全之外的大多数实际用途中），
- 最大“随机”数字周期长度等于PRNG允许的不同种子的数量，或
- 最小“随机”数字周期长度为2¹²⁷或更大。

每个加密RNG也是高质量RNG。

在非加密PRNG适用的情况下，应用程序应尽可能使用允许2¹²⁷或更多种子的高质量PRNG。（这是一个建议，因为如上所述，高质量PRNG只需要允许2⁶³或更多种子。）

示例： 高质量PRNG的例子包括xoshiro256**、xoroshiro128**、xoroshiro128++、Philox4×64-7和SFC64。我在单独的页面中提供了更多示例。

PRNG的设计

以下是实现PRNG的一些方法

作为一个*有状态*对象，它存储内部状态并在每次生成“随机”数字时转换该状态。这种PRNG通过将*种子*转换为内部状态来初始化。
作为一个（无状态）函数，它转换内部状态并输出“随机”数字和转换后的状态。这种设计在Haskell和其他函数式编程语言中很常见。
作为一个（无状态）“可分割PRNG”，在我关于PRNG测试的文档中有更详细的描述。

实现新的RNG API

为应用程序可重用而设计的编程语言API可以使用以下指南来实现RNG—

RNG API可以包含一个方法，该方法用随机比特完全填充一个或多个内存单元（例如，8位字节）。参见示例1。
如果API实现了一个自动播种的RNG，它不应允许应用程序使用种子来初始化同一个RNG以获得可重复的“随机性”⁽⁴²⁾（它可以提供一个单独的PRNG来接受这样的种子）。参见示例2。
如果API提供了一个应用程序可以播种以获得可重复“随机性”的PRNG，它应该记录该PRNG以及API提供的任何使用该PRNG的方法（例如，洗牌和高斯数生成），并且不应以改变给定种子下它们提供的“随机”数字的方式来更改该PRNG或这些方法。参见示例2。
新编程语言的标准库应包含以下方法来生成行为类似独立均匀分布的数字（有关详细信息，请参阅我关于随机化和采样方法的文档）。
- 四种整数方法：0到n（包括n），0到n（不包括n），a到b（包括b），以及a到b（不包括b）。
- 四种实数方法，边界为a和b，包含或不包含端点。

示例

C语言的内存填充RNG方法可能如下所示：int random(uint8_t[] bytes, size_t size);，其中bytes是指向8位字节数组的指针，size是要生成的随机8位字节的数量，如果方法成功则返回0，否则返回非零。
遵循这些指南的Java API可以包含两个类：一个RandomGen类，它实现一个未指定但通用的RNG；一个RandomStable类，它实现一个已记录且将来不会改变的SFC64 PRNG。RandomStable包含一个接受种子以实现可重复“随机性”的构造函数，而RandomGen则不包含。两个类都包含点4中所述的方法，但RandomStable指定了这些方法的具体算法，而RandomGen则不。将来任何时候，RandomGen都可以更改其实现以使用不同的RNG，同时保持向后兼容；而RandomStable必须始终使用相同的算法才能保持向后兼容，特别是因为它接受种子以实现可重复“随机性”。

致谢

我感谢—

CodeProject版本页面的评论者（以及我在CodeProject上的类似文章），包括“Cryptonite”和成员3027120，
Sebastiano Vigna，
Severin Pappadeux，以及
Lee Daniel Crocker，他审阅了本文档并提出了意见。

注释

⁽¹⁾ 另请参阅Stack Overflow上标题为“Matlab rand and c++ rand()”的问题。
⁽²⁾ 区分加密和非加密RNG似乎是自然的，因为许多编程语言提供通用RNG（如C语言的rand或Java的java.util.Random），有时还提供用于信息安全目的的RNG（如Ruby的SecureRandom）。
⁽³⁾ 例如，参见F. Dörre和V. Klebanov，“Practical Detection of Entropy Loss in Pseudo-Random Number Generators”，2016。
⁽⁴⁾ 本文档不将产生非均匀分布数字或信号的项目视为RNG。（例如，高斯和类似噪声发生器不被视为RNG。）然而，其中许多项目通常作为源，可以通过*随机性提取*技术（参见“种子生成”）从中派生出均匀随机行为的数字。
⁽⁵⁾ 另请参阅FIPS 200定义（“保护信息和信息系统免受未经授权的访问、使用、披露、破坏、修改或销毁，以提供机密性、完整性和可用性”）以及ISO/IEC 27000。
⁽⁶⁾ 然而，GLSL的一些版本（特别是WebGL 1.0使用的GLSL ES 1.0）可能支持范围受限的整数（低至-1024至1024），而不是通常常见的32位或更大整数，这使得编写用于生成伪随机数的哈希函数变得困难。应用程序应选择能够提供可接受的“随机”数字的哈希函数，无论支持何种数字。

GLSL和其他片段或像素着色器支持随机性的另一种方法是让着色器对每个像素中的随机数据的“噪声纹理”进行采样；例如，C. Peters，“免费蓝噪声纹理”，Moments in Graphics，2016年12月22日，讨论了如何通过这种方式采样所谓的“蓝噪声”。

另请参阅N. Reed，“Quick And Easy GPU Random Numbers In D3D11”，Nathan Reed的编码博客，2013年1月12日。

⁽⁷⁾ 有关更多信息，请参阅Bruce Dawson的“浮点数确定性”，白皮书“NVIDIA GPU的浮点数和IEEE 754合规性”，以及Intel网络研讨会。
⁽⁸⁾ 对于整数，这个问题也会发生，但通常仅限于整数除法或余数后的舍入问题，不同编程语言的答案不同。
⁽⁹⁾ 定点数是存储1/n倍数的整数（例如1/10000、1/256或1/65536）。与浮点数不同，它们的精度不随数字变化。 “蝴蝶效应——《不可思议的机器》和《Contraption Maker》中的确定性物理学”是一个展示定点数如何有助于可重复性的用例。我写了一个Python实现定点数的示例。
⁽¹⁰⁾ Leierson, C.E., et al., "Deterministic Parallel Random-Number Generation for Dynamic Multithreading Platforms", 2012。
⁽¹¹⁾ Müller, S. "CPU Time Jitter Based Non-Physical True Random Number Generator"。
⁽¹²⁾ Liebow-Feeser, J., "Randomness 101: LavaRand in Production", blog.cloudflare.com, 2017年11月6日。
⁽¹³⁾ Liebow-Feeser, J., "LavaRand in Production: The Nitty-Gritty Technical Details", blog.cloudflare.com, 2017年11月6日。
⁽¹⁴⁾ 与其生成种子，不如说这些步骤可以模拟一个独立均匀随机选择的数字源。然而，这通常比使用PRNG模拟该源要慢。
⁽¹⁵⁾ 例如，Stack Overflow上的许多问题强调了每次需要伪随机数时都创建一个新的.NET FrameworkSystem.Random实例的陷阱，而不是只在应用程序中创建一次。另请参见Johansen, R. S., “可重复随机数入门”，Unity Blog，2015年1月7日。
⁽¹⁶⁾ Salmon, J.K.; Moraes, M.A.; et al., "Parallel Random Numbers: As Easy as 1, 2, 3", 2011。
⁽¹⁷⁾ P. L'Ecuyer, D. Munger, et al. "Random Numbers for Parallel Computers: Requirements and Methods, With Emphasis on GPUs", 2015年4月17日，第4节，更详细地介绍了为并行生成伪随机数初始化PRNG的方法，包括如何在需要时确保可重复的“随机性”。
⁽¹⁸⁾ 对于单周期PRNG，N个进程每个生成L个数字，PRNG周期长度为P，重叠的概率最多为N*N*L/P（S. Vigna，“On the probability of overlap of random subsequences of pseudorandom number generators”，Information Processing Letters 158（2020））。使用两个或多个PRNG设计可以降低由于特定PRNG设计引起的相关性风险。有关进一步讨论和结合两种不同PRNG设计的PRNG示例，请参阅Agner Fog，“Pseudo-Random Number Generators for Vector Processors and Multicore Processors”，Journal of Modern Applied Statistical Methods 14(1)，文章23（2015）。
⁽¹⁹⁾ Bauke and Mertens, "Random numbers for large-scale distributed Monte Carlo simulations", 2007。
⁽²⁰⁾ 除了种子之外，还有其他项目一起作为域分隔标签（参见，例如，工作草案“draft-irtf-cfrg-hash-to-curve”）。请注意以下几点—
- 另请参阅Matsumoto, M., et al., "Common defects in initialization of pseudorandom number generators", ACM Transactions on Modeling and Computer Simulation 17(4), Sep. 2007。
⁽²¹⁾ 不建议使用类似的/dev/random，因为它在某些实现中可能会阻塞数秒钟，尤其是在随机性不足的情况下。另请参阅“关于/dev/urandom的神话”。
⁽²²⁾ Wetzels, J., "33C3: Analyzing Embedded Operating System Random Number Generators", samvartaka.github.io, 2017年1月3日。
⁽²³⁾ B. Peng, "Two Fast Methods of Generating True Random Numbers on the Arduino", GitHub Gist, December 2017。
⁽²⁴⁾ A. Klyubin, "Some SecureRandom Thoughts", Android Developers Blog, 2013年8月14日。
⁽²⁵⁾ Michaelis, K., Meyer, C., and Schwenk, J. "Randomly Failed! The State of Randomness in Current Java Implementations", 2013。
⁽²⁶⁾ 噪声有许多种类，例如过程噪声（包括Perlin噪声、细胞噪声和值噪声）、彩色噪声（包括白噪声和粉红噪声）、周期性噪声以及遵循高斯或其他概率分布的噪声。另请参阅Red Blob Games的两个文章：“噪声函数和地图生成”和“从噪声函数制作地图”。
⁽²⁷⁾ 噪声函数包括组合噪声函数多个输出的函数，包括通过分数布朗运动。根据定义，噪声函数对相同的输入提供相同的输出。
⁽²⁸⁾ 更一般地说，一个列表有N! / (W_1! * W_2! * ... * W_K!)个排列（一个多项式系数），其中N是列表的大小，K是列表中不同项目的数量，而W_i是项目i在列表中出现的次数。然而，这个数字永远不会超过N!，并建议使用较少的随机性，因此应用程序不必使用这个更复杂的公式，并且可以假设一个列表有N!个排列，即使它的某些项目出现多次。
⁽²⁹⁾ Atwood, Jeff. “天真之害”，2007年12月7日。
⁽³⁰⁾ van Staveren, Hans. "Big Deal: A new program for dealing bridge hands", 2000年9月8日。
⁽³¹⁾ 对于跨多个计算机（例如，服务器）分发的应用程序，如果每个计算机都分配了一个来自中央数据库的唯一值，那么此检查会更容易，因为这样计算机就可以使用该唯一值作为其生成的唯一标识符的一部分，并确保标识符在应用程序中是唯一的，而无需进一步联系其他计算机或中央数据库。一个例子是Twitter的Snowflake服务。
⁽³²⁾ 理论上，生成两个或多个相同大小的随机整数有产生重复数字的风险。然而，随着大小的增加，这种风险会降低（参见“生日问题”）。例如，理论上，在生成—
- 大约930万亿亿个随机192位整数后，应用程序有50%的可能性出现重复数字。
⁽³³⁾ 如果应用程序期望最终用户键入唯一标识符，它可能会发现非常长的唯一标识符不适合它（例如，128位数字需要32个十六进制字符）。有办法处理这些和其他长标识符，包括（1）用连字符、空格或其他字符分隔标识符的易记块（例如，“ABCDEF”变为“ABC-DEF”）；（2）从易记词序列生成标识符（如Electrum或Bitcoin的BIP39）；或（3）在标识符末尾添加所谓的“校验和数字”以防止输入错误。在决定使用比本文档建议的更短的标识符之前，应用程序应考虑尝试（1）或（2）。
⁽³⁴⁾ 请注意，如果应用程序通过易于猜测的标识符允许访问敏感资源，但没有任何访问控制检查，则可能发生不安全的直接对象引用问题。
⁽³⁵⁾ “全周期”线性PRNG包括所谓的线性同余生成器，其模数为2的幂。这些生成器的例子请参见Steele和Vigna的“Computationally easy, spectrally good multipliers for congruential pseudorandom number generators”，arXiv:2001.05304 [cs.DS]中的表3、5、7和8。
⁽³⁶⁾ 可验证延迟函数与工作量证明不同，后者可能有多个正确答案。这些函数首次在Boneh, D., Bonneau, J., et al., "Verifiable Delay Functions", 2018中正式定义，但此类函数在Lenstra, A.K., Wesolowski, B., "A random zoo: sloth, unicorn, and trx", 2015中出现。
⁽³⁷⁾ 本页不讨论如何构建使用可验证延迟函数、承诺方案或心智纸牌游戏方案的协议，特别是因为此类协议尚未标准化供一般使用，并且很少有其实现在生产环境中。
⁽³⁸⁾ 实现加密RNG涉及许多安全注意事项，包括以下几点—
1. 如果应用程序在其中存储了加密RNG状态的同一操作系统进程中运行来自不受信任来源的代码，那么恶意代码有可能通过侧信道攻击读取该状态。不应在这样的进程中实现加密RNG。参见（A），另请参见（B）。
2. 由于进程fork或虚拟机快照重置，加密RNG的状态可能会被重复使用。参见（C）和（D）的示例。
3. 如果加密RNG不是“恒定时间”（RNG依赖于数据），其时序差异可能会在安全攻击中被利用。
（A）“Post-Spectre Threat Model Re-Think”，Chromium源代码存储库（2018年5月29日）。
（B）Bernstein, D.J. "Entropy Attacks!", 2014年2月5日。
（C）Everspaugh, A., Zhai, Y., et al. "Not-So-Random Numbers in Virtualized Linux and the Whirlwind RNG", 2014。
（D）Ristenpart, T., Yilek, S. "When Good Randomness Goes Bad: Virtual Machine Reset Vulnerabilities and Hedging Deployed Cryptography", 2010。
有关安全RNG的详细概念，请参见Coretti, Dodis, et al., "Seedless Fruit is the Sweetest: Random Number Generation, Revisited", 2019。
⁽³⁹⁾ 这些数据可以来自非确定性源，还可以包括进程标识符、时间戳、环境变量、伪随机数、虚拟机客户标识符和/或与会话或RNG实例相关的其他特定数据。另请参阅NIST SP 800-90A和上一条注释。
⁽⁴⁰⁾ Bernstein, D.J. "Fast-key-erasure random number generators", 2017年6月23日。
⁽⁴¹⁾ 一个例子是“收缩发生器”技术，用于组合两个RNG；有关更多信息，请参阅J. D. Cook，“Using one RNG to sample another”，2019年6月4日。
⁽⁴²⁾ 允许应用程序这样做会妨碍前向兼容性——API将无法自由地更改RNG的实现方式（例如，使用加密或其他“更好”的RNG），或对使用该RNG的方法（例如，洗牌和高斯数生成）进行改进或错误修复。（作为显著的例子，V8 JavaScript引擎最近将其Math.random()实现更改为使用xorshift128+的变体，这向后兼容，因为JavaScript中没有任何内容允许Math.random()被播种。）尽管如此，API仍然可以允许应用程序提供额外的输入（“熵”）来增加RNG的随机性，而不是确保可重复性。