什麼是 CSPRNG？安全亂數產生器的歷史、演算法與應用

1. 什麼是 CSPRNG？

CSPRNG（Cryptographically Secure Pseudo-Random Number Generator），中文通常譯為密碼學安全偽隨機數產生器，是在一般 PRNG（Pseudo-Random Number Generator）的基礎上，額外滿足密碼學安全要求的亂數產生器。

一個 CSPRNG 至少需要具備兩項核心特性：

Next-bit Test（下一位不可預測性）

即使已知前 n 個輸出位元，也無法在多項式時間（Polynomial Time）內，以高於 50% 的成功率預測第 n+1 個位元。

State Compromise Resilience（狀態洩漏韌性）

即使攻擊者取得目前的內部狀態，也無法回推出先前已產生的亂數。

簡單來說，

CSPRNG 所產生的輸出，在計算上無法與真正的隨機數區分。

2. PRNG 與 CSPRNG 比較

| 特性 | PRNG（例如 Xorshift128+） | CSPRNG（例如 ChaCha20） | |------|-------------------------|--------------------------| | 速度 | 極快（約 2–3 ns／數值） | 很快（約 10–20 ns／數值） | | 是否可預測 | 可以，取得部分輸出即可推回內部狀態 | 幾乎不可行 | | 週期 | 2¹²⁸ − 1 | 約 2²⁵⁶（ChaCha20） | | 可用於密碼學 | ❌ 不可 | ✅ 可以 | | 常見 API | Math.random() | crypto.getRandomValues()、/dev/urandom |

3. 發展歷史

3.1 Blum Blum Shub（1986）

1986 年，

Lenore Blum、Manuel Blum 與 Michael Shub 提出了 Blum Blum Shub（BBS），

它是第一個具有嚴格數學安全證明的 CSPRNG。

其核心公式為：

# BBS
# x(n+1) = x $n$ ^2 mod M
# M = p × q（兩個大型質數乘積）

def bbs(seed, p, q, n):
    M = p * q
    x = seed
    bits = []

    for _ in range $n$ :
        x = (x * x) % M
        bits.append(x & 1)

    return bits

由於需要大量模平方運算，

BBS 非常緩慢，

因此主要具有理論研究價值，

卻奠定了現代 CSPRNG 的基礎。

3.2 Yarrow 與 Fortuna（1999／2003）

Bruce Schneier 與 Niels Ferguson 先後提出：

Yarrow（1999）
Fortuna（2003）

其中：

Yarrow 曾被 macOS、FreeBSD 的 /dev/random 採用。
Fortuna 引入多個 Entropy Pool，自動管理熵來源，避免單點失效。
兩者皆以 AES-256 作為核心區塊加密演算法。

自 macOS 10.12（Sierra）起，

Apple 已改採 Fortuna。

3.3 ChaCha20（2008 至今）

Daniel J. Bernstein 於 2008 年設計 ChaCha20，

它是 Salsa20 的改良版本，

也是目前最廣泛採用的 CSPRNG 之一。

例如：

Linux 4.8（2016）起，/dev/urandom 採用 ChaCha20。
OpenBSD 自 2013 年起將 arc4random() 改為 ChaCha20。
Chrome、Node.js 的 crypto.getRandomValues() 建立於作業系統提供的安全亂數來源。
Rust 的 rand_chacha 預設使用 ChaCha 演算法。

4. 現代 CSPRNG 演算法

4.1 ChaCha20

ChaCha20 是一種 Stream Cipher，

內部使用：

4 × 4 Matrix
共 16 個 32-bit Word
總共 512 位元狀態

核心 Quarter Round：

function quarterRound(state, a, b, c, d) {
  state[a] += state[b];
  state[d] ^= state[a];
  state[d] = rotl32(state[d], 16);

  state[c] += state[d];
  state[b] ^= state[c];
  state[b] = rotl32(state[b], 12);

  state[a] += state[b];
  state[d] ^= state[a];
  state[d] = rotl32(state[d], 8);

  state[c] += state[d];
  state[b] ^= state[c];
  state[b] = rotl32(state[b], 7);
}

ChaCha20 每個 Block：

Key：256 bit
Nonce：96 bit
Counter：32 bit
Output：512 bit

經過 20 輪（Rounds） 運算產生亂數。

4.2 AES-CTR-DRBG（NIST SP 800-90A）

AES-CTR-DRBG 是 NIST 標準，

廣泛應用於：

美國政府
金融系統
FIPS 認證產品

簡化結構如下：

class CTR_DRBG:
    def __init__(self, entropy, nonce):
        self.key = AES_key_from(entropy, nonce)
        self.counter = 0

    def generate(self, n):
        ...

特色：

使用 AES-CTR 模式。
定期 Reseed。
符合 NIST SP 800-90A。

4.3 HMAC-DRBG（RFC 6979）

HMAC-DRBG 以 HMAC-SHA256 為核心。

RFC 6979 使用它來產生：

Deterministic ECDSA Nonce

可避免重複使用 Nonce 而洩漏私鑰。

基本流程：

Seed
   │
   ▼
K
V
   │
   ▼
HMAC 更新
   │
   ▼
Random Output

5. 實際應用

CSPRNG 幾乎存在於所有現代資訊安全系統中，包括：

TLS／HTTPS：Session Key、IV、Nonce。
SSH：金鑰交換。
OAuth、JWT：Access Token、Refresh Token。
密碼系統：Salt、隨機密碼。
區塊鏈：Bitcoin、Ethereum 私鑰。
線上博弈：Provably Fair 隨機種子。

6. 各程式語言 API

JavaScript（Browser / Node.js）

// Browser
const buf = new Uint8Array(32);
crypto.getRandomValues $buf$ ;

// Node.js
import { randomBytes, randomUUID } from "node:crypto";

const key = randomBytes(32);
const uuid = randomUUID();

Python

import secrets
import os

token = secrets.token_urlsafe(32)
pin = secrets.randbelow $1_000_000$ 

raw = os.urandom(32)

# 不可用於安全用途
import random

⚠️ random 模組使用 Mersenne Twister，並非 CSPRNG。

Rust

use rand::rngs::OsRng;
use rand::RngCore;

let mut key = [0u8; 32];
OsRng.fill_bytes(&mut key);

Java

SecureRandom rng = SecureRandom.getInstanceStrong();

byte[] key = new byte[32];
rng.nextBytes $key$ ;

int pin = rng.nextInt $1_000_000$ ;

C（Linux）

#include <sys/random.h>

unsigned char key[32];
getrandom(key, sizeof(key), 0);

7. 著名安全事件

Debian OpenSSL（2008）

CVE-2008-0166
誤刪兩行程式碼。
Entropy 僅剩約三萬種可能。
Debian 約兩年間產生的 SSL 金鑰幾乎都可被暴力破解。

Sony PS3（2010）

Sony 在 ECDSA 中重複使用固定 Nonce（k）。

結果：

私鑰被推算。
PS3 遭全面破解（Jailbreak）。

Android SecureRandom（2013）

Android 初始化亂數時熵不足，

導致大量 Bitcoin 錢包私鑰遭竊。

DualECDRBG（2013）

DualECDRBG 是 NIST 標準中的一種 DRBG。

2013 年曝光其可能遭 NSA 植入後門，

成為密碼學史上最具爭議的事件之一，也使業界重新檢視隨機數產生器的設計與標準制定流程。