翻译:中国科学技术大学信息安全专业老师 第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 值时，对任何