翻译:中国科学技术大学信息安全专业老师 第12章密码学介绍 从前一大约在十年以前,你可能听说密码编码学( cryptography)对计算机安全没有作 出什么贡献。计算机安全是关于TCBs(可信计算基)的、引用监控、自主型和强制访问控 制、安全模型和系统规范的形式验证。按照这种观点,密码所起的作用实际上是外围的。在 安全操作系统当中,存储口令的单向函数仅仅是密码机制的一个明显的实例。 现在,倾向性却走到了另外一个极端。密码被看成了将解决所有计算机安全问题的神奇 的对策。安全操作系统由于太昂贵、使用太受限制和太远离用户的要求,而作为过去的事不 再考虑,它最终像恐龙绝迹一样消亡。密码能够提供这样重要的承诺吗? 目标 了解由于不同的目的使用密码的各种各样的应用 ·对密码学基本概念的介绍 理解密码能够解决问题的类型,在使用密码时需要解决的问题的类型。 ·指出要求支持密码的计算机安全的特征 121简介 密码编码学( cryptography)是书写秘密内容的学科,密码分析学( cryptanalysis)是破 解加密器( cipher)的学科,这两个主题就形成了密码学( Cryptology)。它们曾经是间谍和秘 密部门的领域,由于这些原因,现在仍然给密码罩上一层神秘的面纱。 现代密码学完全是一门数学的学科。对于很好地理解密码学出色的观点所必需的数学背 景的阐述已经超出了本书的范围。我们将尽力解释怎样把密码编码学用于计算机安全,并且 指出计算机安全常常是加密能起作用的一个先决条件。 12.1.老的范型( paradigms) 密码在通信安全中有它自己的根源。通信安全解决了在图121中描述的情况。两个实 体A和B通过一个不安全的信道通信。对抗者是一个入侵者,他可以完全控制这个信道, 能够读他们的消息,删除消息或者插入消息等。两个实体A和B是彼此信任的。他们想保 护通信不受入侵者的破坏。密码使得他们在不安全的物理连接上建立一条安全的逻辑信道。 图121通信安全 在这方面,密码与到目前为止讨论的计算机安全机制是有本质区别的。对于来自底层的 危害,它们全部都是脆弱的。然而,对物理通信链路的访问却不能威胁密码的保护。 在分布式系统中,客户和服务器之间的通信流对一个以入侵者自诩的人来说是一个新的 攻击点。不安全通信链路引入的脆弱性自然能够由通信安全服务和机制来解决。这些服务包 数据机密性:加密算法隐藏了消息的内容 数据完整性:完整性检测功能提供了检测文档是否被改变的方法 第1页共19页 创建时间:2003/7/91446:00
翻译：中国科学技术大学信息安全专业老师 第 1 页 共 19 页 创建时间：2003/7/19 14:46:00 第 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新的范型 让我们关注新鲜的事物。在电子商务中,顾客进入了一个与商家有关的商业事务。两个 参与者都不希望另一方欺骗,但是,纠纷却有可能发生,并且预先有一致的规则总比在发生 纠纷时再采取特定的方式解决要好些。顾客和商家都有运行一个协议的理由,协议并不假设 对方在任何环境下都是可信任的。现在的对抗者是一个误操作的内部人员,而不是一个入侵 者,在图122所示的第三个参与者不再是一个入侵者,而是一个可信任的第三方(TTP), 例如,一个仲裁者。在解决纠纷的时候,不可否认(non- repudiation)服务生成了在解决争 端时仲裁者将要考虑的证据 图122电子商务安全 许多国家都有法律,规定法律执行代理(LEA, law enforcement agent)在什么时候、怎 样获得侦听许可证,以便责成电信服务提供者给他们接入到特定用户之间的通信的权利。现 在,在图12.3中的第三方是一个通信操作员的客户,必须给他提供一个合法的侦听服务。 在这种上下文中,密钥托管服务分发用于加密通信的密钥:密钥托管服务也是目前令人激动 的研讨课题 图12.3通信安全和法律实施 12.1.3密码的密钥 密码员采用锁作为他们特别喜爱的图标,以表示他们给公众提供安全服务。快速査看目 前的允许安全的web浏览器或者e-mai产品的用户接口就能够证实这种观察。但是类推充 满了危险,你不应该过分地信任它们,但是也有一些重要的概念从锁匠传承到了密码员。锁 上门或者打开门上的锁,你需要一把钥匙。从强度上分,锁是不同的。有些很容易撬开,而 其他的锁是如此坚固,以致入侵者不得不采用蛮力攻击破门而入,或者选择一条完全不同的 路径,并且改为从房间的窗户进入房间 密码算法使用密钥来保护数据。从实现方法的强度和范围来看又有各种变种,其中的一 些使用简单的统计方法就可以破解,而另外一些远远超出了目前的数学分析和计算能力所能 够达到的范围。蛮力攻击穷尽一切可能地搜索整个密钥空间,它给出了算法强度的上限 现代密码系统并不依赖于算法的保密。在密码变换中使用的密钥才是唯一需要保护的内 容。这个原则是在上个世纪由 Kerckhoffs提出并作为基本条件的,在我们的新安全范型中是 第2页共19页 创建时间:2003/7/91446:00
翻译：中国科学技术大学信息安全专业老师 第 2 页 共 19 页 创建时间：2003/7/19 14:46:00 ·数据源认证： 消息认证码或者数字签名算法提供了验证消息来源和它的完整性的方 法。 在我们的定义中，数据完整性实际上不是适合通信安全的的概念。消息就基本性而言总 是有一个发送者。如果你接收到一个消息，但不知道谁发送了它，你怎么能够断言它在传输 过程中并没有被修改呢？因此，当你没有验证消息来源的时候，就无法验证它的完整性。另 一方面，你不应该声称已经验证了在传输过程中已被更改了的消息的来源。因此，数据来源 认证包括消息完整性认证，并且我们的数据完整性的概念，更适合于应用而不是通信，比如， 反病毒软件的文件保护。 谁是朋友，谁是敌人这种传统的观点也在计算机安全中有了它自己的位置，但它不再是 驱动计算中密码应用的主要理由。不幸的是，它仍然支配着公众对密码的理解。同样的观点 也反映在用于密码协议的许多验证工具的公理上，它们假设实体 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.14模运算 相当多的现代密码算法都建立在代数学原理的基础上。这些算法可以定义在令人兴奋的 代数结构上,比如椭圆曲线或者伽罗瓦域(有限域)。然而,我们仍然有点停留在实际应用 上,且在它们描述中仅使用整数。在这里,我们将解释一些关于模运算的基本知识,作为后 面描述内容的基础 令m是一个整数。在后面的描述中,我们将m称为模数( modulus)。然后在整数集合 上定义了一个等价关系‘≡ a=bmdm,当且仅当a-b=λ·m,这里,λ是某些整数 我们则说“a等价于b以m为模”。你可以检验‘≡’确实是一个等价关系,它把整数集合 划分成关于m的m个等价类 (a)m=(bla=bmod m),0<a<m 我们更习惯用amdm的形式来表示等价类,我们将遵循这个约定。你可以证明下列 有用的性质: (amod m)+(b mod m)=(a+b)mod m (amod m). (b mod m)=(a-b)mod m 除此之外,对于每一个a≠0modp,p是素数,存在一个整数a-,使得 aa=1mdp。对于一个素模数p,以p为模的乘法阶定义为: 定义令p是一个素数,a是一个任意整数。a模p的乘法阶定义为满足下面关系 的最小整数n:a"≡ I mod p 第3页共19页 创建时间:2003/7/91446:00
翻译：中国科学技术大学信息安全专业老师 第 3 页 共 19 页 创建时间：2003/7/19 14:46:00 非常适用的，在这里必须支持大量具有竞争利益的用户团体。在这种环境下，形成事实上的 标准和对公开算法的开放评估都是很自然的过程，使得每一个参与者都有机会进行他们自己 的安全评估，使新的参与者更容易加入。 因而，从最一般的字面意义上理解，密钥管理对密码机制的安全是极为重要的。你必须 处理下面这些问题： ·密钥在哪儿生成？ ·密钥怎样生成？ ·密钥在哪儿存储？ ·密钥怎样分发？ ·密钥实际上在什么地方使用？ ·密钥怎样撤销和替换？ 在这一点上，圆是闭合的，我们又回到计算机安全。密码密钥是存储在计算机系统中的 敏感数据，计算机系统中的访问控制机制必须保护这些密钥。当访问控制失败时，密码保护 受到了威胁。在大多数目前实施的安全系统中，密码算法是最强的部分，且老谋深算的攻击 者将寻找其他的脆弱性，而不是把他们的时间浪费在密码分析上。 密码对安全问题来说，在任何时候都是一个罕见的解决方案。密码是一个变换机制，它通常把通信安 全问题转化为密钥管理问题，而最终转化成了计算机安全问题。希望最后的问题比原来的问题更容易解决。 总之，密码能够加强计算机安全，但它并不是计算机安全的替代品。 12.1.4 模运算 相当多的现代密码算法都建立在代数学原理的基础上。这些算法可以定义在令人兴奋的 代数结构上，比如椭圆曲线或者伽罗瓦域（有限域）。然而，我们仍然有点停留在实际应用 上，且在它们描述中仅使用整数。在这里，我们将解释一些关于模运算的基本知识，作为后 面描述内容的基础。 令 m 是一个整数。在后面的描述中，我们将 m 称为模数（modulus）。然后在整数集合 上定义了一个等价关系‘ ’： a bmod m ，当且仅当 a −b = m ，这里， 是某些整数， 我们则说“ a 等价于 b 以 m 为模”。你可以检验‘ ’确实是一个等价关系，它把整数集合 划分成关于 m 的 m 个等价类： (a)m ={b | a bmod m},0 a m 我们更习惯用 amod m 的形式来表示等价类，我们将遵循这个约定。你可以证明下列 有用的性质： (amod m) + (bmod m) (a + b)mod m (amod m)(bmod m) (a b)mod m 除 此 之 外， 对于 每 一个 a 0mod p ， p 是 素 数 ，存 在 一个 整数 −1 a ，使得 a a 1mod p 1 − 。对于一个素模数 p ，以 p 为模的乘法阶定义为： 定义 令 p 是一个素数， a 是一个任意整数。 a 模 p 的乘法阶定义为满足下面关系 的最小整数 n： a p n 1mod
翻译:中国科学技术大学信息安全专业老师 费尔马小定理对于每一个a≠0modp,p是素数,有ap≡ I mod p 这个定理表示,任何一个以p为模的非零元素的乘法阶必定是p-1的因子。这个事实 被用于构造相当多的密码算法。这些算法的安全性常常是相关的,在少数场合是等价的,来 自数论中的下述问题中的任何一个都是难解的 离散对数问题(DLP):给定一个作为模的素数p,基数a和值y,根据等式 y≡a3modp,求出y的离散对数x n次方根问题:给定一个整数m,n和a,求出一个整数b,使它满足 a=b"modm。解b就叫做q模m的n次方根 因式分解问题:给定一个整数(合数)n,找出它的素数因子 在参数的正确选择情况下,这些问题是许多密码算法的合适的基础。然而,并不是这些 问题的所有实例都是难解的。很明显,如果p或者n是比较小的整数,那么这些问题就可 以在合理的时间范围内采用穷举搜索来求解。目前,二进制512位的整数已被认为是位数较 短的整数了,一般都推荐使用1024位整数,当然,如果你能够容忍由于算术运算占用更长 的时间而引起性能的下降,你可以使用更长的整数。长度不是你必须考虑的唯一方面。这些 问题的难度也依赖于p和n的结构。(为了进一步追究这个课题,你必须放下这本书,而寻 找一些更专业化的数学方面的书籍来阅读。) 122密码机制 密码机制是密码方案的最基本的构造模块。它们被用在密码协议中,且依赖于好的密钥 管理来提供有效的保护。最频繁应用于计算机安全的密码机制是 加密( encryption)算法 数字签名( digital signature)方案 ·完整性检查功能(密码散列函数,即hash函数)。 为了舍弃传统密码,我们将以相反的顺序来介绍这些概念。 12.2.1完整性检查功能 依赖于特殊应用的需求,对密码散列函数的要求也有一些微妙的差别。我们列出了散列 函数h的一些基本性质,由此来展开这一节的讨论 容易计算:给定x,容易计算h(x)。 ·压缩:对于任意输入长度的x,函数h最后都生成固定长度n的输出h(x)。 预映射抗拒性(单向性):给定一个值y,为了找到x满足h(x)=y,通常在计算 上是不可行的。 第2次预映射抗拒性(弱冲突抗拒性):给定输入x和h(x),求出另外一个x',且 第4页共19页 创建时间:2003/7/91446:00
翻译：中国科学技术大学信息安全专业老师 第 4 页 共 19 页 创建时间：2003/7/19 14:46:00 费尔马小定理 对于每一个 a 0mod p ， p 是素数，有 a p p 1mod 1 − 。 这个定理表示，任何一个以 p 为模的非零元素的乘法阶必定是 p −1 的因子。这个事实 被用于构造相当多的密码算法。这些算法的安全性常常是相关的，在少数场合是等价的，来 自数论中的下述问题中的任何一个都是难解的： ·离散对数问题（DLP）： 给定一个作为模的素数 p ，基数 a 和值 y ，根据等式 y a p x mod ，求出 y 的离散对数 x 。 · n 次方根问题： 给定一个整数 m ， n 和 a ，求出一个整数 b ，使它满足 a b m n mod 。解 b 就叫做 a 模 m 的 n 次方根。 ·因式分解问题： 给定一个整数（合数） n ，找出它的素数因子。 在参数的正确选择情况下，这些问题是许多密码算法的合适的基础。然而，并不是这些 问题的所有实例都是难解的。很明显，如果 p 或者 n 是比较小的整数，那么这些问题就可 以在合理的时间范围内采用穷举搜索来求解。目前，二进制 512 位的整数已被认为是位数较 短的整数了，一般都推荐使用 1024 位整数，当然，如果你能够容忍由于算术运算占用更长 的时间而引起性能的下降，你可以使用更长的整数。长度不是你必须考虑的唯一方面。这些 问题的难度也依赖于 p 和 n 的结构。（为了进一步追究这个课题，你必须放下这本书，而寻 找一些更专业化的数学方面的书籍来阅读。） 12.2 密码机制 密码机制是密码方案的最基本的构造模块。它们被用在密码协议中，且依赖于好的密钥 管理来提供有效的保护。最频繁应用于计算机安全的密码机制是： ·加密（encryption）算法， ·数字签名（digital signature）方案， ·完整性检查功能（密码散列函数，即 hash 函数）。 为了舍弃传统密码，我们将以相反的顺序来介绍这些概念。 12.2.1 完整性检查功能 依赖于特殊应用的需求，对密码散列函数的要求也有一些微妙的差别。我们列出了散列 函数 h 的一些基本性质，由此来展开这一节的讨论： ·容易计算： 给定 x ，容易计算 h(x) 。 ·压缩：对于任意输入长度的 x ，函数 h 最后都生成固定长度 n 的输出 h(x) 。 ·预映射抗拒性（单向性）： 给定一个值 y ，为了找到 x 满足 h(x) = y ，通常在计算 上是不可行的。 ·第 2 次预映射抗拒性（弱冲突抗拒性）： 给定输入 x 和 h(x) ，求出另外一个 x' ，且
翻译:中国科学技术大学信息安全专业老师 x≠x,使得h(x)=h(x),在计算上是不可行的。 冲突抗拒性(强冲突抗拒性):求出任何两个输入x和x,使得h(x)=h(x)成立 在计算上是不可行的 操作检测码( manipulation detection codes,MDCs),也称为修改检测码或者消息完整 码,常常用于检査文档是否发生改变。在文献[99]中提到了两种形式, 单向散列函数(OwHF)具有压缩性、易计算性、预映射抗拒性和第2次预映射抗拒 性等性质。 冲突抗拒散列函数(CRH)具有压缩性、易计算性、第2次预映射抗拒性和冲突抗 拒性等性质 应用散列函数计算的结果分别不同地称为: 散列值( hash value) 消息摘要( message digest) ·校验和( checksum) 最后一个术语为混淆留下了巨大的空间。在通信安全中,校验和是指错误校正码,典型 的是循环冗余校验码(CRC)。另一方面,校验和也被用在反病毒软件的产品中,但是禁止 使用CRC来计算,而必须使用密码散列函数(MDC)来计算。令x是被禁止篡改的程序 在一个没有病毒的环境下计算散列值h(x),并且把结果存储在不能修改它的位置,例如,存 放在CD-ROM上。为了检査程序的状态,重新计算散列值,把它与原来存储的值进行比较。 散列值的保护是重要的。计算散列值并不要求任何秘密的信息,因此,任何人都能对一个给 定的文件计算有效的散列值。 当参数p和g明智地选择时,函数f(x)=gmdp是一个单向函数,这个函数称为 离散求幂。为了反向离散求幂,你必须解决在12.1.4节介绍的离散对数问题。在这一章的 后面你可以看到离散求幂在密码方案的构造中是真正有用的原函数。然而,离散求幂并不是 特别快的操作,当你需要高速处理大量的数据时,你必须转而采用其他的算法 快速散列函数倾向使用类似的设计模式来构造。散列函数的核心是一个压缩函数f∫ 它处理固定长度的输入。一个任意长度的输入x被分割成给定块大小的块x1、…、xm,如 果最后一个块没有达到固定长度,就使用填充的方法使它达到固定的长度。x的散列值则可 以通过反复的使用压缩函数获得。令h是一个(固定的)初始化值。计算 h=∫(x1‖h1-1),i 且取h作为x的散列值,如图124所示。(符号表示级联) 消息认证码(MACs)对消息的来源和完整性提供了保证(数据源认证)。MAC从两个 输入即消息和秘密的密码密钥计算得到。因此,MAC有时也叫做密钥散列函数。正式地说, MAC是用密钥k作为参数化的散列函数h的族。这个族中的每一个成员都具有压缩和容易 计算的特性,附加的抗计算特性也必须满足。 对于任何固定的k值,给定一个值集合(x12h2(x),当攻击者不知道这个固定的k值时,对任何 第5页共19页 创建时间:2003/7/91446:00
翻译：中国科学技术大学信息安全专业老师 第 5 页 共 19 页 创建时间：2003/7/19 14:46:00 x x',使得 h(x) = h(x') ，在计算上是不可行的。 ·冲突抗拒性（强冲突抗拒性）：求出任何两个输入 x 和 x' ，使得 h(x) = h(x') 成立， 在计算上是不可行的。 操作检测码（manipulation detection codes ，MDCs），也称为修改检测码或者消息完整 码，常常用于检查文档是否发生改变。在文献[99]中提到了两种形式, ·单向散列函数（OWHF）具有压缩性、易计算性、预映射抗拒性和第 2 次预映射抗拒 性等性质。 ·冲突抗拒散列函数（CRHF）具有压缩性、易计算性、第 2 次预映射抗拒性和冲突抗 拒性等性质。 应用散列函数计算的结果分别不同地称为：： ·散列值（hash value） ·消息摘要（message digest） ·校验和（checksum） 最后一个术语为混淆留下了巨大的空间。在通信安全中，校验和是指错误校正码，典型 的是循环冗余校验码（CRC）。另一方面，校验和也被用在反病毒软件的产品中，但是禁止 使用 CRC 来计算，而必须使用密码散列函数（MDC）来计算。令 x 是被禁止篡改的程序。 在一个没有病毒的环境下计算散列值 h(x)，并且把结果存储在不能修改它的位置，例如，存 放在 CD-ROM 上。为了检查程序的状态，重新计算散列值，把它与原来存储的值进行比较。 散列值的保护是重要的。计算散列值并不要求任何秘密的信息，因此，任何人都能对一个给 定的文件计算有效的散列值。 当参数 p 和 g 明智地选择时，函数 f x g p x ( ):= mod 是一个单向函数，这个函数称为 离散求幂。为了反向离散求幂，你必须解决在 12.1.4 节介绍的离散对数问题。在这一章的 后面你可以看到离散求幂在密码方案的构造中是真正有用的原函数。然而，离散求幂并不是 特别快的操作，当你需要高速处理大量的数据时，你必须转而采用其他的算法。 快速散列函数倾向使用类似的设计模式来构造。散列函数的核心是一个压缩函数 f ， 它处理固定长度的输入。一个任意长度的输入 x 被分割成给定块大小的块 1 x 、…、 m x ，如 果最后一个块没有达到固定长度，就使用填充的方法使它达到固定的长度。 x 的散列值则可 以通过反复的使用压缩函数获得。令 0 h 是一个（固定的）初始化值。计算 ( || ) i = i hi−1 h f x ，i =1, ,m ， 且取 mh 作为 x 的散列值，如图 12.4 所示。（符号||表示级联） 消息认证码（MACs）对消息的来源和完整性提供了保证（数据源认证）。MAC 从两个 输入即消息和秘密的密码密钥计算得到。因此，MAC 有时也叫做密钥散列函数。正式地说， MAC 是用密钥 k 作为参数化的散列函数 k h 的族。这个族中的每一个成员都具有压缩和容易 计算的特性，附加的抗计算特性也必须满足。 对于任何固定的 k 值，给定一个值集合 ( , ( )) i k i x h x ，当攻击者不知道这个固定的 k 值时，对任何
翻译:中国科学技术大学信息安全专业老师 新的输入x,在计算上来说,要计算出h(x)是不可行的。 为了认证一个消息,接收者必须与发送者共享密码密钥,用来计算MAC。不知道密钥 的第三方不可能确认MAC。使用下面的HMAC构造方法,一个MAC算法则可以从MDC 算法h推导出来。计算 HMAC(x)=h(k‖p2l‖h(k‖p2‖x) 其中P1和p2是填充的位串,它把k扩展成在h中使用的压缩函数需要的长度。 图12.4hash函数构造 安全散列算法 我们将选择安全散列算法(SHA-1)来说明散列函数实际上是怎样设计的。这个算法被 指定用于美国的数字签名标准(DSA)。其他的散列函数是MD4(不是那么强有力的)、MD5 ( Internet协议中的标准选择)和 RIPE-MD。SHA-1处理任意多个512位的数据块,生成 个160位的散列值。参数可以被作为整数解释也可以作为位串解释。在位串和整数之间的转 换算法在我们的描述中省略掉了 输入的末尾将用一个1来填充,然后是一个0串,以使得最后的输入块有448位长度 且最后64位字段指示在填充前输入数据的长度。初始化的值由五个32位的值定义,以十六 进制数表示: A=67452301 D=10325476 E=C3d2elfo SHA-1的压缩函数在一个80步的循环中处理512位的输入,每20步改变一次内部函 数和常数,最后生成一个160位的输出。这些函数是: f(X,H,Z)=(X∧)(X)入Z)t=0.…,19 f(X,Y,2Z)=X⊕Y⊕zt=20,…39, f(x,y,Z)=(XAY)v(X∧2)V(Y∧乙)t=40,…,59, f(X,H,Z)=XGY⊕Zt=60,…,79。 其中,操作符是位与、位或和异或,应用到32位字上去。常数采用十六进制数表示,它们 是 K.=5a827999 K1=6ed9eblt=20,…,39, K, =8flbbcdc t=40, .. 59 第6页共19页 创建时间:2003/7/91446:00
翻译：中国科学技术大学信息安全专业老师 第 6 页 共 19 页 创建时间：2003/7/19 14:46:00 新的输入 x ，在计算上来说，要计算出 h (x) k 是不可行的。 为了认证一个消息，接收者必须与发送者共享密码密钥，用来计算 MAC。不知道密钥 的第三方不可能确认 MAC。使用下面的 HMAC 构造方法，一个 MAC 算法则可以从 MDC 算法 h 推导出来。计算 ( ) ( || || ( || || )) 1 2 HMAC x = h k p h k p x 其中 1 p 和 2 p 是填充的位串，它把 k 扩展成在 h 中使用的压缩函数需要的长度。 图 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 位的输出。这些函数是： f (X,Y,Z) (X Y) (( X) Z) t = t = 0, ,19 ， f t (X,Y,Z) = X Y Z t = 20, ,39 ， f (X,Y,Z) (X Y) (X Z) (Y Z) t = t = 40, ,59 ， f t (X,Y,Z) = X Y Z t = 60, ,79 。 其中，操作符是位与、位或和异或，应用到 32 位字上去。常数采用十六进制数表示，它们 是： Kt = 5a827999 t = 0, ,19 ， Kt = 6ed9eba1 t = 20, ,39， K f bbcdc t = 8 1 t = 40, ,59
翻译:中国科学技术大学信息安全专业老师 K,=c62cld6t=60,…,79 在压缩函数开始的时候,五个32位的变量a、b、c、d和e是用散列函数的中间值 来初始化的。对于第一个输入块,则使用初始值A、B、C、D和E。512位的输入块被 分成了16个32位的字m,并且使用下面的算法,将它们扩展成80个32位的字w: t=0.….15 v1=(w1-3W8由w14④w215)<<1t=16,…79, 其中,符号<<<s表示循环左移s位。现在压缩函数执行下面的循环,其中加法使用模232运 for t=0 to 79 do temp=(a<<<5)+ f(b, c, d )+e+wt+kt c=b<<<30 a-=temp 最后,变量a、b、C、d和e的值被加入到前面的中间散列值中。在处理下一个输入 块的时候,这个结果用作初始的散列值 12.22数字签名 在图12.1中,消息认证码帮助参与者A和B检测在通信信道中由入侵者插入的欺骗消 息。然而,消息认证码并不生成任何证据,供第三方用来判断A或者B是否发送了特定的 消息。因此,在图12.2的电子商务中,顾客需要确保商家不能伪造订单,且商家需要确保 顾客必须认可他们所下的订单,在这样的情况下,消息认证码几乎是没有什么用处的,因而 数字签名就很有必要了。 数字签名方案由签名算法和验证算法组成。一份文档的数字签名是一个值,它依赖于文 档内容和仅由签名者知道的某个秘密,即私有签名密钥;私有签名密钥把文档与一个实体联 系在一起,即公开的验证密钥。验证算法通常使用文档和公开验证密钥作为输入,但是在 些异常的情况下,文档或者文档的一部分可以从签名中恢复出来,且对于签名验证不一定要 提供文档。下述的可验证特性表示了数字签名方案的特征: 规则第三方可以在不知道签名者的私有密钥的情况下,解决关于数字签名有效性的纠纷 数字签名支持不可否认性。公开密钥密码(见12.23节)是数字签名方案的自然来源。 在这种方案中,私有密钥和公开验证密钥之间的联系,是为了确保从验证密钥中推导出签名 密钥在计算上是不可行的。不管在数学基础上的相似性,你应该推断出数字签名和公开密钥 加密算法之间清楚的区别。这两种方案从根本上满足了不同的技术目的。加密保护了消息的 机密性,因此必须是可逆的。数字签名提供了数据来源的认证和不可否认性。数字签名算法 不必是可逆的,事实上,可逆性会引起一些附加的安全担心 次性签名 第7页共19页 创建时间:2003/7/91446:00
翻译：中国科学技术大学信息安全专业老师 第 7 页 共 19 页 创建时间：2003/7/19 14:46:00 Kt = ca62c1d6 t = 60, ,79。 在压缩函数开始的时候，五个 32 位的变量 a 、b 、c 、 d 和 e 是用散列函数的中间值 来初始化的。对于第一个输入块，则使用初始值 A 、 B 、C 、 D 和 E 。512 位的输入块被 分成了 16 个 32 位的字 mt ，并且使用下面的算法，将它们扩展成 80 个 32 位的字 wt ： wt = mt t = 0, ,15 ， wt = (wt−3 wt−8 wt−14 wt−16 ) 1 t =16, ,79 ， 其中，符号 s 表示循环左移 s 位。现在压缩函数执行下面的循环，其中加法使用模 32 2 运 算： 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; 最后，变量 a、b 、 c 、 d 和 e 的值被加入到前面的中间散列值中。在处理下一个输入 块的时候，这个结果用作初始的散列值。 12.2.2 数字签名 在图 12.1 中，消息认证码帮助参与者 A 和 B 检测在通信信道中由入侵者插入的欺骗消 息。然而，消息认证码并不生成任何证据，供第三方用来判断 A 或者 B 是否发送了特定的 消息。因此，在图 12.2 的电子商务中，顾客需要确保商家不能伪造订单，且商家需要确保 顾客必须认可他们所下的订单，在这样的情况下，消息认证码几乎是没有什么用处的，因而 数字签名就很有必要了。 数字签名方案由签名算法和验证算法组成。一份文档的数字签名是一个值，它依赖于文 档内容和仅由签名者知道的某个秘密，即私有签名密钥；私有签名密钥把文档与一个实体联 系在一起，即公开的验证密钥。验证算法通常使用文档和公开验证密钥作为输入，但是在一 些异常的情况下，文档或者文档的一部分可以从签名中恢复出来，且对于签名验证不一定要 提供文档。下述的可验证特性表示了数字签名方案的特征： 规则 第三方可以在不知道签名者的私有密钥的情况下，解决关于数字签名有效性的纠纷。 数字签名支持不可否认性。公开密钥密码（见 12.2.3 节）是数字签名方案的自然来源。 在这种方案中，私有密钥和公开验证密钥之间的联系，是为了确保从验证密钥中推导出签名 密钥在计算上是不可行的。不管在数学基础上的相似性，你应该推断出数字签名和公开密钥 加密算法之间清楚的区别。这两种方案从根本上满足了不同的技术目的。加密保护了消息的 机密性，因此必须是可逆的。数字签名提供了数据来源的认证和不可否认性。数字签名算法 不必是可逆的，事实上，可逆性会引起一些附加的安全担心。 一次性签名
翻译:中国科学技术大学信息安全专业老师 你不需要为构造一个签名方案而钻研数学。为了获得一次性签名,你仅仅需要一个密码 散列函数h就可以了1。为了对一份n位的文档签名,随机选择2n个值的x0和x,1作为你 的私有密钥,且公布y0=h(x10)和y21=(x1),1≤i≤n,作为你的公开密钥。对文档m 的签名s的第i部分则由下式给出 Rio mi S 很明显,你不能再次使用你的私有密钥,因此,这就是一次性签名的由来。验证者拥有 你的公开密钥,并进行检查: h( 0 y1=h(s)m2=1 你将发现,验证者需要附加的证据来进一步证实数值y0和y1确实是你的公开密钥 我们将在124节回到这个主题。 此外,除了依赖数学问题的难解性或者依赖其他的一些密码原函数的强度,你还可以依 赖抗损害硬件设备的难度。这个设备包括一个秘密的签字密钥和/或者秘密的验证密钥。这 个设备是这样构造的,以至它不能使用签名密钥来验证或者用验证密钥来签名。为了签名 份文档,设备使用它的签名密钥构造MAC,然后把它附加到文档上。为了验证这个签名 验证者的设备必须拥有签字者的签名密钥作为验证密钥,用这个密钥来生成MAC,把它同 接收到的签名进行比较 E|Gama|签名和DSA 在文献[45]中的 EI Gamal签名方案用实例说明了签名不是用私有密钥加密。令p是一 个大的和适当选择的素数。令g是以p为模的阶为p-1的整数。令a是用户A的私有签名 密钥,且y=g“modp是对应的公开验证密钥 假设要签的文档是一个整数m,0≤m<p。另外,你也可以应用一个合适的散列函数, 然后对文档的摘要进行签名。为了对m进行签名,用户选择了一个随机数k,0≤k<p 以使得gcd(k,p-1)=1,计算r=gmop,并且解方程: ar+k·s≡ mmod(p-1) 求解未知的S。整数对(r,s)构成A对m的签名。验证者需要A的验证密钥y,并检查 P 对于一个正确的签名,等式: =gar+kr g mod p 第8页共19页 创建时间:2003/7/91446:00
翻译：中国科学技术大学信息安全专业老师 第 8 页 共 19 页 创建时间：2003/7/19 14:46:00 你不需要为构造一个签名方案而钻研数学。为了获得一次性签名，你仅仅需要一个密码 散列函数 h 就可以了[81]。为了对一份 n 位的文档签名，随机选择 2n 个值的 i,0 x 和 i,1 x 作为你 的私有密钥，且公布 ( ) i,0 i,0 y = h x 和 ( ) i,1 i,1 y = h x ，1 i n ，作为你的公开密钥。对文档 m 的签名 s 的第 i 部分则由下式给出： = = = 1 0 ,1 ,0 i i i i i x m x m s 很明显，你不能再次使用你的私有密钥，因此，这就是一次性签名的由来。验证者拥有 你的公开密钥，并进行检查： ( ) 1. ( ) 0, ,1 ,0 = = = = i i i i i i y h s m y h s m 你将发现，验证者需要附加的证据来进一步证实数值 i,0 y 和 i,1 y 确实是你的公开密钥。 我们将在 12.4 节回到这个主题。 此外，除了依赖数学问题的难解性或者依赖其他的一些密码原函数的强度，你还可以依 赖抗损害硬件设备的难度。这个设备包括一个秘密的签字密钥和/或者秘密的验证密钥。这 个设备是这样构造的，以至它不能使用签名密钥来验证或者用验证密钥来签名。为了签名一 份文档，设备使用它的签名密钥构造 MAC，然后把它附加到文档上。为了验证这个签名， 验证者的设备必须拥有签字者的签名密钥作为验证密钥，用这个密钥来生成 MAC，把它同 接收到的签名进行比较。 EIGamal 签名和 DSA 在文献[45]中的 EI Gamal 签名方案用实例说明了签名不是用私有密钥加密。令 p 是一 个大的和适当选择的素数。令 g 是以 p 为模的阶为 p −1 的整数。令 a 是用户 A 的私有签名 密钥，且 y g p a a = mod 是对应的公开验证密钥。 假设要签的文档是一个整数 m ，0 m p 。另外，你也可以应用一个合适的散列函数， 然后对文档的摘要进行签名。为了对 m 进行签名，用户选择了一个随机数 k ，0 k p ， 以使得 gcd(k, p −1) =1 ，计算 r g p k = mod ，并且解方程： a r + k s mmod( p −1) 求解未知的 s 。整数对 (r,s) 构成 A 对 m 的签名。验证者需要 A 的验证密钥 a y ，并检查： y r g p r s m a mod ? = 对于一个正确的签名，等式： y r g g p r s ar ks m a = = mod +
翻译:中国科学技术大学信息安全专业老师 也是成立的。这种方案的安全与离散对数问题紧密相关,但是并不等价于离散对数问题。许 多更安全和更有效的签名方案都是从 EI Gamal签名方案派生而来的。一个这样的签名算法 是数字签名算法(DSA, digital signature algorithm)1。在这个方案中,用户A的私有密 钥和公开密钥通过下述步骤生成 1)选择一个素数q,2139<q<216。 2)选择一个整数t,0≤t≤8,和一个素数p,21164<p<2312+,所以q整除p-1。 3)选择a,1<a<p-1,并计算g= a(p-l)q mod p。如果g=1,用一个新的a再 试。(这一步计算以p为模的阶q的生成元g。) 4)选择一个a,使其满足1≤a≤q-1。 5)计算y=g"mdp。 6)A的私有密钥就是数值a,公开密钥是(p,q1,g,y)。 A为了对文档m进行签名,使用SHA-1计算散列值h(m),并且转换成一个整数,然 后 7)随机地选择一个整数k,1≤k≤q-1。 8)计算r=( g mod p)modq 9)计算 k-mod q 10)计算s=k-(h(m)+ar)modq。 A对m的签名就是整数对(r,S)。这个签名将用A的公开密钥(P,q,g,y)进行检测: 验证1≤r≤q和1≤s≤q 计算= s-mod q 计算41=W,h(m)mdq和l2=rwmd 计算v=(g“y“modp)modq 当且仅当ν=r,则通过验证 RSA签名 在文献[127]中描述的RSA算法是用它的发明者 Rivest、 Shamir和 Adleman的第一个 字母命名的,它同样可以用于签名和加密。RSA的这种特定的性质必须对许多关于数字签 名和公开密钥密码的流行的误解负责。在RSA签名方案中,用户A选择两个素数p和q, 第9页共19页 创建时间:2003/7/91446:00
翻译：中国科学技术大学信息安全专业老师 第 9 页 共 19 页 创建时间：2003/7/19 14:46:00 也是成立的。这种方案的安全与离散对数问题紧密相关，但是并不等价于离散对数问题。许 多更安全和更有效的签名方案都是从 EI Gamal 签名方案派生而来的。一个这样的签名算法 是数字签名算法（DSA，digital signature algorithm）[116]。在这个方案中，用户 A 的私有密 钥和公开密钥通过下述步骤生成。 1）选择一个素数 q ， 159 160 2 q 2 。 2）选择一个整数 t ，0 t 8 ，和一个素数 p ， t t p 511 64 512 64 2 2 − + ，所以 q 整除 p −1。 3）选择 ，1 p −1 ，并计算 g p p q mod ( −1)/ = 。如果 g = 1 ，用一个新的 再 试。（这一步计算以 p 为模的阶 q 的生成元 g 。） 4）选择一个 a ，使其满足 1 a q −1。 5）计算 y g p a = mod 。 6）A 的私有密钥就是数值 a ，公开密钥是 ( p,q, g, y)。 A 为了对文档 m 进行签名，使用 SHA-1 计算散列值 h(m) ，并且转换成一个整数，然 后： 7）随机地选择一个整数 k ，1 k q −1。 8）计算 r g p q k = ( mod )mod 。 9）计算 k mod q −1 。 10）计算 s k (h(m) ar)mod q 1 = + − 。 A 对 m 的签名就是整数对 (r,s) 。这个签名将用 A 的公开密钥 ( p,q, g, y) 进行检测： ·验证 1 r q 和 1 s q ·计算 w s mod q −1 = ·计算 u1 = wh(m)mod q 和 u2 = rwmod q ·计算 v g y p q u u ( mod )mod 1 2 = ·当且仅当 v = r ，则通过验证。 RSA 签名 在文献[127]中描述的 RSA 算法是用它的发明者 Rivest、Shamir 和 Adleman 的第一个 字母命名的，它同样可以用于签名和加密。RSA 的这种特定的性质必须对许多关于数字签 名和公开密钥密码的流行的误解负责。在 RSA 签名方案中，用户 A 选择两个素数 p 和 q
翻译:中国科学技术大学信息安全专业老师 和一个私有签名密钥e,满足gcd(e,p-1)=1和gcd(e,q-1)=1。公开验证密钥则由积 n=pq和指数d组成,并且满足 ed= I mod lcn(p-1,q-1),lcm(p-1,q-1)是欧拉商数。 签名的文档是整数m,≤m<n。为了验证者能识别真正的文档,这个文档必须包含 足够的冗余信息。如果原始文档太长,可以应用散列函数和填充获得摘要进行签名。为了签 名m,用户A用下式生成签名 s=m mod 验证者需要A的验证密钥(n,d),并且检查 d n 是否成立。对于一个正确的签名来说,这个等式是成立的,因为 S·=m= m mod i 短文档可以从签名中恢复,并且不必分别传送。RSA安全与因式分解的难度是相关的 但是并不等价于它的难度。 在某些签名方案中(RSA是基本的范例),你可以选择公开验证密钥,因此签名验证特 别快。图12.5中的表给出了对于1024位参数运行在相当快的机器上的DSA和RSA的性能 的粗略比较,以及一个签名方案的不同部分要求的工作的比较。(信息由在 KU leaven的 ESAT提供。) 图12.5RSA同DSA的比较 12.2.3加密 我们保留了术语加密( encryption),它表示保护数据机密性的算法。加密算法,也叫做 密码( cipher),在密码密钥的控制下,将明文( plain text或 clear text)加密成密文( cipher text) 用适当的解密密钥解密( decryption),可从密文中恢复明文。有些加密算法提供了检测违反 完整性的方法,但情况不总是这样。你甚至可能注意到签名算法被描述为使用私有密钥的加 密,但是,这种说法常常是不正确的,并且总是误导。我们将使用在102.1节中所用的表示 eK(X),表示用密钥K加密明文X; dK(X),表示用密钥K解密密文X 加密算法以两种形式出现。在对称加密算法中,加密和解密使用相同的密钥,这个密钥 必须保密。所有的参与者共享同一密钥,他们可以阅读彼此的加密数据。为了对不同参与者 建立专用信道,对每个信道你需要一个新的密钥。维护大量的共享秘密密钥可能成为一种十 分繁重的管理任务 非对称加密算法,也叫做公开密钥算法( public key algorithm),加密和解密使用不同的 密钥。加密密钥可以公开:解密密钥仍然是私有的,必须保密。很明显,这两个密钥在算法 上是相关的,但是想要从公开密钥导出私有密钥必须是不可行的。为了区分对称密码系统和 第10页共19页 创建时间:20037/914:46:00
翻译：中国科学技术大学信息安全专业老师 第 10 页 共 19 页 创建时间：2003/7/19 14:46:00 和一个私有签名密钥 e ，满足 gcd(e, p −1) =1 和 gcd(e, q −1) =1 。公开验证密钥则由积 n = p q 和指数 d 组成，并且满足 e d 1mod lcm( p −1, q −1) , lcm(p-1, q-1)是欧拉商数。 签名的文档是整数 m ，1 m n 。为了验证者能识别真正的文档，这个文档必须包含 足够的冗余信息。如果原始文档太长，可以应用散列函数和填充获得摘要进行签名。为了签 名 m ，用户 A 用下式生成签名： s m n e = mod 验证者需要 A 的验证密钥 (n, d) ，并且检查 s m n d mod ? = 是否成立。对于一个正确的签名来说，这个等式是成立的，因为 s m m n d e d = = mod 短文档可以从签名中恢复，并且不必分别传送。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 节中所用的表示 法： · eK(X ) ，表示用密钥 K 加密明文 X ； · dK(X ) ，表示用密钥 K 解密密文 X 。 加密算法以两种形式出现。在对称加密算法中，加密和解密使用相同的密钥，这个密钥 必须保密。所有的参与者共享同一密钥，他们可以阅读彼此的加密数据。为了对不同参与者 建立专用信道，对每个信道你需要一个新的密钥。维护大量的共享秘密密钥可能成为一种十 分繁重的管理任务。 非对称加密算法，也叫做公开密钥算法（public key algorithm），加密和解密使用不同的 密钥。加密密钥可以公开；解密密钥仍然是私有的，必须保密。很明显，这两个密钥在算法 上是相关的，但是想要从公开密钥导出私有密钥必须是不可行的。为了区分对称密码系统和
