做密码安全这块，迟早会遇到一个问题：我手里已经有了一张彩虹表，磁盘占用看起来也很可观，可真拿去查一批哈希的时候，实际成功率却总比想象中低一大截。后来我发现，问题不是表不够大，而是大多数人（包括当时的我）根本没把彩虹表的“成功率计算”这件事弄明白。这篇内容我就把这件事彻底讲透：成功率是怎么来的、公式怎么推、参数怎么搭，以及一张看似“完美”的表为什么会翻车。

1. 先把存储机制说清楚：成功率为什么不等于“表大小/明文空间”

很多人对彩虹表有个直觉：表越大、存的条目越多，能覆盖的明文就越多，那成功率自然就等于“覆盖的明文数 / 明文空间大小”。这个直觉害死人。彩虹表几乎从来不会把中间状态全部存下来，它存的是“链首+链尾”，中间所有位置都是通过计算现算的。所以一张表的“有效覆盖”和磁盘条数之间，隔着一整条概率链路。

1.1 链条的构造：哈希函数和归约函数交替折叠

彩虹表的核心单位不是一条记录，而是一条“链”。构造方式是这样的：随便取一个明文作为起点，做一次哈希，再用一个归约函数把哈希值映射回明文空间，再哈希、再归约，如此循环固定次数。定义清楚一点：哈希函数写成 H，归约函数写成 R。链条就是

p0 → H → c1 → R1 → p1 → H → c2 → R2 → p2 → … → p_{t-1} → H → c_t

其中 p 表示明文，c 表示哈希值，t 是链长。构造完这条链之后，我们只保存 (p0, c_t)，也就是起点明文和终点哈希。中间那几百上千个状态，查询的时候现算。

这里有一个看起来不起眼、但影响成功率的关键设计：每一列使用的归约函数 R 是不同的，所以严谨写法是 R1、R2、R3……而不是所有列共用一个 R。原因后面会细讲，这直接关系到链条合并的概率，而链条合并是成功率缩水的第一大元凶。

1.2 查询过程：不是扫描全表，而是从目标哈希反向折叠

如果我们要查的目标哈希值是 c，查询过程是从 c 出发，尝试“折 0 次、折 1 次、折 2 次……直到折 t-1 次”。每次折叠都是先做归约、再做哈希，这样得到的每种结果如果正好等于某条链的链尾，就说明这条链的某一段覆盖了目标哈希。这时候再拿到链首，从头把链条重新走一遍，走到某个位置时如果算出的哈希等于目标值，那个位置前面的明文就是结果。

所以一张彩虹表能覆盖的密度，取决于“所有链条的所有折叠点”在明文空间里的分布密度。注意是“覆盖密度”，不是“条目数量”。链条越长，每个起点产生的可能命中位置越多；链条越多，起点数量越多。而这两者之间存在一个肉眼看不出的此消彼长关系。

1.3 覆盖率不可能到 100% 的物理限制

很多新手默认“我把表做到明文空间的好几倍大小，成功率应该接近 100%”。实际上彩虹表的覆盖率永远达不到 100%，原因有三层。

第一，链条会合并。两条链从不同起点出发，如果某个折叠点撞到了同一个哈希值，那接下来的路径就完全一样了，后边等于白走。链条越长，合并概率越高。第二，链尾碰撞。就算中间没合并，两张表的链尾也可能相同，而存储时为了去重通常会只保留一条，这会悄悄损失掉一部分有效链。第三，端点分布不均匀。归约函数再均匀，在有限空间里也必然存在热点和冷区，冷区里的明文就是那些“理论上在覆盖范围内、实际上永远等不到”的倒霉蛋。

所以成功率的本质，是在“链条长度、链条数量、合并概率、端点碰撞、分布均匀性”这几股力共同作用下的一个统计结果。下面这个数学模型，就是把这些因素尽量量化。

2. 成功率公式的来龙去脉：从漏报概率到可抄走的代码

关于彩虹表成功率的理论，最早来自经典论文里的概率模型。我不重复论文推导过程，直接讲它的核心思路和最终结果，因为实际动手时你需要的是“能用”的公式。

2.1 从“漏报概率”说起：每一列都有盲区

先给一个非常重要的定义：漏报概率，意思是某个明文的哈希值在某一列折叠过程中没有被覆盖到的概率。我们假设明文空间大小是 N，一张表有 m 条链，链长固定为 t。任何一张表在构造过程中，第 i 列上会实际出现一些不同的明文点，用 m_i 表示第 i 列上不同点的期望数量。

m_i 不是一个固定值。第一列近似等于 m，因为 m 个随机起点之间的碰撞还比较少。但从第二列开始，每列的新增点会和已有覆盖点重合，造成浪费。学术上常用一个递推式来近似：

m_{1} = m

m_{i+1} = N × (1 - e^{-m_i / N})

这个式子看着抽象，其实逻辑很朴素：第 i+1 列能贡献的新点数量，取决于“第 i 列已经覆盖到哪里”。如果第 i 列覆盖了 30% 的空间，那第 i+1 列折叠出来的点大约有 30% 的概率落在已覆盖区域，实际新增只有 70%。指数形式来自泊松近似，因为路径上的落点在理想模型下服从随机均匀分布。

有了 m_i，第 i 列的漏报概率就是 1 - m_i / N。这是整张表某一列“没接住”的概率。如果目标哈希在某张表的任何一个折叠列都没被命中，那这张表对这个目标就失效了。

2.2 一张表的成功率：所有列都漏掉才算失败

一张表里任何一列命中一次，就能还原出目标明文。所以“整张表漏掉”等价于“每一列都漏掉”。把所有列的漏报概率乘起来，再被 1 减，就是这张表的理论成功率：

S ≈ 1 - ∏_{i=1}^{t} (1 - m_i / N)

这个公式说明三件事。

第一，链长 t 会增加公式里的乘数项数，每加一列就多一层覆盖机会，所以链长对成功率是正向贡献。第二，每列覆盖点 m_i 受前一轮覆盖影响，链条越长，后面的列增长会越来越慢，这是反向压制。第三，表总数 m 只影响起点数量，不会线性放大成功率，它被塞在 m_i 的递推里，所以“把 m 加倍，成功率远不会加倍”是正常的。

用 Python 实现这个递推，大约就是这么几行：

import math def table_success_prob(N, m, t): ms = [] mi = m for _ in range(t): ms.append(mi) mi = N * (1 - math.exp(-mi / N)) miss = 1.0 for mi in ms: miss *= (1 - mi / N) return 1 - miss

这里有个非常重要的使用边界：这个公式在“链条不太长、表占空间比例不太大”的时候比较接近真实值。一旦 m×t 已经接近甚至超过 N，理论值就会被严重高估，因为模型里没有充分惩罚链条合并带来的全局损失。后面实测对比你会看到这个偏差到底有多大。

2.3 多张表的组合成功率：表之间的“独立”是近似

单张表到不了 100%，人们自然的反应是多做几张表。如果一共有 l 张表，每张表的理论成功率分别是 S1、S2……Sl，在“表与表之间互相独立”的假设下，整体失败率等于每张表失败率的乘积：

S_total ≈ 1 - (1 - S1) × (1 - S2) × … × (1 - Sl)

代码就是几行乘乘除除的事：

def multi_table_success_prob(tables, N): total_miss = 1.0 for m, t in tables: s = table_success_prob(N, m, t) total_miss *= (1 - s) return 1 - total_miss

但这里我必须泼一盆冷水：多张表之间远非独立。只要它们覆盖的是同一个明文空间、用的是同一类归约函数族，就必然存在大量重叠区域。用“独立假设”算出来的组合成功率，通常是乐观值。尤其是当每张表本身的覆盖率已经很高时，新增一张表带来的边际收益会迅速缩水。想准确评估多表成功率，最可靠的办法还是用小规模模拟器实测，然后把偏差系数外推到大空间。

3. 一百万明文空间的实测对比：理论和现实之间有一条深沟

说一万遍理论不如跑一次实验。我在本地搭了一个小规模验证环境，明文空间故意压得很小：6 位数字，也就是 N = 1,000,000。这样在一台普通笔记本上可以真正把表建出来、把查询跑完，适合用来观察理论公式和实测结果之间的差距。

3.1 构造一个可控实验环境

哈希函数直接用常见哈希算法的十六进制摘要，归约函数则从摘要中取不同位置的 8 位十六进制片段、再对 1000000 取模。这样在不同折叠列上使用不同的摘要片段，模拟“不同列使用不同归约函数”的效果。

代码可以简化成下面这样，核心是链构造和链查询：

import hashlib def H(p): return hashlib.md5(str(p).encode()).hexdigest() def R(col, h): # 从摘要的固定偏移位取 8 个十六进制字符，转成整数后取模 off = (col * 8) % (len(h) - 8) return int(h[off:off+8], 16) % 1000000 def fold(col, h): return R(col, H(h))

这里要特别注意：直接把十六进制片段取模是一种“教学用法”，真实工程里归约函数要设计得更复杂，否则容易出现偏置和循环。后面第 5 部分会专门说这个问题。实验环境只是为了对照理论公式，不需要工程级的完美。

有了折叠函数，再写建表和查询。建表时把链尾哈希作为键、链首明文作为值放进字典，重复链尾用第一条覆盖。

3.2 理论值和实际查询成功率的对照

我随机抽了 3000 个明文，用同样的哈希函数算出它们的哈希值作为测试集。测试集里的明文是从整个明文空间随机抽样，而不是只从链覆盖区域抽样，这一点特别重要。然后分别统计理论成功率和实测成功率，得到下面一组数据：

第一眼看过去，理论公式在低覆盖场景下勉强可用，而在高覆盖场景下高估得离谱。这验证了我在 2.2 里说的边界问题：m×t 越大，链条合并越严重，理论公式越失效。

另一个明显趋势是：同样是总折叠次数接近的参数组合，链条短而表多的组合实测效果远好于链条长而表少的组合。m=20000, t=300 的总折叠次数是 600 万，m=50000, t=100 是 500 万，前者折叠次数还更多，实测成功率却更低。原因是链长增加以后，链内合并概率呈非线性增长，很多折叠都浪费在重复路径上了。

3.3 偏差到底出在哪几个环节

理论公式假设“每个折叠点在明文空间中随机落位、互不影响”，这个假设在三个方面破了功。

第一，链尾去重。建表时如果两条链的终点哈希相同，只保留一条。链长越长，终点汇聚越容易发生，去重丢掉的链就越多。实验中 m=10000, t=500 这组，实际存进表里的有效链数远低于 10000，这才是成功率崩盘的直接原因。第二，折叠落点不是标准均匀分布。取模操作总会有轻微偏置，有些区间被反复覆盖，有些区间始终是黑洞。第三，重放链条时还可能遇到循环。如果某个折叠点进去了一个环，链条会在局部打转，导致后续列全是重复覆盖。

所以结论是：理论公式适合用来确定参数搜索的方向，不适合用来作为最终验收指标。真正确认一张表能不能用，必须用独立测试集实测。

4. 反推参数：链长、表数、存储空间怎么权衡

既然理论公式和实测有偏差，那参数到底怎么定？我通常的做法是：先用简化公式做“方向性搜索”，再用小空间模拟器做“精度校正”，最后把校正系数放大到目标空间。这一节讲清楚这三个环节里的关键权衡。

4.1 总存储固定时，链长不是越长越好

假设明文空间是 N，你计划总共建造 M 条链，每条链长 t，那么存储量大约正比于 M（因为每条链只存链首和链尾）。单张表的折叠总次数是 M×t，但有效覆盖率不是 M×t/N，而是要打一个折扣。

我把这个关系拆成两条力单独看。增加链长 t 会带来更多列，理论上每列都是一次覆盖机会，这是正向收益。但同时，链长增加后每一条链内部发生合并的概率更高，链的“末端”更容易和别的链汇合，实际存活链快速下降。实验里 m=10000, t=500 被 m=50000, t=100 全面碾压，已经说明问题：五百步长链还没走到一半就大量身死，不如一百步短链多造几条。

所以固定总折叠次数的情况下，一般应该优先增加链条数量，而不是一味加长链条。到底选多长，取决于明文空间的规模和归约函数的均匀程度。小空间实验里，t 取 50 到 150 之间通常比较稳；空间变大后，t 可以适当加长，但要控制在“平均链长带来的链内合并率可接受”的范围内。

4.2 从目标成功率反推需要的表和链数

如果你手上有一个硬指标，比如要求成功率不低于 90%，可以倒着做参数搜索。步骤大概是这样的：

• 第一步：用小空间模拟器，固定 N=10^6，生成几组 M 和 t 的实测成功率数据；
• 第二步：拟合出“在当前归约函数设计下，指定折叠总量能拿到多少实测覆盖率”的经验曲线；
• 第三步：把目标 N 成比例放大，同时保持“每单位明文空间对应的折叠量”不变，得到目标空间需要的折叠总次数；
• 第四步：根据存储预算交叉约束，确定具体 M 和 t。

这里的放大系数不能拍脑袋，应该来自同一套归约函数、同一类明文空间形态的小规模实验。我吃过的亏是直接拿理论公式放大参数，结果建了张巨大的表，最后实测成功率比预期低了二三十个百分点，白花时间。

4.3 不同场景下的推荐参数范围

以下是我在自建实验环境里测试过后觉得比较合理的经验值，给新手做个起点参考。注意它们不是公式算出来的标准答案，而是“从某个方向上搜索出来的可行区间”。

这个表的含义是：当空间变大时，链长得更粗才能覆盖足够多的“列机会”，但表数也要跟上，而不是单表无限做长。多表之间用不同的归约函数族，才能把“独立近似”的误差尽量压小。

5. 实验里踩过的坑：一张看起来能用的表为什么经常爆冷

最后这部分纯粹是实操中攒出来的经验。很多问题不是理论公式能告诉你的，必须在建表、查表、评估这一整套流程里踩过才知道。

5.1 归约函数设计不当会制造热点和循环

我最初偷懒，归约函数直接取“哈希字符串的前 8 位再取模”，结果表建完以后查了一批哈希，成功率低得离谱。排查下来发现，某些摘要前缀的分布极不均匀，大量折叠点挤在一小段区间里，别的区间根本没人覆盖。后来改成从哈希的不同偏移位取片段、并混合一个常数偏移，覆盖率立刻正常了。归约函数的核心要求是“每一列都尽量像一次新的均匀随机映射”，任何规律性都会变成效率漏洞。

5.2 多张表的“虚假独立性”

为了凑成功率，我同时建过多张表，用的归约函数只是把常数偏移换了几个数字。看着是 l 张不同的表，实际折叠路径高度相似，表与表之间的覆盖率重叠非常严重，组合成功率远低于“1-(1-S)^l”的预期。后来把归约函数族彻底打乱，比如不同表采用不同取模策略、不同摘要片段起始位置，甚至不同哈希算法组合，才算真正发挥了多表优势。

5.3 评估成功率时最容易犯的三个统计错误

一个是用“链覆盖区域内的样本”做测试。建表时已经有了一张终点表，如果测试哈希都从这些链会覆盖的位置附近取，成功率当然虚高。正确做法是从整个明文空间随机取明文，再算哈希，完全不看链表结构。第二个是测试集太小，几百条样本的方差巨大，一次查询多失败几个点，成功率能差出十个百分点。我一般至少跑两千到三千个样本。第三个是只看“总成功率”不看失败样本的分布。如果失败样本集中在某几个区间，说明归约函数存在系统偏置，这比整体低几个百分点更值得警惕。

说回我自己现在的习惯：每次设计彩虹表参数之前，先在一个 10^6 空间的小环境里跑整套模拟，拿到当前归约函数族的“理论→实测偏差系数”，再用这个系数去推算大空间参数。这比迷信任何一个公式都靠谱得多。毕竟成功率这个东西，终究是统计出来的，不是算出来的。