第12章 密码学介绍从前－大约在十年以前，你可能听说密码编码学（cryptography）对计算机安全没有作出什么贡献。计算机安全是关于TCBs（可信计算基）的、引用监控、自主型和强制访问控制、安全模型和系统规范的形式验证。按照这种观点，密码所起的作用实际上是外围的。在安全操作系统当中，存储口令的单向函数仅仅是密码机制的一个明显的实例。
现在，倾向性却走到了另外一个极端。密码被看成了将解决所有计算机安全问题的神奇的对策。安全操作系统由于太昂贵、使用太受限制和太远离用户的要求，而作为过去的事不再考虑，它最终像恐龙绝迹一样消亡。密码能够提供这样重要的承诺吗？
目标
·了解由于不同的目的使用密码的各种各样的应用。
·对密码学基本概念的介绍。
·理解密码能够解决问题的类型，在使用密码时需要解决的问题的类型。
·指出要求支持密码的计算机安全的特征。
12.1 简介密码编码学（cryptography）是书写秘密内容的学科，密码分析学（cryptanalysis）是破解加密器（cipher）的学科，这两个主题就形成了密码学(Cryptology)。它们曾经是间谍和秘密部门的领域，由于这些原因，现在仍然给密码罩上一层神秘的面纱。
现代密码学完全是一门数学的学科。对于很好地理解密码学出色的观点所必需的数学背景的阐述已经超出了本书的范围。我们将尽力解释怎样把密码编码学用于计算机安全，并且指出计算机安全常常是加密能起作用的一个先决条件。
12.1.1 老的范型（paradigms）
密码在通信安全中有它自己的根源。通信安全解决了在图12.1中描述的情况。两个实体A和B通过一个不安全的信道通信。对抗者是一个入侵者，他可以完全控制这个信道，能够读他们的消息，删除消息或者插入消息等。两个实体A和B是彼此信任的。他们想保护通信不受入侵者的破坏。密码使得他们在不安全的物理连接上建立一条安全的逻辑信道。
图12.1 通信安全
在这方面，密码与到目前为止讨论的计算机安全机制是有本质区别的。对于来自底层的危害，它们全部都是脆弱的。然而，对物理通信链路的访问却不能威胁密码的保护。
在分布式系统中，客户和服务器之间的通信流对一个以入侵者自诩的人来说是一个新的攻击点。不安全通信链路引入的脆弱性自然能够由通信安全服务和机制来解决。这些服务包括：
·数据机密性,加密算法隐藏了消息的内容；
·数据完整性,完整性检测功能提供了检测文档是否被改变的方法；
·数据源认证,消息认证码或者数字签名算法提供了验证消息来源和它的完整性的方法。
在我们的定义中，数据完整性实际上不是适合通信安全的的概念。消息就基本性而言总是有一个发送者。如果你接收到一个消息，但不知道谁发送了它，你怎么能够断言它在传输过程中并没有被修改呢？因此，当你没有验证消息来源的时候，就无法验证它的完整性。另一方面，你不应该声称已经验证了在传输过程中已被更改了的消息的来源。因此，数据来源认证包括消息完整性认证，并且我们的数据完整性的概念，更适合于应用而不是通信，比如，反病毒软件的文件保护。
谁是朋友，谁是敌人这种传统的观点也在计算机安全中有了它自己的位置，但它不再是驱动计算中密码应用的主要理由。不幸的是，它仍然支配着公众对密码的理解。同样的观点也反映在用于密码协议的许多验证工具的公理上，它们假设实体A和B的行为与协议规则完全一致，并且只考虑入侵者行为的影响。
12.1.2 新的范型让我们关注新鲜的事物。在电子商务中，顾客进入了一个与商家有关的商业事务。两个参与者都不希望另一方欺骗，但是，纠纷却有可能发生，并且预先有一致的规则总比在发生纠纷时再采取特定的方式解决要好些。顾客和商家都有运行一个协议的理由，协议并不假设对方在任何环境下都是可信任的。现在的对抗者是一个误操作的内部人员，而不是一个入侵者，在图12.2所示的第三个参与者不再是一个入侵者，而是一个可信任的第三方（TTP），例如，一个仲裁者。在解决纠纷的时候，不可否认（non-repudiation）服务生成了在解决争端时仲裁者将要考虑的证据。
图12.2 电子商务安全
许多国家都有法律，规定法律执行代理（LEA，law enforcement agent）在什么时候、怎样获得侦听许可证，以便责成电信服务提供者给他们接入到特定用户之间的通信的权利。现在，在图12.3中的第三方是一个通信操作员的客户，必须给他提供一个合法的侦听服务。在这种上下文中，密钥托管服务分发用于加密通信的密钥；密钥托管服务也是目前令人激动的研讨课题。
图12.3 通信安全和法律实施
12.1.3 密码的密钥密码员采用锁作为他们特别喜爱的图标，以表示他们给公众提供安全服务。快速查看目前的允许安全的Web浏览器或者e-mail产品的用户接口就能够证实这种观察。但是类推充满了危险，你不应该过分地信任它们，但是也有一些重要的概念从锁匠传承到了密码员。锁上门或者打开门上的锁，你需要一把钥匙。从强度上分，锁是不同的。有些很容易撬开，而其他的锁是如此坚固，以致入侵者不得不采用蛮力攻击破门而入，或者选择一条完全不同的路径，并且改为从房间的窗户进入房间。
密码算法使用密钥来保护数据。从实现方法的强度和范围来看又有各种变种，其中的一些使用简单的统计方法就可以破解，而另外一些远远超出了目前的数学分析和计算能力所能够达到的范围。蛮力攻击穷尽一切可能地搜索整个密钥空间，它给出了算法强度的上限。
现代密码系统并不依赖于算法的保密。在密码变换中使用的密钥才是唯一需要保护的内容。这个原则是在上个世纪由Kerckhoffs提出并作为基本条件的，在我们的新安全范型中是非常适用的，在这里必须支持大量具有竞争利益的用户团体。在这种环境下，形成事实上的标准和对公开算法的开放评估都是很自然的过程，使得每一个参与者都有机会进行他们自己的安全评估，使新的参与者更容易加入。
因而，从最一般的字面意义上理解，密钥管理对密码机制的安全是极为重要的。你必须处理下面这些问题：
·密钥在哪儿生成？
·密钥怎样生成？
·密钥在哪儿存储？
·密钥怎样分发？
·密钥实际上在什么地方使用？
·密钥怎样撤销和替换？
在这一点上，圆是闭合的，我们又回到计算机安全。密码密钥是存储在计算机系统中的敏感数据，计算机系统中的访问控制机制必须保护这些密钥。当访问控制失败时，密码保护受到了威胁。在大多数目前实施的安全系统中，密码算法是最强的部分，且老谋深算的攻击者将寻找其他的脆弱性，而不是把他们的时间浪费在密码分析上。
密码对安全问题来说，在任何时候都是一个罕见的解决方案。密码是一个变换机制，它通常把通信安全问题转化为密钥管理问题，而最终转化成了计算机安全问题。希望最后的问题比原来的问题更容易解决。总之，密码能够加强计算机安全，但它并不是计算机安全的替代品。
12.1.4 模运算相当多的现代密码算法都建立在代数学原理的基础上。这些算法可以定义在令人兴奋的代数结构上，比如椭圆曲线或者伽罗瓦域（有限域）。然而，我们仍然有点停留在实际应用上，且在它们描述中仅使用整数。在这里，我们将解释一些关于模运算的基本知识，作为后面描述内容的基础。
令是一个整数。在后面的描述中，我们将称为模数（modulus）。然后在整数集合上定义了一个等价关系‘’：
，当且仅当，这里，是某些整数，
我们则说“等价于以为模”。你可以检验‘’确实是一个等价关系，它把整数集合划分成关于的个等价类：
我们更习惯用的形式来表示等价类，我们将遵循这个约定。你可以证明下列有用的性质：
除此之外，对于每一个，是素数，存在一个整数，使得。对于一个素模数，以为模的乘法阶定义为：
定义 令是一个素数，是一个任意整数。模的乘法阶定义为满足下面关系的最小整数：
费尔马小定理 对于每一个，是素数，有。
这个定理表示，任何一个以为模的非零元素的乘法阶必定是的因子。这个事实被用于构造相当多的密码算法。这些算法的安全性常常是相关的，在少数场合是等价的，来自数论中的下述问题中的任何一个都是难解的：
·离散对数问题（DLP）,给定一个作为模的素数，基数和值，根据等式，求出的离散对数。
· n次方根问题,给定一个整数，和，求出一个整数，使它满足。解就叫做模的n次方根。
·因式分解问题,给定一个整数（合数），找出它的素数因子。
在参数的正确选择情况下，这些问题是许多密码算法的合适的基础。然而，并不是这些问题的所有实例都是难解的。很明显，如果或者是比较小的整数，那么这些问题就可以在合理的时间范围内采用穷举搜索来求解。目前，二进制512位的整数已被认为是位数较短的整数了，一般都推荐使用1024位整数，当然，如果你能够容忍由于算术运算占用更长的时间而引起性能的下降，你可以使用更长的整数。长度不是你必须考虑的唯一方面。这些问题的难度也依赖于和的结构。（为了进一步追究这个课题，你必须放下这本书，而寻找一些更专业化的数学方面的书籍来阅读。）
12.2 密码机制密码机制是密码方案的最基本的构造模块。它们被用在密码协议中，且依赖于好的密钥管理来提供有效的保护。最频繁应用于计算机安全的密码机制是：
·加密（encryption）算法，
·数字签名（digital signature）方案，
·完整性检查功能（密码散列函数，即hash函数）。
为了舍弃传统密码，我们将以相反的顺序来介绍这些概念。
12.2.1 完整性检查功能依赖于特殊应用的需求，对密码散列函数的要求也有一些微妙的差别。我们列出了散列函数的一些基本性质，由此来展开这一节的讨论：
·容易计算,给定，容易计算。
·压缩：对于任意输入长度的，函数最后都生成固定长度的输出。
·预映射抗拒性（单向性）,给定一个值，为了找到满足，通常在计算上是不可行的。
·第2次预映射抗拒性（弱冲突抗拒性）,给定输入和，求出另外一个，且,使得，在计算上是不可行的。
·冲突抗拒性（强冲突抗拒性）：求出任何两个输入和，使得成立，在计算上是不可行的。
操作检测码（manipulation detection codes,MDCs），也称为修改检测码或者消息完整码，常常用于检查文档是否发生改变。在文献[99]中提到了两种形式,
·单向散列函数（OWHF）具有压缩性、易计算性、预映射抗拒性和第2次预映射抗拒性等性质。
·冲突抗拒散列函数（CRHF）具有压缩性、易计算性、第2次预映射抗拒性和冲突抗拒性等性质。
应用散列函数计算的结果分别不同地称为：：
·散列值（hash value）
·消息摘要（message digest）
·校验和（checksum）
最后一个术语为混淆留下了巨大的空间。在通信安全中，校验和是指错误校正码，典型的是循环冗余校验码（CRC）。另一方面，校验和也被用在反病毒软件的产品中，但是禁止使用CRC来计算，而必须使用密码散列函数（MDC）来计算。令是被禁止篡改的程序。在一个没有病毒的环境下计算散列值h(x)，并且把结果存储在不能修改它的位置，例如，存放在CD-ROM上。为了检查程序的状态，重新计算散列值，把它与原来存储的值进行比较。散列值的保护是重要的。计算散列值并不要求任何秘密的信息，因此，任何人都能对一个给定的文件计算有效的散列值。
当参数和明智地选择时，函数是一个单向函数，这个函数称为离散求幂。为了反向离散求幂，你必须解决在12.1.4节介绍的离散对数问题。在这一章的后面你可以看到离散求幂在密码方案的构造中是真正有用的原函数。然而，离散求幂并不是特别快的操作，当你需要高速处理大量的数据时，你必须转而采用其他的算法。
快速散列函数倾向使用类似的设计模式来构造。散列函数的核心是一个压缩函数，它处理固定长度的输入。一个任意长度的输入被分割成给定块大小的块、…、，如果最后一个块没有达到固定长度，就使用填充的方法使它达到固定的长度。的散列值则可以通过反复的使用压缩函数获得。令是一个（固定的）初始化值。计算
，，
且取作为的散列值，如图12.4所示。（符号||表示级联）
消息认证码（MACs）对消息的来源和完整性提供了保证（数据源认证）。MAC从两个输入即消息和秘密的密码密钥计算得到。因此，MAC有时也叫做密钥散列函数。正式地说，MAC是用密钥作为参数化的散列函数的族。这个族中的每一个成员都具有压缩和容易计算的特性，附加的抗计算特性也必须满足。
对于任何固定的值，给定一个值集合，当攻击者不知道这个固定的值时，对任何新的输入，在计算上来说，要计算出是不可行的。
为了认证一个消息，接收者必须与发送者共享密码密钥，用来计算MAC。不知道密钥的第三方不可能确认MAC。使用下面的HMAC构造方法，一个MAC算法则可以从MDC算法推导出来。计算
其中和是填充的位串，它把扩展成在中使用的压缩函数需要的长度。
图12.4 hash函数构造
安全散列算法我们将选择安全散列算法（SHA-1）来说明散列函数实际上是怎样设计的。这个算法被指定用于美国的数字签名标准（DSA）。其他的散列函数是MD4（不是那么强有力的）、MD5（Internet协议中的标准选择）和RIPE-MD。SHA-1处理任意多个512位的数据块，生成一个160位的散列值。参数可以被作为整数解释也可以作为位串解释。在位串和整数之间的转换算法在我们的描述中省略掉了。
输入的末尾将用一个1来填充，然后是一个0串，以使得最后的输入块有448位长度，且最后64位字段指示在填充前输入数据的长度。初始化的值由五个32位的值定义，以十六进制数表示：
A=67452301
B=efcdab89
C=98badcfe
D=10325476
E=c3d2e1f0
SHA-1的压缩函数在一个80步的循环中处理512位的输入，每20步改变一次内部函数和常数，最后生成一个160位的输出。这些函数是：
，
，
，
。
其中，操作符是位与、位或和异或，应用到32位字上去。常数采用十六进制数表示，它们是：
，
，
，
。
在压缩函数开始的时候，五个32位的变量、、、和是用散列函数的中间值来初始化的。对于第一个输入块，则使用初始值、、、和。512位的输入块被分成了16个32位的字，并且使用下面的算法，将它们扩展成80个32位的字：
，
，
其中，符号表示循环左移位。现在压缩函数执行下面的循环，其中加法使用模运算：
for t=0 to 79 do
begin
temp=(a<<<5) + ft(b,c,d) +e+wt+kt;
e=d;
c=b<<<30;
b=a;
a=temp;
end;
最后，变量、、、和的值被加入到前面的中间散列值中。在处理下一个输入块的时候，这个结果用作初始的散列值。
12.2.2 数字签名在图12.1中，消息认证码帮助参与者A和B检测在通信信道中由入侵者插入的欺骗消息。然而，消息认证码并不生成任何证据，供第三方用来判断A或者B是否发送了特定的消息。因此，在图12.2的电子商务中，顾客需要确保商家不能伪造订单，且商家需要确保顾客必须认可他们所下的订单，在这样的情况下，消息认证码几乎是没有什么用处的，因而数字签名就很有必要了。
数字签名方案由签名算法和验证算法组成。一份文档的数字签名是一个值，它依赖于文档内容和仅由签名者知道的某个秘密，即私有签名密钥；私有签名密钥把文档与一个实体联系在一起，即公开的验证密钥。验证算法通常使用文档和公开验证密钥作为输入，但是在一些异常的情况下，文档或者文档的一部分可以从签名中恢复出来，且对于签名验证不一定要提供文档。下述的可验证特性表示了数字签名方案的特征：
规则 第三方可以在不知道签名者的私有密钥的情况下，解决关于数字签名有效性的纠纷。
数字签名支持不可否认性。公开密钥密码（见12.2.3节）是数字签名方案的自然来源。在这种方案中，私有密钥和公开验证密钥之间的联系，是为了确保从验证密钥中推导出签名密钥在计算上是不可行的。不管在数学基础上的相似性，你应该推断出数字签名和公开密钥加密算法之间清楚的区别。这两种方案从根本上满足了不同的技术目的。加密保护了消息的机密性，因此必须是可逆的。数字签名提供了数据来源的认证和不可否认性。数字签名算法不必是可逆的，事实上，可逆性会引起一些附加的安全担心。
一次性签名你不需要为构造一个签名方案而钻研数学。为了获得一次性签名，你仅仅需要一个密码散列函数就可以了[81]。为了对一份n位的文档签名，随机选择2n个值的和作为你的私有密钥，且公布和，，作为你的公开密钥。对文档的签名的第部分则由下式给出：
很明显，你不能再次使用你的私有密钥，因此，这就是一次性签名的由来。验证者拥有你的公开密钥，并进行检查：
你将发现，验证者需要附加的证据来进一步证实数值和确实是你的公开密钥。我们将在12.4节回到这个主题。
此外，除了依赖数学问题的难解性或者依赖其他的一些密码原函数的强度，你还可以依赖抗损害硬件设备的难度。这个设备包括一个秘密的签字密钥和/或者秘密的验证密钥。这个设备是这样构造的，以至它不能使用签名密钥来验证或者用验证密钥来签名。为了签名一份文档，设备使用它的签名密钥构造MAC，然后把它附加到文档上。为了验证这个签名，验证者的设备必须拥有签字者的签名密钥作为验证密钥，用这个密钥来生成MAC，把它同接收到的签名进行比较。
EIGamal签名和DSA
在文献[45]中的EI Gamal签名方案用实例说明了签名不是用私有密钥加密。令是一个大的和适当选择的素数。令是以为模的阶为的整数。令是用户A的私有签名密钥，且是对应的公开验证密钥。
假设要签的文档是一个整数，。另外，你也可以应用一个合适的散列函数，然后对文档的摘要进行签名。为了对进行签名，用户选择了一个随机数，，以使得，计算，并且解方程：
求解未知的。整数对构成A对的签名。验证者需要A的验证密钥，并检查：
对于一个正确的签名，等式：
也是成立的。这种方案的安全与离散对数问题紧密相关，但是并不等价于离散对数问题。许多更安全和更有效的签名方案都是从EI Gamal签名方案派生而来的。一个这样的签名算法是数字签名算法（DSA，digital signature algorithm）[116]。在这个方案中，用户A的私有密钥和公开密钥通过下述步骤生成。
1）选择一个素数，。
2）选择一个整数，，和一个素数，，所以整除。
3）选择，，并计算。如果，用一个新的再试。（这一步计算以为模的阶的生成元。）
4）选择一个，使其满足。
5）计算。
6）A的私有密钥就是数值，公开密钥是。
A为了对文档进行签名，使用SHA-1计算散列值，并且转换成一个整数，然后：
7）随机地选择一个整数，。
8）计算。
9）计算。
10）计算。
A对的签名就是整数对。这个签名将用A的公开密钥进行检测：
·验证和
·计算
·计算和
·计算
·当且仅当，则通过验证。
RSA签名在文献[127]中描述的RSA算法是用它的发明者Rivest、Shamir和Adleman的第一个字母命名的，它同样可以用于签名和加密。RSA的这种特定的性质必须对许多关于数字签名和公开密钥密码的流行的误解负责。在RSA签名方案中，用户A选择两个素数和，和一个私有签名密钥，满足和。公开验证密钥则由积和指数组成，并且满足
,lcm(p-1,q-1)是欧拉商数。
签名的文档是整数，。为了验证者能识别真正的文档，这个文档必须包含足够的冗余信息。如果原始文档太长，可以应用散列函数和填充获得摘要进行签名。为了签名，用户A用下式生成签名：
验证者需要A的验证密钥，并且检查
是否成立。对于一个正确的签名来说，这个等式是成立的，因为
短文档可以从签名中恢复，并且不必分别传送。RSA安全与因式分解的难度是相关的，但是并不等价于它的难度。
在某些签名方案中（RSA是基本的范例），你可以选择公开验证密钥，因此签名验证特别快。图12.5中的表给出了对于1024位参数运行在相当快的机器上的DSA和RSA的性能的粗略比较，以及一个签名方案的不同部分要求的工作的比较。（信息由在KU leaven 的ESAT提供。）
图12.5 RSA同DSA的比较
12.2.3 加密我们保留了术语加密（encryption），它表示保护数据机密性的算法。加密算法，也叫做密码（cipher），在密码密钥的控制下，将明文（plain text或clear text）加密成密文（cipher text）。用适当的解密密钥解密（decryption），可从密文中恢复明文。有些加密算法提供了检测违反完整性的方法，但情况不总是这样。你甚至可能注意到签名算法被描述为使用私有密钥的加密，但是，这种说法常常是不正确的，并且总是误导。我们将使用在10.2.1节中所用的表示法：
·，表示用密钥加密明文；
·，表示用密钥解密密文。
加密算法以两种形式出现。在对称加密算法中，加密和解密使用相同的密钥，这个密钥必须保密。所有的参与者共享同一密钥，他们可以阅读彼此的加密数据。为了对不同参与者建立专用信道，对每个信道你需要一个新的密钥。维护大量的共享秘密密钥可能成为一种十分繁重的管理任务。
非对称加密算法，也叫做公开密钥算法（public key algorithm），加密和解密使用不同的密钥。加密密钥可以公开；解密密钥仍然是私有的，必须保密。很明显，这两个密钥在算法上是相关的，但是想要从公开密钥导出私有密钥必须是不可行的。为了区分对称密码系统和公开密钥密码系统，我们在对称密码系统的上下文中使用秘密密钥，而仅仅在非对称密码系统的上下文中使用私有密钥。
对于秘密密钥密码系统，使正确的密钥存放在合适的地方，这种安全管理任务是很明显的。而公开密钥密码系统看来使管理容易得多。毕竟，公开密钥是公开的，且不需要保密。当你使用公开密钥加密算法加密一份文档的时候，你可能需要知道谁能够阅读这个加密后的文档。更一般地说，私有密钥可能授权给委托人或者用作携带访问权限的能力，例如，读一份文档。现在，保证在公开密钥和访问权限或者与对应的私有密钥联系在一起的委托人之间的联系是一项主要的任务。证书（certificate）常常用来为这种特殊的目的服务。在12.4节，我们将回到这个主题。
加密算法也可以分成块密码和流密码。存在区分它们的两个标准。
·块尺寸,块密码加密较大的数据块，典型的是64位的块，使用一个复杂的加密函数。块密码的安全依赖于加密函数的设计。流密码加密较小的数据块，典型的是位或者字节，使用一个简单的加密函数，例如，按位异或运算。正如你想象的一样，这种区分在边界处就变得模糊不清了。一个16位的块仍然是一个大的块吗？一个加密算法什么时候是简单的？
·密钥流,块密码使用同一密钥来加密属于同一文档的所有的块。而流密码借助连续变化的密钥流加密整个文档。流密码的安全依赖于密钥流生成器的设计。在这种定义下，使用反馈模式的DES(见下文)属于流密码范畴。
数据加密标准DES
数据加密标准（Data Encryption Standard，DES）是对称块密码算法中的经典。DES是在二十世纪七十年代开发的，作为美国政府保护非机密信息的标准，并且作为联邦信息处理标准发布[114]。DES在56位密钥控制下对64位明文块加密。每一个密钥通过一个奇偶检验字节扩展到64位工作密钥。与大多数的块密码一样，DES是基于Feistel 原理的。Feistel密码在大量的循环中迭代相同的基本步骤。第轮的数据被划分成左半部分和右半部分，各32位，而输出采用下式计算：
其中是某种非线性函数，是在这次循环中的子密钥，如图12.6所示。这个操作的逆过程可以通过同样的路线来进行：
图12.6 Feistel原理在DES中的非线性函数将32位输入扩展成48位的块，然后与48位的子密钥进行位的异或运算。这个中间结果划分为8个6位的块，它用作8个盒（substitution boxes，替换盒）的输入。每个盒将6位的输入转换成4位的输出。盒的输出通过一个盒（permutation boxes，置换盒），它对32位的输入执行位排序，给出函数的结果。
DES要进行16轮（round）这样的运算。每轮都使用不同的48位子密钥，这个子密钥是从56位的DES密钥衍生出来的。第一轮的输入是由初始化置换处理的，最后一轮的输出再进行一次逆置换，。图12.7给出了DES的示意图。我们省略了密钥编制表的算法、扩展方案、盒和置换的所有细节。
二十世纪七十年代当DES变成了标准的时候，它得到了十五年的适用期。DES很可能已经老化了，但仍然在广泛使用，特别在商务和金融领域。对DES安全的主要挑战不是来自新的密码技术，而是来自它的密钥大小。今天，不需要专用设备，对56位密钥空间的穷举搜索已经很容易了。工作站的性能正逐年增长，网络使得业余密码分析者可以使用更多的资源。在这样对抗的环境下，你只能指望一个56位的密钥能够生存几个星期或者几个月，而不是几十年或者几个世纪。多重密码扩展了密钥的大小，而不必改变算法。推荐的选择是使用了三个56位密钥的三重DES。有一种变异很受欢迎，因为它保持了与单一的DES的向后兼容性，使用两个56位DES密钥和，按下式对明文进行加密：
图12.7 DES算法块密码模式块密码可以用于各种各样的加密模式。在电子密码本（ECB）模式中，每个明文块都用相同的密钥独立加密。这种模式可能泄漏关于明文的信息。如果一个明文块是重复出现的，这种重复性也会出现在密文中。而且，完整性保护非常有限。解密不检测密文块的顺序是否已经改变，有些块是否已经丢失，或者有些块是否已经被复制。
在图12.8中的密码块链（CBC）模式中，前面的密码块在加密前被加到（按位异或）下一个明文块，即：
。
因此，重复的明文块不会作为重复的密文块表现出来。对于第一个明文块，用作初始化向量。这个初始化向量通常是保密的，尽管在很多的应用中，这并不是必须的安全条件。每一个消息的初始化向量都应该改变，以确保观察者不能检测到两个明文始于相同的块。初始化向量也被用来解密第一个密文块。密文块使用下式进行解密：
如果一个密文块被破坏了，这种损坏将被限制在两个明文块中。假设用来代替了，在下列运算后：
正常的解密服务又恢复了。
图12.8 密码块链模式输出反馈模式（OFB，见图12.9）使用块密码作为流密码的密钥流生成器。在这个模式中，可以处理小于密码算法所要求的块尺寸的明文块（chunk）。给加密函数的输入存储在寄存器中，这个寄存器的初始内容由初始化向量来确定。为了加密一个明文块，把寄存器内容加到加密函数输出的一个子块中（按位异或）。加密函数的输出则被反馈到了移位寄存器。解密过程与加密完全相同。初始化向量对每个消息都必须改变，但是不需要保密。在密文块传送中的错误仅仅影响到对应的明文块。因此攻击者可能通过在对应位置改变密文块来选择性地修改明文块。
图12.9 输出反馈模式
图12.10 密码反馈模式密码反馈模式（CFB，见图12.10）使用块密码来生成与数据相关的密钥流。并且，明文可以在比密码算法要求的尺寸小的情况下进行处理。在这种模式中，先前的密文块被反馈到一个移位寄存器。这个寄存器的内容被加密，且这个密文的子块将被加到下一个明文块中（按位异或）。解密过程与加密相同。在这种模式中，初始化向量对每个消息都必须改变。初始化向量要求用来解密第一个密文块，不必保密初始化向量。密码块的传输错误或者更改将影响解密，直到改变的块从移位寄存器中移出，移位寄存器内容在接收端馈给加密函数。
RSA加密从RSA签名方法中我们已经熟悉这个方案的基本结构了。当RSA用于公开密钥加密算法时，用户A选择两个素数和，一个私有解密指数，满足和。公开加密密钥由积和指数组成，满足
消息必须被分成块，使得每个块都是一个小于的整数。为了发送一个消息块到A，发送者计算：
接收者A使用私有解密密钥以获得：
。
EI Gamal加密
在EI Gamal公开密钥算法中，仍是一个大的且适当选择的素数，且令是一个以为模的高阶整数。令是用户A的私有解密密钥，且是相应的公开加密密钥。消息被划分成块，使得每个块都是一个小于的整数。为了发送一个消息块给A，发送者选择一个随机数，计算，发送如下密文：
给A。A使用其私有解密密钥，可以获得：
在这种方案中，密文块长度是明文块的两倍。另一方面，如果两个明文块是相等的，相应的密文块却是不相同的。随机数仅仅用于加密一次。随机数的重复使用会严重地削弱密码的强度。
12.3 密钥建立协议在一个密码算法可以使用之前，所有的密钥必须存放在正确的地方。当然，密钥可以通过邮政系统邮寄信的方式获得，这是一种通常用的分发信用卡的PIN（个人身份识别码）的方式，或者通过信使在站点之间传递和发放密钥。这些提议或者不是很安全或者很不经济。比较理想的方式，我们希望在已有的通信设施基础上实施密钥管理任务。通过其他协议建立使用密钥的密码协议称为密钥建立协议。
这些协议中的一些仅仅涉及想要设立一个共享密钥的参与者；其他的则要求一个可信第三方的服务。为了区分这两种情况，你必须查阅：
·密钥协商协议：密钥在没有第三方帮助的情况下建立。
·密钥传输协议：密钥由第三方生成和分发。
密码协议的数学细节分析常常揭示了一个弱密钥子集的存在，该集合中的密钥会允许内部人员进行欺骗。因而在设计一个密钥交换协议的时候，你应该回答两个问题：
·如果建立了弱密钥，哪一方将受损害？
·哪一方可以控制密钥的选择？
如果误操作的内部人员可以影响密钥的生成，以致选择了一个弱密钥，则可能存在内部攻击的目标。
现在，研究文献给你提供了广泛的密钥建立协议的选择。我们将提出两种原型协议，它们对密钥建立协议的设计有主要的影响。
12.3.1 Diffie-Hellman协议
Diffie-Hellman协议是一个密钥协商协议[41]。没有共享秘密的两个参与者A和B构造一个共享的秘密密钥。令是一个适当选择的大素数，是一个以为模的高阶元素。A方选择一个随机数，发送到B。B方选择一个随机数，发送到A，并且计算。在接收到后，A使用它自己选择的秘密来计算。因为：
双方则共享了秘密。这里留下了一个小小的问题，任何一方都不知道它和谁共享了这个秘密。为了保证初始的信任，在这个协议中必须加入认证。在文献[42]中的站到站协议解决了这个问题，如下所述。除了建立共享会话密钥的Diffie-Hellman交换外，这个协议使用一个加密算法和签名算法。这里没有规定特定的算法。在下面的描述中和分别是A和B的签名密钥，和表示使用这些密钥产生的签名。在协议中的步骤是：
步骤1 A→B：
步骤2 B→A： ，
步骤3 A→B：
在步骤1，A选择一个随机数，并初始化Diffie-Hellman密钥交换。B接收到以后，选择一个随机数，并计算会话密钥。在步骤2以后，A可以完成它的Diffie-Hellman密钥交换部分，获得会话密钥，然后解密B的消息的第二部分，验证B的签名。在最后一步之后，B可以解密并验证A的签名。
12.3.2 Needham-Schroeder协议
Needham-Schroeder协议是一个密钥传输协议[110]。两个参与者A和B从服务器S那里获得会话密钥。起初，双方都与服务器共享秘密密钥。对称密码用来进行加密，序列号（nonce，随机的复杂问题）包含在消息中以便防止重放攻击。下述的约定使用在协议的描述中：
由A和S共享的秘密密钥
由B和S共享的秘密密钥
由S生成的，用于A和B之间的会话密钥
， 分别由A和B生成的序列号（nonce）
图12.11说明了在A方从服务器S请求一个用于和B通信的会话密钥时所发生的步骤。
步骤1 A→S： A，B，
步骤2 S→A：
步骤3 A→B：
步骤4 B→A：
步骤5 A→B：
在协议的前三步中，A从S获得了会话密钥，并把它转发给B。通过检查在服务器消息中返回的序列号，A可以验证会话密钥已经发出，以响应它最近的请求，而不是对一个先前运行的协议的重放。在最后两步中，B验证了A当前正在使用同一会话密钥。Needham-Schroeder协议安全的详尽分析和更多安全变型的讨论超出了本书的范围。
图12.11 Needham-Schroeder协议
12.4 证书在站到站协议描述中，一个重要的细节被省略了。A和B怎样知道他们用来检测签名的验证密钥恰好对应着正确的一方？在这里必须存在一个可靠来源，它把密码密钥与身份联系起来。在对称加密情况下，参与者A和B信任创建连接的服务器。公开密钥密码和签名方案常常依赖于证书（certificate）。证书管理机构（certification authority，CA）通过签署一个文档来保证用户和密码密钥之间的联系；这份文档包括用户名、密钥、CA的名字和过期日期等。现有几种提议规范了证书的精确的格式，最著名的是在X.509的目录框架结构[27]中使用的证书。这些格式在某种程度上在它们所包含的域（以及各个域的长度）方面不同。在有效的证书处理和对很大范围应用的灵活支持之间的工程平衡是不应该令人感到惊讶的。
把名字和密码密钥绑定在一起的证书在通信安全中有它们的起源。用户想知道他们正在和谁通话。在计算机安全中，它常常更关心一个调用者的访问权限，而不是调用者的身份。当然，你可以使用证书来认证调用者，然后使用调用者的用户名来建立访问权限。然而，你可以取代中间人，而在证书中包含访问权限。相应的私有密钥则有安装在证书中规定访问权限的能力。在这种情况下，你不用检查证书来确认用户的身份。倒不如说你认证一个能力（capability）。
像用户身份一样，证书也被用作两种用途。它们可以标识与密码系统密钥联系在一起的实体或者它可以规定给予密码密钥的拥有者的访问权限（并不鉴别拥有者的身份）。
为了验证一个证书，你需要验证密钥来检查CA的签名。CA的验证密钥可以由另外一个CA来保证。因此你需要另外一个验证密钥，另外一个证书等等。存在关于最适合的证书层次结构组织的热烈争论。在这个领域的一端，X.509目录框架结构以完美的形式把证书安排在一棵有统一的根证书的目录树中。在另一个极端中，PGP（Pretty Good Privacy）证书基于一个推荐的系统，且根本不需要CA。最终，在表面意义上你必须信任验证密钥。你可以从朋友那里接收这个密钥，或者从你的老板、从你的Web浏览器、或者在书本范围外获得密钥。如果你非常谨慎，在信任这个密钥之前你可以参考几个来源。关于证书废除的相关问题已经在第十章中讨论过了。
最后，密码保护一定要建立在非加密的基础上。
12.5 密码机制的强度度量密码算法的强度是一门不精确的艺术，有时建立在牢固的数学基础上，其他时候又依赖于直觉和经验，一个密码算法可以是：
·经验安全（empirically secure）
·可证明的安全
·无条件安全如果一个算法已经经受住了时间的检验，那么我们说它是经验安全的。长期的分析没有发现什么严重的缺陷，虽然没有证明该算法不会最终受到一个新的或者有创造才能的攻击，并且算法已经在密码学界范围内被广泛接受。DES是一个经验安全的最好的例子。新的分析方法，比如差分密码分析学，已经加强而不是削弱了感知到的DES安全。
可证明的安全算法，似乎提供了计算机安全一直渴望的东西，即可证明的安全。可证明的安全是在复杂理论的框架结构内表示的。如果破解一个算法至少和解决另外一个问题一样的困难，而另外一个问题我们已经知道它几乎是不可解的，那么我们就说这个算法是可证明安全的。这个听起来很好，但是阅读这些限制性附属细则是值得的。
“至少一样困难”是一个渐近的概念，对于“足够大”的问题实例它是成立的。然而，这个理论不会告诉你什么是足够大的。相反，你必须评估目前的计算设备的能力和算法设计的进展情况。例如，我们能够进行因式分解的数的大小在近几年中不断地增长。你会同意这是一个经验论点。甚至更坏的情况来了。密码系统特别偏爱的难解问题是因式分解和离散对数问题。现在并没有实际证明这些问题一定是难解的。又一次地，密码系统依赖于经验论证，到目前为止没有找到快速算法，因此极不可能有大的突破。为了更加肯定，这个观念也导致了建设性的结果，相对于破解其他的密码原型函数的难度，它给出了破解一个密码方案所要求的工作的下界。
可证明的安全算法可被拥有足够多计算资源的攻击者攻破。当然，你可以希望这些必需的资源超出了任何攻击者的能力。无条件安全算法不能被攻破，即使攻击者应用无限的计算能力。无条件安全是在按照信息论的概念来表示的。如果一个攻击者从观察密文没有获得关于明文的附加信息，则这个算法就是安全的。
无条件安全算法的标准例子是一次一密算法。发送者和接收者共享一个真正的随机密钥流，这些密钥只使用一次。密文是明文和密钥流的按位异或运算的结果。接收者采用相同的密钥流对密文进行按位异或运算，这样可以从密文中恢复出明文：
ciphertextkey streamplaintextkey streamkey streamplaintext。
因为每个密钥都是等概率的，攻击者不能猜测到关于明文的任何信息，在看到密文以前不可能对明文有任何的猜测。
注意！即使无条件安全的密码也已经被破解。当操作者抄近路和两次使用相同的密钥流时，攻击者叠加这两个密文将看到两个明文的组合：
ciphertext1ciphertext2
plaintext1key streamplaintext2key stream
plaintext1plaintext2。
理解两个覆盖在一起的明文消息完全不是一个困难的密码分析问题。Venona工程证明这样的事件甚至发生在冷战的最严重时期。
最后强调一个至关重要的事实。时常，密码系统被攻破是因为劣质的密钥管理而不是算法的固有弱点。在第二次世界大战时的Enigma(Enigma是纳粹德国在二战期间使用的转轮加密机－译者注)就是说明这种观点的最著名的例子。因此，密钥管理协议的安全就显得极端的重要。然而，安全协议的历史充满了令人讨厌的惊奇；到处都摆着这样的协议：在公认为安全的许多年后，突然就被一个新奇的攻击方法给攻破了。
公平地说，一些所谓的新奇的攻击方法只是简单地改变了协议使用方法的假设，证明了这个协议不能工作在新的环境。如果你追寻这些问题的根源，你将发现协议的设计者仍然在致力于精确定义他们的协议在什么条件下才能获得成功，在什么环境下才能使用。一个相当臭名昭著的例子就是实体认证。甚至连ISO工作组对实体认证是否包含了会话密钥的构建或者是否仅仅验证了一个声称的身份都持有不同的意见。
在这种上下文环境中，像“Alice对Bob讲”或者“Bob验证Alice的身份”这样的拟人化的说法都可能产生误导。在计算机安全中，实体是计算机，不是人类。它们通过网络发送消息，它们并没有谈话，你必须确定验证A的身份到底意味着什么。在计算机之间绝对没有可以看见的接触。
Alice和Bob是“语义心上人”（semantic sugar）。他们允许你描述美好的故事（语义细节），但他们也招致了你在错误的抽象层上的思考。
进一步的阅读如果你对秘密通信的历史感兴趣，文献[73]是一本比较好的参考书。最新的关于密码系统的专业化的参考可以阅读文献[99]。文献[137]给出了对现代密码学的比较好的、非数学的介绍，它还有一个非常丰富的参考目录，并收集了大量的密码算法。在这些书中，你可以找到在这一章中提到的算法的所有细节和进一步的信息。
文献[41]是公开密钥密码的基础论文，在早期它是CESG关于公开密钥系统研究的保密文档，仅仅在最近才去除了对它的限制。相关的报告已经被放到了他们的Web页面上：
http://www.cesg.gov.uk/storynse.htm
Venona文档可以在下面页面得到：
http://www.nsa.gov:8080/docs/venona/venona.html
关于对加密的挑战和一般的密码学的最新信息，可以访问：
http://www.rsa.com
对于在一个真实的密码协议方面的实例研究，检查OAKLEY密钥判决协议，它在IP协议层使用Diffie-Hellman和RSA作为密钥协商协议[120]。
不管Internet起草的简单公开密钥基础设施（SPKI）[46]的短暂性，在关于证书理论的讨论中它是必须提到的。对于证书和公开密钥基础设施，可以参考：
http://www.entrust.com 或者http://www.werisign.com
练习题练习题12.1 密码协议是用来使部门在不安全的网络上进行安全通信。这种说法正确吗？
练习题12.2 密码术需要物理安全。这句话在什么程度上是正确的？
练习题12.3 假设对一个n位整数的求幂模算法，它需要大约次操作，将它从512位的RSA体制发展到1024位的RSA中，将引起多少性能恶化？
练习题12.4 当一份文档太长而不能使用数字签名算法直接进行处理时，对文档计算散列值，然后对散列值进行签名。你要求这个散列函数具有什么样的性质，才能阻止攻击者伪造签名？
·一种情形是仅仅知道受害者签名的消息，另外一种情形是攻击者可以选择由受害者签名的消息。区分这两种情形。
·区别选择伪造（selective forgeries）和存在伪造（existential forgeries），其中选择伪造是攻击者已经控制了伪造消息的内容；存在伪造则是攻击者没有控制伪造消息的内容。
·研究与像RSA这样的可逆签名算法一起使用的散列函数的特定要求。
练习题12.5 对任何一对素数你能安全地使用RSA吗？研究使用“强素数”的理由和由一个“强素数”通常要求的性质。当素数变得很长的时候，你的理由仍然是有效吗？
练习题12.6 在El Gamal签名方案中，如果随机数被用来签两个不同的文档，说明私有签名密钥怎样可能被泄露？
练习题12.7 使用私有RSA指数加密并不能生成数字签名。试解释，如果没有对签名的消息进行冗余检查，攻击者怎样和在什么程度上进行伪造签名。
练习题12.8 证书基础设施对于支持数字签名方案是必须的。提议的范围从X.509的目录树一直到可信任的PGP网络。探讨为什么一个应用可能要求数字签名的理由。哪种证书方案最适合你已经确定的目的？
练习题12.9 NP-完全问题（NP-Complete）是构造密码算法的合适基础吗？
练习题12.10 密钥建立协议不仅仅对内部欺骗是脆弱的。对密钥交换协议做一个完全的威胁分析。
练习题12.11 修改Needham-Schroder密钥交换协议，使得两个参与者A和B都能对会话密钥的生成提供输入。
现在，倾向性却走到了另外一个极端。密码被看成了将解决所有计算机安全问题的神奇的对策。安全操作系统由于太昂贵、使用太受限制和太远离用户的要求，而作为过去的事不再考虑，它最终像恐龙绝迹一样消亡。密码能够提供这样重要的承诺吗？
目标
·了解由于不同的目的使用密码的各种各样的应用。
·对密码学基本概念的介绍。
·理解密码能够解决问题的类型，在使用密码时需要解决的问题的类型。
·指出要求支持密码的计算机安全的特征。
12.1 简介密码编码学（cryptography）是书写秘密内容的学科，密码分析学（cryptanalysis）是破解加密器（cipher）的学科，这两个主题就形成了密码学(Cryptology)。它们曾经是间谍和秘密部门的领域，由于这些原因，现在仍然给密码罩上一层神秘的面纱。
现代密码学完全是一门数学的学科。对于很好地理解密码学出色的观点所必需的数学背景的阐述已经超出了本书的范围。我们将尽力解释怎样把密码编码学用于计算机安全，并且指出计算机安全常常是加密能起作用的一个先决条件。
12.1.1 老的范型（paradigms）
密码在通信安全中有它自己的根源。通信安全解决了在图12.1中描述的情况。两个实体A和B通过一个不安全的信道通信。对抗者是一个入侵者，他可以完全控制这个信道，能够读他们的消息，删除消息或者插入消息等。两个实体A和B是彼此信任的。他们想保护通信不受入侵者的破坏。密码使得他们在不安全的物理连接上建立一条安全的逻辑信道。
图12.1 通信安全
在这方面，密码与到目前为止讨论的计算机安全机制是有本质区别的。对于来自底层的危害，它们全部都是脆弱的。然而，对物理通信链路的访问却不能威胁密码的保护。
在分布式系统中，客户和服务器之间的通信流对一个以入侵者自诩的人来说是一个新的攻击点。不安全通信链路引入的脆弱性自然能够由通信安全服务和机制来解决。这些服务包括：
·数据机密性,加密算法隐藏了消息的内容；
·数据完整性,完整性检测功能提供了检测文档是否被改变的方法；
·数据源认证,消息认证码或者数字签名算法提供了验证消息来源和它的完整性的方法。
在我们的定义中，数据完整性实际上不是适合通信安全的的概念。消息就基本性而言总是有一个发送者。如果你接收到一个消息，但不知道谁发送了它，你怎么能够断言它在传输过程中并没有被修改呢？因此，当你没有验证消息来源的时候，就无法验证它的完整性。另一方面，你不应该声称已经验证了在传输过程中已被更改了的消息的来源。因此，数据来源认证包括消息完整性认证，并且我们的数据完整性的概念，更适合于应用而不是通信，比如，反病毒软件的文件保护。
谁是朋友，谁是敌人这种传统的观点也在计算机安全中有了它自己的位置，但它不再是驱动计算中密码应用的主要理由。不幸的是，它仍然支配着公众对密码的理解。同样的观点也反映在用于密码协议的许多验证工具的公理上，它们假设实体A和B的行为与协议规则完全一致，并且只考虑入侵者行为的影响。
12.1.2 新的范型让我们关注新鲜的事物。在电子商务中，顾客进入了一个与商家有关的商业事务。两个参与者都不希望另一方欺骗，但是，纠纷却有可能发生，并且预先有一致的规则总比在发生纠纷时再采取特定的方式解决要好些。顾客和商家都有运行一个协议的理由，协议并不假设对方在任何环境下都是可信任的。现在的对抗者是一个误操作的内部人员，而不是一个入侵者，在图12.2所示的第三个参与者不再是一个入侵者，而是一个可信任的第三方（TTP），例如，一个仲裁者。在解决纠纷的时候，不可否认（non-repudiation）服务生成了在解决争端时仲裁者将要考虑的证据。
图12.2 电子商务安全
许多国家都有法律，规定法律执行代理（LEA，law enforcement agent）在什么时候、怎样获得侦听许可证，以便责成电信服务提供者给他们接入到特定用户之间的通信的权利。现在，在图12.3中的第三方是一个通信操作员的客户，必须给他提供一个合法的侦听服务。在这种上下文中，密钥托管服务分发用于加密通信的密钥；密钥托管服务也是目前令人激动的研讨课题。
图12.3 通信安全和法律实施
12.1.3 密码的密钥密码员采用锁作为他们特别喜爱的图标，以表示他们给公众提供安全服务。快速查看目前的允许安全的Web浏览器或者e-mail产品的用户接口就能够证实这种观察。但是类推充满了危险，你不应该过分地信任它们，但是也有一些重要的概念从锁匠传承到了密码员。锁上门或者打开门上的锁，你需要一把钥匙。从强度上分，锁是不同的。有些很容易撬开，而其他的锁是如此坚固，以致入侵者不得不采用蛮力攻击破门而入，或者选择一条完全不同的路径，并且改为从房间的窗户进入房间。
密码算法使用密钥来保护数据。从实现方法的强度和范围来看又有各种变种，其中的一些使用简单的统计方法就可以破解，而另外一些远远超出了目前的数学分析和计算能力所能够达到的范围。蛮力攻击穷尽一切可能地搜索整个密钥空间，它给出了算法强度的上限。
现代密码系统并不依赖于算法的保密。在密码变换中使用的密钥才是唯一需要保护的内容。这个原则是在上个世纪由Kerckhoffs提出并作为基本条件的，在我们的新安全范型中是非常适用的，在这里必须支持大量具有竞争利益的用户团体。在这种环境下，形成事实上的标准和对公开算法的开放评估都是很自然的过程，使得每一个参与者都有机会进行他们自己的安全评估，使新的参与者更容易加入。
因而，从最一般的字面意义上理解，密钥管理对密码机制的安全是极为重要的。你必须处理下面这些问题：
·密钥在哪儿生成？
·密钥怎样生成？
·密钥在哪儿存储？
·密钥怎样分发？
·密钥实际上在什么地方使用？
·密钥怎样撤销和替换？
在这一点上，圆是闭合的，我们又回到计算机安全。密码密钥是存储在计算机系统中的敏感数据，计算机系统中的访问控制机制必须保护这些密钥。当访问控制失败时，密码保护受到了威胁。在大多数目前实施的安全系统中，密码算法是最强的部分，且老谋深算的攻击者将寻找其他的脆弱性，而不是把他们的时间浪费在密码分析上。
密码对安全问题来说，在任何时候都是一个罕见的解决方案。密码是一个变换机制，它通常把通信安全问题转化为密钥管理问题，而最终转化成了计算机安全问题。希望最后的问题比原来的问题更容易解决。总之，密码能够加强计算机安全，但它并不是计算机安全的替代品。
12.1.4 模运算相当多的现代密码算法都建立在代数学原理的基础上。这些算法可以定义在令人兴奋的代数结构上，比如椭圆曲线或者伽罗瓦域（有限域）。然而，我们仍然有点停留在实际应用上，且在它们描述中仅使用整数。在这里，我们将解释一些关于模运算的基本知识，作为后面描述内容的基础。
令是一个整数。在后面的描述中，我们将称为模数（modulus）。然后在整数集合上定义了一个等价关系‘’：
，当且仅当，这里，是某些整数，
我们则说“等价于以为模”。你可以检验‘’确实是一个等价关系，它把整数集合划分成关于的个等价类：
我们更习惯用的形式来表示等价类，我们将遵循这个约定。你可以证明下列有用的性质：
除此之外，对于每一个，是素数，存在一个整数，使得。对于一个素模数，以为模的乘法阶定义为：
定义 令是一个素数，是一个任意整数。模的乘法阶定义为满足下面关系的最小整数：
费尔马小定理 对于每一个，是素数，有。
这个定理表示，任何一个以为模的非零元素的乘法阶必定是的因子。这个事实被用于构造相当多的密码算法。这些算法的安全性常常是相关的，在少数场合是等价的，来自数论中的下述问题中的任何一个都是难解的：
·离散对数问题（DLP）,给定一个作为模的素数，基数和值，根据等式，求出的离散对数。
· n次方根问题,给定一个整数，和，求出一个整数，使它满足。解就叫做模的n次方根。
·因式分解问题,给定一个整数（合数），找出它的素数因子。
在参数的正确选择情况下，这些问题是许多密码算法的合适的基础。然而，并不是这些问题的所有实例都是难解的。很明显，如果或者是比较小的整数，那么这些问题就可以在合理的时间范围内采用穷举搜索来求解。目前，二进制512位的整数已被认为是位数较短的整数了，一般都推荐使用1024位整数，当然，如果你能够容忍由于算术运算占用更长的时间而引起性能的下降，你可以使用更长的整数。长度不是你必须考虑的唯一方面。这些问题的难度也依赖于和的结构。（为了进一步追究这个课题，你必须放下这本书，而寻找一些更专业化的数学方面的书籍来阅读。）
12.2 密码机制密码机制是密码方案的最基本的构造模块。它们被用在密码协议中，且依赖于好的密钥管理来提供有效的保护。最频繁应用于计算机安全的密码机制是：
·加密（encryption）算法，
·数字签名（digital signature）方案，
·完整性检查功能（密码散列函数，即hash函数）。
为了舍弃传统密码，我们将以相反的顺序来介绍这些概念。
12.2.1 完整性检查功能依赖于特殊应用的需求，对密码散列函数的要求也有一些微妙的差别。我们列出了散列函数的一些基本性质，由此来展开这一节的讨论：
·容易计算,给定，容易计算。
·压缩：对于任意输入长度的，函数最后都生成固定长度的输出。
·预映射抗拒性（单向性）,给定一个值，为了找到满足，通常在计算上是不可行的。
·第2次预映射抗拒性（弱冲突抗拒性）,给定输入和，求出另外一个，且,使得，在计算上是不可行的。
·冲突抗拒性（强冲突抗拒性）：求出任何两个输入和，使得成立，在计算上是不可行的。
操作检测码（manipulation detection codes,MDCs），也称为修改检测码或者消息完整码，常常用于检查文档是否发生改变。在文献[99]中提到了两种形式,
·单向散列函数（OWHF）具有压缩性、易计算性、预映射抗拒性和第2次预映射抗拒性等性质。
·冲突抗拒散列函数（CRHF）具有压缩性、易计算性、第2次预映射抗拒性和冲突抗拒性等性质。
应用散列函数计算的结果分别不同地称为：：
·散列值（hash value）
·消息摘要（message digest）
·校验和（checksum）
最后一个术语为混淆留下了巨大的空间。在通信安全中，校验和是指错误校正码，典型的是循环冗余校验码（CRC）。另一方面，校验和也被用在反病毒软件的产品中，但是禁止使用CRC来计算，而必须使用密码散列函数（MDC）来计算。令是被禁止篡改的程序。在一个没有病毒的环境下计算散列值h(x)，并且把结果存储在不能修改它的位置，例如，存放在CD-ROM上。为了检查程序的状态，重新计算散列值，把它与原来存储的值进行比较。散列值的保护是重要的。计算散列值并不要求任何秘密的信息，因此，任何人都能对一个给定的文件计算有效的散列值。
当参数和明智地选择时，函数是一个单向函数，这个函数称为离散求幂。为了反向离散求幂，你必须解决在12.1.4节介绍的离散对数问题。在这一章的后面你可以看到离散求幂在密码方案的构造中是真正有用的原函数。然而，离散求幂并不是特别快的操作，当你需要高速处理大量的数据时，你必须转而采用其他的算法。
快速散列函数倾向使用类似的设计模式来构造。散列函数的核心是一个压缩函数，它处理固定长度的输入。一个任意长度的输入被分割成给定块大小的块、…、，如果最后一个块没有达到固定长度，就使用填充的方法使它达到固定的长度。的散列值则可以通过反复的使用压缩函数获得。令是一个（固定的）初始化值。计算
，，
且取作为的散列值，如图12.4所示。（符号||表示级联）
消息认证码（MACs）对消息的来源和完整性提供了保证（数据源认证）。MAC从两个输入即消息和秘密的密码密钥计算得到。因此，MAC有时也叫做密钥散列函数。正式地说，MAC是用密钥作为参数化的散列函数的族。这个族中的每一个成员都具有压缩和容易计算的特性，附加的抗计算特性也必须满足。
对于任何固定的值，给定一个值集合，当攻击者不知道这个固定的值时，对任何新的输入，在计算上来说，要计算出是不可行的。
为了认证一个消息，接收者必须与发送者共享密码密钥，用来计算MAC。不知道密钥的第三方不可能确认MAC。使用下面的HMAC构造方法，一个MAC算法则可以从MDC算法推导出来。计算
其中和是填充的位串，它把扩展成在中使用的压缩函数需要的长度。
图12.4 hash函数构造
安全散列算法我们将选择安全散列算法（SHA-1）来说明散列函数实际上是怎样设计的。这个算法被指定用于美国的数字签名标准（DSA）。其他的散列函数是MD4（不是那么强有力的）、MD5（Internet协议中的标准选择）和RIPE-MD。SHA-1处理任意多个512位的数据块，生成一个160位的散列值。参数可以被作为整数解释也可以作为位串解释。在位串和整数之间的转换算法在我们的描述中省略掉了。
输入的末尾将用一个1来填充，然后是一个0串，以使得最后的输入块有448位长度，且最后64位字段指示在填充前输入数据的长度。初始化的值由五个32位的值定义，以十六进制数表示：
A=67452301
B=efcdab89
C=98badcfe
D=10325476
E=c3d2e1f0
SHA-1的压缩函数在一个80步的循环中处理512位的输入，每20步改变一次内部函数和常数，最后生成一个160位的输出。这些函数是：
，
，
，
。
其中，操作符是位与、位或和异或，应用到32位字上去。常数采用十六进制数表示，它们是：
，
，
，
。
在压缩函数开始的时候，五个32位的变量、、、和是用散列函数的中间值来初始化的。对于第一个输入块，则使用初始值、、、和。512位的输入块被分成了16个32位的字，并且使用下面的算法，将它们扩展成80个32位的字：
，
，
其中，符号表示循环左移位。现在压缩函数执行下面的循环，其中加法使用模运算：
for t=0 to 79 do
begin
temp=(a<<<5) + ft(b,c,d) +e+wt+kt;
e=d;
c=b<<<30;
b=a;
a=temp;
end;
最后，变量、、、和的值被加入到前面的中间散列值中。在处理下一个输入块的时候，这个结果用作初始的散列值。
12.2.2 数字签名在图12.1中，消息认证码帮助参与者A和B检测在通信信道中由入侵者插入的欺骗消息。然而，消息认证码并不生成任何证据，供第三方用来判断A或者B是否发送了特定的消息。因此，在图12.2的电子商务中，顾客需要确保商家不能伪造订单，且商家需要确保顾客必须认可他们所下的订单，在这样的情况下，消息认证码几乎是没有什么用处的，因而数字签名就很有必要了。
数字签名方案由签名算法和验证算法组成。一份文档的数字签名是一个值，它依赖于文档内容和仅由签名者知道的某个秘密，即私有签名密钥；私有签名密钥把文档与一个实体联系在一起，即公开的验证密钥。验证算法通常使用文档和公开验证密钥作为输入，但是在一些异常的情况下，文档或者文档的一部分可以从签名中恢复出来，且对于签名验证不一定要提供文档。下述的可验证特性表示了数字签名方案的特征：
规则 第三方可以在不知道签名者的私有密钥的情况下，解决关于数字签名有效性的纠纷。
数字签名支持不可否认性。公开密钥密码（见12.2.3节）是数字签名方案的自然来源。在这种方案中，私有密钥和公开验证密钥之间的联系，是为了确保从验证密钥中推导出签名密钥在计算上是不可行的。不管在数学基础上的相似性，你应该推断出数字签名和公开密钥加密算法之间清楚的区别。这两种方案从根本上满足了不同的技术目的。加密保护了消息的机密性，因此必须是可逆的。数字签名提供了数据来源的认证和不可否认性。数字签名算法不必是可逆的，事实上，可逆性会引起一些附加的安全担心。
一次性签名你不需要为构造一个签名方案而钻研数学。为了获得一次性签名，你仅仅需要一个密码散列函数就可以了[81]。为了对一份n位的文档签名，随机选择2n个值的和作为你的私有密钥，且公布和，，作为你的公开密钥。对文档的签名的第部分则由下式给出：
很明显，你不能再次使用你的私有密钥，因此，这就是一次性签名的由来。验证者拥有你的公开密钥，并进行检查：
你将发现，验证者需要附加的证据来进一步证实数值和确实是你的公开密钥。我们将在12.4节回到这个主题。
此外，除了依赖数学问题的难解性或者依赖其他的一些密码原函数的强度，你还可以依赖抗损害硬件设备的难度。这个设备包括一个秘密的签字密钥和/或者秘密的验证密钥。这个设备是这样构造的，以至它不能使用签名密钥来验证或者用验证密钥来签名。为了签名一份文档，设备使用它的签名密钥构造MAC，然后把它附加到文档上。为了验证这个签名，验证者的设备必须拥有签字者的签名密钥作为验证密钥，用这个密钥来生成MAC，把它同接收到的签名进行比较。
EIGamal签名和DSA
在文献[45]中的EI Gamal签名方案用实例说明了签名不是用私有密钥加密。令是一个大的和适当选择的素数。令是以为模的阶为的整数。令是用户A的私有签名密钥，且是对应的公开验证密钥。
假设要签的文档是一个整数，。另外，你也可以应用一个合适的散列函数，然后对文档的摘要进行签名。为了对进行签名，用户选择了一个随机数，，以使得，计算，并且解方程：
求解未知的。整数对构成A对的签名。验证者需要A的验证密钥，并检查：
对于一个正确的签名，等式：
也是成立的。这种方案的安全与离散对数问题紧密相关，但是并不等价于离散对数问题。许多更安全和更有效的签名方案都是从EI Gamal签名方案派生而来的。一个这样的签名算法是数字签名算法（DSA，digital signature algorithm）[116]。在这个方案中，用户A的私有密钥和公开密钥通过下述步骤生成。
1）选择一个素数，。
2）选择一个整数，，和一个素数，，所以整除。
3）选择，，并计算。如果，用一个新的再试。（这一步计算以为模的阶的生成元。）
4）选择一个，使其满足。
5）计算。
6）A的私有密钥就是数值，公开密钥是。
A为了对文档进行签名，使用SHA-1计算散列值，并且转换成一个整数，然后：
7）随机地选择一个整数，。
8）计算。
9）计算。
10）计算。
A对的签名就是整数对。这个签名将用A的公开密钥进行检测：
·验证和
·计算
·计算和
·计算
·当且仅当，则通过验证。
RSA签名在文献[127]中描述的RSA算法是用它的发明者Rivest、Shamir和Adleman的第一个字母命名的，它同样可以用于签名和加密。RSA的这种特定的性质必须对许多关于数字签名和公开密钥密码的流行的误解负责。在RSA签名方案中，用户A选择两个素数和，和一个私有签名密钥，满足和。公开验证密钥则由积和指数组成，并且满足
,lcm(p-1,q-1)是欧拉商数。
签名的文档是整数，。为了验证者能识别真正的文档，这个文档必须包含足够的冗余信息。如果原始文档太长，可以应用散列函数和填充获得摘要进行签名。为了签名，用户A用下式生成签名：
验证者需要A的验证密钥，并且检查
是否成立。对于一个正确的签名来说，这个等式是成立的，因为
短文档可以从签名中恢复，并且不必分别传送。RSA安全与因式分解的难度是相关的，但是并不等价于它的难度。
在某些签名方案中（RSA是基本的范例），你可以选择公开验证密钥，因此签名验证特别快。图12.5中的表给出了对于1024位参数运行在相当快的机器上的DSA和RSA的性能的粗略比较，以及一个签名方案的不同部分要求的工作的比较。（信息由在KU leaven 的ESAT提供。）
图12.5 RSA同DSA的比较
12.2.3 加密我们保留了术语加密（encryption），它表示保护数据机密性的算法。加密算法，也叫做密码（cipher），在密码密钥的控制下，将明文（plain text或clear text）加密成密文（cipher text）。用适当的解密密钥解密（decryption），可从密文中恢复明文。有些加密算法提供了检测违反完整性的方法，但情况不总是这样。你甚至可能注意到签名算法被描述为使用私有密钥的加密，但是，这种说法常常是不正确的，并且总是误导。我们将使用在10.2.1节中所用的表示法：
·，表示用密钥加密明文；
·，表示用密钥解密密文。
加密算法以两种形式出现。在对称加密算法中，加密和解密使用相同的密钥，这个密钥必须保密。所有的参与者共享同一密钥，他们可以阅读彼此的加密数据。为了对不同参与者建立专用信道，对每个信道你需要一个新的密钥。维护大量的共享秘密密钥可能成为一种十分繁重的管理任务。
非对称加密算法，也叫做公开密钥算法（public key algorithm），加密和解密使用不同的密钥。加密密钥可以公开；解密密钥仍然是私有的，必须保密。很明显，这两个密钥在算法上是相关的，但是想要从公开密钥导出私有密钥必须是不可行的。为了区分对称密码系统和公开密钥密码系统，我们在对称密码系统的上下文中使用秘密密钥，而仅仅在非对称密码系统的上下文中使用私有密钥。
对于秘密密钥密码系统，使正确的密钥存放在合适的地方，这种安全管理任务是很明显的。而公开密钥密码系统看来使管理容易得多。毕竟，公开密钥是公开的，且不需要保密。当你使用公开密钥加密算法加密一份文档的时候，你可能需要知道谁能够阅读这个加密后的文档。更一般地说，私有密钥可能授权给委托人或者用作携带访问权限的能力，例如，读一份文档。现在，保证在公开密钥和访问权限或者与对应的私有密钥联系在一起的委托人之间的联系是一项主要的任务。证书（certificate）常常用来为这种特殊的目的服务。在12.4节，我们将回到这个主题。
加密算法也可以分成块密码和流密码。存在区分它们的两个标准。
·块尺寸,块密码加密较大的数据块，典型的是64位的块，使用一个复杂的加密函数。块密码的安全依赖于加密函数的设计。流密码加密较小的数据块，典型的是位或者字节，使用一个简单的加密函数，例如，按位异或运算。正如你想象的一样，这种区分在边界处就变得模糊不清了。一个16位的块仍然是一个大的块吗？一个加密算法什么时候是简单的？
·密钥流,块密码使用同一密钥来加密属于同一文档的所有的块。而流密码借助连续变化的密钥流加密整个文档。流密码的安全依赖于密钥流生成器的设计。在这种定义下，使用反馈模式的DES(见下文)属于流密码范畴。
数据加密标准DES
数据加密标准（Data Encryption Standard，DES）是对称块密码算法中的经典。DES是在二十世纪七十年代开发的，作为美国政府保护非机密信息的标准，并且作为联邦信息处理标准发布[114]。DES在56位密钥控制下对64位明文块加密。每一个密钥通过一个奇偶检验字节扩展到64位工作密钥。与大多数的块密码一样，DES是基于Feistel 原理的。Feistel密码在大量的循环中迭代相同的基本步骤。第轮的数据被划分成左半部分和右半部分，各32位，而输出采用下式计算：
其中是某种非线性函数，是在这次循环中的子密钥，如图12.6所示。这个操作的逆过程可以通过同样的路线来进行：
图12.6 Feistel原理在DES中的非线性函数将32位输入扩展成48位的块，然后与48位的子密钥进行位的异或运算。这个中间结果划分为8个6位的块，它用作8个盒（substitution boxes，替换盒）的输入。每个盒将6位的输入转换成4位的输出。盒的输出通过一个盒（permutation boxes，置换盒），它对32位的输入执行位排序，给出函数的结果。
DES要进行16轮（round）这样的运算。每轮都使用不同的48位子密钥，这个子密钥是从56位的DES密钥衍生出来的。第一轮的输入是由初始化置换处理的，最后一轮的输出再进行一次逆置换，。图12.7给出了DES的示意图。我们省略了密钥编制表的算法、扩展方案、盒和置换的所有细节。
二十世纪七十年代当DES变成了标准的时候，它得到了十五年的适用期。DES很可能已经老化了，但仍然在广泛使用，特别在商务和金融领域。对DES安全的主要挑战不是来自新的密码技术，而是来自它的密钥大小。今天，不需要专用设备，对56位密钥空间的穷举搜索已经很容易了。工作站的性能正逐年增长，网络使得业余密码分析者可以使用更多的资源。在这样对抗的环境下，你只能指望一个56位的密钥能够生存几个星期或者几个月，而不是几十年或者几个世纪。多重密码扩展了密钥的大小，而不必改变算法。推荐的选择是使用了三个56位密钥的三重DES。有一种变异很受欢迎，因为它保持了与单一的DES的向后兼容性，使用两个56位DES密钥和，按下式对明文进行加密：
图12.7 DES算法块密码模式块密码可以用于各种各样的加密模式。在电子密码本（ECB）模式中，每个明文块都用相同的密钥独立加密。这种模式可能泄漏关于明文的信息。如果一个明文块是重复出现的，这种重复性也会出现在密文中。而且，完整性保护非常有限。解密不检测密文块的顺序是否已经改变，有些块是否已经丢失，或者有些块是否已经被复制。
在图12.8中的密码块链（CBC）模式中，前面的密码块在加密前被加到（按位异或）下一个明文块，即：
。
因此，重复的明文块不会作为重复的密文块表现出来。对于第一个明文块，用作初始化向量。这个初始化向量通常是保密的，尽管在很多的应用中，这并不是必须的安全条件。每一个消息的初始化向量都应该改变，以确保观察者不能检测到两个明文始于相同的块。初始化向量也被用来解密第一个密文块。密文块使用下式进行解密：
如果一个密文块被破坏了，这种损坏将被限制在两个明文块中。假设用来代替了，在下列运算后：
正常的解密服务又恢复了。
图12.8 密码块链模式输出反馈模式（OFB，见图12.9）使用块密码作为流密码的密钥流生成器。在这个模式中，可以处理小于密码算法所要求的块尺寸的明文块（chunk）。给加密函数的输入存储在寄存器中，这个寄存器的初始内容由初始化向量来确定。为了加密一个明文块，把寄存器内容加到加密函数输出的一个子块中（按位异或）。加密函数的输出则被反馈到了移位寄存器。解密过程与加密完全相同。初始化向量对每个消息都必须改变，但是不需要保密。在密文块传送中的错误仅仅影响到对应的明文块。因此攻击者可能通过在对应位置改变密文块来选择性地修改明文块。
图12.9 输出反馈模式
图12.10 密码反馈模式密码反馈模式（CFB，见图12.10）使用块密码来生成与数据相关的密钥流。并且，明文可以在比密码算法要求的尺寸小的情况下进行处理。在这种模式中，先前的密文块被反馈到一个移位寄存器。这个寄存器的内容被加密，且这个密文的子块将被加到下一个明文块中（按位异或）。解密过程与加密相同。在这种模式中，初始化向量对每个消息都必须改变。初始化向量要求用来解密第一个密文块，不必保密初始化向量。密码块的传输错误或者更改将影响解密，直到改变的块从移位寄存器中移出，移位寄存器内容在接收端馈给加密函数。
RSA加密从RSA签名方法中我们已经熟悉这个方案的基本结构了。当RSA用于公开密钥加密算法时，用户A选择两个素数和，一个私有解密指数，满足和。公开加密密钥由积和指数组成，满足
消息必须被分成块，使得每个块都是一个小于的整数。为了发送一个消息块到A，发送者计算：
接收者A使用私有解密密钥以获得：
。
EI Gamal加密
在EI Gamal公开密钥算法中，仍是一个大的且适当选择的素数，且令是一个以为模的高阶整数。令是用户A的私有解密密钥，且是相应的公开加密密钥。消息被划分成块，使得每个块都是一个小于的整数。为了发送一个消息块给A，发送者选择一个随机数，计算，发送如下密文：
给A。A使用其私有解密密钥，可以获得：
在这种方案中，密文块长度是明文块的两倍。另一方面，如果两个明文块是相等的，相应的密文块却是不相同的。随机数仅仅用于加密一次。随机数的重复使用会严重地削弱密码的强度。
12.3 密钥建立协议在一个密码算法可以使用之前，所有的密钥必须存放在正确的地方。当然，密钥可以通过邮政系统邮寄信的方式获得，这是一种通常用的分发信用卡的PIN（个人身份识别码）的方式，或者通过信使在站点之间传递和发放密钥。这些提议或者不是很安全或者很不经济。比较理想的方式，我们希望在已有的通信设施基础上实施密钥管理任务。通过其他协议建立使用密钥的密码协议称为密钥建立协议。
这些协议中的一些仅仅涉及想要设立一个共享密钥的参与者；其他的则要求一个可信第三方的服务。为了区分这两种情况，你必须查阅：
·密钥协商协议：密钥在没有第三方帮助的情况下建立。
·密钥传输协议：密钥由第三方生成和分发。
密码协议的数学细节分析常常揭示了一个弱密钥子集的存在，该集合中的密钥会允许内部人员进行欺骗。因而在设计一个密钥交换协议的时候，你应该回答两个问题：
·如果建立了弱密钥，哪一方将受损害？
·哪一方可以控制密钥的选择？
如果误操作的内部人员可以影响密钥的生成，以致选择了一个弱密钥，则可能存在内部攻击的目标。
现在，研究文献给你提供了广泛的密钥建立协议的选择。我们将提出两种原型协议，它们对密钥建立协议的设计有主要的影响。
12.3.1 Diffie-Hellman协议
Diffie-Hellman协议是一个密钥协商协议[41]。没有共享秘密的两个参与者A和B构造一个共享的秘密密钥。令是一个适当选择的大素数，是一个以为模的高阶元素。A方选择一个随机数，发送到B。B方选择一个随机数，发送到A，并且计算。在接收到后，A使用它自己选择的秘密来计算。因为：
双方则共享了秘密。这里留下了一个小小的问题，任何一方都不知道它和谁共享了这个秘密。为了保证初始的信任，在这个协议中必须加入认证。在文献[42]中的站到站协议解决了这个问题，如下所述。除了建立共享会话密钥的Diffie-Hellman交换外，这个协议使用一个加密算法和签名算法。这里没有规定特定的算法。在下面的描述中和分别是A和B的签名密钥，和表示使用这些密钥产生的签名。在协议中的步骤是：
步骤1 A→B：
步骤2 B→A： ，
步骤3 A→B：
在步骤1，A选择一个随机数，并初始化Diffie-Hellman密钥交换。B接收到以后，选择一个随机数，并计算会话密钥。在步骤2以后，A可以完成它的Diffie-Hellman密钥交换部分，获得会话密钥，然后解密B的消息的第二部分，验证B的签名。在最后一步之后，B可以解密并验证A的签名。
12.3.2 Needham-Schroeder协议
Needham-Schroeder协议是一个密钥传输协议[110]。两个参与者A和B从服务器S那里获得会话密钥。起初，双方都与服务器共享秘密密钥。对称密码用来进行加密，序列号（nonce，随机的复杂问题）包含在消息中以便防止重放攻击。下述的约定使用在协议的描述中：
由A和S共享的秘密密钥
由B和S共享的秘密密钥
由S生成的，用于A和B之间的会话密钥
， 分别由A和B生成的序列号（nonce）
图12.11说明了在A方从服务器S请求一个用于和B通信的会话密钥时所发生的步骤。
步骤1 A→S： A，B，
步骤2 S→A：
步骤3 A→B：
步骤4 B→A：
步骤5 A→B：
在协议的前三步中，A从S获得了会话密钥，并把它转发给B。通过检查在服务器消息中返回的序列号，A可以验证会话密钥已经发出，以响应它最近的请求，而不是对一个先前运行的协议的重放。在最后两步中，B验证了A当前正在使用同一会话密钥。Needham-Schroeder协议安全的详尽分析和更多安全变型的讨论超出了本书的范围。
图12.11 Needham-Schroeder协议
12.4 证书在站到站协议描述中，一个重要的细节被省略了。A和B怎样知道他们用来检测签名的验证密钥恰好对应着正确的一方？在这里必须存在一个可靠来源，它把密码密钥与身份联系起来。在对称加密情况下，参与者A和B信任创建连接的服务器。公开密钥密码和签名方案常常依赖于证书（certificate）。证书管理机构（certification authority，CA）通过签署一个文档来保证用户和密码密钥之间的联系；这份文档包括用户名、密钥、CA的名字和过期日期等。现有几种提议规范了证书的精确的格式，最著名的是在X.509的目录框架结构[27]中使用的证书。这些格式在某种程度上在它们所包含的域（以及各个域的长度）方面不同。在有效的证书处理和对很大范围应用的灵活支持之间的工程平衡是不应该令人感到惊讶的。
把名字和密码密钥绑定在一起的证书在通信安全中有它们的起源。用户想知道他们正在和谁通话。在计算机安全中，它常常更关心一个调用者的访问权限，而不是调用者的身份。当然，你可以使用证书来认证调用者，然后使用调用者的用户名来建立访问权限。然而，你可以取代中间人，而在证书中包含访问权限。相应的私有密钥则有安装在证书中规定访问权限的能力。在这种情况下，你不用检查证书来确认用户的身份。倒不如说你认证一个能力（capability）。
像用户身份一样，证书也被用作两种用途。它们可以标识与密码系统密钥联系在一起的实体或者它可以规定给予密码密钥的拥有者的访问权限（并不鉴别拥有者的身份）。
为了验证一个证书，你需要验证密钥来检查CA的签名。CA的验证密钥可以由另外一个CA来保证。因此你需要另外一个验证密钥，另外一个证书等等。存在关于最适合的证书层次结构组织的热烈争论。在这个领域的一端，X.509目录框架结构以完美的形式把证书安排在一棵有统一的根证书的目录树中。在另一个极端中，PGP（Pretty Good Privacy）证书基于一个推荐的系统，且根本不需要CA。最终，在表面意义上你必须信任验证密钥。你可以从朋友那里接收这个密钥，或者从你的老板、从你的Web浏览器、或者在书本范围外获得密钥。如果你非常谨慎，在信任这个密钥之前你可以参考几个来源。关于证书废除的相关问题已经在第十章中讨论过了。
最后，密码保护一定要建立在非加密的基础上。
12.5 密码机制的强度度量密码算法的强度是一门不精确的艺术，有时建立在牢固的数学基础上，其他时候又依赖于直觉和经验，一个密码算法可以是：
·经验安全（empirically secure）
·可证明的安全
·无条件安全如果一个算法已经经受住了时间的检验，那么我们说它是经验安全的。长期的分析没有发现什么严重的缺陷，虽然没有证明该算法不会最终受到一个新的或者有创造才能的攻击，并且算法已经在密码学界范围内被广泛接受。DES是一个经验安全的最好的例子。新的分析方法，比如差分密码分析学，已经加强而不是削弱了感知到的DES安全。
可证明的安全算法，似乎提供了计算机安全一直渴望的东西，即可证明的安全。可证明的安全是在复杂理论的框架结构内表示的。如果破解一个算法至少和解决另外一个问题一样的困难，而另外一个问题我们已经知道它几乎是不可解的，那么我们就说这个算法是可证明安全的。这个听起来很好，但是阅读这些限制性附属细则是值得的。
“至少一样困难”是一个渐近的概念，对于“足够大”的问题实例它是成立的。然而，这个理论不会告诉你什么是足够大的。相反，你必须评估目前的计算设备的能力和算法设计的进展情况。例如，我们能够进行因式分解的数的大小在近几年中不断地增长。你会同意这是一个经验论点。甚至更坏的情况来了。密码系统特别偏爱的难解问题是因式分解和离散对数问题。现在并没有实际证明这些问题一定是难解的。又一次地，密码系统依赖于经验论证，到目前为止没有找到快速算法，因此极不可能有大的突破。为了更加肯定，这个观念也导致了建设性的结果，相对于破解其他的密码原型函数的难度，它给出了破解一个密码方案所要求的工作的下界。
可证明的安全算法可被拥有足够多计算资源的攻击者攻破。当然，你可以希望这些必需的资源超出了任何攻击者的能力。无条件安全算法不能被攻破，即使攻击者应用无限的计算能力。无条件安全是在按照信息论的概念来表示的。如果一个攻击者从观察密文没有获得关于明文的附加信息，则这个算法就是安全的。
无条件安全算法的标准例子是一次一密算法。发送者和接收者共享一个真正的随机密钥流，这些密钥只使用一次。密文是明文和密钥流的按位异或运算的结果。接收者采用相同的密钥流对密文进行按位异或运算，这样可以从密文中恢复出明文：
ciphertextkey streamplaintextkey streamkey streamplaintext。
因为每个密钥都是等概率的，攻击者不能猜测到关于明文的任何信息，在看到密文以前不可能对明文有任何的猜测。
注意！即使无条件安全的密码也已经被破解。当操作者抄近路和两次使用相同的密钥流时，攻击者叠加这两个密文将看到两个明文的组合：
ciphertext1ciphertext2
plaintext1key streamplaintext2key stream
plaintext1plaintext2。
理解两个覆盖在一起的明文消息完全不是一个困难的密码分析问题。Venona工程证明这样的事件甚至发生在冷战的最严重时期。
最后强调一个至关重要的事实。时常，密码系统被攻破是因为劣质的密钥管理而不是算法的固有弱点。在第二次世界大战时的Enigma(Enigma是纳粹德国在二战期间使用的转轮加密机－译者注)就是说明这种观点的最著名的例子。因此，密钥管理协议的安全就显得极端的重要。然而，安全协议的历史充满了令人讨厌的惊奇；到处都摆着这样的协议：在公认为安全的许多年后，突然就被一个新奇的攻击方法给攻破了。
公平地说，一些所谓的新奇的攻击方法只是简单地改变了协议使用方法的假设，证明了这个协议不能工作在新的环境。如果你追寻这些问题的根源，你将发现协议的设计者仍然在致力于精确定义他们的协议在什么条件下才能获得成功，在什么环境下才能使用。一个相当臭名昭著的例子就是实体认证。甚至连ISO工作组对实体认证是否包含了会话密钥的构建或者是否仅仅验证了一个声称的身份都持有不同的意见。
在这种上下文环境中，像“Alice对Bob讲”或者“Bob验证Alice的身份”这样的拟人化的说法都可能产生误导。在计算机安全中，实体是计算机，不是人类。它们通过网络发送消息，它们并没有谈话，你必须确定验证A的身份到底意味着什么。在计算机之间绝对没有可以看见的接触。
Alice和Bob是“语义心上人”（semantic sugar）。他们允许你描述美好的故事（语义细节），但他们也招致了你在错误的抽象层上的思考。
进一步的阅读如果你对秘密通信的历史感兴趣，文献[73]是一本比较好的参考书。最新的关于密码系统的专业化的参考可以阅读文献[99]。文献[137]给出了对现代密码学的比较好的、非数学的介绍，它还有一个非常丰富的参考目录，并收集了大量的密码算法。在这些书中，你可以找到在这一章中提到的算法的所有细节和进一步的信息。
文献[41]是公开密钥密码的基础论文，在早期它是CESG关于公开密钥系统研究的保密文档，仅仅在最近才去除了对它的限制。相关的报告已经被放到了他们的Web页面上：
http://www.cesg.gov.uk/storynse.htm
Venona文档可以在下面页面得到：
http://www.nsa.gov:8080/docs/venona/venona.html
关于对加密的挑战和一般的密码学的最新信息，可以访问：
http://www.rsa.com
对于在一个真实的密码协议方面的实例研究，检查OAKLEY密钥判决协议，它在IP协议层使用Diffie-Hellman和RSA作为密钥协商协议[120]。
不管Internet起草的简单公开密钥基础设施（SPKI）[46]的短暂性，在关于证书理论的讨论中它是必须提到的。对于证书和公开密钥基础设施，可以参考：
http://www.entrust.com 或者http://www.werisign.com
练习题练习题12.1 密码协议是用来使部门在不安全的网络上进行安全通信。这种说法正确吗？
练习题12.2 密码术需要物理安全。这句话在什么程度上是正确的？
练习题12.3 假设对一个n位整数的求幂模算法，它需要大约次操作，将它从512位的RSA体制发展到1024位的RSA中，将引起多少性能恶化？
练习题12.4 当一份文档太长而不能使用数字签名算法直接进行处理时，对文档计算散列值，然后对散列值进行签名。你要求这个散列函数具有什么样的性质，才能阻止攻击者伪造签名？
·一种情形是仅仅知道受害者签名的消息，另外一种情形是攻击者可以选择由受害者签名的消息。区分这两种情形。
·区别选择伪造（selective forgeries）和存在伪造（existential forgeries），其中选择伪造是攻击者已经控制了伪造消息的内容；存在伪造则是攻击者没有控制伪造消息的内容。
·研究与像RSA这样的可逆签名算法一起使用的散列函数的特定要求。
练习题12.5 对任何一对素数你能安全地使用RSA吗？研究使用“强素数”的理由和由一个“强素数”通常要求的性质。当素数变得很长的时候，你的理由仍然是有效吗？
练习题12.6 在El Gamal签名方案中，如果随机数被用来签两个不同的文档，说明私有签名密钥怎样可能被泄露？
练习题12.7 使用私有RSA指数加密并不能生成数字签名。试解释，如果没有对签名的消息进行冗余检查，攻击者怎样和在什么程度上进行伪造签名。
练习题12.8 证书基础设施对于支持数字签名方案是必须的。提议的范围从X.509的目录树一直到可信任的PGP网络。探讨为什么一个应用可能要求数字签名的理由。哪种证书方案最适合你已经确定的目的？
练习题12.9 NP-完全问题（NP-Complete）是构造密码算法的合适基础吗？
练习题12.10 密钥建立协议不仅仅对内部欺骗是脆弱的。对密钥交换协议做一个完全的威胁分析。
练习题12.11 修改Needham-Schroder密钥交换协议，使得两个参与者A和B都能对会话密钥的生成提供输入。
