现代密码学理论与实践

Transcription

1 " 巴 l 认 IcnooM30 1" 王罐协.. 筒 'L.f... 豆霄 JI.. I..f.:. 审技 圃画 1" 手立吗 r :f: M ~j M, 一甲,

2 前 我们的社会已经进入了一个崭新时代, 传统的商务活动 事务处理以及政府服务已经或越来越多地将要通过开放的计算机和通信网, 如 Intemet, 特别是基于万维网的工具来实施和提供 对在世界各个角落的人来说, 在线工作有着 " 随时可得 " 的巨大优点 下面是一些可以或即将可以在线完成的事例 : 银行业务 账单支付 家中购物 股票交易 拍卖 税收 赌博 小额支付 ( 例如按下载支付 ) 电子身份 对医药记录的在线访问 虚拟保密网 安全数据存档与恢复 文件的挂号递送 敏感文件的公平交换 公平合同签署 时戳 公正 选举 广告 授权 订票 交互式游戏 数字图书馆 数字权限管理 盗版追踪等 只有在开放网络能提供安全通信的条件下, 上述诱人的商务活动 事务处理以及服务才能实现 而要保证在开放网络中通信的安全性, 一个有效的解决办法就是利用密码技术 加密 数字签名 基于口令的用户认证是实现安全通信的一些最基本的密码技术 但是, 正如我们将在本书中多次看到的那样, 即使是最基本的密码技术, 在应用中也存在令人惊讶的难以捉摸和严重的安全性问题 而且对很多像上一段所列出的 " 想像的 " 应用来说, 这些基本的密码技术是不够的 越来越复杂的电子商务 事务处理和服务形式 1, 对在开放的网络中实现安全通信的需求 正迅速增加 对能够进行设计 开发 分析和维护信息安全系统和密码协议的信息安全方面的 专业人员的需求量正日益增大 这些专业人员可能是从 E 系统的管理员 信息安全工程师和 有安全要求的软 / 硬件系统产品的开发人员, 直到密码学家 在过去的几年里, 作者作为在英国布里斯托尔 Hewlett- Pachard 实验室信息安全与密码系统方面的一名技术顾问, 已经注意到了对信息安全人员需求的持续增长和现有专业人员明显短缺这一失调现象 结果, 很多在密码或信息安全方面缺少适当训练的面向应用的工程师, 由于应用的需要, 不得不 " 挽起袖子 " 成了安全系统或密码协议的设计者或者开发者 尽管这是不争的事实, 但要设计密码系统和协议, 即使对密码学专家来说, 也不是件容易的事 作者的工作性质允许他有机会审查很多信息安全系统和密码协议, 其中有一些就是由 " 挽 袖子 " 工程师所提出和设计的, 而且是用在一些重要的实用上 在很多场合, 作者看到了这些系统中存在有所谓的 " 教科书式密码 " 的特征, 这是把很多密码学教科书中一般都介绍的密码算法直接拿来应用的结果 利用基本的公钥加密算法 ( 如 RSA) 直接对口令 ( 一个不大的秘密数 ) 进行加密就是 " 教科书式密码 " 的一个典型例子 教科书式密码以 " 不可忽略的概率 " 在重要应用场合下的出现引起了作者的担心 看来, 教科书式密码的一般危害, 尚没有被那些针对重要现实应用来设计和开发信息安全系统的许多人所意识到 1 臼血 ler Group 预计, 欧盟的 B2B 和 B2C 电子商务税收在 2 4 年将以 0.7 的概率达到 2.6 万亿美元, 是 2000 年的 28 倍 [5]0 em 础 eter[ 105] 也报告, 美国金融机构在 2 朋年因电子身份问题被窃的损失为 1 物亿美元, 并预计每年将会以 29% 的速度增加. 7. 一

3 考虑到对信息安全专业人才的大量需求, 并相信专业人才的密码学知识不能仅固于教科书式密码学, 作者写了这本 " 非教科书式密码学 " 教材 本书致力于 : 在强调 " 非教科书式 " 的情况下, 广泛介绍有关密码算法 方案和协议 通过展示对这类系统的大量攻击和总结典型的攻击技术, 来说明 " 教科书式密码 " 的不安全性 通过对标准的关注, 为密码系统和协议的设计 分析与实施提供原理和指导原则 研究严格建立密码系统和协议的强而实用安全性表示的形式化技术和方法 为希望系统了解这一领域的读者精心选取学习现代密码学必备的理论素材 本书范围 在过去的 30 年里, 现代密码学的研究可谓突飞猛进, 其研究领域非常广泛和深入 本书集中讨论一个方面的问题 : 对以其强安全性能明确建立起来的实用密码方案和协议进行介绍 本书分为 6 部分 : 第一部分这一部分共有两章内容 ( 第 1 章, 第 2 章 ), 是本书和密码学与信息安全的人门性介 绍 其中第 1 章以解决一个微妙的通信问题为开场白, 来阐述密码学的效用 本章将给 出一个在电话上实现公平掷币的简单密码协议 ( 本书的第一个协议 ) 并对其进行讨论 然后对要研究领域的文化和 " 贸易 " 进行介绍 第 2 章使用一系列的简单认证协议, 来表明该领域的一个不幸的事实 : 缺陷处处存在 作为人门性介绍, 这一部分是为想进入该领域的新手写的 第二部分这一部分介绍学习本书必备的数学背景知识, 它包含 4 章内容 ( 第 3 章 ~ 第 6 章 ) 只想 " 知其然 ", 即了解如何使用实用密码方案和协议的读者, 可以跳过这一部分而基本上不影响大多数后续章节的阅读 要想知道 " 所以然 ", 即为什么这些方案和协议具有强安全性的读者将会发现, 这里给出的数学背景知识是足够的 当我们揭示方案和协议的工作原理, 指出其中的一些方案和协议是不安全的, 或者论述别的协议和方案是安全的时候, 我们就能在这里找到相应的理论根据 这一部分也可作为学习现代密码学理论基础的系统背景知识 第三部分 这部分也有 4 章内容 ( 第 7 章 ~ 第 10 章 ), 介绍提供保密和数据完整性保护最基本 的密码算法和技术 其中第 7 章是对称加密方案, 第 8 章是非对称加密技术, 第 9 章讨论的是, 在数据是随机的理想条件下, 利用基本通用的非对称密码函数所拥有的一个重要的安全特性 最后的第 10 章是数据完整性技术 由于这里介绍的是最基本的方案和技术, 其中多数属于 " 教科书式密码 ", 因而是不安全 的 在介绍这些方案的同时, 也给出不少相应的攻击, 并明确阐述了告诫注释 对于那些不想对实用密码和它们的强安全性概念做深入研究的实际工作人员, 教科书式密码部分也仍会就教科书式密码的不安全性向他们提出明确的预警信号 第四部分这部分有 3 章内容 ( 第 11 章 ~ 第 13 章 ), 介绍应用密码学和信息安全中一个重要 的概念一一认证 这些章节的研究范围很广, 第 11 章介绍技术背景 原理 一系列的基础 协议和标准, 以及常规的攻击技术和防护措施 第 12 章是对四个著名的认证协议系统在 现实应用案例的研究 第 13 章介绍特别适合于开放系统的有关最新技术 8 刊叫如哪一一

4 企业中信息安全系统的管理者 安全产品的软 / 硬件开发商们将会发现这一部分对他们是非常有用的 第五部分这部分有 4 章内容 ( 第 14 章 ~ 第 17 章 ), 对公钥密码技术 ( 加密 签名和签密 ) 的强 ( 实用 ) 安全性概念进行严格的形式化处理, 并给出认证协议的形式化分析方法 第 14 章介绍强安全性概念的形式化定义, 接着的两章是和第三部分教科书式密码方案相对的实用密码方案, 具有形式化建立起 ( 即明确推理 ) 的强安全性 最后, 第 17 章对在第四部分尚未进行分析的认证协议, 给出其形式化的分析方法和技术 第六部分这是本书的最后一部分, 包括两个技术章节 ( 第 18 章 ~ 第 19 章 ) 和一个简短的评 述 ( 第 20 章 ) 其主要的技术章节, 第 18 章, 介绍了 类被称为零知识协议的密码协议 这类协议能提供一种重要的安全性业务, 它为 " 想像中 " 的各种电子商务和事务处理应用 所必需, 在对所声明的内容保持严格保密性的情况下, 对一个秘密数所宣称的性质进行证 实 ( 例如, 符合商业上的需求 ) 这部分要引人零知识协议, 说明了在各种现实应用中对特 定安全性需求的多样性 这种多样性超越了机密性 完整性 认证和不可否认性 在本书的最后一个技术章节 ( 第 19 章 ) 中, 我们将解决本书一开始介绍的协议中的遗留问题实现 " 通过电话公平掷币 " 最后的实现协议不但在效率上适宜实用, 而且也明确地建立起了强安全性 不用说, 对每一个实用密码协议或方案的描述, 都是要先给出与之相应的教科书式密码不适用的原因 我们总是以给出相应存在的攻击来说明原因, 就相应的攻击而言, 这些方案和协议往往存在某些微妙之处 另外, 个实用密码协议和方案的描述, 也必是以其所宣称的必须包含的强 ( 实用 ) 安全性成立的分析来结束 因而, 本书一些部分不可避免地要包含有数学和逻辑推理 为明示和对付攻击所需的归纳和变换 实用密码学并不是一个轻易驾驭或者稍稍读读就能掌握的论题 尽管如此, 本书并不是一本仅为专业密码学家所感兴趣的高深研究课题的书 这里所介绍的东西对密码学家来说都是已知的和相当基本的 作者相信, 在有充足的解释 实例 足够的数学背景知识和参考材料的情况下, 这些东西完全能被非专业人士理解 本书针对的读者对象为 : 已经或即将完成计算机 信息科学 应用数学第一学位课程并计划从事信息安全行业的学生 对他们来说, 本书可以作为应用密码学的高级教程 在高科技公司从事信息安全系统设计和开发的安全工程师 如果我们说在科学研究计划中, 教科书式密码所产生的危害不是很大的话, 至多是出现一种令人尴尬的场面, 那么在信息安全产品中使用教科书式密码将会造成严重损失 因此对这类读者来说, 了解教科书式密码在现实中的不适用性是非常必要的 而且, 这类读者应该对隐藏在实 用方案和协议下的安全原理有很好的理解, 以便能正确地使用这些方案和原理 第 11 部分所给出的自足的数学基础材料使得本书很适合这类读者自学 对企业信息安全系统管理人员或者生产安全产品的软 / 硬件开发商这类读者来说, 第 I 部分是简单而基本的文化和 " 商务 " 方面的培训教程, 第 III 部分和第 W 部分是一个适当裁减的密码学和信息安全知识集 这三部分包含有很多基本的密码方案和协议, 以. 9. d 一

5 致谢 及很多对应的攻击方法和防护措施 这些攻击方法和防护措施能被大多数读者理解, 不需要有所谓理论基础的负担 c 对于刚开始从事密码学或计算机安全方面研究的博士生这类读者来说, 将会欣赏一本能包含强安全性概念的形式化处理并对其进行适当和详细解释的书感兴趣 本书将能帮助他们快速深入地进人这一浩瀚的研究领域 对这类人员来说, 第 11 凹 V 和 VI 部分构成了一个适当深度的文献综述材料, 这将能引导他们找到更进一步的文献, 并能帮助他们明确自己的研究课题 本书的适当取舍 ( 如第 1 章 第 2 章 第 3 章和第 6 章 ) 也可以组成适合计算机 信息科学和应用数学大学高年级学生学习用的应用密码学教程 非常感谢 Feng Bao Colin Boyd Steven Galbraith Dieterωh 四 m Kei 由 Harrison, Marcus Leech Helger Lipm 脑 Hoi-Kwong 1.0 Javier 1.opez John Malone-lee C 缸 y Meltzer Christian Paquin Kenny Paterson, David Pointcheval Vincent Rijmen Nigel Smart David Soldera Paul van Oorschot Serge Vaudenay 和 Stefek Zaba 他们花费了大量时间校阅有关章节或全书, 并提供了非常有价值的评论 批评和建议, 使得本书更加完善 本书还得益于向下列人士的请教 : Mihir Bellare,Jan Camenisch Neil 队 mbar, Yair Frankel Shai Halevi Antoine Joux Marc Joye Chalie Kaufman A 也 t 阻 Kent Hu 伊 Krawczyk Catherine Meadows Bill Munro Phong Nguyen, Radia Perlman Marco Ricca Ronald Riv 臼 t Steve Schneider Victor Shoup 19or Shparlinski 和 Moti Yung 作者还要感谢 Prientic e- Hall 凹 R 的 Jill Harry 和 HP Professional Books 的 Susan Wright, 他们鼓励并引导我写作了本书, 并在我漫长的写作中提供了技术帮助, 感谢阳 entice-hall 凹 R 的 Jennifer Blackwell Robin Canoll Brenda Mulli 伊 n, Justin Somma 和 Mary Sudul 以及 HP Professional Books 的 Walter Bruce 和 Pat Pekaryo 还要感谢我在布里斯托尔 Hewlett-pack 缸 d 实验室的同事们在技术 修辞和管理方面给予 的支持, 他们是 David Ball Rachard Cardwell, Liqun Chen, Lan Cole Gare 出 Jones Stephen p, 四 rson 和 Martin Sadler 作者于英国布里斯托尔 2 3 年 5 月 10 e 今位明咿,

6 目 录 第一部分 百 l 百主 E E 司 第 1 章 一个简单的通信游戏 2 一个通信游戏 我们给出密码学的第一个应用示例 对密码学基础的初步提示 信息安全基础 : 计算困难性的背后 密码学的新作用 : 保证游戏的公平性.... 描述密码系统和协议的准则 保护的程度与应用需求相符合 对安全性的信心要依据所建立的 " 种系 " 实际效率 采用实际的和可用的原型和服务 明确性 开放性 ' 本章小结 习题 ,' 第 2 章防守与攻击....' 引言 本章概述 14 加密 易受攻击的环境 (Dolev-Yao 威胁模型 ).. 16 认证服务器 认证密钥建立的安全特性 利用加密的认证密钥建立协议 消息保密协议 攻击 修复 攻击 修复 消息认证协议 询问. 应答协议 " 实体认证协议 一个使用公钥密码体制的协议 本章小结 " 习题 '" 第二部分数学基础 标准符号 M 第 3 章概率论和信息论 引言 36 11

7 UNU日日臼UHUHη啊川哺 本章纲要 概率论的基本概念 性质 基本运算 加法规则 乘法规则 全概率定律 随机变量及其概率分布 均匀分布 二项式分布 大数定律.. 生日悖论 生日悖论的应用 : 指数计算的 Pollard 袋鼠算法 信息论 惰的性质 自然语言的冗余度.. 本章小结 刀觅觅到好喃喃剁斜仍俑锦州咽血mNUA习题 第 4 章 计算复杂性.. 引言 本章概述 图灵机.... 确定性多项式时间 多项式时间计算性问题 算法与计算复杂度表示 概率多项式时间 差错概率的特征 " 总是快速且正确的 " 子类 " 总是快速且很可能正确的 " 子类.. 臼俑倒回那UN引 " 很可能快且总是正确的 " 于类 " 很可能快且很可能正确的 " 子类 有效算法 非确定多项式时间 非确定多项式时间完全.. 非多项式界 多项式时间不可区分性 计算复杂性理论与现代密码学 必要条件 非充分条件 本章小结 mm胆创阴归自"四盯习题 , 一一 一 一一一

8 第 5 章 代数学基础... m臼引言 章节纲要 群.... 拉格朗日定理 群元素的阶 M5.2.3 循环群.. N5.2.4 乘法群 Z: Mm5.2.1 环和域 叨 有限域的结构 栩栩栩引归5.5 第 6 章 含有素数个元素的有限域 ~ 模不可约多项式的有限域 I 用多项式基构造有限域 () 本原根 用椭圆曲线上的点构造群 佣 l-- mw2u 群运算 点乘 椭圆曲线离散对数问题 5.6 本章小结 H H - H H - H H -unu--113 习题 飞κur04U6.6 WA且T d数论 115 引言 本章概述 115 同余和剩余类 Z. 中运算的同余性质 求解 Z. 中的线性同余式 中国剩余定理 欧拉 函数 费马定理 欧拉定理 拉格朗日定理 二次剩余 二次剩余的判定 勒让德. 雅可比符号 模一个整数的平方根 '.' 求模为素数时的平方根 求模为合数时的平方根 Blum 整数 本章小结 习题 第三部分 基本的密码学技术 第 7 章 加密对称技术 138 引言 ' 叫十一 一 - 一 -

9 本章概述 138 定义 ,.., 代换密码 S 换位密码.. 简单的代换密码 140 多表密码 弗纳姆密码和一次一密 古典密码 : 使用和安全性 古典密码的使用 古典密码的安全性 数据加密标准 (DES) 介绍 DES D 囚的核心作用 : 消息的随机非线性分布 DES 的安全性 高级加密标准 ( 皿 S) Rijndael 密码概述 阳 ijndael Rijndael 密码的内部函数 内部函数的功能小结 快速而安全的实现 , , 运行的保密模式 电码本模式 (ECB) 密码分组链接模式 (CBC) 157 密码反馈模式 ( 口 ~) 输出反馈模式 (OFB 卜.. 1ω 计数器模式 ( 口而 对称密码体制的密钥信道建立 , 本章小结 习题 " QM响mk旧物闹闹闹mAES 对应用密码学的积极影响 mmmmm1ω 第 8 章 加密非对称技术 引言 本章概述 166 " 教科书式加密算法 " 的不安全性 " ()t) Diffie- Hellman 密钥交换协议 "..,....'" , 中间人攻击 ,. 168 U 血 e- Hellman 问题和离散对数问题 " 任意参数对于满足困难假设的重要性 , "..."....., RSA 密码体制 ( 教科书式 ) 公钥密码体制的分析 RSA 问题 整数分解问题 教科书式 RSA 加密的不安全性 一 一

10 MMM咽M牛第牛 习题 第 10 章 ω5ω 中间相遇攻击和教科书式 RSA 上的主动攻击... ~ fuìbin 加密体制 ( 教科书式 ) 教科书式 Rabin 加密的不安全性 囚 Garnal 密码体制 ( 教科书式卜 教科书式囚 Garnal 加密的不安全性 教科书式 ElG 阳 ml 加密的中间相遇攻击和主动攻击 公钥密码系统需要更强的安全定义 非对称密码与对称密码的组合 部公钥密码系统密钥信道的建立 本章小结 理想情况下基本公钥密码函数的比特安全性 192 前言 l 归 本章概述 192 但RSA 比特.. %Rabin 比特 M Blum- Blum-Sh 由伪随机比特生成器 mm到elgan 叫比特叨离散对数比特 H 叨本章小结.. 阴 数据完整性技术.. 引言 , 本章概述.. 定义 对称技术 RSA 签字安全性的非形式化论证 习6题 密码杂凑函数.... E 基于密钥杂凑函数的 MAC 基于分组加密算法的 MAC 非对称技术 L 数字签名 俑 数字签名的教科书式安全概念 , 佣 RSA 签字体制 ( 教科书式版本卜.. 2ω Rabin 签名体制 ( 教科书式版本 ) "...., , 关于 Rabin 签名的一个自相矛盾的安全性基础 " '.' o. "" 210 日 Gamal 签名体制 , '" 日 Gan 时签名体制安全性的非形式化论证...., " 日 Garnal 签名族中的签名体制 , 数字签名体制安全性的形式化证明 非对称技术 II: 无源识别的数据完整性 本章小结 mmmmm 2ω 221 叫 F

11 第四部分 认证 第 11 章 认证协议一一原理篇 ~ mmmmm 引言 章节概述 认证和细化的概念 数据源认证 实体认证 认证的密钥建立 "2: 对认证协议的攻击 扫 约定 基本认证技术 消息新鲜性和主体活现性 双方认证 包含可信第三方的认证 基于口令的认证 , , N 回品 m 口令认证协议及其在 UNIX 操作系统中的实现 , 一次性口令机制 ( 及缺陷的修补 ) , , , 加盐操作 : 加密的密钥交换 (E 阻 ) 242 基于非对称密码学的认证密钥交换 剧 工作站. 工作站协议 简化而协议的一个缺陷 页 S 协议的一个琅疵 对认证协议的典型攻击 消息重放攻击 , 中间人攻击 ,... '" 平行会话攻击 反射攻击 交错攻击 归因于类型缺陆攻击 , 归因于姓名遗漏攻击 密码服务滥用攻击 mmmmm 11.9 习题 第 12 章 12.2 文献简记 '" 本章小结 时言1i-U 酣J于2-嗖 概古队通旧俗议 章网践 篇 - 节时层口用口HtMHE也引mmmmm E 安全协议 (IPSec) 拙 因特网密钥交换 (IKE) 协议....., , '267 IKE 中看似合理的可否认性 'T72

12 引M 习题 第 13 章 对 lpsec 和 IKE 的批评意见 安全壳 (SSH) 远程登录协议 SSH 架构 白 H 传输层协议 白 H 策略 警告 Kemeros 协议及其在 Windows 2 删系统中的实现 单点登录结构 Kerberos 交换 警告 , SS 昨日 ~ " , 咀 S 架构概述 咀 S 握手协议 " 咀 B 握手协议的典型运行..." " 对 ηs 协议的边信道攻击.. 本章小结 公钥密码的认证框架 本章概述 基于目录的认证框架 证书发行 证书吊销 公钥认证框架实例 与 X.509 公钥证书基础设施相关的协议 基于非目录的公钥认证框架 ,..o... " '".,., Shamir 的基于 E 的签名方案..." " 基于 E 的密码确切提供了什么 , 自证实公钥,......'" ,.,.... 2% 利用 " 弱 " 椭圆曲线对构造基于身份的公钥密码体制 句 kai Ohgi 耐和 Kasahara 的基于 E 的非交互密钥分享系统 三方 Diflìe- 剧 lman 密钥协商 Boneh 和 Franklin 的基于 B 的密码体制 ,.., 3()4. 句,&白句,随&吨,,缸 'O 姐姐前言 姐咽Am同MJ内ynyny 非交互特性 : 元密钥信道的认证 3(f 基于身份的公钥密码学的两个公开问题 到 7 本章小结...., 侃 习题 308 第五部分 第 14 章 14.1 安全性的形式化方法 义定性金安强化式形的制体码密1 M 言 W本章概述 一 ~,,,, 一

13 习题 第 15 章 习题 第 16 章 安全性的形式化处理 语义安全性一一可证明安全性的首次亮相 SRA 智力扑克协议 基于教科书式安全的安全性分析 Goldw 脑础和 Micali 的概率加密 GM 密码体制的安全性 , 囚 Gamal 体制的一种语义安全版本 基于 Rahin 比特的语义安全密码体制 语义安全性的不充分性 超越语义安全性 抗击选择密文攻击的安全性 抗击适应性选择密文攻击的安全性 不可展密码学 不可区分性与不可展性的关系 本章小结 可证明安全的有效公钥密码体制 引言 本章概述 最优非对称加密填充 安全性证明的随机预言饥模型 RSA-OAEP RSA-OAEP 证明中的曲折 对 RSA-OAEP 的补救工作 RSA-OAEP" 归约为矛盾 " 的严谨性 对随机预言机模型的批评 作者对随机预言机模型价值的观点 Cramer-Shoup 公钥密码体制 , 在标准困难性假设下的可证明安全性 Cramer-Shoup 体制 安全性证明.. 可证明安全的混合密码体制综述 可证明安全的实用公钥密码体制的文献注记 本章小结 强可证明安全的数字签名方案 引言 本章纲要 数字签名的强安全性定义 ElGarr 叫族签名的强可证明安全 三元组囚 Gamal 族签名 分叉归约技术

14 重行归约方法 适于应用的 RSA 和 Rabin 签名方法 具有随机化填充的签名 概率签名方案 自 S- R: 消息可恢复的签名 签名和加密通用的自 S- R 填充 签密 Zheng 的签密方案 箭双雕 : 采用 RSA 签密 习题 第 17 章 本章小结 分析认证协议的形式化方法 引言 本章概述 佣 17.2 认证协议的形式化描述. 3 佣 加解密认证方法的不精确性 佣 认证协议的细化描述 认证协议细化描述的例子 正确协议的计算观点一 -Bellare-R 嗨 away 模型 叨 参与者行为的形式模型化 相互认证的目标 : 匹配对话 M4P l 协议及其安全性证明 401 协议正确性计算模型的进一步研究 呗 讨论 正确协议的符号操作观点 定理证明 一种认证逻辑 形式化分析技术 : 状态系统探查 俑 模型检验 406 NRL 协议分析机 咽 CSP 方法 ω 17.6 调和安全性形式化技术的两种观点 本章小结 习题 第六部分密码学协议 第 18 章 零知识协议 418 引言 本章纲要 基本定义 计算模型 交互式证明协议的形式化定义 一 - 一 -

15 习题 第 19 章 第 20 章 一个复杂性理论结果 422 零知识特性 完备零知识 ~ 诚实验证者的零知识 4η 计算零知识 统计零知识 证明还是论据 零知识论据 零知识证明 , 433 双边差错协议 零知识证明双素整数 轮效率 子群成员归属的轮效率下界 , 离散对数的常数轮证明 非交互式零知识 斜 利用指定验证者获得 NIZK 本章小结 回到 " 电话拇币 " 协议 Blum" 电话掷币 " 协议 安全性分析 效率 本章小结 结束语 到 4 到 参考文献

16 矗=立目同本书第一部分由两个引论性的篇章组成 主要为我们介绍密码学和信息安全中的一些基 本概念 : 我们进行通信与处理敏感信息的环境 ; 在该环境下参与演出的几位著名 " 人物 " 以及其中一些扮演坏家伙的标准伎俩 ; 密码学和信息安全系统研究与发展领域的社团文化, 以及这些系统极为容易出错的现实 作为初级引论, 这一部分所针时的读者是希望进入这一领域的初学者 一叩

17 第 1 章一个简单的通信游戏 作为本书的开场白, 我们用应用密码学中的一个简单例子来解决一个简单问题 这个例子对我们要在本书中介绍的内容有三个方面的作用 : 初步揭示了应用密码技术解决应用中的敏感问题的效力和实用性 对密码学的基础知识进行了初步提示 初步建立了从事信息 安全的密码系统的开发所要求的思考形式 首先, 我们将给出一个平凡且简单的问题, 然后给出同样简单的相应解决办法 该解决办法是我们大家都熟悉的二人博弈 可是我们将会发现, 当两个参与者披此相距遥远时, 这个简单游或将马上变得麻烦起来 游戏双方彼此的物理分离就会丧失公平游戏的基础, 从而会引出麻烦, 玩游戏的各方不可能相信另 方在公平地进行游戏 远距离参与者公平进行游戏的需求将 " 激励 " 我们, 利用盔甲的屏障进行防护来强化我们的简单游戏 这种强化游戏的方法来自长期树立起来的 在公开网络中保护通信的思想, 即利用密码技术隐藏信息 在应用密码技术很好地解决了我们的第一个安全问题之后, 我们将对密码系统的质量准则进行 系列的讨论 ( 见 1. 2 节 ), 这些讨论是我们为保护敏感信息所进行的研究和开发的技术领域的背景知识和文化的介绍 1. 1 一个通信游戏 这是个简单问题 3 两个朋友, Alice 和 Bob1 想在晚上一起外出, 但是他们定不下来是去电影院还是歌剧院 尽管如此, 他们达成了 个通过掷硬币来决定的协议, 这和我们都很熟悉的掷硬币游戏一样 Alice 拿着一个硬币并对 Bob 说 :" 你选择一面, 然后我来抛 "0 Bob 选择后, Alice 把硬币抛向空中 然后他们都注视硬币, 看结果是哪一面朝上 如果 Bob 选择的那面朝上, 则他就可决定要去的地方, 否则由 Alice 决定 在通信规程的研究中, 对上述的一个多方游戏可以给予 个更 " 科学的 " 名字 : 协议 一个协议是一个适当定义的 在多个参与实体之间执行的规程 这里要注意多个实体参与的重要性 : 如果一个规程仅由一个实体执行, 那么它只是一种程序, 不能称之为协议 我们给出密码学的第一个应用示例 现在假想这两个朋友尝试在电话上执行上述协议, Alice 向 Bob 说 :" 你选一面, 然后我抛硬币并告诉你是否赢了 " 显然 Bob 不会同意, 因为他不能验证抛掷硬币的结果 1 在密码学 密码协议和信息安全领域. Ali ce 和 Bob 都是著名的角色, 他们将在本书的大多数协议中出现 一舶 " 一一 一

18 第 1 章一个简单的通信游戏 3 然而, 我们可以在这个协议中加入一点密码技术, 把它变成一个适合在电话上工作的形 式 其结果就成为一个密码协议, 即本书的第一个密码协议! 现在先让我们把所用到的 " 密码 术 " 看做是一个数学函数 j( 川, 它是整数上的映射并具有下列奇妙性质 : 性质 1. 1 奇妙函数 f I) 对任意整数 x, 由 Z 计算 j(x) 是容易的, 而给出 j( 川, 要找出对应的原像 Z 是不可能 的, 不管 z 是奇数还是偶数 11) 不可能找出一对整数 ( 耳, y), 满足 x~y 且 j(x) = j(y) 在性质 1. 1 中, 形容词 " 容易 " 和 " 不可能 " 的意思需要做进一步的阐述 同样, 由于这些词 与困难的程度有密切关系, 我们必须搞清楚它们的量化表示 可是, 因为现在我们把 j(x) 看成是一个特殊类型的函数, 采用常规语言使用这些词依然是安全的 在第 4 章我们将为本书中使用的各种 " 容易 " 和 " 不可能 " 提供数学公式描述 本书的重要任务之一就是为各种 " 容易 " " 困难 " 和 " 不可能 " 建立量化表示 事实上, 我们最终将在本书最后的技术性篇章 ( 第 19 章 ) 看到, 在 我们最终所实现的掷币协议中, 性质 1. 1 中奇妙函数 j" 不可能 " 的两种用法将有大不相同的定 量量度 假定两个朋友已经就奇妙函数 j(x) 达成了一致, 并一致同意用偶数来表示 " 正面 ", 用奇 数来表示 " 背面 " 现在他们做好了在电话上执行我们第 个密码协议 ( 协议 1.1) 的准备 协议 1.1 电话掷币假定 Alice 和 Bob 已经同意 : i) 具有性质 1. 1 的一个特殊函数 f ii) j(x) 中的偶数 Z 代表 " 正面 ", 奇数 z 代表 " 背面 " ( * 注意 : 由于 (ii), 该协议有一个弱点, 详见习题 1. 2 * ) 1. Alice 选择一个大随机数 Z 并计算 j(x) ; 然后通过电话告诉 Bobj( 川的值 ; 2. Bob 告诉 Alice 自己对 z 的奇偶性猜测 ; 3. Al ice 告诉 Bobx 的值 ; 4. Bob 验证 j(x) 并察看他所傲的猜测是正确或错误 要说明上述 " 电话掷币协议 " 能在电话上很好地工作并不困难, 下面是对其初步的 " 安全性 分析 "( 注意, 这里为安全性分析加上引号是因为我们在这里所给出的分析是远远不够的 ) 初步的 " 安全性分析 " 首先, 根据 f 具有的 " 性质 II", Alice 无法找到不同的两个数 z 和 y, 其中一个是奇数而另 一个是偶数 ( 可表示为 x~y mod 2), 使其满足 j(x) = j( y) 因此, Alice 一旦通过电话告诉 Bobj( 川的值 ( 第 1 步 ), 她也就向 Bob 就 z 的值做出了承诺, 她无法再改变 z 的值 也就是说 Alice 已经完成了其掷硬币过程 第二, 由于 f 具有 " 性质 I", 已知 j(x),bob 不能判定出 Alice 所使用的 z 是奇数还是偶数, 因而他不得不把其猜测 ( 第 2 步 ) 真实地给出 ( 即, 并非通过各种推导得到的 ) 这样, Alice 可

19 4 现代密码学理论与实践 给出 z 的值令 Bob 相信其猜测是否正确 ( 第 3 步 ) 事实上, 如果 Bob 利用 Al ice 告诉的 Z 对 f(x) 进行计算的结果 ( 第 4 步 ) 与 Al ice 在第 1 步给出的结果一样, 且 Bob 相信 f 所具有的性质, 则 Bob 应该相信最终的输赢 而且, 在 z 选自一个充分大的空间且 Bob 的猜测元优 ( 即获胜的概率不大于 1/2) 的情况下, 掷硬币是公平的 应该指出, 在对协议 1. 1 的 " 安全性分析 " 中, 我们已做了若干简化和省略 这样, 当前的协议版本还远不能用于具体的实际 本章将讨论其中的一些简化和省略 不过, 正确而具体地实现该协议所必要的技术, 以及分析其安全性所必要的方法, 将是本书后续章节要讨论的主题 我们将把对协议 1. 1 正确而具体的实现 ( 更确切地说是 " 奇妙函数 "f) 推迟到本书最后一章 ( 第 19 章 ) 在那里, 我们已做好了技术准备, 将能对其具体实现提供一个形式化的安全性分析 对密码学基础的初步提示 虽然上述第一个协议很简单, 但它的确是一个合格的密码协议, 因为协议中使用的 " 奇妙函数 " 是构成现代密码学的一个基本要素一一单向函数 性质 1. 1 所列出的两个奇妙特性提出了两个计算固难性问题, 其中一个对应 Alice, 另一个对应 Bob 根据对协议 '1.1 的初步安全性分析, 我们可以断言, 单向函数的存在性意味着在娱乐场地进行安全选取的可能性 下面是这一论断的合理推广 : 单向函数的存在性意味着安全密码系统的存在性 现在也已众所周知, 上述断言的逆命题也是成立的 : 安全的密码系统的存在性意味着羊向函数的存在性 目前普遍认为确实存在有单向函数 因而在保护信息方面我们是乐观的 我们的乐观态 度常常能被我们的日常经验所证实 : 现实中的很多过程, 不管是数学的或是其他方面的, 都具有单向性 考虑下面的物理现象 ( 虽然不是一个非常精确的数学类比 ) : 茶杯掉在地上摔成碎片并耗散一定的能量进入周围环境中 ( 例如, 热 声音或甚至一点暗淡的光 ) 是一个容易的过程 而相反的过程, 即重新将耗散的能量收集起来, 并用来把碎片整合成一个完整的杯子, 即便不是不可能的, 也必然是很困难的 ( 如果可能, 则整个收集起来的能量就能够把重新整合的杯子弹回到其开始降落时的高度 )! 在第 4 章, 我们将看到一类数学函数, 这类函数为现代密码学提供所需的单向性质 信息安全基础 : 计算因难性的背后 我们已经断言, 信息安全性需要某些数学特性 而且, 我们还做了一个乐观的论断 : 数学特性意味着 ( 即保证了 ) 信息安全性 但在现实中, 后面的断言并不元条件成立! 现实应用的安全性依赖于很多问题 让我们继续以第一个协议例子来给予说明 应该指出, 在对协议 1. 1 的初步安全性分析中, 有很多重要问题我们没有考虑 事实上, 协议 1. 1 本身是一个非常简化的版本, 它省略了一些细节, 这些细节对于设计的协议所要提供的安全性服务是非常重要的 这些省略阻碍了我们询问一些问题 例如, 我们可以怀疑 :Alice 真的 " 被迫 " 不改变她所使用的川同样,Bob 真的 " 被迫 " 不改变他对 z 的奇偶性猜测? 这里 " 被迫 " 的意思是指, 不管电话上的声音是否足以保证上述强数 ~

20 第 1 章一个简单的通信游戏 5 学性质起作用 我们还可以间,Alice 是否有一个好的随机数发生器使她能获得随机数 z 这个问题在很多需要做出公平判定的更为关键的应用中是至关重要的 所有这些细节都在该简化协议的说明中省略了, 因而它们都变成了隐含的假定 ( 后面有更详细的叙述 ) 事实上, 如果用这个协议做更严格的判定, 协议还应该包含一些明确的用法说明 例如, 当读出 j(x) 的值和 z 的奇偶性猜测时, 两个参与者都要考虑记录对方的电话录音, 以便在发生争议时使用 一些密码系统和协议, 特别是密码教科书所介绍的, 与 " 电话掷币 " 协议类似, 常以简化的形式给出 采用简化的形式有助于更清楚地陈述, 特别当一些约定被认为是显然的时候 但是有时候, 隐含的约定或假设可能是非常微妙的, 并可能会带来意想不到的后果 这对于本想通过省略一些细节达到更 " 清楚陈述 " 的做法多少有些讽刺意味 安全系统中一个假定的不成立, 可能会招致某种形式的攻击, 并因而导致所提供的服务成为泡影 要意识到一个隐含的假定不成立是相当困难的 在 节中, 我们将对有关密码系统的明确设计和规范的重要性进行讨论 本书的一个主要论题就是要说明在现实应用的安全性中, 有很多与应用相关的微妙之处需要认真对待 密码学的新作用 : 保证游戏的公平性 密码学一度曾为政府所独占 军事和外交部门使用它来保密消息 可是今天, 密码学除了用于对信息进行保密外, 还有一个新的用途 : 在有大量 " 玩家 " 的 " 游戏 " 中保证公平 ' 性 这也是我们选用一个通信游戏作为论述密码学的本书开场的部分原因 在一个娱乐场所进行判决可能不是 件大不了的事情, 因而通过电话掷硬币来做决定只可能被看成是一种取乐的通信游戏 可是, 有很多通信 " 游戏 " 必须更加认真地对待 随着越来越多的事务处理和电子商务活动在开放的网络中以电子方式开展, 我们通信中的许多实例将会捞及各种各样的 " 游戏 "( 在本书的前言中, 我们已经列出了在开放网络上开展的很多事务处理和服务的例子, 所有这些例子都包含参与者按一套规则的交互式活动, 都可以看成是 " 玩通信游戏 ") 这些" 游戏 " 可能是非常重要的! 一般来说, 这种 " 游戏 " 的 " 玩家 " 往往彼此物理上相距很远, 要依靠不安全的开放网络进行通信 物理距离和缺少安全性组合到一块儿, 有助于和 / 或激励一些 " 玩家 "( 甚至一些未受邀请的玩家 ) 以某种聪明的方式挫败游戏规则 违背规则的企图是为了获得某种未授权的优势, 例如造成秘密信息的泄露 改变数据而不被发现 伪造证据 责任否认 破坏审计和信任 降低可用性或完全不提供服务等 现代通信在事务处理 商业运作 提供服务 ( 以及很多其他方面, 如公司业务 个人信息 军事活动和国家事务的保密 ) 方面的重要性意味着要求不遵守游戏规则的玩家不应该获得任何未授权的优势 在简单 " 电话掷币 " 密码协议的开发中, 我们已经目睹了如下过程 : 容易破坏的通信游戏演变成 个密码协议, 而且能完成所希望的安全服务 我们的例子展示了密码技术在维护 " 玩游戒 " 秩序方面的作用 的确, 在开放的计算机和通信网络中保证安全通信, 采用密码学是一种有效而且是惟一可行的办法 密码协议正是以密码技术 " 武装 " 的通信程序, 因而具有保护功能, 保持通信的正常秩序 电子商务 事务处理和服务对安全通信的元尽需求, 再和另一种对 " 不按照规则游戏 " 的不停诱惑的企盼的需求, 结合在一起就导致了很多密码系统和协议的产生, 这些系统和协议构成了本书的主要内容... 比一

21 6 现代密码学理论与实践 :!. 1.2 描述密码系统和协议的准则 我们应当从一个基本的问题开始 : 什么是好的密码系统和协议? 显然, 这个问题不好回答! 其中一个原因是由于 " 好 " 一词有很多意思, 不同的意思也就有不同的回答 本书的一个主要任务就是对这个基本问题给出更深入的答案 但本章我们只能给出一些初步的答案 保护的程度与应用需求相符合 让我们来看我们在 节中所设计的第一个密码协议 我们可以说 " 电话掷币 " 是一个很好的协议, 因为从概念看它非常简单 一些已经熟悉很多实用单向杂凑函数 (h 臼 h function, 例如 SHA-l, 见 节 ) 的读者, 也许会更进一步想到, j(x) 是很容易计算的, 即便在袖珍计算器上也不难实现 例如, SHA-l 的输出是 1ω 位的比特串, 或 20 字节 ; 采用 16 进制的编码方案 ( 见例 5.17), 这样的输出可编码成 40 个十六进制的字符 1 因此, Alice( Bob) 在电话上读 ( 草记下 ) 上述数据不至于太令人厌烦 这样一种实现方式对 Alice 和 Bob 要决定娱乐场点来说应该说是足够安全的 : 如果 Alice 想欺骗, 她就要找出 x~ y(mod 2) 使 j( x) = j( y), 而这将是一个异常困难的问题 ; 同样, Bob 也将面临一个异常困难的问题, 即已知 j(x) 判断 z 是奇数还是偶数 不过, 我们判断采用 SHA-l 来实现 " 电话掷币 " 协议的质量是根据游戏人对游戏的结果的认真程度来说的 但在很多更重要的应用场合 ( 例如, 节中要讨论的情况 ), 要将公平掷硬币的原型用于密码, 所要求的单向性和承诺性一般要比实用的单向杂凑函数如 SHA-l 所提供的要强得多 应该注意, 如果我们仅从字面上理解 " 不可能 " 这一概念, 具有性质 1. 1 的函数就是 个完全安全的单向函数 这种函数是不容易实现的 更糟糕的是, 甚至其存在性仍然是一个公开问题 ( 尽管我们对其存在性是乐观的, 在 节种可以看到我们的乐观看法, 我们将在第 4 章进一步讨论单向函数的存在条件 ) 因此, 对很多公平掷币的更重要的应用场合, 实用的杂凑函数不一定就是好的, 必须用更加严格的密码技术 另一方面, 对决定娱乐场点来说, 使用重量级密码技术显然是不必要的 应当指出, 对有些应用来说, 太强的保护甚至会妨碍想要的安全服务的正常性能 例如, Rivest 和 Shamir 提出了一个称做 MicroMint 的微支付方案 [244 ], 它利用了一个众所周知的 低效率的加密算法来实现方案的优势 该支付系统采用了如下的合理假设 : 只有资源充足的服务提供商 ( 如大银行或金融机构 ) 才能在 - 个实用的单向函数下以较低代价找出大量的 " 碰撞 " 也就是说, 服务提供商可以计算出 k 个不间的数 (X1, 屿,, Xk)' 使得 j(x1) =j(x2) ='" =j(x.) 叭, 句,, 均被称为单向函数 f 下的碰撞 很容易验证一对碰撞, 因为计算它们的单向函数是很容易的, 这些碰撞可以看成是资源充足的服务提供商发布的, 因而可表示一个被证实的 1 十六进制字符是集合 \0, 1, 2,, 9, A, ß,, Fl 中的元素, 用来表示 4 比特数的 16 种情况 川一

22 第 1 幸一个简羊的通信游戏 7 值 人们建议用数据加密标准 (DES, 见 7.6 节 ) 作为实现这种单向函数的适用算法 [ 到 4 ], 相应得到的输出空间不大 (64 位 ) 因此, 并不像平常密码学使用的单向函数那样, 其中一个碰撞几乎就构成对系统的一次成功攻击 ( 例如," 电话掷币 " 协议例 ). 在 MicroMint 中, 碰撞是用来实现一个奇妙的微支付服务! 显然, 利用大得多的输出空间的强单向函数 ( 即 :>64 位, 如有 lω 位的 SHA- l). 即便对 个资源充足的服务提供商, 也不能提供任何服务 ( 在 3.6 节, 我们将研究寻找 hash 函数碰撞的计算复杂度 ) 虽然采用重量级密码技术来设计安全系统 ( 例如多层加密 任意使用数字签名 由 个甚至多个可信赖第三方提供在线服务 ) 可以使人们觉得能实现更强安全性 ( 也可能减轻设计工作 ), 但这种感觉常常只会提供虚假的保证 人们并不希望穿上累赘的 " 盔甲 " 来表演 " 杀鸡用牛刀 ", 因为这样做可能会要求更强的安全性假设, 并导致更加复杂的系统 复杂的系统还会增加安全性分析和安全实现的困难 ( 因而更容易出错 ), 以及在运行和维护上更高的费用支出 O 设计密码或安全系统的一项更重要和更具挑战性的工作是, 仅采用必不可少的技术来实现足够的安全保护 这也是衡量一个密码和安全系统好坏的一个重要因素 对安全性的信心要依据所建立的 " 种系 "1 我们如何才能相信一个密码算法或协议是安全的呢? 能否因为还没有人攻破它就说它是安全的呢? 令人遗憾的是, 答案是否定的 般地, 对一个未被攻破的算法, 我们只能说还不知道如何攻破它 因为在密码学中, 一个被攻破的算法有时意味着能够定量地度量 ; 如果一个未被攻破的算法没有这种度量, 那我们就甚至无法断言 个未被攻破的算法是否比一个已被攻破的算法更安全 然而, 也有一些例外 在大多数情况下, 攻破一个密码算法或方案的任务归结为解决某个数学问题, 如方程求解或函数求逆 这些数学问题被认为是 " 困难的 " 或 " 不可解的 " " 困难的 " 或 " 不可解的 " 的形式化定义将在第 4 章中给出 这里, 我们可以非正式而保险地说, 如果一个数学问题尚不能用已知的方法在合理的时间段内求解, 则它是困难的 有很多著名的困难问题常被作为现代密码学的标准组成成分, 特别是在公钥或非对称密码体制中 ( 见 8.3 节 节 ) 例如, 在公钥密码学中, 困难问题包含大整数分解问题 离散对数问题 Diffie- Hellman 问题, 以及其他一些有关问题 ( 在第 8 章中我们将定义和讨论这些问题 ) 这些问题可以被看做为已建立的零散" 种系 ", 因为它们已被一代又一代的数学家长期不懈地研究, 所以有很高的可信度令人相信, 要解它们确实很困难 今天, 要建立对密码算法安全性的高可信度, 其标准技术就是给出一个形式化的证明, 能够展示对预算法一种攻击就可用来解决 " 种系 " 中的一个困难性问题 证明本身就是一个或 系列高效的数学变换, 从对算法的一种攻击变为困难问题的一种解法 这种高效变换称为归约, 即把对算法的攻击 " 归约 " 为解困难问题 由于我们深信归约成的困难问题很可能是无法解的 ( 特别是在以攻击和归约变换来度量的时间代价上 ). 我们将能推出一种可度量的信任度, 从而能断言 : 所谓的攻击是不存在的 o 这种安全性证明方法因而被称为 " 矛盾归约 ": 某个困难问题是易解的 1 此处指密码算法源于 " 名门望族 ", 如大整数分解 离散对数等公认的数学难题 二一

23 8 现代密码学理论与实践 形式化的可证明安全性, 特别是在各种强力攻击即适应性攻击 (Adaptive Attack) 模型下, 是评价一个密码算法和协议 " 好坏 " 的重要标准 我们将采用适用安全性 ( Fit 也 r-application) 来命名在各种强力攻击模型下通过形式化和矛盾归约方法所建立起来的安全性的质量 作为本书的一个重要议题, 我们将研究很多密码协议和算法的适用安全性 实际效率 我们说一个数学问题是高效的或高效可解的, 是指该问题能在问题规模的多项式时间内可解 第 4 章中将给出的效率的形式化定义, 使我们能对这类断言提供精确的度量 我们暂时不考虑断言的定量上的细节 可以粗略地说, 这类断言将所有的问题分成如下两类 : 容易处理的和困难的 这种划分在奠定现代密码学 ( 基于计算复杂性理论的密码 ) 的基础中起着十分重要的作用 显然, 一个密码算法一方面应该设计成容易处理的, 以便能被合法用户使用 ; 另一方面还应该是困难的, 以便对非用户和攻击者构成一个要解的困难问题 不过我们应该注意到, 上述可解性的断言覆盖了很宽的量度范围, 对一个合法用户来说, 如果一个问题的计算时间是一个很大的多项式, 那么其 " 效率 " 一般认为是不可行的, 即无任何实用价值 因此, 密码算法是 " 好的 " 的一个重要准则是, 对合法用户来说它应该是实用高效的 特别地, 衡量用户资源代价的多项式应该很小 ( 即为低次式, 第 4 章将介绍这一概念 ) 在第 14 章, 我们将讨论有关可证明强公钥密码体制的一些先驱性工作 这些工作所提出的一些公钥加密算法, 都是在一个共同的动机下提出的, 很多公钥加密算法的基本形式是不安全的 ( 费们把这些不安全的方案称为 " 教科书式密码 ", 因为大多数密码教科书所介绍的就是这种基本的和初始的形式, 本书第皿部分将给予介绍 ) 可是, 关于可证明强公钥密码系统的大多数初创性工作都采用逐位加密方式 [127, 212, 243], 有些甚至采用超常的步骤和公钥认证框架 [212J 来增进对每一比特加密正确性的知识证明 [243J 虽然这些早期的先驱工作对达到强安全性提供深入看法上是重要的, 但他们所建议的系统一般都效率低下而不实用 在第 14 章之后, 我们将进一步研究继先驱工作之后出现的一系列有关可证明强安全的公钥密码体制和数字签名方案的工作 这些后来的研究工作所提出的密码体制不仅具有强安全性, 而且在效率方面也是实用的 它们确实是非常好的密码体制 一个密码协议不仅是一个算法, 也是一个通信过程, 该过程包含不同协议参与者在一组约定规则下通过计算机网络进行的消息传递 因此, 在效率度量方面协议就多了一个量纲 : 通信交互的次数, 通常称为通信轮数 一般地, 通信的 步比一步本地计算 ( 典型的一组计算机指 令集的执行, 例如计算设备上两个数的乘法 ) 的代价要大 因此, 人们希望尽量减少密码协议的轮数 评价一个算法是否高效的标准有效性准则是, 其运行时间以问题规模的低次多项式 为界 如果我们把这个有效性准则用到协议上, 那么一个高效协议的轮数应以次数很低的多 项式界定 : 常数 (0 次 ) 或至多为线性函数 (1 次 ) 一个协议的通信轮数超过线性函数, 它就不会被认为是实际有效的, 即实际中毫无用途 在 节中, 我们将讨论一些通信轮数以非线性多项式度量的零知识证明协议 应该指出, 那些协议并不是为现实应用提出的, 但它们在密码和计算复杂性理论方面很重要 对于设计实用高效的零知识协议, 我们将在第 18 章看到更多的研究工作 采用实际的和可用的原型和服务 适用于某种应用的安全性级对于另一种应用未必就足够好 让我们再次以掷硬币协议为 ~ 咽,

24 第 1 章一个简羊的通信游戏 9 例 在 节中我们已经看到, 如果采用一个实用的单向杂凑函数来实施 " 电话掷币 " 协议, 那么对 Alice 和 Boh 通过电话来决定娱乐场点来说, 该协议已经够了 但是, 在公平掷硬币原型的许多密码应用中, 安全服务都在严格得多的安全级上抗击欺诈和 / 或实现公平性 ; 在 - 些应用中, 要求绝对意义上的严格性 例如, 在第 18 章我们将讨论一个零知识证明协议, 它需要随机比特串输入, 且这个随机输入必须得到证明者和验证者双方的信任, 否则会对一方或双方造成严重损害 在这种零知识证明协议中, 如果通信双方不曾接触或不信任基于第三方服务所提供的随机数 ( 这种服务常被戏称为 " 天上掉下来的随机数 " 来意指其不现实 ), 那么他们就不得不通过掷币协议, 交互式地逐比特产生大家都信赖的随机数 注意, 这里以 ( 通过掷币协议 ) 逐比特来产生随机数的方式满足某种特定要求, 如协议的正确性和零知识性 在这种情况下, 仅有实用上好这一安全级 ( 即在 " 电话掷币 " 协议中采用实用杂凑函数的意义上 ) 很可能不能满足要求 在密码学和密码协议的应用性研究中, 一项具有挑战性的工作就是从实用和可得到的密码原型建立高质量的安全服务 让我们再次引用掷币协议来阐述这一观点 这是由 Blum 提出的一个远程掷币协议 [44]0 Blum 协议利用实际安全和容易实现的 " 单向 " 函数, 按非常流行的方式实现了高水平的安全性, 可做如下解释 : 首先, 它对抗击掷硬币方 ( 如 Al ice) 欺诈的困难性实现了定量的度量, 即找出一对碰撞 (x, y), 满足 j(x) =f(y) 而 Z 于付 这里, 困难性被量化为分解一个大的合数, 即解决一个 " 种系 " 困难问题 其次, 猜测方绝对无法以超过 1/2 的概率获胜, 这可用完全安全性来称颂 因此, 从仅使用实用密码的原型就能实现强安全性的意义上来说, Blum 掷币协议是非常好的 作为我们的第一个密码协议的强化和具体实现, 我们将描述 Blum 掷币协议, 这是本书的最后一个密码协议 公钥密码学 [98, 99, 248J 出现几年之后, 大家逐渐认识到, 些基本的且最著名的公钥加密算法 ( 我们称之为 " 教科书式密码 ") 一般有两种弱点 : (i) 它们会泄露加密的消息的部分信息 ;(ii) 它们对主动攻击都相当脆弱 ( 见第 14 章 ) 这些弱点意味着" 教科书式密码 " 不适于实际应用 早期对教科书式密码弱点通常的补救方法一直是采用逐比特加密方式, 甚至应用逐比特的零知识证明技术加上认证框架来防止主动攻击 这些结果虽然对可证明安全的公钥加密算法的发展有价值, 但对大多数加密应用来说不适用, 这是因为在加密算法中要求零知识证 明或认证框架是不切实际的 自从采用随机化填充方案强化公钥加密算法获得初步成功以后 [25 ], 产生了一种利用诸如杂凑函数和伪随机数生成器等通用原型, 将普通教科书式公钥加密算法强化为可证明安全算法的一般方法 这些强化的加密方案是实用的, 因为它们使用了像杂凑函数等实用的原型, 因此其效率与相应的 " 教科书式密码 " 类似 由于这一重要的质量因素, 一些使用实用和通用的原型强化后的算法成为公钥加密和数字签名的标准 我们将在第 15 章和第 16 章研究其中的一些方案 利用已有的和通用的技术和原型来设计密码体制 协议和安全系统, 从如下的意义上说, 也是所希望的 : 由于这些结果能吸引广泛的兴趣来对其进行详细审查, 最终它们很可能是安全的 明确性 在却世纪 ω 年代末期, 软件系统变得非常庞大和复杂, 计算机程序员开始遇到危机, 即所 一句 "

25 10 现代密码学理论与实践 谓的 " 软件危机 " 大而复杂的软件系统越来越容易出错, 排除错误的代价远远起过程序设计和开发的费用 不久, 计算机科学家发现了一些制造危机的 " 罪犯 ", 即坏的编程习惯, 包括 : 乱用 ωto 语句 ( 上下跳转看起来非常方便 ) 大量使用全局变量 ( 造成无法控制它们的值的变化, 例如在非预期的子程序的执行中 ) 不声明变量类型就使用 ( 隐含类型可以在 Fo 此 m 中使用, 例如, 个实数可以截短为一个整数而没引起程序员的注意 ) 非结构化的 组织混乱的大块代码用于多个任务 ( 一块可能有上千行语句 ) 注释行太少 ( 由于它们并不被执行 1) 程序员编程时可能图 " 方便 ", 但已经证明, 这种做法将给程序的调试 维护和进一步开发带来很大的困难 用这种 " 方便 " 特征所设计的软件代码可能太含糊不清而难以理解和维护 一个程序员在几个月或几个星期前写的一小段代码, 现在却看不懂了, 这种现象经常出现 一旦理解了坏的编程习惯会带来灾难性的后果, 程序设计方法学也就成为一个研究学科, 在这个学科中, 明确性是编程的 个重要原则 明确性包含限制使用 GOTO 语句和全局变量 ( 最好是完全不用 ) ; 明确声明 ( 通过强制 ) 任何变量的类型, 使得编译者能系统地和自动地检查类型错误 ; 模块化程序设计 ( 把大的程序分解成许多更小的部分, 每部分执行一个任务 ) ; 使用足够的 ( 尽量清楚 ) 说明性材料, 这些材料是在程序中或文档外以文本文件的形式出现的 一个安全系统 ( 密码算法或协议 ) 包括软件和 / 或硬件中实现的程序部分, 对于协议的情况, 程序的各部分要在很多独立的主机上运行 ( 或很多程序并行 交互地运行在这些主机上 ) 软件工程的明确性原则自然适用于安全系统的设计 ( 特别是对协议 ) 可是, 安全系统是假定运行在一个充满敌意的环境下的, 即使合法用户在该环境下也可能是恶意的 因此这种系统的设计者还应该明确很多的附加问题 这里我们列出三个重要方面来作为对安全系统的设计者和实施者的一般指导原则 ( 在本书的其余部分, 我们将遇到很多对算法和协议的攻击, 它们源于这些系统的设计或说明不够明确 ) 1. 要明确所需要的所有假定一个安全系统要通过和环境的交互来运行, 因而有一组由所在环境必须满足的要求 这些要求称之为系统运行的假定 ( 或前提 ) 违反一个协议的假定就可能招致对系统的攻击, 其结果可能是使假定的服务成为泡影 违反一个没有特别清晰说明的 ( 隐含的 ) 假设是很难被发现的, 因此安全系统的所有假定都应当非常明确 协议中有一个隐含的假定或期望是很平常的, 例如假定或期望协议所运行的主机可以提供好的随机数, 但现实中的台式机或掌上设备很少能满足这一假定 如果采用很差的随机数源, 就可对其协议实施一种所谓的低蛐攻击 对安全套接层 (SSL) 协议 (WWW 浏览器与服务器间的一个认证协议, 见 12.5 节 ) 早期实现的一种广泛发布的攻击就是低 ' 脑攻击的一个著名例子 [ 125] 对假定的明确鉴别和规范也有助于对复杂系统的分析 DeMillo 等 ( [92J 的第 4 章 ) DeMillo 和 Meπitt[93 J 建议密码协议的设计和分析采用下面的两步方法 (M lre[ 206,207 J 对其改 进后 ) : i) 标明协议中所在的假定 ii) 对第 (i) 步的每一个假定, 确定违反该假定对协议的安全性所造成的影响 一一

26 第 1 幸一个简单的通信游戏 要明确所提供的确切的安全服务密码算法 / 协议提供特定的安全服务, 一些重要的安全服务包括 : 机密性 ( 消息不能被非接收方理解 ) 认证性( 能确定消息的完整性或消息来源 ) 不可否认性( 不能否认对消息的接触 ) 知识证明 ( 在不泄露的情况下出示证据 ) 和承诺 ( 例如, 我们的第一个密码协议 - 一 " 电子掷币 协议 " 所提供的服务, Alice 无法改变曾使用的宇串 ) 0 当设计一个密码协议时, 设计者应该对协议要提供什么样的服务非常明确, 而且对这些服务应该进行明确的说明 这种明确鉴别和规范不仅能帮助设计者选择正确的密码原型或算法, 而且也能帮助实施者正确地实现协议 服务的鉴别对于上述例子中所给定的一般服务的级别细化往往是不合用的, 还需要对它们进一步细化 下述是一些可能的改进方法 : 机密性 ( Confidentìality ) 认证 (Aut 伽 hen 时 mt 趾 ikca 创 ti0 创 I 川不可否认 d 性 (Non-repudiatìon) 司隐私性 匿名性 不可见性 不可区分性 = 斗珍数据据 源 数据完整性 = 丰消息发布 消息收据 知识证明 (Proof of Knowledge) => 知识拥有权 知识结构 在协议设计中, 对服务的错误鉴别可能导致误用密码原型, 从而导致协议的安全性缺陷 在第 2 章和第 11 章我们将看到灾难性的例子, 由于对安全服务在机密性和认证性的错误鉴别, 导致了认证协议的严重安全缺陷 还可能有很多名字更特别的安全服务 ( 例如, 消息的新鲜性 不可延展性 前向保密 完善零知识 公平性 绑定性 否认性 无收据等 ) 这些服务可被看成是从前面已列出的一般性服务的导出结果或进一步细化 ( 导出也可以是否定的, 例如否认性就是不可否认性的否定导出 ) 尽管如此, 为了避免设计缺陷, 对它们进行明确区分往往是必要的 3. 要明确数学方面的 - 些特殊情况正像在 节中讨论过的那样, 计算复杂性理论中的一些困难问题能给密码算法或协议提供更高可信度的安全性 但是, 一个困难问题往往有一些特殊情况, 其中的该问题根本不难 例如, 大整数分解问题一般是很困难的, 但对大合数 N= PQ, 如果 Q 是大素数 P 的下 个大素数, 则分解就不是什么难题! 我们可以通过计算 L.J 万 J(L.J 称为底函数, 表示取整 ) 并用 些离 P 和 Q 很近的素数试着去除就能很快求解 密码算法赖以工作的常用代数结构 ( 如在第 5 章将研究的群 环和域 ) 也包含一些特殊情况, 也会产生一些例外的容易问题 乘法群或有限域中的低阶元素 ( 定义见第 5 章 ) 就提供这样一个例子, 一个极端情况是 Di ffi e- Hellman 密钥交换协议 ( 见 8.3 节 ) 中的基是这些代数结构中的单位元 椭圆曲线的弱的情况, 例如," 超奇异曲线 " 和 " 非正规曲线 " 也是很好的例子 超奇异曲线上离散对数问题可归约为有限域中的离散对数问题, 称为 Menezes-Okamoto- Vanstone 攻击 [199J( 见 节 )0 " 非正规曲线 " 的点数与相应的有限域中元素的个数是一样的, 其离散对数问题存在一个多项式时间攻击, 称为 Satoh 也地 i[254] Semaev[260] 和 Smart[280] 攻击 O 一种容易的特殊情况如果未能被算法 / 协议的设计者摘明白, 或 / 和在算法 / 协议规范中没有明确说明, 那么它就可能很容易地混人到实现中去, 从而被攻击者所利用 因而算法 / 协议设计者必须警觉数学方面的特殊情况, 并应该对实现者明确地说明其过程, 以避免这种情况的发生 为明确性而列出更多的条目并不困难 ( 例如, 密钥管理协议应该明确地规定密钥管理的规则, 比如不同用途的密钥应该分离, 适当的密钥分发步骤等 ) 由于这些条目的特定性, 我们无法 十一

27 12 现代密码学理论与实践 在这里把它们都列出来 不过, 作为密码算法 / 协议的设计和规范的一个一般准则, 明确性在本书的其余部分将会经常提及 一般, 一个密码算法 / 协议设计和规范得越清楚, 对其分析也就越容易, 因而也就越有可能正确地实现, 算法 / 协议遭受意想不到攻击的可能性也就越小 开放性 密码学一度为政府专有 军事和外交机构用它来保密消息 在那些年代, 大多数密码研究都是关起门来做的, 算法和协议是秘密 的确, 政府过去而且今后仍然会认为, 对他们的密码研究活动进行保密是有道理的 让我们设想 个政府机构发布了一个密码 我们仅能认为所发布的密码是可证明安全的 ; 否则发布就很危险并最终可能让政府感到非常尴尬 那么别的政府可能会利用这个可证明安全的密码, 结果就削弱了发布这一密码的政府中破译者的战斗力 可是今天, 密码机制已经与很多大范围的民用系统结合在一起 ( 在本章最开头我们已粗略地列举了一些应用 ) 民用的密码研究应该采用公开的途径 密码算法确实用到一些秘密, 但这些秘密应该局限在密码的密钥或密钥数据 ( 如口令或个人身份号 PIN) ; 算法本身应该公开 让我们来解释这样规定的理由 在任何研究领域, 高质量的研究都依赖于通过会议报告和在学术期刊上发表文章来公开交换想法 这种交换以一般的形式进行 但对于密码算法 协议和安全系统, 公开研究不仅是一般意义上的获得和增长知识 公开研究的一个重要作用是公开的专家检验 大家都知道, 密码协议 算法和安全系统很容易出错 一个密码研究结果一旦被发布, 就可以由很多专家来检验 因而设计者所忽视的错误 ( 可能在设计中或在安全分析中 ) 被发现的机会就大大增加了 相反, 如果对算法的设计和开发保密, 那么为了保密, 即使可能有, 也只有很少专家能够接触和检查算法的细节, 结果发现错误的机会也就减少了 一个更坏的情况是, 设计者可能已经知道有错误, 并将其秘密地用于谋取私利 民用的密码算法 协议和安全系统必须公开, 并且必须经过长时间的公开检验, 现在已经成为一个既定的准则 一个安全的系统也应该由反对的专家进行同等的评价 1.3 小结 在本章, 我们以应用密码学的一个简单例子开场 这个例子达到了三个目的 : i) 展示了密码学在解决问题方面的效力 ii) 致力于对密码学基础的了解 iii) 强调了非教科书式安全方面的重要性这些构成了本书其余部分要讨论的主要内容 我们接着进行了一系列的讨论, 目的是给出这一研究领域的初始背景和文化导论 我们对 这些方向的讨论并不完全 其他几位作者已对密码学和信息安全领域的原理 指导原则和文化进行了广泛的研究 下面的几本书是很好的进一步阅读材料 : Schneier [ 256 ] Gollmarm [ 131 ] 和 Anderson[ 14] 0 Schneier 创办的月刊 "c 叨,to- Gram Newslet 始岛 " 也是很好的阅读材料 要订阅这份 快报, 请发电子邮件到 schneier@ unte 耶皿 e.ωn ~ 叫一一

28 第 1 章一个简单的通信游戏 13 习 1. 1 算法和协议的区别是什么? 1. 2 在协议 1. 1 中, Alice 能决定正面或背面 这在某些应用中可能是不公平的, 请修正 该协议, 以便使 Alice 不再具有这个优势 提示 : 让正确的猜测决定是正面或背面 1. 3 设函数 f: 是从 2 比特的整数集合到 1 比特的整数集合的映射, 映射规则如下 : f(x) ~ (x 的前 1 比特 )EB(x 的后 l 比特 ) 这里 5 表示逐比特异或 (XOR) 运算, 即 αebb:::. O 若 α =b 1 其他 i) f 的效率高吗? i 川 i) f 是否具有 " 性质 1" 巧,? iii) f: 是是否具有 " 性质 Il 町 1" i 川 v 讨 ) 该函数能在协议 1. 1 中使用吗? 1. 4 未被攻破的密码算法比已被攻破的就安全吗? 如果不, 为什么? 1. 5 复杂的系统容易出错, 给出复杂的安全系统更容易出错的其他原因 一一

29 第 2 章防守与攻击 2.1 引言 存在众多密码学协议的一个原因是基于以下事实 : 确保密码协议正确是很困难的 设计一个正确的协议要投入无限的精力 许多新提出的协议是为了修补已发现的现有协议的安全缺陷 密码协议中的安全隐患总是可以用一个攻击脚本描述, 在其中协议所提供的 些安全服务能够被一个或一些相互勾结的攻击者蓄意破坏 在密码协议领域, 似乎永远存在着协议设计者和攻击者之间的较量 : 提出一个协议, 发现一种攻击, 跟着进行修补, 而后又发现另一种攻击, 再一次修补... 在这一章中, 我们将演示一系列攻击和修补之间争斗的例子 我们从故意设计一个存在缺陷的做作协议出发, 通过将这个协议经历 " 修补 攻击 再修补 再攻击 " 的过程, 最终将得到两个协议, 它们是由计算机安全学家们所设计的, 用以解决现实世界中的信息安全问题 ( 此前所有那些有缺陷的和被修补的, 因而被攻破的协议都是故意设计的 ) 这两个源于我们的" 修补 攻击 再修补 再攻击 " 过程所得到的协议不仅是真实的, 而且是闻名的 其理由有二, 它们在应用上和在密码学协议的形式化分析的基础性重要研究上都起着根本性的作用 遗憾的是, 这两个通过修补得到的真实协议仍含有安全缺陷, 在协议发表很久以后才发现 它们 其中一个协议的一个缺陷是发表三年之后才发现的, 而另外一个协议的一个缺陷竟然又过了十四年才被揭露! 在披露这些缺陷之后, 我们将试图对其进行最后的修补 虽然在最后修补结果中还有某些进一步的安全问题, 但我们将推迟到后面的章节中再去揭示, 那时我们已具备了处理这些问题的能力 本章不打算解决安全问题, 而是想提出一个 " 早期警报 " 消息 : 密码算法 协议和系统很容易包含有缺陷 本章也作为一个材料和理念上的技术性引论, 使我们 ( 尤其对于刚接触到密码学 密码协议和信息安全领域的读者 ) 建立起在该领域的研究中遇到的一些常见的重要概念 定义和约定, 包括一些基本的术语 它们的含义 ( 第一次出现的词会用黑体形式 ) 和一些在全书中经常遇到的协议参与者的约定取名 还会介绍对这些有安全缺陷的协议的各种攻击, 这将使我们对在我们的对弈游戏中扮演特殊角色 ( 攻击我们所设计的密码协议的敌人 ) 的一些典型行为逐渐熟悉起来 在 2.2 节我们介绍了只用于本章的一个简化的加密概念 在 2.3 节 节中我们将介绍密码技术, 特别是认证 协议中的标准威胁模型 环境和目标 最后, 在 2.6 节我们对一系列 认证协议展开讨论 2.2 加密 本章中要设计的所有协议都用到加密技术 我们要对这种 " 锅煮 " 的加密做法及早提 f11

30 第 2 章防守与攻击 15 一个忠告 : 在许多情况下, 这种用法是不正确的, 而应该用其他一些密码原型来代替 在本书中, 我们将逐步建立对为获得精确的安全服务需要准确地应用密码原型的意识 不过, 为了简化我们的介绍, 在本章中我们仅使用加密技术 加密 ( 有时称为加密作业, 是将一条信息变换成为不可理解的形式的过程 输入到该变换器的信息叫明文或明掘, 输出的叫密文或密报 将密文转换成明文的过程叫解密或解密作业 注意明文和密文是一对相对应的记号 : 前者是指一个加密算法的输入, 后者是指输出 明文不必是可理解的 ; 例如, 在双重加密的情形中, 位于中间的密文可以看成是第二次加密的明文 ; 本章我们还会多次看到, 在密码协议中对随机数的加密是很普遍的 通常, 明报是所有消息集合的一个小的子集, 这个小子集具有一定的可辨认的分布 在 3.7 节中我们研究消息的分布 加密和解密算法统称为密码算法 ( 密码系统或密码体制, Cryptosystem), 加密和解密过程均由密钥控制 在对称 ( 或共事密钥 ) 密码体制中, 加密和解密采用同一密钥 ; 而在非对称 ( 或公钥 ) 密码体制中, 加密和解密采用两个不同的密钥 : 加密密钥和 ( 相匹配的 ) 解密密钥, 加密密钥可以公开 ( 因此也称为公开密钥 ) 而不会泄露解密密钥 ( 因此公钥密码体制中解密密钥也称为私钥 ) 图 2.1 给出了密码体制的简单图形描述 更加完整的密码体制的描述将在第 7 章 给出 ( 见图 7.1 ) 加密 明文 加密密钥 解密密钥 密文 解密 图 2.1 密码系统的简化图形描述 应当指出, 在本章范围内, 词语 " 明文 " " 密文 " " 加密 " " 解密 " " 加密密钥 " 和 " 解密密钥 " 是成对关联的概念 对于消息 M( 不管是明文还是密文 ) 密码算法 A( 不管它代表加密还是解密 ) 和密钥 K( 不管它是加密密钥还是解密密钥 ), 我们可以用 M' = A(K, M) 表示一个密码变换, 它代表了图 2.1 和 K' 来表示 中上面方框或者下面方框的作用 因而, 我们可以用 A' M = A' (K', M') f!p M = A' (K', A (K, M)) 叫可川

31 16 现代密码学理论与实践 以走完图 2.1 中的圈 在对称钥密码体制中, 我们可以认为 K' = K, 在公钥密码体制中, K' 表示 K 的秘密部分或与 K 相匹配的部分 本章协议中消息的密文习惯上记为! Mf K 在学了消息的概率分布 ( 在 3.7 节 节中介绍 ) 后, 我们就会知道明文 ( 更精确地说, 明报或可懂的 ) 消息是整个消息空间中的一个小的子集, 而密文消息在这个空间中的分布要广得多, 这是明文和密文的本质区别 我们应该注意, 在这一章中, 我们所谓的密文总是指采用下述两个意义上的 " 完善 " 密码算法所得到的 : 性质 2.1 用符号! Mf K 表示的完善加密 i) 不用密钥 K( 在对称密码体制中 ), 或者不用与 K 相匹配的私钥 ( 在公钥密码体制中 ), 密文 1 M! K 不提供任何求解明文消息 M 的密码分析方法 ii) 密文 1M! K' 也许还有一些关于明文消息 M 的已知信息, 不提供任何求解密钥 K( 在对 称密码体制中 ) 或与 K 相匹配的私钥 ( 在公钥密码体制中 ) 的密码分析方法 具有这两个性质的完善加密 ( 还有一个附加性质将在 节中介绍 ) 是对现实世界中存在的加密算法的理想化 这个理想化能便于我们处理, 可将协议设计与分析的责任同协议所使用的密码算法的设叶和分析的责任分离 这种分离使协议的设计和分析工作变得容易 我们马上就会看到, 完善加密并不能防止协议含有安全缺陷 事实上, 本章要示范的协议的任何一种攻击, 都不是因为相应的密码体制不完善 我们将在后面的章节中 ( 第 7 章 第 8 章 第 13 章和第 15 章 ) 介绍加密的形式化定义和几个加密算法 尽管如此, 这里对加密和解密作用描述的抽象程度能够满足本章的要求 把加密算法看成是一个有钥匙的挂锁, 而把密文看成是装在挂锁锁上的盒子中的文本, 对我们目前来说是元害的 读者可以参阅文献 [268] 来获得有关信息安全的有用词汇 2.3 易受攻击的环境 ( Dolev-Yao 威胁模型 ) 由计算机 设备和资源构成的大型网络 ( 例如因特网 ) 是典型开放性的, 这就意味着一个主体 ( 或实体 代理 用户 ) 能够加入这样的网络, 并通过该网络来发送和接收消息, 而不需要由 " 超级 " 主体授权, 这里的主体可以是一台计算机, 一个设备, 一些资摞 服务的提供者, 一个人或一个组织等 在这样的开放性环境中, 我们必须想到会有坏人 ( 攻击者 对手 敌人 入侵者 窃昕者 冒名顶替者等 ), 他们会做各种坏事, 不仅仅是被动地窃听, 而且会主动地改变 ( 可能用某些未知的运算或方法 ) 伪造 复制 改变路由 删除或注入消息 注人的消息可能是恶意的并对接收端主体以破坏性的影响 在密码学文献中, 这些坏人叫主动攻击者 本书中, 我们把攻击者称为她 Iice( 是指经常带着不同身份面具做坏事或捣蛋的人 )0 Malice 可以是单个的, 也可以是相互句结的攻击团伙, 一个特例是, 它可能是协议中的一个合法主体 ( 内部人员 ) 一般假定 Malice 在操纵经开放性网络的通信方面是相当聪明的 由于他们的行为是不规施的, 其操纵技术也是难以预料的 而且, 由于 Malice 可以表示一个相互勾结的坏蛋团伙, 他

32 一..r 第 2 章防守与攻击 17 可以同时控制地域上相距很远的一些网络节点 Malìce 何以能做这些的真正原因将在 12.2 节中介绍 在这样脆弱的环境中预料到如此强大的对手, Dolev 和 Yao 提出了一个威胁模型, 这一模型被广泛地采纳为密码协议的标准威胁模型 [102J 0 在这个模型中, Malìce 有如下特征 : 他能获得经过网络的任何消息 他是网络的一个合法使用者, 因而能够发起与任何其他用户的对话 他有机会成为任何主体发出信息的接收者 他能够冒充任何别的主体给任意主体发消息 因此, 在 Dolev-Y: 栅威胁模型中, 发送到网中的任何消息都可看成是发送给 Malice 处理的 ( 根据他的计算能力 ) 因而从网络接收到的任何消息都可以看成是经过 Malice 处理过的 换句话说, 可认为 Malice 已完全控制了整个网络 事实上, 将开放性网络看成是 Malice 是无害的 但是, 除非明确声明, 我们并不认为 Malice 是全能的 这意味着即使把他看成是一个相互勾结的犯罪团伙, 能够并行使用跨越开放网络中的大量计算机, 也还有一些 Malice 所不能做的事情 下面在不对 " 不能做 " 的意思量化的情况下, 我们列出一些 Malice 不能做的事情, 准确的量化将在第 4 章给出 : Malice 不能猜到从足够大的空间中选出的 没有正确的密钥 ( 或私钥 ), Malice 不能由给定的密文恢复出明文 ; 对于完善加密算法, Malìce 也不能从给定的明文构造出正确的密文 Malice 不能求出私有部分, 比如, 与给定的公钥相匹配的私钥 Malìce 虽然能控制我们的计算和通信环境的大量公共部分, 但一般他不能控制计算环 境中的许多私有区域, 如访问离线主体的存储器 我们将采用 Dolev-Yao 威胁模型来处理所有我们将遇到的协议 2.4 认证服务 假设两个主体 Alìce 和 Bob( 我们在第一个密码协议 " 电话掷币 " 中已遇到过, 协议 1.1) 希望相互通过安全方式进行通信 假设 Al ice 和 Bob 以前从未见过面, 因而他们不能事前就有一个共享密钥, 也不能确定对方的公钥 那么他们怎样通过根本不安全的网络安全地通信呢? 直接的方式是 Al 悦和胁可约会至少彼此见一面, 并建立一个共享秘密钥或交换有关对方公钥的确切知识 然而, 在有 N 个用户希望进行秘密对话的系统中, 为了安全地建立这些密钥, 这些用户需要进行多少次旅行才行呢? 答案是 N(N -1) /2 遗憾的是, 对于 个庞大系统, 这意味着其代价是不可行的 因此, 在现代通信系统中这种直接的安全密钥建立方式是不实际的 然而, 每一个主体选用安全的通信来获得认证 ( 和目录 ) 服务是可行的 N 四晶 m 和 Schr 佣 der 提出这种服务可以由认证服务器来提供 [215J 这种服务器就像一个名字注册机构, 它根据它所服务的主体的名字维护一个检索数据库, 并能够递送通过请求主体密钥所计算出来的身份信息, 而该密钥为服务器和主体所共事 认证服务器是一种特殊的主体, 它的行为老实并必须得到用户 ( 客户主体 ) 们的信赖 也就是说, 只要客户主体要求, 它就严格按照协议规范做出反应, 而不会参与其他任何故意破坏 一

33 18 现代密码学理论与实践 客户安全的活动 ( 比如, 它永远不会向任何第三者泄露它和顾客共享的密钥 ) 这样的主体称为可信第三方或简记为 T 凹, 在本书中我们用 Trent 来命名可信第三方 O 我们假设 Alice 和 Bob 使用由各自的认证服务器提供给他们的认证服务 在扩大的网络中, 仅用一个中心认证服务器是不明智的 N 白 dham 和 Schroeder 建议用相互了解的多个认证服务器 因而, 仅由一个认证服务器提供服务的主体的名字格式为 " 认证机构. 简单名字 " Diffie 和 Hellman 也曾提出了使用多个认证服务器的想法 [98] 然而, 为了简单 清楚地描述本章中的协议, 我们假设 Alice 和 Bob 使用同一个认证服务器 Trent 在第 12 章, 我们将介绍和分析 Windows 2 侧操作系统中的网络认证基础一 -Ke 如 m 认证协议 [9 1], 它考虑采用多个认证服务器管理多个网络的一般性网络构造 在同一个认证服务器提供服务下, 我们假定 Alice( Bob) 和 Trent 共享一个密钥, 设密钥由 K AT ( KBT ) 表示 以后我们将会看到这种密钥称为密钥 - 加密密钥, 因为它的用途主要是加密 其他密钥 由于建立这样一个密钥的高额花费, 它应该被长期应用, 因此它也叫长期密钥 2.5 认证密钥建立的安全特性 本章中描述的所有协议都属同一类型, 它们都用来实现认证的密钥建立 这种安全服务 的确切含义可由以下的三个性质详细说明 假设 K 表示 Alice 和 Bob 要建立的共享密钥, 在本章中所要设计的协议都应实现具有以 下三个性质的安全服务 协议执行完毕后 : 1. 只有 Alice 和 Bob( 或者可能还有他们都信任的某个主体 ) 能够知道 K 2. Alice 和 Bob 应当知道对方主体知道 K 3. Alice 和 Bob 应当知道 K 是新生成的 第一个条性质是由认证的最基本含义得出的 : 识别将要通信的目标主体 如果启用密钥 K" 加锁 ", Alice( 或 Bob) 应当确信通信的另一端一定是 Bob( 或 Alice) 如果密钥建立服务是在 Trent 的帮助下实现的, 那么应当相信 Trent 不会伪装成两个主体中的任何一个 第二条性质将认证服务扩展到另一个方面, 即实体认证, 或者是已识别出的通信对象主体 的活现性 Alice( 或 Bob) 应当确信, 当前通信协议运行中 Bob( 或 Alice) 参与了, 并对通信做出 响应 c 以后我们将会看到, 为了防止对旧消息的重放攻击, 这条性质是必要的 对第三条性质的需求源于密码学中长期确立的密钥管理原则 原则规定 : 当 个密钥是共 享密钥并用于大量的数据加密时, 只能使用较短的时间 这种密钥的用法和 " 密码加密密钥 " 或 2.4 节末所提到的长期密钥的用法大为不同 这种密钥管理原则有两个原因 : 第一, 如果一个数 据的加密密钥是共事的, 那么即使共享者中的 方 Alice 在密钥的管理和使用中非常谨慎, 而在 Al ice 的控制之外, 由于另一个共享者 Bob 的不谨慎而泄露了这个共享密钥, 仍然会导致 Al ice 的 安全得不到保障 ; 第二, 在保密通信中, 通常大多数数据包含 ( 可能是大量 ) 已知的或可以预料的 信息或结构 例如, 一段计算机程序包含大量的已知词汇, 如 g 伊 n 正,γemnd"γ Jfλ 川 " 1 'cl 飞阳 ω 酣 s 旷,γint 川 t"γ JJ 汀 " γ 1i 勺 " 由 ednd,"'\ J " 飞 edlsded"\, J " ++" 等 这种数据包含大量的冗余 ( 定义见 3.8 节 ) 这类数据的加密使得密钥 成为以寻找密钥和明文为目标的密码分析的对象, 延长这类数据加密密钥的使用时间将会降低 密码分析的困难性 我们还应该考虑到,Mal ice 有元限的时间来寻找一个旧的加密密钥, 并在找 --'- '-'-ω 山峰

34 第 2 章防守与攻击 19 到后把它当做新的密钥来用 已经牢固建立并广为接受的密钥管理原理规定, 一个共享密钥仅 能用于一次通信会话 因此这种密钥也称会话密钥和短期密钥 认证密钥建立服务的第三条性 质向 Alice 和 Bob 保证, 建立的会话密钥 K 是新产生的 2.6 利用加密的认证密钥建立协议 现在我们已经做好了设计认证密钥建立协议的准备, 要设计的第一个协议只是为了直接 实现下列简单想法 : Alice 和 Bob, 虽然彼此不认识, 但都认识 Trent 并且分别和 Trent 共享长期 密钥, 因而 Trent 能安全地在他们之间传递消息 消息保密协议 由于协议的运行环境是脆弱的, 我们的协议将使用加密技术来防范可能的威胁 在一步一步讨论的最初阶段, 我们将把注意力放在对消息保密的威胁上 从 Alice 到缸旷协议设 Alice 发起运行这样一个协议 她首先随机生成一个会话密钥, 然后用已有的和 Trent 共享的长期密钥对这个会话钥加密, 并把密文连同自己和 Bob 的身份信息发给 Trent 在收到 Alice 会话密钥递送的请求后, Trent 首先从数据库中找出 Alice 请求中提到的两个主体的长期 共享密钥, 然后用 Alice 的密钥解密密文, 再用 Bob 的密钥对解密后的结果进行加密并把加密 后的新密文送给 Bob 最后, 收到递送的会话密钥数据并经解密后, Bob 就用新收到的会话密 钥加密一条消息发给 Alice 来确认此次接收 协议 2.1 示例了实现从 Alice 到 Bob 会话密钥传 递的协议描述 在这个协议中,Alice 是发起者,Bob 是响应者 协议 2.1 从 Alice 到 Bob 假定 Al ice 和 Trent 共享密钥 K"'T,Bob 和 Trent 共享密钥 KBTo 目标 Al ice 和 Bob 想要建立一个新的共享密钥 K A 且由 Trent Bob Alice 产生一个随机数 K, 创建! K 1 K Ar 并且向 Trent 发送 : Al 町, Bob,!Kl 与 T; 2. Trent 找出密钥 K"'T 和 KBT' 解密! Kl K 恢复 K, 创建! Kl K 并向 Bob 友送 : Al 町, Bob, AT. "BT! Kl K 盯 ; 3. Bob 解密 1 Kl K 町恢复 K, 向 Alice 发送 : 1 你好 Al 町, 我是 Bob! 1 K 二

35 凶 现代密码学理论与实践 本章中, 我们将分两部分介绍我们的大多数协议 ( 和对协议的攻击 ), 图示部分说明在主体之间传递的消息流, 说明部分将给出主体进行发送和接收消息活动的细节 虽然单单说明部分就已足够精确描述协议 ( 在本书其余章节中, 仅用说明部分作为协议的描述方式 ), 但我们打算通过增加消息流的图示表示, 使密码协议领域的初学者轻松起步 这也是本章的目的之一 在研究协议 " 从 Al ice 到 Bob" 是否包含任何安全缺陷之前, 我们应该首先讨论协议的设计特征 协议使得 Alice 生成一个与 Bob 共享的会话密钥, 那么 Bob 对此高兴吗? 如果发现由 Alice 产生的会话密钥的随机性并不足够好 ( 密钥应该是随机的以使用猜测很难确定 ), 因为密钥是共享的, 那么 Bob 的安全性将不能得到保障 也许 Alice 并不关心会话密钥是否强, 或者她只是为了方便记忆 只要 Bob 不信任 Alice( 甚至在协议运行前不相识 ), 那么他可能不愿意接受这样一个会话密钥并与之共事 我们将修改这一协议, 去掉协议的这一设计特征并讨论修改后协议的安全性 " 来自 Trent 的会话密钥 " 协议由于 Trent 得到了两个客户主体的信任, 他通过适当方式生成的会话密钥应能得到双方的信任 因而可以把协议 2.1 修改成协议 2.2 首先, Alice 把自己和 Bob 的身份信息发给 Trent, 这两个主体 Alice 和 Bob 想共享一个秘密通信的会话密钥来进行保密通信 在收到 Alice 的请求后, Trent 将在自己的数据库中找出两个主体各自的密钥, 生成一个要在这两个主体之间共享的新的会话密钥, 然后分别用相应的密钥对会话密钥进行加密, 并把加密后的结果送给 Aliceo Alice 对属于自己的部分进行处理, 并把属于 Bob 的那部分传给 Bob 最后,Bob 处理协议中自己的那一部分, 并发送收到会话密钥的一个肯定回执来结束协议 我们把修改后的协议命名为 " 来自 Trent 的会话密钥 " 协议 2.2 来自 Trent 的会话密钥 假定 Al ice 和 Trent 共享密钥 KAT,Bob 和 Trent 共享密钥 KB7 咽 目标 Al ice 和 Bob 想要建立一个新的共享密钥 Ko Alice Trent Bob l Alice 发给 Trent: Alice, Bob ; 2. Trent 找出密钥 KAT~KB1', 随机生成 K, 发送给 Mim:lkkTJKlk 町 ; 3. Alice 解密 1 Kl K AT 并发给 Bob: Trent, Al 时, 1KIK BT ; 4. Bob 解密 1 Kl KBJ' 恢复 K, 发给 Alice: 1 你好 Al 町, 我是 Bob!IKo 川一一叫

36 第 2 章防守与攻击 21 在完善加密方案下对会话密钥加密后, 一个被动的窃听者在看到 " 来自 Trent 的会话密钥 " 协议的运行后, 因为这些密文仅能由合法的接收者用各自的密钥解密后阅读, 在没有加密钥 ιt 和 K 盯的情况下, 无法得到会话钥 K 的任何信息 攻击 修复 攻击 修复 现在我们来举例说明本书的一个标准场景, 即攻击 修复 攻击 修复 一个攻击 协议 " 来自 1Ì'ent 的会话密钥 " 是有缺陷的 此协议的问题是, 谁应该得到会话密钥这 - 信息没有得到保护 攻击 2.1 给出了一个攻击方式 在这个攻击中, Malice 截获网上传递的 些消 息, 将它们修改后并假冒某些主体发给另外一些主体 在攻击 2.2 所描述的攻击中, 我们用 Alice 发送给 Malice("T 陀 nt"):" 来表示 Malice 截获 Alice 发给 Trent 的消息的行动, 用 Malice( " Alice" ) 发送给 Trent: 来表示 Malice 通过模仿 Alice 向 Trent 发送消息的行为 我们应该注意, 根据我们在 2.3 节所同意的协议环境的 Dolev-Y;ω 威胁模型, 假定 Malice 能完全控制脆弱的网络 因此 Malice 能够采取上面提到的恶意行为 我们能够想像, 当 Malice 操纵了通过网络的消息时, 代号 (" 主体 名字 ") 就成了 Malice 佩戴的面具了 在 12.2 节我们将从技术上看到 Malice 是如何通过这种办法操纵在网络中所传递的消息的 攻击 2.1 对 " 来自 Trent 的会话密钥 " 协议的一种攻击 假定除了原协议的假定外, Malice 和 Trent 共享密钥 KM'J' 攻击结果 Alice 认为在和 Bob 共享密钥 K, 但事实上是在和 Malice 共享密钥 K AIi 臼 MaIice Trent Bob Alice 发给 Malice( "Trent") : Al, 时, Bob; 2. Malice(" Alice") 发给 Trent: Alice, Malice ; 3. Trent 找出密钥 KA. T, KM'J', 随机产生 KAM 并发给 Alice: 1 KAM f K ' 1 KAM f KM'J' ; AT 4. Alice 解密情川马 T 并发给 Malice(" Bob") : Trent, Al 时, 1 KAM 1 KM'J' ; S. Malice(" Boh") 发给 Alice: 1 你好 Al 町, 我是 Bob!IK "AM 4.~~ 叩

37 22 现代密码学理论与实践 Malice 开始截获由 Al ice 发送给 Trent 的初始消息 这条消息的意思是让 Trent 产生 - 个由 Alice 与 Bob 共享的会话密钥 K 翩 Malice 通过把 Bob 的身份改为自己的身份来改变这条消息并把它发送给 Trento Trent 会认为 Al ice 想和 Malice 交谈, 因此他产生了一个 Malice 和 Al ice 共享的新的会话密钥 KAM' 同时 Trent 用和这两个主体共享的长期密钥分别进行加密 由于 Alice 不能区分发送给其他用户的加密消息, 所以她不会察觉出这种改变 Malìce 随后就可截获 Alice 打算发给 Bob 的信息, 而 Bob 并不知道他被要求运行这个协议 攻击的结果是, Al ice 认为和 Bob 成功地完成了这个协议, 而实际上 Malice 知道 K 脯, 因此可以伪装成 Bob 窃听 Alice 发送给 Bob 的所有消息 注意, 仅在 Malice 对于 Trent 是一个已知合法用户的情况下, 这种攻击才会成功 这又是 - 个现实的假设一一内部攻击者通常比外部攻击者更有威胁 我们已经看到, 上述攻击结果是 Malice 通过改变 Bob 的身份造成的 我们注意到这种改变是可能的, 因为 Bob 的身份是用明文发送的 这就提示我们通过隐藏 Bob 的身份来修改协议 一种修补 在理解了上述 Malice 改变 Bob 身份的攻击后, 要修改协议 " 来自 Trent 的会话密钥 " 看来就很简单了 例如, 我们可以对协议进行修改, 将第一条消息中 Bob 的身份处理成为秘密的, 用 Alice 和 Trent 之间的共享密钥进行加密 也就是说, 协议 " 来自 Trent 的会话密钥 " 中第一条消息应正确地修改为 1. Al ice 发送给 Trent: Al 时,! Bob f K AT ; 注意, 这里 Al ice 解密 的身份仍为明文是必要的, 以便 Trent 能知道他应用哪个密钥对密文部分进行 另一种攻击 然而, 上述修改方法没有为 " 来自 Trent 出, Malice 会执行 : 的会话密钥 " 提供 种彻底的修补 例如, 不难看 1. Malice(" Alice") 向 Trent 发送 :Alkh i MdmkT; 协议的其余部分与攻击 2.1 相同 如果 Malice 起初不知道 Al ice 打算和谁运行这个协议, 因为消息中必须包含 Bob 的地址以便网络正确传递信息, 于是当他截获到 Al ice 发送给 Bob 的消息, 就可以知道这部分信息 因此 Malice 最终仍然能成功地伪装成 Bob o 注意, 在这个攻击中 我们假定 Malice 有密文!Malice! 凡 T: 这可能是因为 Malice 已经从 Alice 和 Malice 先前的 - 个协 议运行中 ( 一个正确的运行 ) 将它记载下来了 再一种攻击 事实上, 对协议 " 来自 Trent 的会话密钥 "( 或上述它的修补 ) 还有一种攻击方法, 它并不依赖改变任何主体的身份 而是, Malice 将 Trent 发给 Alice 的消息 ( 协议 " 来自 Trent 的会话密钥 " 第 2 条中的消息 ) 改变为 Malice( "T 陀 nt" ) 向 Al ice 友送 :! K' f K ' AT 十一