[原创]自定义LCG洗牌算法的种子空间坍缩分析与反推实践-密码应用-看雪安全社区

[原创]自定义LCG洗牌算法的种子空间坍缩分析与反推实践

发表于: 2026-8-25 14:49 209

[原创]自定义LCG洗牌算法的种子空间坍缩分析与反推实践

梧桐生

2026-8-25 14:49

209

> 声明：本文为纯技术分析，不针对任何具体已运营产品。文中涉及的算法结构来自反编译观察，
> 卡牌ID、数值样例均为脱敏/构造数据，不对应任何真实游戏内容。

## 0. 前言

移动端游戏客户端里很常见这样一种设计：战斗开始前，服务器下发一个随机数种子（seed），
客户端本地用这个种子初始化一个PRNG，对固定的一副卡/一组资源做洗牌，得到本局的实际顺序。
这种设计的出发点通常是省流量、省服务端算力——服务器只需要传一个4字节的整数，剩下的计算
全部交给客户端。

这篇文章记录一次完整的技术分析过程：给定客户端本地的洗牌实现（来自反编译），能否在不
hook客户端进程的前提下，仅凭观测到的洗牌结果反推出服务器下发的种子。整个过程涉及到
LCG的代数性质、Fisher-Yates算法的双射结构、信息论角度的可行性判定，以及最终从Python到
纯前端JS的工程实现。

本文中的 `ReentrantRand` 洗牌算法，来自笔者此前分析的同一款游戏，是那次分析之外的
一个额外副产物：[《某手游逆向全流程复盘：从 IL2CPP Dump 到 TCP 握手协议还原》
](https://bbs.kanxue.com/thread-290459.htm)。前文聚焦网络协议层（TCP握手、AES会话
密钥、RSA密钥交换、Puerts脚本层协议还原），本文则单独展开客户端本地洗牌逻辑这一支线。

---

## 1. 目标算法

反编译得到的核心类如下（变量名做了适当整理，逻辑保持原样）：

```python
class ReentrantRand:
    MASK32 = 0xFFFFFFFF

def __init__(self, seed: int):
        self.seed = seed & self.MASK32

def _hiword(self, x):
        return (x >> 16) & 0xFFFF

def next(self) -> int:
        v4 = (1103515245 * self.seed + 12345) & self.MASK32
        v5 = (1103515245 * v4 + 12345) & self.MASK32
        v6 = (1103515245 * v5 + 12345) & self.MASK32
        self.seed = v6
        result = (self._hiword(v6) & 0x3FF) | \
                 ((((v4 >> 6) & 0x1FFC00) | (self._hiword(v5) & 0x3FF)) << 10)
        return result & self.MASK32

def next_range(self, frm: int, to: int) -> int:
        if to >= frm and (to - frm) != 0:
            frm = frm + (self.next() % (to - frm))
        return frm

def next_rc(self, frm: int, to: int) -> int:
        if to >= frm:
            frm = frm + (self.next() % (1 - frm + to))
        return frm

def shuffle(self, arr: list):
        n = len(arr)
        for i in range(n - 1, 0, -1):
            j = self.next_rc(0, i)
            arr[i], arr[j] = arr[j], arr[i]
```

洗牌部分的写法：

```python
for i in range(n - 1, 0, -1):
    j = self.next_rc(0, i)
    arr[i], arr[j] = arr[j], arr[i]
```

跟教科书写法（`for i from n−1 downto 1: j ← random(0, i); swap a[i], a[j]`）完全一致，是
标准的 **Fisher-Yates（Durstenfeld变体）**，原地swap实现，没有做任何变种或魔改。这一点
在后面第3节会成为关键的可利用性质。

真正有自定义成分的是随机数生成部分 `next()`，下一节展开分析。

---

## 2. 算法结构拆解

### 2.1 内部是三次经典LCG迭代

把 `next()` 里的核心运算单独摘出来看：

```
v4 = (1103515245 * seed + 12345) mod 2^32
v5 = (1103515245 * v4   + 12345) mod 2^32
v6 = (1103515245 * v5   + 12345) mod 2^32
```

这是标准的线性同余生成器（Linear Congruential Generator），乘数 `1103515245`、增量
`12345`——眼熟的话，这正是glibc/ANSI C `rand()` 系实现里最常见的一组LCG常量。区别在于
标准库通常一次调用只推进一步状态，这里在一次 `next()` 调用里**连续推进了三步**。

### 2.2 输出如何由三个中间状态拼接而成

```python
result = (hiword(v6) & 0x3FF) | \
         ((((v4 >> 6) & 0x1FFC00) | (hiword(v5) & 0x3FF)) << 10)
```

拆解之后，输出各比特位的来源如下：

| 输出位区间 | 来源 |
|---|---|
| bit 0–9  | `v6` 的 bit 16–25 |
| bit 10–19 | `v5` 的 bit 16–25 |
| bit 20–30 | `v4` 的 bit 16–26 |
| bit 31 | 恒为 0 |

也就是说，`next()` 一次调用消耗了三步LCG状态，却只从每一步里抽取了**中高位**的一小段
（10~11位），拼成一个31位的输出。三个状态的低16位、以及`v6`更靠后的高位区间从未被
直接输出。

### 2.3 这种设计的直觉动机与潜在问题

"只取中高位"是LCG使用中的一个经典技巧——因为LCG的低位比特存在明显偏短的周期（比如
最低位的周期只有2，次低位周期4，以此类推），直接输出低位会让随机数呈现出肉眼可见的
规律。工程上"扔掉低位、只用高位"是缓解这个问题的常见手段。

但这里做得更进一步：不仅扔掉了低位，连**最高的若干位**似乎也没有被完全利用——`v4`只
用到bit16-26（11位），`v6`只用到bit16-25。这是否意味着，一部分seed的信息从一开始
就没有参与到最终的可观测输出中？第4节会给出确切的答案。

---

## 3. 完整观测下的反推

场景设定：能拿到某一局洗牌**前**的固定基准顺序（`orig`），以及**打乱后**观测到的完整
顺序（`shuffled`），求当时使用的seed。

### 3.1 利用 Fisher-Yates 双射性质，无需seed反推每一步随机数

Fisher-Yates（Durstenfeld）洗牌对**元素互不相同**的数组是一个双射：位置 `i`（`i≥1`）
一旦在第 `i` 轮被换入，后续轮次（`i-1, ..., 1`）永远不会再触碰它。也就是说，`shuffled[i]`
就是"第 `i` 轮换进来的值"。

利用这个性质，倒着从 `i=n-1` 扫到 `1`，在当前工作数组的 `[0..i]` 范围内定位
`shuffled[i]`，那个位置就是 `next_rc(0, i)` 在第 `i` 轮选中的 `j_i`：

```python
def recover_js(orig, shuffled):
    n = len(orig)
    cur = orig.copy()
    js = []
    for i in range(n - 1, 0, -1):
        j = cur.index(shuffled[i])
        js.append((i, j))
        cur[i], cur[j] = cur[j], cur[i]
    assert cur == shuffled
    return js
```

这一步是**确定性的、精确的**，不依赖seed，也不是暴力搜索——纯粹是对Fisher-Yates数学
结构的逆用。

需要强调一个前提：**数组内元素必须互不相同**。如果存在重复元素，`cur.index()` 只会
定位到第一个匹配位置，可能推出错误的 `j_i`。更危险的是，这种错误往往是**静默的**——
用错误的 `(i,j)` 序列重新模拟一遍，最终数组依然可能拼出正确的 `shuffled`（因为只要
交换序列自洽，最终排列就能对上），`assert cur == shuffled` 不会报错，但推出的约束链条
已经不是真实发生过的那一条了，后续拿它去搜索seed，会搜不到或者搜到错误结果。

### 3.2 用约束逐轮剪枝暴力搜索seed

`next_rc(0, i)` 每一步只泄露 `next() % (i+1)`，对于 `n=15` 的场景，14轮加起来理论
信息量：

```
log2(15!) ≈ 40.3 bit
```

超过种子的32位熵，理论上有唯一解（第4节会看到这个理论熵和有效熵之间存在系统性差异）。

搜索时按约束顺序做**逐轮剪枝**：第一轮把候选砍到 1/15，第二轮再砍到 1/14……候选集呈
几何级数收缩，总耗时几乎完全取决于第一轮扫一遍整个种子空间的成本，后续几轮的开销
可以忽略不计。

### 3.3 Python实现与实测

```python
import numpy as np

MASK32 = np.uint64(0xFFFFFFFF)
MUL = np.uint64(1103515245)
ADD = np.uint64(12345)

def next_vec(seed):
    v4 = (MUL * seed + ADD) & MASK32
    v5 = (MUL * v4 + ADD) & MASK32
    v6 = (MUL * v5 + ADD) & MASK32
    result = ((v6 >> np.uint64(16)) & np.uint64(0x3FF)) | \
             ((((v4 >> np.uint64(6)) & np.uint64(0x1FFC00)) |
               ((v5 >> np.uint64(16)) & np.uint64(0x3FF))) << np.uint64(10))
    return v6, result & MASK32

def crack_seed_full(orig, shuffled, chunk=1 << 22, search_space=1 << 32):
    js = recover_js(orig, shuffled)
    constraints = [(i + 1, j) for i, j in js]
    found = []
    for start in range(0, search_space, chunk):
        end = min(start + chunk, search_space)
        cur = alive = np.arange(start, end, dtype=np.uint64)
        for modulus, value in constraints:
            cur, r = next_vec(cur)
            mask = (r % np.uint64(modulus)) == np.uint64(value)
            cur, alive = cur[mask], alive[mask]
            if alive.size == 0:
                break
        if alive.size > 0:
            found.extend(alive.tolist())
    return found
```

对一组15张卡的实测样例（`orig`固定基准顺序，seed取一个测试值生成`shuffled`），用单个
chunk的实测耗时外推，全空间 `2^32` 扫描单线程预计约17分钟。后面用第6节的JS实现对
`2^32` 做了一次真实的完整扫描，实测 **62.5秒**，扫出的候选不是1个而是**32个**——这32个
seed彼此的高5位各不相同，正是第4节要讨论的"等价类"现象的一次提前印证。等到第4节引入
"有效搜索空间只有 `2^27`"这个发现、把搜索范围限定到低27位之后，同样的搜索**降到了
5.2秒（numpy）/ 1.3秒（JS）**，且只返回等价类中唯一的最小代表值。

---

## 4. 意外发现：算法本身的seed碰撞

### 4.1 实测中发现的"孪生seed"现象

对同一段观测数据反复验证时，出现了两个不同的seed（记为 `s1` 和 `s2`）都能精确复现同一次
洗牌结果的情况。进一步测试发现：不仅这一次洗牌的结果相同，**继续用同一个RNG实例调用
更多轮 `next()`，两者的输出流也始终保持逐位一致**（验证了20轮以上）。

对比两个seed的位模式：

```
s1 = 0b101110011010011010011000011011
s2 = 0b000110011010011010011000011011
diff = s1 - s2 = 0x28000000   (仅在 bit27、bit29 上不同)
```

两者的低16位完全相同，差异集中在高位。

### 4.2 代数证明：seed最高5位对输出无影响

用随机采样先做初步验证：对2000个随机seed，测试 `seed` 和 `seed + 0x28000000` 是否
在多轮调用后输出流保持一致，结果 **2000/2000 全部一致**。进一步定位发现，单独翻转
bit27~bit31 这5个比特里的**任意一个**，都不影响输出：

```python
single_bit_invariants = []
for b in range(32):
    if is_invariant(1 << b, trials=50, steps=6):
        single_bit_invariants.append(b)
# 结果: [27, 28, 29, 30, 31]
```

这个结论其实可以严格代数证明，不必依赖采样。设 `seed = s0 + delta·2^27`，其中 `s0` 是
低27位，`delta ∈ [0, 31]` 是高5位。因为乘数 `a = 1103515245` 是奇数：

```
v4 = (a·seed + c) mod 2^32
   = (a·s0 + c) + a·delta·2^27   (mod 2^32)
```

`a·delta·2^27 mod 2^32` 这一项必然**只有 bit27~31 可能非零**——因为 `2^27` 乘任何
整数，模 `2^32` 之后低27位天然是0。而加法的进位只会从低位往高位传，不会反向影响低位。
所以不管 `delta` 取什么值，`v4` 的低27位都原封不动，只有它自己的高5位会变化。`v5`、`v6`
分别是对 `v4`、`v5` 再做一次同样的LCG，同样的论证递归成立——`v5`、`v6` 的低27位也只由
输入的低27位决定，跟高5位无关。而 `next()` 的输出只用到了 `v4/v5/v6` 的 bit16~26，
全部落在低27位以内。这是一个严格的代数证明，不是概率性质。

### 4.3 推论：有效状态空间只有 2^27

- 这个PRNG的**有效种子空间是 `2^27 ≈ 1.34亿`**，而不是名义上的 `2^32`，缩小了32倍
- 任意一次观测对应 **32个等价seed**（高5位任意取值都行），彼此**永远无法通过任何后续
  观测区分**——不是"观测不够多"的问题，是这32个seed的输出流永远逐位相同
- 反推只能拿到这个等价类里的**最小代表值**（高5位置0），但功能上和真实seed完全等价：
  用它重新初始化RNG，未来任何一次调用的结果都和真实seed产生的结果一模一样

这也解释了3.2节里提到的理论熵（40.3 bit）与实际有效熵（27 bit）之间的差异：`next_rc`
虽然名义上每轮泄露 `log2(i+1)` bit的信息，但这些信息都是关于同一个27位有效状态的，
一旦观测量超过27 bit的阈值（对15张牌的完整洗牌而言，14轮累积信息量远超这个阈值），
解就会收敛到唯一，多余的信息只是提供了冗余校验，不会进一步区分seed。

### 4.4 延伸讨论：这类设计缺陷是否常见

"只用LCG的高位、丢弃低位"是缓解低位弱随机性的正确做法，但这里的实现走向了另一个极端——
连高位区间的选取也没有覆盖到完整的32位状态。三次LCG迭代的状态，最终只有中间一段
连续的11~16位比特参与了输出，两端（最低16位、最高5~6位）都被架空。低位被架空是刻意为之
（避免弱随机性），但高位被同样架空更可能是实现时的疏忽——比如位运算的移位/掩码常量在
适配到32位输出格式时出现了偏差，导致这部分本该参与的状态被无意间丢弃。

这提示一个具体的检查点：自定义PRNG如果涉及"手工拼位"的输出提取逻辑，需要对每一位
seed状态做一次完整的"是否参与最终输出"的追踪，而不能仅凭"用了高位所以是安全的"这种
直觉判断。

---

## 5. 部分观测场景

场景设定：只能看到打乱后结果的前 `k` 张牌（比如玩家实际打出的牌，能实时观测，但没有
拿到完整15张的顺序）。

### 5.1 为什么完整观测的技巧在这里失效

`shuffle()` 从 `i=n-1` 倒序处理到 `i=1`。位置 `0..k-1` 恰恰是**最后 `k` 轮**
（`i=k-1,...,1`）才被锁定的位置。要用3.1节的"查位置"技巧反推 `j_i`，前提是要知道
**执行到第i轮时数组的完整状态**——而这依赖前面若干轮完全看不到的"盲操作"，无法回避。

这意味着只能退回到直接暴力：对每个候选seed完整模拟整个洗牌过程，再比对前k位。而且
前 `n-k` 轮完全没有过滤效果（观测不到这部分位置的结果），必须完整跑完才能开始比对，
无法像完整观测场景那样逐轮剪枝。

### 5.2 信息论角度：观测量 vs 有效熵

| 观测数 k | 排列数 = 15×14×...×(16-k) | 有效seed空间 2^27 / 排列数 | 期望候选数 |
|---|---|---|---|
| 5 | 360,360 | ≈ 372 | 不唯一 |
| 6 | 3,603,600 | ≈ 37 | 大概率不唯一 |
| 7 | 32,432,400 | ≈ 4 | 少量候选 |
| 8 | 259,459,200 | ≈ 0.5 | 大概率唯一（但也可能无解） |

判定公式：

```
期望候选数 ≈ 2^27 / [15 × 14 × ... × (16-k)]
```

当这个值远大于1时，观测量不足以唯一确定seed；接近或小于1时，大概率能收敛到唯一解
（或者因为观测数据本身有误而搜出0解，见第7节）。

实测（`k=5`，全空间暴力模拟）：候选数342个，与理论期望372高度吻合，真实答案确实在
候选集中但无法单独确定。

### 5.3 两阶段策略

- **阶段①**：多进程/多线程暴力扫 `2^27`，用观测到的前k张过滤，拿到候选集
  （几十到几百个）
- **阶段②**：候选集已经很小，之后每多观测到一张新牌，直接对候选集做一次全量模拟比对，
  秒级完成，候选数指数收缩

实测链路：342个候选（前5张）→ 补第6张 → 32个 → 补第7张 → 唯一，且等于真实答案。

```python
def refine_candidates(orig, candidates, known_positions):
    """known_positions: {5: 某张牌id} 表示第6张(0-indexed位置5)的真实值"""
    orig_arr = np.array(orig, dtype=np.int64)
    arr = simulate_shuffle_batch(orig_arr, candidates)
    mask = np.ones(len(candidates), dtype=bool)
    for pos, val in known_positions.items():
        mask &= (arr[:, pos] == val)
    return [c for c, m in zip(candidates, mask) if m]
```

---

## 6. 从Python到浏览器：性能优化的几个点

出于让非技术用户也能在本地浏览器里直接使用的考虑，把整套方案移植到了纯前端
（HTML + JS + Web Worker），不依赖任何后端服务。最初考虑过用WASM（比如Emscripten
编译C实现）进一步提速，但实测纯JS配合`Math.imul`已经能拿到不错的性能（下面6.4的
对比表），且部署更简单（单文件HTML即可，不需要额外的.wasm资源和胶水代码），所以
最终没有引入WASM，留作后续如果需要处理更大搜索空间时的优化方向。

### 6.1 numpy向量化 vs 逐轮剪枝

Python端用 `numpy` 把候选seed当成数组批量处理：每一轮LCG迭代都是对整个候选数组做一次
向量化运算，匹配失败的候选通过布尔mask过滤掉，数组随之收缩（compaction）。完整观测
场景下，这套写法几秒内出结果；部分观测场景下因为无法提前剪枝，需要老老实实模拟完整
15轮，单线程耗时明显更长（`2^27`全空间约200秒量级）。

### 6.2 移植到JS的注意点

浏览器端没有 `numpy`，直接照搬会面临32位整数运算的问题——JS的 `Number` 是双精度浮点，
直接做乘法（`1103515245 * seed`）在seed较大时会超出安全整数范围导致精度丢失。

解决方式是用 `Math.imul(a, b)`：它按32位有符号整数语义做乘法，返回结果的低32位，
恰好对应C语言里 `uint32_t` 相乘时的截断行为。配合无符号右移 `>>>` 做位提取，就能
精确复现Python版本里 `& 0xFFFFFFFF` 的效果，且不需要引入更慢的 `BigInt`：

### 6.3 一个来自实践的优化技巧：观测窗口内的提前退出

部分观测场景下，虽然前 `n-k` 轮无法提前过滤，但可以在**每完成一轮就检查该轮是否
刚好落在可观测窗口内**，一旦落在窗口内且不匹配，立刻中止当前候选，不必跑完剩余轮次：

```javascript
for (var i = n - 1; i >= 1; i--) {
  // ...计算 v4,v5,v6,r...
  var j = r % (i + 1);
  var t = arr[i]; arr[i] = arr[j]; arr[j] = t;
  if (i < k && arr[i] !== observed[i]) { ok = false; break; }  // 关键
}
```

因为绝大多数候选会在进入可观测窗口的第一步就失配，这个提前退出显著减少了平均每个
候选的实际计算量。批量向量化的实现（如numpy）很难做到"单个候选内部提前退出"，这算是
逐标量循环在这个具体场景下反而更有优势的一个例子。

### 6.4 Web Worker并行化与实测对比

用 `navigator.hardwareConcurrency` 决定并行度，每个Worker通过 `postMessage` 领取一段
`[lo, hi)` 区间独立计算；主线程用递增的"运行令牌"机制丢弃过期的异步结果，支持中途取消。

单线程实测对比（同一台机器）：

| 场景 | Python(numpy向量化) | JS(V8) | 加速比 |
|---|---|---|---|
| 完整观测，`2^27`全扫 | 5.2s | 1.3s | ~4x |
| 部分观测(前5张)，`2^27`全扫 | ~204s | 21.3s | ~10x |

部分观测场景下的差距主要来自6.3节的提前退出优化。浏览器内用满多核Worker并行后，等待
时间可以进一步压缩到个位数秒级别，达到了"边打牌边实时收敛seed"的可用程度。

---

## 7. "为什么搜不到"的边界情况讨论

一个容易被忽略的问题：卡片不重复、数据格式合法，是否就一定能搜到seed？答案是否定的，
但原因不在算法本身，而在于**这个PRNG能产生的输出，只是所有理论排列里的一个真子集**。

### 7.1 判定标准

由第4节的证明，有效种子空间是 `2^27`。每个seed对应一条**确定**的输出序列，所以这个
算法**最多**只能产生 `2^27` 种不同的"前k张"结果。而"前k张"理论上一共存在
`15 × 14 × ... × (16-k)` 种可能排列。两者的比值：

```
可达比例 ≈ 2^27 / [15 × 14 × ... × (16-k)]
```

当这个比例明显小于1时，意味着相当一部分理论上"看起来合法"的排列，**在数学上永远
不可能由这个算法在任何seed下产生**。

### 7.2 实测验证

以 `k=8` 为例：

```
2^27 / (15×14×13×12×11×10×9×8) = 2^27 / 259,459,200 ≈ 0.517
```

也就是说即便这个PRNG的输出分布完全均匀，也只有大约51.7%的排列组合是它有可能产出的。
用一组随手构造（而非真实观测）的"前8张"数据去搜索，实测在跑满 `2^27` 全空间后，
候选数确认为 **0**——这不是搜索不彻底，是这组数据本身就落在了算法"永远无法生成"的
那部分排列空间里。

### 7.3 排查方向

- 卡不重复、`orig`/`observed`确实来自同一次真实洗牌、复现的算法细节完全准确
  ⇒ **理论保证能找到**（第4.2节的代数证明是严格的，不存在"运气不好搜不到"的情况）
- 搜出0候选 ⇒ 应当怀疑的是上述前提是否被违反：数据是否真实观测得到、记录顺序是否
  有误、`orig`基准顺序是否对应同一份实际使用的卡组——而不是怀疑搜索范围不够大

---

## 8. 空间换时间：预计算查找表

前面几节的暴力搜索，不管是完整观测还是部分观测，都是"每来一局数据、重新扫一遍种子
空间"。但仔细看会发现一个关键性质：这套搜索本质上跟"这一局具体是哪些牌"完全无关，
只跟"有多少张牌（`n`）"以及算法本身有关。这意味着可以把搜索成本从"每局一次"整体
挪到"全局一次"，用磁盘空间换掉后续每一局的计算时间。

### 8.1 核心性质：算法行为与牌面内容解耦

`shuffle()` 内部生成 `j = next_rc(0, i)` 的过程，从头到尾只用到了 `i`（当前处理到
第几个位置）这一个参数，从来没有读取数组里的实际内容。换句话说，**同一个seed对
"位置索引数组`[0..n-1]`"做shuffle，得到的index排列，和对任意具体卡组内容做shuffle
后反推出的index排列，完全一致**：

```javascript
// 直接对索引 [0..14] 跑shuffle
const idxPerm = shuffleIndices(seed, 15);

// 对具体卡组跑shuffle, 再用 orig.indexOf 反推index排列
const shuffled = shuffleCards(seed, orig);
const recoveredIdx = shuffled.map(v => orig.indexOf(v));

// 两者逐位相同
```

推论是：只要卡组张数 `n` 不变、算法本身没改，"seed → 位置置换关系"这张映射表
**只需要生成一次，可以无限期复用**，跟卡组具体内容、赛季更迭都无关；唯一会让表
失效的情况是 `n` 变了，或者游戏更新了这套RNG算法本身。

### 8.2 设计：把暴力搜索的成本从"每局一次"摊到"全局一次"

具体做法：离线遍历有效种子空间内的每一个候选seed，模拟出洗牌后前 `K` 个位置对应的
原始索引，把 `(索引前缀编码, seed)` 这一对记录下来，按索引前缀编码排序后整体存盘。
之后每一局只需要把观测到的前 `K` 张牌换算成同样的索引编码，对这张表做一次**二分
查找**，就能直接拿到候选种子，不需要再重新跑一遍暴力搜索。

小规模（`2^22`）原型验证的单项耗时：

| 步骤 | 耗时 |
|---|---|
| 建表（遍历全部候选seed，模拟shuffle，取前K个索引） | 693ms |
| 排序（为二分查找做准备） | 399ms |
| 单次查表（二分查找） | 亚毫秒级 |

外推到真实规模 `2^27`（放大32倍）：

| 项目 | 估算值 |
|---|---|
| 建表耗时 | ~22秒 |
| 排序耗时 | ~16秒（`O(n log n)`，略超线性放大） |
| 一次性总成本 | ~40秒左右，且全局只需要做一次 |
| 表文件大小 | `2^27 × 8字节 ≈ 1GB` |
| 之后每次查表 | 亚毫秒级 |

### 8.3 编码设计与一个值得记录的实现教训

每条记录被打包成一个64位整数：高位存"前K个索引"的编码（每个索引占4bit），低位存
seed（占 `bits` 位，通常27位）。这里有一个硬约束：`K × 4 + bits ≤ 64`，超出就会
溢出。

第一版实现在这里踩了两层坑，值得记录下来：

**第一层**：最初把打包偏移量硬编码成32位（`code << 32 | seed`），导致不管 `K` 取
多大，表文件大小都只跟搜索空间位数挂钩，跟 `K` 完全无关——`K=8` 和 `K=15` 生成的
文件字节数完全一样。修复方式是把偏移量改成实际的 `bits`，并在建表时显式校验
`K*4+bits<=64`，超限直接报错而不是静默截断。

**第二层**：修完第一层之后，`K=9`（`bits=27` 时理论允许的上限）依然会出问题——
因为 `code` 变量本身的累加过程（`code = (code << 4) | idx`）用的是JS原生 `Number`
的32位位运算，跟打包阶段的偏移量选择是两件完全独立的事。构造两个只有第一个索引
不同、其余8个索引相同的前缀，`K=9` 时用这种写法编码出来的结果**完全相同**——真实
碰撞，不是巧合。最终修复是把 `code` 的累加过程整体换成 `BigInt`（`0n`、`<<4n`、
`BigInt(idx)`），彻底摆脱32位边界；建表和查表两侧要同步修改，否则两边的编码方式
不一致，查出来的结果照样是错的。

这个案例的教训比较通用：**"看起来只是打包偏移量的问题"和"数值本身的位宽限制"是两
个独立的坑，修好一个不代表另一个也修好了**，需要针对边界值（比如这里的 `K=9`，
刚好是"理论上被允许、但打包之前的中间计算已经出问题"的临界点）单独构造对拍测试，
不能只验证 `K` 较小时的情况。

### 8.4 什么时候该用表，什么时候直接暴力更划算

- 观测不完整、且要针对同一套卡组反复反推（`K` 较小，比如只能看到局内已经打出的几张
  牌）：用表，查询频繁，一次性建表成本能被大量摊销
- 能观测到全部 `n` 张：不需要建表，直接对这一局做逐轮剪枝暴力搜索即可（前述实测
  1.3秒量级），信息量最大的场景本身求解就很快，没有"重复成本"可摊；而且 `K` 越大，
  8.3节的位宽限制越容易被撞到，不如直接暴力
- 实际使用时两条路径可以并存：能看到几张就是几张，凑够建表时设定的 `K` 就查表拿
  候选（不唯一时用后续观测继续收敛），碰巧能看全的场景直接切到暴力搜索，二者按
  实际能拿到的信息量自由切换

---

## 9. 总结

这次分析从一段反编译得到的自定义洗牌实现出发，得到了几个层次的结论：

1. 只要洗牌算法是标准的swap-based Fisher-Yates，在拿到完整的"打乱前/打乱后"数组时，
   可以**无需seed、精确无损**地反推出每一步随机数选择，这是纯粹的组合数学性质，
   不依赖RNG的具体实现
2. 结合这些约束对种子空间做逐轮剪枝暴力搜索，可以在秒级时间内确定seed——前提是
   RNG本身的有效状态空间被准确评估（本例中的 `2^27` 而非名义上的 `2^32`）
3. 自定义PRNG如果采用"手工拼接多次LCG迭代的中间状态"这类设计，需要仔细验证seed的
   每一个比特是否真正参与到了最终输出——本例中因为高5位被无意间丢弃，导致种子空间
   实际缩水了32倍，这是一个可以通过静态位追踪提前发现的问题
4. 部分观测场景下，能否唯一确定seed取决于观测量与算法有效熵的相对大小，可以用
   一个简单的组合数公式提前判定，不需要真的跑一遍暴力搜索才知道能不能收敛
5. 工程实现上，Web端用 `Math.imul` 复现32位整数运算、结合观测窗口内的提前退出剪枝，
   可以让部分观测场景下的暴力搜索速度获得一个数量级左右的提升
6. 由于算法行为跟牌面内容解耦，可以把种子空间预先建成一张"索引前缀 → seed"的查找表，
   一次性成本在秒级到分钟级，之后每一局的反推退化成一次二分查找（亚毫秒级）——这是
   否值得做，取决于同一套牌组规模下的查询频率是否足够高

对游戏客户端RNG设计的启示：如果洗牌/抽卡结果需要对客户端保密，服务器下发一个确定性
seed、交给客户端本地复现的模式，本质上只是把"保密"这件事的强度，降低到了"这个PRNG
的seed空间有多大、结构上是否存在可被逆向利用的性质"这个层面——而不是真正意义上的
服务器端保密。

---

最后感谢 Claude（Anthropic）在本文分析与工程实现过程中的协助——从代数性质的推导验证、
Python/JS两版代码的实现与交叉测试，到预计算表方案里两轮编码位宽bug的排查，中间不少
环节是靠反复验证、快速试错跑出来的，AI工具把这部分体力活省下了不少时间。文中提到的
DeepSeek同样在代码审查环节抓出过一处实质性bug，一并感谢。

## 参考/延伸阅读方向

- Fisher-Yates / Durstenfeld shuffle 的双射性质与均匀性证明
- 经典LCG（`glibc`/ANSI C `rand()`系）低位周期短的问题，及"仅取高位"这一缓解手段的
  历史背景
- 模偏差（modulo bias）：`rand() % n` 在 `n` 不整除RNG值域时引入的轻微非均匀性

冰与火的战歌：Windows内核攻防实战高级班！从零到实战，融合AI与Windows内核攻防全技术栈，打造具备自动化能力的内核开发高手。

收藏・1

点赞・2

打赏