密码分析

密码分析（英语：cryptanalysis，来源于希腊语kryptós，即“隐藏”，以及analýein，即“解开”），是研究在不知道通常解密所需要的秘密资讯的情况下对已加密的资讯进行解密的一门学问。一般情况下，要成功解密需要查找到一个秘密的钥匙，俗称破解密码（破密）。

从广义的角度看，密码分析这个词语有时也泛指绕开某个密码学算法或密码协议的尝试，而不仅仅是针对加密算法。但是，密码分析通常不包括并非主要针对密码算法或协议的攻击。尽管这些攻击方式是电脑安全领域里的重要考虑因素，而且通常比传统的密码分析更加有效。

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

密码分析的历史

主条目：密码学史

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

经典密码分析

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

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

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

现代密码分析

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

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

密码分析的后果

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

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

攻击类型

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

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

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

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

另外，通常用攻击模式来描述攻击者可以获得关于系统资讯的方式。攻击模式包括以下几种：

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

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

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

成功密码分析的类别

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

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

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

非对称密码学的密码分析

非对称密码学是一种使用不同密钥（公开密钥和私有密钥）进行加密和解密的密码学。这种方法的安全性基于数学难题，如大素数的因数分解或离散对数问题。密码分析方法通常针对非对称密码学中的公开密钥进行，以下是一些常见的分析方法：

1. 因数分解攻击：基于大数的因数分解的困难性，通常使用一个大素数的乘积作为公开密钥，从而使得破解加密消息需要极其巨大的计算量。然而，随着量子计算技术的进步，Shor算法可能会在未来成为一种威胁，因为它可以有效地破解这种加密方法。
2. 密码文攻击：尝试利用公开密文来推断出明文或密钥的攻击。这可能包括使用已知的明文-密文对来推断出密钥，或者利用密文的统计特性来猜测明文。
3. 选择明文攻击：攻击者能够选择自己感兴趣的明文消息，并根据相应的密文来观察公开密钥加密的过程，从而获取有关密钥或加密算法的资讯。
4. 侧信道攻击：利用加密算法实现的物理实现的特定资讯，如功耗、电磁辐射或时间，来推断出密钥的攻击。这些攻击不直接针对算法本身，而是利用实际实现的特性来进行攻击。
5. 离散对数攻击：基于离散对数问题的困难性，如在椭圆曲线密码学中使用的ElGamal加密算法，攻击者可能会尝试利用数学技巧来破解密文。
6. 公开密钥替换攻击：当攻击者能够将合法的公开密钥替换为自己的公开密钥时，便可进行攻击。这可能发生在中间人攻击或者通过窃取合法用户的公开密钥来实现。

为了防止这些攻击，密码学家们致力于开发更强大的加密算法和协议，并提供相应的安全性证明。此外，密码学家们还研究和开发用于抵御侧信道攻击和其他物理攻击的硬件和软件保护措施。

量子计算在密码分析中的应用

量子计算在密码分析中具有潜在的显著影响，因为它利用了量子力学中的特性，如量子叠加和量子纠缠，可以在某些情况下实现比传统计算更快速和更有效的运算。以下是量子计算在密码分析中的应用：

1. Shor算法：Shor算法是一种著名的量子算法，用于因数分解。这对于公钥加密系统（如RSA）是一个潜在的威胁，因为这些系统的安全性基于大素数因子的难解性。Shor算法可以在多项式时间内找到大数的因子，从而破解这些加密系统。
2. 量子搜索算法：Quantum Search Algorithms，如Grover算法，可以在平方根的时间内搜索未排序的数据库。这意味着在破解基于密码哈希的加密时，攻击者可以更快地找到碰撞（即具有相同哈希值的不同输入）。
3. 量子密钥分发：Quantum Key Distribution（QKD）利用了量子力学中的原理来实现安全的密钥传输。这可以用于在通信过程中安全地交换密钥，防止量子计算攻击者监听通信。
4. 量子侧信道攻击：与传统侧信道攻击相比，量子侧信道攻击可能更加强大。这些攻击利用量子计算的特性，例如通过观察量子位元的状态来推断密码。

虽然量子计算在密码分析中带来了一些新的挑战，但也促使密码学家开发出新的加密技术，这些技术能够抵御量子计算的攻击。这包括基于格的加密、量子安全的哈希函数和量子安全的密码协议等。因此，量子计算不仅是一个威胁，同时也是激励加密技术进步的动力。

密码分析的方法

密码分析是一门涉及破解、评估和保护密码的学科。这涉及多种技术和方法，以下是一些常见的密码分析方法：

1. 暴力破解（Brute Force）：这是一种基本的方法，通过尝试所有可能的组合来找到密码。这可以是字典攻击（使用预先准备的单词列表）或是全盘搜索。
2. 字典攻击（Dictionary Attack）：使用预先准备好的单词列表（字典）来尝试可能的密码。这种方法假设用户使用常见的单词或短语作为密码。
3. 彩虹表攻击（Rainbow Table Attack）：这是一种使用预先计算的密码散列值和对应的明文密码之间的映射表的攻击方法。这可以节省计算时间，因为不需要每次都重新计算密码的散列值。
4. 社会工程学（Social Engineering）：这种方法涉及通过欺骗、询问或其他方式来获取密码。这可能包括伪装成合法的用户或系统管理员，以便用户自己提供密码。
5. 侧通道攻击（Side-Channel Attacks）：这种攻击利用了密码处理系统的实际实现漏洞，而不仅仅是依赖于破解密码本身。这可能包括分析电源消耗、计算时间等来推断密码。
6. 网络监听（Network Sniffing）：通过监听网络流量，特别是在未加密的情况下，攻击者可以截取带有密码的通信。
7. 钓鱼（Phishing）：这是一种通过伪造信任来诈骗用户提供他们的密码的方法，通常通过伪装成合法的网站或服务来实现。
8. 侧信道攻击（Side-Channel Attacks）：这是一种利用实际装置的特性（如功耗、电磁辐射等）来推断密码的攻击方法。
9. 社交工程：攻击者可能通过与目标交往、通过社交媒体收集资讯等方式来获取关于目标的资讯，以便猜测或重置其密码。

综合利用这些方法可以提高对不同密码的破解成功率，而针对性的密码保护方法也应该考虑这些攻击手段来提高安全性。

参见

• Ophcrack