频率分析

频率分析在数学、物理学和信号处理中是一种分解函数、波形、或者信号的频率组成，以获取频谱的方法。在密码学中，频率分析是指研究字母或者字母组合在文本中出现的频率。应用频率分析可以破解古典密码。频率分析基于如下原理：在任何一种书面语言中，不同的字母或字母组合出现的频率各不相同。而且，对于以这种语言书写的任意一段文本，都具有大致相同的特征字母分布。比如，在英语中，字母E出现的频率很高，而X则出现得较少。类似地，ST、NG、TH，以及QU等双字母组合出现的频率非常高，NZ、QJ组合则极少。英语中出现频率最高的12个字母可以简记为“ETAOIN SHRDLU”。在一个简单的替换密码中，明文中的每一个字母都被另一个字母替换,而且明文中相同的字母在转换为密文时总是被同一个字母所替换。比如，所有的e都会被替换成 X.一个含有大量X的密文消息会向密码破译者暗示X替换e.现假设爱丽丝与鲍伯中的伊夫截获了一段密码（列于下方），它使用了一个简单替换密码进行加密：在这个例子中，大写字母表示密文，小写字母则表示明文（或猜测在这样），而X~t用来代表一个关于：密文X 代表明文t的猜测。伊夫可以使用频率分析，以下面的消息来帮助解决密文大意：单字母中I最为常见；XL是最为常见的双字母组；而XLI则为最为常见的三字母组，且密文中找不到D。根据英文的字母分布，e是最常见的单字母，th是最为常见的双字母组，而the则为最为常见的三字母组。因些她猜测X~t、L~h及I~e。第二个密文中最常见的字母是E；t是英文中第二常见的字母，因此应该是E~t，但由于已假设X~t，所以伊夫暂且假设E~a。姑且让这些假设进行解码，获得以下的（部分）已解密消息。使用这些初始的猜测，伊夫发现了某些规律，来让她可以确认其猜测，例如"that"。此外，其他规律则建议了进一步的猜测："Rtate"可能是"state"，即R~s。同样，"atthattMZe"可以是"atthattime"，写出M~i及Z~m。而且，"heVe"可能是"here"，给出V~r。再填入本来的密文，获得：反过来，这些猜测还建议一些例子（例如"remarA"可能是"remark"，即A~k）。接着，相对简单地就可推断出其余字母，最终产生明文：到了此时，伊夫便可以加上空格及标点符号：其实这个例子是来自金甲虫，正好伊夫的猜测全部正确。这并非总是如此，个别明文中的统计资料变化可能意味着最初的猜测并不正确。这样可能就要做回溯法来更正错误或进一步推测。明文中没有表现出预期的字母频率分布也有可能。越短的消息越会表现出其更多的变化。明文本来就是经过人为扭曲的文本，例如整篇明文没有了一些字母，通常会是最常见的“e”，这样就称为漏字文。第一个已知频率分析（事实上，是任何一种密码分析）的解释是在9世纪时，阿拉伯博学家－肯迪所著的《手稿上破译加密消息》之上。 它对于古兰经的文本研究发现阿拉伯文有一个特别的字母频率。其使用快速蔓延，类似的系统在文艺复兴时期的欧洲国家十分流行。1474年，Cicco Simonetta 写了一本手册，上有关于破译已加密的拉丁语和意大利语文本。密码学家为加强简单替换加密，使用了数项措施，包括：所有这些抵御频率分析攻击的尝试都有一个缺点：它增加了加密和解密的难度，可能导致使用失误。而最著名的的事件如下：最初英国外交部拒绝使用波雷费密码，认为它太复杂。当惠斯登证明邻近学校的四个男孩中，有三个可以在15分钟内学会这种方法，外交部副秘书长的回应是：“这是有可能的，可惜你不能教晓那些高层人员。”20世纪首50年，旋转盘的使用兴起（例如，恩尼格玛密码机），其基本上不会受到直接频率分析攻击。然而，其他种类的分析成功解译了其中一些信息（其中最著名为Ultra计划）。频率分析只需基本了解明文字母的统计，以及一些解决问题的能力，而且此方法可用人手解译。在第二次世界大战期间，英国与美国同时使用各大报纸上字谜和密码比赛来招募解码专家。轴心国中使用了某些很容易遭频率分析破解的密码（例如日本第二次世界大战时的领事密码）。机械替换加密或解密亦于第二次世界大战之时开始使用。现时，频率分析基本上全由电脑来完成，因此，现时替换式密码很容易就被破解。柯南‧道尔所写的侦探小说《福尔摩斯‧归来记》中《跳舞的人》篇中，福尔摩斯就在墙上看到五个跳舞人的画，他从英语用语对答的常用性与英语使用频率最高的字母E猜出了其中一次跳舞人画所代表的字为Never，从而破解了字谜。爱伦坡的《金甲虫》亦是一小说有密文的例子。