频率分析法

    以前讲过凯撒密码是一种移位加密，密钥就是平移的字母的个数。由于字母表只有26个字母，因此加密用的密钥只有0到25共26种（密钥为0相当于没有加密），因此凯撒密码可以通过暴力破解来破译。暴力破解是指将所有可能的密钥全部尝试一遍，又称为穷举搜索。

    而简单替换密码很难通过暴力破解来破译。这是因为简单替换密码可以使用的密钥数量比凯撒密码要多得多。简单替换密码中，明文a可以对应A~Z这26个字母的任意一个，b可以对应除a对应的字母以外的剩余25个字母中的任意一个。以此类推，简单替换密码的密钥总数为：

26*25*24*23*…*1= 403291461126605635584000000

这么庞大的数字，如果用暴力破解，即使每秒能够遍历10亿个密钥，要遍历完也需要120亿年。

    因为破译困难，从公元前开始，简单替换密码在几百年的时间里一直被用于秘密通信。然而在阿拉伯学者发明了频率分析法之后，这种密码就可以被破译了。频率分析法利用了明文中字母的出现频率与密文中字母出现的频率一致这一特性。有以下分析方法：

1、英语中出现频率最高的字母是e，假定密文中出现频率最高的字母是e

2、 英语中出现最多的单词是The

3、 英语文章中9个最常用的字母是e，t，a，o，n，i，r，s, h

4、英语单词中有一半以上是以t，a，o，s或w开头的

5、 仅10个单词（the，of，and，to，a，in，that，it，is和I）就构成标准英语文章四分之一以上的篇幅

6、 密文越长越容易破译。

【案例分析】

    我们以小说《金甲虫》中藏宝图上的密码为例，使用频率分析法进行破译：

53§§+305))6*;4826)4§．)4§);806*;48+8β60))85;;］8*;:§*8+83(88)5*+;46(;88*96*?;8)*§(;485);5*+2:*§(;4956*2(5*-4)8β8*;4069285);)6+8)4§§;;1(§9;48081;8:8§1;48+85;4)485+528806*81(§9;48;(88;4(§?34;48)4§;161;:188;§?;

    首先，我们统计一下这段密文中每个符号出现的频率，排出前几位的符号：

    一般英语文章中出现频率最高的字母是e，该段密文中出现频率最高的符号是8，我们假设8->e，将密文中的8全部替换，替换后的密文如下：

53§§+305))6*;4e26)4§．)4§);e06*;4e+eβ60))e5;;］e*;:§*e+e3(ee)5*+;46(;ee*96*?;e)*§(;4e5);5*+2:*§(;4956*2(5*-4)eβe*;40692e5);)6+e)4§§;1(§9;4e0e1;e:e§1;4e+e5;4)4e5+52ee06*e1(§9;4e;(ee;4(§?34;4e)4§;161;:1ee;§?;

    英语中出现最多的单词是the，我们寻找一下以e结尾的3个字符组合，发现;4e这3个字符的组合是最常出现的，很有可能就是the。于是我们假设;->t，4->h，而且;->t也符合t出现频率较高的规则：

53§§+305))6*the26)h§．)h§)te06*the+eβ60))e5tt］e*t:§*e+e3(ee)5*+th6(tee*96*?te)*§(the5)t5*+2:*§(th956*2(5*-h)eβe*th0692e5)t)6+e)h§§t1(§9the0e1te:e§1the+e5th)he5+52ee06*e1(§9thet(eeth(§?3hthe)h§t161t:1eet§?t

    我们发现中间有一些词比较可疑：thet(ee可能是the tree吧，尝试(->r：

53§§+305))6*the26)h§．)h§)te06*the+eβ60))e5tt］e*t:§*e+e3ree)5*+th6rtee*96*?te)*§rthe5)t5*+2:*§rth956*2r5*-h)eβe*th0692e5)t)6+e)h§§t1r§9the0e1te:e§1the+e5th)he5+52ee06*e1r§9thetreethr§?3hthe)h§t161t:1eet§?t

    th6rtee*很难不联想到thirteen，假设6->i，*->n：

53§§+305))inthe2i)h§．)h§)te0inthe+eβi0))e5tt］ent:§ne+e3ree)5n+thirteen9in?te)n§rthe5)t5n+2:n§rth95in2r5n-h)eβenth0i92e5)t)i+e)h§§t1r§9the0e1te:e§1the+e5th)he5+52ee0ine1r§9thetreethr§?3hthe)h§t1i1t:1eet§?t

    thetreethr§?3hthe这个组合，可能是the tree through the，§->o，?->u，3->g：

5goo+g05))inthe2i)ho．)ho)te0inthe+eβi0))e5tt］ent:one+egree)5n+thirteen9inute)northe5)t5n+2:north95in2r5n-h)eβenth0i92e5)t)i+e)hoot1ro9the0e1te:eo1the+e5th)he5+52ee0ine1ro9thetreethroughthe)hot1i1t:1eetout

    为了方便查看，对已识别的单词加入空格：

5goo+g05)) in the 2i)ho．)ho)te0 in the +eβi0))e5tt］ent:one+egree)5n+ thirteen 9inute)northe5)t5n+2:north95in2r5n-h)eβenth0i92e5)t)i+e)hoot1ro9the0e1te:eo1the+e5th)he5+52ee0ine1ro9the tree through the )hot1i1t:1eet out

    9inute)可能是minutes，thirteen minutes也说得通，9->m，)->s

5goo+g05ssin the 2isho.shoste0 in the +eβi0sse5tt]ent:one+egrees5n+thirteen minutes northe5st5n+2:northm5in2r5n-hseβenth0im2e5stsi+eshoot1romthe0e1te:eo1the+e5thshe5+52ee0ine1romthe tree through the shot1i1t:1eet out

    发现有一组是northe5st5nd，northe5st可能是northeast；5n+多次出现，可能是一个单词；而且高频字母中的a还没有找到对应的字符，5也在高频符号中，假设5->a，+->d：

A good g0assin the 2isho．shoste0 in the deβi0sseatt]ent:one degrees and thirteen minutes northeast and 2:northmain2ran-hseβenth0im2east side shoot 1rom the 0e1te:eo1 the deathsheada2ee0ine1romthe tree through the shot 1i1t:1eet out

    g0ass可能是grass,glass，由于前面假设(->r，所以这里0-l：

a good glass in the 2isho.shostel in the deβilsseatt]ent:one degrees and thirteen minutes northeast and 2: north main 2ran-hseβenthlim2east side shoot 1rom the le1te:eo1 the deaths head a2eeline1romthe tree through the shot1i1t:1eet out

    1rom可能是from，1-f：

A good glassin the 2isho.s hostel in the deβilsseatt]ent: one degreesand thirteen minutes  northeast and 2: northmain 2ran-hseβenthlim2east side shoot from the left e:eofthe deathsheada2eeline from the tree through the shot fift:feet out

    fift:feet可能是fiftyfeet，:->y：

A good glassin the 2isho.s hostel in the deβilsseatt]enty one degreesand thirteen minutes northeast and 2y north main 2ran-hseβenthlim2eastside shoot from the left eye of the deathsheada2eeline from the tree through theshot fifty feet out

    2y应该是by，2->b：

A good glassin the bisho.s hostel in the deβilsseatt]enty one degreesand thirteen minutes northeast and by north main bran-hseβenthlimb east side shoot from the left eye of the death's head a beeline from the treethrough the shot fifty feet out

    bisho.s应该是bishops；bran-h应该是branch，seβenth应该是seventh，所以.->p，- ->c，β->v：

A good glassin the bishop's hostel in the devil's seat t]enty one degrees and thirteen minutesnortheast and by north main branch seventh limb east side shoot from the left eyeof the death's head a beeline from the tree through the shot fifty feet out

    最后]对应到w：

A good glassin the bishop's hostel in the devil's seat twenty-one degrees and thirteen minutesnortheast and by north main branch seventh limb east side shoot from the left eyeof the death's head a beeline from the tree through the shot fifty feet out.

    中文翻译如下：

一面好镜子在皮肖甫客店魔椅──二十一度十三分──东北偏北──最大树枝第七根桠枝东面──从骷髅头左眼射击──从树前引一直线距线通过子弹延伸五十英尺。