洗牌只有 8,640 萬種：遊戲 RNG 認證在檢查什麼

1999 年，Reliable Software Technologies 的幾位工程師研究了 PlanetPoker 的洗牌程式。那套軟體由 ASF Software 開發，為了讓玩家相信洗牌公平，ASF 把洗牌演算法貼在網站上。一副牌有 52! 種排法，大約是 2 的 226 次方，他們讀完程式碼發現，實際可能出現的牌序少得多。

洗牌用的是 Borland 編譯器附的亂數產生器，只有 32 位元的 seed，最多 40 億種牌序，而 seed 又取自「午夜以來的毫秒數」，一天只有 86,400,000 種可能。把自己的時鐘和伺服器對準之後，範圍縮到大約 20 萬種。牌局開始後，只要知道自己的兩張手牌和翻牌的三張，程式就能找出唯一符合的 seed，之後每一局的整副牌都能在一秒內算出來。他們聯絡 ASF 之後，對方改了演算法。

另一個常被拿出來講的例子在 2008 年。Debian 和 Ubuntu 的 OpenSSL 套件有一個 patch，讓亂數產生器實際上只剩 process ID 一個熵來源，當時 PID 最大值多半是 32,768，同一種架構、同一種金鑰能產生的金鑰就只有那麼多。這個問題從 2006 年 9 月就在 unstable 裡，2007 年 4 月進了 stable，到 2008 年 5 月 13 日才公告。

兩個例子出事的地方都在 seed、狀態，以及把亂數接到業務邏輯的那幾行程式碼，遊戲 RNG 認證主要檢查的也是這些。下面用 GLI-11（實驗室 GLI 給博弈設備的技術標準，v3.0）的條文對照，範例在 Python 3.13.15 上跑過。

一、seed 空間：看到 5 張牌就夠了

先把 1999 年的情況簡化重現：用午夜以來的毫秒數當 seed 洗牌，攻擊者看到前 5 張牌，自己的時鐘和伺服器差不到兩秒：

import random, time

def shuffle_with_seed(seed):
    deck = list(range(52))
    random.Random(seed).shuffle(deck)
    return deck

server_seed = 45_296_789          # 12:34:56.789
deck = shuffle_with_seed(server_seed)
seen = deck[:5]                   # 自己的兩張手牌 + 翻牌三張
guess_clock = 45_296_000          # 攻擊者的時鐘，誤差在 ±2 秒內

t0 = time.perf_counter()
hits = [s for s in range(guess_clock - 2000, guess_clock + 2001)
        if shuffle_with_seed(s)[:5] == seen]
dt = time.perf_counter() - t0
print("hits:", hits, f"time: {dt*1000:.0f} ms")
print("full deck recovered:", shuffle_with_seed(hits[0]) == deck)

hits: [45296789] time: 81 ms
full deck recovered: True

4,001 個候選 seed，81 毫秒就找到唯一的那一個，剩下 47 張牌全部知道。這裡的洗牌演算法本身沒有問題，Python 的 shuffle 是正確的 Fisher-Yates，問題全在 seed：可能的值太少，又跟一個外人猜得到的東西（時間）綁在一起。

GLI-11 對這件事的要求寫在 3.3.2：軟體 RNG 的初始狀態要由「不受控制且無法預測的事件」決定。時間、PID、遞增計數器都不符合。實務上就是向作業系統拿，Linux 的 getrandom、Go 的 crypto/rand、Python 的 secrets，這些介面本來就是為了這件事存在的。

二、統計測試過了，不代表猜不到

GLI-11 3.2.2 要求一組統計測試，列了 chi-square、overlaps、coupon collector、runs、interplay correlation、serial correlation、duplicates 等，整體以 99% 信心水準評估。

這些測試檢查的是分布：每個值出現的頻率對不對、前後有沒有相關。它們不檢查「看到一段輸出之後，能不能推出下一個」。上面範例用的 Python random 模組，核心是 Mersenne Twister，週期長達 2 的 19937 次方減 1，統計性質相當好，Python 文件卻明寫它不該用於安全用途，要用 secrets。它的內部狀態可以從足夠多的連續輸出推回去（需驗證：常見的說法是 624 個 32 位元輸出就夠）。

所以標準在統計測試之外另外要求不可預測性。3.2.6 寫的是，除非使用「cryptographic RNG」，否則每一局之間都要改變 RNG 的狀態，做法包括 background cycling（在背景持續丟棄亂數，讓外人無法對準位置）或者重新注入熵。3.6 則要求 cryptographic RNG 能抵抗三種攻擊：直接的密碼分析、已知輸入攻擊，以及狀態洩漏之後的延伸攻擊，也就是某一刻的內部狀態被拿到了，之後的輸出也不能因此被算出來，這就需要定期從外部注入熵。

CSPRNG 的設計目標正好對應這些要求，常見的做法是拿一個串流加密法或雜湊函式當核心，NIST SP 800-90A 列的 Hash_DRBG、HMAC_DRBG、CTR_DRBG 都是這一類。認證時選哪一種不太要緊，要能說明它屬於這一類、seed 從哪裡來、多久重新注入一次。

三、亂數沒問題，對應到牌面時歪了

RNG 輸出的是一串位元，遊戲要的是「1 到 52 之間的一個數」或「轉軸停在第幾格」，中間那一步叫 scaling 或 mapping。GLI-11 3.2.3 對這一步的要求很直接：所有 scaling、mapping 和 shuffling 演算法都必須完全沒有偏差，並且要經過原始碼審查確認。

最常見的偏差是取餘數。拿一個隨機 byte（0 到 255）對 52 取餘數：

from collections import Counter
counts = Counter(b % 52 for b in range(256))
print(sorted(set(counts.values())), 5/256, 4/256)

[4, 5] 0.01953125 0.015625

256 不是 52 的倍數，0 到 47 各有 5 種 byte 會對應過去，48 到 51 只有 4 種，最後四張牌出現的機率比其他牌低兩成。換成 32 位元的亂數，偏差會小到很難用統計測試看出來，但它還是存在，而標準要求的是「完全沒有」，審查原始碼的人一眼就會挑出來。

修法是拒絕取樣：落在無法整除的尾段就丟掉重抽。各語言的標準函式庫多半已經做好，Go 的 crypto/rand.Int、Python 的 secrets.randbelow 都是，自己寫 rand() % n 反而是最容易出事的地方。

洗牌也一樣。Fisher-Yates 的寫法是第 i 張只跟「還沒處理過的範圍」裡的任一張交換，常見的錯是每一張都跟整副牌任一張交換。三張牌就能把所有情況列出來：

import itertools
from collections import Counter

def naive(n):
    res = Counter()
    for choices in itertools.product(range(n), repeat=n):
        a = list(range(n))
        for i, j in enumerate(choices):
            a[i], a[j] = a[j], a[i]
        res[tuple(a)] += 1
    return res

print(dict(sorted(naive(3).items())))

{(0, 1, 2): 4, (0, 2, 1): 5, (1, 0, 2): 5, (1, 2, 0): 5, (2, 0, 1): 4, (2, 1, 0): 4}

27 種抽法分給 6 種排列，除不盡，所以有三種排列一定比較常出現。PlanetPoker 的程式還多一個 off-by-one：交換對象只會從第 1 到第 51 張裡挑，永遠選不到第 52 個位置。把同樣的寫法縮到 4 張牌：

never-last n=4, distinct perms: 18 of 24; who ends last: {0: 27, 1: 27, 2: 27}

24 種排列只出現 18 種，原本在最後一張的牌永遠不會留在最後，換成 52 張，就是 1999 年那份報告寫的「第 52 張牌永遠不會出現在第 52 個位置」。

四、狀態和熵：Debian 的那一行

Debian 那次的起因，是套件維護者為了消掉 Valgrind 對「使用未初始化記憶體」的警告，把 md_rand.c 裡 RAND_add 的一行 MD_Update 註解掉。那一行除了混入未初始化的資料，也負責把正常的熵加進去，拿掉之後就只剩 PID，演算法本身完全沒變，金鑰卻變得可以枚舉。

Ryan Finnie 在 2024 年寫了一篇回顧，說他在官方公告前幾個月就注意到不同虛擬機器之間出現了相同的 SSH host key，只是當時沒想到原因。這種症狀在遊戲系統裡也有對應：從同一個映像檔複製出來的機器，如果 RNG 的狀態跟著映像檔一起被複製，兩台機器開出來的結果就會一模一樣。

跟這一段相關的檢查有幾項：seed 是不是每次啟動都重新向作業系統拿；長時間執行的 RNG 有沒有定期重新注入熵（GLI-11 3.6 的要求）；同一個 RNG 實例在多個執行緒之間共用時有沒有競態，會不會讓兩個請求拿到同一段輸出；以及 log、錯誤訊息、除錯介面有沒有不小心把內部狀態或 seed 吐出去。

五、RNG 沒問題，公告的機率錯了

前面幾節講的都是亂數本身。台灣這幾年最受關注的機率爭議，問題卻出在另一個地方。

《天堂M》有一種叫「紫布」的道具要靠製作取得，每次製作有一定機率成功。依公平會調查，韓版是用 201 個材料製作一次、成功率 10%，台版是 99 個材料製作一次、成功率 5%。代理商遊戲橘子在 2019 年 12 月的玩家座談會上表示台版機率跟韓版一模一樣，沒有說明兩邊的差異。2021 年 9 月，直播主丁特在直播中製作了 471 次，成功率大約 2.3%，和玩家以為的 10% 差很多，事情因此延燒（投入金額各家報導數字不一，這裡不列）。

公平會在 2022 年 6 月 9 日認定座談會上的說法屬於虛偽不實、引人錯誤的表示，依公平交易法第 21 條處 200 萬元罰鍰，這是國內第一件因為遊戲機率宣稱不實被公平會處分的案子。遊戲橘子提起行政訴訟，台北高等行政法院 2024 年駁回，最高行政法院 2025 年 6 月 12 日駁回上訴確定。差不多同一段時間，經濟部修正了「網路連線遊戲服務定型化契約應記載及不得記載事項」，2023 年 1 月 1 日起，機率型商品要在官網、登入頁和購買頁揭露中獎機率。

從工程角度看，這件事裡的 RNG 可能一點問題都沒有，前面所有的統計測試、seed、mapping 檢查都可以通過，因為出錯的是「設定值」和「對外說的數字」之間的落差，還有兩個地區版本各自維護的設定。RNG 認證檢查的是亂數怎麼產生、怎麼對應到結果，不會替你確認公告頁上的百分比和伺服器實際載入的參數是同一個數字。

外人能做的檢查其實不難。假設 471 次裡成功約 11 次（2.3% 換算回來的推算值），用二項分布算在不同真實機率下出現這麼少成功的機率：

from math import comb

def cdf(k, n, p):
    return sum(comb(n, i) * p**i * (1 - p)**(n - i) for i in range(k + 1))

n, k = 471, 11
for p in (0.10, 0.05):
    print(f"p={p:.2f}  expected={n*p:5.1f}  P(X<={k})={cdf(k, n, p):.2e}")

p=0.10  expected= 47.1  P(X<=11)=6.38e-11
p=0.05  expected= 23.6  P(X<=11)=2.71e-03

如果真實機率是 10%，期望大約成功 47 次，只成功 11 次以下的機率在百億分之一的等級，幾乎可以排除；如果是 5%，機率約千分之三，很低，但還不到不可能。這種外部推算有幾個限制要記得：直播是一個人的一段樣本，會被放上檯面討論的通常是運氣特別差的那幾場；在多少次之後停手也會影響結論；每次製作是否獨立、有沒有隱藏的條件，外人都看不到。所以它適合拿來提出疑問，不適合單獨拿來下定論。

營運方手上有完整的紀錄，能做的事情多得多，也比較該由營運方來做：

公告頁上的機率直接從伺服器實際使用的設定產生，不要另外手寫一份，兩邊只要有一份是人工維護的，遲早會對不上。
設定按地區、版本分開保存，每次變更留紀錄，變更前先公告。
每個機率型項目在正式環境持續統計實際成功次數，用同樣的二項分布算出控制界線，例如 5%、471 次時期望 23.6 次、標準差約 4.7，觀察值跑出界線就告警，在玩家發現之前先自己發現。
有保底、分段機率、條件觸發的機制，公告時要能換算成玩家實際面對的機率，只公告其中一段的數字，和沒公告差不多。

六、送件前可以先問自己的事

把上面的內容反過來，就是送去實驗室之前可以先自己過一遍的清單：

seed 從哪裡來，能不能說出它是「不受控制且無法預測」的事件。
用的是不是 CSPRNG；如果不是，每局之間怎麼改變狀態（background cycling 或重新注入熵）。
從 RNG 輸出到遊戲結果的每一步 mapping、scaling、shuffle，有沒有取餘數、浮點數乘法、自己寫的洗牌，能不能逐行說明為什麼沒有偏差。
內部狀態在什麼情況下可能被外人看到或複製：映像檔、snapshot、log、除錯介面。
能不能匯出足夠多的原始輸出給實驗室跑統計測試，匯出的路徑和正式的路徑是不是同一段程式碼。
對外公告的機率和伺服器實際載入的設定是不是同一個來源，各地區版本有沒有各自對過。

實際的送件格式和要附哪些文件，各實驗室和各司法管轄區都有自己的規定，要以送件當時的版本為準。

補充筆記

比起演算法本身，更常出事的是 seed、狀態和 mapping，1999 年的撲克和 2008 年的 Debian 都是這樣。
seed 空間要大，也要跟外人猜不到的東西綁在一起；時間、PID、計數器都不行，直接向作業系統拿。
統計測試只檢查分布，不檢查可預測性；GLI-11 另外要求每局改變狀態，或使用能抵抗狀態洩漏的 cryptographic RNG。
rand() % n 在 n 不能整除範圍時一定有偏差，用拒絕取樣，或用標準函式庫現成的函式。
洗牌用正確的 Fisher-Yates，交換範圍只能是還沒處理的部分；三張牌就能列舉出錯誤寫法的偏差。
複製出來的機器、snapshot 會連 RNG 狀態一起複製，啟動時要重新取 seed。
RNG 過了認證，不代表公告的機率是對的；公告要從實際設定產生，正式環境要持續用二項分布監控實際成功率。