计算机并非随机。恰恰相反，硬件设计人员会非常努力地确保计算机每次都能以相同的方式运行所有程序。因此，当程序确实需要随机数时，就需要额外的努力。传统上，计算机科学家和编程语言在两种不同类型的随机数之间进行了区分：统计随机性和加密随机性。在 Go 中，它们分别由 math/rand 和 crypto/rand 提供。这篇博文将介绍 Go 1.22 如何通过在 math/rand（以及如我们 上一篇博文中所述的 math/rand/v2）中使用加密随机数源来使两者更加接近。其结果是更好的随机性，并且当开发人员不小心将 math/rand 用作 crypto/rand 时，造成的损害要小得多。

在我们解释 Go 1.22 做了什么之前，让我们先仔细看看统计随机性与加密随机性的区别。

统计随机性

通过基本统计测试的随机数通常适用于模拟、采样、数值分析、非加密随机算法、随机测试、打乱输入以及随机指数退避等用例。非常基本且易于计算的数学公式足以满足这些用例。然而，由于方法非常简单，因此能够看到足够多值的观察者通常可以预测序列的其余部分。

基本上所有编程环境都提供了一种生成统计随机数的机制，该机制追溯到 C 语言的 Research Unix 第三版（V3），该版本添加了一对函数：srand 和 rand。手册页中包含一条注释，写道：

警告：编写此例程的作者多年来一直在编写随机数生成器，从未写过一个真正有效的。

这条注释部分是一个笑话，但也是一个承认这类生成器本质上不是随机的。

生成器的源代码清楚地表明其多么简单。将其从 PDP-11 汇编语言翻译成现代 C 语言，如下所示：

uint16 ranx;

void
srand(uint16 seed)
{
    ranx = seed;
}

int16
rand(void)
{
    ranx = 13077*ranx + 6925;
    return ranx & ~0x8000;
}

调用 srand 使用单个整数种子来播种生成器，rand 返回生成器的下一个数字。返回语句中的 AND 操作清除符号位，以确保结果为正。

此函数是线性同余生成器 (LCG) 的通用类别的一个实例，Knuth 在其《计算机程序设计艺术》第 2 卷第 3.2.1 节中对此进行了分析。LCG 的主要优点是可以通过选择常数使其在重复之前发出所有可能的输出值一次，就像 Unix 实现那样处理 15 位输出。然而，LCG 的一个严重问题是状态的高位完全不影响低位，因此序列截断到 k 位必然会以较小的周期重复。低位必须切换：0、1、0、1、0、1。低两位必须向上或向下计数：0、1、2、3、0、1、2、3，或者 0、3、2、1、0、3、2、1。有四种可能的 3 位序列；原始 Unix 实现重复 0、5、6、3、4、1、2、7。（这些问题可以通过对素数取模来避免，但当时成本会很高。请参阅 S. K. Park 和 K. W. Miller 1988 年的 CACM 论文“随机数生成器：好的很难找到”进行简要分析，以及 Knuth 第 2 卷的第一章进行更详细的分析。）

即使存在这些已知问题，srand 和 rand 函数也被包含在第一个 C 标准中，并且几乎所有语言自那时以来都包含了等效的功能。LCG 曾是主要的实现策略，尽管由于一些重要的缺点，它们已不再受欢迎。一个重要的现有用途是 java.util.Random，它为 java.lang.Math.random 提供支持。

从上面的实现中，您还可以看到内部状态完全被 rand 的结果暴露。了解算法并看到单个结果的观察者可以轻松计算所有未来的结果。如果您运行一个服务器，该服务器会计算一些公开的随机值和一些必须保密的随机值，使用这种生成器将是灾难性的：秘密将不再是秘密。

比原始 Unix 生成器更现代的随机生成器并不那么糟糕，但它们仍然不是完全不可预测的。为了说明这一点，接下来我们将看看 Go 1 中的原始 math/rand 生成器以及我们在 math/rand/v2 中添加的 PCG 生成器。

Go 1 生成器

Go 1 的 math/rand 中使用的生成器是所谓的线性反馈移位寄存器的一个实例。该算法基于 George Marsaglia 的一个想法，由 Don Mitchell 和 Jim Reeds 进行了调整，然后由 Ken Thompson 为 Plan 9 和 Go 进一步定制。它没有官方名称，因此这篇博文称其为 Go 1 生成器。

Go 1 生成器的内部状态是一个包含 607 个 uint64 的切片 vec。在该切片中有两个特殊的元素：“tap”（抽头）是 vec[606]，即最后一个元素；“feed”（馈送）是 vec[334]。为了生成下一个随机数，生成器将 tap 和 feed 相加生成一个值 x，将 x 存回 feed，将整个切片向右移动一位（tap 移动到 vec[0]，vec[i] 移动到 vec[i+1]），然后返回 x。该生成器被称为“线性反馈”，因为 tap 被加到 feed 上；整个状态是一个“移位寄存器”，因为每一步都会移动切片元素。

当然，实际移动每个切片元素代价太高，因此实现会将切片数据保留在原位，并在每一步将 tap 和 feed 的位置向后移动。代码如下所示：

func (r *rngSource) Uint64() uint64 {
    r.tap--
    if r.tap < 0 {
        r.tap += len(r.vec)
    }

    r.feed--
    if r.feed < 0 {
        r.feed += len(r.vec)
    }

    x := r.vec[r.feed] + r.vec[r.tap]
    r.vec[r.feed] = x
    return uint64(x)
}

生成下一个数字非常便宜：两次减法、两次条件加法、两次加载、一次加法、一次存储。

不幸的是，由于生成器直接返回其内部状态向量中的一个切片元素，读取该生成器的 607 个值会完全暴露其所有状态。有了这些值，您可以通过填充自己的 vec 并运行算法来预测所有未来值。您还可以通过向后运行算法（从 feed 中减去 tap 并将切片向左移动）来恢复所有先前的值。

作为完整演示，这是一个不安全程序，它生成伪随机认证令牌，并附有根据一系列早期令牌预测下一个令牌的代码。正如您所见，Go 1 生成器根本不提供安全性（它本来就没有这个目的）。生成的数字的质量也取决于 vec 的初始设置。

PCG 生成器

对于 math/rand/v2，我们希望提供一个更现代的统计随机生成器，并最终选择了 Melissa O’Neill 的 PCG 算法，该算法于 2014 年发表在她题为“PCG：用于随机数生成的一系列简单、快速、节省空间的统计良好算法”的论文中。该论文中的详尽分析可能一开始会让人难以注意到生成器有多么简单：PCG 是一个后处理的 128 位 LCG。

如果状态 p.x 是一个 uint128（假设），计算下一个值的代码将是

const (
    pcgM = 0x2360ed051fc65da44385df649fccf645
    pcgA = 0x5851f42d4c957f2d14057b7ef767814f
)

type PCG struct {
    x uint128
}

func (p *PCG) Uint64() uint64 {
    p.x = p.x * pcgM + pcgA
    return scramble(p.x)
}

整个状态是一个单一的 128 位数字，更新是一个 128 位乘法和加法。在返回语句中，scramble 函数将 128 位状态降低到 64 位状态。原始 PCG 使用（再次使用假设的 uint128 类型）

func scramble(x uint128) uint64 {
    return bits.RotateLeft(uint64(x>>64) ^ uint64(x), -int(x>>122))
}

此代码将 128 位状态的两个半部分进行异或，然后根据状态的最高六位旋转结果。此版本称为 PCG-XSL-RR，代表“xor shift low, right rotate”（异或低位移位，右旋转）。

基于O’Neill 在提案讨论期间的建议，Go 的 PCG 使用一种基于乘法的新 scramble 函数，该函数更积极地混合位。

func scramble(x uint128) uint64 {
    hi, lo := uint64(x>>64), uint64(x)
    hi ^= hi >> 32
    hi *= 0xda942042e4dd58b5
    hi ^= hi >> 48
    hi *= lo | 1
}

O’Neill 将此 scrambler 与 PCG 称为 PCG-DXSM，代表“double xorshift multiply”（双异或移位乘法）。Numpy 也使用这种形式的 PCG。

尽管 PCG 生成每个值需要更多的计算，但它使用的状态要少得多：两个 uint64 而不是 607 个。它对状态的初始值也不那么敏感，并且它通过了许多其他生成器无法通过的统计测试。在很多方面，它是一个理想的统计生成器。

即便如此，PCG 仍然是可预测的。虽然用于准备结果的位混合不像 LCG 和 Go 1 生成器那样直接暴露状态，但PCG-XSL-RR 仍可能被逆向，并且 PCG-DXSM 也能如此也并不奇怪。对于秘密，我们需要不同的东西。

加密随机性

加密随机数在实践中需要完全不可预测，即使对于知道它们如何生成并且观察过任意数量先前生成值的观察者也是如此。加密协议、密钥、现代商业、在线隐私等的安全都严重依赖于对加密随机性的访问。

提供加密随机性最终是操作系统的职责，它可以从物理设备收集真正的随机性——鼠标、键盘、磁盘和网络的计时，以及最近的CPU 本身测量的电噪声。一旦操作系统收集了足够多的随机性——例如，至少 256 位——它就可以使用加密哈希或加密算法将该种子扩展成任意长的随机数序列。（实际上，操作系统也在不断收集新的随机性并将其添加到序列中。）

确切的操作系统接口随着时间的推移而演变。十年前，大多数系统提供一个名为 /dev/random 或类似名称的设备文件。如今，考虑到随机性的重要性，操作系统提供了直接的系统调用。（这还允许程序在与文件系统隔离的情况下读取随机性。）在 Go 中，crypto/rand 包封装了这些细节，在所有操作系统上提供相同的接口：rand.Read。

math/rand 每次需要 uint64 时都向操作系统请求随机性是不现实的。但是，我们可以使用加密技术来定义一个进程内随机生成器，该生成器在 LCG、Go 1 生成器甚至 PCG 的基础上进行了改进。

ChaCha8Rand 生成器

我们新生成的器，为方便说明，我们将其命名为 ChaCha8Rand，并作为 math/rand/v2 的 rand.ChaCha8 实现，它是 Daniel J. Bernstein 的 ChaCha 流密码的一个轻微修改版本。ChaCha 以 20 轮形式 ChaCha20 广泛使用，包括在 TLS 和 SSH 中。Jean-Philippe Aumasson 的论文“Too Much Crypto”令人信服地论证了 8 轮形式的 ChaCha8 也是安全的（并且速度大约快 2.5 倍）。我们将 ChaCha8 作为 ChaCha8Rand 的核心。

大多数流密码，包括 ChaCha8，通过定义一个函数来工作，该函数接收一个密钥和一个块号并生成一个固定大小的、看起来随机的数据块。它们的目标（并且通常满足）的标准是，在没有任何指数级昂贵的暴力搜索的情况下，其输出与实际随机数据无法区分。消息通过将输入的连续块与生成的连续随机数据块进行异或来加密或解密。为了将 ChaCha8 用作 rand.Source，我们直接使用生成的块而不是将它们与输入数据进行异或（这等同于加密或解密所有零）。

我们更改了一些细节，使 ChaCha8Rand 更适合生成随机数。简而言之：

• ChaCha8Rand 接受一个 32 字节的种子，用作 ChaCha8 密钥。
• ChaCha8 生成 64 字节的块，计算将块视为 16 个 uint32。一种常见的实现方式是使用SIMD 指令一次计算四个块，每个块包含 16 个向量寄存器，每个寄存器包含四个 uint32。这会生成四个交错的块，必须进行解交错才能与输入数据进行异或。ChaCha8Rand 定义交错的块为随机数据流，消除了解交错的成本。（出于安全目的，这可以视为标准的 ChaCha8 后跟一个重新洗牌。）
• ChaCha8 通过将某些值添加到块中的每个 uint32 来完成一个块。一半的值是密钥材料，另一半是已知常量。ChaCha8Rand 定义不重新添加已知常量，从而消除了最后一半的加法。（出于安全目的，这可以视为标准的 ChaCha8 后跟减去已知常量。）
• 每生成 16 个块，ChaCha8Rand 就会将该块的最后 32 字节用于自身，将其作为下一个 16 个块的密钥。这提供了一种前向保密：如果系统因恢复生成器全部内存状态的攻击而被攻破，则只能恢复自上次重新密钥生成以来生成的值。过去是无法访问的。到目前为止定义的 ChaCha8Rand 必须一次生成 4 个块，但我们选择每 16 个块进行一次密钥轮换，以保留使用 256 位或 512 位向量进行更快实现的可能性，这些向量一次可以生成 8 或 16 个块。

我们为 ChaCha8Rand 编写并发布了C2SP 规范以及测试用例。这将使其他实现能够在给定种子的情况下与 Go 实现共享可重复性。

Go 运行时现在维护每个核心的 ChaCha8Rand 状态（300 字节），该状态由操作系统提供的加密随机数播种，以便可以快速生成随机数而无需任何锁争用。每个核心分配 300 字节听起来可能很昂贵，但在 16 核系统上，它与存储单个共享的 Go 1 生成器状态（4,872 字节）大致相同。速度值得内存。现在，这个每个核心的 ChaCha8Rand 生成器在 Go 标准库的三个不同位置使用：

1. math/rand/v2 包中的函数，例如 rand.Float64 和 rand.N，始终使用 ChaCha8Rand。

2. math/rand 包中的函数，例如 rand.Float64 和 rand.Intn，在未调用 rand.Seed 时使用 ChaCha8Rand。在 math/rand 中应用 ChaCha8Rand 可以在程序更新到 math/rand/v2 之前提高程序的安全性，前提是它们没有调用 rand.Seed。（如果调用了 rand.Seed，则实现被要求回退到 Go 1 生成器以保持兼容性。）

3. 运行时使用 ChaCha8Rand 而不是之前使用的安全性较低的基于 wyrand 的生成器来选择每个新映射的哈希种子。需要随机种子，因为如果攻击者知道映射实现的特定哈希函数，他们就可以准备输入，使映射进入二次行为（请参阅 Crosby 和 Wallach 的“通过算法复杂度攻击拒绝服务”）。使用每个映射的种子而不是所有映射的一个全局种子，还可以避免其他退化行为。虽然不完全清楚映射是否需要加密随机种子，但也不清楚它们是否不需要。切换似乎是审慎且微不足道的。

需要自己的 ChaCha8Rand 实例的代码可以直接创建自己的 rand.ChaCha8。

修复安全错误

Go 旨在帮助开发人员编写默认安全的代码。当我们观察到常见的、具有安全后果的错误时，我们会寻找方法来降低该错误的风险或完全消除它。在这种情况下，math/rand 的全局生成器过于容易预测，导致在各种情况下出现严重问题。

例如，当 Go 1.20 弃用 math/rand 的 Read 时，我们收到了开发人员的反馈，他们发现（由于工具提示使用了已弃用的功能）他们曾将其用于crypto/rand 的 Read 肯定需要的地方，例如生成密钥材料。使用 Go 1.20，这个错误是一个严重的安全问题，需要进行详细调查以了解造成的损害。密钥用在哪里？密钥是如何泄露的？其他随机输出是否被泄露，可能导致攻击者推断出密钥？等等。使用 Go 1.22，这个错误只是一个错误。使用 crypto/rand 仍然更好，因为操作系统内核可以更好地将随机值保密，防止各种窥探，内核会不断向其生成器添加新的熵，并且内核已经过更多审查。但是，意外使用 math/rand 不再是安全灾难。

还有各种看起来不像“加密”但仍需要不可预测随机性的用例。使用 ChaCha8Rand 而不是 Go 1 生成器可以使这些情况更加健壮。

例如，考虑生成一个随机 UUID。由于 UUID 不是秘密，使用 math/rand 似乎没问题。但如果 math/rand 使用当前时间进行播种，那么在同一时刻在不同计算机上运行它将产生相同的值，使其不“普遍唯一”。在当前时间精度仅为毫秒的系统上尤其如此。即使使用 Go 1.20 中引入的 OS 提供的熵进行自动播种，Go 1 生成器的种子也只是一个 63 位整数，因此在启动时生成 UUID 的程序只能生成 2⁶³ 个可能的 UUID，并且在出现大约 2³¹ 个 UUID 后很可能会发生冲突。使用 Go 1.22，新的 ChaCha8Rand 生成器从 256 位熵播种，可以生成 2²⁵⁶ 个可能的第一个 UUID。它不需要担心冲突。

作为另一个例子，考虑前端服务器中的负载均衡，该服务器随机将传入请求分配给后端服务器。如果攻击者可以观察分配情况并知道生成它们的不可预测算法，那么攻击者就可以发送大量廉价请求，但安排所有昂贵的请求都落到单个后端服务器上。使用 Go 1 生成器，这是一种不太可能但并非不可能出现的问题。使用 Go 1.22，这根本不是问题。

在所有这些示例中，Go 1.22 都消除了或大大减少了安全问题。

性能

ChaCha8Rand 的安全优势确实有很小的成本，但 ChaCha8Rand 的性能仍与 Go 1 生成器和 PCG 在同一量级。以下图表比较了在各种硬件上运行的三个生成器的性能，它们执行两个操作：“Uint64”原始操作，返回随机流中的下一个 uint64；以及“N(1000)”高级操作，返回范围 [0, 1000) 内的随机值。

“运行 32 位代码”图表显示了在 GOARCH=386 构建的代码上执行的现代 64 位 x86 芯片，这意味着它们在 32 位模式下运行。在这种情况下，PCG 需要 128 位乘法使其比 ChaCha8Rand 慢，而 ChaCha8Rand 只使用 32 位 SIMD 算术。实际的 32 位系统每年都越来越不重要，但 ChaCha8Rand 在这些系统上比 PCG 更快仍然很有趣。

在某些系统上，“Go 1: Uint64”比“PCG: Uint64”更快，但“Go 1: N(1000)”比“PCG: N(1000)”慢。发生这种情况是因为“Go 1: N(1000)”使用 math/rand 的算法将随机 int64 减少到范围 [0, 1000) 内的值，该算法执行两次 64 位整数除法。相比之下，“PCG: N(1000)”和“ChaCha8: N(1000)”使用更快的 math/rand/v2 算法，该算法几乎总是避免除法。删除 64 位除法对于 32 位执行和 Ampere 上的算法更改起着主导作用。

总的来说，ChaCha8Rand 比 Go 1 生成器慢，但其速度从未超过两倍，在典型服务器上，这种差异从未超过 3ns。很少有程序会因为这种差异而成为瓶颈，而许多程序将受益于改进的安全性。

结论

Go 1.22 在无需更改代码的情况下使您的程序更加安全。我们通过识别意外使用 math/rand 而非 crypto/rand 的常见错误，然后加强 math/rand 来实现这一点。这是 Go 在默认情况下使程序保持安全这一持续旅程中的一小步。

这些类型的错误并非 Go 所独有。例如，npm 的 keypair 包尝试使用 Web Crypto API 生成 RSA 密钥对，但如果不可用，它将回退到 JavaScript 的 Math.random。这种情况绝非孤例，我们系统的安全性不能依赖于开发人员不犯错误。相反，我们希望最终所有编程语言都能为“数学”随机性采用加密强大伪随机生成器，从而消除这种类型的错误，或者至少大大减小其影响范围。Go 1.22 的 ChaCha8Rand 实现证明了这种方法与其他生成器相比具有竞争力。