密码学原理与实践（第三版）

本书是密码学领域的经典著作，被世界上的多所大学用做指定教科书。本书在第二版的基础上增加了7章内容，不仅包括一些典型的密码算法，而且还包括一些典型的密码协议和密码应用。全书共分14章，从古典密码学开始，继而介绍了Shannon信息论在密码学中的应用，然后进入现代密码学部分，先后介绍了分组密码的一般原理、数据加密标准(DES)和高级加密标准(AES)、Hash函数和MAC算法、公钥密码算法和数字签名、伪*数生成器、身份识别方案、密钥分配和密钥协商协议、秘密共享方案，同时也关注了密码应用与实践方面的一些进展，包括公开密钥基础设施、组播安全和版权保护等。在内容的选择上，全书既突出了广泛性，又注重对要点的深入探讨。书中每一章后都附有大量的习题，这既利于读者对书中内容的总结和应用，又是对兴趣、思维和智力的挑战。

Douglas R. Stinson 本书作者Douglas R. Stinson：加拿大安大略省滑铁卢（Waterloo）大学计算机学院首席研究员。目前的研究兴趣包括认证码，秘密共享，通用Hash函数，弹性函数，广播加密，密钥分配协议，组合设计理论等。

第1章 古典密码学 1
1.1 几个简单的密码体制 1
1.1.1 移位密码 2
1.1.2 代换密码 5
1.1.3 仿射密码 6
1.1.4 维吉尼亚密码 9
1.1.5 希尔密码 10
1.1.6 置换密码 14
1.1.7 流密码 16
1.2 密码分析 19
1.2.1 仿射密码的密码分析 21
1.2.2 代换密码的密码分析 22
1.2.3 维吉尼亚密码的密码分析 24
1.2.4 希尔密码的密码分析 27
1.2.5 LFSR流密码的密码分析 28
1.3 注释与参考文献 29
习题 30
第2章 Shannon理论 36
2.1 引言 36
2.2 概率论基础 37
2.3 完善保密性 38
2.4 熵 42
2.4.1 Huffman编码 43
2.5 熵的性质 46
2.6 伪密钥和**解距离 48
2.7 乘积密码体制 52
习题 54
第3章 分组密码与高级加密标准 57
3.1 引言 57
3.2 代换-置换网络 58
3.3 线性密码分析 61
3.3.1 堆积引理 61
3.3.2 S盒的线性逼近 63
3.3.3 SPN的线性密码分析 66
3.4 差分密码分析 69
3.5 数据加密标准 74
3.5.1 DES的描述 74
3.5.2 DES的分析 78
3.6 高级加密标准 79
3.6.1 AES的描述 80
3.6.2 AES的分析 84
3.7 工作模式 84
3.8 注释与参考文献 87
习题 88
第4章 Hash函数 92
4.1 Hash函数与数据完整性 92
4.2 Hash函数的安全性 93
4.2.1 随机谕示模型 94
4.2.2 随机谕示模型中的算法 95
4.2.3 安全性准则的比较 98
4.3 迭代Hash函数 100
4.3.1 Merkle-Damg?rd 结构 101
4.3.2 安全Hash算法 106
4.4 消息认证码 108
4.4.1 嵌套MAC和HMAC 109
4.4.2 CBC-MAC 111
4.5 无条件安全消息认证码 113
4.5.1 强泛Hash函数族 115
4.5.2 欺骗概率的优化 117
4.6 注释与参考文献 119
习题 120
第5章 RSA密码体制和整数因子分解 126
5.1 公钥密码学简介 126
5.2 更多的数论知识 127
5.2.1 Euclidean算法 127
5.2.2 中国剩余定理 131
5.2.3 其他有用的事实 133
5.3 RSA密码体制 135
5.3.1 实现RSA 136
5.4 素性检测 139
5.4.1 Legendre和Jacobi符号 140
5.4.2 Solovay-Strassen算法 142
5.4.3 Miller-Rabin算法 146
5.5 模n的平方根 147
5.6 分解因子算法 148
5.6.1 Pollard p?1算法 148
5.6.2 Pollard ?算法 150
5.6.3 Dixon的随机平方算法 152
5.6.4 实际中的分解因子算法 156
5.7 对RSA的其他攻击 157
5.7.1 计算?(n) 157
5.7.2 解密指数 158
5.7.3 Wiener的低解密指数攻击 162
5.8 Rabin密码体制 165
5.8.1 Rabin密码体制的安全性 167
5.9 RSA的语义安全性 168
5.9.1 与明文比特相关的部分信息 169
5.9.2 **非对称加密填充 171
5.10 注释与参考文献 176
习题 177
第6章 公钥密码学和离散对数 184
6.1 ElGamal密码体制 184
6.2 离散对数问题的算法 186
6.2.1 Shanks算法 186
6.2.2 Pollard ?离散对数算法 188
6.2.3 Pohlig-Hellman算法 190
6.2.4 指数演算法 193
6.3 通用算法的复杂度下界 194
6.4 有限域 197
6.5 椭圆曲线 201
6.5.1 实数上的椭圆曲线 201
6.5.2 模素数的椭圆曲线 203
6.5.3 椭圆曲线的性质 206
6.5.4 点压缩与ECIES 206
6.5.5 计算椭圆曲线上的乘积 208
6.6 实际中的离散对数算法 210
6.7 ElGamal体制的安全性 211
6.7.1 离散对数的比特安全性 211
6.7.2 ElGamal体制的语义安全性 214
6.7.3 Diffie-Hellman问题 215
6.8 注释与参考文献 216
习题 217
第7章 签名方案 222
7.1 引言 222
7.2 签名方案的安全性需求 224
7.2.1 签名和Hash函数 225
7.3 ElGamal签名方案 226
7.3.1 ElGamal签名方案的安全性 228
7.4 ElGamal签名方案的变形 230
7.4.1 Schnorr签名方案 230
7.4.2 数字签名算法(DSA) 232
7.4.3 椭圆曲线DSA 234
7.5 可证明安全的签名方案 235
7.5.1 一次签名 235
7.5.2 全域Hash 238
7.6 不可否认的签名 241
7.7 fail-stop签名 245
7.8 注释与参考文献 248
习题 249
第8章 伪随机数的生成 252
8.1 引言与示例 252
8.2 概率分布的不可区分性 255
8.2.1 下一比特预测器 257
8.3 Blum-Blum-Shub生成器 262
8.3.1 BBS生成器的安全性 264
8.4 概率加密 268
8.5 注释与参考文献 272
习题 272
第9章 身份识别方案与实体认证 275
9.1 引言 275
9.2 对称密钥环境下的挑战-响应方案 277
9.2.1 攻击模型和敌手目标 281
9.2.2 交互认证 282
9.3 公钥环境下的挑战-响应方案 284
9.3.1 证书 285
9.3.2 公钥身份识别方案 285
9.4 Schnorr身份识别方案 287
9.4.1 Schnorr身份识别方案的安全性 290
9.5 Okamoto身份识别方案 293
9.6 Guillou-Quisquater身份识别方案 296
9.6.1 基于身份的身份识别方案 298
9.7 注释与参考文献 299
习题 299
第10章 密钥分配 303
10.1 引言 303
10.2 Diffie-Hellman密钥预分配 306
10.3 无条件安全的密钥预分配 307
10.3.1 Blom密钥预分配方案 307
10.4 密钥分配模式 313
10.4.1 Fiat-Naor密钥分配模式 315
10.4.2 Mitchell-Piper密钥分配模式 316
10.5 会话密钥分配方案 319
10.5.1 Needham-Schroeder方案 320
10.5.2 针对NS方案的Denning-Sacco攻击 321
10.5.3 Kerberos 321
10.5.4 Bellare-Rogaway方案 324
10.6 注释与参考文献 326
习题 327
第11章 密钥协商方案 330
11.1 引言 330
11.2 Diffie-Hellman密钥协商 330
11.2.1 端-端密钥协商方案 332
11.2.2 STS的安全性 332
11.2.3 已知会话密钥攻击 335
11.3 MTI 密钥协商方案 336
11.3.1 关于MTI/A0的已知会话密钥攻击 339
11.4 使用自认证密钥的密钥协商 341
11.5 加密密钥交换 344
11.6 会议密钥协商方案 346
11.7 注释与参考文献 348
习题 349
第12章 公开密钥基础设施 351
12.1 引言：PKI简介 351
12.1.1 一个实际协议：安全套接层SSL 353
12.2 证书 354
12.2.1 证书生命周期管理 355
12.3 信任模型 356
12.3.1 严格层次模型 356
12.3.2 网络化PKI模型 357
12.3.3 Web浏览器模型 359
12.3.4 Pretty Good Privacy(PGP) 359
12.4 PKI的未来 361
12.4.1 PKI的替代方案 361
12.5 基于身份的密码体制 362
12.5.1 基于身份的Cock加密方案 363
12.6 注释与参考文献 367
习题 368
第13章 秘密共享方案 370
13.1 引言：Shamir门限方案 370
13.1.1 简化的(t, t)门限方案 373
13.2 访问结构和一般的秘密共享 374
13.2.1 单调电路构造 375
13.2.2 正式定义 379
13.3 信息率和高效方案的构造 382
13.3.1 向量空间构造 383
13.3.2 信息率上界 389
13.3.3 分解构造 392
13.4 注释与参考文献 395
习题 396
第14章 组播安全和版权保护 398
14.1 组播安全简介 398
14.2 广播加密 398
14.2.1 利用Ramp方案的一种改进 406
14.3 组播密钥重建 409
14.3.1 “黑名单”方案 410
14.3.2 Na

译 者 序
2002年我组织相关专家翻译了Douglas R. Stinson所著的《密码学原理与实践》一书的第二版，本书翻译出版后在国内密码学界产生了很大的影响，反应很好。凭我自己的学习经验，要掌握好一门课程，必须精读一两本好书，我认为本书是值得精读的一本。2008年年初，电子工业出版社委托我翻译Douglas R. Stinson所著的《密码学原理与实践》一书的第三版，我通读了一遍本书，发现本书的前7章与第二版的几乎一样，只有细微差异，但新增加了7章内容，这些内容都很基础也很新颖，我受益匪浅，于是我花了大量时间翻译了本书，以供密码学爱好者参考。
本书是一本很有特色的教科书，具体表现在以下6个方面：
1．表述清楚。书中所描述的问题浅显易懂，如分组密码的差分分析和线性分析本是很难描述的问题，本书中以代替置换网络(SPN)作为数学模型表述得很清楚。
2．论证严谨。书中对很多密码问题如**解距离、Hash函数的延拓准则等进行了严格的数学证明，有一种美感。
3．内容新颖。书中从可证明安全的角度对很多密码问题特别是公钥密码问题进行了清楚的论述，使用了谕示器(Oracle)这一术语，通过阅读本书可使读者能够掌握这一术语的灵魂。书中对一些**领域，如组播安全、数字版权保护等也做了相应的介绍。
4．选材精良。书中选择一些典型的、相对成熟的素材进行重点介绍，对一些正在发展的方向或需要大量篇幅介绍的内容以综述或解释的方式进行处理，特别适合于各种层次的教学使用。
5．覆盖面广。几乎覆盖了密码学的所有核心领域以及部分前沿内容，通过阅读本书可以了解密码学的全貌。
6．习题丰富。书中布置了大量的习题，通过演练这些习题可以熟练掌握密码学的基本技巧。
本书在翻译过程中，得到了很多老师的协助，张斌副研究员协助翻译了第8章、徐静副教授协助翻译了第9章、张振峰副研究员协助翻译了第10章、陈华副研究员协助翻译了第11章、张立武副研究员协助翻译了第12章、林东岱研究员协助翻译了第13章、赵险峰副研究员协助翻译了第14章，全书由我统一统稿。没有他们的鼎力相助，本书决不会这么快问世，在此对他们表示衷心的感谢。
本书的出版得到了国家973项目(编号：2007CB311202)和国家自然科学基金(编号：60673083)的支持，在此表示感谢。

冯登国
2008年夏于北京
前 言
本书的**版出版于1995年，共包含13章内容。**版的编写目标是编写一本关于密码学所有核心领域以及部分前沿内容的通用教材。在编写过程中，我尽力使本书的内容能够适应密码学相关各种课程的要求，使其可用于数学、计算机和各工程专业的大学生和研究生课程。
本书的第二版出版于2002年，内容集中于更适合在课程中介绍的密码学核心领域的内容。与**版相反，第二版只包含7章。我当时的目的是编写一本随身手册，包含**版各章节更新后的内容，也有介绍新内容的章节。
然而，在撰写第三版时，我改变了计划，决定编写一本扩充内容的第三版。第三版内容的广度和范围更类似于**版，不过大部分内容都经过完全重写。这个版本适当更新了第二版7章中的内容，并新加入了另外7章的内容。下面是这本《密码学原理与实践》第三版总共14章的简要大纲：
? 第1章对简单的“经典”密码体制做了基本的介绍。这一章也介绍了本书中使用的基本数学知识。
? 第2章介绍了Shannon对密码学研究的主要内容。包括完善保密性和熵的概念，以及信息论在密码学中的应用。
? 第3章关注的是分组密码。使用了代替置换网络(SPN)作为数学模型来介绍现代分组密码设计和分析的很多概念，包括差分和线性分析，并侧重于介绍基本原理。使用两个典型的分组密码(DES和AES)来阐述这些基本原理。
? 第4章统一介绍了带密钥和不带密钥的Hash函数，以及它们在构造消息认证码方面的应用，侧重于数学分析和安全性验证。本章还包括了安全Hash算法(SHA)的介绍。
? 第5章是关于RSA密码体制，以及大量数论背景知识的介绍，如素性检测和因子分解。
? 第6章讨论了公钥密码体制，如基于离散对数问题的ElGamal密码体制。另外还有一些关于计算离散对数、椭圆曲线和Diffie-Hellman问题的内容。
? 第7章介绍的是数字签名方案。介绍了很多具体方案，如数字签名算法(DSA)，还包括了一些特殊类型的签名方案，如不可否认、fail-stop签名方案等。
? 第8章包含了密码学中的伪随机比特生成器。本章基于**版的相关章节。
? 第9章是关于身份识别(实体认证)。本章**部分讨论了从简单的密码本原(primitive)，如数字签名方案或消息认证码构造的方案。第二部分在**版内容的基础上介绍了特殊目的的“零知识”方案。
? 第10章和第11章讨论了各种不同的密钥建立方法。第10章是关于密钥分配，第11章介绍了密钥协商协议。这两章的内容比**版内容丰富了很多(第二版不包含密钥建立的内容)。这两章比以前更加侧重于安全模型和证明。
? 第12章对公钥基础设施(PKI)做了总体的介绍，同时也讨论了与PKI拥有同样作用的基于身份的密码学。这是一个全新的章节。
? 第13章的主题是秘密共享方案。本章内容基于**版的相应章节。
? 第14章是一个全新的章节，讨论了组播安全。包括广播加密和版权保护。
下面是本书所有版本的特点：
? 所有需要相应数学背景知识的地方都有很及时的介绍。
? 对密码体制非正式的描述都附带伪代码。
? 使用了很多例子来阐述本书中大多数的算法。
? 各算法和密码体制的数学基础都有很严格、很仔细的解释。
? 本书包含了很多习题，其中一些相当具有挑战性。
我相信这些特点使得本书用于课堂讲授和自学都更加有用。
在本书中，尽量按照符合逻辑的、自然的顺序安排书中的内容。有时读者有可能为了集中了解后面的某一内容而跳过前面的章节。不过有几章的内容确实非常依赖前面的章节。下面是一些重要的依赖关系：
? 第9章使用了第4章(消息认证码)和第7章的内容(数字签名方案)。
? 第13章的13.3.2节使用了第2章关于熵的结论。
? 第14章使用了第10章(密钥预分配)和第13章(秘密共享)的内容。
还有很多地方，前面章节介绍的数学工具会用到后面的章节里，但是应该不会造成课堂讲授的困难。
决定介绍多少数学基础知识，是编写任何一本密码学书籍*困难的事情之一。密码学是一个涉及面广的学科，需要若干数学领域的知识，如数论、群环域理论、线性代数、概率论和信息论。同样也需要熟悉计算复杂度、算法和NP问题。在我看来，数学知识不够是很多学生在刚开始学习密码学时遇到困难的原因。
本书中尽量介绍遇到的数学背景知识，在大多数时候，都会详细介绍用到的数学工具。但是如果读者对基本的线性代数和模运算有一定了解的话，是非常有帮助的。
很多人指出了第二版和第三版草稿中的错误，并对加入的新内容的选择和内容的广度提出了有用的建议。特别要感谢Carlisle Adams，Eike Best，Dameng Deng，Shuhong Gao，K.Gopalakrishnan，Pascal Junod，Torleiv Kl?ve，Jooyoung Lee，Vaclav Matyas，Michael Monagan，James Muir，Phil Rose，Tamir Tassa和Rebecca Wright。与往常一样，希望大家能够用勘误表的方式通知我，我会把它们放在一个网页上。

Douglas R. Stinson
于加拿大安大略省滑铁卢市