第一章 基础知识
1.1 专业术语
发送者和接收者
假设发送者想发送消息给接收者，且想安全地发送信息：她想确信偷听者不能阅读发送的消息。
消息和加密
消息被称为明文。用某种方法伪装消息以隐藏它的内容的过程称为加密，加了密的消息称为密文，而把密文转变为明文的过程称为解密。图1.1表明了这个过程。
（如果你遵循ISO 7498-2标准，那就用到术语“译成密码（encipher）”和“解译密码（decipher）”。某些文化似乎认为术语“加密(encrypt)”和“解密(decrypt)”令人生厌，如同陈年腐尸。）
图1.1 加密和解密
使消息保密的技术和科学叫做密码编码学，从事此行的叫密码编码者，密码分析者是从事密码分析的专业人员，密码分析学就是破译密文的科学和技术，即揭穿伪装。作为数学的一个分支的密码学包括密码编码学和密码分析学两者，精于此道的人称为密码学家，现代的密码学家通常也是理论数学家。
明文用M（消息）或P（明文）表示，它可能是比特流（文本文件、位图、数字化的语音流或数字化的视频图像）。至于涉及到计算机，P是简单地二进制数据（除了这一章节外，这本书本身只涉及二进制数据和计算机密码学）。明文可被传送或存储，无论在哪种情况，M指待加密的消息。
密文用C表示，它也是二进制数据，有时和M一样大，有时稍大（通过压缩和加密的结合，C有可能比P小些。然而，单单加密通常达不到这一点）。加密函数E作用于M得到密文C，用数学表示为：
E（M）=C.
相反地，解密函数D作用于C产生M
D（C）=M.
先加密后再解密消息，原始的明文将恢复出来，下面的等式必须成立：
D（E（M））=M
鉴别、完整性和抗抵赖
除了提供机密性外，密码学通常有其它的作用：.
－鉴别
消息的接收者应该能够确认消息的来源；入侵者不可能伪装成他人。
－完整性
消息的接收者应该能够验证在传送过程中消息没有被修改；入侵者不可能用假消息代替合法消息。
－抗抵赖
发送者事后不可能虚假地否认他发送的消息。
这些功能是通过计算机进行社会交流，至关重要的需求，就象面对面交流一样。某人是否就是他说的人；某人的身份证明文件（驾驶执照、医学学历或者护照）是否有效；声称从某人那里来的文件是否确实从那个人那里来的；这些事情都是通过鉴别、完整性和抗抵赖来实现的。
算法和密钥
密码算法也叫密码，是用于加密和解密的数学函数。（通常情况下，有两个相关的函数：一个用作加密，另一个用作解密）
如果算法的保密性是基于保持算法的秘密，这种算法称为受限制的算法。受限制的算法具有历史意义，但按现在的标准，它们的保密性已远远不够。大的或经常变换的用户组织不能使用它们，因为每有一个用户离开这个组织，其它的用户就必须改换另外不同的算法。如果有人无意暴露了这个秘密，所有人都必须改变他们的算法。
更糟的是，受限制的密码算法不可能进行质量控制或标准化。每个用户组织必须有他们自己的唯一算法。这样的组织不可能采用流行的硬件或软件产品。但窃听者却可以买到这些流行产品并学习算法，于是用户不得不自己编写算法并予以实现，如果这个组织中没有好的密码学家，那么他们就无法知道他们是否拥有安全的算法。
尽管有这些主要缺陷，受限制的算法对低密级的应用来说还是很流行的，用户或者没有认识到或者不在乎他们系统中内在的问题。
现代密码学用密钥解决了这个问题，密钥用K表示。K可以是很多数值里的任意值。密钥K的可能值的范围叫做密钥空间。加密和解密运算都使用这个密钥（即运算都依赖于密钥，并用K作为下标表示），这样，加/解密函数现在变成：
EK（M）=C
DK（C）=M.
这些函数具有下面的特性（见图1.2）：
DK（EK（M））=M.
图1.2 使用一个密钥的加/解密
图1.3 使用两个密钥的加/解密
有些算法使用不同的加密密钥和解密密钥（见图1.3），也就是说加密密钥K1与相应的解密密钥K2不同，在这种情况下：
EK1（M）=C
DK2（C）=M
DK2 （EK1（M））=M
所有这些算法的安全性都基于密钥的安全性；而不是基于算法的细节的安全性。这就意味着算法可以公开，也可以被分析，可以大量生产使用算法的产品，即使偷听者知道你的算法也没有关系；如果他不知道你使用的具体密钥，他就不可能阅读你的消息。
密码系统由算法、以及所有可能的明文、密文和密钥组成的。
对称算法
基于密钥的算法通常有两类：对称算法和公开密钥算法。
对称算法有时又叫传统密码算法，就是加密密钥能够从解密密钥中推算出来，反过来也成立。在大多数对称算法中，加/解密密钥是相同的。这些算法也叫秘密密钥算法或单密钥算法，它要求发送者和接收者在安全通信之前，商定一个密钥。对称算法的安全性依赖于密钥，泄漏密钥就意味着任何人都能对消息进行加/解密。只要通信需要保密，密钥就必须保密。
对称算法的加密和解密表示为：
EK（M）=C
DK（C）=M
对称算法可分为两类。一次只对明文中的单个比特（有时对字节）运算的算法称为序列算法或序列密码。另一类算法是对明文的一组比特亚行运算，这些比特组称为分组，相应的算法称为分组算法或分组密码。现代计算机密码算法的典型分组长度为64比特——这个长度大到足以防止分析破译，但又小到足以方便使用（在计算机出现前，算法普遍地每次只对明文的一个字符运算，可认为是序列密码对字符序列的运算）。
公开密钥算法
公开密钥算法（也叫非对称算法）是这样设计的：用作加密的密钥不同于用作解密的密钥，而且解密密钥不能根据加密密钥计算出来（至少在合理假定的长时间内）。之所以叫做公开密钥算法，是因为加密密钥能够公开，即陌生者能用加密密钥加密信息，但只有用相应的解密密钥才能解密信息。在这些系统中，加密密钥叫做公开密钥（简称公钥），解密密钥叫做私人密钥（简称私钥）。私人密钥有时也叫秘密密钥。为了避免与对称算法混淆，此处不用秘密密钥这个名字。
用公开密钥K加密表示为：
EK（M）=C.
虽然公开密钥和私人密钥是不同的，但用相应的私人密钥解密可表示为：
DK（C）=M
有时消息用私人密钥加密而用公开密钥解密，这用于数字签名（见2.6节），尽管可能产生混淆，但这些运算可分别表示为：
EK（M）=C
DK（C）=M
密码分析
密码编码学的主要目的是保持明文（或密钥，或明文和密钥）的秘密以防止偷听者（也叫对手、攻击者、截取者、入侵者、敌手或干脆称为敌人）知晓。这里假设偷听者完全能够接获收发者之间的通信。
密码分析学是在不知道密钥的情况下。恢复出明文的科学。成功的密码分析能恢复出消息的明文或密钥。密码分析也可以发现密码体制的弱点，最终得到上述结果（密钥通过非密码分析方式的丢失叫做泄露。）
对密码进行分析的尝试称为攻击。荷兰人A.Kerckhoffs最早在19世纪阐明密码分析的一个基本假设，这个假设就是秘密必须全寓于密钥中[794]。Kerckhoffs假设密码分析者已有密码算法及其实现的全部详细资料（当然，可以假设中央情报局(CIA)不会把密码算法告诉摩萨德(Mossad)（译注：以色列的情报组织），但Mossad也许会通过什么方法推出来）。在实际的密码分析中并不总是有这些详细信息的¾¾应该如此假设。如果其他人不能破译算法，即便了解算法如何工作也是徒然，如果连算法的知识都没有，那就肯定不可能破译它。
常用的密码分析攻击有四类，当然，每一类都假设密码分析者知道所用的加密算法的全部知识：
(1) 唯密文攻击。
密码分析者有一些消息的密文，这些消息都用同一加密算法加密。密码分析者的任务是恢复尽可能多的明文，或者最好是能推算出加密消息的密钥来，以便可采用相同的密钥解出其他被加密的消息。
已知：C1=EK（P1），C2=EK（P2），LL，CI=EK（Pi）
推导出：P1，P2，L，Pi；K或者找出一个算法从Ci+1= EK（Pi+1）推出Pi+1。
(2) 已知明文攻击。
密码分析者不仅可得到一些消息的密文，而且也知道这些消息的明文。分析者的任务就是用加密信息推出用来加密的密钥或导出一个算法，此算法可以对用同一密钥加密的任何新的消息进行解密。
已知：P1，C1=Ek（P1），P2，C2=Ek（P2），L，Pi，Ci=Ek（Pi），
推导出：密钥k，或从Ci+1= Ek（Pi+1）推出Pi+1的算法。
（3）选择明文攻击。
分析者不仅可得到一些消息的密文和相应的明文，而且他们也可选择被加密的明文。这比已知明文攻击更有效。因为密码分析者能选择特定的明文块去加密，那些块可能产生更多关于密钥的信息，分析者的任务是推出用来加密消息的密钥或导出一个算法，此算法可以对用同一密钥加密的任何新的消息进行解密。
已知：P1，C1=Ek（P1），P2，C2=Ek（P2），L，Pi，Ci=Ek（Pi）
其中P1，P2，L，Pi是由密码分析者选择的。
推导出：密钥k，或从Ci+1= Ek（Pi+1）推出Pi+1的算法。
（4）自适应选择明文攻击。
这是选择明文攻击的特殊情况。密码分析者不仅能选择被加密的明文，而且也能基于以前加密的结果修正这个选择。在选择明文攻击中，密码分析者还可以选择一大块被加了密的明文。而在自适应选择密文攻击中，他可选取较小的明文块，然后再基于第一块的结果选择另一明文块，以此类推。
另外还有至少三类其它的密码分析攻击。
（5）选择密文攻击。
密码分析者能选择不同的被加密的密文，并可得到对应的解密的明文，例如密码分析者存取一个防窜改的自动解密盒，密码分析者的任务是推出密钥。
已知：C1，P1=Dk（C1），C2，P2=Dk（C2），L，Ci，Pi=Dk（Ci），
推导出： k。
这种攻击主要用于公开密钥体制，这将在19.3节中讨论。选择密文攻击有时也可有效地用于对称算法（有时选择明文攻击和选择密文攻击一起称作选择文本攻击。）
（6）选择密钥攻击。
这种攻击并不表示密码分析者能够选择密钥，它只表示密码分析者具有不同密钥之间的关系的有关知识。这种方法有点奇特和晦涩，不是很实际，将在12.4节讨论。
（7）软磨硬泡(Rubber-hose)攻击。
密码分析者威胁、勒索，或者折磨某人，直到他给出密钥为止。行贿有时称为购买密钥攻击。这些是非常有效的攻击，并且经常是破译算法的最好途径。
已知明文攻击和选择明文攻击比你想象的更常见。密码分析者得到加了密的明文消息或贿赂某人去加密所选择的消息，这种事情时有所闻。如果你给某大使一则消息，也可能发现该消息已加密了，并被送回他的国家去研究。此时你会去贿赂某人；密码分析者也许知道，许多消息有标准的开头和结尾。加密的源码特别脆弱，这是因为有规律地出现关键字， 如出现：#define，struct，else，return等。加了密的可执行代码也有同样问题，如：调用函数、循环结构等等。已知明文攻击（甚至选择明文攻击）在二战中已被成功地用来破译德国和日本的密码。David Kahn的书中有此类攻击的历史例子[794，795，796]。
不要忘记Kerckhoffs的假设：如果你的新的密码系统的强度依赖于攻击者不知道算法的内部机理，你注定会失败。如果你相信保持算法的内部秘密比让研究团体公开分析它更能改进你的密码系统的安全性，那你就错了。如果你认为别人不能反汇编你的代码和逆向设计你的算法，那你就太天真了（1994年RC4算法就发生了这种情况—见17.1节）。最好的算法是那些已经公开的，并经过世界上最好的密码分析家们多年的攻击，但还是不能破译的算法（国家安全局对外保持他们的算法的秘密，但他们有世界上最好的密码分析家在内部工作，你却没有。另外，他们互相讨论他们的算法，通过执著的审查发现他们工作中的弱点）。
密码分析者不是总能知道算法的。例如在二战中美国人破译日本人的外交密码——紫密（PURPLE）[794]就是例子，而且美国人一直在做这种事。如果算法用于商业安全程序中，那么拆开这个程序，把算法恢复出来只是时间和金钱问题；如果算法用于军队的通讯系统中，购买（或窃取）这种设备，进行逆向工程恢复算法也只是简单的时间和金钱的问题。
那些因为自己不能破译某个算法就草率地声称有一个不可破译的密码的人要么是天才，要么是笨蛋，不幸的是后者居多。千万要提一味吹嘘算法的优点，但又拒绝公开的人，相信他们的算法就像相信骗人的包医百病的灵丹妙药一样。
好的密码分析家总会坚持审查，以图把不好的算法从好的算法中剔除出去。
算法的安全性
根据被破译的难易程度，不同的密码算法具有不同的安全等级。如果破译算法的代价大于加密数据的价值，那么你可能是安全的。如果破译算法所需的时间比加密数据保密的时间更长，那么你可能是安全的；如果用单密钥加密的数据量比破译算法需要的数据量少得多，那么你可能是安全的。
我说“可能”是因为在密码分析中总有新的突破。另一方面，大多数数据随着时间的推移，其价值会越来越小，而数据的价值总是比突破保护它的安全性的代价更小，这点是很重要的。
Lars Knudsen把破译算法分为不同的类别，安全性的递减顺序[858]为：
1．全部破译。密码分析者找出密钥K，这样DK（C）=P。
2．全盘推导。密码分析者找到一个代替算法A，在不知道密钥K的情况下，等价于 DK（C）=P。
3．实例（或局部）推导。密码分析者从截获的密文中找出明文。
4．信息推导。密码分析者获得一些有关密钥或明文的信息。这些信息可能是密钥的几个比特、有关明文格式的信息等等。
如果不论密码分析者有多少密文，都没有足够的信息恢复出明文，那么这个算法就是无条件保密的，事实上，只有一次一密乱码本（参看1.5节），才是不可破的（给出无限多的资源仍然不可破）。所有其它的密码系统在唯密文攻击中都是可破的，只要简单地一个接一个地去试每种可能的密钥，并且检查所得明文是否有意义，这种方法叫做蛮力攻击（见7.1节）。
密码学更关心在计算上不可破译的密码系统。如果一个算法用（现在或将来）可得到的资源都不能破译，这个算法则被认为在计算上是安全的（有时叫做强的）。准确地说， “可用资源”就是公开数据的分析整理。
你可以用不同方式衡量攻击方法的复杂性（见11.1节）：
1．数据复杂性。用作攻击输入所需的数据量。
2．处理复杂性。完成攻击所需要的时间，这个经常叫做工作因素。
3．存储需求。进行攻击所需要的存储量。
作为一个法则，攻击的复杂性取这三个因数的最小化，有些攻击包括这三种复杂性的折中：存储需求越大，攻击可能越快。
复杂性用数量级来表示。如果算法的处理复杂性是2128，那么破译这个算法也需要2128次运算（这些运算可能是非常复杂和耗时的。）。假设你有足够的计算速度去完成每秒钟一百万次运算，并且用100万个并行处理器完成这个任务，那么仍需花费1019年以上才能找出密钥，那是宇宙年龄的10亿倍。
当攻击的复杂性是常数时（除非一些密码分析者发现更好的密码分析攻击），就只取决于计算能力了。在过去的半个世纪中，我们已看到计算能力的显著提高，并且没有理由认为这种趋势不会继续。许多密码分析攻击用并行处理机是非常理想的：这个任务可分成亿万个子任务，且处理之间不需相互作用。一种算法在现有技术条件下不可破译就简单地宣称该算法是安全的，这未免有些冒险。好的密码系统应设计成能抵御未来许多年后计算能力的发展。
过去的术语
历史上，将处理语言单元的密码系统称为密本：字、短语、句子等。例如，单词 “OCELOT”可能是整个短语“TURN LEFT 90 DEGREES，”的密文，单词“LOLLIPOP”可能是“TURN RIGHT 90 DEGREES”的密文，而字“BENT EAR”可能是“HOWITZER”的密文。这种类型的密本在本书里没有讨论。密本在特殊环境中才有用，而密码在任何情况下都有用；密码本中若没有“ANTEATERS“这一条，那么你就不能提它。但你可以用密码来指代任何东西。