滚动哈希和卡哈希的数学原理

translate from The Mathematics Behind Rolling Hashes and Anti-hash Tests

设计难卡的滚动哈希

滚动哈希

我们使用二元组$(p,a)$来描述滚动哈希。其中$p$是模数（modulo），$a$是基数（base）。

对于长度为$n$的字符串$s$，它的滚动哈希函数为

$$h(S)=\sum_{i=1}^{n}a^{n-i}s_i \mod p$$

对于等长的两个字符串$S,T$，若$S\ne T$且$h(S)=h(T)$，则称这是等长冲突（equal-length collision）。

随机基数

考虑我们固定一个质数模数$p$，在$[1,p)$中随机一个整数作为基数$a$来做滚动哈希。

对于两个长度为$n$的串$S,T(S\ne T)$，考虑计算他们等长冲突的概率：

$$\begin{aligned} &h(S)=h(T) \\ \Leftrightarrow &\sum_{i=1}^na^{n-i}S_i=\sum_{i=1}^na^{n-i}T_i \mod p\\ \Leftrightarrow & P(a)=\sum_{i=1}^na^{n-i}(S_i-T_i)=0\mod p \end{aligned}$$

在这里$P(a)$是一个关于$a$的$n-1$度的多项式。那么$h(S)=h(T)$的概率就是$P(a)=0\pmod p$的概率，即$a$是$P$的根的概率。

由于$p$是质数，因此这构成一个域。在域中，任何$\le n-1$度的多项式最多有$n-1$个根。因此

$$\Pr[h(S)=h(T)]=\Pr[P(a)=0]\le \frac{n-1}{p}$$

对于$n=10^5,p=10^9+7$，这个概率是$10^{-4}$级别的。

$\frac{n-1}{p}$的范围其实比较紧的。如果$(n-1)\mid (p-1)$。考虑$S=\text{ba...aa},T=\text{aa...ab}$，则$P(a)=A^{n-1}-1\pmod p$。根据一些群论知识，这个方程有$n-1$个根。

随机模数

考虑固定基数$a(|\Sigma|\le a <N)$，然后在$[N,2N-1]$的范围内随机选择一个整数作为模数$p$。

同样地，对于两个长度为$n$的串$S,T(S\ne T)$，考虑计算他们等长冲突的概率：

$$\begin{aligned} h(S)=h(T) \Leftrightarrow X=\sum_{i=1}^na^{n-i}(S_i-T_i)=0\mod p \end{aligned}$$

则可以通过一些数学知识得到

$$\Pr[h(S)=h(T)]=\Pr[p\mid X]\le \sim\frac{n\ln(a)}{N}$$

对于$n=10^5,a=26,N=10^9$，这个概率是$3\times 10^{-4}$级别的。

如何随机

以下三种可以考虑：

//by Sshwy
//#define DEBUGGER
#include<chrono>
#include<iostream>
using namespace std;

int main(){
    cout<<chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count()<<endl;
    cout<<chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count()<<endl;
    cout<<__builtin_ia32_rdtsc()<<endl;
    return 0;
}

多重哈希

我们可以使用多重的随机滚动哈希。如果$k$重哈希的冲突概率分别是$\alpha_1,\alpha_2,\cdots,\alpha_k$，则你哈希碰撞的概率就是$\prod_{i=1}^k \alpha_i$。

更大的模数

你哈希的模数越大，冲突的概率就越小。但是更大的模数在计算过程中会很吃力。使用__int128会降低计算速度。不过有一个质数例外，那就是梅森质数$p=2^{61}-1$，我们可以通过位运算来计算$a\times b\mod p$：

constexpr uint64_t mod = (1ull<<61) - 1;
uint64_t mul(uint64_t a, uint64_t b){
	uint64_t l1 = (uint32_t)a, h1 = a>>32, l2 = (uint32_t)b, h2 = b>>32;
	uint64_t l = l1*l2, m = l1*h2 + l2*h1, h = h1*h2;
	uint64_t ret = (l&mod) + (l>>61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;
	ret = (ret & mod) + (ret>>61);
	ret = (ret & mod) + (ret>>61);
	return ret-1;
}

卡哈希

接下来就是关于如何卡哈希的教程了。

如何卡哈希

在介绍具体的方法之前，先思考一下，面对一道哈希问题，如果去卡它？

本质上，分为两个步骤：

1. 对于该哈希方式找一个等长冲突；
2. 利用这个等长冲突来造数据卡他。

单哈希

Thue–Morse 序列攻击：ULL 自然溢出

考虑$p=2^{64}$，$a$任意的情况。我们可以使用 Thue–Morse 序列来卡。它的生成方式如下：

const int Q = 10;
const int N = 1 << Q;
std::string S(N, ' '), T(N, ' ');

for (int i = 0; i < N; i++)
    S[i] = 'A' + __builtin_popcount(i) % 2;
for (int i = 0; i < N; i++)
    T[i] = 'B' - __builtin_popcount(i) % 2;

这时$S,T$就发生了等长冲突（不论$a$的值）。具体参见 这篇文章。

生日攻击：32 位模数，固定模数和基数

考虑使用生日攻击。固定长度$l$，令$k=1+\sqrt{(2\ln 2)p}$。并且等概率随机（uniformly at random）生成$k$个长度为$l$的字符串。

如果$l$的值不是特别小，则这$k$个串的哈希值可以近似看作等概率随机分布，使用生日悖论，则这$k$个数全部两两不同的概率是

$$\prod_{i=0}^{k-1}\left(1-\frac{i}{p} \right)<\prod_{i=0}^{k-1}e^{-\frac{i}{p}}<e^{-\ln 2}=\frac{1}{2}$$

因此我们重复这个过程，可以在$O(\sqrt{p})$的时间内找到等长冲突。

生日攻击不依赖于哈希函数（异或哈希也可以）。但它不能卡回文串。

代码

树攻击：更大模数，固定模数和基数

对于更大的模数，生日攻击将会变得很慢。

考虑树攻击（tree-attack）。

对于两个长度为$n$的的字符串$S,T$，我们知道

$$h(S)=h(T)\Leftrightarrow \sum_{i=1}^n(a^{n-i}\bmod p)(S_i-T_i)=0\mod p$$

不妨设$A_i=S_i-T_i$。显然$-|\Sigma|\le A_i\le |\Sigma|$。树攻击会尝试寻找一个$A_i\in\{-1,0,1\}$的序列使得

$$\sum_{i=1}^n(a^{n-i}\bmod p)A_i=0$$

考虑维护$k$个集合$C_1,\cdots,C_k$。定义$S(C)=\sum_{i\in C}(a^{n-i}\bmod p)A_i$。

如果我们合并两个集合$C_1,C_2$为$C_3$，则我们可以：

1. 直接合并，则$S(C_3)=S(C_2)+S(C_1)$；
2. 把$\forall i\in C_1,A_i$都乘$-1$再合并，则$S(C_3)=S(C_2)-S(C_1)$；
3. 类似 2，可以令$S(C_3)=S(C_1)-S(C_2)$；
4. 把$\forall i\in C_1,A_i$都变成$0$，则$S(C_3)=S(C_2)$；
5. 类似 4，可以令$S(C_3)=S(C_1)$。

一开始我们有$n$个集合，设每个集合的$A_i$都是$1$。不妨设$n=2^k$。则我们每个阶段，都把集合按$S(C)$排序，然后使用 2 或者 3 方法来合并相邻两个集合（要保证合并完后$S(C)$非负）。一轮完成后，集合数量减半。如果出现了一个$S(C)=0$的集合，那么我们把其他集合的$A_i$都置为$0$即可。这样会最多做$k$轮。如果没有找到，那么就对更大的$k$继续这个过程。

如果一开始$n$个集合的$S(C)$是等概率随机分布于$[0,p-1]$，则$k$期望为$\sqrt{2\lg p}+1$时可以找到。那么我们就可以$\Theta(n)$地构造长度为$n=2^{\sqrt{2\lg p}+1}$的等长冲突的串了。

注意，树攻击是依赖于哈希函数的，即你的哈希函数必须是多项式函数。

卡回文串

树攻击可以卡回文串。以偶回文串为例，具体地说，我们要构造一个长度为偶数的串$S$，使得$S\ne S^R,h(S)=h(S^R)$。$S^R$表示反串。

那么这等价于

$$\begin{aligned} &h(S)=h(S^R)\\ \Leftrightarrow& \sum_{i=1}^n(a^{n-i}\bmod p)(S_i-S_{n+1-i})=0\mod p\\ \Leftrightarrow& \sum_{i=1}^{\frac{n}{2}}((a^{n-i}-a^{i-1})\bmod p)(S_i-S_{n+1-i})=0 \end{aligned}$$

因此我们设$A_i=S_i-S_{n+1-i}$，得到

$$\sum_{i=1}^{\frac{n}{2}}((a^{n-i}-a^{i-1})\bmod p)A_i=0$$

那么我们对这个做一次正常的树攻击，就可以构造出一组$S_i-S_{n+1-i}$的值。

那么用字符$\text{a}$和$\text{b}$来构造串$S$即可。

代码

多重树攻击

尽管树攻击速度很快，生成的字符串可能会过长（对于$p=2^{61}-1$，通常$n=2048$）。实际上我们可以花更多的计算时间来生成一个尽量短的等长冲突。对于每个集合，我们可以维护$m$个最小的可能的和（单树攻击是$m=1$的情况）。合并两个集合可以使用堆在$O(m\log_2m)$的时间内完成。

一通鬼畜分析后，我们得到$k=\sqrt{2\frac{\lg p}{\lg m}}+\log_2(m)$。

这个东西 Dls 也没写过，所以不知道好不好使。

多重哈希

卡多重哈希的方式有两种。

逐个击破

以双哈希为例，考虑$(a_1,p_1),(a_2,p_2)$双哈希。首先我们使用生日攻击或者树攻击找到$(a_1,p_1)$的一个等长冲突$S,T$。然后我们以$\{S,T\}$作为字符集对$(a_2^{|S|},p_2)$求出等长冲突（以$\{S,T\}$作为字符集的意思是，我们用$S$和$T$拼接出一个更大的串）。这样就可以把两个哈希都冲突掉。

使用这个方法，时间复杂度是每次攻击的复杂度之和。但生成的串长会随着哈希的重数而指数级增长。

不过这个方法不用考虑模数的大小。

中国剩余定理（CRT）

对于树攻击，我们可以使用中国剩余定理来卡哈希。本质上，我们要求

$$\begin{cases} \sum_{i=1}^n({a_1}^{n-i}\bmod {p_1})A_i=0\\ \sum_{i=1}^n({a_2}^{n-i}\bmod {p_2})A_i=0 \end{cases}$$

设$x_i=a_1^{n-i},y_i=a_2^{n-i}$。然后我们使用 CRT 求出一个$z_i(0\le z_i <[p_1,p_2])$，使得

$$\begin{cases} z_i=x_i \mod p_1\\ z_i=y_i \mod p_2 \end{cases}$$

那么我们就只需要

$$\sum_{i=1}^n(z_i\bmod [p_1,p_2])A_i=0$$

即可。 那么我们对此做一次树攻击即可。

这个方法的要求模数的 LCM 不能太大。不过它的优点是，双哈希的回文串它也能卡。