书名：深入浅出密码学
ISBN：978-7-115-60034-9
本书由人民邮电出版社发行数字版。版权所有，侵权必究。
您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。
我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。
如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。
著 ［美］戴维•王（David Wong）
译 韩露露 谢文丽 杨雅希
责任编辑 郭 媛
人民邮电出版社出版发行 北京市丰台区成寿寺路11号
邮编 100164 电子邮件 315@ptpress.com.cn
网址 http://www.ptpress.com.cn
读者服务热线：(010)81055410
反盗版热线：(010)81055315
读者服务：
微信扫码关注【异步社区】微信公众号，回复“e60034”获取本书配套资源以及异步社区15天VIP会员卡，近千本电子书免费畅读。
密码学是信息安全的基础，本书教读者应用加密技术来解决现实世界中的一系列难题，并畅谈了密码学的未来，涉及“加密货币”、密码验证、密钥交换和后量子密码学等话题。
全书分为两个部分，第一部分介绍密码原语，涉及密码学基础概念、哈希函数、消息认证码、认证加密、密钥交换、非对称加密和混合加密、数字签名与零知识证明、随机性和秘密性等内容；第二部分涉及安全传输、端到端加密、用户认证、“加密货币”、硬件密码学、后量子密码、新一代密码技术等内容。
本书形式新颖、深入浅出，非常适合密码学领域的师生及信息安全从业人员阅读，也适合对密码学及其应用感兴趣的读者阅读。
David Wong是O(1)实验室的一位高级密码工程师，他致力于Mina“加密货币”的研发。在此之前，他曾在Facebook Novi工作，担任Diem（正式名称为Libra）“加密货币”研发团队的安全顾问。在Facebook工作前，他还在NCC集团的加密服务机构做过安全顾问。
David在他的职业生涯中多次参与开源审计工作，比如审计OpenSSL库和Let’s Encrypt项目。他曾在多个会议（如“Black Hat”和“DEF CON”）上做过报告，并在“Black Hat”会议上讲授密码学课程。他为TLS 1.3协议和Noise协议框架的发展做出了贡献。此外，他还发现了许多库存在的漏洞，例如 Go 语言标准库中的CVE-2016-3959漏洞，TLS库中的CVE-2018-12404、CVE-2018-19608、CVE-2018-16868、CVE-2018-16869和CVE-2018-16870漏洞。
David还是Disco协议和基于智能合约的去中心化应用程序安全项目的开发者之一。他的研究内容包括对RSA的缓存攻击、基于QUIC的协议、对ECDSA的时序攻击或针对DH算法的后门攻击等领域的安全技术。
韩露露，暨南大学博士研究生，研究方向为安全多方计算和数据隐私，是《深入浅出CryptoPP密码学库》的作者和《Python编程实战——妙趣横生的项目之旅》的译者。
谢文丽，暨南大学硕士研究生，研究方向为基于格的公钥密码。
杨雅希，暨南大学博士研究生，研究方向为应用密码和隐私计算。
本书封面上的人物是印第安人。这幅插图取自雅克·格拉塞特·德·圣索维尔（Jacques Grasset de Saint-Sauveur，1757—1810）1797年在法国出版的包含不同国家或地区服装合集的书，书名为Costumes de Différents Pays。每幅插图都是手工绘制和着色的。圣索维尔收藏的丰富多样性生动地提醒我们，在200多年前，世界上不同城镇和地区在文化上就存在巨大差异。由于彼此隔绝，人们说着不同的语言。无论是在街道上还是在乡村，仅仅通过他们的衣着就很容易看出他们住在哪里，看出他们的职业或生活状况。
从那以后，我们的着装方式发生了变化，当时各地区的着装风格如此丰富多样，而现在这种多样性在逐渐消失。现在，人们很难通过着装区分不同大陆的居民，更不用说不同的国家、地区或城镇的居民了。也许我们用文化多样性换取了一种更多样化的个人生活——就是一种更多样化、更快节奏的科技生活。
如今，曼宁出版社将雅克·格拉塞特·德·圣索维尔著作中的图片用于封面，以此来说明计算机行业的创造性和主动性。
当拿起本书时，读者可能会有这样的疑惑，为什么又是一本关于密码学的图书？甚至会困惑，为什么要读本书？要想知道这个问题的答案，就必须了解本书的写作过程。
今天，通过使用必应或百度搜索，我们几乎可以了解任何东西。然而，对于密码学，我们可以检索到的知识或资源非常有限。很久以前，我就遇到过这样的情况。从那时起，密码学相关资源的匮乏就成为我钻研密码学的阻碍。
上大学时，有一门课要求我实现差分功耗分析攻击。在密码分析领域，这种攻击在当时算是一个重大突破，它也是第一个公开的侧通道攻击。差分功耗分析攻击是一种非常神奇的密码算法攻击方法，该方法通过测量设备在加密或解密时的功耗，提取出加密算法所使用的密钥。在阅读相关论文时，我意识到，优质的论文可以传达伟大的思想，但很多论文往往不够清晰易懂。那时，我曾使出浑身解数，尝试弄明白作者想表达的意思，但却找不到解释这些论文的在线资源。因此，我绞尽脑汁，最终才彻底读懂这些论文。当时，一个想法在我脑海涌现，我可以想办法帮助像我这样经历这场“磨难”的人。
出于这样的动机，我画了一些动图，以记录我对论文的理解。我还在视频网站上分享了自己制作的密码学视频。
若干年后，每次发布完视频，我仍然能收到网友们的赞扬之词。就在我写这篇序言时，仍有人发帖说：“谢谢你，你的解释非常到位，为我理解这篇文章节省了大量时间。”
对我来说，这是莫大的激励！在迈出这一步后，我就有了在教育领域做更多尝试的想法。我开始录制更多的视频，同时开始写一些关于密码学的博文。在开始撰写本书之前，我已经在博客上发布了近500篇文章，它们解释了许多与密码学相关的概念。实际上，在曼宁出版社（Manning Publications）向我约稿之前，我已经有了写书的想法。
我读完理论数学学士学位后，不知道接下来该从事什么职业。我一直在规划自己的人生，想在职业选择与人生追求之间找到平衡。自然地，我对密码学产生了浓厚兴趣。研究密码学既让我有事情可做，也符合我对人生的规划。于是，我开始阅读各种与密码学有关的图书。很快，我就发现了人生的价值。
很多书总是花费大量篇幅去介绍密码学的发展历史，而我一向只对技术细节感兴趣，因此我发誓，如果我要写一本关于密码学的书，绝不会介绍维吉尼亚密码、凯撒密码和其他陈旧的密码算法。在获得法国波尔多大学的密码学硕士学位后，我本以为自己已做好畅游“实用密码世界”的准备。但实际情况是，我掌握的密码学知识仍然太少。
原本我以为自己的学位已经足够了，但实际上我从学校里学到的知识还不够多，我甚至缺乏攻击现实世界密码协议所需的基本知识。我花了很多时间学习与椭圆曲线有关的数学知识，但并没有学习如何在密码算法中使用椭圆曲线。我还在学校里学习了LFSR、ElGamal和DES算法，以及一系列加密原语，但是后来我再也没见过它们。
我的第一份工作是在Matasano（后来变成NCC集团）审计OpenSSL库，它是一种最为常用的SSL/TLS实现——整个互联网的流量都是基于该协议进行加密的。这份工作让我伤透了脑筋。我记得每天回家后都头痛得厉害。当时，我不知道若干年后自己会成为TLS 1.3协议的开发者。
但是，当时我在想，这些东西是我本应该在学校学习的。而我现在正在学习的才是对现实世界有用的知识。毕竟，在密码学领域里，我也是一位信息安全从业者。我审查过许多现实世界的密码应用程序，这份工作也是许多拥有密码学学位的学生梦寐以求的。我的工作就是实现、验证和使用各种密码学算法，并对具体应用中使用哪种密码学算法给出建议。以上就是我声称自己是本书的第一位读者的原因。我将本书献给过去的自己，证明我为进入实用密码世界做好了准备。
我参与审查了许多现实世界中的密码应用程序，如OpenSSL、谷歌的加密备份系统、Cloudflare的TLS 1.3实现、“Let’s Encrypt”证书颁发授权协议、Zcash“加密货币”协议、NuCypher的门限代理重加密方案，以及其他几十个不能公开的现实世界密码应用程序。
在工作初期，我参与审查了一家知名公司自己定制的安全通信协议。审查结果表明，这个协议可以为除了临时密钥之外的几乎所有信息生成签名。这种做法导致替换临时密钥会很困难，这完全破坏了协议的整体设计原则，绝大多数有安全传输协议开发经验的新手容易犯这样的错误，但即便有足够的安全传输协议开发经验，开发人员仍有可能忽略一些细节。记得在审查即将结束时，我解释了这个漏洞，那时一屋子的工程师几乎沉默了30秒。
这样的情形在我的职业生涯中多次出现。有一段时间，在审查另一个客户的“加密货币”协议时，我发现其使用的签名协议存在二义性，这让我可以从已有交易伪造新的交易。通过检查一个客户的TLS协议实现，我发现了一些攻击RSA实现的巧妙方法。这一发现进一步转化为一份由RSA发明者之一参与撰写的白皮书，它报告了十几个开源项目存在的常见漏洞和弱点。在写本书的时候，我查看了Matrix聊天协议实现。我发现该协议中的身份验证协议存在问题，进而导致协议内置的端到端加密算法易被攻破。不幸的是，在使用密码技术时，有太多的细节可能会被疏忽。此时，我意识到必须写一些与实用密码有关的东西。这也是书中有很多这种轶事的缘由。
我会审查用各种编程语言编写的密码程序库和应用程序，在这个过程中，我发现了许多安全漏洞（例如，在 Go 语言的标准库中发现了CVE-2016-3959漏洞）。我还研究了密码程序库欺骗开发者滥用这些漏洞的方法（请阅读我的论文“How to Backdoor Diffie-Hellman”），并为开发者应该使用哪些密码库给出具体建议。开发人员总是不知道该使用哪些密码库，这是一件非常棘手的事情。
我提出了Disco协议，并用不到1000行代码将它编写成一个功能齐全的密码库，而且这个密码库使用了多种编程语言。Disco协议仅依赖两个密码原语：SHA-3置换和Curve25519曲线。是的，开发人员只需1000行代码就能实现这两个密码原语，进而可以实现认证密钥交换、数字签名、非对称加密、消息认证码、哈希函数、密钥派生函数等密码原语。编写Disco协议的过程为我提供了一个独特的视角，它让我明白一个好的密码库应该包含哪些基本密码原语。
本书包含许多实用见解。具体来讲，每章都包含密码算法的应用示例且它们涉及多种编程语言，同时这些密码算法都来自广泛应用的密码库。
当我在“Black Hat”（一个著名的安全会议）上进行一年一度的密码学课程培训时，一名学生问我是否可以向他推荐一本密码学著作或一门在线课程。我给出的建议是，阅读一本由 Boneh和Shoup撰写的密码学著作，同时也可以在Coursera网站上观看Boneh的密码学课程。
学生告诉我，“啊，我读过那本书，它太理论化了！”学生的回答让我记忆至今。起初我不同意学生的看法，但慢慢地意识到他的说法是对的。大多数资源都包含大量数学知识，大多开发人员都不想处理与数学有关的问题。那他们还有其他学习资源可以选择吗？
《应用密码学》（Applied Cryptography）和《密码工程》（Cryptography Engineering）是另外两本广为人知的密码学著作，这两本书都由布鲁斯·施奈尔（Bruce Schneier）撰写。《应用密码学》总共有4章内容都在介绍分组密码，其中有一章内容讲解分组密码的操作模式，但这本书没有包含认证加密的相关内容。最新版的《密码工程》只在脚注中提到椭圆曲线密码。此外，我的许多视频或博客文章逐渐成为开发人员理解一些密码学相关概念的重要参考资源，我会以独特的方式讲解密码学相关概念。
渐渐地，许多学生开始对“加密货币”产生兴趣，他们向我提出的问题越来越多。与此同时，我审查的“加密货币”类应用程序也越来越多。后来我到Facebook工作，负责Libra“加密货币”（现在称为Diem）的安全。当时，“加密货币”属于最热门的研究，它包含许多非常有趣的加密原语（零知识证明、聚合签名、门限加密、多方计算、共识协议、密码学累加器、可验证随机函数、可验证延迟函数等）。除了“加密货币”之外，到目前为止这些原语几乎没有其他的实际应用。然而，任何一本密码学图书都没有包含与“加密货币”相关的内容。
我意识到通过撰写一本图书，我可以告诉学生、开发人员、顾问、安全工程师和其他人现代应用密码学的几乎全部内容。这将是一本几乎不涉及任何数学公式但会包含许多图示的书。本书不会介绍密码学发展史，但会包含许多我在现实中见到的现代密码失败的案例。本书也不会介绍已成为历史的密码算法，但涵盖正在大规模使用的密码算法或协议，包括TLS协议、Noise协议框架、Signal协议、“加密货币”、硬件安全模块、门限密码等。本书几乎不涉及任何理论密码学的内容，但会包含一些目前处于理论研究而未来可能变得实用的密码学原语：口令认证密钥交换、零知识证明、后量子密码学等。
2018年，当曼宁出版社联系我，问我是否想写一本关于密码学的书时，我的脑海已经有了答案。我早就想写一本关于密码学的书，也想好要写哪些内容，一直在等待一个机会和理由将写书这件事情提上日程。而碰巧曼宁出版社已经出版了“现实世界”（Real World）系列图书，因此我也建议将我的图书作为这个系列的扩展。现在，本书呈现在读者面前，这是我两年多辛勤付出的结果。希望读者能够喜欢本书！
David
从我开始写本书到图书出版已经有几年了。最初，我打算将本书作为介绍现实世界常用密码原语的图书。但是，这显然是一件不可能完成的事情。任何一个领域都不可能用一本书来总结清楚。出于这个原因，我必须在知识的深度和广度之间找到平衡。我希望读者在学习密码学时少走弯路。如果读者正在寻找一本有助于了解密码公司以及产品实现与使用的密码算法类的图书，或者好奇于现实世界密码学的底层机制但不想了解算法的实现细节，那么本书就是你的最佳选择。
这里列出了一些我认为可以从本书中受益的读者。
如果你正在学习计算机科学、信息安全或密码学，并且想了解现实世界中使用的密码学技术（因为你的目标要么是在工业界工作，要么是在学术界从事应用学科研究），那么本书适合作为你的教科书。正如序言中说的那样，我曾经和你一样，也是一名在校的学生，因此我编写了一本自己曾经希望拥有的书。
在教授应用密码学时，我发现大部分学生都是渗透测试工程师、安全顾问、安全工程师、安全架构师和其他安全从业者。因此，当我试图向非密码学从业者解释复杂的密码学概念时，我收到了许多问题，从而改进了相关材料。作为一名安全从业者，在为大公司审核密码应用的过程中，我了解和发现了许多漏洞，这些经历对本书的编写也有着不小的影响。
与客户和同事之间的多次讨论也对我编写本书产生了影响，而他们大都不是安全从业者或密码学家。现今，在不涉及密码学的情况下编写代码变得越来越难，因此，开发人员需要了解自己正在使用的密码学工具。本书包含不同编程语言的代码示例，有利于读者理解这些密码学工具的使用方法。如果读者对此感兴趣的话，还可以进一步参考与本书配套的示例代码。
本书主要介绍的是应用密码学，对于像我这样的应用密码从业者来说，本书很有价值。本书是对我过去所从事工作的总结。如果我能将本书写好，理论密码学家应该能够快速了解应用密码学世界的现状；对称加密研究者通过阅读相关章节能够快速了解口令认证密钥交换协议的本质；密码协议使用者能够快速理解量子密码学的原理；等等。
本书还试图回答一些我认为面向安全产品方面的问题：某种算法在安全性与效率之间做出了何种平衡？使用某种算法可能面对何种安全威胁？某种算法是符合规定的吗？我需要按照规定使用某种算法并且与政府合作吗？
实际上，即便你不是上述的几类读者，只要对现实世界中的密码学感到好奇，你就可以阅读本书。但请记住，我不会介绍与密码学有关的历史，也不会讲解任何计算机科学方面的基础知识。因此，在阅读本书之前，读者应该具备一定的密码学背景知识。
如何才能充分地利用本书呢？本书假设读者对计算机或互联网的工作原理有一些基本的了解，至少应该听说过加密技术。本书讨论的内容是现实世界的密码学，因此，如果读者完全不了解计算机或者从来没有听说过加密这个概念，那么理解本书可能有些困难。
假设读者已经知道本书涵盖哪些领域的知识，那么读者应该了解位和字节，看过甚至使用过像异或、左移之类的位操作，这些背景知识都是读者学习本书的优势。如果没有这些优势，会导致读者无法阅读本书吗？不会，但这可能意味着读者必须花时间去网络上搜索阅读过程中遇到的问题及其解答，才能继续阅读本书。
事实上，无论读者对相关知识了解到何种程度，在阅读本书时，都不得不偶尔停下来，在互联网搜索并了解更多的背景知识。不过，这都不妨碍读者阅读和理解本书，因为我会尽可能解释本书涉及的概念。
最后，当我使用密码学这个词时，读者脑中出现的可能是数学。不过，读者并不需要太过担心。本书主要讨论的是对密码学技术的宏观认识，并尽可能避免从数学的角度讨论它们的本质，这样读者也能够对密码学技术的运作原理有直观的理解。
当然，本书肯定会介绍一部分数学知识，因为讨论密码学就无法避开数学。所以，我想说的是：如果读者的数学基础不错，就会非常有利于读者理解本书的内容。但如果没有数学基础，也不妨碍读者阅读本书的大部分内容。有些章节，特别是最后两章的内容的理解需要读者有比较好的数学基础，通过阅读这些章节以及搜索矩阵乘法和其他相关知识，读者也可以了解相关的数学知识。读者可以选择跳过这些章节，但请不要跳过第16章，因为这章包含一些十分有用的知识。
本书分为两部分。第一部分的内容应该都有必要阅读，这部分涵盖密码学中的许多原语。读者最终会像搭积木一样利用密码原语构建更复杂的系统和协议。
● 第1章对实用密码学进行介绍，让读者了解可以从本书学到的内容。
● 第2章讨论哈希函数相关的知识。哈希函数是一种基本的密码学算法，它可以根据输入的字符串生成一个唯一的标识符。
● 第3章讨论数据认证以及确保消息不被他人篡改的方法。
● 第4章讨论加密算法，加密算法用于确保通信双方交互的消息不会被其他人观察到。
● 第5章介绍密钥交换算法，我们可以通过密钥交换算法与其他人协商出一个秘密值。
● 第6章介绍非对称加密算法，它允许多人给同一个人发送已加密的消息，还介绍了混合加密技术。
● 第7章讨论签名算法，它是现实世界纸质签名在计算机中的等价物。
● 第8章讨论随机数的定义以及生成秘密值的方法。
本书的第二部分介绍基于上述原语构造的密码系统。
● 第9章介绍使用加密以及认证算法保证机器之间安全通信的方法。
● 第10章介绍端到端加密，它讨论通信双方建立信任的方法。
● 第11章介绍机器验证用户身份以及人工辅助机器进行身份认证的方法。
● 第12章介绍一个新兴的密码领域——“加密货币”。
● 第13章重点介绍硬件密码学，也就是可以用来防止密钥泄露的设备。
● 第14章和第15章所涉及的内容（后量子密码和新一代密码技术）相关性越来越高，又或者因为它们变得更加实用和高效，相关的技术已经开始进入工业界。如果读者跳过这两章内容，那也没什么问题，不过读者必须读完第16章。
● 第16章总结密码学从业者必须记住的不同的挑战和不同的经验教训。正如蜘蛛侠的叔叔Ben所说，“能力越大，责任越大。”
本书包含许多源代码示例，源代码都使用等宽字体格式，以便将其与普通文本区分开。有时代码也以粗体显示，以突出显示相关的内容。
大多数情况下，本书中的代码已被重新格式化；我们添加了换行符和重新修改的缩进，以适应书中可用的页面空间。在极少数情况下，这样也不能使内容适应页面空间，我们会在代码清单中使用行延续标记（➥）。此外，当文本已经对代码进行描述时，源代码清单中通常会删除原有的注释。许多代码清单仍附有代码注释，以突出一些重要的概念。
本书由异步社区出品，社区（https://www.epubit.com）为您提供相关资源和后续服务。
本书提供配套资源，请在异步社区本书页面中单击
，跳转到下载界面，按提示进行操作即可。
您还可以扫码右侧二维码， 关注【异步社区】微信公众号，回复“e60034”直接获取,同时可以获得异步社区15天VIP会员卡，近千本电子书免费畅读。
作者和编辑尽最大努力来确保书中内容的准确性，但难免会存在疏漏。欢迎您将发现的问题反馈给我们，帮助我们提升图书的质量。
当您发现错误时，请登录异步社区，按书名搜索，进入本书页面，单击“提交勘误”，输入勘误信息，单击“提交”按钮即可（见下图）。本书的作者和编辑会对您提交的勘误进行审核，确认并接受后，您将获赠异步社区的100积分。积分可用于在异步社区兑换优惠券、样书或奖品。
扫描下方二维码，您将会在异步社区微信服务号中看到本书信息及相关的服务提示。
我们的联系邮箱是contact@epubit.com.cn。
如果您对本书有任何疑问或建议，请您发邮件给我们，并请在邮件标题中注明本书书名，以便我们更高效地做出反馈。
如果您有兴趣出版图书、录制教学视频，或者参与图书翻译、技术审校等工作，可以发邮件给我们；有意出版图书的作者也可以到异步社区在线提交投稿（直接访问www.epubit.com/ selfpublish/submission即可）。
如果您所在的学校、培训机构或企业，想批量购买本书或异步社区出版的其他图书，也可以发邮件给我们。
如果您在网上发现有针对异步社区出品图书的各种形式的盗版行为，包括对图书全部或部分内容的非授权传播，请您将怀疑有侵权行为的链接发邮件给我们。您的这一举动是对作者权益的保护，也是我们持续为您提供有价值的内容的动力之源。
“异步社区”是人民邮电出版社旗下IT专业图书社区，致力于出版精品IT技术图书和相关学习产品，为作译者提供优质出版服务。异步社区创办于2015年8月，提供大量精品IT技术图书和电子书，以及高品质技术文章和视频课程。更多详情请访问异步社区官网https://www.epubit.com。
“异步图书”是由异步社区编辑团队策划出版的精品IT专业图书的品牌，依托于人民邮电出版社近40年的计算机图书出版积累和专业编辑团队，相关图书在封面上印有异步图书的LOGO。异步图书的出版领域包括软件开发、大数据、AI、测试、前端、网络技术等。
异步社区
微信服务号
欢迎来到实用密码学世界！本书分为两部分，每部分均包含8章内容。通过阅读第一部分的内容，读者将学到与现实世界有关的大部分密码学知识。
请注意，尽管每章都会告诉读者应该先了解哪些内容，但本书的第一部分本就是按阅读顺序撰写的，所以不必将每章的前置知识视为强制性约束。前8章将介绍密码学的基础知识，包括一些新的密码原语，并介绍它们的用途、工作原理及其如何与其他密码原语结合起来使用。学习第一部分内容的目的是，让我们在开始学习第二部分之前，对密码学的基础有较好的理解和认识。
祝你好运！
本章内容：
● 密码学的定义；
● 理论密码学与实用密码学之间的区别；
● 本书包含的密码学知识。
你好，旅行者！
请扶好坐稳，我们将进入一个充满奇迹和弥漫着神秘色彩的密码学世界。密码学是一门古老的科学，用于保护易受到恶意用户侵扰的场景。本书将带领读者使用“咒语”来抵御恶意攻击。许多人曾经尝试学习密码学这门科学，但很少有人能经受得住学习之路上面临的挑战，难以真正掌握这门科学。激动人心的冒险旅途在前面等待着我们！
本书将揭示密码算法如何保证我们的信件安全，帮助我们识别“盟友”，保护信息免遭他人窃取。密码学是现实世界中所有安全技术的基础，密码学上的一丁点儿错误都可能带来难以估量的损失，因此探索密码学的旅途注定不会一帆风顺。
记住：
即便发现自己在密码学的海洋里迷失了方向，我们也仍要继续向前航行。请相信，我们终会冲破迷雾，见到光明。
在本次密码学旅行的开始，先向读者介绍密码学的目标：密码学是一门旨在保护协议免受攻击者破坏的科学。那么，协议是什么呢？简单来说，协议是一个人（或者多个人）为了完成某件事情而必须遵循的一系列步骤。想象这样一个情景：旅途疲惫的我们需要小憩一下，不过这样一来我们的“魔剑”可能在数小时内无人看管。这样一个协议的执行过程可能如下：
（1）把武器放在地上；
（2）在树下小睡一会儿；
（3）从地上捡起武器。
当然，在我们睡着的时候任何人都可能偷走我们的“魔剑”，所以这并不是一个好的协议。在密码学中，我们总会把寻找协议破绽的“敌手”考虑进来。
在古代，当统治者和将军们互相背叛并各自策划秘密行动时，他们面临的最大问题就是如何与他们信任的人分享机密信息。在此背景下，密码学的相关概念和技术应运而生。此后，经过几个世纪的演变，密码学成为一门严谨的科学。如今，密码学无处不在，它为我们提供了许多底层服务，让我们能够从容应对这个复杂多变的世界。
本书的内容与密码学的实践应用密切相关。本书涵盖当今广泛使用的各种密码协议，同时还会展示这些密码协议的组成部分，以及这些协议如何有机地组合在一起。大部分的密码学图书都从密码学的发展开始讲，并介绍它的发展历史，但是我认为这样做没有多大意义，我想介绍一些更加实用的东西。我曾以软件顾问的身份为大公司审查与密码相关的应用程序，也曾作为密码工程师将加密技术应用到各个领域。这些在现实中遇到的密码学知识才是我想分享的。
本书不会涉及令人害怕的数学公式。本书的目的是揭开密码学的神秘面纱，介绍当今常用的密码学技术，并给出这些技术在我们身边的应用案例。本书适合那些对密码学怀有好奇心的人、有强烈求知欲的工程师、富有冒险精神的软件开发人员和兴趣广泛的研究人员。
本章旨在带领读者开启密码学世界之旅。我们将探讨不同类型的密码算法，并找到其中对我们很重要的一部分算法，以及阐明全世界一致使用这些算法的原因。
对称加密（Symmetric Encryption）是密码学的重要概念之一。对称密码在密码学中有着举足轻重的地位，本书中的大多数密码算法或协议都用到对称密码。现在，我们借助将要介绍的第一个协议引入对称加密这个新概念。想象这样一个情景：Alice需要给住在城堡外的Bob寄送一封信件。如图1.1所示，Alice要求她忠实的信使（Messenger）骑上他的骏马，穿越前方危险的土地，向Bob传递重要消息。然而，Alice对信使很是怀疑；尽管这位忠实的信使为她效劳多年，但她仍希望此次传递的消息对包括信使在内的所有被动观察者均保密。试想一下，这封信可能包含一些关于王国的流言蜚语。
图1.1 Alice通过信使向Bob发送重要消息
Alice需要的是一个协议，它能模拟Alice亲自将消息传递给Bob的过程。这是一个在现实中不可能解决的问题，除非我们采用密码学（或隐形传输）技术。这就要用到密码学家多年前发明的一种新型加密算法，常称为对称加密算法（Symmetric Encryption Algorithm）。
注意：
顺便说一下，密码学算法通常也被称为密码学原语。我们可以将密码学原语视为密码学中一种最小的算法构造，它通常与其他原语一起用于构造新的协议。“密码学原语”一词经常出现在相关文献中，了解它有利于阅读文献，但它本身确实没有特别的意义，仅仅是一个新的术语而已。
接下来，让我们看看如何使用这个对称加密算法向信使隐藏Alice的真实消息。现在，假设这个密码学原语是一个提供了以下两个函数的黑盒子（我们无法看到它的内部构造）。
● ENCRYPT；
● DECRYPT。
第一个函数ENCRYPT以密钥（Secret Key）和消息（Message）为输入，它输出一系列看起来像是随机选择的数字，如果我们愿意的话，它也可以输出像噪声一样的数据。我们把这个函数的输出称为加密消息。函数ENCRYPT的原理如图1.2所示。
图1.2 函数ENCRYPT以密钥和消息为输入，输出一个加密后的消息（看起来像噪声一样的随机数字序列）
第二个函数DECRYPT是第一个函数ENCRYPT的逆函数，它以ENCRYPT输入的密钥和输出的加密消息为输入，输出原始消息。函数DECRYPT的原理如图1.3所示。
图1.3 函数DECRYPT以密钥和加密消息为输入，输出原始消息
为了使用这个新的密码学原语，Alice和Bob不得不在现实世界中先会面一次，商定他们将要使用的密钥。之后，Alice可以使用商定的密钥和函数ENCRYPT去保护她的消息。接着，她将加密的消息交给信使，并由信使转交给Bob。Bob收到加密的消息后，使用与Alice相同的密钥和函数DECRYPT恢复出原始消息。具体过程如图1.4所示。
图1.4 （1）Alice使用函数ENCRYPT和密钥将消息转变成像噪声一样的随机数字序列；（2）她将加密的消息交给信使，信使无法获知真实消息；（3）Bob一旦收到加密的消息，他就可以使用和Alice一样的密钥和DECRYPT函数恢复出原始内容
在该消息传递过程中，信使拥有的都是看起来随机的消息，这不会对他获得隐藏的消息提供任何有意义的帮助。借助密码学技术，我们有效地将不安全的协议转变为安全协议。新协议使得Alice可以在没有任何人（除Bob外）知道消息内容的情况下向Bob传递一封机密信件。
在密码学中，使一个协议变得安全的常见做法就是：使用密钥将消息转变成噪声，使经过变换后的消息与随机数字序列无法区分开来。在接下来的章节中，我们将通过学习更多的密码算法来了解这个过程。
顺便说一句，对称加密是对称密码（Symmetric Cryptography）或密钥密码（Secret Key Cryptography）的一部分。此类密码学原语的不同函数往往使用相同的密钥。在后面的章节中，我们还会看到密钥有时不止一个。
设计一个密码算法（就像我们前面提到的对称加密原语）是一件简单的事情，但是设计一个安全的密码算法并非易事。虽然本书很少涉及构造这样的密码原语，但是本书会教大家判别一个密码算法优劣的方法。这做起来可能有点困难，因为对于一个给定的任务，我们可能有许多密码算法可以选择。不过，我们可以从密码学历史和密码学社区吸取他人的经验教训，并从中得到一些启示。通过回顾历史，我们可以了解到如何将一个密码算法变成安全可信的算法。
数百年后，依靠信件传递消息的Alice和Bob已经成为历史，纸质信件不再是我们的主要交流方式，取而代之的是更好、更实用的通信技术。如今，我们可以使用功能强大的计算机和互联网。当然，这意味着我们以前面临的恶意信使也变得更加强大。恶意信使无处不在：它可以是咖啡店里的Wi-Fi发射器，也可以是组成互联网并转发信息的服务器，还可以是运行我们算法的计算机。我们的敌手（恶意信使）现在也有能力观察到更多的信息，例如向网站发出的每一个请求都可能通过错误的线路传递，并在几纳秒内被更改或复制，而这一切可能不会有人察觉到。
回顾历史，我们可以清晰地看到密码算法存在漏洞、被一些组织或独立研究人员破解、不能真正地保护消息和未实现设计者所声称功能的例子比比皆是。通过从这些错误中总结经验教训，慢慢地我们知道了设计良好密码算法的方法。
注意：
攻破一个密码算法的方法有很多种。对于加密算法，我们可以通过以下方法来攻击这个算法：将密钥泄露给攻击者、在没有密钥的情况下解密消息、仅仅通过观察加密的消息就可以知道消息本身等。任何对算法假设的削弱也可以认为算法被攻破。
密码学的发展经历了漫长的试错过程，而一个更成熟的观点也在这个过程中产生：为了对密码学原语的安全性获得足够的信心，每个密码原语必须由密码专家对其进行公开分析。若做不到这一点，密码原语的可靠性只能依赖于含糊不清的安全性说明，而历史证明了其效果不尽如人意。这就是密码学家（Cryptographer，密码原语设计者）长期以来需要密码分析者（Cryptanalyst，又称“密码原语分析者”）帮助他们分析所构造密码原语安全性的原因（见图 1.5）。因此，密码学家也常常是密码分析者，反之亦然。
图1.5 密码分析者的主要工作就是帮助密码学家分析所构造密码学原语的安全性
我们以高级加密标准（Advanced Encryption Standard，AES）加密算法为例。AES算法是一个由美国国家标准与技术研究院（National Institute of Standards and Technology，NIST）组织的国际竞赛的产物。
注意：
NIST是一个美国的标准和指南制定机构，其提出的标准主要供美国政府相关职能部门、其他公共和私人组织使用。NIST对许多像AES算法这样应用广泛的密码原语进行了标准化。
AES加密算法竞赛持续了数年之久，其间有许多来自世界各地的密码分析者参与尝试攻击各种各样的候选算法。历经数年的公开分析，人们对候选算法产生了足够的信心，最终将一个最具竞争力的算法提名为AES算法。如今，人们普遍认为AES算法是一个可靠、应用广泛的加密算法。例如，我们每天浏览网页就会用这个算法加密。
以公开方式构造密码算法标准的思路与Kerckhoff原则有关，该原则可以理解为：依靠保密算法来实现安全是不明智的，因为敌手很容易知道我们所使用的密码算法。因此，我们会选择公开密码算法。
如果Alice和Bob的敌手知道他们加密信息的算法，那么他们的加密算法还怎么保证安全呢？答案是密钥。协议的安全依赖密钥，而与算法本身是否保密无关。无论是我们将要学习的密码算法，还是在现实世界中使用的密码算法，我们通常都可以自由地进行研究和使用，这是本书涉及的密码算法的共性。只有作为这些算法输入的密钥才需要保密。就像吉恩·罗伯特·杜卡莱特（Jean Robert du Carlet）所说：“即使对大师来说，艺术也是一个秘密。”在1.4节中，我们将讨论一种完全不同的密码原语。现在，让我们用图1.6来汇总目前已学到的内容。
图1.6 AES是一个对称加密算法实例，对称加密算法是对称密码体系中的一类算法
在前面关于对称加密的讨论中，我们曾提到：Alice和Bob在安全传递信件前需要见面，以确定他们将要使用的对称加密密钥。这是一个合理的要求，许多协议实际上都有这样的前提要求。然而，这样的要求在有许多参与者的协议中很快变得不那么实用：在安全连接到谷歌、Facebook、亚马逊和其他数十亿网站之前，网络浏览器是否也要满足这样的要求（即在连接前，浏览器之间要相互确定使用的对称加密密钥）？
这也称为密钥分发问题，在相当长的一段时间内该问题都未被解决，直到20世纪70年代末密码学家发现了另一类称为非对称密码（Asymmetric Cryptography）或公钥密码（Public Key Cryptography）的算法，密钥分发问题才得以解决。在非对称密码中，不同的函数（ENCRYPT和DECRYPT）使用不同的密钥（对称密码仅使用单个密钥）。为了说明公钥密码如何帮助人们建立信任，我将在本节介绍一些非对称密码原语。注意，这些原语只是本书内容的概览，在后续章节中我们会更详细地讨论这些密码原语。
我们学习的第一个非对称密码原语是密钥交换（Secret Key Exchange）。DH密钥交换算法是密码学家提出的第一个公钥密码算法，该算法以其提出者（Diffie和Hellman）的名字的首字母命名。DH密钥交换算法的主要目的是为通信双方生成一个共享的秘密。这个双方共享的秘密可以用于不同的目的，例如作为对称加密原语的密钥。
在第5章中，我将详细解释DH密钥交换的工作原理。在本小节我们使用一个简单的类比来解释密钥交换。与大多数密码算法一样，在密钥交换算法执行前，参与者也必须获得一组公共参数。在类比说明中，我们用正方形■表示Alice和Bob协商好的公共参数（公共形状）。接下来，他们各自找到一个秘密地点，并随机选择一个形状。假设Alice选择的形状是三角形▲，而Bob选择的是星形★，同时他们会不惜一切代价地保密自己所选的形状。这些随机选择的形状就是他们各自的私钥（Private Key），如图1.7所示。
图1.7 在DH密钥协商的第一步，双方生成私钥。在类比说明中，Alice的私钥是三角形，Bob的私钥是星形
当Alice和Bob选择完私钥后，他们就各自将他们随机选择的形状与他们起初协商的公共形状（正方形）结合起来。这些组合会产生唯一的新形状，每个新形状表示一个公钥（Public Key）。公钥属于公开信息，因此Alice和Bob可以相互交换他们的公钥。该过程说明如图1.8所示。
现在我们来思考这个算法为什么属于公钥密码算法。这是因为此类密码算法的密钥由一个公钥和一个私钥组成。DH密钥交换算法的最后一步相当简单，即Alice和Bob分别将对方的公钥和自己的私钥结合在一起。最终，双方得到完全相同的结果（形状）。在所给的类比示例中，由正方形、星形和三角形组合在一起产生的形状如图1.9所示。
图1.8 在DH密钥协商的第二步，双方交换公钥。双方通过将公共形状和私钥结合在一起来生成公钥
图1.9 在DH密钥协商的最后一步：双方生成共享密钥。为了生成这个密钥，双方都将对方的公钥和自己的私钥结合在一起，而且仅仅通过两个公钥无法生成共享密钥
之后，协议的参与者可以使用这个共享密钥。本书也包含许多共享密钥使用场景的例子。例如，Alice和Bob可以将共享密钥当作对称加密算法的密钥，进而使用这个对称加密原语去加密消息。DH密钥交换的整个过程概括如下：
（1）Alice和Bob交换掩盖了他们各自私钥的公钥；
（2）双方均使用对方的公钥和己方的私钥计算出共享密钥；
（3）敌手通过观察公钥不能获得私钥的任何信息，更不能计算出共享密钥。
注意：
在所给示例中，敌手很容易绕过最后一个问题。因为在不知道私钥的情况下，我们可以将公钥结合在一起生成共享密钥。幸运的是，这只是类比示例本身的局限性，而且并不影响我们理解密钥交换的内部原理。
实际上，DH密钥交换是非常不安全的。你能花上几秒找出其不安全的原因吗？
这是因为Alice接收任何来自Bob的公钥，所以我可以拦截Bob发向Alice的公钥，并用我的公钥替换掉Bob的公钥，这样我就可以冒充Bob（反之，我也可以向Bob冒充Alice）。这样的中间人（Man-in-the-Middle，MITM）攻击者方法可以成功地攻击该密钥交换协议。那么如何修复协议的这个漏洞呢？在第2章我们会看到，修复该协议有两种方法，即用另一个加密原语增强这个密钥交换协议，或者提前知道Bob的公钥。但这不就意味着我们又回到了原点，即如何在协议开始之前确定双方公钥？
先前我们提到，Alice和Bob需要知道一个共同的密钥；现在，我们又要求，Alice和Bob需要事先知道彼此的公钥。双方如何才能知道对方的公钥呢？这不就是一个先有鸡还是先有蛋的问题吗？是的，的确如此。正如我们将看到的一样，在实践中，公钥密码并不能解决信任问题，它只是简化了信任的建立难度（特别是参与者数量有很多时）。
现在，让我们用图 1.10 来汇总目前学到的内容。我们停止讨论该话题，转而继续学习1.4.2小节内容。在第5章中，我们会了解更多关于密钥交换的内容。
图1.10 到目前为止，我们学到的密码算法分属两大类，即对称密码（包含对称加密）和 非对称密码（包含密钥交换）
在DH密钥交换算法提出后不久，密码学家Ron Rivest、Adi Shamir和Leonard Adleman又提出了一个新的密码算法，该算法也以他们的名字命名，称为RSA算法。RSA算法包含两类不同的密码学原语：公钥加密（或非对称加密）算法和（数字）签名算法。这两个密码算法属于非对称密码中两类不同的密码学原语。在本小节中，我们将解释这些原语的功能以及它们在密码协议里发挥的作用。对于非对称加密，其功能与我们前面讨论的对称加密算法类似：它通过加密消息来保证机密性。不过，对称加密中两个参与方使用相同的密钥加密和解密消息，但在非对称加密中加密和解密消息的方式则完全不同：
● 非对称加密有两个密钥，分别称为公钥和私钥；
● 任何人都可以使用公钥加密消息，但是只有私钥拥有者才可以解密消息。
现在，我们用另外一个简单的类比示例来解释非对称加密的使用方法。我们再次从我们的老朋友Alice谈起，假设她持有私钥及其对应的公钥。我们把她的公钥想象成一个打开的盒子，它向公众敞开，任何人均可使用它，如图1.11所示。
图1.11 为了使用非对称加密，Alice首先公开她的公钥（这里用打开的盒子来表示）。任何人都可以使用这个公钥加密向她发送的消息。Alice可以使用私钥解密收到的加密消息
任何人都可以使用Alice的公钥加密发向她的消息。在类比说明中，我们将加密消息想象成把消息放到打开的盒子里并关上它。一旦盒子关上，除了Alice，任何人都没法打开放有消息的盒子。这个盒子有效地保证了消息的机密性，避免第三方获得消息本身。Alice收到关闭的盒子（加密的消息）后，她可以用只有自己知道的私钥打开盒子（解密消息），获得消息，如图1.12所示。
图1.12 非对称加密：（1）任何人都可以用Alice的公钥加密发给她的消息；（2）接收到加密的消息后； （3）她可以用对应的私钥解密，获得消息本身，第三方没法直接观察到发给Alice的消息
我们用图 1.13 总结了到目前为止学到的密码学原语。距离实用密码学之旅结束，我们需要学习的密码学原语只差一个！
图1.13 到目前为止，我们学到的密码算法分属两大类，即对称密码（包含对称加密）和 非对称密码（包含密钥交换和非对称加密）
在1.4.2小节，我们了解了由RSA算法衍生出的非对称加密算法。同时提到，RSA算法还能实现数字签名。数字签名原语能够有效地帮助Alice和Bob建立起信任，它的作用与手写签名十分类似。例如，当租赁公寓时，我们需要在租住合同上签字。
我们可能会产生这样的疑问：如果他们伪造我的签名怎么办？确实，手写签名在现实世界中并不能提供足够的安全性。密码上的签名也可能伪造，但是密码签名还会提供一个带有签名者姓名的密码证书。这能保证密码签名不可伪造，进而让别人很容易验证签名。与在支票上写的古老签名相比，密码签名更加有用！
在图1.14中，我们想象这样一个场景：Alice想向David证明她信任Bob。这是一个在多方环境中建立信任以及非对称密码技术使用场景的典型例子。Alice通过在一张写有“Alice信任Bob”的纸上签名来表明立场，并告诉David：Bob是可以信任的。如果David信任Alice和她的签名算法，那么他也可以选择信任Bob。
具体来说，就是Alice用她的RSA签名算法以及私钥对消息“Alice信任Bob”签名。这会产生一个类似随机噪声的签名，如图1.15所示。
图1.14 David信任Alice。如果Alice信任Bob，那么David也可以信任Bob吗
图1.15 Alice用她的私钥生成消息的签名
任何人都可以通过以下信息验证这个签名：
（1）Alice公钥；
（2）待签消息；
（3）消息的签名。
验证结果只能是真（签名有效）或者假（签名无效），如图1.16所示。
图1.16 为了验证Alice的签名，验证者还需要待签消息本身和Alice的公钥。验证结果只能是签名有效或者无效
到现在为止，我们已经学了3个不同的非对称密码原语：
（1）DH密钥交换；
（2）非对称加密；
（3）RSA数字签名。
这是3个非常著名且应用广泛的非对称密码算法。这些算法对于解决现实世界的安全问题所发挥的作用可能不会十分明显，但是这些算法确实每时每刻都在保护着我们所触及的各类应用。现在，让我们还用图来总结到目前为止我们学到的所有密码算法，如图1.17所示。
图1.17 到目前为止，我们学过的对称密码算法和非对称密码算法
我们将密码算法分为两大类。
● 对称密码（密钥密码）——算法只有一个密钥。如果多个参与者都知道该密钥，该密钥也称为共享密钥。
● 非对称密码（公钥密码）——参与者对密钥的可见性是非对称的。例如，一些参与者仅知道公钥，而另一些参与者同时知道公钥和私钥。
虽然对称密码和非对称密码并不是密码学中仅有的两类原语，但是由于我们很难对密码学的其他的子类进行划分，所以本书的大部分篇幅都是关于对称和非对称密码原语的。当今广泛应用的密码算法都包含在这两类原语中。另一种划分密码学原语的方式如下。
● 基于数学理论构造——这种密码算法的构造都建立在诸如因子分解之类的数学困难问题上。基于RSA算法的数字签名和非对称加密就属于这种构造。
● 基于启发式构造——这种算法的构造依赖于密码分析者的观察和统计分析。AES算法就是这种构造的典型案例。
这种分类方式还考虑到算法效率因素，基于数学理论构造通常比基于启发式构造的密码算法要慢得多。我们可以得出这样的结论：对称密码大多数都是基于启发式构造的，而非对称密码主要是基于数学理论构造的。
我们很难严格地对密码学涉及的所有算法进行准确分类。事实上，每本书或每门课程对密码学定义和分类都有所不同。其实，这些定义和分类对我们来说并不重要，因为我们只会将这些密码学原语看作独特且具有各自的安全声明的工具。反过来，我们可以把这些工具当作构造安全协议的基础原语。对于实现协议安全，了解这些工具的工作原理以及提供的安全声明才是重中之重。出于这种考虑，本书的第一部分主要介绍常用的密码原语及其安全属性。
本书中的许多概念在初次使用时可能比较难懂。但与学习和理解其他知识一样，对这些概念了解得越多，在具体语境中见到的次数越多，我们就越能把它们抽象出来，理解起来也就愈加自然。本书的作用就是帮助读者建立起密码算法构造的抽象思维模型，理解把各类密码算法组合在一起形成安全协议的方法。本书会反复提到各类密码原语构造的接口，给出它们在现实世界的实际使用示例。
密码学以前的定义很简单，其原理类似于Alice和Bob想要交换秘密信息。当然，现在密码学的定义已经有了变化。当今，密码学围绕着新的发现、突破和实际需求演变成一门非常复杂的学科。归根结底，密码学的真正目的在于增强协议安全性，使协议在敌手存在的情况下仍能安全运行。
为了准确地理解密码学使协议变得安全的原理，厘清协议所要达到的一系列安全目标至关重要。本书涉及的密码原语至少满足下面性质中的一条。
● 机密性——掩藏和保护一些不想让别人看到的消息。例如，加密就可以掩盖传输中的消息。
● 认证性——确定通信另一方的身份。例如，认证技术可以让我们确信接收到的消息确实是由Alice发送来的。
当然，这里只是对密码学所能提供的算法功能进行了简化。在大多数情况下，每个密码原语的安全定义中都包含对算法功能的详细说明。密码原语的使用方式不同，协议产生的安全属性也会不同。
在本书中，我们将会学习一些新的密码原语，同时还会学习将它们组合起来实现满足机密性或认证性等安全属性的方法。请认识到这样一个事实：密码学是一门在敌手存在的环境下为协议提供安全保护的技术。虽然本书对“敌手”还没给出明确的定义，但是我们可以把企图破坏协议的参与者、观察者、中间人都当作敌手。这些角色反映了现实生活中敌手可能的身份。毕竟，密码学是一个实用的领域，它最终对抗的坏人是有血有肉的。
1993年，Bruce Schneier出版了《应用密码学》（Applied Cryptography）一书，该书旨在帮助应用程序开发者和软件工程师构建密码学应用。2012年前后，Kenny Paterson和Nigel Smart发起了一个名为“Real World Crypto”的年度会议，该密码学会议仍面向程序开发者和软件工程师。那么，应用密码学和实用密码学指的是什么？密码学难道不止一种吗？
要回答这些问题，我们还须从理论密码学（密码设计者和密码分析者所研究的密码学）的定义开始谈起。理论密码学研究者大多来自学术界和高校，但有少部分人可能来自工业界和政府特定部门。这些研究者的研究领域涉及密码学的各个方面，他们通过在期刊和会议上发表论文和演讲的形式向本领域的同行们分享最新研究成果。然而，并非每个研究者所做的研究都能在实际环境下应用。通常，这些研究者也不会对所提概念进行实证或进行代码实现。世界上甚至也不存在足以运行这些研究的计算机，所以这样的研究通常对现实应用没有多大意义。话虽如此，理论密码学有时也会走向实用密码学这一边，进而变得更有实用价值。
与理论密码学相对立的另一边是应用密码学（Applied Cryptography）或实用密码学（Real-world Cryptography）。实用密码学（应用密码学）是保证现实应用安全的基础。人们在现实生活中几乎感受不到实用密码学的存在，也无法直接看到它的具体应用。但是，当在互联网上登录银行账户，或向好友发送消息时，实用密码学技术就开始发挥作用了。实用密码学无处不在，不幸的是，不断观察和尝试破坏系统的攻击者也无处不在。实用密码学领域的工作者大多来自工业界，但他们有时也需要学术界的研究者帮助他们审查算法和设计的协议。实用密码学的研究结果也会通过会议、博客、帖子和开源软件等共享出来。
通常，实用密码学非常关心一些现实需求：算法提供的确切安全级别是多少？算法的运行时间是多长？密码原语要求的输入和输出有多大？我们可能已经猜到，本书的主题是实用密码学。虽然理论密码学并非本书主题，但在最后几章中我们会了解一些密码学家的前沿研究。等着吧，实用密码学未来的发展会让我们感到吃惊的。
现在，我们可能会有疑问：开发人员和工程师在实际应用中怎样选择和使用密码原语？
在密码学领域金字塔上面的是提出并解决数学难题的密码分析师，在金字塔下面的是希望加密某些数据的软件工程师。
——Thai Duong （“So you want to roll your own crypto?”，2020）
在研究和使用密码学的这些年里，我从未见过以单一模式在实际应用程序中使用密码原语的例子。现实情况是，密码学的使用方式相当混乱。在某一理论原语被采用前，会有很多的密码学研究者对其进行研究和分析，最终将其变成更实用、更安全的密码学原语。我该怎么解释这些呢？
听说过Choose Your Own Adventure一书吗？这是一个相对老旧的故事集，我们必须选择逐步完成故事中的任务。原则很简单，先按顺序阅读，然后通过书中提供的一些选项让我们决定接下来选择阅读哪一部分。每个选项都与一个不同的节号相关联，我们可以直接跳到所选节号的内容。因此，我也按照这种方式安排本书内容。从下一段开始，我们可以按照本书所给顺序去读本书。
一切从这里开始。你是谁？你是密码学家Alice吗？还是在私企工作而且有问题亟待解决的David呢？或者你是在特殊部门工作，专门从事密码学研究的Eve？
● 如果你是Alice，请跳到步骤1。
● 如果你是David，请跳到步骤2。
● 如果你是Eve，请跳到步骤3。
步骤 1：研究人员必须进行研究。你是一位在大学工作的研究员，或者是一名任职于私人公司或非营利组织的研究者，或者你就职于NIST或NSA等美国政府研究机构。因此，你的研究资助可能来自不同的机构或组织，这可能会激励你研究不同的东西。
● 你会发明一个新的密码原语，请跳到步骤4。
● 你会提出一个新的构造，请跳到步骤5。
● 你打算参与一场密码竞赛，请跳到步骤6。
步骤 2：工业有需求。工作任务就是提出新的行业标准。例如，Wi-Fi联盟就是一个由专注于Wi-Fi协议的公司资助的非营利组织，该组织旨在制定一套有关Wi-Fi协议的标准。另一个与标准工作有关的例子是，多家银行联合制定支付卡行业数据安全标准（The Payment Card Industry Data Security Standard，PCI-DSS），在处理信用卡号时，该标准会强制要求使用规定的算法和协议。
● 你决定去资助一些需要的研究，请跳到步骤1。
● 你决定提出一些新的原语或协议，请跳到步骤5。
● 你打算发起一场密码算法竞赛，请跳到步骤6。
步骤 3：政府有需求。你为政府效力，需要设计一些新的密码算法。例如，NIST的任务就是发布联邦信息处理标准（The Federal Information Processing Standard，FIPS），该标准规定了处理政府事务的公司可以使用哪些密码算法。虽然这些标准中大多是成功的案例，人们对政府机构推行的标准也抱有高度的信任，但是关于这些标准的失败之处也值得一谈。
2013年，在爱德华·斯诺登（Edward Snowden）披露了一些美国政府的丑闻之后，人们发现美国国家安全局（NSA）故意将一个藏有后门的算法纳入其推行的标准中（见Bernstein等人的文章“Dual EC: A Standardized Back Door”），这个后门算法允许NSA（只有NSA）推测密钥。这些后门如同“魔法口令”一样，使美国政府（据说只有美国政府）可以破解加密的消息。之后，密码社区不再信任美国政府机构推出的标准和建议。在2019年，人们发现俄罗斯标准机构GOST也出现类似的情况。
密码学家一直怀疑GOST在2006年发布的一项NIST通过的标准中植入了漏洞，后来这项标准被由拥有163个成员方的国际标准化组织（International Organization for Standardization）采纳。而美国国家安全局的机密备忘录似乎也能证实：两位微软密码学家在2007年发现该标准中的致命弱点是由GOST机构设计的。值得注意的是，正是NSA编写了该标准，并积极在国际组织上推行该标准，并私下称其为“技巧上的挑战”。
——《纽约时报》（“N.S.A. Able to Foil Basic Safeguards of Privacy on Web”，2013）
● 你要资助一些研究，请跳到步骤1。
● 你要组织一场公开竞赛，请跳到步骤6。
● 你打算将正在使用的原语或协议标准化，请跳到步骤7。
步骤4：提出新概念。作为一名研究人员，总是设法做到一些不可能完成的事情；确实，尽管可用的加密原语已经有很多，但密码学家每年仍会提出一些新的原语。其中，有些概念是不可能实现的，而有些概念最终可以实现。也许，你已有实际的构造，并将其作为所提原语的一部分，或者选择等待，看看是否有人可以想出一些新的原语。
● 你提出的原语已经实现，请跳到步骤5。
● 你提出的原语最终不可以实现，请跳到开头部分。
步骤5：一个新的原语或协议被提出。密码学家通过提出一种新的算法来实例化一个概念。例如，AES是一个加密方案（AES最初由Vincent Rijmen和Joan Daemen提出，他们用其名字的缩写Rijndael来命名这个算法，又称Rijndael加密法）。下一步该怎么做呢？
● 某个人以你的构造为基础提出新的构造，请跳到步骤5。
● 你参加了一个公开的比赛，并且赢得这场赛事！请跳到步骤6。
● 你所做的工作受到大肆宣传，并且即将成为标准，请跳到步骤7。
● 你决定将你的构造申请成专利，请跳到步骤8。
● 你或其他人认为你构造的原语非常有趣，并决定将该构造实现出来，请跳到步骤9。
步骤 6：算法在竞赛中获胜。密码学家最喜欢的竞技就是一场公开的比赛！例如，AES就是一项由世界各地密码学研究者都可自由参加的竞赛。整个竞赛经过数十次的提交和几轮密码分析者的分析（这可能需要几年时间），候选算法名单中的算法逐渐减少，直至剩下一个算法，便将该算法作为标准。
● 你很幸运，经过多年的竞争，你的新构造最终赢得比赛！请跳到步骤7。
● 你不够走运，输掉了比赛，请回到开头。
步骤 7：标准化算法或协议。标准通常由政府或标准化机构发布。标准化的目的是最大限度地提高互操作性。例如，NIST会定期发布一些密码标准。著名的密码学标准化机构当属国际互联网工程任务组（Internet Engineering Task Force，IETF），本书中涉及的许多互联网标准（如TCP、UDP、TLS等）都出自该机构。IETF中的标准被称为征求意见（Request For Comment，RFC），并且几乎任何想要编写标准的人都可以编写。
为了强调不通过投票表决问题，我们还采用了“决议”的传统：例如，在面对面的会议中，工作组主席为了让大家获得“决策权”，有时会要求参会者就一个特定的问题（“赞成”或“反对”）进行交流，而不是举手表决。
——RFC 7282（“On Consensus and Humming in the IETF”，2014）
有时，某个公司会直接发布一个标准。例如，RSA Security LLC（由RSA算法的创建者出资）为了让本公司使用的算法和技术合法化，曾发布了15个称为公钥加密标准（Public Key Cryptography Standards，PKCS）的技术文件。如今，这种情况非常少见。现在，许多公司都是通过IETF将它们的协议或算法标准化为RFC文档，而不是去自定义一些新的标准化文档。
● 你提出的算法或协议得到实现，请跳到步骤9。
● 没有人关心你发布的标准，请回到开头。
步骤 8：专利到期。通常，密码算法被申请了专利就意味着没有人会使用该算法。然而，一旦专利到期，人们会对这个算法重新产生兴趣，这并不是什么罕见之事。最典型的例子可能是Schnorr签名，该算法是一个备受欢迎的签名算法，这种情形持续到1989年Schnorr为该签名算法申请专利。这导致NIST只能将一个较差的签名算法作为标准，称为数字签名算法（Digital Signature Algorithm，DSA），该算法在当时成为首选签名算法，但如今很少使用。Schnorr签名的专利于2008年到期，此后该算法再次流行起来。
● 时间过了很久，你提出的算法仍无人过问，请回到开头。
● 你的构造引发了一系列新的构造，这些新的构造都以你先前的构造为基础，请跳到步骤5。
● 现在很多人想使用你的构造，但只有你的构造成为标准后他们才肯使用，请跳到步骤7。
● 一些开发者正在使用你设计的算法，请跳到步骤10。
步骤9：实现一个新的构造或协议。实现者不仅要完全搞懂一篇论文或一项标准（尽管标准的撰写本来就应该是面向实现者的），而且必须使实现的算法易于使用，这是一项艰巨的任务。另外，使用者还可能会以一种错误的方式使用密码算法，因此做到正确使用密码算法也并非易事。
● 有人认为标准本身应该包含相应的实现，不提供具体实现的标准不够完备，请跳到步骤7。
● 你编写的密码程序库得到极力推广，请跳到步骤10。
步骤 10：作为开发人员在应用程序中使用密码协议或原语。你的密码程序库可以轻松满足开发人员的需要！
● 某个原语可以解决你的需求，但它没有被标准化。情况有点不好，请跳到步骤7。
● 我希望用我熟悉的编程语言实现这个原语，请跳到步骤9。
● 我以错误的方式使用这个密码库，或者使用的构造已被攻破，游戏结束。
让一个密码原语变得在现实世界可用的方法有很多。最好的方法应该是采用经过多年的安全分析、对算法实现者友好的标准，以及性能良好的密码程序库。最糟糕的方法是使用不安全的算法和不友好的实现。一个密码原语变得实用的最佳路线如图1.18所示。
图1.18 一个密码算法的理想生命周期始于密码学家实例化了某个概念。例如，AES是对称加密概念的一个实例（对称加密算法还有很多）。一个新的密码原语构造可以这样被标准化：每个人都同意以某种方式来实现它以最大限度地提高互操作性。然后，用不同的语言实现该标准，使标准化的密码算法得以广泛应用
无论是那些业余的密码学爱好者，还是那些顶尖的密码学家，他们都能设计出一种自己无法破解的密码算法。
——Bruce Schneier (“Memo to the Amateur Cipher Designer”, 1998)
在这里我们必须知道这样一个事实：密码学是一门很难完全掌握的技术。读完本书后就去尝试设计复杂的密码协议是一种不明智的做法。在这段密码学之旅中，本书的目的是给大家带来一些启发，告诉大家密码学能够做什么，让大家理解一些密码学技术的原理，但无法让大家成为密码学大师。
本书不是密码学圣经。本书的最后会告诉大家一条重要的经验——不要独自进行密码学上的冒险。为了打败可以“杀人”的“恶龙”，我们需要一些持续不断的支持。换句话来说，密码学是复杂的，本书的主要作用就是不让我们滥用所学的密码学知识。对于设计复杂的密码学系统，唯有在密码学领域深耕多年的专家才能胜任。本书主要让大家明白哪些场合该用密码技术，或者什么样的使用方式应该受到怀疑，使用哪些密码原语和协议才能解决大家正面临的问题，以及所有这些密码算法的底层原理。如果已经了解了这些警示之言，那就开始学习下一章内容吧！
● 协议是一个参与者通过逐步交互实现机密信息交换的过程。
● 密码学是一门考虑在敌手存在的条件下使协议变得安全的学科。其中的实现过程经常需要密钥。
● 一个密码学原语指的是一类密码算法。例如，对称加密是一个密码原语，而AES是一个具体的对称加密算法。
● 对不同的密码学原语可按多种方式分类，其中一种方式是将它们分为两类：对称密码和非对称密码。对称密码只有一个密钥（如对称加密），而非对称密码有多个不同的密钥（如密钥交换、非对称加密和数字签名）。
● 按照密码算法的性质很难对其进行分类，但这些算法通常主要提供两个基本功能：认证性和机密性。认证性是指验证某些消息或人的真实性，而机密性是指数据或身份的隐私性。
● 实用密码学在实际的技术应用中无处不在，而理论密码学在实践中往往用处不大。
● 本书中包含的大多数密码学原语都是经过标准化才确定下来的。
● 密码学本身非常复杂，在实现和使用密码学原语时需要多加小心。
读者服务：
微信扫码关注【异步社区】微信公众号，回复“e60034”获取本书配套资源以及异步社区15天VIP会员卡，近千本电子书免费畅读。
本章内容：
● 哈希函数的定义及其安全性质；
● 目前广泛采用的哈希函数；
● 现有的其他类型哈希函数。
在本章中我们学习的第一个密码学原语就是——哈希函数（Hash Function），它可以给任何数据生成一个全局唯一的标识符。哈希函数在密码学中随处可见！非正式地说，哈希函数以任意值为输入，并输出一个唯一的字节串。给定相同的输入，哈希函数总是产生相同的字节串。这可能看起来没什么，但在密码学中，许多算法都是基于哈希函数构造的。在本章中，我们将了解到关于哈希函数的所有知识，以及它应用广泛的原因。
现在，我们可以看到一个网页（见图2.1），而下载（DOWNLOAD）按钮占据该网页的大部分空间。通过单击下载（DOWNLOAD）按钮，我们会跳转到一个包含待下载文件的网站。在这个按钮的下面有一长串难以理解的字符串：
f63e68ac0bf052ae923c03f5b12aedc6cca49874c1c9b0ccf3f39b662d1f487b
后面还有一串看起来像某种首字母缩略词的字符（sha256sum:）。这个字符串看起来是不是有点眼熟呢？在生活中，我们可能也下载过附带类似字符串格式的文件。
我们可以利用这个长字符串按照如下步骤来检测文件的完整性：
（1）点击按钮来下载文件；
（2）采用SHA-256算法来计算下载文件的哈希值；
（3）将哈希函数的输出（摘要）与网页上显示的字符串进行比较。
这个字符串还可以帮助我们验证下载的文件是否正确。
图2.1 该网页链接到包含一个文件的外部网站。该网页提供了该文件的哈希值，因为哈希值可以保证外部网站无法随意修改文件内容而不被察觉。该文件的哈希或摘要确保了下载文件的完整性
注意：
哈希函数的输出通常被称为摘要（Digest）或哈希值（Hash）。本书将交替使用这两个词。其他书可能会称哈希函数为校验和（Checksum），但因为这个术语主要用于指代非密码学的哈希函数，所以本书没有使用这个名词。我们只需要牢记，不同的代码库或文件会使用不同的术语。
当我们想要尝试计算哈希值时，可以使用流行的OpenSSL库。该库提供了一个多用途的命令行接口（Command Line Interface，CLI），macOS之类的许多系统中自带该命令行工具。例如，打开终端并输入如下命令：
$ openssl dgst -sha256 downloaded_file
f63e68ac0bf052ae923c03f5b12aedc6cca49874c1c9b0ccf3f39b662d1f487b通过上述命令，我们可以使用SHA-256哈希函数把输入（下载的文件）转化为一个唯一的标识符（命令返回的值）。执行这些额外操作的目的是，检验文件的完整性（Integrity）和真实性（Authenticity），保证下载的文件确实是我们想要的。
这些工作，要归功于哈希函数的安全性质——抗第二原像性。这个术语意味着从这个哈希函数的长输出f63e...中，我们无法推断出另一个文件也可以通过相同的哈希函数得到相同的输出f63e...。在实践中，这意味着该摘要与正在下载的文件密切相关，没有攻击者能够不知不觉地将原文件替换为不同的文件。
十六进制编码
顺便说一下，上面的字符串f63e...采用的是十六进制（Base16编码，使用从0到9的数字和从a到f的字母来表示任意数据）表示形式。我们本可以用包含0和1的二进制编码方法表示哈希函数的输出，但这样会占用更多空间。十六进制编码允许我们将8比特（1字节）数编码成2个字符。这种编码方式具有可读性强、占用的空间少的优点。我们还可以使用其他的编码方法将二进制数据编码成可读字符，但十六进制编码和Base64编码是使用最多的两种编码方式。在Base系列编码中，基越大，编码二进制数据需要的字符数就越多。当然，如果用的基过大，我们可能就无法用已有的可读字符编码二进制数据。
请注意，这个长字符串由网页的所有者控制，任何能够修改该网页的人都可修改该字符串。（如果不相信这一点，请花点儿时间思考一下原因。）因此，为了确保文件的完整性，我们需要信任包含摘要字符串的网页、网页的所有者以及获取网页页面的安全机制，而不必信任包含下载文件的网页。从这个意义上说，单独使用一个哈希函数并不能提供完整性。因为下载文件的完整性和真实性来自文件摘要以及摘要的可信机制（在本例中为HTTPS）。我们将在第9章讨论HTTPS，但现在我们先假设该协议允许我们与网站进行安全通信。
我们可以将哈希函数看作图2.2中的黑匣子。我们的黑匣子接收一个输入并产生一个输出。
图2.2 哈希函数可以接收任意长度的输入（文件、消息、视频等）并产生固定长度的输出（例如，SHA-256算法的输出为256比特）。对于同一个哈希函数，相同的输入会产生相同的摘要或哈希值
哈希函数的输入可以是任意大小，甚至可以是空值，而它的输出的长度总是固定的，且具有确定性：给定相同的输入，哈希函数总是产生相同的输出。在我们的示例中，SHA-256始终提供256比特（32字节）的输出，它的输出终被编码为64个十六进制字符。哈希函数的一个主要特性是无法求逆，也就是说无法从输出中找到输入。因此，我们说哈希函数是单向（One-way）的。
为了说明哈希函数在实践中的工作原理，我们将使用OpenSSL命令行工具中的SHA-256哈希函数计算不同输入的哈希值。在OpenSSL命令行工具中，SHA-256算法的输入和输出如下所示：
$ echo -n “hello” | openssl dgst -sha256
2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824
$ echo -n “hello” | openssl dgst -sha256 ←--- 对同样的输入计算哈希值，会得到相同的输出
2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824
$ echo -n “hella” | openssl dgst -sha256 ←--- 对哈希函数的输入内容的细微修改会得到完全不同的哈希值
70de66401b1399d79b843521ee726dcec1e9a8cb5708ec1520f1f3bb4b1dd984
$ echo -n “this is a very very very very very very ←--- 无论输入的消息有多长，哈希函数输出值的长度总是固定的
➥ very very very long sentence” | openssl dgst -sha256
1166e94d8c45fd8b269ae9451c51547dddec4fc09a91f15a9e27b14afee30006在2.2节中，我们将看到哈希函数的其他性质。
通常，应用密码学定义的哈希函数具有3个特定的安全属性。这个定义会随着时间的推移而改变，我们将在2.3节中给出这些性质的详细描述。但是现在，让我们先定义构成哈希函数的三大基础属性。这些内容对于了解哈希函数的适用场合非常重要。
哈希函数的第一个属性是抗第一原像性（Pre-image Resistance）。这一属性表示无法根据哈希函数的输出恢复其对应的输入。在图2.3中，我们可以把哈希函数想象成一个搅拌机，这种“单向性”意味着我们无法从“搅拌后的冰沙”中恢复出原始成分。
图2.3 从技术上讲，给定哈希函数（图中表示为搅拌机）生成的摘要， 不可能推导出它的原始输入。这种安全属性称为抗第一原像性
注意：
如果输入值很小，那是否就能找到原始输入呢？假设输入的可取值是oui或non，那么攻击者很容易对所有可能的3个字母的单词进行哈希并找出输入值。所以，当输入空间很小时，我们就需要对输入的变体计算哈希值。此外，当需要计算哈希值的内容是一个句子时，例如，“我将在星期一凌晨3点回家”，尽管攻击者不知道具体的时间，但是他可以尝试所有可能的时间组合，从而猜测出原始输入。因此，抗第一原像性有一个明显的前提：输入空间不能太小且要具有不可预测性。
哈希函数的第二个属性是抗第二原像性（Second Pre-image Resistance）。前面提到的文件完整性验证示例就用到这个安全性质。该性质说明如下：给定一个输入和它的哈希值，无法找到一个不同于该输入的新输入，使得这两个输入产生一样的哈希值。图2.4说明了哈希函数的这一性质。
图2.4 给定一个输入及其摘要，无法找到哈希值相同的另一个不同的输入。这种安全属性称为抗第二原像性
请注意，在图2.4中，第一个输入是固定的，我们只能控制第二个输入。这对于理解哈希函数的下一个安全性质很重要。
哈希函数的第三个属性是抗碰撞性（Collision Resistance）。这个性质保证不能够产生哈希值相同的两个不同的输入（见图2.5）。在图2.5中，攻击者可以改变两个输入，这与之前只准改变其中一个输入的要求不同。
图2.5 无法找到哈希值（右侧）相同的两个不同的输入（在左侧表示为两个随机数据块）。 这种安全属性称为抗碰撞性
抗碰撞性和抗第二原像性很容易混淆。我们需要花点儿时间来了解它们之间的差异。
随机预言机（Random Oracle）
此外，我们认为哈希函数的输出是不可预测且随机的。这样的性质对证明协议的安全性非常有用，这一切都要归功于哈希函数具有的安全性质（例如抗碰撞性）。密码学中的许多协议都在随机预言机模型下被证明是安全的，证明过程中使用了一个虚构的理想参与者，即随机预言机。在这种类型的协议中，人们可以将任何输入作为请求发送到该随机预言机，它会返回完全随机的输出，且与哈希函数一样，对于两次相同的输入返回相同的输出。
用这样的模型证明算法的安全性有时会引起争议，因为我们不确定在实践中是否存在能够替换这些随机预言机的哈希函数。不过，许多合法协议已经被证明在随机预言机模型下是安全的，其中所使用的哈希函数比真实函数更理想。
到目前为止，我们列举了哈希函数的3个安全属性：
● 抗第一原像性；
● 抗第二原像性；
● 抗碰撞性。
这些安全属性本身是没有意义的，哈希函数的安全性取决于我们使用它的方式。然而，在我们学习哈希函数的一些现实应用之前，需要了解哈希函数的一些局限性。
首先，哈希函数满足这些安全属性的前提是，我们应以正确的方式使用哈希函数。假设有一个场景，对单词yes或no进行哈希处理，然后发布它们的摘要。如果我们想知道哈希结果对应的是哪个单词，我们可以简单地对yes和no这两个单词进行哈希处理，并将计算的结果与发布的结果进行比较。这是因为这个过程不涉及任何秘密，而且我们使用的哈希算法是公开的。人们可能会认为这不符合哈希函数的抗第一原像性，但其实这是因为输入不够“随机”。此外，因为哈希函数可以接收任意长度的输入并且总是产生相同长度的输出，所以就可能有无数个输入会得到相同的输出值。这下人们可能会说，“好吧，这不是打破了抗第二原像性吗？”，但抗第二原像性的定义只是说很难找到另一个输出值相等的输入，所以我们假设它在实践中是不可能找到另一个输入的，但在理论上这并非不可能。
其次，哈希函数输出的摘要大小对其安全性也很重要，但这不仅仅是哈希函数的特性。所有密码算法在实践中都必须关心其参数的大小。让我们想象下面这个极端的例子。我们有一个哈希函数，它以均匀随机的方式产生长度为2比特的输出（这意味着它将在25%的时间内输出00，在25%的时间内输出01，以此类推）。在这种情况下，我们不需要做太多的工作来制造冲突。在对一些随机输入字符串进行“哈希”后，应该就能够找到两个哈希值相同的输入比特串。出于这个原因，在实践中会要求哈希函数的输出长度不能低于256比特。对于这么大的输出空间，除非在实际计算方面有所突破，否则几乎不可能发生碰撞。
那这个数字（256）是怎么得来的？在现实世界的密码学中，算法的安全级别不能低于128比特。这意味着想要破坏算法（提供128位安全性的算法）的攻击者必须执行大约2128次操作（算法的输入长度为128比特，尝试所有可能的输入字符串将需要2128次操作）。为了满足前面提到的3个安全属性，哈希函数的安全级别至少要是128比特。对哈希函数最简单的攻击通常是找到由于生日界限引起的碰撞。
生日界限（Birthday Bound）
生日界限源于概率论，其中生日问题（一个房间里至少需要多少人，才能使得两个人生日相同的概率至少达到50%）揭示了一些不直观的结论。事实证明，随机抽取23个人，他们中有两个人生日相同的概率就足以达到50%！这确实是个很奇怪的现象。
这个现象被称为生日悖论。实际上，当我们从2N种可能性的空间中随机生成字符串时，在已经生成大约2N /2个字符串后，发现碰撞的概率为50%。
如果哈希函数产生256比特的随机输出，那么所有输出的空间大小为2256。这意味着，在生成了2128个摘要后（由于生日界限），发现碰撞的概率就很高了。但2128就是我们想要达到安全目标所需要的最大操作次数。这就是哈希函数至少要提供256比特输出的原因。
受某些因素的限制，有时会促使开发者通过截断（Truncating）的方式（删除一些字节）减少摘要的长度。在理论上这是可行的，但是会大大降低哈希函数的安全性。为了实现128比特安全性这个最低的安全目标，在以下情况下不能截断摘要：
● 为了满足抗碰撞性，摘要长度至少是256比特；
● 为了满足抗第一原像性和抗第二原像性，摘要长度至少是128比特。
也就是说，哈希函数的摘要是否可以被截端取决于具体方案所依赖的哈希函数的属性。
正如我们前面所说，哈希函数在实践中很少单独使用。它们常与其他元素结合，以构建一个密码原语或密码协议。在本书中，我们将列举许多使用哈希函数来构建更复杂对象的例子，不过本节将介绍现实世界中使用哈希函数的几种不同方式。
想象一下，如果我们知道了市场上的一只股票会增值，并在未来一个月达到50美元/股，虽然我们不能在当时告诉朋友（也许是出于某种法律原因），却还是希望可以在事后告诉朋友我们早知道这件事了。那么，我们就可以对一句话生成一个承诺，如计算“股票X下个月将达到50美元/股”这句话的哈希值，并把输出结果交给朋友。一个月后当我们公开这句话时，朋友将能够通过计算这句话的哈希值，然后与我们一个月前公开的哈希值进行比较，从而判断我们所说的真伪。这就是承诺方案。密码学中的承诺需要具备以下两种性质。
● 隐蔽性（Hiding）：承诺必须隐蔽基础值。
● 绑定性（Binding）：承诺必须只隐藏一个值。换句话说，如果给定一个值x的承诺，那么之后无法公开另一个可以通过承诺验证的值y。
习题
如果把哈希函数作为一种承诺方案，它是否能提供隐蔽性和绑定性？
网页导入外部JavaScript文件的时候需要用哈希函数来验证子资源的完整性。例如，很多网站使用内容分发网络（Content Delivery Network，CDN）将JavaScript库或网络框架相关的文件导入网页中。这种CDN被部署在重要位置以便迅速将这些文件传递给访问者。然而，如果CDN不守规矩，故意为访问者提供恶意的JavaScript文件，则可能造成严重的问题。为了解决这个问题，网页可以使用子资源完整性（Subresource Integrity）的功能，允许在导入标签中包含一个摘要：
<script src=”https://code.jquery.com/jquery-2.1.4.min.js”
integrity=”sha256-8WqyJLuWKRBVhxXIL1jBDD7SDxU936oZkCnxQbWwJVw=”></script>一旦检索到JavaScript文件，浏览器就会计算它的哈希值（使用SHA-256算法），并核实它是否与页面中硬编码的摘要一致。如果一致，则可以通过完整性验证，该JavaScript文件就会被执行。
世界各地的用户使用比特流（BitTorrent）协议，在彼此之间直接分享文件（这种方式称为Peer-to-Peer）。为了分发一个文件，首先将文件切割成块，每个块都被单独计算哈希值。之后这些哈希值作为共享的信任源，代表要下载的文件。
比特流协议有几种机制，使得一个Peer可以从不同的Peer中获得一个文件不同的块。最后，整个文件的完整性将通过以下方式得到验证：在将文件从块中重新组合之前，对每个块进行哈希运算，并将输出结果与各自已知的摘要进行比对。例如，下面的例子代表Ubuntu操作系统的 19.04版本。它是通过对文件的元数据以及所有块的摘要进行哈希运算得到的一个摘要（用十六进制表示）：
magnet:?xt=urn:btih:b7b0fbab74a85d4ac170662c645982a862826455洋葱路由（Tor）浏览器出现的目的是使个人可以匿名浏览互联网。它的另一个特点是，人们可以创建隐藏的网页，即网站的物理位置难以追踪。我们可以通过一个使用网页公钥的协议来保证与这些网页的安全连接。（第9章讨论会话加密时将列举更多关于该协议的工作原理）例如，毒品交易网站在被FBI查封之前，可以在Tor浏览器中通过silkroad6ownowfk.onion进行访问。这个Base32字符串实际上代表了丝绸之路网站公钥的哈希值。因此，可以通过洋葱路由地址来验证隐藏网页的公钥，并确定当前访问的网页是正确的（而不是一个冒名顶替者）。如果不能理解这一点也不必担心，我们将在第9章中再次提到这个问题。
习题
显而易见，silkroad6ownowfk.onion这个字符串并没有256比特（32字节），那么根据我们在2.3节中所学到的知识，这怎么能提供足够的安全性呢？
恐惧海盗罗伯茨（丝绸之路网站管理员的昵称）是如何设法获得一个包含网站名称的哈希值的呢？
在本节的所有例子中，哈希函数可以在以下场景中提供内容的完整性或真实性验证：
● 可能有人篡改哈希函数的输入；
● 能够安全传递哈希值。
我们有时也将内容完整性或者真实性验证称为对某事或某人进行认证。重要的是，如果不能安全地获得哈希值，那么任何人都可以用其他内容的哈希值来替换真实内容的哈希值。因此，哈希值本身并不提供完整性验证。在第3章“消息认证码”中，我们将通过引入秘密值来解决这个问题。接下来让我们来学习一些实际应用中的哈希函数算法。
我们在前面的例子中提到了SHA-256，它只是我们可以使用的哈希函数之一。在继续列举其他推荐使用的哈希函数之前，我们要先提一下，在现实世界应用的一些非密码哈希函数算法。
首先，像CRC32这样的函数不是密码哈希函数，而是错误检测码函数。虽然它们有助于检测一些简单的错误，但却没有提供前面提到的安全属性，也不能与我们所说的哈希函数混淆使用（尽管它们有时可能共用一个名字）。它们的输出通常被称为校验和。
其次，如MD5和SHA-1这类流行的哈希函数，现在被认为是有缺陷的。虽然在20世纪90年代，MD5和SHA-1就已经标准化并且成为应用很广泛的哈希函数，但它们却分别在2004年和2016年被证明是有缺陷的，因为一些科研团队发布了在这些函数中找到攻击方法。这些攻击之所以成功，一部分是因为计算能力的进步，但主要还是因为在哈希函数的设计方式中发现了缺陷。
弃用以前的哈希函数的困难之处
在研究人员证明MD5和SHA-1缺乏抗碰撞的能力之前，它们都被认为是好的哈希函数。哪怕在今天，它们的抗第一原像性和抗第二原像性仍然没有受到任何攻击的影响。这对我们来说并不重要，因为我们在本书中只想讨论安全的算法。尽管如此，仍然有人在系统中使用MD5和SHA-1，而这些系统只依赖于这些算法的抗第一原像性，而不是它们的抗碰撞性。使用这些算法的人经常争辩，他们是因为一些历史遗留和向后兼容的问题而无法将哈希函数升级到更安全的版本的。但是，由于本书旨在为实用密码学初学者提供一些在未来很长时间内都保持正确性的知识，因此，这将是本书最后一次提到这些有缺陷的哈希函数。
接下来的2.5.1小节和2.5.2小节将介绍SHA-2和SHA-3函数，它们是两个使用广泛的哈希函数。图 2.6 给出了这两个哈希函数的构造原理。
图2.6 SHA-2和SHA-3是两个使用广泛的哈希函数。SHA-2基于Merkle-Damgård结构， 而SHA-3基于海绵结构
SHA-2是广泛应用的哈希函数。SHA-2算法由NSA发明并在2001年由NIST进行了标准化。SHA-2算法在设计上借鉴了由NIST标准化过的SHA-1算法。SHA-2算法族共有 4 个不同的版本，它们分别产生224、256、384和512比特的输出。这些算法在命名上包含其输出的比特长但省略了算法的版本，它们的名字分别为SHA-224、SHA-256、SHA-384 和 SHA-512。此外，SHA-512/224和SHA-512/256算法是通过截断SHA-512算法的输出产生的两个变种算法，它们分别提供224比特和256比特的输出。
在下面的终端会话中，我们用OpenSSL CLI调用SHA-2算法的每个变体。通过观察算法的输出，我们可以发现：给定相同的输入，不同的变体产生的输出结果和长度均不同。
$ echo -n “hello world” | openssl dgst -sha224
2f05477fc24bb4faefd86517156dafdecec45b8ad3cf2522a563582b
$ echo -n “hello world” | openssl dgst -sha256
b94d27b9934d3e08a52e52d7da7dabfac484efe37a5380ee9088f7ace2efcde9
$ echo -n “hello world” | openssl dgst -sha384
fdbd8e75a67f29f701a4e040385e2e23986303ea10239211af907fcbb83578b3
➥ e417cb71ce646efd0819dd8c088de1bd
$ echo -n “hello world” | openssl dgst -sha512
309ecc489c12d6eb4cc40f50c902f2b4d0ed77ee511a7c7a9bcd3ca86d4cd86f
➥ 989dd35bc5ff499670da34255b45b0cfd830e81f605dcf7dc5542e93ae9cd76f现在，应用非常广泛的哈希函数还有SHA-256算法，它满足前面提到的3个安全属性，且能提供128比特的安全性。对于高度敏感的应用，我们需要使用安全性更强的哈希函数SHA-512。现在，让我们来看看SHA-2算法的工作原理。
XOR操作
要理解下面的内容，我们需要先了解XOR（异或）操作。XOR是一种按位操作的运算。以下展示了它的运算规则。XOR操作在密码学算法中很常见。
XOR（通常表示为⊕）的操作对象是2个比特。除两个操作数都是1的情况外，XOR运算与OR运算的结果完全一样。
这一切都始于一个被称为压缩函数（Compression Function）的特殊函数。压缩函数以两个特定长度的数据为输入，产生与其中一个输入大小相同的输出。简单地说，它接收一些较长的数据，输出更短的数据。压缩函数的执行过程如图2.7所示。
图2.7 压缩函数接收长度为X和Y的两个不同输入（这里都是16字节）并生成长度为X或Y的输出
虽然构造压缩函数的方法有很多，但SHA-2算法的压缩函数采用的是Davies-Meyer构造方法（见图 2.8），它在内部采用了一个分组密码算法。虽然第1章中提到了AES分组密码，但本书到目前为止并没有详细介绍这个算法。现在，请把压缩函数想象成一个黑匣子，我们在第4章介绍认证加密的内容时再详细阐述它。
图2.8 基于Davies-Meyer结构设计压缩函数。该压缩函数的第一个输入块作为分组密码的密钥；第二个输入块作为分组密码的输入进行加密。然后，用第二个输入块与分组密码的输出进行异或操作
SHA-2是一种采用Merkle-Damgård结构来构造的哈希函数。Merkle-Damgård是一种算法（由Ralph Merkle和Ivan Damgård提出），通过迭代调用压缩函数来计算消息的哈希值。具体来说，SHA-2的执行过程分为以下两个步骤。
首先，我们对需要进行哈希运算的输入做填充，然后将填充后的输入划分为等长的分组，每个分组的长度等于压缩函数的输入长度。填充是指在输入中添加特定的字节，使输入的长度变成分组大小的整数倍。这样一来，我们就可以把上述分组作为压缩函数的第一个输入参数。例如，SHA-256算法输入的分组大小为512比特，如图2.9所示。
图2.9 第一步是对输入消息进行填充。填充后消息的长度应该是压缩函数输入长度的倍数（例如，8字节）。为了做到这一点，我们在输入的消息中额外加入5字节，使其成为32字节，然后我们把消息划分为4个8字节的分组
然后，将压缩函数应用于消息的所有分组，在每次迭代过程中，都将上一轮的输出作为压缩函数的第二个输入参数，而将消息的某个分组作为它的第一个输入参数。将压缩函数最终的输出作为消息的摘要。用压缩函数迭代计算消息摘要的过程如图2.10所示。
图2.10 第二步是将一个压缩函数迭代地应用到消息分组，每次迭代都以前一个压缩函数的输出以及消息的一个分组作为压缩函数的输入。将最后一次调用压缩函数产生的输出作为摘要
以上就是SHA-2的工作原理，它在输入的消息分组上反复调用压缩函数直到生成最终的摘要。
注意：
如果压缩函数本身是抗碰撞的，那么我们就可以证明Merkle-Damgård结构是抗碰撞的。这样一来，输入长度不固定的哈希函数的安全性就简化为输入长度固定的压缩函数的安全性，因此该结构使我们更容易设计和分析哈希函数。这就是Merkle-Damgård结构的巧妙之处。
在第一次调用压缩函数时，它的第二个参数通常是固定的，且标准文件中将其指定为特定的值。具体来说，SHA-256使用第一个素数的平方根来生成这个初始值。密码学专家相信这个特定的值不会让哈希函数安全性变弱（例如，故意留下一个后门）。这种提高算法参数可信度的做法在密码学中相当常见。
警告：
虽然SHA-2是一个非常完美的哈希函数，但它不适合用于计算秘密消息的哈希值。这是由于Merkle-Damgård构造存在一个缺点，使得SHA-2在计算秘密消息的哈希值时容易受到长度扩展（Length Extension）攻击。我们将在第3章更详细地讨论这个问题。
正如前面提到的，MD5和SHA-1哈希函数近来都被破解了。这两个函数都使用2.5.1 小节提到的Merkle-Damgård构造。正因为如此，再加上SHA-2容易受到长度扩展攻击，2007年NIST 决定组织一次公开的竞赛，来选择一个新的哈希函数标准：SHA-3。本小节主要介绍这个新的标准，并从宏观上解释其内部原理。
2007年，来自不同国家科研团队的64个候选算法进入SHA-3的竞赛。5年后，经过多轮评审，其中的一个提交方案Keccak最终胜出，被命名为SHA-3。2015年，FIPS 202将SHA-3指定为新的哈希函数标准。
SHA-3算法满足了我们之前谈到的3个安全属性，并且和SHA-2的变体达到同样级别的安全性。此外，SHA-3算法不容易受到长度扩展攻击，并可用于计算秘密消息的哈希值。正因如此，SHA-3 成为当前主要推荐使用的哈希函数。与SHA-2一样，SHA-3也提供了一些变体，这些变体在名称中都包含SHA-3字样：SHA-3-224、SHA-3-256、SHA-3-384和SHA-3-512。例如，与SHA-2类似，SHA-3-256提供了256比特的输出。现在我们来了解SHA-3的运行方式。
SHA-3是一种建立在置换（Permutation）之上的密码算法。为了理解置换，我们可以想象一种简单的情况：假设左边有一组元素，在右边有一组同样的元素，现在，我们通过箭头让左边每个元素都指向右边的每个元素。假设每个元素只能有一个箭头从它出发或者只能有一个箭头指向它，这样元素之间进行了置换，如图 2.11 所示。根据定义，任何置换都是可逆的，也就是说，我们可以根据输出找到其对应的输入。
图2.11 4种形状之间的置换方式演示。我们可以根据中间图片中箭头的指示将左边某个形状 转换为右边的某个形状
SHA-3是基于海绵结构（Sponge Construction）构造的，这是一种与Merkle-Damgård不同的结构。SHA-3基于称为keccak-f的特殊置换，这个置换接收一个输入并产生一个与输入等长的输出。
注意：
本章不会解释keccak-f的设计过程，我们将在第4章对其概念进行介绍，因为它与AES算法十分相似（除了keccak-f没有密钥外）。两者结构相似并非偶然，AES算法的发明者之一也参与了SHA-3算法的设计。
接下来，我们以8比特置换为例来说明海绵结构的工作原理。因为置换的方式是一成不变的，我们可以用图2.12中的示例表示基于8比特置换创建的映射函数。与图2.11所示的示例相对应，每个8比特串相当于不同形状（比如，000...表示三角形，100...表示正方形，等等）。
为了在海绵结构中使用置换，我们还需要将输入和输出的比特串都划分为比率比特串和容量比特串，如图2.13所示。这看起来有点儿奇怪，让我们来看看这样做的原因。
不同版本的SHA-3使用不同的划分方式。事实上，容量也看作秘密值，容量越大，海绵结构就越安全。
现在，就像所有哈希函数一样，我们需要使用这个结构来计算一些消息的哈希值，否则，这个结构就没有用处了。为此，我们只需将哈希函数的输入与置换输入的比率进行异或操作。一开始，这只是一串0。正如我们之前指出的，容量被视为秘密值，因此我们不会对其进行任何异或操作，如图2.14所示。
图2.12 一个使用特定置换函数f的海绵结构。通过依次输入所有可能的8比特串，示例中的置换可以创建一个从8比特输入到8比特输出的映射
图2.13 置换函数f 将大小为8比特的输入随机化为长度相同的输出。在海绵结构中，这种置换的输入和输出都分为两部分：比率（长度为r）和容量（长度为c）
图2.14 为了吸收哈希函数输入的00101这5个比特，可以使用比率为5比特的海绵结构将5比特的输入与比率比特（初始化为0）进行异或，然后将产生的结果作为置换函数的输入，实现对输入的随机化
现在我们得到的输出应该看起来是随机的（尽管我们可以很容易地找到输出对应的输入，这是因为置换是可逆的）。如果我们想计算更长输入的哈希值该怎么做呢？参考SHA-2的解决方式，具体做法如下：
（1）对输入进行填充（如有必要），然后将输入分成与比率比特串长度相等的分组；
（2）迭代调用置换函数，每次将消息分组与置换输入的比率比特串进行异或，然后将中间输出状态输入置换函数，直至处理完所有的消息分组为止。
为简化，我们忽略了填充的实现方式，但填充是非常重要的步骤，它必须保证一些特殊的输入（例如0和00）在填充后依然可以区分。上述两个步骤的直观描述如图2.15所示。
图2.15 为了吸收长度大于比率串长度的输入，海绵结构迭代地将输入块与速率异或并对产生的结果进行置换
到目前为止我们还没有讨论如何产生一个摘要。为此，我们可以简单地截取海绵结构的最后输出状态的比率比特串作为摘要（同样，我们不会使用容量比特串的值）。为了获得更长的摘要，我们可以继续读取输出状态的比率比特串部分，然后对其进行置换，如图2.16所示。
图2.16 为了使用海绵结构生成输入消息的摘要，迭代地调用置换函数获取多个输出状态，并根据安全性需要，选择尽可能多的比率比特串（即截取状态的上部分比特串），将它们拼接成消息的摘要
这就是SHA-3算法的工作原理。因为该算法是基于海绵结构的，所以我们将它处理输入消息的过程也称为吸收（Absorbing），将创建消息摘要的过程称为挤压（Squeezing）。海绵结构使用1600比特的置换结构，并采用不同的r和c值，具体取决于不同版本的SHA-3所公布出来的安全等级。
SHA-3是一个随机预言机
我们之前谈到了随机预言机：一种理想的虚拟结构，向随机预言机发出问询，它将返回完全随机的结果，如果两次查询的输入相同，它就会产生同样的输出。事实证明，只要海绵结构使用的置换看起来足够随机，海绵结构的行为就很接近随机预言机。那么我们如何证明这种置换结构足够随机呢？最好的方法就是不断尝试破解这种置换结构，直到我们可以相信它的设计足够安全为止（这就是在SHA-3竞赛期间每个候选算法需要接受的挑战）。SHA-3可以被视为随机预言机这一事实赋予它一些安全属性，而这些安全属性正是我们期望哈希函数能够拥有的。
接下来我们介绍两个主要的哈希函数标准：SHA-2和SHA-3。这些是定义明确的哈希函数，它们接收任意长度的输入并分别产生随机和固定长度的输出。正如后面的章节中将要介绍的，密码协议通常需要这种类型的原语，但不希望受到哈希函数摘要为固定大小所带来的一些限制。出于这个原因，SHA-3标准引入了一种更通用的原语，称为可扩展输出函数（Extendable Output Function）或XOF（发音为“zoff ”）。本小节介绍两种标准化的XOF：SHAKE和cSHAKE。
FIPS 202 和 SHA-3 标准中指定的SHAKE函数可以看作一个产生任意长度输出的哈希函数。SHAKE与SHA-3的结构基本相同，不同之处在于SHAKE运行速度更快，并且在挤压阶段，可以根据不同的置换方式进行置换，而不是只能采用固定的方式进行置换。生成不同长度输出的哈希函数非常有用，它不仅可以用于生成摘要，还可以用于生成随机数、派生密钥等。本书后面将再次讨论SHAKE的不同应用场景（现在可以想象一下，除了SHAKE的输出为任意长度外）。我们可以把SHAKE函数和SHA-3算法视为两个一样的算法。
这种结构在密码学中非常有用，以至于在SHA-3标准化一年后，NIST发布了其特别版本800-185，其中包含一个名为cSHAKE的可定制SHAKE函数。cSHAKE与SHAKE非常相似，不同之处在于前者需要一个自定义字符串。此自定义字符串可以为空，也可以是任何字符串。我们先来看一个在伪代码中使用cSHAKE的例子：
cSHAKE(input=”hello world”, output_length=256, custom_string=”my_hash”)
-> 72444fde79690f0cac19e866d7e6505c
cSHAKE(input=”hello world”, output_length=256, custom_string=”your_hash”)
-> 688a49e8c2a1e1ab4e78f887c1c73957尽管cSHAKE与SHAKE、SHA-3都是确定性算法，但由于可以使用不同的自定义字符串，cSHAKE算法能在相同的输入下产生不同的摘要。这样的特性使得我们可以自定义XOF。这在某些协议中很有用，例如，必须使用不同的哈希函数才能使得安全性证明顺利执行的协议。我们称cSHAKE算法的这种特性为域隔离（Domain Separation）。
请记住密码学的黄金法则：如果在不同的应用实例中使用相同的密码原语，请不要使用相同的密钥（如果需要密钥），或者在使用同样的密钥时应用域分离。我们在后面的章节中介绍密码协议时，会介绍更多关于域分离的例子。
警告：
NIST倾向于用比特来度量算法参数，而很少把字节当作算法参数的单位。在前面所给的示例中，要求输出的摘要长度为256比特。想象一下，我们要求输出的摘要长度是16字节，而程序只产生了2字节的摘要。这正是因为程序默认的单位是比特，而16比特恰好等于2字节。这种情况有时被称为比特攻击。
与密码学中的所有算法一样，密钥、参数和输出等的长度与系统的安全性密切相关。重要的是不能让SHAKE或cSHAKE的输出太短。使用256比特的输出永远不会出错，因为它提供了128比特的安全性以防止碰撞攻击。但现实世界中的密码方案可能由于运行环境的限制只能使用较短的输出。但如果能仔细分析系统的安全性，也可以将短输出的哈希函数用于系统中。例如，如果在该系统中抗碰撞性是无关紧要的，则只需要选择SHAKE或cSHAKE的128比特输出版本来保证抗第一原像性即可。
本章已经讨论不同类型的密码原语和密码算法，具体内容如下：
● SHA-2哈希函数，虽然它容易受到长度扩展攻击，但仍然被广泛使用，因为在有些场景下，我们不需要计算秘密消息的哈希值；
● SHA-3哈希函数，这是目前推荐使用的哈希函数；
● SHAKE和cSHAKE这两个可扩展的输出函数，是目前用途比哈希函数更广的工具，因为它们可以提供可变长度的输出。
接下来介绍一个更易使用的函数——元组哈希（TupleHash），它基于cSHAKE提出并与cSHAKE定义在相同的标准中。元组哈希是一个有趣的哈希函数，它允许对一个元组（某事物的列表）进行哈希。下面我们来了解一下元组哈希的概念以及它的使用方式。
几年前，我的一部分工作是审查一种“加密货币”。我审查的内容包括账户、支付等“加密货币”通用功能的实现情况。在“加密货币”中，用户之间的交易中包含记录“加密货币”的来源与去向、转账金额的元数据，以及一小笔用来补偿网络节点处理交易的费用。
例如，Alice 可以将交易发送到网络，但要让这些交易被各个节点接收，她需要提供证据证明交易由她发起。为此，她可以对交易进行哈希并签名（第 1 章中给出了类似的例子）。任何人都可以计算这笔交易的哈希值并验证哈希值上的签名，以查看这是否为Alice发起的交易，该过程如图 2.17 所示。在交易到达网络之前，试图拦截交易的中间人攻击者无法在不被察觉的前提下篡改交易内容。这是因为攻击者虽然可以篡改交易内容并生成对应的哈希值，却无法伪造Alice的签名，从而导致假的交易与真实的签名无法通过验证。
图2.17 Alice 发送一个交易以及对交易哈希值的签名。如果中间人攻击者试图篡改交易， 那么交易的哈希值就会改变，原始附加的签名将无法通过验证
在第7章中我们会提到这样的攻击者无法在新摘要上伪造Alice的签名。这是因为“加密货币”中使用的哈希函数具有抗第二原像性，攻击者无法找到一个不同的交易，使其哈希值与原来的交易相同。
这能说明中间人攻击者不足为惧吗？很可惜，这个问题还没有定论。实际上，我正在审计的“加密货币”是通过简单地连接每个字段，然后将拼接后的字符串哈希值作为交易的哈希值：
$ echo -n “Alice””Bob””100””15” | openssl dgst -sha3-256
34d6b397c7f2e8a303fc8e39d283771c0397dad74cef08376e27483efc29bb02这看起来虽然没问题，但完全破坏了“加密货币”的支付系统。这样做使得攻击者可以轻易攻破哈希函数的抗第二原像性。花点儿时间思考一下，如何找到哈希值同样为34d6...的不同交易？
如果将费用字段的首位数字移除，并把它追加到总额字段的末位，我们会看到修改前后，两个交易生成相同的哈希值：
$ echo -n “Alice””Bob””1001””5” | openssl dgst -sha3-256
34d6b397c7f2e8a303fc8e39d283771c0397dad74cef08376e27483efc29bb02因此，如果中间人攻击者希望Bob收到更多的钱，那他将能够在确保签名有效的情况下修改交易。这就是元组哈希要解决的问题：它允许我们使用非歧义编码，确定性地计算字段列表的哈希值。现实中采用以下方式计算交易的哈希值（使用||表示字符串连接操作）：
cSHAKE(input=”5”||”Alice”||”3”||”Bob”||”3”||”100”||”2”||”10”,
➥ output_length=256, custom_string=”TupleHash”+”anything you want”)现在，在交易中的每个字段前面都加上本字段的长度，最终将这它们拼接在一起形成哈希函数的输入。让我们花些时间想想这种做法是如何解决上述问题的。通常，只要始终确保在计算哈希值之前，先对输入进行序列化（Serialize），就可以安全地使用任何哈希函数。将输入序列化意味着总是存在反序列化的方法（意味着根据序列化结果可以恢复原始输入）。如果可以反序列化输入的数据，就不会在字段的划分上产生任何歧义了。
我们在本章中介绍了常见的函数，它们都属于哈希函数或者可扩展哈希函数。在进入第3章之前，我们需要学习口令哈希（Password Hashing）算法。
想象以下场景：如果有一个网站（你就是网站管理员），并且你希望用户注册并登录到该网站，因此你创建了两个网页来实现这两个功能。马上你就会想，网站要如何存储他们的口令？能否将它们以明文形式存储在数据库中？虽然一开始存储明文似乎也没什么问题，但是这样会带来安全威胁。由于人们倾向于在很多地方重复使用相同的口令，如果你的网站被攻破并且攻击者设法转储了你所有用户的口令，这将对你的用户不利，并且对你的平台声誉也不利。想得更深入一点，你就会意识到能够窃取此数据库的攻击者，将能够以任何用户身份登录。所以，以明文形式存储口令不太理想，你希望有更好的方法来处理这个问题。一种解决方案是计算所有口令的哈希值并仅存储用户对应的摘要。当用户登录网站时，流程类似于以下内容：
（1）收到用户的口令；
（2）计算口令的哈希值，然后去掉口令；
（3）将摘要与之前存储的用户对应的摘要进行比较，如果匹配，则用户可登录。
该流程允许网站在有限的时间内处理用户的口令。尽管如此，在你检测到悄悄进入你的服务器的攻击者之前，他们仍然可以悄悄地留下来并记录登录流程中出现的口令。这确实不是一个完美的防御方案，但这样仍然提高了网站的安全性。在安全方面，我们也称这种防御为纵深防御，即对不完善的防御进行分层的行为，寄希望于攻击者无法攻破所有的层。纵深防御也是实用密码学的意义所在。但是，这个解决方案还存在其他问题。
● 如果攻击者提取到口令的哈希值，则可以进行暴力攻击或穷举搜索（尝试所有可能的口令）。每次猜测口令时，都针对整个数据库进行比对。理想情况下，我们希望攻击者一次只能攻击一个口令的哈希值。
● 哈希函数运行速度应该是非常快的。攻击者可以利用它进行暴力破解（每秒可以产生很多口令）。理想情况下，我们会有一种机制来减缓此类攻击。
第一个问题通常通过使用加盐（Salts）技术来解决，盐值是指对每个用户公开且不同的随机值。我们要对加盐的口令计算哈希值，从某种意义上说，这就像在cSHAKE中使用每个用户自定义的字符串：该方法可以有效地为每个用户创建不同的哈希函数。由于每个用户使用不同的哈希函数，攻击者无法预先计算大型密码表（称为彩虹表），也无法针对整个被盗口令哈希值数据库进行测试。
第二个问题是用口令哈希解决的，口令哈希算法的运行速度很慢。目前最优的选择是 Argon2算法，它是2013年至2015年口令哈希竞赛的获胜算法。在撰写本书时（2021年），Argon2有望在RFC系列文档中标准化。在实践中，还使用了其他非标准算法，如PBKDF2、Bcrypt和Scrypt算法。不过，这些算法使用的参数可能会不安全，因此在实践中这些算法使用起来很复杂。
此外，只有Argon2和Scrypt可以抵御攻击者大幅度优化过的攻击，因为其他算法不是内存困难的（Memory Hard）。内存困难意味着只能通过优化内存访问来优化算法。换句话说，优化算法的其余部分并不会给攻击算法带来太多好处。即使是专用硬件，通过优化内存访问来改善攻击效果，其改善程度也是有限的（CPU周围只能放置这么多缓存），因此内存困难函数在任何类型的设备上都运行得很慢。当要防止攻击者在计算函数时获得不可忽视的速度优势时，内存困难函数就是我们的一个理想选择。
图2.18总结了本章中介绍的不同类型哈希函数。
图2.18 在本章中，我们学习了4种类型的哈希函数：（1）为任意长度的输入提供唯一随机标识符的普通哈希函数；（2）提供任意长度输出的可扩展输出函数；（3）允许对输入进行非歧义编码的元组哈希函数；（4）为了安全地存储口令而设计的口令哈希函数
● 哈希函数具有抗第一原像性、抗第二原像性、抗碰撞性。
❏ 抗第一原像性意味着无法从一个摘要找到它对应的输入。
❏ 抗第二原像性意味着根据一个输入和它的摘要不能够找到一个不同的输入，使哈希函数生成相同的摘要。
❏ 抗碰撞性是指，人们应该无法找到两个随机的输入，而这两个输入又能产生相同的哈希值。
● 当前，应用最广泛的哈希函数是SHA-2，而本书推荐使用的哈希函数是SHA-3。由于SHA-2无法抵抗长度扩展（Length Extension）攻击，因此本书建议使用SHA-3算法。
● SHAKE是一个可扩展输出的函数（XOF），其作用类似于哈希函数，但可以输出任意长度的摘要。
● cSHAKE（customizable SHAKE）允许人们轻松地创建SHAKE算法的实例。这些实例就像许多个XOF函数，这就是所谓的域隔离。
● 消息应该在序列化之后再计算哈希值，以避免破坏哈希函数的第二抗原像性。像TupleHash这样的算法会自动对输入进行序列化。
● 对口令进行哈希时，应使用专门设计的、运行速度较慢的哈希函数，Argon2算法就是口令哈希函数的最优选择。
读者服务：
微信扫码关注【异步社区】微信公众号，回复“e60034”获取本书配套资源以及异步社区15天VIP会员卡，近千本电子书免费畅读。
