当密码学遇上统计学

标题取的很大，主要是为了将文章上升到科学的层次，而不仅仅是某一项具体的应用。

本文简述卡方统计量的思想，及其在Caesar加密破解中的应用。

Caesar 加密，将每个字母用其在字母表之后的某个位置的字母代替，比如用d代替a， e代替b，f代替c，对于z，用c代替。1 如果将a, b, c, ..., z 从0开始编号，这种替换的过程，可以看成是字母的循环右移（或者左移）。在古典加密中，这个位置参数是保密的，如果被第三方知道，密文也就随之破解。

320px-Caesar3.svg.png

比如每个字母右移12位，将 "All models are wrong, but some are useful."通过Caesar加密，得到如下密文：
"Mxx yapqxe mdq idazs, ngf eayq mdq geqrgx."

加密后的文本不可读，但若得到位置信息，即可将每个字母左移12位，即可得到原文。如果不知道这个位置信息，就需要暴力穷举，对于Caesar加密而言，只有25种情况（因为看到的密文已经是一种），这适合用计算来解决。

再进一步论述之前，需要说说英语本身的一种特性。在英语中，每个字母出现的频次是不一样的，有的很高，有的很少出现，比如字母e经常出现，而字母z则很少出现。理论上，可以得到每个字母的出现百分比。

a	b	c	d	e	f	g	h	i	j	k	l	m
8.2	1.5	2.8	4.3	12.7	2.2	2	6.1	7	0.2	0.8	4	2.4

n	o	p	q	r	s	t	u	v	w	x	y	z
6.7	7.5	1.9	0.1	6	6.3	9.1	2.8	1	2.4	0.2	2	0.1

对于Caesar加密，虽然字母被映射成别的字母，但是也将相应字母的出现频率映射给新的字母，比如出现几率最高的e，如果被映射成h，则在Caesar加密后，统计词频，可以发现h的出现几率最高。对于其他的字母，有类似的情况。这也为通过词频破解Caesar加密提供了思路。

对于一段密文，左移（或者右移），然后统计其词频，并与标准的英语字母词频做比较。若移动的位数正好是Caesar加密所使用的位数，则每个字母的词频与标准英语字母的词频比较接近，否则相差应该较大。这种差异可以通过卡方统计量来刻画，

对于26个字母，在标准英语下，每个字母具有比例$\pi_{1i}$，其中$i = 1, 2, 3, .., 26$；对于待解密的文本，某次移动后，每个字母的出现频率为$\pi_{2i}$，其中$i = 1, 2, 3, ..., 26$。

可以构建极大似然统计量，当文本较多时，可以等价地构建皮尔逊卡方统计量。[2][]

$$\chi^2 = n\sum_{i = 1} ^{26} \frac{ (\pi_{2i} - \pi_{1i})^2 } { \pi_{1i} }$$

其中$n$是带解密文本中字母的个数。如果$\pi_{2i}$与$\pi_{1i}$一致，则该统计量较小，否则该统计量较大。也就是说卡方统计量的大小衡量移位后词频与标准词频之间的匹配程度。对于Caesar加密，穷举所有可能的移位，计算其对应的卡方统计量，其最小值对应的文本，很有可能是正确解密的文本。由于对于一段固定的密文，$n$是常数，故可在计算中忽略不计。

$$\chi^2 = \sum_{i = 1} ^{26} \frac{ (\pi_{2i} - \pi_{1i})^2 } { \pi_{1i} }$$

[2]: John A. Rice, 数理统计与数据分析, page 263.