频率分析
频率分析在数学、物理学和信号处理中是一种分解函数、波形、或者信号的频率组成，以获取频谱的方法。
在密码学中，频率分析是指研究字母或者字母组合在文本中出现的频率。应用频率分析可以破解古典密码。
频率分析基于如下原理：在任何一种书面语言中，不同的字母或字母组合出现的频率各不相同。而且，对于以这种语言书写的任意一段文本，都具有大致相同的特征字母分布。比如，在英语中，字母E出现的频率很高，而Z则出现得较少。类似地，ST、NG、TH，以及QU等双字母组合出现的频率非常高，NZ、QJ组合则极少。英语中出现频率最高的12个字母可以简记为“ETAOIN SHRDLU”。在现代标准汉语中，汉字“的”、“不”、“是”出现的频率很高，而汉字“翊”、“谧”、“觑”则出现的较少，见常用国字标准字体表，后三个字属于次常用字。
简单替换密码的频率分析
[编辑]在一个简单的替换密码中，明文中的每一个字母都被另一个字母替换,而且明文中相同的字母在转换为密文时总是被同一个字母所替换。比如，所有的e都会被替换成 X.一个含有大量X的密文消息会向密码破译者暗示X替换e.
一个例子
[编辑]现假设爱丽丝与鲍伯中的伊夫截获了一段密码（列于下方），它使用了一个简单替换密码进行加密：
LIVITCSWPIYVEWHEVSRIQMXLEYVEOIEWHRXEXIPFEMVEWHKVSTYLXZIXLIKIIXPIJVSZEYPERRGERIM WQLMGLMXQERIWGPSRIHMXQEREKIETXMJTPRGEVEKEITREWHEXXLEXXMZITWAWSQWXSWEXTVEPMRXRSJ GSTVRIEYVIEXCVMUIMWERGMIWXMJMGCSMWXSJOMIQXLIVIQIVIXQSVSTWHKPEGARCSXRWIEVSWIIBXV IZMXFSJXLIKEGAEWHEPSWYSWIWIEVXLISXLIVXLIRGEPIRQIVIIBGIIHMWYPFLEVHEWHYPSRRFQMXLE PPXLIECCIEVEWGISJKTVWMRLIHYSPHXLIQIMYLXSJXLIMWRIGXQEROIVFVIZEVAEKPIEWHXEAMWYEPP XLMWYRMWXSGSWRMHIVEXMSWMGSTPHLEVHPFKPEZINTCMXIVJSVLMRSCMWMSWVIRCIGXMWYMX
在这个例子中，大写字母表示密文，小写字母则表示明文（或猜测在这样），而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。姑且让这些假设进行解码，获得以下的（部分）已解密消息。
heVeTCSWPeYVaWHaVSReQMthaYVaOeaWHRtatePFaMVaWHKVSTYhtZetheKeetPeJVSZaYPaRRGaReM WQhMGhMtQaReWGPSReHMtQaRaKeaTtMJTPRGaVaKaeTRaWHatthattMZeTWAWSQWtSWatTVaPMRtRSJ GSTVReaYVeatCVMUeMWaRGMeWtMJMGCSMWtSJOMeQtheVeQeVetQSVSTWHKPaGARCStRWeaVSWeeBtV eZMtFSJtheKaGAaWHaPSWYSWeWeaVtheStheVtheRGaPeRQeVeeBGeeHMWYPFhaVHaWHYPSRRFQMtha PPtheaCCeaVaWGeSJKTVWMRheHYSPHtheQeMYhtSJtheMWReGtQaROeVFVeZaVAaKPeaWHtaAMWYaPP thMWYRMWtSGSWRMHeVatMSWMGSTPHhaVHPFKPaZeNTCMteVJSVhMRSCMWMSWVeRCeGtMWYMt
使用这些初始的猜测，伊夫发现了某些规律，来让她可以确认其猜测，例如"that"。此外，其他规律则建议了进一步的猜测："Rtate"可能是"state"，即R~s。同样，"atthattMZe"可以是"atthattime"，写出M~i及Z~m。而且，"heVe"可能是"here"，给出V~r。再填入本来的密文，获得：
hereTCSWPeYraWHarSseQithaYraOeaWHstatePFairaWHKrSTYhtmetheKeetPeJrSmaYPassGasei WQhiGhitQaseWGPSseHitQasaKeaTtiJTPsGaraKaeTsaWHatthattimeTWAWSQWtSWatTraPistsSJ GSTrseaYreatCriUeiWasGieWtiJiGCSiWtSJOieQthereQeretQSrSTWHKPaGAsCStsWearSWeeBtr emitFSJtheKaGAaWHaPSWYSWeWeartheStherthesGaPesQereeBGeeHiWYPFharHaWHYPSssFQitha PPtheaCCearaWGeSJKTrWisheHYSPHtheQeiYhtSJtheiWseGtQasOerFremarAaKPeaWHtaAiWYaPP thiWYsiWtSGSWsiHeratiSWiGSTPHharHPFKPameNTCiterJSrhisSCiWiSWresCeGtiWYit
反过来，这些猜测还建议一些例子（例如"remarA"可能是"remark"，即A~k）。接着，相对简单地就可推断出其余字母，最终产生明文：
hereuponlegrandarosewithagraveandstatelyairandbroughtmethebeetlefromaglasscasei nwhichitwasencloseditwasabeautifulscarabaeusandatthattimeunknowntonaturalistsof courseagreatprizeinascientificpointofviewthereweretworoundblackspotsnearoneextr emityofthebackandalongoneneartheotherthescaleswereexceedinglyhardandglossywitha lltheappearanceofburnishedgoldtheweightoftheinsectwasveryremarkableandtakingall thingsintoconsiderationicouldhardlyblamejupiterforhisopinionrespectingit
到了此时，伊夫便可以加上空格及标点符号：
Hereupon Legrand arose, with a grave and stately air, and brought me the beetle from a glass case in which it was enclosed. It was a beautiful scarabaeus, and, at that time, unknown to naturalists—of course a great prize in a scientific point of view. There were two round black spots near one extremity of the back, and a long one near the other. The scales were exceedingly hard and glossy, with all the appearance of burnished gold. The weight of the insect was very remarkable, and, taking all things into consideration, I could hardly blame Jupiter for his opinion respecting it.
其实这个例子是来自金甲虫，正好伊夫的猜测全部正确。这并非总是如此，个别明文中的统计资料变化可能意味着最初的猜测并不正确。这样可能就要做回溯法来更正错误或进一步推测。
明文中没有表现出预期的字母频率分布也有可能。越短的消息越会表现出其更多的变化。明文本来就是经过人为扭曲的文本，例如整篇明文没有了一些字母，通常会是最常见的“e”，这样就称为漏字文。
历史和应用
[编辑]
第一个已知频率分析（事实上，是任何一种密码分析）的解释是在9世纪时，阿拉伯博学家肯迪所著的《手稿上破译加密消息》之上。[1] 它对于古兰经的文本研究发现阿拉伯文有一个特别的字母频率。其使用快速蔓延，类似的系统在文艺复兴时期的欧洲国家十分流行。1474年，西科·西蒙内塔写了一本手册，上有关于破译已加密的拉丁语和意大利语文本。[2]
密码学家为加强简单替换加密，使用了数项措施，包括：
- 使用“谐音替换法” - 使用某几个不太常用的字母替代最常见的字母（例如，在英语密文中，X和Y都可以代表明文E）；
- 使用“多字母替换加密” - 使用另一组文字作密钱来加密密钥 - 参见多字母替换加密(莱昂·巴蒂斯塔·阿尔伯蒂可能是第一个这样做的人）；及
- 使用“表格式替换加密”，为每对字母进行加密，而非每个字母。例子为波雷费密码。
所有这些抵御频率分析攻击的尝试都有一个缺点：它增加了加密和解密的难度，可能导致使用失误。而最著名的的事件如下：最初英国外交部拒绝使用波雷费密码，认为它太复杂。当惠斯登证明邻近学校的四个男孩中，有三个可以在15分钟内学会这种方法，外交部副秘书长的回应是：“这是有可能的，可惜你不能教晓那些高层人员。”
20世纪首50年，旋转盘的使用兴起（例如，恩尼格玛密码机），其基本上不会受到直接频率分析攻击。然而，其他种类的分析成功解译了其中一些信息（其中最著名为Ultra计划）。
频率分析只需基本了解明文字母的统计，以及一些解决问题的能力，而且此方法可用人手解译。在第二次世界大战期间，英国与美国同时使用各大报纸上字谜和密码比赛来招募解码专家。轴心国中使用了某些很容易遭频率分析破解的密码（例如日本第二次世界大战时的领事密码）。机械替换加密或解密亦于第二次世界大战之时开始使用。现时，频率分析基本上全由电脑来完成，因此，现时替换式密码很容易就被破解。
小说中的频率分析
[编辑]阿瑟·柯南·道尔所写的侦探小说《福尔摩斯‧归来记》中《跳舞的人》篇中，福尔摩斯就在墙上看到五个跳舞人的画，他从英语用语对答的常用性与英语使用频率最高的字母E猜出了其中一次跳舞人画所代表的字为Never，从而破解了字谜。
参考文献
[编辑]引用
[编辑]- ^ Ibrahim A. Al-Kadi‧《密码学的起源：阿拉伯国家的贡献》，Cryptologia （页面存档备份，存于互联网档案馆）, 16(2) (1992年4月) pp. 97–126.
- ^ Kahn, David L. 密碼破譯者：加密的故事. 纽约: Scribner. 1996. ISBN 0-684-83130-9.
书籍
[编辑]- Helen Fouché Gaines, "Cryptanalysis", 1939, Dover. ISBN 978-0-486-20097-2
- Ibraham A. “Al-Kindi: The origins of cryptology: The Arab contributions”, Cryptologia, 16(2) (April 1992) pp. 97–126.
- Abraham Sinkov, "Elementary Cryptanalysis : A Mathematical Approach", The Mathematical Association of America, 1966. ISBN 978-0-88385-622-2.
