密码学基础教程:秘密与承诺

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

目录A Cryptography Primer: Secrets and Promises出版者的话译者序前言第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/key11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2El Gamal 密码系统143关于El Gamal密码系统的更多说明144实践中的公钥密码145签名146陷门单向函数及其在公钥加密和数字签名中的应用147RSA陷门单向函数148RSA公钥密码系统149RSA数字签名方案1410消息摘要函数1411消息摘要函数在承诺中的应用1412思考题延伸阅读索引

前言A Cryptography Primer: Secrets and Promises作为一个数论专家与和平主义者，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细节的读者可以在其他教材中轻易地找到这些知识。 致谢非常感谢Sarah Finney、Peter Galea、Kevin Ingersoll和Mark Weaver帮助我完成基于该书的课程。同样感谢国家科学基金对该课程建设的资助，感谢Michael Yanagisawa帮助书稿的校对，后还要感谢Alice、Bob、Eve以及其他频繁出现在现代密码学文献中的角色。