随机到底是什么？

这里开始讲一讲伪随机和真随机的内容喔。整理的不一定很完全希望批评指正！

抛硬币是随机吗？

第一节：什么是随机

随机在目前有两种解释

1.每个选项的概率平均

例如1和0的随机输出当基数足够大的时候应该各占50%，满足平均分布各个选项

2.不可预判性

这和1的概念有违背，它的意思是可能当基数足够大的时候并没有各占50%，但是保证你无法预判下一次的出0或1的概率

不可预判性让每次的概率都独立存在，哪怕是在100次的1 0随机中，前99次有49次0和50次1，第100次0和1的概率也是各50%的概率

第二节：随机种类

随机分为真随机和伪随机，它们有各自的优缺点

随机方式	优点	缺点
真随机TRNG	完全无法预测，通过物理方式来随机	生成速度慢，价格昂贵
伪随机PRNG	可快速生成大量随机数	伪随机本质通过算法生成，只是因为接收方不知道种子，看上去没有规律可循，无法预判之后的随机

接下来我们来仔细讲讲真随机和伪随机的生成方式

一.真随机 TRNG

要了解TRNG的生成方式，首先我们要知道一个概念——熵

高中的物理让我们了解到，熵是衡量一个系统的混乱程度或不确定性的物理量，熵值越大越混乱，在物理学中，宇宙从开始到混沌的一过程就是熵值变大的过程——我们称之为熵增。

那么在TRNG这里，熵的概念就可以理解成不确定性的量，随机数的生成源自于一个或一类不确定量的产生（比如电子噪声、时钟抖动、量子真空涨落等）

而TRNG的生成过程大致就是如下：

物理现象 → 传感器测量 → 采样数字化 → (熵池混合) → 白化后处理 → 随机位
└────────── 熵源：真随机在这一段 ──────────┘   └─ von Neumann / SHA-256 ─┘

下面我们来一个个讲其中的概念

物理现象：即熵的原产地。一般来说，物理源来自于以下的几个部分：

1. 电子噪声类 —— 电场里的随机涨落

热噪声（Johnson–Nyquist 噪声）：电阻里的电子做热运动，造成两端电压的随机微波动。是硬件RNG的主力。
散粒噪声（shot noise）：电流的本质是离散的电子流，单位时间内穿过 PN 结的电子个数有泊松涨落。
雪崩噪声：二极管反向击穿时，载流子雪崩倍增的过程不可控，噪声幅度大的特点让它也适合随机采样。

2. 时钟抖动类 —— 把噪声翻译成时间

时钟抖动 / 振荡器相位噪声：振荡电路的边沿时刻，会被电路内部的噪声（以热噪声为主）随机推来推去。
环形振荡器（ring oscillator）：做两个频率略有差异的振荡环，让快的去采样慢的，采到的 0/1 由抖动决定。FPGA、CPU、智能卡里最流行；它的“乱”追到底依然是热噪声，只是形态从电压换成了时刻。

3. 量子 / 核物理类 —— 原理级不可预测

单光子行为：光子通过半透半反镜时走哪条路、何时到达探测器，都不可预测。
量子真空涨落：真空并不“空”，零点涨落天然随机，商用量子 RNG 卡就基于它。
放射性衰变：原子核何时衰变，物理上不可预测（HotBits 网站的老配方）。
这类与前两类有个本质区别：电子噪声的“不可预测”来自自由度太多、算不过来；量子过程则是原理保证“压根没定”。

4. 环境与传感器类 —— 宏观世界的混沌

大气静电噪声：用无线电接收大气噪声（random.org 就靠这个）。
传感器噪声：麦克风底噪、摄像头传感器的暗噪声、陀螺仪与加速度计的输出抖动。
用户行为：键盘击键间隔、鼠标轨迹的微抖动（Linux 熵池的传统熵源）。
I/O 与中断时序：磁盘读写完成的时刻、中断到达的时刻。

传感器测量+数字化

物理源	测量器件	输出形态
热噪声 / 散粒噪声 / 雪崩噪声	敏感元件（电阻、二极管）＋放大器	模拟电压（微伏级 → 放大）
时钟抖动	环形振荡器电路本身＋D 触发器	数字位，直接输出
单光子	分束器＋单光子探测器（SPAD）	电脉冲事件
放射性衰变	盖革计数器	电脉冲事件
大气噪声	无线电接收机（天线＋调谐）	模拟信号
传感器噪声	麦克风 / CMOS 图像传感器 / MEMS 陀螺仪（设备自带）	数字采样流
用户行为	键盘、鼠标（＋系统时钟）	事件时间戳
I/O 与中断时序	高精度定时器 / 时间戳计数器	数字时间差

注意：

（1）电子噪声是通过放大器+比较器来读取的，这一套相当于一个 ADC（Analog-to-Digital Converter，模数转换器，把连续变化的模拟信号（电压、电流等）转换成离散的数字量（0 和 1 组成的数值））。而严格来说单个比较器不算是 ADC（或者只能叫 1-bit ADC），因为为了让数字量更加精确，一般会取多个比较器作为 ADC（8-bit / 16-bit / 32-bit ADC...）

（2）电路自己作为传感器：环形振荡器（Ring Oscillator —— RO）是 TRNG 里最经典的熵源之一。要了解RO的原理，我们要知道一个电子元件——反相器（Inverter）。一个反相器（Inverter）的功能是：输入 1 输出 0，输入 0 输出 1。

而环形振荡器是把奇数个反相器首尾相接成环，让信号在环里不停翻转、从而产生周期振荡的电路。 为什么是奇数个？因为偶数个反相器串成环，信号翻转一圈后会回到和初始相同的值，系统会稳定在两个状态之一，不振荡。奇数个才能让每绕一圈都产生一次逻辑反转，维持振荡。那里面到底是怎么随机呢？熵来自哪里？我们不妨看看理想中的震荡周期和实际周期的区别。

   理想：  |←— T —→|←— T —→|←— T —→|←— T —→|
   真实：  |←T+δ₁→|←T+δ₂→|←T+δ₃→|←T+δ₄→|

发现了吗？真实的周期是存在噪音δ的，多个δ的累和就是熵的来源。

（3）事件型：探测器+计时。指的是一类基于离散物理事件的时间属性来提取熵的 TRNG 架构。它的核心逻辑是：等待一个物理上不可预测的事件发生，然后测量它发生的精确时间，用这个时间信息来生成随机数。把时间（不确定性）变成随机，这就是事件型TRNG的本质——利用物理事件发生时刻的不可预测性（量子事件为原理级，宏观事件为统计级），通过“探测器 + 计时”把它转换成随机数。

熵池混合

把熵池当作一个箱子，里面汇集着来自不同熵源的样本，熵池负责收集、混合、缓冲这些样本，为后面取随机数做准备。
Q：为什么需要多个熵源？
A：单一物理源的输出不稳定、不均匀、不独立，且一旦被人为或自然干扰就会有很大的风险。
怎么混合呢？哈希。

  池    ←    H (  池      ‖    新样本)
新熵池 赋值  哈希 原熵池  拼接  新样本

为什么要这么做：

（1）只要动了 1 bit，在哈希的算法下整个熵池都会和动之前的完全不一样——雪崩效应
（2）攻击者哪怕掌握了部分熵源，但是只要未被攻击者掌握的那部分里真熵足够，在多次的混合之下池的输出也会变得未知——把多个弱的熵源合成强熵，即随机性提取器（Randomness Extractor）：原始噪声源产生的比特，通常是有偏、有相关、不均匀的，不能直接用。提取器的作用是把这些“不完美”的原始比特，压缩成“接近完美”的均匀随机比特。

顺便补充，如果熵源不够，就会发生熵源饥饿：

Debian OpenSSL（2008）：有人为消调试告警，把随机数初始化的代码注释掉 → 熵只剩 PID 当种子，全世界可能的密钥只剩 32768 种，埋了两年。
Android SecureRandom（2013）：种子处理缺陷 → 比特币钱包私钥可推算，资金被盗。

可见熵源不够就会导致严重的泄露。

白化处理

TRNG本身就慢，而白化又让TRNG变得更慢了

物理采样出来的原始位流有三个毛病，直接出厂是不合格的：

有偏：0/1 比例不是 1:1（比较器阈值漂移、抖动分布不对称都会造成）
相关：相邻位不独立（连续采样共享同一个慢变的环境量）
可能含可预测成分：电源纹波、温度、周期性干扰

白化的任务：把“有偏、相关”的原始位流，洗成均匀且看起来独立的位流——洗牌

白化目前有两种主流方式：

（1）冯·诺伊曼（von Neumann）矫正器

  01 → 输出 0
  10 → 输出 1
  00 / 11 → 丢弃

Q：为什么要去掉 00 和 11 的情况？ A：因为现实中 0 和 1 分别出现的概率可能不是各 50%，我们假设 0 的概率是 p，1 的概率就是 (1-p)，这样的情况下 00 的概率为 p² 而 11 的概率是 (1-p)²，我们假设 00 输出 0 而 11 输出 1，这样就会导致最后输出的时候 0 和 1 的概率不一样，而对于冯·诺伊曼矫正器来说，无论 0 和 1 的概率分别是多少，01和10的概率都是 p(1-p)，最后输出的 0 和 1 概率是一样的。但是缺点就是会失去 ≥ 75% 的数据（因为 00 和 11 需要去掉），导致了白化效率低下。有没有效率高一点的呢？

（2）哈希提取（SHA）——高效的现代方式

   即 output =  H   ( input )
       输出  = 哈希  输入的原始样本

Q：为什么可以选哈希来白化？ A：哈希具有单向性、抗碰撞性（找不到两个不同的输入能产生相同的输出）、雪崩效应（原始数据里哪怕只有部分比特有真随机性，哈希后这些随机性会被扩散到整个输出，使得输出难以预测）、输出均匀且定长。

	冯·诺伊曼矫正器	哈希提取
原理	利用 `01`/`10` 的对称性去偏	用密码学哈希压缩混合
是否需要知道偏置(p)的大小	不需要	不需要
效率	极低（约 25% 甚至更低）	高（最高可接近 1:1 压缩）
输出均匀性保证	有严格证明（独立同分布下）	依赖哈希函数假设
抗相关性	只处理独立比特	能处理相关性
实现复杂度	极简	需要哈希函数实现
典型用途	简单 TRNG、教学	现代 TRNG、熵池

白化不增加原熵值，只是把长段的随机位流浓缩成更短的输出。

最后随机位

即输出处理筛选好的随机数，就是整条流水线的最终产品（对外输出）。

TRNG的作用

之前我们讲了TRNG的生成是慢而且昂贵的，那我们生成TRNG除了把它当真的随机数来用，还可以干嘛呢？聪明的我们想到了：如果我们把TRNG的数作为一个引子，来引出后面通过算法而快速算出的其它数，是不是就可以让TRNG发挥它很大的价值？恭喜你发明了seed与PRNG

二.伪随机 PRNG(Pseudo-Random Number Generator)

1.定义
从一个seed出发，通过算法来无限展开看上去随机的数。
(一般seed的来源是TRNG)
“伪”的定义在于可复现，不是“假”。在概率统计上可以做到很像真随机(MT19937这个PRNG能通过最严格的统计检验)，但是只要种子被猜到或被反推，整串数全部暴露。

2.特点
在于如果你知道了seed和算法，就可以在任何时间任何地点推出一模一样后面随机的数
而换一个种子（哪怕只差 1），对扩散性好的算法（如 MT19937、CSPRNG）会产生雪崩效应——输出序列完全不同。（但弱 PRNG 如 LCG 不保证这点：换种子可能只是同一循环换个相位。）

伪随机通过算法出来的随机数本质上是数列，状态是有限的 → 数列必有周期（状态空间绕一圈就回来了）。所以“周期多长、状态多大”是评价 PRNG 质量的第一硬指标。
状态越大越难看出规律——MT 的状态有 19937 bit，周期是天文数字 2¹⁹⁹³⁷−1。

3.过程

种子 seed
   │ 播种   初始状态 = 种子（或种子的哈希展开）
   ▼
状态 s₀ ──输出──▶ 随机数 ①   输出：从当前状态算出一个对外数值 o = f(s)
   │ 更新   更新：内部状态前进 s' = g(s)
   ▼
状态 s₁ ──输出──▶ 随机数 ②
   │ 更新
   ▼
状态 s₂ ──输出──▶ 随机数 ③ …

4.主流算法

(1). 经典的 LCG(Linear Congruential Generator，线性同余发生器)

LCG的递推公式很简单

   X_{n+1}  =  (a ·  X_n  +  c)  mod   m
   X：状态序列  a：乘数     c：增量   m：模数     X₀：种子
   
   取 a = 5, c = 3, m = 16, X₀ = 1：
   X₁ = (5·1 + 3) mod 16 = 8
   X₂ = (5·8 + 3) mod 16 = 43 mod 16 = 11
   X₃ = (5·11 + 3) mod 16 = 58 mod 16 = 10
   X₄ = (5·10 + 3) mod 16 = 53 mod 16 = 5
   X₅ = (5·5 + 3) mod 16 = 28 mod 16 = 12
   ...

看上去是随机的，实际上完全由算法决定。 Q：既然是数列，那会不会出现一种情况：在周期内的数无法覆盖 0 到 m−1 内的所有数字？ A：是的，因此，为了防止这样的情况发生，我们利用了Hull-Dobell 定理

   Hull-Dobell 定理

   LCG 达到满周期（周期 = m）的充要条件：
   1. c 与 m 互质
   2. a − 1 能被 m 的所有质因子整除
   3. 如果 m 是 4 的倍数，则 a − 1 必须是 4 的倍数
   满足这三条，LCG 就能在 0 到 m−1 之间遍历所有值。

LCG 在对于c是否为 0 的情况存在两种不同的算法

1. c = 0 时是乘法LCG （也叫做Lehmer 发生器）公式如下

$$ X_{n+1} = (a·X_n) mod m $$
特点：周期最多为m-1，实现简单。典型是MINSTD（minimal standard）感兴趣可以上网搜索相关资料了解，后面常见参数选择也会给到m、a、c的取值

2. c ≠ 0 时是混合LCG 公式如下

$$X_{n+1} = (a·X_n + c) mod m$$
特点：周期最多为m，实现略微复杂。典型为C库的rand( )

虽然LCG这么的简单快速，但是LCG也有很大的缺陷：周期有限（最多 m，通常 2³¹ 或 2³²），低位质量非常差，可预测，统计性差（无法通过严格的随机性测试）

常见的参数选择

用途	m	a	c
C 库 `rand()` / glibc（老实现）	2³¹	1103515245	12345
Numerical Recipes	2³²	1664525	1013904223
MINSTD	2³¹−1	16807	0

(2). LFSR （Linear Feedback Shift Register，线性反馈移位寄存器） 也是一种经典的PRNG，在硬件和通信领域更常见。

它并不是整数，而是一串比特，而在每个时钟周期都会循环做以下的事情：1.所有比特右移一位。2.最右侧的比特丢弃或输出。3.最左边未填充的地方填入一个反馈比特，由一些比特异或得到。

   ┌─────┬─────┬─────┬─────┐
   │ b₃  │ b₂  │ b₁  │ b₀  │ → 输出
   └──┬──┴──┬──┴──┬──┴─────┘
      │     │     │
      └─────┴─────┘
           ↓
         异或 → 反馈到最左边

如果寄存器有 n 位，状态是 (b_{n-1}, ..., b₁, b₀)，那么每个周期：

    新最高位 = c_{n-1}·b_{n-1} ⊕ ... ⊕ c₁·b₁ ⊕ c₀·b₀

其中 c_i 是反馈系数（0 或 1），决定哪些位参与异或。

整体移位：

    b_i ← b_{i-1}  （所有位右移）
    b_{n-1} ← 反馈比特

LFSR 的优点在于它的速度很快，适合硬件（硬件的需求很简单），统计性质好。但是缺点在于它依旧是线性的（本质上它是 GF(2) 上的线性函数，可以被反推——用 Berlekamp–Massey 算法破解），可预测（知道 2n 个连续输出比特，就能重建整个 LFSR）
有没有状态大得多的 PRNG 呢？有的兄弟有的。隆重介绍：

(3). MT19937 梅森旋转 （Mersenne Twister 19937）

是迄今为止使用最广泛的通用 PRNG 之一。Python 的 random 模块、NumPy、Ruby、PHP 等很多语言的默认随机数都基于它。 MT 是梅森旋转算法，而 19937 是状态的位数（19937 bit），周期为 2¹⁹⁹³⁷ − 1 为什么叫“梅森”：2¹⁹⁹³⁷ − 1 是一个梅森素数（形如 2^p − 1 的素数）。算法名字就来自这个数学对象。 为什么叫“旋转”：算法的核心操作是对状态数组进行旋转和扭曲（twist），所以叫 Twister。

工作流程如下

    种子 → 初始化状态数组（624 个字）
           ↓
        [状态数组]
           ↓
      ┌─────────────┐
      │  Twist 旋转  │  ← 每 624 次输出后才做一次
      └─────────────┘
           ↓
      ┌─────────────┐
      │ Tempering   │  ← 每次输出都做
      │   回火       │
      └─────────────┘
           ↓
        输出一个 32 位字

1.初始化
先给一个32位整数作为种子，然后MT19937来填满624个状态字。
伪代码表示如下：

    state[0] = seed
    for i = 1 到 623:
        state[i] = 1812433253 × (state[i-1] ⊕ (state[i-1] >> 30)) + i
        # 全程按 mod 2³² 运算

怕你看不懂（其实我也没看懂）我做了如下解释：
初始化的目的就是把一个32位的种子扩散成一个624个32位字的大数组。
其中state[0]是seed，而显然state[i]是由state[i - 1]推出来的。
递推公式如下

state[i-1] >> 30 // 步骤1：取前一个字的高 2 位

state[i-1] ⊕ (上面步骤1结果) // 步骤2：异或回自身

1812433253 × (上面步骤2结果) // 步骤3：乘以一个常数

(上面步骤3结果) + i // 步骤4：加上下标 i

用python写就是这样的

# ============================================================
# MT19937 初始化：用种子生成 624 个状态字
# ============================================================

N = 624                  # 状态数组大小
INIT_MULT = 1812433253   # 初始化用的常数
MASK32 = 0xFFFFFFFF      # 用于取低 32 位

def init_state(seed):
    """
    输入：seed（32 位整数）
    输出：state（长度 624 的列表，每个元素是 32 位整数）
    """
    state = [0] * N

    # 第一步：把种子放进 state[0]，只保留低 32 位
    state[0] = seed & MASK32

    # 第二步：递推生成 state[1] 到 state[623]
    for i in range(1, N):
        prev = state[i - 1]

        # 取前一个字的高 2 位，异或回自身
        # 作用：让高位信息影响低位，增加混合
        mixed = prev ^ (prev >> 30)

        # 乘以常数，加上下标 i，再取低 32 位
        # 乘法在 mod 2^32 下起扩散作用
        # 加 i 是为了打破对称性，防止退化
        state[i] = (INIT_MULT * mixed + i) & MASK32

    return state

完成这一步初始化（已经循环624次）之后，还不能直接输出之后的数字，而是要进行下一步：twist

Twist 完整代码如下：

for i in range(624):
    y = (state[i] & 0x80000000) | (state[(i+1) % 624] & 0x7FFFFFFF)

    # 拼接 y 从两个相邻的状态字里各取一部分，拼成一个新的 32 位值 y
    # y的结构最终会变成如下：
    # y = [state[i] 的最高位] + [state[i+1] 的低 31 位]
    #        ← 1 位 →              ← 31 位 →
    # 特地考虑到当 i = 623时 i + 1 = 624 %624 = 0 ，也就是 623 和 0 进行Twist

    state[i] = state[(i+397) % 624] ^ (y >> 1)
    #这一步用 偏移 397 位置的字 和 y 的右移一位 做异或，得到新的 state[i]。
    #选397是保证了这个周期的长度，包括624也是如此，它们都是固定参数
    #>>1也是特征式的一部分

    if y & 1:
        state[i] ^= 0x9908B0DF
    #如果 y 的最低位是 1，就把 state[i] 和魔数 0x9908B0DF 异或。
    #为什么需要这一步
    #在 GF(2) 上，矩阵乘法可以写成：
    #新状态 = T × 旧状态
    #当 y 的最低位是 1 时，y >> 1会丢失这个 1。为了补偿这个丢失的信息，需要异或一个固定值。
    #这个固定值 0x9908B0DF 就是特征多项式对应的反馈常数。它保证整个变换在 GF(2) 上是线性的、可逆的，并且满足周期要求。
    #当然觉得比较复杂也可以先放放，这里的异或的原因和解释为什么是397和624的原因差不多

这样你就得到了下一组数据（共624个）
也就是第625 626 ... 1248个数
可能我这么说还难以理解。那简单来说，Twist就是将一开始初始化好的数字变成下一组新的随机数，而输出的第625号数字则是Tempering(新 state[0]) —— 对应 1号数字， 626则是对应的2号数字。当然只是位置一样，它们的内容完全不一样。这里也可能会产生误区说625和1是必然联系，实际上是不对的，准确来说625的产生是和前624个数都有关系。
你可以这么理解

    [1,  2,  3,  4 .... 624]
    [625,626,627,628....1248]
    1 和 625 属于结构型同构

相较于之前讲的 LFSR，MT19937 的最大优势在于它的高维均匀性非常好（得益于 MT 算法，Twist 操作被专门设计来保证高维均匀——这个以后单独展开）。相比 n 只有几十、几百位的 LFSR，它有 624 个 32 位字的状态，更难被反推，周期也大得多。
核心区别也在于它们的输出方式：LFSR 每个时钟只吐 1 bit；而 MT19937 每次输出一个 32 位字，底下的状态每 624 个字才 twist 一次。

缺点仍然在于数列的可倒推性，如果攻击者拿到了一组连续的（624）数，就可以重建状态，虽然难，但是不代表不可以。

以上介绍的LCG LFSR MT19937都有一个共同特点：线性方程的可预测性，这也预示着这些 PRNG 是不安全的，那么就要问了：有没有什么PRNG是安全的呢？有的兄弟有的。

下面介绍CSPRNG (Cryptographically Secure Pseudo-Random Number Generator)

密码学安全伪随机数发生器，也会叫做 CPRNG、DRBG

为什么安全？
建立在两个核心上：计算不可区分性和单向性

不可区分性指：它的输出必须让任何多项式时间的攻击者都无法区分其与TRNG的差异，即CSPRNG 的输出序列必须在计算上无法与真正的随机序列区分。攻击者即使知道算法，也无法以显著优于猜测的概率预测下一位或下几位比特。

单向性指：无法（极难）反推，CSPRNG 本质上是一个单向函数。给定种子顺推容易，但是知道过程反推种子极其困难，哪怕攻击者拿到了很多很多很多的输出，但是依旧难以反推种子（通常关联到 P vs NP 问题，感兴趣可以了解一下，千禧年七大数学难题之一）。这保证了即使部分输出泄露，攻击者也无法重构生成器状态来预测未来输出。

以下是主流的CSPRNG介绍，了解即可

算法类别	典型代表	核心原理与安全依据
基于分组密码	CTR_DRBG (如 AES-CTR)	使用 AES 等分组密码在计数器模式下加密一个递增的计数值来产生密钥流。其安全性直接归约到底层分组密码的安全性（即 AES 是伪随机置换）。
基于密码学哈希	Hash_DRBG / HMAC_DRBG	基于 SHA-256 等哈希函数的单向性和抗碰撞性构建。NIST SP 800-90A 标准推荐，安全性依赖于哈希函数的伪随机性。
流密码方案	ChaCha20	一种高速流密码，其核心是 ARX（加法-旋转-异或）结构。通过模加运算引入非线性，设计上天然抵抗时序攻击（无查表操作）。
专用架构	Fortuna	由 Ferguson 和 Schneier 设计，采用“熵池 + 生成器”分离的架构。使用 32 个熵池收集输入，即使部分熵源被污染，只要攻击者没有掌握此后全部的熵事件，下一次重新播种后整体安全性就能恢复。

所以当我们选择CSPRNG时，应优先使用标准化且经过严格分析的方案：CTR_DRBG（AES） 是硬件加速场景的首选，ChaCha20 是软件实现和抗侧信道场景的优选，而 Fortuna 则适合需要长期运行且需应对熵源不确定性的系统级应用。但是前提是我们需要一个高质量熵源（一般都是用的TRNG）来提供种子。

三.PRNG 如何在 CTF 中打穿

擒贼先擒王

打穿PRNG的关键在于：你得知道它是哪种类型的PRNG，是LCG？MT19937？还是LFSR？CSPRNG？
这本质上是一个统计推断 + 逆向工程的问题。你拿到一串输出，想反推它背后是哪种 PRNG。能做到什么程度，取决于三个因素：

你拿到了多少输出

你对候选算法了解多少

目标 PRNG 的“指纹”有多明显

~~当然，运气再好一点（种子空间很小，或者种子本身可猜），你甚至不用判定类型——直接枚举种子，生成序列对照一下就行了~~

随后对于部分非CSPRNG有专门的解法

LCG：几个连续输出 → 解方程恢复参数/状态（条件不足时还有“截断 LCG”格攻击这一路）

LFSR：约 2n 位输出 → Berlekamp–Massey 直接还原反馈多项式

MT19937：攒 624 个连续 32 位输出 → untwist 反推整个状态；种子空间小的话连输出都不用攒——直接枚举种子

import random
from randcrack import RandCrack

# 1. 收集 624 个 32 位整数输出(任意连续即可)
rc = RandCrack()
for _ in range(624):
    # 用 getrandbits(32) 直接获取 32 位输出
    rc.submit(random.getrandbits(32))
  
# 2. 状态已恢复，现在可以预测
predicted = rc.predict_getrandbits(32)
actual = random.getrandbits(32)
print(f"预测值: {predicted}, 实际值: {actual}")  # 两者应相同

# 也可以预测原本的 random.random()
predicted_float = rc.predict_random()
actual_float = random.random()
print(f"预测浮点数: {predicted_float}, 实际浮点数: {actual_float}")

如果是 CSPRNG，就把它当用法问题查（熵池饥饿之类）——不过这太难了，直接逆向出 CSPRNG 的 seed？那是何方神圣。

第三节：所以，回答开头的问题

PRNG真的随机吗？
从概率统计上来看，那些质量高的PRNG能够满足统计学的随机，但是PRNG不同于真正随机的TRNG，它仍然是由算法从一个种子顺推到后面的随机数的（无论是普通的 PRNG 还是 CSPRNG）。——不过，这是“作者”视角的观察（作者 = 知道种子和算法的人）。
当我们以“读者”的视角来观察 PRNG 的时候（读者 = 只能看到输出的人），正常情况下我们也无法预判下一个数到底是什么。当然作为攻击者而言，LCG，MT19937这样的PRNG仍然是有被反推回种子的可能性，就算是CSPRNG也可以通过暴力枚举这样的方式来猜出种子，但是为什么安全？就在于它虽然有被猜出来的概率，但是当猜出来这个种子所要花的时间金钱远大于攻击者想要获取的内容价值，或者在时间上：找到种子花的时间远高于种子更换的时间（比如枚举出生成令牌的种子可能需要好几年，但令牌一天就自动换一次），这个时候，进攻的路就被封死了——从概率上并不为 0，但从成本上：破解要花的钱和时间远超收益、或远超令牌的有效期，这条路就等于封死。这就是密码学里的“计算安全”：不是不可破，而是不值得破。

抛硬币真的随机吗？
其实抛硬币相当于一台“力学 PRNG”：如果你能精确知道手用力的大小、硬币的质量、抛的高度、空气阻力……一切初始条件，结果就被物理定律定死了——但这些条件无法精确测量，也没人会去测。所以答案是：在物理定律的意义上它不是随机，在我们的测量能力面前它是随机。

那面对不同的情况，我们要怎么选随机呢？

如果你想把这个数作为种子，或者想要一个质量很高的熵源——TRNG
如果你想把这个数字当作密钥/令牌/密码——CSPRNG（Python 里的 secrets 模块）
如果你只是想要一个游戏/模拟的随机——普通 PRNG（Python 里的 random 模块）

它们都有各自的优缺点，怎么选的关键在于：它需不需要安全？需不需要快速？

第四节：总结

随机在计算机的世界中占据了一个很重要的地位，普通的 TRNG 虽然可以产生高质量熵源，但它又慢又贵——为了“让人无法预判”这一件事，要花掉非常多的钱。而 PRNG 要做的，就是用算法让你辨别不出它到底是不是真的随机。为了让PRNG看上去更像是TRNG，算法工程师们潜心研究，发明了各种的PRNG算法来面对不同的情境。

用一个seed来长出“随机”的大树。

下一站预告：单机随机解决了，那互不信任的多方怎么一起产生随机？

Cola_CaO
2026.10.15

这里开始讲一讲伪随机和真随机的内容喔。整理的不一定很完全希望批评指正！

抛硬币是随机吗？

第一节：什么是随机

随机在目前有两种解释

1.每个选项的概率平均

例如1和0的随机输出当基数足够大的时候应该各占50%，满足平均分布各个选项

2.不可预判性

这和1的概念有违背，它的意思是可能当基数足够大的时候并没有各占50%，但是保证你无法预判下一次的出0或1的概率

不可预判性让每次的概率都独立存在，哪怕是在100次的1 0随机中，前99次有49次0和50次1，第100次0和1的概率也是各50%的概率

第二节：随机种类

随机分为真随机和伪随机，它们有各自的优缺点

随机方式	优点	缺点
真随机TRNG	完全无法预测，通过物理方式来随机	生成速度慢，价格昂贵
伪随机PRNG	可快速生成大量随机数	伪随机本质通过算法生成，只是因为接收方不知道种子，看上去没有规律可循，无法预判之后的随机

接下来我们来仔细讲讲真随机和伪随机的生成方式

一.真随机 TRNG

要了解TRNG的生成方式，首先我们要知道一个概念——熵

那么在TRNG这里，熵的概念就可以理解成不确定性的量，随机数的生成源自于一个或一类不确定量的产生（比如电子噪声、时钟抖动、量子真空涨落等）

而TRNG的生成过程大致就是如下：

物理现象 → 传感器测量 → 采样数字化 → (熵池混合) → 白化后处理 → 随机位
└────────── 熵源：真随机在这一段 ──────────┘   └─ von Neumann / SHA-256 ─┘

下面我们来一个个讲其中的概念

物理现象：即熵的原产地。一般来说，物理源来自于以下的几个部分：

1. 电子噪声类 —— 电场里的随机涨落

热噪声（Johnson–Nyquist 噪声）：电阻里的电子做热运动，造成两端电压的随机微波动。是硬件RNG的主力。
散粒噪声（shot noise）：电流的本质是离散的电子流，单位时间内穿过 PN 结的电子个数有泊松涨落。
雪崩噪声：二极管反向击穿时，载流子雪崩倍增的过程不可控，噪声幅度大的特点让它也适合随机采样。

2. 时钟抖动类 —— 把噪声翻译成时间

时钟抖动 / 振荡器相位噪声：振荡电路的边沿时刻，会被电路内部的噪声（以热噪声为主）随机推来推去。
环形振荡器（ring oscillator）：做两个频率略有差异的振荡环，让快的去采样慢的，采到的 0/1 由抖动决定。FPGA、CPU、智能卡里最流行；它的“乱”追到底依然是热噪声，只是形态从电压换成了时刻。

3. 量子 / 核物理类 —— 原理级不可预测

单光子行为：光子通过半透半反镜时走哪条路、何时到达探测器，都不可预测。
量子真空涨落：真空并不“空”，零点涨落天然随机，商用量子 RNG 卡就基于它。
放射性衰变：原子核何时衰变，物理上不可预测（HotBits 网站的老配方）。
这类与前两类有个本质区别：电子噪声的“不可预测”来自自由度太多、算不过来；量子过程则是原理保证“压根没定”。

4. 环境与传感器类 —— 宏观世界的混沌

大气静电噪声：用无线电接收大气噪声（random.org 就靠这个）。
传感器噪声：麦克风底噪、摄像头传感器的暗噪声、陀螺仪与加速度计的输出抖动。
用户行为：键盘击键间隔、鼠标轨迹的微抖动（Linux 熵池的传统熵源）。
I/O 与中断时序：磁盘读写完成的时刻、中断到达的时刻。

传感器测量+数字化

物理源	测量器件	输出形态
热噪声 / 散粒噪声 / 雪崩噪声	敏感元件（电阻、二极管）＋放大器	模拟电压（微伏级 → 放大）
时钟抖动	环形振荡器电路本身＋D 触发器	数字位，直接输出
单光子	分束器＋单光子探测器（SPAD）	电脉冲事件
放射性衰变	盖革计数器	电脉冲事件
大气噪声	无线电接收机（天线＋调谐）	模拟信号
传感器噪声	麦克风 / CMOS 图像传感器 / MEMS 陀螺仪（设备自带）	数字采样流
用户行为	键盘、鼠标（＋系统时钟）	事件时间戳
I/O 与中断时序	高精度定时器 / 时间戳计数器	数字时间差

注意：

（1）电子噪声是通过放大器+比较器来读取的，这一套相当于一个 ADC（Analog-to-Digital Converter，模数转换器，把连续变化的模拟信号（电压、电流等）转换成离散的数字量（0 和 1 组成的数值））。而严格来说单个比较器不算是 ADC（或者只能叫 1-bit ADC），因为为了让数字量更加精确，一般会取多个比较器作为 ADC（8-bit / 16-bit / 32-bit ADC...）

（2）电路自己作为传感器：环形振荡器（Ring Oscillator —— RO）是 TRNG 里最经典的熵源之一。要了解RO的原理，我们要知道一个电子元件——反相器（Inverter）。一个反相器（Inverter）的功能是：输入 1 输出 0，输入 0 输出 1。

   理想：  |←— T —→|←— T —→|←— T —→|←— T —→|
   真实：  |←T+δ₁→|←T+δ₂→|←T+δ₃→|←T+δ₄→|

发现了吗？真实的周期是存在噪音δ的，多个δ的累和就是熵的来源。

（3）事件型：探测器+计时。指的是一类基于离散物理事件的时间属性来提取熵的 TRNG 架构。它的核心逻辑是：等待一个物理上不可预测的事件发生，然后测量它发生的精确时间，用这个时间信息来生成随机数。把时间（不确定性）变成随机，这就是事件型TRNG的本质——利用物理事件发生时刻的不可预测性（量子事件为原理级，宏观事件为统计级），通过“探测器 + 计时”把它转换成随机数。

熵池混合

  池    ←    H (  池      ‖    新样本)
新熵池 赋值  哈希 原熵池  拼接  新样本

为什么要这么做：

（1）只要动了 1 bit，在哈希的算法下整个熵池都会和动之前的完全不一样——雪崩效应
（2）攻击者哪怕掌握了部分熵源，但是只要未被攻击者掌握的那部分里真熵足够，在多次的混合之下池的输出也会变得未知——把多个弱的熵源合成强熵，即随机性提取器（Randomness Extractor）：原始噪声源产生的比特，通常是有偏、有相关、不均匀的，不能直接用。提取器的作用是把这些“不完美”的原始比特，压缩成“接近完美”的均匀随机比特。

顺便补充，如果熵源不够，就会发生熵源饥饿：

Debian OpenSSL（2008）：有人为消调试告警，把随机数初始化的代码注释掉 → 熵只剩 PID 当种子，全世界可能的密钥只剩 32768 种，埋了两年。
Android SecureRandom（2013）：种子处理缺陷 → 比特币钱包私钥可推算，资金被盗。

可见熵源不够就会导致严重的泄露。

白化处理

TRNG本身就慢，而白化又让TRNG变得更慢了

物理采样出来的原始位流有三个毛病，直接出厂是不合格的：

有偏：0/1 比例不是 1:1（比较器阈值漂移、抖动分布不对称都会造成）
相关：相邻位不独立（连续采样共享同一个慢变的环境量）
可能含可预测成分：电源纹波、温度、周期性干扰

白化的任务：把“有偏、相关”的原始位流，洗成均匀且看起来独立的位流——洗牌

白化目前有两种主流方式：

（1）冯·诺伊曼（von Neumann）矫正器

  01 → 输出 0
  10 → 输出 1
  00 / 11 → 丢弃

（2）哈希提取（SHA）——高效的现代方式

   即 output =  H   ( input )
       输出  = 哈希  输入的原始样本

	冯·诺伊曼矫正器	哈希提取
原理	利用 `01`/`10` 的对称性去偏	用密码学哈希压缩混合
是否需要知道偏置(p)的大小	不需要	不需要
效率	极低（约 25% 甚至更低）	高（最高可接近 1:1 压缩）
输出均匀性保证	有严格证明（独立同分布下）	依赖哈希函数假设
抗相关性	只处理独立比特	能处理相关性
实现复杂度	极简	需要哈希函数实现
典型用途	简单 TRNG、教学	现代 TRNG、熵池

白化不增加原熵值，只是把长段的随机位流浓缩成更短的输出。

最后随机位

即输出处理筛选好的随机数，就是整条流水线的最终产品（对外输出）。

TRNG的作用

二.伪随机 PRNG(Pseudo-Random Number Generator)

3.过程

种子 seed
   │ 播种   初始状态 = 种子（或种子的哈希展开）
   ▼
状态 s₀ ──输出──▶ 随机数 ①   输出：从当前状态算出一个对外数值 o = f(s)
   │ 更新   更新：内部状态前进 s' = g(s)
   ▼
状态 s₁ ──输出──▶ 随机数 ②
   │ 更新
   ▼
状态 s₂ ──输出──▶ 随机数 ③ …

4.主流算法

(1). 经典的 LCG(Linear Congruential Generator，线性同余发生器)

LCG的递推公式很简单

   X_{n+1}  =  (a ·  X_n  +  c)  mod   m
   X：状态序列  a：乘数     c：增量   m：模数     X₀：种子
   
   取 a = 5, c = 3, m = 16, X₀ = 1：
   X₁ = (5·1 + 3) mod 16 = 8
   X₂ = (5·8 + 3) mod 16 = 43 mod 16 = 11
   X₃ = (5·11 + 3) mod 16 = 58 mod 16 = 10
   X₄ = (5·10 + 3) mod 16 = 53 mod 16 = 5
   X₅ = (5·5 + 3) mod 16 = 28 mod 16 = 12
   ...

   Hull-Dobell 定理

   LCG 达到满周期（周期 = m）的充要条件：
   1. c 与 m 互质
   2. a − 1 能被 m 的所有质因子整除
   3. 如果 m 是 4 的倍数，则 a − 1 必须是 4 的倍数
   满足这三条，LCG 就能在 0 到 m−1 之间遍历所有值。

LCG 在对于c是否为 0 的情况存在两种不同的算法

1. c = 0 时是乘法LCG （也叫做Lehmer 发生器）公式如下

2. c ≠ 0 时是混合LCG 公式如下

$$X_{n+1} = (a·X_n + c) mod m$$
特点：周期最多为m，实现略微复杂。典型为C库的rand( )

常见的参数选择

用途	m	a	c
C 库 `rand()` / glibc（老实现）	2³¹	1103515245	12345
Numerical Recipes	2³²	1664525	1013904223
MINSTD	2³¹−1	16807	0

(2). LFSR （Linear Feedback Shift Register，线性反馈移位寄存器） 也是一种经典的PRNG，在硬件和通信领域更常见。

   ┌─────┬─────┬─────┬─────┐
   │ b₃  │ b₂  │ b₁  │ b₀  │ → 输出
   └──┬──┴──┬──┴──┬──┴─────┘
      │     │     │
      └─────┴─────┘
           ↓
         异或 → 反馈到最左边

如果寄存器有 n 位，状态是 (b_{n-1}, ..., b₁, b₀)，那么每个周期：

    新最高位 = c_{n-1}·b_{n-1} ⊕ ... ⊕ c₁·b₁ ⊕ c₀·b₀

其中 c_i 是反馈系数（0 或 1），决定哪些位参与异或。

整体移位：

    b_i ← b_{i-1}  （所有位右移）
    b_{n-1} ← 反馈比特

(3). MT19937 梅森旋转 （Mersenne Twister 19937）

工作流程如下

    种子 → 初始化状态数组（624 个字）
           ↓
        [状态数组]
           ↓
      ┌─────────────┐
      │  Twist 旋转  │  ← 每 624 次输出后才做一次
      └─────────────┘
           ↓
      ┌─────────────┐
      │ Tempering   │  ← 每次输出都做
      │   回火       │
      └─────────────┘
           ↓
        输出一个 32 位字

1.初始化
先给一个32位整数作为种子，然后MT19937来填满624个状态字。
伪代码表示如下：

    state[0] = seed
    for i = 1 到 623:
        state[i] = 1812433253 × (state[i-1] ⊕ (state[i-1] >> 30)) + i
        # 全程按 mod 2³² 运算

state[i-1] >> 30 // 步骤1：取前一个字的高 2 位

state[i-1] ⊕ (上面步骤1结果) // 步骤2：异或回自身

1812433253 × (上面步骤2结果) // 步骤3：乘以一个常数

(上面步骤3结果) + i // 步骤4：加上下标 i

用python写就是这样的

# ============================================================
# MT19937 初始化：用种子生成 624 个状态字
# ============================================================

N = 624                  # 状态数组大小
INIT_MULT = 1812433253   # 初始化用的常数
MASK32 = 0xFFFFFFFF      # 用于取低 32 位

def init_state(seed):
    """
    输入：seed（32 位整数）
    输出：state（长度 624 的列表，每个元素是 32 位整数）
    """
    state = [0] * N

    # 第一步：把种子放进 state[0]，只保留低 32 位
    state[0] = seed & MASK32

    # 第二步：递推生成 state[1] 到 state[623]
    for i in range(1, N):
        prev = state[i - 1]

        # 取前一个字的高 2 位，异或回自身
        # 作用：让高位信息影响低位，增加混合
        mixed = prev ^ (prev >> 30)

        # 乘以常数，加上下标 i，再取低 32 位
        # 乘法在 mod 2^32 下起扩散作用
        # 加 i 是为了打破对称性，防止退化
        state[i] = (INIT_MULT * mixed + i) & MASK32

    return state

完成这一步初始化（已经循环624次）之后，还不能直接输出之后的数字，而是要进行下一步：twist

Twist 完整代码如下：

for i in range(624):
    y = (state[i] & 0x80000000) | (state[(i+1) % 624] & 0x7FFFFFFF)

    # 拼接 y 从两个相邻的状态字里各取一部分，拼成一个新的 32 位值 y
    # y的结构最终会变成如下：
    # y = [state[i] 的最高位] + [state[i+1] 的低 31 位]
    #        ← 1 位 →              ← 31 位 →
    # 特地考虑到当 i = 623时 i + 1 = 624 %624 = 0 ，也就是 623 和 0 进行Twist

    state[i] = state[(i+397) % 624] ^ (y >> 1)
    #这一步用 偏移 397 位置的字 和 y 的右移一位 做异或，得到新的 state[i]。
    #选397是保证了这个周期的长度，包括624也是如此，它们都是固定参数
    #>>1也是特征式的一部分

    if y & 1:
        state[i] ^= 0x9908B0DF
    #如果 y 的最低位是 1，就把 state[i] 和魔数 0x9908B0DF 异或。
    #为什么需要这一步
    #在 GF(2) 上，矩阵乘法可以写成：
    #新状态 = T × 旧状态
    #当 y 的最低位是 1 时，y >> 1会丢失这个 1。为了补偿这个丢失的信息，需要异或一个固定值。
    #这个固定值 0x9908B0DF 就是特征多项式对应的反馈常数。它保证整个变换在 GF(2) 上是线性的、可逆的，并且满足周期要求。
    #当然觉得比较复杂也可以先放放，这里的异或的原因和解释为什么是397和624的原因差不多

    [1,  2,  3,  4 .... 624]
    [625,626,627,628....1248]
    1 和 625 属于结构型同构

缺点仍然在于数列的可倒推性，如果攻击者拿到了一组连续的（624）数，就可以重建状态，虽然难，但是不代表不可以。

下面介绍CSPRNG (Cryptographically Secure Pseudo-Random Number Generator)

密码学安全伪随机数发生器，也会叫做 CPRNG、DRBG

为什么安全？
建立在两个核心上：计算不可区分性和单向性

以下是主流的CSPRNG介绍，了解即可

算法类别	典型代表	核心原理与安全依据
基于分组密码	CTR_DRBG (如 AES-CTR)	使用 AES 等分组密码在计数器模式下加密一个递增的计数值来产生密钥流。其安全性直接归约到底层分组密码的安全性（即 AES 是伪随机置换）。
基于密码学哈希	Hash_DRBG / HMAC_DRBG	基于 SHA-256 等哈希函数的单向性和抗碰撞性构建。NIST SP 800-90A 标准推荐，安全性依赖于哈希函数的伪随机性。
流密码方案	ChaCha20	一种高速流密码，其核心是 ARX（加法-旋转-异或）结构。通过模加运算引入非线性，设计上天然抵抗时序攻击（无查表操作）。
专用架构	Fortuna	由 Ferguson 和 Schneier 设计，采用“熵池 + 生成器”分离的架构。使用 32 个熵池收集输入，即使部分熵源被污染，只要攻击者没有掌握此后全部的熵事件，下一次重新播种后整体安全性就能恢复。

三.PRNG 如何在 CTF 中打穿

擒贼先擒王

你拿到了多少输出

你对候选算法了解多少

目标 PRNG 的“指纹”有多明显

~~当然，运气再好一点（种子空间很小，或者种子本身可猜），你甚至不用判定类型——直接枚举种子，生成序列对照一下就行了~~

随后对于部分非CSPRNG有专门的解法

LCG：几个连续输出 → 解方程恢复参数/状态（条件不足时还有“截断 LCG”格攻击这一路）

LFSR：约 2n 位输出 → Berlekamp–Massey 直接还原反馈多项式

MT19937：攒 624 个连续 32 位输出 → untwist 反推整个状态；种子空间小的话连输出都不用攒——直接枚举种子

import random
from randcrack import RandCrack

# 1. 收集 624 个 32 位整数输出(任意连续即可)
rc = RandCrack()
for _ in range(624):
    # 用 getrandbits(32) 直接获取 32 位输出
    rc.submit(random.getrandbits(32))
  
# 2. 状态已恢复，现在可以预测
predicted = rc.predict_getrandbits(32)
actual = random.getrandbits(32)
print(f"预测值: {predicted}, 实际值: {actual}")  # 两者应相同

# 也可以预测原本的 random.random()
predicted_float = rc.predict_random()
actual_float = random.random()
print(f"预测浮点数: {predicted_float}, 实际浮点数: {actual_float}")

如果是 CSPRNG，就把它当用法问题查（熵池饥饿之类）——不过这太难了，直接逆向出 CSPRNG 的 seed？那是何方神圣。

第三节：所以，回答开头的问题

那面对不同的情况，我们要怎么选随机呢？

如果你想把这个数作为种子，或者想要一个质量很高的熵源——TRNG
如果你想把这个数字当作密钥/令牌/密码——CSPRNG（Python 里的 secrets 模块）
如果你只是想要一个游戏/模拟的随机——普通 PRNG（Python 里的 random 模块）

它们都有各自的优缺点，怎么选的关键在于：它需不需要安全？需不需要快速？

第四节：总结

用一个seed来长出“随机”的大树。

下一站预告：单机随机解决了，那互不信任的多方怎么一起产生随机？

Cola_CaO
2026.10.15

什么是随机？PRNG真的随机吗？

随机到底是什么？

第一节：什么是随机

第二节：随机种类

一.真随机 TRNG

二.伪随机 PRNG(Pseudo-Random Number Generator)

下面介绍CSPRNG (Cryptographically Secure Pseudo-Random Number Generator)

三.PRNG 如何在 CTF 中打穿

第三节：所以，回答开头的问题

第四节：总结

什么是随机？PRNG真的随机吗？

第一节：什么是随机

第二节：随机种类

一.真随机 TRNG

二.伪随机 PRNG(Pseudo-Random Number Generator)

下面介绍CSPRNG (Cryptographically Secure Pseudo-Random Number Generator)

三.PRNG 如何在 CTF 中打穿

第三节：所以，回答开头的问题

第四节：总结