《密码术的奥秘》不可破译的密码？

引言

出于实际考虑，第三章给出的例子都很简单。其中大多数都是很容易被破译的，尽管在它们被设计出来的那个时代情况并非如此。密码分析通常伴随着大量的尝试与错误，随着新的技术进步，特别是计算机的出现，试错过程已变得更为容易了。最明显的一种实施试错攻击的例子，是我们在第二章讨论过的密钥穷举搜索法。假设有一个具有合理长度密钥词——比如说它有6个字母——的维热纳尔密码，在16世纪要通过手工计算来试验所有可能的密钥，恐怕会令人望而却步。然而，如果我们使用计算机，它每秒钟可以试验10,000个六字母密钥词，那么不到一天就可完成全部任务。

在我们从上一章的历史例证转向讨论现代技术之前，有必要来探讨一下不可破译之密码的概念。很多设计者都曾宣称他们的算法是不可破译的，结果往往是一败涂地。我们现在讲两个历史上著名的误信其密码不可破译的例子，一个发生在16世纪，另一个发生在第二次世界大战中。

16世纪时，苏格兰的玛丽（Mary）女王在她的密信中使用了简单代换密码的一个变种密码。这些通信谈到了两个计划：越狱并且暗杀英格兰女王伊丽莎白（Elizabeth），以夺取英格兰王位。这些信被拦截并破译了，成为审判她的罪证。在这些密信中，玛丽与她的同谋者毫不隐晦地讨论他们的计划，因为他们相信别人都看不懂这些信。这个错误的代价是让玛丽断送了性命。

在第二次世界大战期间，德国军队使用一种叫做谜密码机的装备来加密大量重要的或不重要的军事通讯。谜密码机用于加密的机械结构看起来错综复杂，一台初级的谜密码机有多于10²⁰种可能的密钥，甚至超过了某些现代算法。这导致了使用者相信谜密码是不可破译的。然而就如现在广为人知的情况那样，联军在不同的时期都破译过谜密码，部分原因是他们充分利用了敌方在使用过程和密钥管理中的错误。破译工作的中心在布莱奇利公园里，现在那里是博物馆。据估计，在布莱奇利公园进行的工作使二战提前两年结束。

在本章我们将讨论完全保密的概念；在某种意义下，它是我们在加密信息时所期望达到的最好结果。然后，我们来探讨一次填充密码，它是唯一一种不可破译的算法。

完全保密

到目前为止，我们所描述的大致情景是：一个发送者试图将一保密信息发送给预定的接收者，且在此过程中发送者使用了一个密码系统使得所传输的密文在第三方眼里是篇不可识别的电文。然而，即便第三方没能拦截到这次信息传输，但也有可能（尽管大多数情形下这种可能性是极其微小的）他们已经猜到了信息的内容。所以，给信息加密并不能确保第三方无法取得信息的内容，通信者所能指望的最好结果是当第三方设法拦截时，其拦截到的东西不能给他们带来任何有助于了解信息真实内容的情报。换句话说，密码系统应该迫使截获了密文的人仍要去猜测信息的内容。当然，密码系统完全无法阻止攻击者猜测信息。

能够达到上述目标的系统即可被认为提供了完全保密。现在我们举一个小例子说明完全保密是可以做到的。

假定X先生正准备作出一个将严重影响一家公司股票值的决定。如果他作出的决定是“买”，那么股票就将升值。但如果决定“卖”，则将导致股票暴跌。此外假定公众知道他将传送这两个信息中的一个给他的股票经纪人。很清楚，任何人只要先于经纪人得知了这个决定，那他就有机会利用这个情报，根据决定的内容或是获利或是规避灾难性的损失。自然，无论如何，任何人都可自由地猜测信息的内容并采取相应的行动。他们有50％的胜算，但这样的行动与赌博没什么区别。

X先生希望一作出决定就尽快把他的决定通过公共网络发送出去。为了保护他们的利益，他和他的经纪人约定信息在加密后传送。一种选择是使用简单代换密码，我们已经说过，这对保护短信息来说往往就足够了。但在这个特定的例子中，每个信息因其长度的不同而具有独特性^【1】。假定拦截者知道通信使用的密码系统，那么当他得到了密文的长度后，他将对该信息的内容有100％的把握，尽管他还不能确定所用的密钥。

另一种选择是使用下述系统，其中两个密钥k1和k2具有均等的可能性。为了描述完整的算法，我们使用标准的数学符号。对于密钥k1，明文信息“买”的密文是0，而“卖”的密文是1，我们简写为E_k1（买）＝0和E_k1（卖）＝1。表达式E_k1（买）＝0应读作“使用密钥k1对明文'买’加密的结果是0”。全部密码是：

密钥k1：E_k1（买）＝0，E_k1（卖）＝1

密钥k2：E_k2（买）＝1，E_k2（卖）＝0

下列图示是上述密码的等价写法：

应用这个系统时，比如说拦截者截获了0这个信息，那么他能推断出的所有结论就是：如果通信者使用的密钥是k2，则该信息为“卖”；如果使用的是k1，则信息为“买”。于是，拦截者将被迫去猜通信者到底用的是哪个密钥，因为这两个密钥被选用的机会均等，他能猜对的概率是50％。

注意，实质上在拦截到密文之前，攻击者唯一能做的就是去猜这个信息。而一旦得到密文，他们能做的仍是去猜密钥。由于密钥的个数与信息的数目相同，所以前后两次猜对的机会是相等的。这就是完全保密。在这个特定的例子中，攻击者猜中信息的机会有50％，这是很高的几率了。这样，尽管我们实现了完全保密，但我们并没有提供额外的保护措施来增加信息保密的可能性。不管怎么说，这种弱点要归因于信息的数量太小，而不是加密手段太差。

在真实生活的一些情景中，潜在信息的数量非常有限，此时信息被猜中的危险大于加密信息被破译的危险。一个几乎涉及到我们每个人的例子是在自动柜员机（ATM）上使用带身份识别号码的信用卡或借记卡。在此情景中，使用者都有一个身份识别号码（PIN）用以证实他们拥有这张卡。如果PIN要经过某财政机构的中心计算机的确认，那么从ATM到主计算机间的信息传送是有加密保护的。如果使用者的卡丢了，那么任何捡到卡的人都可以将它插入ATM中，并键入他“猜测的”PIN。大多数PIN是由四个（十进制）数字组成的，所以至多有10,000个不同的PIN。那个捡到卡的人理论上可以不断地去猜那个PIN，直到找到正确的为止，这比破译密码要容易些。何况，对此问题也不存在密码术上的解决方法。认识到这一事实，大多数系统只允许出现三次输入错误，之后ATM将把卡吞掉。可见，在某些情况下，密码术只能部分地解决安全问题，为了提高安全性，需要实施特别的管理决策，上例就是众多例子中的一个。

也许值得注意的是，在我们关于完全保密的简单例子中，两个集团一知道他们可能需要交换机密信息时，或许就已作出使用何种密钥的协定。这个协定可能是在他们两家之一的基地秘密作出的。这些密钥的保密可能会采用物理手段，比如在使用之前将它们锁在保险箱里。这一做法的意义在第八章讲述密钥管理时，就变得显而易见了。

尽管上面那个关于完全保密的例子中仅含有两个信息，但对于任何长度信息的通信，都可以设计出类似的保密方案。当然，完全保密只能在密钥数量至少与信息数量一样多的情况下才能实现。

一次填充密码

从我们对完全保密的讨论，可以得出一个重要结论：完全保密是可以实现的，但对于存在大量潜在信息的系统，我们需要付出很高的代价对潜在的大量密钥进行管理。一次填充密码是完全保密的密码系统的经典例子。假设信息是一段舍去了所有标点与空格的英文文本，它包含n个字母，那么密钥就是从字母表中随机生成的n个字母的序列，每个密钥仅使用一次以保护单个信息。加密规则就是在维热纳尔密码中使用的那种，但要用密钥替代后者的密钥词。如果我们按惯例将A到Z的字母依次和0到25的数字相联系，信息记为m₁、m₂、……、m_n，密钥记为k₁、k₂、……、k_n，则密文中第i个分量记为：

c_i＝（m_i＋k_i）mod 26

注意，此时密钥与信息具有相同的长度，这保证了在加密过程中我们不需要重复密钥。

这个算法有另一种很常见的版本，常被称为维南密码，其中所用的字母表是二元的，即只有0和1，密文是信息与密钥两者相加模2所得。毫无疑问，维南密码是一次填充密码在数字通信中使用的版本。

由于完全保密是可实现的，谁都不免要问：为什么它没有得到广泛的应用，为什么人们要用那些可能被破译的密码系统。在提示这类问题该如何回答之前，很重要的一点是要记住储存数据的加密与保护通讯的加密并不是一回事。同样重要的是，我们通常集中关注通讯方面，因为其中会涉及更多管理方面的问题。

在定义一次填充密码时，我们只列出了加密算法和加密密钥。解密密钥与加密密钥相同，但解密算法要求从密文中减去密钥字母从而得到明文。通讯系统的工程师们现在面临着一个可能很困难的问题。如何让对方得到这个随机序列？因为这个序列是随机生成的，发信人与收信人“不可能”同时生成同样的密钥。于是他们中的一方必须首先生成一个密钥，然后将其（秘密地）发送给另一方。这时，想要保证密钥的秘密不被泄露，在发送时需要对它加以保护。如果通信者之间只有一条通信链路可用，那他们就需要再使用一个一次填充随机序列去保护这第一个序列。很清楚，这种推理将导致一个不可企及的要求，即要有无穷多的随机序列，其中每一个都用来保护前一个序列从发送方到接收方之间通信的安全。于是，使用一次填充密码的条件是通信者必须有第二种交流信息的安全手段。读者一定记得，完全保密系统的例子中所讲到的X先生和他的经纪人之间就有这样一条信道。一般认为，一次填充密码只用于最高层次的安全链路，例如莫斯科–华盛顿热线。在这种情形下，所生成并储存起来的随机序列是通过安全信使送达另一方的。然后随机序列能被储存在受到高度保护的地方，需要时产生，用完后立即销毁。必须认识到，这第二条安全信道既缓慢又昂贵，它不可能用于发送信息，因为此时人们可能需要对方立刻作出回答和反应。

我们已经提到过，在一个安全网络中，密钥配送是个疑难问题，它不仅限于一次填充密码。对第二条安全信道的要求也是很常见的。区别在于，一次填充密码的第二条信道所承载的传输量与信息传输量是相当的，但通常情况下第二信道承载的传输量要少得多。即使有第二条安全链路，一次填充密码仍然不适合包含很多网点的系统，因为每个网点都需要有与其他所有网点关联的安全链路。此时的疑难之点似乎在于掌握已使用过的密钥的信息，也许还涉及对大量密钥资料的管理。完全保密依赖于每个密钥只使用一次。对于一个庞大而频繁使用的网络而言，要管理好它所需要的全部密钥资源几乎是不可能的。

毫不奇怪，虽然一次填充密码展示了一种终极的安全水平，但几乎没有实际的通信网络系统使用。当然，如果有人只因私人之需加密文件并储存起来，那么他们不需要配送任何密钥。在很多储存方案中，唯一的难点就是密钥的存储，因此对于其中的某些方案来说，一次填充密码像其他任何密码一样可行。（弗雷德·派珀）

注释

【1】　“买”（buy）在英语中有3个字母，而“卖”（sell）则有4个字母，因此用简单代换密码加密后的信息长度是不同的。