如何有理有据地卡古典字符串哈希

前置知识

古典字符串哈希

• 模数和 base 固定
• 每个字符的权值在一个连续的小区间内。例如，$\mathtt{\{'A','B','C','D',\dots\}}\rightarrow \{0,1,2,3,\dots\}$。

由于单模 hash 和自然溢出 hash 的卡法已经众所周知了，在这里不做赘述。

格，基

对于一组线性无关的 $n$ 维列向量 $\{\mathbf{b_1,b_2,\dots,b_k}\}$ 定义其生成的格为：

$$ \mathcal{L}(\{\mathbf{b_1,b_2,\dots,b_k}\}) = \{\sum_{i}\mathbf{c_ib_i\ |\ c_i\in \mathbb{Z}}\} $$

称 $\mathbf{B=[b_1,b_2,\dots,b_k]}$ 为格的一组基。

定义古典 hash 函数 $f(S,e,p)= \sum_i{S_i e^i} \bmod p$

发现我们实际上要构造一个这样的状物：

$\sum_i{(S_i-T_i) e^i} \equiv 0 \bmod p$

发现我们只需要关心 $S_i-T_i$，并且要能让这个差值 fit 进字符集里。

构造如下的列向量：

$$ B = \begin{bmatrix} 1 & 0 & 0 & \dots & 0 & 0\\ 0 & 1 & 0 & \dots & 0 & 0\\ 0 & 0 & 1 & \dots & 0 & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 0 & 0 & 0 & \dots & 1 & 0\\ e^0 & e^1 & e^2 & \dots & e^n & p \end{bmatrix} $$

则若 $\mathcal{L}(B)$ 中存在一个短向量，满足最后一个元素为 $0$，并且前面部分绝对值都小于 $\sigma$，那么就找到了一组解。

问题转化成了找格中的短向量。

如果要找最短向量是 NPC 的，但是我们有一个不错的算法可以找出一组近似解。

LLL 算法

我们定义 Gram-Schmidt 正交化：

对于一组向量 $\mathbf{(b_1,b_2,\dots,b_n)}$ 其正交化结果为：

$$ \mathbf{b^*_i:= b_i}-\sum_{j=1}^{i-1} \mathbf{b_j^*}\mu_{i,j} $$

其中 $\mu_{i,j}=\dfrac{<\mathbf{b_i,b_j^*}>}{<\mathbf{b_j^*,b_j^*}>}$，即 $\mathbf{b_i}$ 在 $\mathbf{b_j}$ 上的投影。

如果没看懂可以尝试阅读这个。

定义 LLL-简化基：

对于一个参数 $\delta \in (\frac{1}{4},1)$，$\mathbf{B=[b_1,b_2,\dots,b_k]}$ 是 LLL-简化基的充要条件为：

• $\forall 1\le j<i\le n, |\mu_{i,j}| \le \frac{1}{2}$（也就是向量之间比较接近正交）
• $\forall 1\le i < n, \delta ||\mathbf{b_i^*}||^2 \le ||\mathbf{b_{i+1}^*}+\mu_{i+1,i}\mathbf{b_i^*}||^2$（也就是 $\mathbf{b_{i+1}^*}$ 并不比 $\mathbf{b_i^*}$ 短很多）

可以证明，在这两个条件下，我们有：

$$ ||\mathbf{b_1}|| \le (\delta-\frac{1}{4})^{\frac{1-n}{2}} \bf \lambda_1 $$

其中 $\bf\lambda_1$ 是格中最短非零向量的长度。

取 $\delta = \frac{1}{4}+(\frac{3}{4})^{\frac{n}{n-1}}$，则有：

$$ ||\mathbf{b_1}|| \le (\dfrac{2}{\sqrt3})^n \bf \lambda_1 $$

也就是说，只要找到了这样的一组基，我们就有了格中最短向量的近似解。

算法流程：

先定义三个步骤：

• Build: 跑一遍 Gram-Schmidt 正交化。
• Reduction：从前向后处理每个 $\mathbf{b_i}$，每次按照 $j$ 递减的顺序令 $\mathbf{b_i} \gets \mathbf{b_i}-c_{i,j}\mathbf{b_j}$，其中 $c_{i,j}$ 为 $\mu_{i,j}$ 四舍五入后的结果。可以证明，一轮 Reduction 结束后，$\mathbf{b_i^*}$ 的值不变，且第一个条件得到了满足。
• Swap：找到任意一个 $i\in[1,n)$ 不满足第二个条件，然后交换 $\bf b_i, b_{i+1}$。如果无法找到这样的 $i$，则终止算法。

LLL 算法：依次运行 Build, Reduction, Swap 直到得到了一组 LLL-简化基。

可以证明，算法一定会停机，且时间复杂度为 $\tilde O(n^5q^2)$，其中 $n$ 为输入矩阵大小，$q$ 为 $\bf B$ 中元素值域的对数。

如何有理有据地卡哈希？

首先，为了尽可能保证得到的列向量最后一行为 $0$，并加入多哈希的支持，不妨将 $\bf B$ 修改为这样：

$$ B = \begin{bmatrix} 1 & 0 & 0 & \dots & 0 & 0 & 0 & \dots & 0\\ 0 & 1 & 0 & \dots & 0 & 0 & 0 & \dots & 0\\ 0 & 0 & 1 & \dots & 0 & 0 & 0 & \dots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & 0\\ 0 & 0 & 0 & \dots & 1 & 0 & 0 & \dots & 0\\ Me_1^0 & Me_1^1 & Me_1^2 & \dots & Me_1^n & Mp_1 & 0 & \dots & 0\\ Me_2^0 & Me_2^1 & Me_2^2 & \dots & Me_2^n & 0 & Mp_2 & \dots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots\\ Me_m^0 & Me_m^1 & Me_m^2 & \dots & Me_m^n & 0 & 0 & \dots & Mp_m\\ \end{bmatrix} $$

其中 $M\approx 2\sigma$，目的是增大最后 $m$ 行权重，使得只有最后 $m$ 行为 $0$ 的向量才是短的。

直接跑 LLL 即可，$n$ 设为 $32$ 左右即可在 5s 左右卡掉大多数 5 模数哈希，而对于这样级别的 hash 通过生日悖论碰撞的代价是不可接受的。

同样也可以支持多模 long long 的情况，但是可能需要高精度小数，有空接一个 $\text{GMP}$ 进来。

下面是代码（写得较丑，轻喷）：

namespace LLL {
using vec = vector<ldb>;
using mat = vector<vec>;
constexpr ldb eps = 1e-7;
il ldb inner(const vec &x, const vec &y) {
  assert(x.size() == y.size());
  ldb ans = 0;
  int n = x.size();
  For(i, 0, n - 1) ans += x[i] * y[i];
  return ans;
}
il vec mul(const db &x, vec y) {
  for (auto &v : y)
    v *= x;
  return y;
}
il void do_sub(vec &x, const vec &y) {
  assert(x.size() == y.size());
  int n = x.size();
  For(i, 0, n - 1) x[i] -= y[i];
}
il ldb sq_mod(const vec &x) {
  ldb sum = 0;
  for (auto v : x)
    sum += sq(v);
  return sum;
}
vector<vec> trans;
vector<ldb> in_prod;
il void init(const mat &todo) {
  int n = todo.size();
  trans.resize(n), in_prod.resize(n);
  trans[0] = todo[0], in_prod[0] = inner(trans[0], trans[0]);
  For(i, 1, n - 1) {
    trans[i] = todo[i];
    For(j, 0, i - 1) {
      ldb mu = inner(todo[i], trans[j]) / in_prod[j];
      do_sub(trans[i], mul(mu, trans[j]));
    }
    in_prod[i] = inner(trans[i], trans[i]);
  }
}
il void reduction(mat &todo) {
  int n = todo.size();
  For(i, 1, n - 1) {
    ForDown(j, i - 1, 0) {
      ldb mu = inner(todo[i], trans[j]) / in_prod[j];
      do_sub(todo[i], mul(round(mu), todo[j]));
    }
  }
}
il bool swap(mat &todo, ldb dlt) {
  int n = todo.size();
  For(i, 0, n - 2) {
    ldb val1 = dlt * sq_mod(trans[i]);
    ldb mu = inner(todo[i + 1], trans[i]) / in_prod[i];
    ldb val2 = sq_mod(trans[i + 1]) + sq(mu) * sq_mod(trans[i]);
    if (val1 > val2 + eps) {
      swap(todo[i], todo[i + 1]);
      return 1;
    }
  }
  return 0;
}
il void solve(mat &todo, ldb dlt) {
  for (auto iter = 0;; iter++) {
    if (iter % 100 == 0)
      cerr << "iteration #" << iter << '\n';
    bool flg = (init(todo), reduction(todo), swap(todo, dlt));
    if (!flg)
      break;
  }
}
} // namespace LLL
il vector<pair<string, string>> hashBuster(vector<pii> info,
                                           const int M = 64) { // (base, mod)
  auto solve = [&](int len) {
    int sz = len + info.size();
    vector<ll> Pw(info.size(), 1);
    LLL::mat matrix(sz);
    for_each(matrix.begin(), matrix.end(), [&](auto &x) { x.resize(sz); });
    For(i, 0, len - 1) {
      matrix[i][i] = 1;
      For(j, 0, signed(info.size()) - 1) {
        matrix[i][len + j] = Pw[j] * M;
        (Pw[j] *= info[j].fi) %= info[j].se;
      }
    }
    For(i, len, len + signed(info.size()) - 1) {
      matrix[i][i] = 1ll * info[i - len].se * M;
    }
    LLL::solve(matrix, 0.25 + qpow(0.75, sz / (sz - 1)));
    auto check = [&](const auto &qwq) -> bool {
      if (abs(qwq.back()) > LLL::eps)
        return false;
      int u = qwq.size();
      For(i, 0, u - 2) if (fabsl(qwq[i]) >= 26.0) return 0;
      return 1;
    };
    auto build = [&](const auto &qwq) {
      mt19937 rnd(random_device{}());
      auto getChar = [&](ll dlt) {
        assert(abs(dlt) < 26);
        int L = max(0ll, -dlt);
        int R = min(25ll, 25ll - dlt);
        uniform_int_distribution<int> intDist(L, R);
        char pre = 'a' + intDist(rnd), nxt = pre + dlt;
        if (pre < 'a' || nxt > 'z')
          cerr << dlt << '\n';
        return mkp(pre, nxt);
      };
      int u = qwq.size();
      string A = "", B = "";
      For(i, 0, u - 2) {
        auto [x, y] = getChar(qwq[i]);
        A += x;
        B += y;
      }
      reverse(A.begin(), A.end());
      reverse(B.begin(), B.end());
      return mkp(A, B);
    };
    vector<pair<string, string>> ans;
    for (auto qwq : matrix) {
      if (check(qwq)) {
        ans.emplace_back(build(qwq));
      }
    }
    return ans;
  };
  for (auto len = 8; len <= 512; len <<= 1) {
    cerr << "Running on len = " << len << '\n';
    auto ans = solve(len);
    if (!ans.empty())
      return ans;
  }
  return {};
}

对于以下常用 base-mod 组合：

23 998244353
31 99824353
37 1000000007
29 998244853
41 1000000009

这份程序在 5.5s 左右给出了一车碰撞数据：

placnubsftmnlublhlyijnynybdtmbjqxbmm placiapjfzrtikhjhmyilevkvcjxpcdwpeik
oeqsggljwxrjqfpfjqlpohqzdwjhiukdwali oeqsqobjswkokexhlokrvgoqhtfajwrtgmzc
laxcnmkmdmvityzfrblxhhaijleonxeiltus laxcjniumkobjsiohckoboislqgmsyadmibk
mparsgbuotdhnrukdksydgapvkftqxnzkior mparwtfzmkmrfkfkewonblbopwctquzusdlz
rhbhetirigmiwbcthojhnkxrggonkkdbmqwv rhbhjrqddxgzybfimrdefmljejvjkoromruo
qnrpzlhzctpqtzlbroqolnbtyjgeokgsfdkl qnrpxfswhblreclmejsknnmyilqllkkdkgam
oumkqcqovrrgaikxmkefzfvnlpcomiynanku oumkqozvnrifhjwkidkrkewnaukmfjskykgx
cbondiupkyejwkvpecuodgywawdhpsacgrpw cbonllqlmxitsxmdlvmjoenwfrbfxuvsayjk
ekgtckudhvhkjjleqcivknxaqxqnnfmjtair ekgtnufkralukeulmrfnocnfdomrmezipfvu
ynaxdmfwqyabxottfixfzmawrphgwgnhveen ynaxfrmhpuftwkyzbfzbrcgrlkcnofkvboeu
alsdusdwmjzikqeqzussjtrbywxbvkreriuo alsdznsnnvsnrodhrpuoatilhuwrsldfpcph
ovpdwhxrqpsafgvebflnxcfmhfpixcbumonc ovpdqfupqcsmvkyqeiunnhqygafanbkktfql
tdcrrteeexjjlyovpbucccrwhpcqhzaaoqtu tdcrjkjgjlqexucsuouhhopsrubmfzuirkpr
ntcrvaucnnhvegvgtxqlyodcyidygarqzxop ntcroquppsoyaimxdtrkrifsnoexfbdruihy
mzjhglhqtzcjjwdqocpvuyaswwlmviglphbh mzjhnfekvhdzjietwgmstiagmglypgqiaqaq
hzmfhbqdtlfsvmrisycfodwoekebjautjknc hzmfinvcmnnppnxincmhndypppiceanksyph
asleowksxbfxnjknhvrazpbqocjeexinqowt asleqltfpiguuvhdamehxuinpgphfxdmugjk
qsoiagnkkojwekqpbwohudygmjoqjvzugtia qsoibfnphzhwcetbjkobuapjkbeziximrrjn
wbupltoqiqmizzdrzxrocmzqilclokacyeqw wbupkfmzkbkeuokzzyhknjnvgncgnfebxjlo
vbfhcqaqnbhijqmmbgthogovoqnxgdaxbxlp vbfhbefvpfrvtsqtaqupocltmhpymmozbndz
vrdyeynapnjlormjrqcxlpsaxowzhrwitteo vrdyktgdxtikovzvzokzuukeprhkhlzimtvs
macvwjisrnbeefftdqxaaugwzuzleepirgnx macvzviohgbfblykfexoppttlnnhbhgcrvmt
cypstymjilxuhfykdpphpyrmbwjaijpkhvnb cypslrvcvwtjlaojdgxmhojgnwpdkihomssa
chludxxmtwmnwgsbpaqiqdawmzftxifntnxm chluhzorqoetlktrqhqkhkgvdxpwrkstviof
teapeglgyimlqqnscvswylmtwtcvogdaolty teappjccwpnpjmguhxdznvtxyxgkaphgkcdv
ilnbrhbwgydhwuylfobxcpambgwmsctgvdiw ilnbfitjbqlxyrsnrnasntekcpxlwduwlqxq
dehgnopbcbfprwhdzmkyakhokdotmhrhkshe dehgybinebezcarlkhdzoehhbsqyzfikluoh
yagleiyqzqvqroqgnnohjqvqkhqiaovvjnfj yaglqfrmxyyamhtoiswtmutdzohddvbofqkn
uvaiphxjeauocneaylktsmxxvnhudrkiwogo uvailnpakttxhuofvmllnhwnsbxjeebvooqv

可见其高效性。