密码分析

密码分析和密码学是共同演化的。这从密码学史中可以看得很明显。总是有新的密码机被设计出来并取代已经被破解的设计，同时也总是有新的密码分析方法被发明出来以破解那些改进了的方案。事实上，密码和密码分析是同一枚硬币的正反两面：为了创建安全的密码，就必须考虑到可能的密码分析。

经典密码分析

尽管“密码分析”这个词是晚近出现的（1920年由William Friedman（英语：William_Friedman）确立），但破解密码和密码机的方法却由来已久。世界上最早的破解密码方法的文字记录可以追溯到九世纪阿拉伯通才肯迪所著《破解密码信息》（A Manuscript on Deciphering Cryptographic Messages），这篇文章论述了一个频率分析的方法。

频率分析是破解经典密码的一个基本方法。在自然语言里，字母表里的有些字母比其它的字母出现得更频繁。例如，在英语里，字母E很有可能是在任何文字样本里出现频率都最高的字母。同样的，TH这两个字母连起来是最有可能出现的字母对。频率分析法假设密码没有隐藏这样的统计信息。例如，在简单的替换密码中，每个字母只是简单地被替换成另一个字母，那么在密文中出现频率最高的字母就最有可能是E。

频率分析法除了需要用到统计学外，也需要用到语言学。但随着密码算法的日渐复杂，密码分析也渐渐变得主要依赖数学方法。这个改变在第二次世界大战时最为明显。那时，为了破解轴心国的密码，需要发展更加复杂的数学方法。而且，自动计算也头一次被应用到密码分析中，如密码炸弹（英语：Bomba_(cryptography)）以及最早的计算机之一，巨人计算机。

现代密码分析

尽管第二次世界大战时计算机的运用使得密码分析更加容易，这同时也使得新的密码学方案的复杂程度上升了好几个数量级。总体来说，破解密码在现代比起只用纸和笔的年代来说要困难得多了。现在看来，似乎密码学对纯密码分析来说已经占了上风。美国历史学家卡恩（David Kahn（英语：David_Kahn））在2002年这样说道：“今天，由数百个商家提供的很多密码系统都不能被已知的密码分析方法来破解。确实，在这样的密码系统中，即使用选择明文攻击，也就是攻击者可以选择明文并比对相应的密文，也不能找出可以用来解开其它加密信息的钥匙。从某种意义上来说，密码分析已经死了。但是，故事还没有结束。密码分析也许是死了，但是，打个不恰当的比方，其实条条大道通罗马。”（2002年11月1日在美国国家安全局50周年纪念会上的讲话）。卡恩接着又提到，其它的攻击方式的可能性增加了。例如拦截攻击，窃听，侧信道攻击，以及用量子计算机来代替传统计算机做密码分析[1]（页面存档备份，存于互联网档案馆）。

卡恩对于密码分析所作的论断也许还为时过早。不安全的密码并没有绝迹，美国国家情报机构的密码分析方法也没有公开过。在学术界，新的密码在不断地被设计出来，也经常地被破解。1984年，Madryga（英语：Madryga） 分组密码被一种唯密文攻击破解。1998年，原本提出来要取代DES标准加密算法的分组密码 FEAL-4（英语：FEAL），也因为被学术界发现了很多类似而且实际可行的攻击而消亡。在工业界，很多密码也被发现有漏洞。例如，在手机中使用的A5/1，A5/2以及CMEA（英语：CMEA_(cipher)）算法，用一般的计算工具可以在几小时、几分钟内，甚至是实时地被破解。2001年，用来保护无线Wi-Fi网络的有线等效加密协议（或称无线加密协议，即WEP）也可以用相关钥匙攻击来破解。

密码分析的后果

无疑，成功的密码分析影响了历史的进程。能够看懂别人本以为是秘密的想法或计划，这种能力可以成为决定性的优势。在战争期间尤其如此。例如，在第一次世界大战中，成功地破解齐默尔曼电报是促使美国参战的直接原因。在第二次世界大战中，对德国密码的成功破解，包括恩尼格玛密码机（Enigma）和洛仑兹密码机（Lorenz Cipher），其后果从使欧洲战场早几个月结束，到对整个战争起决定性作用，各种说法都有（参见ULTRA（英语：Ultra））。美国也从对日本的PURPLE（英语：PURPLE）密码的密码分析中受益（参见MAGIC（英语：Magic_(cryptography)））。

一些国家的政府很早就已经意识到了密码分析对于情报收集的重要性，不管是对于军事还是外交都一样。这些国家还创建了专门破解密码的机构，如英国政府通信总部（GCHQ），以及美国国家安全局（NSA）。这些机构在当今都非常活跃。2004年，有报道说美国成功破解了伊朗的密码。但这是纯粹的密码分析还是有其它因素，目前还不清楚 [2]（页面存档备份，存于互联网档案馆）。

不同的密码分析攻击有不同的效力，对于实际的密码系统的威胁也不尽相同。有的时候，对于某个密码系统的攻击只是停留在理论上，对于任何实际的密码系统可能并不适用。这就是所谓的“证书式弱点”（certificational weakness）。现代密码分析的学术研究结果大部分都属于这一类。从根本上说，某种攻击方式在实际中的有效性取决于它对于以下几个问题给出的答案：

1. 这个攻击需要何种知识及能力？
2. 通过攻击可获得多少新的秘密信息？
3. 这个攻击需要花多少工夫？（它的计算复杂度为何？）

先验知识：密码分析中的情形

在攻击中，通过观察或研究目标系统，多少会获得关于这个系统的信息。随着能够获得信息多少的假设不同，密码分析的方法也不尽相同。在密码分析中最基本的一点，就是假设攻击者能够知道系统所用的算法。这也就是“敌人了解系统”的所谓柯克霍夫原则。这个假设在实际中是合理的。从古至今，有无数的秘密算法最后终为人所知，而其途径多种多样，包括间谍，叛变，以及逆向工程。在一些不多见的情况下，密码机也能够通过纯粹的推演而被重建。例如德国的洛仑兹密码机（Lorenz Cipher）和日本的PURPLE密码机，以及其它很多经典密码。

另外，通常用攻击模式（英语：Attack_model）来描述攻击者可以获得关于系统信息的方式。攻击模式包括以下几种：

• 唯密文攻击：攻击者仅能获得一些加密过的密文。
• 已知明文攻击：攻击者有一些密文并且知道相对应的明文。
• 选择明文攻击：攻击者在开始攻击之前可以选择一些明文并从系统中获得相对应的密文。如果攻击者在攻击中途可以根据已经获得的信息选择新的明文并获得对应的密文，则称为适应性选择明文攻击。
• 选择密文攻击：攻击者在开始攻击之前可以选择一些密文并从系统中获得相对应的明文。如果攻击者在攻击中途可以根据已经获得的信息选择新的密文并获得对应的明文，则称为适应性选择密文攻击。
• 相关钥匙攻击（英语：Related-key attack）：与选择明文（或密文）攻击类似。不同的是，攻击者可以得到被两个不同的钥匙所加密（或解密）得到的密文（或明文）。攻击者不知道这两个钥匙的数值，但知道这两个钥匙之间的关系，比如两个钥匙之间相差一个比特。

显然，这些不同种类的攻击在实际中可能出现的机会也大不相同。尽管有些攻击比其它的较为常见，密码学家在设计算法时通常会采取保守的方式看待安全问题，总是假设最坏的情形。理由是，如果一个算法连不现实的攻击都可以承受，那么它自然也可以抵抗实际可行的密码分析。

事实上，这些假设虽然初看上去不切实际，但其实不然。例如在已知明文攻击中，密码分析者很有可能能够知道或猜出明文的一部分。比方说，一封加密过的信有可能是以“敬启者”开头，而一个电脑会话则有可能以“用户名：”开头。选择明文攻击在密钥密码中较为少见，但也并非不可能。而在公钥密码中，选择明文攻击人人都可做到，因为加密用的钥匙通常是公开或已知的。相关钥匙攻击通常只是在理论上的讨论，但在实际中也会被用到，例如对WEP的攻击。

成功密码分析的类别

对于密码分析的结果来说，其有用的程度也各有不同。密码学家Lars Knudsen（英语：Lars_Knudsen）于1998年将对于分组密码的攻击按照获得的秘密信息的不同分为以下几类：

• 完全破解 -- 攻击者获得秘密钥匙。
• 全局演绎 -- 攻击者获得一个和加密和解密相当的算法，尽管可能并不知道钥匙。
• 实例（局部）演绎 -- 攻击者获得了一些攻击之前并不知道的明文（或密文）。
• 信息演绎 -- 攻击者获得了一些以前不知道的关于明文或密文的香农信息。
• 分辨算法 -- 攻击者能够区别加密算法和随机排列。

对于其它类型的密码学算法，也可以做出类似的分类。

复杂度

• Ophcrack