字符串 Hash 的攻击
强烈建议尝试 Luogu U461211 字符串 Hash（数据加强）
前言
某天看到同学打 字符串hash，发现还在用 腐朽 的 单模数hash。
为了帮助他改进码风，我决定 卡炸hash。
一、大模数哈希
1.前言
我们知道，要想卡掉 hash，本质上就是让两个字符串有相同的 hash 值，我们称为哈希碰撞。
假设 hash 中每个值生成概率相同，则碰撞概率取决于两个因素： - 取值空间大小 - hash 的计算次数
这个问题在数学中有一个经典的问题，叫 生日问题。
简单来说，就是在一个有 d 人的班中，有人生日相同的概率为多少。
实际上，这个问题的答案并没有想象中的小，下面是部分概率： | 人数 | 概率 | | :—: | :——: | | 23 | 50% | | 50 | 97% | | 70 | 99.9% |
2.计算冲突概率
我们设 hash 的取值空间为 d，计算次数为 n。 则 hash 不冲突的概率为：
$$ \overline{p}(n,d) = 1 \cdot \left (1 - \frac{1}{d} \right) \cdot \left ( 1- \frac{2}{d}\right) \cdots \left ( 1- \frac{n-1}{d}\right) $$
经过亿点点的数学计算，他可以变为：
$$ \frac{d!}{d^n\left(d-n\right)!} $$
则 hash 冲突概率为：
$$ p(n,d)=1-\frac{d!}{d^n\left(d-n\right)!} $$
但是，这个太丑了，计算也太复杂了，我们换种方法。
根据泰勒公式：
$$ \exp(x) = \sum_{k=0}^{\infty}\frac{x^k}{k!}=1+x+\frac{x^2}{2}+\frac{x^3}{6}+\frac{x^4}{24}+\cdots $$
当 x 为一个极小的值，那么 exp (x) ≈ 1 + x
将上面 hash 不冲突的原始公式带入：
$$ \overline{p}(n,d) = 1 \cdot \exp(-\frac{1}{d}) \cdot \exp(-\frac{2}{d}) \cdots \exp(-\frac{n-1}{d}) $$
化简得：
$$ \overline{p}(n,d) = \exp(-\frac{n(n-1)}{2d}) $$
则 hash 冲突的概率为：
$$ p(n,d) = 1-\exp(-\frac{n(n-1)}{2d}) $$
3.卡 Hash
言归正传，注意这个公式：
$$ p(n,d) = 1-\exp(-\frac{n(n-1)}{2d}) $$
我们只要使 d（取值空间）比模数大，并找一个 n（计算次数），使得 p(n, d) 尽量为 1，就完成了。
例：
对于字符集为大小写字母及其数字，我们设模数为 109 + 7：
log62109 + 7 ≈ 6
p(106, 662) ≈ 0.9
所以共有 106 个字符串，每个字符串长度为 6 就是个不错的数据。
二、自然溢出 Hash
我们知道，这种 Hash 是形如 hs = hs ⋅ base + s[i]，分情况讨论。 ### 1.base 为偶数 这种简单，构造两个长度相同且大于64，并只有首字母不同的字符串，形如：
aaa...a
baa...a
2.base 为奇数
定义 !si 为 si 的倒串,hashi 为 si 的 Hash 值,!hashi 为 !si 的 Hash 值。
例如： si = abbab
则：!si = baaba
设 s1 = a
之后不断构造 si = si − 1 + !si − 1 就有：
$$ hash_i = hash_{i-1}\cdot base^{2^{i-2}} + !hash_{i-1}\\ !hash_{i} = !hash_{i-1}\cdot base^{2^{i-2}}+hash_{i-1} $$
尝试相减：
$$ \begin{align*} &hash_i - !hash_i\\ =\ &hash_{i-1}\cdot base^{2^{i-2}} + !hash_{i-1}-(!hash_{i-1}\cdot base^{2^{i-2}}+hash_{i-1})\\ =\ &(hash_{i-1}-!hash_{i-1})\cdot (base^{2^{i-2}}-1) \end{align*} $$
发现出现了 2i，但是原式太复杂，尝试换元：
设：
fi = hashi − !hashi
gi = base2i − 2 − 1
带回原式：
$$ \begin{align*} f_i &= f_{i-1} \cdot g_i\\ &=f_1 \cdot g_1 \cdot g_2 \cdots g_{i-1}\\ \end{align*} $$
因为 base2i − 2 一定是奇数，所以 gi 一定是偶数。
所以：
2i − 1|fi
但这样太大了，i − 1 ≥ 64 才能卡掉，继续化简。
$$ g_i = base^{2^{i-2}-1} = (base_{2^{i-2}}-1)\cdot(base^{2^{i-2}}+1)\\ $$
$$ \begin{align*} \therefore & 2^i | g_i\\ &2^2\cdot2^2\cdot2^3\cdots2^{i-1} | f_i\\ &2^{i(i-1)/2} | f_i \end{align*} $$
即当 i = 12 时就可以使 264|hashi − !hashi 达到要求。
s12 和 !s12 就是我们要的两个字符串。
参考：