内容简介

　　《密码学基础教程:秘密与承诺》解释了用来实现通信隐私性的密码协议，以及如何使用保证消息、文档或者程序的正确性、完整性及来源可靠性的数字签名。书中提供了关于现代密码学基本原理和数学知识的导引，主要内容包括模算术、加法密码、函数、概率论、完美保密与完美安全的密码系统、数论、欧几里得算法、易解和难解计算问题、模乘幂、模对数、单向函数、Diffie-Hellman指数密钥协商协议、计算安全的单钥密码系统、公钥密码系统和数字签名等。《密码学基础教程:秘密与承诺》叙述清晰，简单易懂，适合作为高等院校计算机及相关专业本科生教材。

目录

ACryptographyPrimer:SecretsandPromises
出版者的话
译者序
前言
第1章引论
1.1加密与解密
1.2信道、安全与不安全
1.2.1互联网
1.2.2局域网
1.2.3移动电话
1.3隐匿式安全
1.4另一种选择：柯克霍夫原则
1.5密码学分类
1.6对密码系统的攻击
1.7思考题
第2章模算术
2.1凯撒密码
2.2整数“圈
2.3日常生活中的模算术
2.4同余
2.4.1模7同余
2.5另一个例子：模10同余
2.6同余代换
2.6.1使用代换简化多个数相加
2.6.2使用代换简化多个数相乘
2.6.3舍九法
2.7代表元与余数
2.7.1商和余数
2.7.2利用rem检查两个数是否同余
2.7.3使用rem简化模同余式
2.7.4利用rem简化涉及rem计算的等式
2.7.5负整数的代表元
2.8思考题
第3章加法密码：一个不安全的分组密码
3.1加法密码
3.2分组密码
3.3对加法密码的攻击
3.3.1已知明文攻击
3.3.2唯密文攻击
3.4对使用ECB模式的分组密码的攻击
3.5思考题
第4章函数
4.1基础知识
4.2可逆性
4.2.1一对一和映上
4.3模算术函数
4.3.1模加和加法逆元
4.3.2计算模m加法逆元
4.3.3模乘和乘法逆元
4.3.4计算模7乘法逆元的简单方法
4.3.5乘法逆元不总是存在
4.4函数符号
4.5函数的使用
4.6一个两输入函数：一般化凯撒密码的加密函数
4.7特殊化：将两输入函数转化为单输入函数
4.8思考题
第5章概率论
5.1实验结果
5.2结果的概率
5.3绘制概率分布图
5.4实验结果集合的概率
5.5小结
5.6均匀分布
5.7随机变量
5.7.1基于另一个随机变量定义随机变量
5.7.2随机变量的形式化数学定义
5.7.3随机变量的均匀分布
5.8思考题
第6章完美保密与完美安全的密码系统
6.1窃听者能够从密文中获得什么
6.2密码系统的评估
6.3完美保密与唯一解密性
6.4完美保密简史
6.4.1弗纳姆机器
6.4.2一次性密码本
6.5完美保密密码系统的缺点
6.6思考题
第7章数论
7.1整除
7.2互素
7.3素数
7.4素因子分解
7.5欧拉函数(x)
7.6乘幂
7.6.1幂指数相加法则
7.6.2幂指数相乘法则
7.7欧拉定理
7.8思考题
第8章欧几里得算法
8.1测量谜题
8.1.1一个更复杂的例子
8.2通过解决测量谜题求模乘法逆元
8.3欧几里得算法
8.3.1欧几里得算法计算什么
8.3.2前向计算
8.4欧几里得算法的后向部分
8.5欧几里得卡片
8.6欧几里得算法教会我们什么
8.7思考题
第9章完美保密的某些应用
9.1秘密分享与完美保密
9.2门限秘密分享
9.3消息认证码
9.4思考题
第10章计算问题：易解和难解
10.1计算问题
10.2算法
10.2.1模幂运算的重复平方算法
10.3预测一个算法需要的计算机执行步数
10.4快速算法和慢速算法：容易问题和困难问题
10.4.1计算问题和密码学
10.5思考题
第11章模乘幂、模对数和单向函数
11.1单向函数在口令安全中的应用
11.1.1针对使用单向函数的口令文件的字典攻击
11.1.2为口令文件“掺盐
11.2单向函数在登录中的应用：s/key
11.3单向函数在承诺中的应用/误用
11.3.1不隐藏
11.3.2不绑定
11.4思考题
第12章DiffieHellman指数密钥协商协议
12.1动机
12.2背景
12.3协议
12.4安全
12.5中间人攻击
12.6思考题
第13章计算安全的单钥密码系统
13.1现实世界中安全的分组密码
13.2密文分组链
13.3指数密码
13.4如何寻找大素数
13.5思考题
第14章公钥密码系统和数字签名
14.1公钥密码系统
14.2ElGamal密码系统
14.3关于ElGamal密码系统的更多说明
14.4实践中的公钥密码
14.5签名
14.6陷门单向函数及其在公钥加密和数字签名中的应用
14.7RSA陷门单向函数
14.8RSA公钥密码系统
14.9RSA数字签名方案
14.10消息摘要函数
14.11消息摘要函数在承诺中的应用
14.12思考题
延伸阅读
索引

前言/序言

　　ACryptographyPrimer:SecretsandPromises作为一个数论专家与和平主义者，G.H.Hardy在其自传《一个数学家的致歉》中写道:……令高斯以及少数数学家们欣慰的是，至少还有一种科学“数论”……能够远离人们的日常活动，它应当保持纯粹和优雅。
　　Hardy的这《密码学基础教程:秘密与承诺》于1940年出版，他当时正面临着职业生涯的结束。如果他能够延后30年再做出论断的话，或许他会得出截然不同的结论，因为数论成为一项与战争相关的重要技术（密码学——研究秘密编码的应用学科）的基础。
　　密码学的应用至少有数千年的历史。在印度圣经中，密码学被列为64项女人的技艺之一。其中一个著名的初等密码系统要归功于尤里乌斯·凯撒。许多逸闻趣事证实了多年以来密码学和密码分析学（即编码破解）在战争和外交博弈中的重要作用。例如，英国人曾截获并破译了由德国外交部发给墨西哥政府（经由大使）的齐默曼电报，在电报中德国许诺将得克萨斯州、新墨西哥州以及亚利桑那州划归给墨西哥作为其帮助对抗美国的回报，这促进了美国加入第一次世界大战的进程。密码分析学同时也在不那么重大的事件中发挥着作用，以下文字摘自Casanova（1757）的自传：
　　五六周之后，她问我是否已经解密了这些手稿……我告诉她是的。
　　“先生，恕我冒昧。没有密钥，这怎么可能呢？”
　　“希望我告诉你密钥吗，夫人？”“如果这样的话告诉我吧。”
　　我告诉她密钥，这个密钥并不属于任何语言，然后看到她吃惊的表情。她告诉我说这是不可能的，因为她坚信她自己是唯一掌握这些密钥的人，她仅仅将这些密钥记在脑海中，从来没有写下来。
　　我本可以告诉她真相的——已被我掌握的与解密手稿同样的计算已经让我知道了密钥——但是一个邪恶的想法闪过心头，阻止我告诉她这一真相。我保持神秘使她深深地被我俘获，那天我主导了她的灵魂，肆意地散发着我的力量。
　　然而在信息时代，或许密码学最大的贡献还是在商业领域。一直以来,银行用密码学来保障电子传输的安全，分布在不同地域的公司用密码学来保证他们之间的通信不被工业谍报人员窃听。但是，或许最令人兴奋的应用在于，让素未谋面并因此无法提前协商密钥的双方也能够安全地通信。随着互联网上的商业活动日渐繁荣，这种应用变得更加普及。幸运的是，现今的指数密钥交换协议和公钥密码学能够使这类应用成为现实。
　　Diffie和Hellman在1976年提出了公钥密码学，其思想在于：有两个不同密钥，公开密钥用来加密消息，而私有密钥则用于解密；由一方秘密地生成这对密钥，他可以将加密密钥公开而不暴露用于解密的密钥。因而任何人都可以给密钥生成者发送加密的消息，而只有密钥生成者能够解密这一消息。Rivest、Shamir和Adleman于1978年最先实现了这一思想。至于他们的方案有多么闻名于世，我们来看看下面这段摘自滑稽喜剧《山河之旅》中的对白吧：
　　“杰伊，我不太熟悉计算机，对此知之甚少。我了解到这个密码是两个差不多100位的大素数相乘得到的，对吧？”
　　“是的，很对。这被称为RSA密码系统。”
　　“好吧，这一名字来源于MIT的Rivest、Shamir和Adleman。我只知道这么多。我也知道即使是使用先进的计算机来破解，也需要花费无穷无尽的时间，”她回忆着，“两个100位的素数相乘得到的密钥差不多需要38亿年的时间来破解，对吧？”“完全正确。很明显，所有被窃取的信息都来自于从公司办公室到你家的电话线路上发生的窃听。假设只有麦克掌握解密密钥，如果他不将这一密钥分发给别人，那么是没人能够解密这一编码的。但是这一说法在逻辑上还有一点不严谨之处，”他边说边松了松深绿色的丝织领带，“Vee，这里比我想象的热好多啊，你介意我脱掉外套吗？”
　　“当然不，你太客气了。”她说道……我们的女主角Vee说道，RSA的安全性是基于分解两个素数乘积的困难性，因此，它使得Hardy最喜欢的“纯”数学领域（数论）有了用武之地。这一密码系统（同大多数密码系统一样）的根基在于简单与困难的区别。生成一个公钥/私钥对就如同选择两个100位的素数并将它们相乘那么容易，而正如Vee所言，攻破这一系统（利用当前已知的方法）则需要大量的时间才能完成；这似乎需要用两个素数的乘积来确定这两个素数分别是什么，这一问题称为整数分解。尽管针对这一问题的研究有着持续的进展，但是无论如何，已知的算法的速度都还没有快到足以威胁RSA安全性的程度。下面引用一个更了解市场营销手段而不精通数论的人的一句话：
　　由于数字货币系统的隐私性和安全性都依赖于密码学，因此任何能够攻破密码系统的数学或计算机科学的突破都会是一场灾难。而在数学方面最为显而易见的突破或许就是构建一个能够快速分解大整（素）数的方法。——比尔·盖茨，《未来之路》第一版，265页（大整数分解是这样的问题，即已知一个数，求这个数是由哪些素数相乘得到的，如果这个数是一个素数，那么分解的结果就是它本身。）但是RSA不仅仅用于加密。正如Diffie和Hellman意识到的那样，公钥密码学的另一个方面在于数字签名。使用类似于RSA的方式，公私密钥对的生成者可以用私钥对文档产生一个签名。这是一个由文档产生的数字，拥有公钥的人都可以验证这一签名与文档是一致的（满足某种数学关系），而且只有拥有私钥的人才能够为文档产生合法的签名。因此一个文档的合法签名可以作为密钥生成者需要为此负责这一事实的强有力的证据。如果有人篡改了文档，那么篡改后的文档和签名不会再有相同的数学关系了，因此这一文档将会被视作无效。于是，数字签名可以用于互联网中传输的消息的认证，以此来防止潜在的消息篡改和伪造。它们可以用于创建不可伪造的证书，如电子版的信用卡或护照。它们也可以用于检测对计算机程序未经授权的篡改，如病毒的侵入等。
　　与此同时，其他保障计算机安全的技术也被陆续提出，包括对身份的安全认证（这与在电话中询问某电话号码、信用卡号码等信息以确认对方身份类似），对一个文档内容承诺但不泄露其信息的方法（对一个密封的信封的模拟），为一个文档打上时间标记的方法（对给自己邮寄一封信以得到带有时间的邮戳这一方法的模拟）。
　　计算科学对计算简单问题与计算困难问题进行了分类，而密码学技术正是构建于计算科学这一理论之上：在你拥有密钥的情况下，解密编码是容易的；而如果你没有密钥则不然。密码学正是对这种智慧追求的具体实现。
　　为了让更为广大的读者都能接触到这一饶有趣味的、令人兴奋的而且越来越重要的充满智力挑战性的领域，我开设了课程“秘密与承诺：数字安全导论”。我为这门课撰写了这《密码学基础教程:秘密与承诺》作为教材。题目中“秘密”这个词表示用密码学的方法来实现私密通信；“承诺”这个词表示用数字签名来保证消息、文档或程序的有效性与完整性。《密码学基础教程:秘密与承诺》旨在对现代密码学的基本理论和其所依赖的数学基础给出一个简介，而并非一部面向实践的、教你如何做的教材，即这《密码学基础教程:秘密与承诺》不会指导读者如何用现代计算机程序（如网页浏览器和电子邮件系统）来实现数字安全。这些程序一直在更新换代，而且如果想在市场上占有一席之地，必须做到让它们的使用者无须了解这些软件所依赖的安全技术便可轻松使用。在《密码学基础教程:秘密与承诺》中，我们要透过现象看到问题的本质，研究安全技术，探寻其之所以安全的原因。
　　对于一些基本的密码学方案，如DES和SHA，其细节并没有启发作用，因而在《密码学基础教程:秘密与承诺》中我们省略对其细节的讨论。其他一些基于初等数论的方案也能发挥与之相同的功能，尽管这些基于数论的方案效率低下难以实用，但是它们被认为是安全的，而且适合在这门课中讲解。因此为了最大限度地做到可读性与一致性，我们在实用性方面做出一定的牺牲与权衡，对于急切想了解DES细节的读者可以在其他教材中轻易地找到这些知识。
　　致谢非常感谢SarahFinney、PeterGalea、KevinIngersoll和MarkWeaver帮助我完成基于该书的课程。同样感谢国家科学基金对该课程建设的资助，感谢MichaelYanagisawa帮助书稿的校对，最后还要感谢Alice、Bob、Eve以及其他频繁出现在现代密码学文献中的角色。
　　译者序ACryptographyPrimer:SecretsandPromises计算机信息网络已经成为人们社会生活的基础设施，人们对网络的依赖已经可以和水、电等基本生活必需品比肩，大量的生活信息、工作信息和社会信息在网络中高速传送、处理和应用，多维度地支撑着人们家庭及社会生活的方方面面，形成了人们生活的另一个“空间”，财产、身份、学历甚至整个社会关系都变成了信息网络空间中的一条条“记录”。但是，人们对信息网络的强烈依赖，也产生了另一方面的问题。存储于网络空间中的数据便于传输、处理、共享但可控性差。网络空间给人们带来便利的同时也带来了隐私信息泄露、商业信息泄密以及消息被篡改、不当使用、身份被假冒等多重风险，如果不能对信息进行很好的保护，将会造成不可估量的损失。
　　密码学是一门古老的学科，甚至可追溯到古埃及的法老时代。当然，最初的密码应用环境非常简单，是一种主要用于保证通信安全的技术或技巧，直到20世纪40年代香农创立信息论并以此研究保密系统开始，密码的设计和分析开始变为一种有理论基础、有科学方法的“科学”。而目前信息网络应用的普遍性和其中信息安全问题的广泛性，使得密码学不再是军事、外交、国防领域的专宠，而成为人们社会生活中时时处处依赖的信息安全保障必备工具，这也是从20世纪70年代以来密码学迅速发展的原因。密码学已经成为当今社会不可或缺的应用学科。
　　为了使网络使用者对密码学有一个初步了解，我们翻译了美国布朗大学PhilipN.Klein教授编著的《ACryptographyPrimer：SecretsandPromises》一书。与普通的密码学教程不同，这《密码学基础教程:秘密与承诺》不以密码学的研究和应用为目的，而注重密码知识的普及。阅读该书几乎不需要任何专门知识，书中从最初步的概念、最易理解的例子、最简单的应用开始，深入浅出，层层递进，一直到密码学思想的实质。《密码学基础教程:秘密与承诺》不追求表达的严谨性和方法的通用性，力求让读者理解密码学最本质的原理，是一本极具特色的入门书，通俗易懂而又极其深刻。译者在翻译该书的过程中深感获益，希望该书中文版的出版能够给希望了解密码学的中文读者带来帮助。
　　对该书的编著者PhilipNKlein表示敬意。
　　译者2016年7月27日

其他推荐