【文章】应用密码学：一次一密乱码本 - 大数

1.5  一次一密乱码本

    不管你是否相信它，有一种理想的加密方案，叫做一次一密乱码本，由Major Joseph Mauborgne和AT&T公司的Gilbert Vernam在1917年发明的[794]（实际上，一次一密乱码本是门限方案的特殊情况，见3.7节）。典型地，一次一密乱码本不外乎是一个大的不重复的真随机密钥字母集，这个密钥字母集被写在几张纸上，并一起粘成一个乱码本。它最初的形式是将一次一密乱码本用于电传打字机。发方用乱码本中的每一密钥字母准确地加密一个明文字符。加密是明文字符和一次一密乱码本密钥字符的模26加法。

    每个密钥仅对一个消息使用一次。发方对所发的消息加密，然后销毁乱码本中用过的一页或用过的磁带部分。收方有一个同样的乱码本，并依次使用乱码本上的每个密钥去解密密文的每个字符。收方在解密消息后销毁乱码本中用过的一页或用过的磁带部分。新的消息则用乱码本的新的密钥加密。

    例如，如果消息是： ONETIMEPAD，

    而取自乱码本的密钥序列是： TBFRGFARFM，

    那么密文就是： IPKLPSFHGQ ，

    因为：

              O + T mod26 = I

              N + B mod26 = P

              E + F mod26 = K

              等等。

    如果偷窃听者不能得到用来加密消息的一次一密乱码本，这个方案是完全保密的。给出的密文消息相当于同样长度的任何可能的明文消息。

    由于每一密钥序列都是等概的（记住，密钥是以随机方式产生的），敌方没有任何信息用来对密文进行密码分析，密钥序列也可能是：

        POYYAEAAZX

    解密出来是：

        SALMONEGGS

    或密钥序列为：

        BXFGBMTMXM

    解密出来的明文为：

        GREENFLUID

    值得重申的是：由于明文消息是等概的，所以密码分析者没有办法确定哪一明文消息是正确的。随机密钥序列异或一非随机的明文消息产生一完全随机的密文消息。再大的计算能力也无能为力。

    值得注意的是，密钥字母必须是随机产生的。对这种方案的攻击将是针对用来产生密钥序列的那种方法。使用伪随机数发生器是不值得考虑的，它们通常具有非随机性。如果你采用真随机源（这比第一次出现难得多，见17.14节。），它就是安全的。

    另一个重要的事情是密钥序列不能重复使用，即使你用多兆字节的乱码本，如果密码分析家有多个密钥重叠的密文，他也能够重构明文。他把每排密文移来移去，并计算每个位置的适配量。如果他们排列正确，则适配的比例会突然升高（准确的百分比与明文的语种有关）。从这一点来说，密码分析是容易的，它类似于重合指数法，只不过用两个“周期”作比较[904]。所以千万别重复使用密钥序列。

    一次一密乱码本的想法很容易推广到二进制数据的加密，只需由二进制数字组成的一次一密乱码本代替由字母组成的一次一密乱码，用异或代替一次一密乱码本的明文字符加法就成。为了解密，用同样的一次一密乱码本对密文异或，其他保持不变，保密性也很完善。

    这听起来很好，但有几个问题。因为密钥比特必须是随机的，并且绝不能重复使用，密钥序列的长度要等于消息的长度。一次一密乱码本可能对短信息是可行的，但它决不可能在1.44Mbps的通信信道上工作。你能在一张CD-ROM中存储650兆字节的随机二进制数。但有一些问题：首先，你需要准确地复制两份随机数比特，但CD-ROM只是对大量的数据来说是经济的；其次，你需要能够销毁已经使用过的比特，而CD-ROM没有抹除设备，除非物理毁坏整张盘。数字磁带对这种东西来说是更好的媒体。

    即使解决了密钥的分配和存储问题，还需确信发方和收方是完全同步的。如果收方有一比特的偏移（或者一些比特在传送过程中丢失了），消息就变成乱七八糟的东西了。另一方面，如果某些比特在传送中被改变了（没有增减任何比特，更像由于随机噪声引起的），那些改变了的比特就不能正确地解密。再者，一次一密乱码本不提供鉴别。

    一次一密乱码本在今天仍有应用场合，主要用于高度机密的低带宽信道。美国和前苏联之间的热线电话（现在还在起作用吗？）据传就是用一次一密乱码本加密的。许多苏联间谍传递的消息也是用一次一密乱码本加密的。到今天这些消息仍是保密的，并将一直保密下去。不管超级计算机工作多久，也不管半个世纪中有多少人，用什么样的方法和技术，具有多大的计算能力，他们都不可能阅读苏联间谍用一次一密乱码本加密的消息（除非他们恰好回到那个年代，并得到加密消息的一次一密乱码本）。

1.6 计算机算法

    计算机密码算法有多种，最通用的有三种：

    ——DES（数据加密标准）是最通用的计算机加密算法。DES是美国和国际标准，它是对称算法，加密和解密的密钥是相同的。

    ——RSA（根据它的发明者命名的，即Rivest，Shamir 和Adleman）是最流行的公开密钥算法，它能用作加密和数字签名。

    ——DSA（数字签名算法，用作数字签名标准的一部分）是另一种公开密钥算法，它不能用作加密，只用作数字签名。

    这些就是本书所要涉及的题材。

1.7 大数

    在整本书中，我用各种大数去描述密码算法中的不同内容。因为很容易忽略这些数和它们的实际意义，所以表1.1给出了一些大数的物理模拟量。

    表中这些数是估计的数量级，并且是从各种资料中精选得到的，天体物理学中许多大数在Freeman Dyson的文章中有解释，该文章发表在《现代物理学评论》中，名为“时间永无止境：开放宇宙中的物理学和生物学”。汽车事故的死亡人数是根据1993年交通部统计数据每百万人中有178起死亡事故和人均寿命为75.4年计算出来的。

表1.1  大数

每天被闪电杀死的可能性                                                                   90亿（2³³）分之一

赢得国家发行彩票头等奖的可能性                                                     4百万（2²²）分之一

赢得国家发行彩票头等奖并且在同一天被闪电杀死的可能性                     1/2⁵⁵

每年淹死的可能性                                                                                   

1993年在美国交通事故中死亡的可能性                                      6100（2¹³）分之一

一生在美国死于交通事故的可能性                                                  88（2⁷）分之一

到下一个冰川年代的时间                                                                   14000（2¹⁴）年

到太阳变成新星的时间                                                                             10⁹（2³⁰）年

行星的年龄                                                                                        10⁹（2³⁰）年

宇宙的年龄                                                                                        10¹⁰（2³⁴）年

行星中的原子数                                                                                 10⁵¹（2¹⁷⁰）

太阳中的原子数                                                                                 10⁵⁷（2¹⁹⁰）

银河系中的原子数                                                                                    10⁶⁷（2²²³）

宇宙中的原子数（黑粒子除外）                                                               10⁷⁷（2²⁶⁵）

宇宙的体积                                                                                        10⁸⁴（2²⁸⁰）cm³

如果宇宙是封闭的：

宇宙的生命期                                                                                           10¹¹（2³⁷）年

                                                                                                      10¹⁸（2⁶¹）秒

如果宇宙是开放的：

到小弥撒星冷却下来的时间                                                                      10¹⁴（2⁴⁷）年

到行星脱离星系的时间                                                                             10¹⁵（2⁵⁰）年

到行星脱离银河系的时间                                                                   10¹⁹（2⁶⁴）年

到由引力线引起的轨道蜕变的时间                                                     10²⁰（2⁶⁷）年

到由散播过程引起黑洞湮没的时间                                                     10⁶⁴（2²¹³）年

到所有物质在0⁰时都为液体的时间                                                    10⁶⁵（2²¹⁶）年

到所有物质都蜕变成铁的时间                                                            年