随机数与熵：从 LCG 到 CSPRNG 的工程实践

引言

“随机"在工程里其实分三种：统计随机（分布均匀、通过检验）、密码学随机（不可预测、能抗攻击）、可复现随机（给定种子完全确定）。把三者混用是常见事故源——用 Math.random() 生成会话令牌、用系统熵源做单元测试、用有种子 PRNG 做密钥，都是典型翻车。本文从"熵"这个源头讲起，拆解 LCG、Mersenne Twister、PCG 的取舍，讲清种子与可复现性、CSPRNG 与 /dev/urandom，再落到采样、洗牌、分布变换这些日常操作。

前置：标识符设计：UUID v4/v7、ULID、雪花算法与工程权衡、加密与证书工具箱。概率分布见 概率统计基础实战。

目录

• 1. 三种随机：统计、密码学与可复现
• 2. 伪随机生成器：LCG、MT 与 PCG
• 3. 种子与可复现性
• 4. CSPRNG 与操作系统熵池
• 5. 采样、洗牌与拒绝采样
• 6. 分布变换：从均匀到正态
• 7. UUID、Token 与密钥中的随机
• 8. 常见误用与安全陷阱
• 9. 测试与验证随机性
• 10. 速查表与一句话记忆
• 延伸阅读

1. 三种随机：统计、密码学与可复现

核心问题：“均匀"不等于"不可预测”。Mersenne Twister 分布极均匀，但观测到 624 个连续输出就能完全重建内部状态并预测后续所有值——用它生成令牌等于明文。

选择的第一问：这个随机数会被攻击者看到吗？ 会 → CSPRNG；不会且要快 → 普通 PRNG；要能复现 → 带种子的 PRNG。

记忆：随机分三种——统计（分布好）、密码学（不可预测）、可复现（同种子同序列）；第一问永远是"会不会被攻击者看到”。

2. 伪随机生成器：LCG、MT 与 PCG

线性同余（LCG）：x_{n+1} = (a·x_n + c) mod m，一个乘法加一个加法。

# 经典 LCG 参数（Numerical Recipes）
def lcg(seed, a=1664525, c=1013904223, m=2**32):
    x = seed
    while True:
        x = (a * x + c) % m
        yield x / m

优点：极快、状态极小（一个整数）。缺点：低位周期极短、高维分布有规律（Marsaglia 的"晶格结构"问题），绝不能用于密码学。

Mersenne Twister（MT19937）：周期 2^19937 − 1，分布质量高，是 Python random、PHP mt_rand、Ruby 的默认实现。

优点：周期极长、速度快、分布好、统计检验通过
缺点：状态 2.5KB、可被观测重建、非密码学安全、非跳跃友好

PCG（Permuted Congruential Generator）：用 LCG 做状态转移，再叠加一层"输出置换"，兼顾小状态、快速度、好分布。

选型：模拟/游戏/采样用 PCG 或 xoshiro；任何涉及安全的一律 CSPRNG。

# Python 的 random 是 MT19937
import random
rng = random.Random(42)
print([rng.randint(1, 6) for _ in range(5)])   # 可复现

记忆：LCG 快但分布差、MT 好但可被重建、PCG/xoshiro 是现代的默认——但都"非密码学安全"。

3. 种子与可复现性

种子决定序列：给定相同种子，PRNG 输出完全确定。这是测试、仿真、机器学习的基石，也是安全事故的来源。

import random

random.seed(42)
a = [random.random() for _ in range(3)]

random.seed(42)
b = [random.random() for _ in range(3)]

print(a == b)   # True —— 同种子同序列

可复现性的工程价值：单元测试固定种子后失败可复现（不是"偶发"）、仿真同种子跑两次必须同结果、ML 的数据打乱/权重初始化/dropout 都要固定、train/test 切分用固定种子。

反面：seed(time.time())、seed(os.getpid()) 这类"想随机一点"的写法，实际是伪随机且可预测——攻击者知道时间窗就能暴力枚举。

Python 3 的两套 API：random 模块的全局函数用系统熵自动播种，但独立 Random(seed) 实例才是可复现的正确姿势——别污染全局状态。

# 正确：独立实例，互不干扰
r1 = random.Random(1)
r2 = random.Random(2)
print(r1.random(), r2.random())

记忆：种子 = 可复现的开关——测试/仿真/ML 必须固定；但"用时间当种子"是伪随机不是安全随机。

4. CSPRNG 与操作系统熵池

**CSPRNG（密码学安全伪随机）**要求：给定过去全部输出，无法预测下一个输出（不可预测性 + 抗状态恢复）。

熵池的来源：操作系统从硬件事件收集不确定性——中断时序、键盘/鼠标间隔、磁盘寻道、rdrand/rdseed 指令、CPU 抖动。

/dev/random vs /dev/urandom：历史上 /dev/random 会在熵耗尽时阻塞，/dev/urandom 不阻塞但可能"熵不足"。现代 Linux（5.6+）/dev/random 也已不再阻塞，getrandom(2) 是首选接口。实践结论：用 /dev/urandom / getrandom，不要用 /dev/random——它带来的只是无谓阻塞，不会更安全。

import os, secrets

print(os.urandom(16).hex())        # 16 字节密码学随机
print(secrets.token_hex(16))       # 推荐：高层 API
print(secrets.token_urlsafe(16))   # URL-safe 令牌

secrets 优于 random：secrets 明确以 CSPRNG 为后端，语义上就宣告"这是安全用途"。

import secrets
print(secrets.choice(['a', 'b', 'c']))
print(secrets.randbelow(100))      # [0,100) 无偏

记忆：安全随机用 getrandom / os.urandom / secrets——/dev/random 的"阻塞更安全"是过时神话。

5. 采样、洗牌与拒绝采样

均匀整数 [0, n) 的正确做法是拒绝采样，而不是取模：

# 错误：取模引入偏差（2^32 不能被 n 整除时，小余数概率偏高）
def bad_rand(n):
    return os.urandom(4)[0] % n

# 正确：拒绝采样，丢弃落在"尾巴"上的值
def good_rand(n):
    limit = 256 - (256 % n)
    while True:
        b = os.urandom(1)[0]
        if b < limit:
            return b % n

为什么取模有偏：若随机源均匀分布在 [0, 256)，而 n=3，则余数 0 会拿到 {0,3,…,255}（86 个），余数 1、2 各 85 个——偏差约 1.2%，在抽奖、密钥生成里是致命漏洞。

Fisher–Yates 洗牌（正确且均匀）：

import random

def shuffle(a):
    a = a[:]
    for i in range(len(a) - 1, 0, -1):
        j = random.randrange(i + 1)   # 关键：j ∈ [0, i]，不是 [0, n)
        a[i], a[j] = a[j], a[i]
    return a

错误洗牌：sorted(a, key=lambda _: random.random()) 看似优雅，但分布不均（受排序算法与 key 碰撞影响）；random.shuffle 内部就是正确的 Fisher–Yates。

import random
a = list(range(10))
random.shuffle(a)     # 正确：原地 Fisher–Yates

从集合均匀采样 k 个：

import random
print(random.sample(range(100), 5))   # 无放回，均匀

记忆：取模有偏要用拒绝采样，洗牌必须 Fisher–Yates——sorted(key=random) 是错的。

6. 分布变换：从均匀到正态

逆变换采样：给定目标分布的 CDF 反函数 F⁻¹，X = F⁻¹(U)（U 均匀）就服从目标分布。

import random, math

# 指数分布：F⁻¹(u) = -ln(1-u)/λ
def exp_sample(lam):
    u = random.random()
    return -math.log(1 - u) / lam

Box–Muller：把两个均匀数变成两个独立标准正态：

import math, random

def normal_pair():
    u1 = random.random()
    u2 = random.random()
    r = math.sqrt(-2 * math.log(u1))
    return r * math.cos(2 * math.pi * u2), r * math.sin(2 * math.pi * u2)

print(normal_pair())

Box–Muller 的坑：u1 可能为 0 → log(0) 是 -inf，要重采样或加 epsilon。

Python 内置：random.gauss(mu, sigma)（非线程安全、缓存一个值）、random.normalvariate（较慢但无缓存）。统计用途注意 gauss 会缓存第二个值，某些测试下会产生相关性。

import random
print(random.gauss(0, 1))
print(random.normalvariate(0, 1))

拒绝采样：目标分布难以直接采样时，用一个易采样的"提议分布" + 接受概率来采。接受率太低会慢——这是蒙特卡洛的常见调优点。

记忆：逆变换用 CDF 反函数、正态用 Box–Muller（防 log(0)）——gauss 会缓存一个值，统计敏感场景用 normalvariate。

7. UUID、Token 与密钥中的随机

三者的随机强度要求递增：

UUID v4 的随机源：Python 的 uuid.uuid4() 用 os.urandom，是密码学安全的；但有些语言的默认 UUID 实现用非安全 PRNG——跨语言时要核对。

import uuid, secrets
print(uuid.uuid4())                     # 122 位随机，CSPRNG 后端
print(secrets.token_urlsafe(32))        # 43 字符 URL-safe，约 256 位

令牌长度与碰撞：生日界下，n 位随机标识符在约 2^(n/2) 个对象后出现碰撞。128 位 → 约 2^64 才显著，够用几百年；64 位 → 约 2^32 就有碰撞风险，不够。

令牌长度经验：
  64 位随机  → 约 40 亿个后碰撞概率显著（不够）
  128 位随机 → 约 1.8×10^19 个（足够）
  256 位随机 → 密钥级

雪花/自增 ID 绝不能当令牌：它们可枚举、可预测——ID 是标识符不是凭证。

记忆：标识符不是凭证——令牌要 ≥128 位 CSPRNG 随机，密钥用 os.urandom/KMS，雪花与自增 ID 绝不能当认证凭据。

8. 常见误用与安全陷阱

六大高频事故：

并发陷阱：全局 PRNG 在多线程下可能返回相同值（某些语言），或产生可预测交错。每线程独立实例或直接用 CSPRNG。

# 错误：全局 random 在多线程下有状态竞争
# 正确：每线程一个 Random 实例，或直接用 secrets
import threading, random

local = threading.local()
def worker():
    local.rng = random.Random()     # 线程本地

“随机数不够随机"的真实案例：某抽奖系统用 rand() % 100，攻击者观测若干结果后预测下一位，拿走大奖——分布偏差 + 可预测 = 可操纵。

检查清单：

□ 这个值会被攻击者看到吗？→ 是则必须 CSPRNG
□ 用了取模吗？→ 改用拒绝采样
□ 令牌长度 ≥128 位吗？
□ 洗牌是 Fisher–Yates 吗？
□ 种子来自哪里？→ 安全用途绝不能是时间/PID

记忆：安全随机只有一条线——CSPRNG；取模偏差、时间种子、伪洗牌是三大隐形杀手。

9. 测试与验证随机性

随机代码的测试悖论：随机结果不能断言具体值，只能断言分布性质与边界性质。

三种测试策略：

1. 固定种子 → 断言确定序列（回归测试）
2. 大量样本 → 断言统计性质（卡方、均值、方差）
3. 属性测试 → 断言不变量（洗牌后集合相等、采样无重复）

import random, collections

def test_shuffle_is_uniform():
    rng = random.Random(0)
    counts = collections.Counter()
    for _ in range(100000):
        a = [0, 1, 2]
        rng.shuffle(a)
        counts[tuple(a)] += 1
    # 6 种排列应大致均匀（各约 1/6）
    print(counts)

卡方检验判"分布是否均匀”：

# 简化：观测频次 vs 期望频次的卡方统计量
# 期望 = N/k，统计量 = Σ (obs - exp)^2 / exp
# 自由度 k-1，超过临界值则怀疑分布有偏

工具：Dieharder、TestU01（PRNG 质量套件）；NIST SP 800-22（密码学随机检验）。

测试随机代码的实践：

- 注入 RNG（依赖注入）→ 测试时传固定种子
- 断言范围而非具体值：0 <= x < n
- 统计检验用大样本 + 宽容差（避免 flaky）
- 避免用随机做"唯一"假设（生日碰撞）

记忆：随机代码测试"分布与边界"而非具体值——固定种子做回归、大样本做统计、注入 RNG 做可控。

10. 速查表与一句话记忆

全篇速查：

一句话记忆：随机分三种——统计随机的分布好但可被重建（MT 观测 624 个输出即破），密码学随机不可预测（getrandom/os.urandom/secrets），可复现随机靠种子（测试/仿真/ML 的基石）；安全第一问永远是"会不会被攻击者看到"；取模有偏要用拒绝采样、洗牌必须 Fisher–Yates、令牌 ≥128 位 CSPRNG、ID 绝不是凭证；把时间当种子是伪随机不是安全随机，用 /dev/random 追求"更安全"是过时神话——随机代码测试断言分布与边界，而非具体值。

延伸阅读

• 标识符设计：UUID v4/v7、ULID、雪花算法与工程权衡
• 加密与证书工具箱
• 概率统计基础实战：贝叶斯、随机变量、分布与推断
• 安全专题 — 密码学与安全实践
• 算法与面试专题 — 随机化算法与采样