哈希

我们定义一个把字符串映射到整数的函数 ff，这个 ff 称为是 Hash 函数，我们希望这个函数 ff 可以方便地帮我们判断两个字符串是否相等，这就是哈希。

一般来说，哈希值都是使用 hashi=(base⋅hashi−1+si)%modhash_i=(base\cdot hash_{i-1} +s_i)\%mod 这个转移方程得到的。

在这个转移方程中，ss 为字符串，basebase 被称为底数，而 modmod 被称为模数。

生日悖论

如果一个班级有 2323 个人, 那么其中有两个人生日相同的概率超过 50%50\%。因为这与自己的直觉相不符，所以被称为生日悖论。

其实出现这样问题的原因是并没有将“两个人的生日相同”和“有人和自己的生日相同”很好的区分开。

定义两人生日重复的情况叫同生缘。

假设一年有 NN 天，那么不发生同生缘的概率可以写作：

1−P=∏i=1n−1(1−iN)1-P=\prod_{i=1}^{n-1} (1-\frac{i}{N})

当 n≤Nn\le N 时，因为 (1−1N)n≈1−nN(1-\frac{1}{N})^n\approx 1-\frac{n}{N}，所以

1−P≈∏i=1n−1(1−1N)i=(1−1N)n⋅(n−1)21-P\approx \prod_{i=1}^{n-1}(1-\frac{1}{N})^i =(1-\frac{1}{N})^{\frac{n\cdot(n-1)}{2}}

P=1−(1−1N)n⋅(n−1)2P=1-(1-\frac{1}{N})^{\frac{n\cdot(n-1)}{2}}

当 N=365N=365 时，函数图像可点击此链接查看。

可以观察到，在 n=23n=23 时 PP 已经接近了 50%50\%。

卡大质数哈希

假设模数为 109+710^9+7，构造一个长度为 10510^5 的字符串。

将这个数据带入上方函数，得到成功让字符串哈希冲突的概率为 P=0.993261715159P=0.993261715159。

所以直接使用随机构造的方式，在一般情况下就可以将其 hack。

#include<bits/stdc++.h>
using namespace std;
int main(){
    printf("100000 20\n");
    for(int i = 1;i <= 100000;i++){
        putchar(rand() % 26 + 'a');
    }
    return 0;
}

自然溢出

自然溢出，即 hash 数组使用 unsigned long long，也就是对于 2642^{64} 取模。不光其值域不难出现哈希冲突，而且代码长度与常数都会大大减小，得到了不少的同学的青睐。

将 N=264,n=105N=2^{64},n=10^5 带入上面的函数后，我们发现出现哈希冲突的可能性 PP 无限接近与 00，所以使用生日攻击成功的可能性极小。

底数为偶数

可以构造全部为 a\texttt{a} 的子串和第一个为 b\texttt{b} 其余均为 a\texttt{a} 的两个长度相等且长苏大于 6464 的两个不一样的字符串。

因为底数的 6464 次方以上模 2642^{64} 都是 00，所以即是两个字符串不同，他们的哈希值也都会一样。

底数为奇数

设一些串 ss，sis_i 表示第 ii 个串，sis_i 的哈希值为 hash(si)hash(s_i)。

定义 f(s)f(s) 为字符串 ss 内全部的 a\texttt{a} 都变为 b\texttt{b}，所有的 b\texttt{b} 都变成 a\texttt{a}。

定义 si+sjs_i+s_j 的意思为将 sjs_j 添加到 sis_i 的末尾形成的新的字符串。

构造方法为：s1=as_1=\texttt{a}，si=si−1+f(si−1)s_i=s_{i-1}+f(s_{i-1})，所以 ∣si∣=2i−1|s_i|=2^{i-1}。

所以：

hash(si)=hash(si−1)⋅base∣si−1∣+hash(f(si−1))=hash(si−1)⋅base2i−2+hash(f(si−1))hash(s_i)=hash(s_{i-1})\cdot base^{|s_{i-1}|}+hash(f(s_{i-1}))=hash(s_{i-1})\cdot base^{2^{i-2}}+hash(f(s_{i-1}))

hash(f(si−1))=hash(f(si−2))⋅base2i−2+hash(si−1)hash(f(s_{i-1}))=hash(f(s_{i-2}))\cdot base^{2^{i-2}}+hash(s_{i-1})

hash(si)−hash(f(si−1))=(hash(si−1)−hash(f(si−2)))⋅base2i−2−(hash(si−1)−hash(f(si−2)))hash(s_i)-hash(f(s_{i-1}))=(hash(s_{i-1})-hash(f(s_{i-2})))\cdot base^{2^{i-2}}-(hash(s_{i-1})-hash(f(s_{i-2})))

hash(si)−hash(f(si−1))=(hash(si−1)−hash(f(si−2)))⋅(base2i−2−1)hash(s_i)-hash(f(s_{i-1}))=(hash(s_{i-1})-hash(f(s_{i-2})))\cdot (base^{2^{i-2}}-1)

因为希望产生哈希冲突，即 264∣hash(si)−hash(f(si))2^{64}\mid hash(s_i)-hash(f(s_i))。

设 gig_i 表示 hash(si)−hash(f(si))hash(s_i)-hash(f(s_i))，那么 gg 满足一下性质：

gi=gi−1⋅(basei−2−1)g_i=g_{i-1}\cdot (base^{i-2}-1)

因为每一个 base2i−1−1base^{2^{i-1}}-1 都是偶数，所以是的 gg 到达第 6464 项就可以 hack 了。

因为 base2i−1−1=(base2i−2−1)⋅(base2i−2+1)base^{2^{i-1}}-1=(base^{2^{i-2}}-1)\cdot(base^{2^{i-2}}+1) 且为一个偶数乘一个偶数, 而左边的可以继续递归下去, 所以到第 1212 位其实就可以 hack 了。

#include <iostream>
#include <cstring>
using namespace std;
char s[10000];
int main(){
	cout<<(1<<12)+65<<' '<<(1<<11)<<'\n';
	int now=1;
	s[1]='a';
	for (int i=1;i<=12;i++){
		for (int j=1;j<=now;j++) s[now+j]=s[j]=='a'?'b':'a';
		now<<=1;
	}
	for (int i=1;i<=now;i++) printf("%c",s[i]);
	for (int i=1;i<=65;i++) putchar('a');
	return 0;
}

参考文章 博客园