现代密码学及其应用

本书阐述了密码学的发展历史，重点介绍了密码学的基本概念、基本理论和基本方法以及常用具体算法。首先，本书对密码学所需的数论、抽象代数和信息论等预备知识进行了详细叙述，并介绍了非对称密码体制（公钥密码学）中的经典算法RSA、Elgamal、Rabin、Diffie–Hellman密钥交换协议等。在此基础上，依次介绍了安全通信要用到的对称密码（分组密码和流密码）与散列函数及其常用算法和分析方法。后，本书以一半的篇幅详细介绍了安全通信所涉及的公钥密码学新成果，包括椭圆曲线密码、超椭圆曲线密码、双线性对密码、格密码等，并简要介绍了安全与鉴别密码协议。本书可作为密码学和信息安全方向的本科生和研究生教材，也可供密码学和信息安全方向的广大科技工作者参考。

理查德 E. 布拉胡特（Richard E. Blahut）

美国工程院院士、IEEE香农奖获得者、伊利诺伊大学香槟分校（UIUC）电气与计算机工程系荣休教授。他于1972年获得康奈尔大学电气工程博士学位，曾先后在康奈尔大学、普林斯顿大学、瑞士联邦理工学院和伊利诺伊大学香槟分校任教。他在1990年当选美国工程院院士，1981年当选IEEE Fellow，主要研究领域有编码理论与应用、通信、计算机成像系统、光通信和信号处理，曾获1998年IEEE贝尔奖（IEEE Alexander Granham Bell Medal）、IEEE 第三次千禧奖章 (IEEE Third Millennium Medal)、2005年IEEE香农奖（IEEE Claude E. Shannon Award）等。

目　录
Cryptography and Secure Communication

出版者的话
译者序
前言
致谢
第1章　概述1
　1.1　经典密码学1
　1.2　密码保密的概念3
　1.3　分组密码5
　1.4　流密码7
　1.5　公钥密码学8
　1.6　迭代与级联密码9
　1.7　密码分析学10
　1.8　现实攻击11
　1.9　复杂度理论12
　1.10　认证与鉴别13
　1.11　所有权保护14
　1.12　隐蔽通信15
　1.13　信息保护史16
　第1章习题17
　第1章注释18
第2章　整数20
　2.1　数论基础20
　2.2　欧几里得算法23
　2.3　素数域25
　2.4　平方剩余26
　2.5　二次互反性30
　2.6　雅可比符号32
　2.7　素性检验35
　2.8　费马算法36
　2.9　Solovay-Strassen算法37
　2.10　Miller-Rabin算法39
　2.11　整数分解41
　2.12　Pollard因子分解算法42
　2.13　素数域上的平方根43
　第2章习题48
　第2章注释50
第3章　基于整数环的密码学51
　3.1　双素数密码51
　3.2　双素数密码的实施52
　3.3　双素数密码的协议攻击54
　3.4　双素数加密的直接攻击55
　3.5　双素数因子分解56
　3.6　平方筛选法56
　3.7　数域筛选法60
　3.8　Rabin密码体制62
　3.9　背包密码体制的兴衰64
　第3章习题65
　第3章注释66
第4章　基于离散对数的密码学67
　4.1　Diffie-Hellman密钥交换67
　4.2　离散对数68
　4.3　Elgamal密码体制69
　4.4　陷门单向函数70
　4.5　Massey-Omura密码体制70
　4.6　Pohlig-Hellman算法71
　4.7　Shanks算法75
　4.8　离散对数的Pollard算法77
　4.9　指数计算方法79
　4.10　离散对数问题的复杂度81
　第4章习题83
　第4章注释83
第5章　密码学中的信息论方法85
　5.1　概率空间85
　5.2　熵86
　5.3　理想保密87
　5.4　Shannon-McMillan定理89
　5.5　解距离90
　5.6　自然语言的熵92
　5.7　熵扩展93
　5.8　数据压缩94
　5.9　窃听信道95
　第5章习题98
　第5章注释99
第6章　分组密码100
　6.1　分组代换100
　6.2　Feistel网络101
　6.3　数据加密标准102
　6.4　数据加密标准的使用105
　6.5　双重和三重DES加密105
　6.6　高级加密标准106
　6.7　差分密码分析109
　6.8　线性密码分析110
　第6章习题110
　第6章注释111
第7章　流密码112
　7.1　依赖状态的加密112
　7.2　加法流密码113
　7.3　线性移位寄存器序列115
　7.4　线性复杂度攻击117
　7.5　线性复杂度分析118
　7.6　非线性反馈产生的密钥流120
　7.7　非线性组合产生的密钥流121
　7.8　非线性函数产生的密钥流123
　7.9　相关性攻击128
　7.10　伪随机序列130
　7.11　序列的非线性集131
　第7章习题133
　第7章注释134
第8章　认证与所有权保护135
　8.1　认证135
　8.2　鉴别136
　8.3　认证签名136
　8.4　散列函数138
　8.5　生日攻击140
　8.6　迭代散列构造141
　8.7　理论散列函数141
　8.8　实用散列函数142
　第8章习题146
　第8章注释147
第9章　群、环与域148
　9.1　群148
　9.2　环150
　9.3　域151
　9.4　素数域153
　9.5　二进制域与三进制域153
　9.6　一元多项式154
　9.7　扩张域159
　9.8　有限域上的乘法循环群163
　9.9　分圆多项式165
　9.10　向量空间167
　9.11　线性代数169
　9.12　傅里叶变换170
　9.13　有限域的存在性173
　9.14　二元多项式176
　9.15　模数约简与商群179
　9.16　一元多项式分解180
　第9章习题182
　第9章注释184
第10章　基于椭圆曲线的密码学185
　10.1　椭圆曲线185
　10.2　有限域上的椭圆曲线189
　10.3　点的加法运算191
　10.4　椭圆曲线的阶数194
　10.5　椭圆曲线的群196
　10.6　超奇异椭圆曲线197
　10.7　二进制域上的椭圆曲线199
　10.8　点的乘法计算201
　10.9　椭圆曲线密码学202
　10.10　投影平面204
　10.11　扩张域上的点计数206
　10.12　有理数上椭圆曲线的同态映射210
　10.13　有限域上椭圆曲线的同态213
　10.14　基域上的点计数217
　10.15　Xedni（仿指数）计算方法220
　10.16　椭圆曲线与复数域223
　10.17　采用复数乘法构造的曲线225
　第10章习题231
　第10章注释233
第11章　基于超椭圆曲线的密码学235
　11.1　超椭圆曲线235
　11.2　坐标环和函数域238
　11.3　极根和零根240
　11.4　约数242
　11.5　主约数244
　11.6　椭圆曲线上的主约数246
　11.7　雅可比商群249
　11.8　超椭圆曲线的群250
　11.9　半简化约数和雅可比商群252
　11.10　Mumford变换253
　11.11　Cantor约简算法257
　11.12　简化约数和雅可比商群259
　11.13　Cantor-Koblitz算法260
　11.14　超椭圆曲线密码学263
　11.15　超椭圆雅可比商群的阶264
　11.16　一些雅可比商群的例子265
　第11章习题268
　第11章注释269
第12章　基于双线性对的密码学270
　12.1　双线性对270
　12.2　基于配对的密码学271
　12.3　基于配对的密钥交换272
　12.4　基于身份的加密273
　12.5　基于配对的签名275
　12.6　攻击双线性

前　言Cryptography and Secure Communication信息传输和信息保护就像是同一幅织锦的两面，但信息保护有着更为错综复杂的多重纹路。信息保护学科的核心就是经典密码学中特有的主题，即保护消息的内容避免被未授权的接收者所理解，但不以其他方式来保护消息。本书大部分内容专注于古典意义上的密码学，但用现代先进的方式来探讨。现代密码学与信息保护总体上是一个由数学、工程、信息与计算机科学组成的迷人交叉学科，这些交叉可以在本书中找到。
信息保护学科正在迅速演变，它远远超越了点对点密码学中的古典观念。当前大型公共网络对保密与安全有强烈的需求。在公共网络通信的大背景下，还有很多其他重要问题，包括授权、证书和认证等问题，这为讨论中带来了很多需要考虑的微妙因素。虽然本书的重点是密码学，但也同样涉及这些问题。同我的其他书一样，我的目标集中于讨论这些形式化的、可能永恒的问题，而不是现用系统的细节。虽然本书没有编写成一本手册来描述当前标准密码体制，但有些主题通过讨论现用的实际系统进行了好的描述。
现代密码学采用了大量源自数论、抽象代数和代数几何等科目的高等数学资料。我相信，一个人如果对这些资料没有一定的理解，不可能成为密码学学科的专家。因此，本书对所有相关的数学主题进行了正式且严谨的探讨，但简化了描述以适应目前的需求。
本书由一个工程师而非密码学者编写，是写给那些特别想要在一定程度上深入了解信息保护学科的工程师们。虽然我承认这样做有一定风险，但也希望会有积极的教学意义。作为这个学科的外行，我能更容易地看出那些对专家显而易见而对新手却难以理解的知识点，而这些知识需要更细心地对待。但是，同时我也坚信密码学的工科生不应该缩手缩脚。尽管工程师的起始背景可能不同于一个数学家，但他能够且应该理解主要的数学知识，而不要以为任何基本原理都是理所当然的。
在写这本书时，有时我不得不按自己的方式来达到所需的结果，而这超越了我的常规教育。为此，本书以目标为中心，直接深入展开，但不失严谨性。我希望这样一本由非专业人士编写的科技书籍会适合普通技术教育读者。
当然，很多现代密码学的软肋是复杂度问题，但这个主题在本书中没有详细讨论。呈现给对手的计算问题貌似复杂难解，这样秘密就得到了保护。计算复杂难解的证据往往只是传闻。众所周知的形式化论述是经过检验的，并往往只能间接应用。关于复杂度的描述通常指的是渐近复杂度，这是理论意义上的，但可以与实例问题的实际复杂度有很大不同。由于我们倾向于在本书中尽量避免无证据的论断，所以很多关于复杂度的表述通常只出现在一般术语中，或者在章末注释中。
本书讨论了古典和现代密码学的很多专业概念，甚至讨论了一些过时的或者不足信的技术，因为它们对本学科的历史和文化很重要。这些思想有助于理解本书，并可能引领未来的发展。
许多不同的数学科目构成了密码学学科的基础，这部分内容将在第9章介绍，而在第2章将介绍数论的相关内容。背景材料放到第9章再介绍有助于塑造本书的风格，但有时需要提前参考第9章的定义和定理。本书的前半部分（第1～8章）讨论经典密码学和公钥密码学的早期基本方法，这些主要是基于数论的。本书前半部分所需的数学主要是数论，以及群论的基本概念，这在第2章中就展开论述了。第3章和第4章探讨了公钥密码学。第5章探讨了信息论问题，第6章和第7章探讨了传统的分组密码和流密码，第8章涵盖了消息认证。
本书中间的第9章，简要总结了后面几章所需的数学，前面几章偶尔也需要。本书的后半部分也需要其他高等数学的知识，特别是代数几何的概念。这些主题的绝大部分在需要用到的地方展开论述。特别地，第10～12章讨论基于椭圆和超椭圆曲线的密码学，包括配对方法。后3章圆满完成了本书。第13章讨论实际的实施问题。第14章讨论了身份鉴别，而第15章讨论了基于格和基于编码的密码学。大部分的处理是自成一体的，或者说是有这样的目的。
本书所讲述的数学成熟、美丽而优雅，在某些方面与信号处理的工程数学相关，但是它更高级，并用自己的语言来表述。也许其中一些理论有一天将进入工程师的日常工具箱。
致　谢Cryptography and Secure Communication这本书开始于一套未编辑的讲义笔记，源自1999年我和Nigel Boston教授一起讲授的密码学课程，并于2003年和2005年同Iwan Duursma教授一起重新教该课。这些早期讲义笔记只是把讲座作为班级学生的助学工具，试图把问题阐述清楚，并帮助我自己理解相关数学内容。由于当时有许多草率未完的边角工作，这些笔记并不适于全面发行。2009年到2011年，当我主要面向工科学生单独讲授该课程时，继续完善和修订了这些笔记，终完成当前这本书。
我对数学主题有更深层次的理解，要感谢与Boston在课堂内外的共享时光，以及与Duursma的互动。没有这些亲密合作，我不可能加深对这些内容的理解。虽然我确实感谢他们给我带来了这个新的兴趣点，但我也责怪他们让我来担负起一个新的嗜好。还要感谢与Ian Blake和Jim Massey的长期友谊，这两个人就像