密码分析

一门研究对信息进行解密的学问

密码分析（英语：cryptanalysis，来源于希腊语kryptós，即“隐藏”，以及analýein，即“解开”），是一门研究在不知道通常解密所需要的秘密信息的情况下对信息进行解密的学问。通常，这需要寻找一个秘密的钥匙。用不是很正规的话来说，这就是所谓的破解密码。

产品说明

密码分析这个词有时也被用来指广义上的绕开某个密码学算法或密码协议的尝试，而不仅仅是针对加密算法。但是，密码分析通常不包括并非主要针对密码算法或协议的攻击。

虽然密码分析的目标在密码学的历史上从古至今都一样，但是实际使用的方法和技巧则随着密码学变得越来越复杂而日新月异。密码学算法和协议从古代只利用纸笔等工具，发展到第二次世界大战时的恩尼格玛密码机（又称“谜”，德语：Enigma），直到目前的基于电子计算机的方案。而密码分析也随之改变了，无限制地成功破解密码已经不再可能。事实上，只有很少的攻击是实际可行的。在上个世纪70年代中期，公钥密码学作为一个新兴的密码学分支发展起来了，而用来破解这些公钥系统的方法则和以住完全不同，通常需要解决精心构造出来的纯数学问题，其中最著名的就是大数的质因数分解。

经典密码分析

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

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

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

现代密码分析

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

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

密码分析的后果

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

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

成功密码分析的类别

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

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

可将密码分析分为以下五种情形。

（1）惟密文攻击（Ciphertext only）

对于这种形式的密码分析，破译者已知的东西只有两样：加密算法、待破译的密文。

（2）已知明文攻击（Known plaintext）

在已知明文攻击中，破译者已知的东西包括：加密算法和经密钥加密形成的一个或多个明文—密文对，即知道一定数量的密文和对应的明文。

（3）选择明文攻击（Chosen plaintext）

选择明文攻击的破译者除了知道加密算法外，他还可以选定明文消息，并可以知道对应的加密得到的密文，即知道选择的明文和对应的密文。例如，公钥密码体制中，攻击者可以利用公钥加密他任意选定的明文，这种攻击就是选择明文攻击。

（4）选择密文攻击(Chosen ciphertext)

与选择明文攻击相对应，破译者除了知道加密算法外，还包括他自己选定的密文和对应的、已解密的原文，即知道选择的密文和对应的明文。

（5）选择文本攻击（Chosen text）

选择文本攻击是选择明文攻击与选择密文攻击的结合。破译者已知的东西包括：加密算法、由密码破译者选择的明文消息和它对应的密文，以及由密码破译者选择的猜测性密文和它对应的已破译的明文。

很明显，惟密文攻击是最困难的，因为分析者可供利用的信息最少，上述攻击的强度是递增的。一个密码体制是安全的，通常是指在前三种攻击下的安全性，即攻击者一般容易具备进行前三种攻击的条件。