本博客假设读者熟悉滚动 Hash 的基本概念。有些部分涉及大量数学知识，但无需了解每个细节即可掌握大部分概念。

本博客主要关注如何选择滚动 Hash 参数以避免被 Hack ，以及如何选择不当的参数 Hack hash。

设计难以破解的滚动 Hash

回顾滚动 Hash 和 Hash 碰撞

回想一下，滚动 Hash 有两个参数 \((p,a)\)，其中 \(p\) 是模数，\(0\le a < p\) 是基数。 （我们将看到 \(p\) 应该是一个大素数，并且 \(a\) 应该大于字母表的大小。）

字符串 \(S=s_0\cdots s_{n-1}\) 的 Hash 值由以下公式给出：

\[ h(S) = (\sum^{n-1}_{i=0} a^{n-i-1} s_i) \mod P \]

现在，让我们考虑一个简单的问题：给定两个长度相等的字符串 \(S,T\)，通过比较它们的 Hash 值 \(h(S), h(T)\) 来判断它们是否相等。如果 \(h(S) = h(T)\)，我们的算法将 \(S\) 和 \(T\) 声明为相等。大多数滚动 Hash 解决方案都是基于对此子问题的多次调用或依赖于此类调用的正确性。

让我们将两个长度相等的字符串 \(S, T\) 称为 等长碰撞（或 等长冲突），其中 \(S \neq T\) 和 \(h(S) = h(T)\)。我们希望避免 等长冲突，因为它们会导致我们的算法错误地将 \(S\) 和 \(T\) 评估为相等。（请注意，我们的算法绝不会错误地将字符串评估为不同的。）对于固定参数和相当小的长度，字符串的数量远多于可能的 Hash 值，因此总是存在 等长冲突。因此，您可能会认为，对于任何滚动 Hash ，都有一些 Hack 导致 等长冲突。

幸运的是，随机化可以拯救我们。我们的算法不必固定 \((p, a)\)，它可以根据某种方案随机选择。如果我们可以证明对于任意两个字符串 \(S, T\)，\(S\neq T\)，该方案会以高概率选择 \((p, a)\)，使得 \(h(S) \neq h(T)\)，则该方案是可靠的。请注意，概率空间仅包括方案内部的随机选择；输入 \((S, T)\) 是任意的、固定的，不一定是随机的。 （如果您认为输入来自 Hack ，那么这意味着无论输入是什么，我们的解决方案都不会以高概率失败。）

我将向您展示两个可靠的方案。（请注意，方案可靠并不意味着您的实现很好。必须小心使用随机数生成器。）

随机化基础

本部分基于 rng_58 的 博客。他的帖子涵盖了更一般的 Hash 问题，值得一看。

该方案使用 \(a\) 个固定的 素数 \(p\)（即 \(10^9 + 7\) 或 \(4\cdot 10^9 + 7\)）并从 \([0,p-1]\) 中均匀随机地选取 \(a\)。令 \(A\) 为选择 \(a\) 的随机变量。

为了证明该方案是好的，考虑两个长度相等的字符串 \((S, T)\) 并进行一些计算：

\[ \begin{aligned} h(S)&=h(T)\\ (\sum_{i=0}^{n-1} A^{n-i-1} S_i) \mod p & = (\sum_{i=0}^{n-1} A^{n-i-1} T_i) \mod p \end{aligned} \]

因此，我们有：

\[ \sum_{i=0}^{n-1} A^{n-i-1} S_i \equiv \sum_{i=0}^{n-1} A^{n-i-1} T_i \pmod p\\ \]

我们让 \(P(A)\) 表示 \(A\) 中次数为 \(\le n-1\) 的多项式:

\[ P(A) = \sum_{i=0}^{n-1} A^{n-i-1}(S_i-T_i) \equiv 0 \pmod p \]

当 \(S \neq T\) 时，\(P\) 非零。计算表明，当且仅当 \(A\) 是 \(P(A)\) 的根时，\(h(S) = h(T)\)。

由于 \(p\) 是素数，并且我们正在进行 \(\mod p\) 计算，因此我们正在一个域中工作。在一个域上，任何次数为 \(\le n - 1\) 的多项式最多有 \(n-1\) 个根。因此，最多有 \(n - 1\) 个 a 选项导致 \(h(S) = h(T)\)。因此：

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

因此，对于任何两个长度相等的字符串 \((S, T)\)，它们形成等长碰撞的概率最多为 \(\frac{n-1}{p}\)。对于 \(n = 10^5, p = 10^9 + 7\)，这个概率大约是 \(10^{-4}\)。选择较大的素数，例如 \(2^{31} - 1\) 或 \(4\cdot 10^9 + 7\) 可以稍微改善这一点，但需要更加注意溢出。

边界的紧密性

目前，这部分仅适用于具有平滑 \(p - 1\) 的素数，因此它不适用于例如 \(p = 10^9 + 7\)。找到一种可计算且在一般情况下有效的构造将会很有趣。

如果 \(n-1|p-1\)，则此方案的边界 \(\frac{p-1}{p}\) 实际上是紧的。考虑 \(S=ba...a\) 和 \(T=aa...b\)，其中 \(P(A)=A^{n-1}-1\)。

由于 \(p\) 为素数，\(\frac{\mathbb{Z}}{p\mathbb{Z}}\) 是阶为 \(p - 1\) 的循环群，因此存在阶为 \(n - 1\) 的子群 \(G \subseteq \frac{\mathbb{Z}}{p\mathbb{Z}}\)。任何 \(g\subseteq G\) 都满足 \(g^{n - 1} = 1\)，因此 \(P(A)\) 有 \(n - 1\) 个不同的根。

随机化模数

该方案固定基数 \(a \le |\sum|\) 和边界 \(N > a\)，并从 \([N, 2N - 1]\) 中均匀随机地选取一个 素数 p。

为了证明该方案是好的，再次，考虑两个长度相等的字符串\((S, T)\)并进行一些计算：

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

因此，我们有：

\[ \sum_{i=0}^{n-1} a^{n-i-1} S_i \equiv \sum_{i=0}^{n-1} a^{n-i-1} T_i \pmod p\\ \]

所以：

\[ X = \sum_{i=0}^{n-1}a^{n-i-1}(S_i-T_i) \equiv 0 \pmod p \]

当 \(X \equiv 0 \pmod p,p|X\) 时，我们选择一个足够大的值，\(X \neq 0\)。此外，\(|X| < a^n\)。\([N, 2N - 1]\) 中 \(X\) 的不同素因数的数量上限由 \(\log_N (|X|) = \frac{n\ln (a)}{\ln N}\) 给出。根据素数密度定理，\([N, 2N - 1]\) 中大约有 \(\frac{X}{\ln{N}}\) 个素数。因此：

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

请注意，此界限比随机化基数的界限稍差。当 \(n = 10^5、a = 26、N = 10^9\) 时，该界限约为 \(3\cdot 10{-4}\)。

如何正确随机化

以下是初始化随机数生成器的好方法。

  • 高精度时间。

    1
    2
    chrono::duration_cast<chrono::nanoseconds>      (chrono::high_resolution_clock::now().time_since_epoch()).count();
    chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count();

    两者之一都可以。（理论上，high_resolution_clock 应该更好，但它在 codeforces 上的精度却低于 steady_clock？？）

  • 处理器周期计数器

    1
    __builtin_ia32_rdtsc();

  • 一些堆地址转换为整数

    1
    (uintptr_t) make_unique<char>().get();

  • 处理器随机性（需要 pragma 或 asm）（感谢 halyavin 建议 此。）

    1
    2
    3
    4
    5
    6
    7
    // pragma 版本
    #pragma GCC target ("rdrnd")
    uint32_t rdrand32(){
        uint32_t ret;
        assert(__builtin_ia32_rdrand32_step (&ret));
        return ret;
    }
    1
    2
    3
    4
    5
    6
    // asm 版本
    uint32_t rd() {
        uint32_t ret;
        asm volatile("rdrand %0" :"=a"(ret) ::"cc");
        return ret;
    }

如果您使用 C++11 样式的 rng（您应该使用），则可以使用上述组合：

1
2
3
4
5
6
7
seed_seq seq{
    (uint64_t) chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count(),
    (uint64_t) __builtin_ia32_rdtsc(),
    (uint64_t) (uintptr_t) make_unique<char>().get()
};
mt19937 rng(seq);
int base = uniform_int_distribution<int>(0, p-1)(rng);

请注意，这确实会在内部丢弃参数中的高 32 位，但这实际上并不重要，因为低位更难预测（尤其是在第一种情况下使用 chrono）。

请参阅“滥用不良随机化”部分，了解一些不良示例。

扩展到多个 Hash

我们可以使用多个 Hash （即使使用相同的方案和相同的固定参数），并且只要随机样本是独立的， Hash 就是独立的。如果单个 Hash 失败的概率最多为 \(a_1,\cdots, a_k\)，则所有 Hash 失败的概率最多为 \(\prod_{i=1}^k a_i\)。

例如，如果我们使用两个 Hash ，其中 \(p = 10^9 + 7\) 和随机化基数，则发生碰撞的概率最多为 \(10^{ - 8}\)；对于四个 Hash ，它最多为 \(10 ^{- 16}\)。这里，稍大素数的常数更为重要，对于 \(p = 2^{31} - 1\)，概率约为 \(2.1\cdot 10^{ - 9}\) 和 \(4.7\cdot 10^{ - 18}\)。

更大的模数

使用更大的（即 60 位）素数将使碰撞的可能性更小，并且不会受到错误界限内 \(n\) 累积因子的影响。但是，滚动 Hash 的计算变得更慢、更困难，因为 codeforces 上没有 __int128。

一个例外是梅森素数 \(p = 2^{61} - 1\)；我们可以改用位移位来减少 \(\mod p\)。 （感谢 dmkz 提出此建议。）以下代码不使用 __int128 计算 \(a\cdot b \mod p\)，仅比使用模数的 \(30\) 位 Hash 慢约 \(5\%\)。

对于参数，条件 \(0\le a,b < mod\) 应该成立。然后返回值也满足此条件。

1
2
3
4
5
6
7
8
9
constexpr uint64_t mod = (1ull<<61) - 1;
uint64_t modmul(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;
}

使用无符号类型和 \(p=4\cdot 10^9 + 7\) 可以获得较小的因子。

请注意，\(p=2^{64}\)（unsigned long long 溢出）不是素数，无论随机化如何都可以被破解（见下文）。

扩展到多个比较

通常，滚动 Hash 值用于多个比较。如果我们仅基于 \(m\) 次比较，并且一次比较失败的概率为 \(p\)，则任何一次失败的概率最多为 \(m\cdot p\)（根据联合界限）。请注意，当 \(m = 10^5\) 时，我们至少需要两个或三个 Hash 才能使这个概率很小。

在估计成功所需的比较次数时，必须非常小心。如果我们对 Hash 进行排序或将它们放入一个集合中，我们需要有成对不同的 Hash ，因此对于 \(n\) 个字符串，总共需要 \(\binom{n}{2}\) 次比较成功。如果 \(n = 3\cdot 10^5\)，\(m=4.5\cdot 10^9\)，所以我们需要三个或四个 Hash （如果我们使用 \(p = 2^{61} - 1\)，则只需要两个）。

扩展到不同长度的字符串

如果我们处理不同长度的字符串，我们可以通过在 Hash 中存储长度来避免比较它们。但是，如果我们假设 没有字符 Hash 为 \(0\)，则情况并非如此。在这种情况下，我们可以简单地想象我们在较短的字符串前面添加空字节以获得相同长度的字符串而不改变 Hash 值。那么上面的理论就适用了。（如果某个字符（即 a） Hash 为 \(0\)，我们可能会生成看起来相同但在添加过程中并不相同的字符串（即 a 和 aa）。）

计算反 Hash 测试

本节介绍一些利用滚动 Hash 实现中常见错误的技术，主要用于破解其他解决方案。这里有一个表格，其中简要总结了这些方法。

名称用例运行时间字符串长度注释
Thue-Morse 序列带溢出的 Hash\(O(1)\)\(2^{10}\)可同时适用于所有基数。
生日攻击小模数\(O(\sqrt{p}\log p)\)\(\approx 2\log_{ \begin{vmatrix}\sum\end{vmatrix} }p\)可以找到多个碰撞。
树攻击大模数\(O(2^{\sqrt{p\lg p}})\)\(O(2^{\sqrt{p\lg p}}+1)\)更快；更长的字符串
多树攻击大模数\(O((2^{\sqrt{2\lg m p}}+\log_{ \begin{vmatrix}\sum\end{vmatrix} } m)\cdot m\log m)\)\(\approx O((2^{\sqrt{2\lg m p}}+\log_{ \begin{vmatrix}\sum\end{vmatrix} }m))\)更慢；更短的字符串
格子缩减中大型字母表，多重 Hash\(O(length^3)\)\(\approx \sum_{i=0}^{n-1} \log_{ \begin{vmatrix} \sum \end{vmatrix}} (p_n)\)对于 \(\begin{vmatrix}\sum\end{vmatrix} =26\) 的结果很好，对多重 Hash 很有效。对二进制字母表很差。
组合多重 Hash单个运行时间的总和单个字符串长度的乘积结合了两种攻击。

单个 Hash

Thue–Morse 序列：带有无符号溢出的 Hash （\(p = 2^{64}\)，\(q\) 任意）

一种适用于任何基数的反 Hash 测试是 Thue–Morse 序列，由以下代码生成。

1
2
3
4
5
6
7
8
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\) 都会形成等长碰撞。

有关详细讨论，请参阅此 博客。请注意，链接博客上的界限可以略微改进，因为对于奇数 \(X\)，\(X^2 - 1\) 总是可以被 \(8\) 整除。 （因此我们可以使用 \(Q = 10\) 而不是 \(Q = 11\)。）

生日攻击：使用 32 位素数和固定基数的 Hash （\(p < 2^{32}\) 固定，\(q\) 固定）

具有单个小素数的 Hash 可以通过生日悖论进行攻击。固定长度 \(l\) 和字母表 \(d\) 的大小，并随机均匀地选择长度为 \(l\) 的 \(k\) 个字符串。如果 \(l\) 不太小，则生成的 Hash 值将大致均匀分布。根据生日悖论，我们挑选的所有字符串 Hash 值都不同的概率是：

\[ \sum_{i=0}^{k-1}(1-\frac{i}{d}) < \sum_{i=0}^{k-1}(e^{-\frac{i}{d}}) =e^{-\frac{k(k-1)}{2d}} < e^{-\ln 2} = \frac{1}{2} \]

因此，概率为 \(> \frac{1}{2}\)，我们发现两个字符串有 Hash 到相同的值。通过重复此操作，我们可以在 \(O(\sqrt{p})\) 中找到具有高概率的等长碰撞。实际上，生成的字符串可能非常小（对于 \(p = 10^9 + 7\)，长度 $ $ 和 \(d=62\)，不确定如何限制其上限。）。

更一般地，我们可以使用与 \(r = m \cdot p^{1-\frac{1}{m}}\) 相同的技术在 \(O(m\cdot p^{1-\frac{1}{m}})\) 中计算具有相等 Hash 值的 \(m\) 个字符串。

树攻击：使用较大素数和固定基数（\(p\) 固定，\(q\) 固定）进行 Hash 运算

感谢 Kaban-5 和 pavel.savchenkov 提供的 链接 一些描述此想法的俄罗斯评论。

对于较大的素数，生日攻击速度太慢。回想一下，对于两个长度相等的字符串 \((S, T)\)：

\[ h(S)=h(T) \]

\[ \sum_{i=0}^{n-1}a^{n-i-1}(S_i-T_i) \equiv 0 \pmod{p} \]

我们设置 \(\alpha_i = S_i - T_i\) 满足 \(-|\sum| \le \alpha_i \le |\sum|\)。树攻击试图找到 \(\alpha_i \in\{-1,0,1\}\) 使得：

\[ \sum_{i=0}^{n-1} (a_{n-i-1} \mod p) \cdot \alpha_i = 0 \]

攻击维护系数簇 \(C_1, ..., C_k\)。集群 \(C\) 的总和 \(S(C)\) 由以下公式给出：

\[ S(C) = \sum_{i\in C} (a_{n-i-1} \mod p) \cdot \alpha_i \]

我们可以将两个集群 \(C_1\) 和 \(C_2\) 合并为总和为 \(S(C_1) - S(C_2)\) 的集群 \(C_3\)，方法是将 \(C_2\) 中的所有 \(\alpha_i\) 乘以 $ - 1$，并将 \(C_1\) 和 \(C_2\) 的系数集合并。此操作可以在恒定时间内实现，方法是将集群存储为二叉树，其中每个节点存储其总和；然后，合并操作为 \(C_3\) 添加一个新节点，该节点具有子节点 \(C_1\) 和 \(C_2\)，总和为 \(S(C_1) - S(C_2)\)。为了确保 \(S(C_3) \ge 0\)，必要时交换 \(C_1\) 和 \(C_2\)。\(\alpha_i\) 的值未明确存储，但可以通过遍历树在最后重新计算。

最初，我们从 \(n = 2k\) 开始，每个 \(\alpha_i=1\) 都在自己的集群中。在一个阶段中，我们首先按总和对集群进行排序，然后合并相邻的集群对。如果我们在任何时候遇到总和为 \(0\) 的集群，我们将通过将不在该集群中的所有 \(\alpha_j\) 设置为 \(0\) 来完成。如果我们在 \(k\) 个阶段后仍未完成，请使用更大的 \(k\) 值重试。

对于哪些 \(k\) 值，我们可以期望这有效？如果我们假设总和最初在 \([0,p-1]\) 中均匀分布，则在阶段 \(i\) 中，最大总和应该减少因子 \(\sim 2^{k-i}\)。经过 \(k\) 个阶段后，最大和约为 \(\frac{p}{2^{\binom{k}{2}}}\)，因此 \(k\approx \sqrt{2\lg p}+1\) 有效。这会在 \(O(n)\) 时间内生成长度为 \(n=2^{\sqrt{2\lg p}+1}\) 的字符串。（可以在论文“在预期多项式时间内解决中密度子集和问题”第 2.2 节中找到更正式的分析。论文中的问题和算法略有不同，但方法相似。）

多树攻击

虽然树攻击运行速度非常快，但生成的字符串可能会变得有点长。 (\(n = 2048\)，\(p = 2^{61} - 1\)。) 我们可以花费更多时间来搜索更短的碰撞，方法是存储每个集群中可以获得的最小 \(m\) 个和。（单树攻击只使用 \(m = 1\)。）合并两个集群可以在 \(O(m\log m)\) 中完成，使用最小堆和 \(2m\) 指针遍历。为了尽快获得 \(m\) 个字符串，我们允许所有值 \(\alpha_i\in[-|\sum|,|\sum|]\) 并排除所有 \(\alpha_i\) 都为零的简单情况。

分析 \(k\) 的预期值以使其发挥作用非常困难。乐观地假设我们在 \(\log_{|\sum|}m\) 步之后每个节点达到 \(m\) 个总和，并且总和会像单树攻击一样减少，而且根据生日悖论，当它们变得小于 \(m^2\) 时我们可以预期会发生碰撞，我们得到 \(k = \sqrt{2\frac{\lg p}{\lg m}}+\log_{|\sum|} m\)。 （更现实的界限是 \(k=\frac{\lg p}{\lg m}+log_{|\sum|}m\)，这可以通过考虑论文“关于随机高密度子集总和”中证明的界限中的生日悖论来获得，定理 3.1。）

在实践中，我们可以使用 \(m \approx 10^5\) 来找到长度为 \(128\) 的碰撞，其中 \(|\sum|=2\)，\(p = 2^{61} - 1\) 大约需要 0.4 秒。

格子缩减攻击：对不太小的字母表进行单个或多个 Hash

感谢 hellman_ 提及此内容，请在此处查看他关于此主题的文章。此处 也有其他人的文章。

与树攻击一样，我们正在寻找 \(\alpha_i\in[-|\sum|,|\sum|]\)，使得：

\[ \sum_{i=0}^{n-1} (a_{n-i-1} \mod p) \cdot \alpha_i = 0 \]

换成集合形式：

\[ {\alpha_0,\cdots,a_{n-1},\beta} | \beta \equiv \sum_{i=0}^{n-1} (a_{n-i-1} \mod p)\cdot \alpha_i \]

形成一个格（嵌入在 \(\mathbb{R}^n\) 子空间中的自由 \(\mathbb{Z}\) 模块。）我们在格中寻找一个元素，使得 \(\beta = 0\) 且 \(|\alpha_i| \le |\sum|\)。我们可以通过考虑以下因素来惩罚 \(\beta\) 的非零值：

\[ \beta = 10^5((\sum_{i=0}^{n-1} (a_{n-i-1} \mod p)\cdot \alpha_i)) \mod p \]

然后我们寻求最小化 \(\max\{|\alpha_0|,\cdots,|a_{n-1}|,|\beta|\}\)。不幸的是，这个优化问题相当困难，所以我们尝试最小化：

\[ \alpha_0^2 + \cdots + \alpha_{n-1}^2 + \beta^2 \]

结果问题仍然很难，可能是 NP 完全的，但有一些很好的近似算法可用。

与向量空间类似，我们可以在格中定义一个基。对于我们的情况，基础由以下公式给出：

\[ \{e_\beta+10^5(a_{n-i-1} \mod p)e_{a_i} | 0\le i < n\} \cup \{p\cdot 10^5e_\beta\} \]

格简化算法采用此基础并将其（通过具有行列式 \(\pm\) 的可逆矩阵）转换为具有近似最短向量的另一个基础。实现它们非常困难（并且会受到精度错误或大数减速的影响），因此我决定使用 sage 中的内置实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
"""通过格子归约生成反滚动 Hash 测试
原始代码由 Hellman_ 编写，由 dacin21 修改
"""

from sage.all import *

def anti_hash(PAs, string_length, sigma, block_size = 0, MULTIPLIER = 100000, sigma_base = ord('a')):
    n = len(PAs)
    N = string_length
    As = [a for p, a in PAs]
    Ps = [p for p, a in PAs]

    def h(s):
        """多项式 Hash 模数 <n> 素数"""
        v = [0] * n
        for c in s:
        v = [(x * q + ord(c))%p for x, q, p in zip(v, As, Ps)]
        return tuple(v % p for v, p in zip(v, Ps))

    mv = matrix (ZZ, N, N)
    for y in xrange(N) ：
    for x, q, p in zip(range(n), As, Ps) 中：
    mv[y,x] = pow(q, N-y-1, p);

    m = matrix(ZZ, N + n, N + n)
    # 带项的子矩阵
    m.set_block(0, 0, MULTIPLIER * mv)
    # 模数减少
    m.set_block(N, 0, MULTIPLIER * diagonal_matrix(Ps))
    # 项系数
    m.set_block(0, n, Identity_matrix(N))
    # 第 4 个子矩阵为零

    m_reduced = m.LLL()
    if block_size > 0:
    m_reduced = m_reduced.BKZ(block_size = block_size)

    for row in m_reduced:
        print row[:n], min(row[n:]), "~", max(row[n:])
        delta = max(abs(v) for v in row[n:])
        if set(row[:n]) == {0} and delta < sigma:
            print "发现碰撞！"
            s = [None] * N
            t = [None] * N
            for i, v in enumerate(row[n:]):
            a = sigma_base
            b = a + abs(v)
            if v > 0:
                a, b = b, a
            s[i] = a
            t[i] = b
        s = "".join(map(chr, s))
        t = "".join(map(chr, t))
        print s + " " + t
        # print h(s)
        # print h(t)
        assert h(s) == h(t)
        break
    else:
        print "无法找到碰撞，请尝试更大的 string_length"
        print "对于长度 > 30，建议将 block_size 设置为 10 或 15"

if __name__ == '__main__':
    with open("hash.in", 'r') as infile:
        n, k, sigma = map(int, infile.readline().strip().split())
        PAs = [tuple(map(int, infile.readline().strip().split())) for _ in xrange(n)]
        anti_hash(PAs, k, sigma)

输入取自格式为 hash.in 的文件。要使用 BKZ 算法，请设置 block_size 参数。

输入格式：

1
2
3
4
n lenth sigma
p_1 a_1
...
p_n a_n

Sage 提供两种算法：LLL 和 BKZ，前者速度更快，但近似值更差，尤其是对于较长的字符串。分析它们很困难，所以我做了一些实验，固定 \(|\sum|=26\)、\(p = 2^{61} - 1\) 并随机固定 \(a_1,\cdots ,a_n\)，并使用这两种算法搜索简短的反 Hash 测试。结果非常好。

LLL 算法：

\(n\)最小长度花费的时间（秒）
1120.02
2230.04
3340.08
4480.18
5600.34
6770.75
73015.14
8\(>1500\)\(>990\)

对于 \(n = 8\)，算法无法找到长度为 \(\le 1500\) 的碰撞。

BKZ 算法，其中 block_size = 10:

\(n\)最小长度所用时间（秒）
1120.02
2230.04
3330.09
4450.21
5570.58
6721.12
7882.59
81085.33

block_size = 15 的 BKZ 算法：

\(n\)最小长度所用时间（秒）
1120.02
2230.04
3330.09
4450.21
5570.52
6701.24
7852.41
81025.20

block_size = 25 的 BKZ 算法：

\(n\)最小长度所用时间（秒）
1120.02
2230.04
3330.10
4460.58
5571.14
6703.67
7846.96
89626.70

请注意，当 \(n > 1\) 时，此攻击对小（即二进制）字母表效果不佳，并且字符必须散列为连续值，因此如果用于组合攻击，这必须是第一次攻击。

组合攻击：多个 Hash

本部分归功于 ifsmirnov，我在他的 jngen 库中找到了这种技术。

使用两个或更多 Hash 通常足以防止直接生日攻击。 对于两个素数，有 \(N = p_1·p_2\) 个可能的 Hash 值。 生日攻击在 \(O(\sqrt{N})\) 中运行，对于大约 \(10^9\) 的素数，这大约是 \(\approx 10^{10}\)。 此外，内存使用量超过 \(\sqrt{(2 \ln 2)N}\cdot 8\) 字节（如果您只存储 Hash 和 rng 种子），大约是 9.5 GB。

破解多个 Hash 的关键思想是逐个破解它们。

  • 首先为第一个 Hash \(h_1\) 找到一个等长碰撞（通过生日攻击），即两个长度相等的字符串 \(S, T, S \neq T\)，其中 \(h_1(S) = h_1(T)\)。请注意，在字母表 \(S, T\) 上构建的等长字符串（即通过将 \(S\) 的一些副本与 \(T\) 的一些副本连接起来，反之亦然）现在将在 \(h_1\) 下散列为相同的值。
  • 然后在为第二个 Hash \(h_2\) 搜索等长碰撞（再次通过生日攻击）时使用 \(S\) 和 \(T\) 作为字母表。结果也将自动成为 \(h_1\) 的碰撞，因为我们使用 \(S, T\) 作为字母表。

这减少了运行时间 \(O(\sqrt{p_1}+\sqrt{p_2})\) 。请注意，如果我们使用 Thue-Morse 序列代替第二个生日攻击，这也适用于 30 位素数 Hash 和 Hash 模 \(2^{64}\) 的组合。同样，对于更大的模数，我们可以使用树攻击而不是生日攻击。

另一件需要注意的事情是，字符串长度会随着 Hash 数的增加而迅速增长。 （大约 \(2\log_{|\sum|}(\sqrt{(2\ln 2)p_1})\cdot\log_2 (\sqrt{(2\ln 2)p_2})\cdots \log_2(\sqrt{(2\ln 2)p_k})\)，在第一次生日攻击后，字母表大小减少到 \(2\)。实际上，第一次迭代的倍数为 \(2\)。）如果我们在中间步骤中搜索 2 个以上具有相同 Hash 值的字符串，字母表大小将更大，从而导致字符串更短，但生日攻击的运行时间会变慢（例如，对于 \(3\) 个字符串，运行时间为 \(O(p^{\frac{2}{3}})\)）。

滥用不良随机化

在 codeforces 上，很多人会随机化他们的 Hash 值。（不幸）的是，他们中的许多人都以次优的方式进行。本节介绍了人们搞砸 Hash 随机化的一些方法以及破解其代码的方法。

本节更广泛地适用于其他参与者可以破解您的解决方案的环境中任何类型的随机算法。

固定种子

如果 rng 的种子是固定的，它总是会产生相同的随机数序列。您只需运行代码即可查看哪些数字是随机生成的，然后找到这些数字的反 Hash 测试。

从一小群基数中挑选（rand()%100）

请注意，rand() % 100 最多产生 100 个不同的值 \([0,99]\)。我们可以为每个值找到一个单独的反 Hash 测试，然后将这些测试合并为一个。 （您的组合测试方式是针对特定问题的，但它适用于大多数问题。）

rand() 的更多问题

在 codeforces 上，rand() 仅产生 \(15\) 位值，因此最多产生 \(2^{15}\) 个不同的值。虽然运行 \(2^{15}\) 个生日攻击可能需要一段时间（在我的笔记本电脑上使用单个线程估计 \(p = 10^9 + 7\) 需要 \(111\) 分钟），但这可能会导致其他一些随机算法出现一些大问题。

编辑：如果我们使用多树攻击，这种类型的 Hack 攻击可能是可行的。对于 $ p =10^9+7,||=26$，运行 \(2^{15}\) 多树攻击，其中 \(m = 10^4\) 需要大约 \(2\) 分钟，并产生 \(5.2\cdot 10^5\) 个字符的输出。对于大多数问题来说，这仍然有点太大，但例如，可以在开放 Hack 阶段分成多个 Hack 攻击。

在 C++11 中，您可以使用 mt19937 和 uniform_int_distribution 代替 rand()。

低精度时间（Time(NULL)）

Time(NULL) 每秒仅更改一次。可以按以下方式利用它

  1. 选择一个时间跨度 \(\Delta T\)。
  2. 找到生成测试所需时间的上限 \(T\)。
  3. 通过自定义调用找出 Time(NULL) 的当前值 \(T_0\)。
  4. 对于 \(t = 0,\cdots,(\Delta T) - 1\)，将 Time(NULL) 替换为 \(T_0 + T + t\)，并针对此固定种子生成反测试。
  5. 在时间 \(T_0 + T\) 提交 hack。

如果您的 hack 在接下来的 \(\Delta T\) 秒内执行，Time(NULL) 将是您为其生成反测试的值，因此解决方案将失败。

MinGW 上的随机设备（std::random_device）

请注意，在 codeforces 上，std::random_device 是确定性的，将产生相同的数字序列。使用它的解决方案可以像固定种子解决方案一样被破解。

本文翻译自 On the mathematics behind rolling hashes and anti-hash tests

转载请注明原文出处

警告：本文部分使用了 AI 翻译，可能存在不准确或错误的地方。