本书着重介绍现代密码学的加密思想及其实现方法，内容涉及数论、概率论、抽象代数、加密算法的思想及复杂度理论。本书介绍了密码学的历史沿革，剖析了古典的加密算法为何会被现代的加密算法所取代，展望了密码编码领域的发展，为古典和现代密码体系提供了数学理论基础，还给出了一些针对各种加密算法的密码分析方法。
本书适合作为高校计算机安全与信息安全专业密码学导论的简明教材，也可供对密码学、数论和计算机数论有兴趣的技术人员参考。
本书主要内容包括
·介绍密码学的历史沿革，剖析古典的加密算法为何会被现代的加密算法所取代
·古典和现代密码学体系的数学理论基础
·各种加密算法的密码分析方法
·展望密码编码领域的未来
作者简介：
PaulGarrett 1973年21岁时获普渡大学硕士学位，1977年于普林斯顿大学获博士学位，之后在耶鲁大学任教。1979～1981年在加州大学伯克利分校获得美国国家科学基金会资助的博士后奖学金，1979年成为斯坦福大学副教授，自1982年起，Paul
Garrett开始在明尼苏达大学授课，1987年成为该校教授，目前他是该校数学系研究生教学主任，指导着13位博士。Paul Garrett主要的研究方向是数论，并由此而对密码学、计算及算法产生了兴趣。著有《Holomorphic
Hilbert Modular Forms》、《Buildings and ClassicaI Groups》，以及两本密码学教材。
PauI Garrett欢迎读者们访问他的本人网址http://www.math.umn.edu/garrett/，并希望能跟志同道合者深入探讨和研究。
吴世忠：博士、研究员，中国信息安全产品测评认证中心主任。现为全国信息安全标准化技术委员会副主任，中国信息产业商会信息安全产业分会理事长，《信息安全与通信保密》杂志主编。
已公开出版文章百余篇，著有《信息系统的互连与互通》、《C31系统的安全与保密》、《关贸总协定：中国准备好了吗?》、《首都信息化标准指南·信息安全与保密标准化体系》等专著五部和《应用密码学》、《网络信息安全的真相》、《密码学的理论和实践》、《中文Windows2000的安全性》等译著五部，同时还主持起草了防火墙、应用网关安全技术要求以及信息技术安全性评估准则等7项国家标准，并主笔撰写了与信息安全战略技术发展有关的多篇专题报告。
宋晓龙：男，1970年9月出生。2000年5月毕业于中国人民解放军信息工程大学，获理学硕士学位：主要研究兴趣为密码算法与理论、密码分析和密码产品测试技术；曾在《通信学报》、《信息安全与通信保密》等刊物发表论文多篇，译著有《密码编码和密码分析：原理与方法》。
郭涛：男，1974年9月出生，湖北宜昌人。毕业于华中科技大学计算机学院，2003年10月将获得工学博士学位：主要研究方向为安全电子支付、信息安全、密码学；曾在《通信学报》、《高技术通讯》等刊物发表论文十几篇。
本书主要介绍现代密码学的加密思想及其实现方法，涉及数论、概率论、抽象代数。此外，还有一些是加密算法思想的描述及复杂度理论。我们在讨论安全通信及其理论时，有三个专业术语的含义有些许差异，它们是密码编码(cryptography)、密码分析(cryptanalysis)和密码学(cryptology)。其中，密码编码指的是用各种不同的加密算法对信息进行加密，以保证其安全性;密码分析是相对于密码编码而言的，它包含有密码攻击、发现漏洞和系统安全性证明的内容。密码学则是一个比较综合的概念，它涵盖了密码编码和密码分析两个概念，
这也是使用最频繁的一个词。
在介绍了密码编码、密码分析和密码学的概念之后，下面我们介绍一下本书的主要内容：
1)介绍密码学的历史沿革，特别是给出一些古典的加密算法，并且分析这些算法为什么被现代的加密算法所取代。
2)密码编码领域的展望(在实际应用领域，加密并不仅仅用于数据的安全和保密)。
3)介绍古典和现代密码体系的同时，给出这些密码体系的数学理论基础。
4)给出一些针对各种加密算法的密码分析方法。
5)阐明密钥管理和执行是基础。
阅读本书要求读者具备跟微积分相关的复杂数学和一些基本的线性代数知识。
首先我们将有选择性地介绍古典密码学，这主要是指20世纪40年代之前的密码编码和密码分析技术。特别是在1935年到1940年期间，一些通过机械的和初级的电子设备自动实现加密和解密的设备大量出现，这些设备工作速度很慢，而且非常的笨重。这主要是由于加密和解密的过程基本上是用机械和电子方法实现的，并不是通过软件实现的。
按照现代的标准来衡量，那些古典密码(德国的恩格码之前的密码)看来是很失败的。这主要归功于现代的计算机远比20世纪40年代那些用真空电子管的机器要好得多，而且现在的加密算法远比以前的复杂，主要是为了防止一些在以前看来是不可思议的攻击。
虽说古典的密码分析和现代的密码分析有很大的区别，但它们有一个共同的地方：都使用了数学中的统计算法(stochastic algorithm)或者概率算法(probabilistic algorithm)。这相对于初等数学中非常传统而且较常用的确定性算法(deterministi calgorithm)形成了鲜明的对比。对于许多应用目的而言，这样的算法运行速度非常快但成功率却达不到100％，或者说通常运算速度较快，但不总对。这似乎就像现实生活，而非人为的特意忽略。
在这里需要说明的一点就是，计算机的普及对密码学理论产生了很大的影响，极大地改变了密码学，例如：
1)加、解密的工作可以自动完成，大规模的加、解密的运算变得很容易完成，设计更为精巧的系统成为可能。
2)计算机网络中数据的存储、传输和数据处理的激增，对有效的加密及相关技术提出了新的要求。
3)当然，这也使密码分析攻击变得很容易。所以，可能以前只有小孩或者间谍才感兴趣的问题，而现在却有很多人感兴趣。
这是一门应用数学的学科，在以往我们所接触的数学绝大部分都是由应用来推动的。在这里，我们将要接触的有：数论、线性代数、抽象代数、概率论、复杂度理论和其他一些数学知识。当然，我们在本书中不可能把所有的理论一一细述，但会介绍一些和本书相关的知识。
当然，在本书中我们也没有足够的篇幅把有关密码学的历史演变和现在的发展完整地讲述一遍。我们只会给出一些具有代表性而且在密码学发展历史上比较重要的例子，并描述一下密码学发展的其他分支。
我们也不可能全面模拟现实生活中的各种有关加密的问题并进行讨论，密码分析尤其是更不可能。因为我没有实际接触过那些机器，而且，在现实生活中，无论是加密还是密码分析的模拟，都可能需要几个小时甚至几天的时间，此外还需要大量的存储空间。普通的计算机处理加密和(授权的)解密很快，而现实生活中对密码系统的攻击可能需要花费数天甚至数月的时间。
因此，我们会首先讨论一些古典的加密系统，以及这些加密系统中所使用的数学知识，甚至用来理解或者破译这些加密系统的数学知识，这是一种好的热身方式。然后我们会讨论一种现在正在使用的对称加密系统——DES(数据加密标准，Data Encryption Standard)。 DES加密算法比那些古典的加密算法要复杂得多。当然，也正是由于它的成功，目前还没出现一种好的攻击方法。DES早在20世纪70年代中期就已经成为美国的一套加密标准(对称密码)。
而且，DES标准除了在美国以外的其他国家也得到了广泛的应用。从DES标准被采用至今，经过20多年来的密码分析考验，还没有发现它有什么致命的弱点。但现在计算机的运算速度已是远非1976年那时候的计算机所能比拟的，通过穷举法进行攻击已经成为可能。事实上，在1998年中期，美国的EFF(Electronic Frontier Foundation)花费了100 000美元，用一般商用元件构造了一个DES破解器，这个破解器可以在两天内获得一个DES密钥。好在还可用DES做三次加密，即所谓的3-DES加密算法，这种算法被认为是一种比较安全的算
法。然而，美国国家标准协会(National lnstitute of Standard)正在征集一种新的128位对称加密算法。迄今为止，征集还没有结束，最终被采纳的加密算法将被命名为高级加密标准(Advanced Encryption Standard，AES)。
本书中还将讨论另外一类密码算法——非对称加密算法，又称公钥密码算法。我们将主要讨论两种公钥密码算法：一种是RSA算法，另外一种是ElGamal算法及其应用。RSA加密算法比较简单而且也很流行，但ElGamal算法更适用于椭圆曲线密码。RSA加密算法的安全性基于数学中的一个难题：大整数因式分解。ElGamal加密算法的安全性则是基于这样一个难题：有限域中的离散对数计算(这在后面会给出具体的含义)。这两种密码体制中的任何一种加密算法都需要生成大量且很大的素数，其实这本身就是一个有趣的问题。在介绍完这两个加密算法后，我们将进一步介绍NTRU密码，这是一种新的密码，从数学理论上它显得更为成熟。与对称密码体制相比，非对称密码体制由于它更加依赖于数学理论的本质，似乎看上去更容易受到攻击。在这部分我们将介绍一些重要而且精妙的数学问题。
在介绍完经典问题以后，我们会专门给出一些数论的知识，这些知识和现代加密系统有着很大的关系，在公钥加密体制(如RSA加密系统和EIGamal加密系统)中尤其如此。这部分将包括下面这样一些内容：
1)公钥(非对称)密码
2)伪随机数发生器(pRNG)
3)协议必要的数学知识将包括：
1)一些数论和抽象代数的结论
2)素性检验、因式分解及相关算法
3)复杂度理论
我们不会过多地讨论复杂度理论，在书中我们只简单地介绍一下复杂度理论的有关指标，并且判断一些问题的复杂程度。
在这里，素数检验和整数分解是所有问题的根本，许多实际的加密算法都可以通过这些基本问题来描述。尽管有时候要解释一个完整的算法，往往还需要很多其他的知识。但是不用解释算法的实质，我们也有可能通过实验对算法的性能和准确性有一个直观的认识。
首要的基本问题就是整数模n的结构以及它的一般化问题，记为Z／n。我们需要明白，对于n为合数和n为素数时，得到的这个Z／n存在本质上的区别。
在好多高效的算法中，还有一个很重要的随机化问题。在数学中，我们可能已经习惯了每个问题都会有一个肯定的结果，即确定性。随机化可能看上去不是那么容易理解，但在许多情况下，这又恰恰是很多加密算法的重要的理论基础。那么我们直接面临的问题就是去考虑概率意义上的素性检验，比如索洛维—斯特拉森方法和米勒—罗宾方法，并证明它们真正可行。
本书中所包含的内容，可能已经超过了一学期的课程，目前书中的内容都是经过我精心筛选的。如果给一年的时间来学习这门课，可能就会比较轻松一点。
本教程在实际教学中已经使用了多次，并且都是基于这么一个前提，学生对数论、抽象代数、概率甚至密码编码都没有什么了解。密码应用总是离不开数学问题，本书则使得注重实用的人和注重理论的人都可在书中得到各自感兴趣的信息。在编写此书的过程中，我已经尽量使各章节内容相互独立，以便读者可以跳过自己不喜欢的章节，而不影响对其他章节的理解。因此，在某些章节，可能会重复出现某些知识。从教与学的观点看，适当的内容重复是一件好事。
如果把此书作为一学期的数论教材，可以跳过密码编码和计算部分，但可把这部分作为选读资料。当然，在本书中，还有很多抽象代数的知识，这些知识已经远远超过了传统的数论教程。在我为本科生讲授数论课程的时候，我总是考虑一个问题，那就是，在讲授数论的时候是将抽象代数的知识作为独立的预备知识，还是由数论的知识来引出抽象代数的知识。最后我往往会选择后者，就是在讲述数论知识的同时，我一般会附带上抽象代数，但很少会有一本教材能够符合这个要求。本书的一部分内容是我为本科生所写的讲义，在那个讲义中
我将数论和抽象代数都纳入其中，并将数论作为引入抽象代数的一个具体入口，而反过来数论的一些基本结论又来源于抽象代数。在选择把此书作为数论的教程时，应该跳过前面六章的内容(前六章主要讲的是加解密的问题)。此外，还要跳过“希尔密码”这一章。有关公开密钥加密系统的章节也可以跳过，但这却是数学在通信中的主要应用之一。
此外，可以将此书作为密码学知识的简短介绍性教程(略过有关数学的知识)。为了使本书更容易理解，书中在涉及到数学知识的时候，一般只提到一些必须需要了解的知识，而且都是一些基本知识。我在编写时也力图使这些数学知识无论是从初级的观点，还是高级的观点都是容易理解的。一般来说，在遇到需要证明的时候，我们往往都对特殊情况给出初等证明，而对一般情况给出较高层次的证明。我认为在教学中，这是一种比较好的教学方法，而且我也没有在这方面吝惜时间和篇幅。另外。一些比较严格的密码学教材都有一个通病，
即相关的数学知识受到了冷遇。还有一个普遍的局限就是它们总是假定读者已经具备了相当的数学功底。相比较而言，在本书中不仅为希望了解数学在密码学中如何应用的学生提供了充足的数学资源，而且还尽可能降低对数学知识的要求。因此，本书完全可以作为一本密码学导论的简明教材。从某种意义上说，这也是写作本书的初衷。
如果要把此书作为计算数论的教材，我建议读者应该把注意力集中在算法上，减少对密码学以及更多的理论数学部分的关注。在我教授这门课的过程中，我没有假定学生能够或者愿意做任何的计算机的工作，毕竟这需要CPU的时间。在本书中，我详细地给出了算法的描述，目的就是使其清晰易懂，但并没有给出具体的算法的伪代码或者算法的某种语言实现。我之所以这么做，很重要的一个原因就是，我希望学生至少明白算法是如何工作的，而不是简单地去执行它。我没有用专用语言写出算法的另一个原因，是因为我无意认可某种语言及
其所需要的全部东西。尽管我坚决支持学生去学习如何编写程序，但不鼓励他们去研究软件包。但是，界面友好的软件包的确很容易上手。
在授课的过程中，若有些学生已经学习过概率论或者数论的知识，就可以跳过其中一些相关的章节。在本书的编写工作中，我将大量的数学知识放到了各章各节中去讲解，而不像有的教程将所有的知识放到最后的附录中。我是基于这么一种考虑，那就是，已经学过这些知识的学生可以跳过相关章节不看，而不了解这些知识的学生可以直接按着顺序阅读，无需为了看一些相关知识而前后翻个不停。这样组织也是为了各章保持独立性。
最后，我要感谢我的朋友们，他们给我的初稿提出了好多宝贵的意见，在此我特别感谢：美国艾奥瓦州立大学的Irvin Roy Hentzel教授、艾奥瓦大学的Yangbo Ye、圣母玛利亚大学的Joachim Rosenthal、密苏里大学的Daniel Lieman、密歇根州立大学的Jonathan Hall等人。在我写书的这么多年中，我的学生们一直都在使用这些初稿，我要感谢这些学生，他们给我提出了很多好的建议，而且也指出了初稿中的若干问题，使本书的质量有了较大的提升。
Paul Garrett
于明尼阿波利斯，明尼苏达大学
garrett@math．umn．edu
paul．garrett@acm．org
http：／／www. math．umn．edu／-ganett/
吴世忠 宋晓龙 郭涛：吴世忠: 吴世忠，博士、研究员，中国信息安全产品测评认证中心主任。现为全国信息安全标准化技术委员会副主任，中国信息产业商会信息安全产业分会理事长，《信息安全与通信保密》杂志主编。已公开出版文章百余篇，著有《信息系统的互连与互通》、《C3I系统的安全与保密》、《关贸总协定：中国准备好了吗？》、《首都信息化标准指南·信息安全与保密标准化体系》等专著五部和《应用密码学》、《密码编码和密码分析原理和方法》、《网络世界信息安全的真相》、《密码学的理论和实践》、《中文Windows2000的安全性》、《密码学导引》译著六部，同时还主持起草了防火墙、应用网关安全技术要求以及信息技术安全性评估准则等7项国家标准，并主笔撰写了与信息安全战略与技术发展有关的多篇专题报告。
宋晓龙: 男，1970年9月出生。2000年5月毕业于中国人民解放军信息工程大学，获理学硕士学位；主要研究兴趣为密码算法与理论、密码分析和密码产品测试技术；曾在《通信学报》、《信息安全与通信保密》等刊物发表论文多篇，译著有《密码编码与密码分析原理和方法》和《密码学导引》。
郭涛: 郭涛，男，1974年9月出生，湖北宜昌人。2003年10月毕业于华中科技大学计算机学院，获得工学博士学位。中国信息安全产品测评认证中心高级研究人员，参加了多项国家重大科研项目。主要研究方向为信息安全技术、密码理论、安全测试技术、安全电子支付技术等；曾在《通信学报》、《高技术通讯》等刊物发表论文十几篇，译著有《密码学导引》。
自从20世纪末以来，信息安全成为了人们密切关注的热点问题，而作为信息安全理论基石的密码学更是成为学术界炙手可热的研究方向。市场上关于密码学的译著已经不下几十本，当然也包括我们翻译的《应用密码学》、《密码编码和密码分析》(中译本由机械工业出版社引进出版)等书。而明尼苏达州大学数学系的PaulGarrett教授所著的这本书以其深入浅出、条理清晰的风格而在诸多密码学专著中独具特色，它弥补了其他密码学专著忽略密码学相关数学知识的不足，介绍了与密码学相关的几乎所有数学知识。通过阅读本书，读者可以对密码学涉及到的所有数学知识有一个比较全面的了解，有助于加深读者对密码学的理解。
本书并没有深入阐述密码理论和具体的密码算法，而是就密码学相关的数学知识做详细介绍。如果跳过数学知识部分，本书可以作为一本密码学导论。但本书更是一本数论教程，一本以密码学为主线、包含抽象代数的广义数论教程。因此，本书不仅适合于广大数学、密码学专业的学生阅读，也适合于密码学和网络安全专业人士参考。我们希望所有读者阅读之后都能有所收益。
本书的翻译工作受到国家自然科学基金重大项目(90104033)的资助。
本书由吴世忠、郭涛、宋晓龙主持翻译，其他参与翻译校对工作的人员还有杨玉斌、付敏、彭建芬等，在此一并表示感谢。
由于水平所限，翻译不妥或错误之处在所难免，敬请广大读者批评指正。
昊世忠
2002年9月
于中国信息安全产品测评认证中心
第1章 简单密码
1．1 移位密码
1．2 约简／整除算法
1．3 一次一密密码本
1．4 仿射密码
第2章 概率
2．1 计数
2．2 基本思想
2．3 英文统计
2．4 对仿射密码的攻击
第3章 置换
3．1 暗号：代替
3．2 变位字：换位
3．3 置换概念
3，4 洗牌
3．5 分组交错
第4章 严格的密码
4．1 维吉尼亚密码
4．2 最小公倍数LCM和最大公约数GCD
4．3 Kasiski攻击
4．4 期望值
4，5 Friedman攻击
第5章 概率问题
5．1 生成函数
5．2 方差、标准差
5．3 车贝雪夫不等式
5．4 大数定律
第6章 现代对称密码
6．1 设计目标
6．2 数据加密标准
6．3 高级加密标准
第7章 整数
7．1 整除性
7．2 因式唯一分解
7．3 欧几里得算法
7．4 乘法逆元
7．5 乘法逆元的计算
7．6 等价关系
7．7 整数模m
7．8 本原根和离散对数
第8章 希尔密码
8．1 希尔密码原理
8．2 对希尔密码的攻击
第9章 复杂度
9．1 大O和小O符号
9．2 位操作
9．3 概率算法
9．4 复杂度
9．5 子指数算法
9．6 柯尔莫哥洛夫复杂度
9．7 线性复杂度
9．8 最差情况与期望值
第10章 公钥密码算法
10．1 陷门
10．2 RSA密码
10．3 Diffie-Hellman密钥交换
10．4 ElGamal密码
10．5 Knapsack密码
10．6 NTRU密码
10．7 算术密钥交换
10．8 量子密码
10．9 美国出口限制
第11章 素数
11．1 欧几里得定理
11．2 素数定理
11．3 序列中的素数
11．4 车贝雪夫定理
11．5 最佳渐进法
11．6 黎曼假设
第12章 modp的根
12．1 费马小定理
12．2 特殊的因式分解表达式
12．3 梅森数
12．4 更多的例子
12．5 指数算法
12．6 modp 的二次根
12．7 modp的高次根
第13章 模合数的根
13．1 孙子定理
13．2 特殊方程组
13．3 模是合数的同余方程
13．4 亨泽尔引理
13．5 平方根oracle
13．6 欧拉定理
13．7 原根的性质
13．8 欧拉判别准则
第14章 弱乘法性
14．1 弱乘法性的定义
14．2 算术卷积
14．3 墨比乌斯反演
第15章 二次互反定理
15．1 二次根
15．2 二次符号
15．3 乘法性质
15．4 二次互反律
15．5 快速计算
第16章 伪素数
16．1 费马伪素数
16．2 非素的伪素数
16．3 欧拉伪素数
16．4 索洛维-斯特拉森检验
16．5 强伪素数
16．6 米勒-罗宾检验
第17章 群
17．1 群概念
17．2 子群
17．3 拉格朗日定理
17．4 子群的指标
17．5 指数定律
17．6 循环子群
17．7 欧拉定理
17．8 群的指数
第18章 协议概述
18．1 基本的公钥协议
18．2 Diffie-Hellman密钥交换
18．3 秘密共享
18．4 不经意传输
18．5 零知识证明
18．6 鉴别
18．7 电子货币和电子商务
第19章 环、域、多项式
19．1 环、域
19．2 整除性
19．3 多项式环
19．4 欧几里得算法
19．5 欧几里得环
第20章 分圆多项式
20．1 特征
20．2 重因子
20．3 解分圆多项式
20．4 本原根
20．5 模p的本原根
20．6 素数方幂
20．7 本原根的计数
20．8 不存在性
20．9 搜索算法
第21章 随机数发生器
21．1 假的一次一密乱码本
21．2 伪随机数发生器的周期
21．3 同余发生器
21．4 反馈移位发生器
21．5 Blum-Blum-Shub发生器
21．6 Naor-Reingold发生器
21．7 线性同余发生器的周期
21．8 本原多项式
21．9 线性移位寄存器的周期
21．10 本原多项式的例子
21．11 本原性检验
第22章 群的更多知识
22．1 群同态
22．2 有限循环群
22．3 无限循环群
22．4 群中的根和方幂
22．5 平方根算法
第23章 伪素性证明
23．1 A函数
23．2 卡米克尔数
23．3 欧拉证据
23．4 强证据
第24章 因式分解攻击
24．1 Pollard的Rho方法
24．2 Pollard的p-1方法
24．3 Pocklington-Lehmer准则
24．4 强素数
24．5 素性证书
第25章 现代因式分解攻击
25．1 高斯消元法
25．2 随机平方分解
25．3 Dixon算法
25．4 非筛的二次筛法
25．5 二次筛法
25．6 其他改进
第26章 有限域
26．1 有限域的构造
26．2 域扩张的例子
26．3 模户加法
26．4 模户乘法
26．5 模户乘法逆
第27章 离散对数
27．1 Baby-stepGiant-step算法
27．2 Pollard的Rho方法
27．3 指数演算
第28章 椭圆曲线
28．1 抽象的离散对数
28．2 离散对数
28．3 椭圆曲线上的运算
28．4 无穷远点
28．5 射影椭圆曲线
第29章 有限域的更多知识
29．1 交换环上的理想
29．2 环同态
29．3 商环
29．4 极大理想和域
29．5 域扩张的更多知识
29．6 费罗贝尼乌斯自同构
29．7 不可约多项式的计数
29．8 本原多项式的计数
附录A 相关公式
附录B 部分习题答案
附录C 常用数表
