第 1 章   密码学及其应用概述

人们总想对他人保守自己信息的秘密，历史上有不少这方面的例子。国王和将军们利用基本的密码方法与他们的军队进行通信，以防止敌人获得敏感的军事信息。据说凯撒大帝（Julius Caesar）就用过一种后来以他名字命名的简单密码。

随着社会的发展，人们对更先进的数据保护方法的需求在不断增加。在如今的信息时代，这种需求比以往更为显著。随着世界的联系变得更加紧密，对信息和电子服务的需求也在不断增长，这种需求的增长造成了对电子系统的更加依赖。诸如信用卡号之类的敏感信息交换在因特网上已经成了一件普通事。保护数据与电子系统对我们的生活方式至关重要。

用来保护数据的技术属于密码学领域。实际上，它有cryptography、cryptology和cryptanalysis 3个名字，这些名字经常交替使用。但是从技术上说，cryptology是一个全面的术语，它指的是对不安全信道上的通信及相关问题的研究，而设计能够进行这种通信的密码系统的过程则称为cryptography。cryptanalysis所处理的问题是破译这种密码系统。当然，不管是进行cryptography还是cryptanalysis，如果对这两方面中的方法没有良好理解，那基本上是不可能做到的。

编码理论（coding theory）这个术语经常会被用来描述密码学，但这样会导致混淆。编码理论所做的是把输入的信息符号用称为码符号的输出符号表示出来。编码理论包括3个基本应用—压缩、保密和纠错。在过去的几十年中，编码理论这个术语变成主要是和纠错码相关了。编码理论因此成为研究噪声信道上的通信以及如何确保收到正确消息的理论，与密码学相反，它是要保护不安全信道上的通信。

虽然纠错码是本书的一个次要论题，但我们还是要强调，在任何一个现实世界的系统中，纠错码都是和加密一起使用的，因为任何一位的改变都足以破坏一个设计良好的密码系统的消息完整性。

现代密码学是一个高度依赖于数学、计算机科学和聪明才智的领域。本书介绍了建立安全的数据传输和电子系统所需的数学和协议知识，以及包括电子签名和秘密共享在内的技术。

1.1   安全通信

在如图1-1所描绘的基本通信模式中，有Alice 和 Bob两方互相通信。第三方Eve，则是一个隐藏的窃听者。

当Alice向Bob发送消息（称之为明文）时，她与Bob使用预先约定的方法对消息进行加密。通常，假定加密方法为Eve所知；能使消息保密的是密钥。当Bob收到加密的消息（称之为密文）时，他便用解密密钥把密文还原成明文。

Eve可能有如下意图：

(1) 阅读该消息；

(2) 找到密钥以便阅读所有用该密钥加密的消息；

(3) 窜改Alice的消息，使Bob以为Alice发的是改写后的那条消息；

(4) 冒充Alice与Bob通信，并使Bob相信自己是在和Alice通信。

我们面临的是以上哪种情形要视Eve有多邪恶而定。情形(3)和(4)分别与完整性和鉴别相关，我们将很快讨论到这些。像情形(3)和(4)中那样比较主动和恶意的敌方，在文献中通常称他Mallory；而更为被动的观察者（如情形(1)和(2)中那样）则有时称为Oscar。我们一般仅用Eve这个名字，并且假定她在条件所允许的情况下会做到最坏。

图1-1   密码学基本通信模式

1.1.1   可能的攻击

Eve有4种主要的攻击方式。这些攻击方式的区别在于Eve在试图获取密钥时所拥有的信息量。这4种攻击方式如下所述。

(1) 唯密文：Eve只有一份密文的副本。

(2) 已知明文：Eve有一份密文的副本以及相应的明文。例如，假设Eve截获了一份加密的通信稿，并在第二天看到了解密后的通信稿。如果Alice没有改变密钥而Eve又能推断出解密密钥来，那么她就能读出将来的所有信息。或者，如果Alice总是以“Dear Bob”作为其消息的开头，那么Eve就有了一小份密文和相对应的明文。对许多弱密码系统来说，这足以找到密钥了。即使是对于像二战中使用的德国的Enigma密码机这样比较强的密码系统，上述的这种信息也起了很大的作用。

(3) 选择明文：Eve有短暂的机会接触加密机。她不能打开机器来找密钥，但可以加密大量经过适当选择的明文，然后试着利用所得的密文来推断密钥。

(4) 选择密文：Eve有短暂的机会接触解密机，她用它来对若干字符串符号解密，然后试着用所得结果推断密钥。

有一种选择明文攻击可能按如下方式发生。你想识别一架飞机是敌机还是友机。向这架 飞机发送一个随机消息，飞机对消息自动加密后将其返回。假定只有友机有正确的密钥。将从飞机上返回的消息与正确加密的消息相比较，如果吻合那么飞机是友机，否则就是敌机。但是，敌方可以发送大批经过选择的消息给你方的某架飞机，然后查看收到的密文。如果他们可以因此推断出密钥，那敌方就可以把他们的飞机伪装成友机。

一个已知明文攻击的实例据说发生在二战时期的撒哈拉沙漠。一个孤立的德军前哨每天都会发送一个同样的消息，报告没有什么新情况，这条消息当然是用当天的密钥加密的，所以盟军每天可以获得一个明文－密文对，这对于确定密钥来说是非常有用的。而事实上在撒哈拉战役期间，蒙哥马利将军一直在非常小心地控制着这个前哨，以使得这种消息传递不会被中断。

现代密码学中一个最要的假设就是Kerckhoffs原则：在评估一个密码系统的安全性时，必须假定敌方知道所用的加密方法。这个原则是由Auguste Kerckhoffs于1883年在他的经典论文 La Cryptographie Militaire中阐明的。敌方可以有很多方式获得这个信息，如加密/解密机可以被俘获和分析，或者人员叛变或被捕。系统的安全性因而应该基于密钥而不是所用算法的隐蔽性。所以，我们总是假定Eve知道用来加密的算法。

1.1.2   对称和公钥算法

加密/解密方法可分成两个范畴：对称密钥和公钥。在对称密钥算法中，加密密钥和解密密钥为Alice和Bob所共知。例如加密密钥共享后，解密密钥很容易由其算出。在很多情况下，加密密钥和解密密钥是相同的。所有的传统（1970年以前）密码系统都是对称密码，正如后来的数据加密标准（DES）和高级加密标准（AES）。

20世纪70年代提出的公钥算法是密码学的一次革命。假设Alice想和Bob安全地通信，但他们相隔数百公里而且没有商量好要用的密钥。如果没有事先碰头商量好密钥或由一个信得过的信使把密钥从一方送到另一方，那么要想做到安全通信看起来几乎是不可能的。Alice当然不能通过公开信道发送消息来告诉Bob密钥，然后发送用这个密钥加密的密文。令人惊奇的是这个问题居然有解，即所谓的公钥密码学：加密密钥是公开的，但是如果没有仅为Bob所知的信息，要找到解密密钥在计算上是不可行的。应用最为普遍的公钥算法是RSA（见第6章），它是基于大整数因子分解的困难性。其他公钥算法（见第7章、第17章和第18章）还有ElGamal 系统（基于离散对数问题），NTRU（基于格）和McEliece系统（基于纠错码）。

有一个非数学的方式可以用来解释公钥密码通信。Bob发送给Alice一个盒子和一把开着的挂锁。Alice把消息放入盒子并用Bob的锁锁上，然后送还给Bob。当然，只有Bob能够打开盒子阅读信息。前面提到的公钥方法正是这个想法的数学实现。显然这里有鉴别的问题必须解决。例如Eve可能会截住第一次传送的盒子并换上她自己的锁。如果她接着截住Alice发还给Bob的上锁的盒子，那么就可以打开她的锁，然后阅读Alice的消息。这是任何此种系统必须解决的普遍性问题。

公钥密码学所代表的可能是这段令人感兴趣的历史进步中的最后一步。在密码学的初期，安全性依赖于加密方法的保密。后来就假定加密方法是已知的，而安全性则依赖于将（对称）密钥保密或不让敌方知晓。在公钥密码学中，加密方法和加密密钥是公开的，而且每个人都知道如何去找解密密钥。其安全性依赖于这样一个事实（或愿望）：找解密密钥在计算上是不可行的。经过若干年的发展，密码算法的功能日益增强，但与此对应的是敌方所掌握的关于这些算法的信息量也在不断增加，这相当矛盾。

公钥方法功能强大，看起来对称密码似乎要被废弃了。然而，这种新添的灵活性不是免费的，它是以计算为代价的。公钥算法所需的计算量通常比DES或Rijndale这样的算法的计算量高几个数量级。经验告诉我们，不要用公钥方法来加密大批量的数据。因此，公钥方法只用于少量数据的处理上（如数字签名和发送对称密钥算法中使用的密钥）。

对称密码学中有两种类型的密码：流密码和分组密码。在流密码中，数据是一小片一小片（若干位或字符）地输入算法，输出也是一小片一小片地产生。但在分组密码里，一组位一次性全部输入到算法中，输出的也是一组位。在2.11节中将讨论一个基于线性反馈移位寄存器的流密码的例子，但我们更多地还是关注分组密码。同时给出两个重要的例子，第一个是DES，第二个是Rijndael，后者被（美国）国家标准技术研究所（NIST）于2000年选来代替DES。像RSA这样的公钥方法也可以看作是分组密码。

最后，我们给出历史上两个不同类型的加密，即码（code）和密码（cipher）。在码里，单词或某个字母组合由码字（可能是符号串）代替。例如，一战期间英国海军用03680C、36276C和50302C分别代表shipped at、shipped by和shipped from。码的缺点在于不能使用未曾预料的单词。相反，密码不需要用到消息的语言结构，而只要用某个算法对每一串字符加密，不管它是否有意义，因此密码比码用途更广。在密码学的早期，普遍使用码，有时也结合密码一块使用，而且在今天仍被使用—隐蔽的军事行动经常以码命名。然而,任何秘密要保证安全都要使用密码加密。本书我们只讨论密码。

1.1.3    密钥长度

密码学算法的安全性是一个很难度量的性质。大多数算法会使用密钥，并且算法的安全性与敌方确定密钥的困难程度相关。最显著的方法是尝试每一个可能的密钥，看哪些能得到有意义的解密，这种攻击被称为蛮力攻击（brute force attack）。在蛮力攻击中，密钥的长度直接和搜索整个密钥空间所需的时间相关。例如一个密钥的长度是16位，那么就有216＝65536个可能的密钥。DES算法的密钥长度为56位，从而有256≈7.2×1016个可能的密钥。

本书中有很多这样的情况，即系统看起来似乎可以通过简单地尝试所有可能的密钥而被破解，可是说起来容易做起来难。假定需要尝试1030种可能性，而你的计算机每秒可做109次这种运算。一年大约有3×107秒，所以需要3×1013年还多一些的时间才能完成这个任务，这比所预测的宇宙的寿命还长。

较长的密钥更有优势，但是这并不保证会增加敌方破译任务的困难性，算法本身也起了关键的作用。有些算法可能被蛮力之外的其他方法所攻击，还有些算法并不能很有效地使用密钥位。有一点非常重要，需要牢记：不是所有的128位的算法天生就是平等的！

例如，一个最容易破解的密码系统就是替换密码（我们将在2.4节讨论），虽然这个密码的可能密钥数为26!≈4×1026个。相比较而言，复杂的DES（见第4章）有256≈7.2×1016个可能的密钥，在一个特别设计的计算机上找一个DES密钥通常也要一天的时间。两者的区别在于，对替换密码的攻击用的是语言的基本结构，而对DES的攻击用的是蛮力攻击，这要尝试所有可能的密钥。

蛮力攻击应该是最后使用的手段，一个密码分析员总是希望能找到比这更快的攻击方法。我们将会碰到的例子有频率分析（用于替换密码和维吉内尔密码）和生日攻击（用于离散对数）。

我们也要告诫读者，一个算法现在看起来似乎安全，但并不意味着它以后也是如此。人类的智慧已经对密码协议产生了创造性的攻击方法。现代密码学中有很多算法或协议被成功攻破的例子，这或者是由于不当操作引起的漏洞造成的，或者是由于技术的进步造成的。DES算法经受住了20年的考验，最终被一台精心设计的并行计算机攻破。当你阅读本书时，量子计算的研究正在进行，它将极大地改变将来密码学算法的面貌。

例如，将要研究的几个系统的安全性都依赖于因子分解像200位这么大整数的困难性。假定想分解这般大小的一个数n，小学用的方法是用n除以所有不超过n的平方根的素数。小于10^100的素数大约有4×10^97个，用每一个去试是不可能的。宇宙中电子的数目据估计小于10^90，早在你完成计算之前，就会接到电力公司的电话让你停止计算。显然，必须使用更精致的因子分解算法，而不是这种蛮力攻击。当RSA被发明时已经有一些好的因子分解算法可用，但是据当时估计，要分解如RSA挑战数（见6.5节）这样的129位数在很长一段可预见的未来时间里是不可能完成的。然而算法和计算机体系结构的进步已经使得那样的分解成为很平常的事（虽然这仍需要大量的计算资源），所以为了安全性，现在通常推荐使用几百位的整数。但是如果一台完整的量子计算机建好了，那么这些数的分解就会变得非常容易，因而整个RSA方案（以及其他许多方法）就需要重新考虑。

因此自然会提出一个问题，是否有不可破译的密码系统，为什么不能总是用这种系统？

答案是肯定的，有一个被称为一次一密（one-time pad）的系统就是不可破译的。甚至用蛮力攻击也得不到密钥。但不幸的是，使用一次一密的代价非常昂贵，它需要交换一个和明文一样长的密钥，而这个密钥只能用一次。因此人们会选择当操作正确、密钥长度适当时能在合理时间内不被攻破的算法。

在考虑密钥大小时很重要的一点就是，在大多数情况下虽然增加密钥长度可以在数学上提高安全性，但这在实际中却并不总是可行的。如果你用的芯片可以处理64位长的单词，那么密钥长度从64位增长到65位就可能意味着硬件要重新设计，而这是非常昂贵的。因此，设计好的密码系统需要同时考虑数学和工程两个方面。

最后，我们要讨论一下数的大小。直觉可能会告诉你，使用20位数的工作时间是使用10位数的两倍，这在某些算法里是对的。然而如果你算到10^10，并没有接近10^20，你只是算到了一百亿分之一的地方。类似地，蛮力攻击60位的密钥所花的时间比攻击30位的密钥的时间长10亿倍。

有两个方法可以衡量数的大小：数n的实际大小和数的十进制表示的位数（也可以用它的二进制表示），后者大约是log10(n)。用小学的标准算法算一个k位数n的平方所需做的各个位数乘法的数目是k2，或大约是log10(n)2。为分解数n，用所有不超过n的平方根的素数去除n所要做的除法次数大约是n1/2。一个运行时间为log10n的幂的算法比运行时间为n的幂的算法要可取得多。在目前这个例子中，如果让n的位数翻一倍，那么平方n所需的时间就增长了4倍，而分解n所需的时间剧增。当然，有更好的算法可用来做这两种运算；但就目前来讲，分解运算所需的时间大大超过乘法运算的时间。

我们将碰到执行某种计算所需的时间是log10n的幂的算法（例如找最大公因子和做模指数运算）。还有其他的一些计算，对它们来说使用最好的算法也仅仅是比n的幂稍好一点（如因子分解和寻找离散对数）。最快算法和最慢算法之间的相互作用，是本书中将遇到的几个密码学算法的基础。