应用密码学
前言
世界上有两种密码：一种是防止你的小妹妹看你的文件；另一种是防止当局者阅读你的文件资料。这本书写的是后一种情况。
如果把一封信锁在保险柜中，把保险柜藏在纽约的某个地方…，然后告诉你去看这封信。这并不是安全，而是隐藏。相反，如果把一封信锁在保险柜中，然后把保险柜及其设计规范和许多同样的保险柜给你，以便你和世界上最好的开保险柜的专家能够研究锁的装置。而你还是无法打开保险柜去读这封信，这样才是安全的。
许多年来，这种密码学是军队独家专有的领域。美国国家安全局以及前苏联、英国、法国、以色列及其它国家的安全机构已将大量的财力投入到加密自己的通信，同时又千方百计地去破译别人的通信的残酷游戏之中，面对这些政府，个人既无专门知识又无足够财力保护自己的秘密。
在过去20年里，公开的密码学研究爆炸性地增长。从二次世界大战以来，当普通公民还在长期使用经典密码时，计算机密码学成为世界军事的独占领域。今天，最新的计算机密码学已应用到军事当局的高墙之外，现在非专业人员都可以利用密码技术去阻止最强大的敌人，包括军方的安全机构。
平头百姓真的需要这种保密性吗？是的，他们可能正策划一次政治运动，讨论税收或正干一件非法的事情；他们也可能正设计一件新产品，讨论一种市场策略，或计划接管竞争对手的生意，或者，他们可能生活在一个不尊重个人隐私权的国家，也可能做一些他们自己认为并非违法实际却是非法的事情。不管理由是什么，他的数据和通信都是私人的、秘密的，与他人无关。
这本书正好在混乱的年代发表。1994年，克林顿当局核准了托管加密标准（包括Clipper芯片和Fortezza卡），并将数字电话法案签署成为法律。这两个行政令企图确保政府实施电子监控的能力。
一些危险的Orwellian假设在作祟：即政府有权侦听私人通信，个人对政府保守秘密是错误的，如果可能，法律总有能力强制实施法院授权的监控，但是，这是公民第一次被强迫采取积极措施，以使他们自己能被监控。这两个行政令并不是政府在某个模糊范围内的简单倡议，而是一种先发制人的单方面尝试，旨在侵占以前属于人民的权力。
Clipper和数字电话不保护隐私，它强迫个人无条件地相信政府将尊重他们的隐私。非法窃听小马丁·路德·金电话的执法机构，同样也能容易地窃听用Clipper保护的电话。最近，地方警察机关在好些管区内都有因非法窃听而被控有罪或被提出民事诉讼的，这些地方包括马里兰、康涅狄格、佛蒙特、佐治亚、密苏里和内华达。为了随时方便警察局的工作而配置这种技术是很糟糕的想法。
这儿给我们的教训是采用法律手段并不能充分保护我们自己，我们需要用数学来保护自己。加密太重要了，不能让给政府独享。
本书为你提供了一些可用来保护自己隐私的工具。提供密码产品可能宣布为非法，但提供有关的信息绝不会犯法。
怎样读这本书？
我写《应用密码学》一书是为了在真实介绍密码学的同时给出全面的参考文献。我尽量在不损失正确性的情况下保持文本的可读性。这本书不想成为一本数学书。虽然我无意给出任何错误信息，但匆忙中理论难免有失严谨。对形式方法感兴趣的人，可以参考大量的学术文献。
第一章介绍了密码学，定义了许多术语，简要讨论了计算机出现前密码学的情况。
第一篇（第二~六章）描述密码学的各种协议：人们能用密码学做什么。协议范围从简单（一人向另一人发送加密消息）到复杂（在电话上抛掷硬币）再到深奥的（秘密的和匿名的数字货币交易）。这些协议中有些一目了然，有些却十分奇异。密码术能够解决大多数人绝没有认识到的许多问题。
第二篇（第7~10章）讨论密码技术。对密码学的大多数基本应用来说，这一部分的四章都是很重要的。第七章和第八章讨论密钥：密钥应选多长才能保密，怎样产生、存储密钥，怎样处理密钥等等。密钥管理是密码学最困难的一部分，经常是保密系统的一个致命弱点；第九章讨论了使用密码算法的不同方法；第十章给出了与算法有关的细节：怎样选择、实现和使用算法。
第三篇（第9~23章）列出了多个算法。第11章提供了数学背景，如果你对公开密钥算法感兴趣，这一章是需要了解的。如果你只想实现DES（或类似的东西），你可以跳过这一章；第12章讨论DES：DES算法、它的历史、它的安全性和它的一些变形；第13、14、15章讨论其它的分组算法。如果你需要比DES更保密的算法，请阅读IDEA和三重DES算法这节。如果你想阅读一系列比DES算法更安全的算法，就请读完整章；第16、17章讨论序列密码算法；第18章集中讨论单向hash函数；虽然讨论了好些单向hash函数，但MD5和SHA是最通用的；第19章讨论公开密钥加密算法。第20章讨论了公开密钥数字签名算法；第21章讨论了公开密钥鉴别算法；第22章讨论了公开密钥密钥交换算法。几种重要的公开密钥算法分别是RSA、DSA、Fiat-Shamir和Diffie-hellman算法；第23章有更深奥的公开密钥算法和协议。这一章的数学知识是非常复杂的，请系好你的安全带。
第四篇（第24~25章）转向密码学的真实世界。第24章讨论这些算法和协议的一些实际实现；第25章接触到围绕密码学的一些政治问题，这些章节并不全面。
此外，书中还包括在第三篇中讨论的10个算法的源代码清单，由于篇幅的限制，我不可能涉及所有的源代码，况且，密码的源代码不能出口（非常奇怪的是，国务院允许本书的第一版和源代码出口，但不允许含有同样源代码的计算机磁盘的出口）。配套的源代码盘包括的源代码比本书中列出的要多得多；这也许是除军事机构以外的最大的密码源代码集。我只能发送源代码盘给住在美国和加拿大的美国和加拿大公民，但我希望有一天这种情况会改变。如果你对这本书的实现或密码算法均感兴趣的话，设法得到这个磁盘。详细情况请看本书的最后一页。
对这本书的一种批评，是它的广博性代替了可读性。这是对的，但我想给可能是偶然在学术文献或产品中需要一个算法的人提供一个参考。对于那些对教材更感兴趣的人，我只能抱歉。密码学领域正日趋热门，这是第一次把这么多资料收集在一本书中。即使这样，还是有许多东西限于篇幅舍弃了，我尽量保留了那些我认为是重要的、有实用价值的或者是有趣的专题，如果我对某一专题讨论不深，我会给出深入讨论这些专题的参考文献。
笔者在写作过程中已尽力查出和根除书中的错误，但我相信不可能消除所有的错误。第二版肯定比第一版的错误少得多。谌误表可以从我这里得到，并且它被定期发往Usenet的新闻组sci.crypt。如果读者发现错误，请通知我，我将向发现每个错误的第一个人免费寄送一张源码盘，以示感谢。
致谢
为本书提供帮助的人真是数不胜数，他们都值得提及。我谨感谢Don Alvarez, Ross Anderson, Dave Balenson, Karl Barrus, Steve Bellovin, Dan Bernstein, Eli Biham, Joan Boyar, Karen Cooper, Whit Diffie, Joan Feigenbaum, Phil Karn, Neal Kobitz, Xuejia Lai, Tom Leranth, Mike Markowitz, Ralph Merkle, Bill Patton, Peter Pearson, Charles Pfleegar, Ken Pizzini, Bart Preneel, Mark Riordan, Joachim Schurman和Marc Schwartz感谢他们对本书第一版的审阅和校订。感谢Marc Vauclair将它译成法文。感谢Abe Abraham, Ross Anderson, Dave Banisar, Steve Bellovin, Eli Biham, Matt Bishop, Matt Blaze, Gary Carter, Jan Camenisch, Claude Crepeau, Joan Daemen, Jorge Davila, Ed Dawson, Whit Diffie, Carl Ellison, Joan Feigenbaum, Niels Ferguson, Matt Franklin, Rosario Gennaro, Dieter Gollmann, Mark Goresky, Richard Graveman, Stuart Haber, Jingman He, Bob Hogue, Kenneth Iversen, Markus Jakobsson, Burt Kaliski, Phil Karn, John Kelsey, John Kennedy, Lars Knudsen, Paul Kocher, John Ladwig, Xuejia Lai, Arjen Lenstra, Paul Leyland, Mike Markowitz, Jim Massey, Bruce McNair, William Hugh Murray, Roger Needham, Clif Neuman, Kaisa Nyberg, Luke O’Connor, Peter Pearson, Rene Peralta, Bart Preneel, Yisrael Radai, Matt Robshaw, Michael Roe, Phil Rogaway, Avi Rubin, Paul Rubin, Selwyn Russell, Kazue Sako, Mahmoud Salmasizadeh, Markus Stadler, Dmitry Titov, Jimmy Upton, Marc Vauclair, Serge Vaudenay, Gideon Yuval, Glen Zorn和其它不愿透露姓名的政府官员们对第2版的审阅和校订。感谢Lawrie Brown, Leisa Condie, Joan Daemen, Peter Gutmann, Alan Insley, Chris Johnston, John Kelsey, Xuejia Lai, Bill Leininger, Mike Markowitz, Richard Outerbridge, Peter Pearson, Ken Pizzini, Colin Plumb, RSA Data Security, Inc.,Michael Wood和Phil Zimmermann提供的源代码。感谢Paul MacNerland为第一版制图；Karen Cooper为第二版排版；Beth Friedman为第二版核对；Carol Kennedy为第二版做索引；sci.crypt和Cypherpunks邮件列表的读者们在主意、答问和谌误方面的支持；Randy Seuss提供的Internet接入；Jeff Duntemann和Jon Erickson给我鼓励、支持、交谈和友情和食粮让我动手写作；还要感谢AT&T公司开除我，使这一切成为可能。没有这些人的帮助，仅靠我个人是不可能写出好书的。
B.施柰尔
作者简介：
BRUCE SCHNEIER是Counterpane Systems公司的总裁，该公司位于伊利诺依州的Oak公园，是一个密码学和计算机安全方面的专业咨询公司。Bruce还是《电子邮件安全》(E-Mail Security
目录
序 I
W.迪菲(Whitfield Diffie) I
前 言 IV
怎样读这本书？ V
致谢 VI
作者简介 VII
第一章 基础知识 1
1.1 专业术语 1
1.2 隐写术 7
1.3 代替密码和换位密码 8
1.4 简单异或 11
1.5 一次一密乱码本 12
1.6 计算机算法 14
1.7 大数 14
第一篇 密码协议 16
第二章 协议结构模块 16
2.1 协议介绍 16
2.2 使用对称密码术的通信 21
2.3 单向函数 22
2.4 单向Hash函数 23
2.5 使用公开密钥密码术的通信 24
2.6 数字签名 26
2.7 带加密的数字签名 31
2.8 随机和伪随机序列的产生 33
第三章 基本协议 36
3.1 密钥交换 36
3.2 鉴别 40
3.3 鉴别和密钥交换 43
3.4 鉴别和密钥交换协议的形式分析 50
3.5 多密钥公开密钥密码学 53
3.6 秘密分割 54
3.7 秘密共享 55
3.8 数据库的密码保护 58
第四章 中级协议 59
4.1 时间戳服务 59
4.2 阈下信道 62
4.3 不可抵赖的数字签名 63
4.4 指定的确认者签名 64
4.5 代理签名 65
4.6 团体签名 65
4.7 失败-终止 数字签名 66
4.8 用加密数据计算 67
4.9 比特承诺 67
4.10 公平的硬币抛掷 69
4.11 智力扑克 72
4.12 单向累加器 75
4.13 秘密的全或无泄露 76
4.14 密钥托管 76
第五章 高级协议 79
5.1 零知识证明 79
5.2 身份的零知识证明 85
5.3 盲签名 87
5.4 基于身份的公钥密码 90
5.5 不经意传输 90
5.6 不经意签名 92
5.7 同时签约 92
5.8 数字证明邮件 95
5.9 秘密的同时交换 97
第六章 深奥的协议 98
6.1 保密选举 98
6.2 保密的多方计算 105
6.3 匿名报文广播 107
6.4 数字现金 109
第二篇 密码技术 116
第七章 密钥长度 116
7.1 对称密钥长度 116
7.2 公钥密钥长度 122
7.3 对称密钥和公钥密钥长度的比较 128
7.4 对单向Hash函数的生日攻击 128
7.5 密钥应该多长 128
7.6 总结 129
第八章 密钥管理 130
8.1 密钥生成 130
8.2 非线性密钥空间 135
8.3 发送密钥 135
8.4 验证密钥 137
8.5 使用密钥 138
8.6 更新密钥 139
8.7 存储密钥 139
8.8 备份密钥 140
8.9 泄露密钥 141
8.10 密钥有效期 141
8.11 销毁密钥 142
8.12 公开密钥的密钥管理 143
第九章 算法类型和模式 146
9.1 电子密码本模式 146
9.2 分组重放 147
9.3 密码分组链接模式 149
9.4 序列密码算法 152
9.5 自同步序列密码 154
9.6 密码反馈模式 155
9.7 同步序列密码 157
9.8 输出反馈模式 158
9.9 计数器模式 160
9.10 其他分组密码模式 161
9.11 选择密码模式 163
9.12 交错 164
9.13 分组密码算法与序列密码算法 165
第十章 使用算法 167
10.1 选择算法 167
10.2 公钥密码与对称密码 169
10.3 通信信道加密 169
10.4 加密数据存储 172
10.5 硬件加密与软件加密 174
10.6 压缩、编码、加密 176
10.8 密文中隐藏密文 177
10.9 销毁信息 178
第三篇 密码算法 180
第十一章 数学背景 180
11.1 信息论 180
11.2 复杂性理论 183
11.3 数论 187
11.4 因子分解 200
11.5 素数产生 202
11.6 有限域上的离散对数 205
第十二章 数据加密标准（DES） 207
12.1 背景 207
12.2 DES描述 210
12.3 DES的安全性 219
12.4 差分及线性分析 224
12.5 实际设计的准则 232
12.6 DES变形 232
12.7 DES现在的安全性如何？ 238
第十三章 其它分组密码算法 239
13.1 LUCIFER算法 239
13.2 MADEYGA算法 239
13.3 NewDES算法 241
13.4 FEAL算法 243
13.5 REDOC算法 247
13.6 LOKI算法 248
13.7 KHUFU和KHAFRE算法 250
13.8 RC2算法 252
13.9 IDEA算法 253
13.10 MMB算法 259
13.11 CA—1.1算法 260
13.12 SKIPJACK算法 261
第十四章 其它分组密码算法（续） 263
14.1 GOST算法 263
14.2 CAST算法 265
14.3 BLOWFISH算法 266
14.4 SAFER算法 269
14.5 3—WAY算法 271
14.6 CRAB算法 271
14.7 SXAL8/MBAL算法 273
14.8 RC5算法 273
14.9 其它分组密码算法 274
14.10 分组密码设计理论 274
14.11 使用单向散列函数的算法 278
14.12 分组密码算法的选择 281
第15章 组合的分组密码 283
15.1 双重加密 283
15.2 三重加密 284
15.3 加倍分组长度 288
15.4 其它一些多重加密方案 289
15.5 缩短CDMF密钥 291
15.6 白噪声 291
15.7 级联多重加密算法 291
15.8 组合多重分组算法 292
第十六章 伪随机序列发生器和序列密码 293
16.1 伪随机序列发生器 293
16.2 线性反馈移位寄存器 297
16.3 序列密码的设计与分析 304
16.4 使用LFSR的序列密码 305
16.5 A5 313
16.6 Hughes XPD/KPD 313
16.7 Nanoteq 314
16.8 Rambutan 314
16.9 附加式发生器 314
16.10 GIFFORD 316
16.11 M算法 317
16.12 PKZIP 318
第17章 其它序列密码和真随机序列发生器 320
17.1 RC4 320
17.2 SEAL 321
17.3 WAKE 322
17.4 带进位的反馈移位寄存器 323
17.5 使用FCSR的序列密码 329
17.6 非线性反馈移位寄存器 332
17.7 其它序列密码 333
17.8 序列密码设计的系统理论方法 334
17.9 序列密码设计的复杂性理论方法 335
17.10 序列密码设计的其它方法 336
17.11 多个序列密码的级联 337
17.12 序列密码的选择 337
17.13 从单个伪随机序列发生器生成多个序列 338
17.14 真随机序列产生器 339
第十八章 单向hash函数 344
18.1 背景 344
18.2 SNEFRU 346
18.3 N- hash 346
18.4 MD4 349
18.5 MD5 350
18.6 MD2 354
18.7 安全hash算法（SHA） 354
18.8 RIPE- MD 357
18.9 HAVAL 357
18.10 其它单向hash函数 358
18.11 使用对称分组算法的单向hash函数 358
18.12 使用公开密钥算法 365
18.13 单向hash函数的选择 365
18.14 消息鉴别码 366
第19章 公开密钥算法 370
19.1 背景 370
19.2 背包算法 371
19.3 RSA算法 374
19.4 POHLIG-HELLMAN算法 381
19.5 RABIN算法 381
19.6 ElGAMAL算法 383
19.7 McELIECE算法 385
19.8 椭圆曲线密码体制 386
19.9 LUC算法 386
19.10 有限自动机公开密钥密码体制 387
第二十章 公开密钥数字签名算法 389
20.1 数字签名算法(DSA) 389
20.2 DSA的变形 396
20.3 GOST数字签名算法 398
20.4 离散对数签名方案 399
20.5 ONG-SCHNORR-SHAMIR 401
20.6 ESIGN 401
20.7 细胞自动机 402
20.8 其它公开密钥算法 403
第21章 鉴别方案 405
21.1 FEIGE—FIAT—SHAMIR算法 405
21.2 GUILLOU—QUISQUATER算法 409
21.3 SCHNORR算法 411
21.4 身份识别方案转为数字签名方案 412
22.1 Diffie-Hellman 算法 413
22.2 站间协议 415
22.3 Shamir的三次传递协议 415
22.4 COMSET 416
22.5 加密的密钥交换 416
22.6 加强的密钥协商 420
22.7 会议密钥分发和秘密广播 420
23 协议的专用算法 423
23.1 多重密钥的公开密钥密码学 423
23.2 秘密共享算法 423
23.3 阈下信道 426
23.4 不可抵赖的数字签名 431
23.5 指定的确认者签名 433
23.6 用加密数据计算 434
23.7 公平的硬币抛掷 435
23.8 单向累加器 437
23.9 秘密的全或无泄露 437
23.10 公平和防错的密码体制 439
23.11 知识的零知识证明 440
23.12 盲签名 442
23.13 不经意传输 443
23.14 保密的多方计算 443
23.15 概率加密 444
23.16 量子密码学 446
第四篇 真实世界 449
24 实现方案范例 449
24.1 IBM秘密密钥管理协议 449
24.2 MITRENET 450
24.3 ISDN 450
24.4 STU-Ⅲ 452
24.5 KERBEROS 452
24.6 KRYPTOKNIGHT 457
24.7 SESAME 457
24.8 IBM 通用密码体系 458
24.9 ISO鉴别框架 459
24.10 保密性增强邮件（PEM） 462
24.11 消息安全协议（MSP） 467
24.12 PRETTY GOOD PRIVACY（PGP） 467
24.13 智能卡 469
24.14 公开密钥密码学标准（PKCS） 470
24.15 通用的电子支付系统（UEPS） 471
26.16 CLIPPER 473
24.17 CAPSTONE 475
24.18 AT&T 3600型电话保密设备（TSD） 475
25 政治 476
25.1 国家安全局（NSA） 476
25.2 国家计算机安全中心（NCSC） 477
25.3 国家标准技术所（NIST） 478
25.4 RSA数据安全有限公司 481
25.5 公开密钥合作者 481
25.6 国际密码研究协会（IACR） 482
25.7 RACE 完整性基本评估（RIPE） 483
25.8 对欧洲的有条件访问（CAFE） 483
25.9 ISO/IEC 9979 484
25.10 专业人员、公民自由及产业性组织 484
25.11 Sci. Crypt 485
25.12 Cypherpunks 485
25.13 专利 486
25.14 美国出口法规 486
25.15 其他国家的密码进出口 491
25.16 合法性问题 492
Matt Blaze 跋 493
第五篇 源代码 495
1. DES 495
2. LOK191 505
3. IDEA 510
4. GOST 516
5. BLOWFISH 520
6. 3-Way 529
7. RC5 535
8. A5 539
9. SEAL 545
References 553