計算機並非隨機。恰恰相反，硬體設計人員會非常努力地確保計算機每次都能以相同的方式執行所有程式。因此，當程式確實需要隨機數時，就需要額外的努力。傳統上，計算機科學家和程式語言在兩種不同型別的隨機數之間進行了區分：統計隨機性和加密隨機性。在 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 實現證明了這種方法與其他生成器相比具有競爭力。