软件的奥秘——加密、密码、压缩、搜索是如何工作的

版权信息

书名：软件的奥秘——加密、密码、压缩、搜索是如何工作的

ISBN：978-7-115-46199-5

本书由人民邮电出版社发行数字版。版权所有，侵权必究。

您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。

我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。

如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。

•　著　　　　[美] V. Anton Spraul

　   译　　　　解福祥

　   责任编辑　陈冀康

•　人民邮电出版社出版发行　　北京市丰台区成寿寺路11号

　   邮编　100164 　电子邮件　315@ptpress.com.cn

　   网址　http://www.ptpress.com.cn

•　读者服务热线：(010)81055410

　   反盗版热线：(010)81055315

版权声明

Simplified Chinese-language edition copyright © 2017 by Posts and Telecom Press.

Copyright © 2016 by V.Anton Spraul. Title of English-language original: How Software Works,

ISBN-13: 978-1-59327-666-9, published by No Starch Press.

All rights reserved.

本书中文简体字版由美国No Starch出版社授权人民邮电出版社出版。未经出版者书面许可，对本书任何部分不得以任何方式复制或抄袭。

版权所有，侵权必究。

内容提要

软件已经成为人们日常生活与工作中常见的辅助工具，但是对于软件的工作原理，很多人却不是非常了解。

本书对软件的工作原理进行了解析，让读者对常用软件的工作原理有一个大致的了解。内容涉及数据如何加密、密码如何使用和保护、如何创建计算机图像、如何压缩和存储视频、如何搜索数据、程序如何解决同样的问题而不会引发冲突以及如何找出最佳路径等方面。

本书适合从事软件开发工作的专业技术人员，以及对软件工作原理感兴趣的读者。

作者简介

V. Anton Spraul已经为来自世界各地的学生讲授了15年以上的入门编程和计算机科学。同时他也是《Think Like a Programmer》（No Starch出版社）和《Computer Science Made Simple》（Boardway出版社）这两本书的作者。

技术审阅者简介

Randall Hyde是《The Art of Assembly Language》和《Write Great Code》这两本书（No Starch出版社）的作者，同时他还是《The Waite Group’s Microsoft Macro Assembler 6.0 Bible》这本书的合著者。Hyde在加州大学河滨分校（University of California, Riverside）讲授汇编语言已有10多年。在过去的12年中，他一直在为核反应堆控制台编写软件。

致谢

本书是在一群才华横溢的编辑们的塑造和指导下才得以出版，他们分别是Alison Law、Greg Poulos、Seph Kramer、Hayley Baker、Randall Hyde、Rachel Monaghan和No Starch 出版社的“Big Fish”以及Bill Pollock。除了全体编辑工作人员之外，我还要对在No Starch共事过的每个人的支持和帮助表示衷心的感谢。

其中对我帮助最大的是Mary Beth和Madeline，她们是最棒的妻子和女儿，没有她们的爱与支持，这本书是不可能成形的。

前言

科幻小说家Arthur C. Clarke曾写道：“任何足够先进的技术都与魔法无异”。如果我们不知道事物背后的原理，倒不妨用超自然力量来解释。不过若是按照这个标准来说的话，那我们无异于生活在一个充满魔法的时代。

今天软件已经融入了我们的生活，例如在线交易、电影特效以及流式视频播放等这样的日常事务。我们逐渐淡忘了在过去的生活中不但没有Google搜索，甚至连计划一次汽车旅行的路线时，都不得不先打开一份烦琐的地图。

但很少有人知道这些软件背后的工作原理。与过去的很多创新不同，对软件来说，你无法把它拆开来一窥究竟。所有的一切都发生在计算机芯片内，无论那些计算设备正在执行一项了不起的任务，还是压根就没有启动，这些在我们看来并没有什么两样。想要了解程序的工作原理，似乎需要花费多年的学习成为一名编程人员才可以。因此，难怪许多人会认为软件超出了普通大众的理解，而只有那些技术精英才能掌握其中的奥秘。但实际上这种想法是不对的。

本书适用对象

其实任何人都能了解软件的工作原理，所需的只是好奇心而已。无论你只是对技术突然感兴趣，还是一名成长中的编程人员，抑或是二者之间，本书都适合你。

本书涵盖了在软件中常用的一些技术，并且没有任何代码，因此无须事先学习计算机的运行原理。为了达到此效果，我简化了一些技术和细节，但这并不代表本书只是些高度概述，相反，本书含有丰富的细节讲述，使你能从中学到真正的“干货”，从而真正了解这些程序背后的工作原理。

章节内容

计算机在现代生活中无处不在，我能拿出来讲的主题无穷无尽，这里我只挑选了那些对我们的生活最有影响以及解释起来最有趣的主题。

• 第1章：加密使我们可以混淆数据以便只有我们自己能够访问数据。当你锁定你的手机或是通过密码保护.zip文件时，你就是在使用加密技术。我们将在本章中看到在现代加密软件中是如何组合使用那些不同的加密技术的。
• 第2章：密码是指我们在加密数据时，或是在远程系统上识别自己时所用到的密钥。在本章中你将会了解到那些加密技术是如何使用密码的，并且还会学到一些必要的手段去保护密码的安全。
• 第3章：网络安全是我们在进行安全的在线购物时，或是访问自己的账户时需要用到的技术。对传输数据的加密需要用到一种不同的加密技术——公钥加密。此外你还将了解到一个安全的网络会话如何利用前3章中涵盖的所有技术。
• 第4章：电影CGI是纯粹的软件魔法，它用数学的概念创造了电影的整个世界。在本章中你将了解到软件是如何接管传统的cel动画的，此外还能学到在用软件制作整个电影场景时背后所涉及的核心技术。
• 第5章：游戏图形之所以令人印象深刻，不仅在于它们的视觉效果，还在于它们如何能在仅仅几分之一秒的时间内就创造出了这些效果。我们将在本章探讨在游戏开发过程中会用到的一些技巧，并讲述它们是如何在没有充足的时间去利用上一章介绍的那些技术时，还能产生惊人的画面效果的。
• 第6章：数据压缩可以缩减数据，以便我们可以更充分地利用存储和带宽。我们将在本章中探讨缩减数据的最佳方法，并且还会了解到如何将这些技术组合起来去压缩蓝光光盘和网络流中的高清视频。
• 第7章：搜索是指即时查找数据，可以是搜索自己计算机上的文件，也可以是搜索整个网络。我们将在本章中探讨如何组织数据以满足快速搜索，以及如何通过网络搜索返回最有用的结果。
• 第8章：并发使得多个程序可以共享数据。若没有并发技术，那多人视频游戏将不可能实现，在线银行系统一次只能处理一位客户的需求。此外我们还将讨论一些可以使不同处理器访问相同数据并且不会相互影响的方法。
• 第9章：地图路径就是我们从地图网站或车载导航仪中获得的那些即时路线。你将在本章中了解到软件世界对地图的定义，以及一些用于找出最佳路径的特殊搜索技术。

寄语

我认为分享这些知识很重要。我们不应该生活在一个我们不了解的世界中，如果不了解软件背后的工作原理，就不可能了解当今的世界。Clarke的话可以看做一种警告，那些了解技术原理的人可以去糊弄那些不了解的人。例如，一家公司可能会声称其用户登录信息的失窃对其客户不会造成什么影响。果真如此吗？为何呢？读完本书后，你就将会知道此类问题的答案。

除此之外，关于为何要了解软件的工作原理还有一个更好的理由：因为这些技术实在是太酷了。而且我认为最好的魔法技巧在你了解其秘诀后会让你觉得更加神奇。继续读下去，你就会明白我的意思。

第1章 加密

我们每天都在依赖软件来保护我们的数据，但大部分人对这种保护原理知之甚少。为何浏览器角落的“锁”图标意味着输入信用卡卡号是安全的？手机设置密码后是如何保护内部数据的？是什么真正阻止了其他人登录你的网络账号？

计算机安全是一门保护数据的科学。从某种程度来说，计算机安全相当于通过技术来解决由技术带来的问题。不久以前，大部分数据并没有以数字化形式存储，办公室有文件柜，床底下有放照片的鞋盒。当然，那时你不能方便地与世界各地的朋友们分享你的照片，也不能用手机核查银行存款余额，但是，也没人可以窃取你的私人数据，除非去偷走它本身。而如今，你的私人数据不仅可以被远程窃取，甚至在银行打电话问你为何买了数千元的礼品卡之前，你可能都不知道它们已经被窃取了。

在本书的前3章中，我们将讨论计算机安全背后最重要的一些概念。在本章中，我们先来讨论加密。加密使我们能够加密数据，并且只有我们自己才能解密数据。接下来的两章讨论的技术都是以加密为基础，并且需要依赖完整的安全套件，因此加密才是计算机安全的核心。

1.1　加密目标

想象一下你计算机上的文件，可能是文本、照片、电子表格、音频或者视频，你希望能够访问这些文件但又对其他人保密，其实这就是计算机安全的基本问题。为了使这些文件保密，你可以将其加密（encryption）成一种不可读的新格式，直到把它们解密（decryption）回原有格式。原有文件是明文（plaintext，即便不是文本文件），加密后的文件是密文（ciphertext）。

攻击者（attacker）是指那些企图擅自对密文进行解密的人。加密的目标就是创建一个密文，在便于授权用户解密的同时，又使得攻击者几乎不可能解密，这“几乎”是许多安全研究人员头痛的来源。就像没有什么锁是绝对牢不可破的一样，加密也绝非不能被解密。在足够多的时间和足够强的计算能力的前提下，任何加密方案在理论上都是可以破解的。因此计算机安全的目标，就是加大攻击者解密的难度，使解密所需的计算资源远超攻击者所拥有的资源，以致攻击行为在实际上不可能成功。

与其一头扎进错综复杂的基于软件的加密中去，不如先从一些简单的例子开始。尽管多年来加密强度有了很大的改进，但这些经典技术是一切加密的基础。稍后，你将看到在现代数字化加密方案中，这些技术是如何结合使用的。

1.2　换位法：相同的数据，不同的顺序

加密数据的一个最简单的方法叫作换位（transposition），简单来说就是“改变位置”。换位是我和我的朋友们在上小学传纸条时所用到的一种加密技术。由于纸条会经过一些不能信任的人，所以必须使除我们之外的其他人无法理解这些纸条。

为了使信息保密，我们使用了一个简单、易恢复的方法来重新排列字母的顺序。假设我需要分享的重要情报是CATHY LIKES KEITH。为了加密信息，我复制了明文的每第3字母（忽略任何空格）。第一遍处理完消息后，我复制了5个字母，如图1-1所示。

图1-1　示例信息的第一遍换位处理

在到达信息尾部后，我从头开始并继续从剩下的字母中选出每第3个字母，经过第二遍处理后的结果如图1-2所示。

图1-2　第二遍换位处理

最后，我复制了剩下的所有字母，如图1-3所示。

图1-3　最后一遍换位处理

最终生成的密文是CHISIAYKKTTLEEH。我的朋友们通过逆转换位的过程，就能够读懂这条信息。逆转处理的第一步如图1-4所示，将所有的字母逆转回原位即可展现明文。

图1-4　解密时逆转换位的第一遍处理

这个基本的换位方法使用起来很有趣，但是它的加密性非常弱。最大的问题在于泄密——某个朋友将加密方法泄露给了圈外的人。一旦发生这种情况，即使发送的是加密过的消息也将不再安全，加密本身变得没有任何意义。可悲的是泄密是不可避免的，不仅只有小学生会泄密，每个加密方法都很容易被泄漏出去。使用一个特定加密方法的人越多，就越有可能泄漏。

出于这个原因，所有优秀的加密系统都遵循由早期荷兰密码学家奥古斯特·柯克霍夫（Auguste Kerckhoffs）提出的柯克霍夫原则（Kerckhoffs’ principle）：数据的安全不应依赖于加密方法本身来保证加密。

1.2.1　密钥

这就引发了一个明显的问题，如果加密方法本身不是保密的，那我们该如何安全地加密数据？答案在于加密方法本身可以公开，但是必须使用密钥（cipher key或key）去保证不同数据对应的加密结果也不同。为了理解什么是密钥，先来解释一个更常见的换位方法。

在该方法中，发送任何消息之前，发送方和接收方共享一个密码。假设我和我的朋友们都同意使用374作为密码。我们将使用这个数字来改变生成密文时的换位模式。还是以消息CATHY LIKES KEITH为例，如图1-5所示。我们密码中的数字决定了应该将明文中的哪一个字母复制到密文。因为密码的第一个数字是3，所以明文的第3个字母T就成为了密文的第1字母。而密码的下一个数字是7，所以下一个要复制的是T后面的第7个字母，也就是S。然后，是S后面的第4个字母。经过这样的处理后，密文的前3个字母是TST。

图1-5　使用密钥374来进行第一遍换位处理

图1-6展示了接下来的两个字母是如何被复制到密文的。接着上次的位置开始（图中圈1位置），往后数3个位置，若到达尾部则回到明文头部并继续进行，因此选到了A作为密文的第4个字母。而下一个要复制的字母是A后面数7个位置，且需要跳过我们已经复制过的字母，所以是K。继续这样的处理直到所有明文的字母都被换位。

这个密码374，就是我们说的密钥。其他人即使截获了该信息，甚至知道我们使用的是换位加密法，但在没有密钥的情况下，仍然无法解密信息。密钥可以定期更改，以防止泄密。

图1-6　使用密钥374进行第二遍换位

1.2.2　对加密的攻击

即使没有密钥，攻击者仍然可以通过其他手段去尝试恢复明文。加密后的数据可以通过暴力攻击（brute force），尝试所有的可能性以找出密文所使用的加密方法。对于一条使用了换位加密的信息来说，暴力攻击将检测密文的所有排列。由于暴力攻击几乎总会被使用，所以攻击者用来找出明文所需要尝试的次数，是一个很好的判断加密强度的基准。在我们的示例中，消息CATHY LIKES KEITH大约有400亿种排列。

这是一个巨大的数字，所以聪明的攻击者将会使用一些常识以便更快地恢复明文，而不是一味地蛮用暴力攻击。如果攻击者可以假设明文都是英文，那么在测试之前就可以排除掉很大一部分的排列。例如，攻击者可以假设明文不会以字母HT开始，因为没有英文单词会是以这些字母开头，这就有10亿的排列不需要攻击者去检测了。

如果攻击者有了信息中单词的一些线索，那就可以更机智地破译出明文。在我们的示例中，攻击者可能猜到消息中会包含同班同学的名字，所以他们可以先找出密文中的字母能够组成哪些名字，然后再确定剩下的字母可以组成哪些单词。

这种猜测明文内容的手段被称为cribs。最强的一种crib是已知明文攻击（known-plaintext attack）。想要采取这种攻击方式的话，攻击者必须能够获知明文A、对应的密文A以及与密文A使用了相同密钥加密的密文B。尽管这种情况听起来不太可能，但它确实会发生。人们经常会使一些他们认为不再是机密的文档处于无保护状态，而并没有意识到这些文档也可能会被用于协助攻击其他文档。已知明文攻击很强大，当你同时拥有明文和密文时，要找出其中的换位模式将会很容易。

对已知明文攻击最好的防御，就是形成良好的安全实践，例如定期更改密码。不过即使有最好的安全实践，攻击者也总是能够获得明文内容的一些线索（这就是为什么他们会如此有兴趣去读那些无保护文档的原因）。在许多情况下，他们将知道大多数的明文，并且可能还会获知明文——密文对。所以一个良好的加密系统应该使cribs和已知明文对攻击者无用。

1.3　替换法：替换数据

另一种基本的加密技术对cribs更具抵抗力。与数据移位不同，替换法（substitution）会系统地替换各个独立的数据块。以文本信息为例，替换的最简单的形式就是把信息中的每一个字母替换成另一个字母。例如：把每个A换成D，把每个B换成H，以此类推。这种技术用到的加密密钥如表1-1所示。

表1-1　替换密钥

虽然简单替换法（simple substitution）比换位法有所改善，不过它也存在问题：正如其名，由于它比较简单，替换的可能性有限，所以攻击者有时通过暴力攻击法就可以解密密文。

简单替换法在频率分析（frequency analysis）面前也很脆弱。只要给定一门语言，攻击者就可以通过常识来得知哪些字母或字母组合会经常出现。所以一般来说，攻击者如果知道了明文中数据项可能出现的频率，对其破解将会很有帮助。例如，字母E是英文书信中最常见的字母，TH则是最常见的字母对。因此，在一段长密文中，最频繁出现的字母很可能会是明文E，而最频繁出现的字母对则很可能是明文TH。

频率分析的威力，意味着替换加密法会随着信息长度的增加而变得愈发脆弱。当已知一批密文是采样相同的密钥进行加密时，那攻击也会更容易。因此，避免任何形式的密钥重用（key reuse）是一项重要的安全实践。

1.3.1　变化替换模式

为了强化加密来应对频率分析，我们可以在加密时变化替换模式。比如明文中的第一个E可能会被替换成A，但明文中的第二个E却会被替换为T。这个技术也被称为多表替换（polyalphabetic substitution）。多表替换的一种形式是使用一个被称为tabularecta的字母表格，如图1-7所示。在该表中，每行和每列都以该行或该列的起始字母作为标签，表格中的每个位置都可以由两个字母来定位，例如D行H列对应的字母是K。

图1-7　tabula recta，带阴影的第一列和第一行即为标签

当使用tabularecta时，密钥是文本式的，用于变化加密的是字母，而不是在之前换位示例中用到的数字。在tabularecta中，明文中的字母用来选择行，而密钥中的字母用来选择列。例如，假设明文信息是单词SECRET，密钥是单词TOUGHT，由于明文的第一个字母是S，密钥的第一个字母是T，所以密文的第一个字母就是tabularecta中S行T列对应的字母L。然后使用表格的E行O列来加密明文的第二个字母E（结果为S），以此类推，如图1-8所示。由于明文的长度比密钥长，所以我们会循环密钥并重用其第一个字母。

图1-8　使用表格法搭配密钥TOUGHT来进行加密

通过逆转上述的整个过程就可以进行解密，如图1-9所示。密钥中的字母表明了要找的列，然后在该列中找到对应的密文字母，其所在行对应的行标签便是明文字母。在我们之前的示例中，由于密钥的第一个字母是T，而密文的第一个字母是L，所以我们先在tabularecta的T列中找到L，因为L处在S行，所以对应的明文字母就是S。针对密文中的每个字母，重复该过程即可获得完整明文。

图1-9　使用tabularecta搭配密钥TOUGHT来进行解密

多表替换法比简单替换法效果更好，因为它在加密消息的过程中变化了替换模式。以我们的例子来说，明文中两个E变成了两个不同的密文字母，而密文中的两个L也代表了两个不同的明文字母。

1.3.2　密钥扩展

虽然多表替换法比简单替换法有了很大的改善，但它仅在密钥重复度不高的情况下才有比较好的效果，否则它会存在与简单替换法同样的问题。例如，对于一个长度为5的密钥，由于每个明文字母仅能被加密成5种不同的密文字母，所以长密文在频率分析和cribs面前仍然会很脆弱。虽然攻击者在破解时会有一定难度，但只要给定足够长的密文，攻击者就仍然可以破解加密。

为了最大化加密的效果，我们需要让加密时用的密钥变得和明文一样长。对此有一种被称为一次性密码本（one-time pad）的技术，不过在大多数情况下它并不是一个实用的解决方案。而另一种被称为密钥扩展（key expansion）的方法也可以使短密钥达到长密钥的效果。它的用法经常会出现在间谍小说里，当两名间谍需要交换信息时，他们并不是事先共享一个超长的密钥，而是通过一个商定好的密码本（codebook），以此来作为长密钥的资源库。为了避免引起怀疑，密码本往往只是一件再普通不过的文学作品，例如莎士比亚戏剧的某个特定的版本。

假设会使用该方法发送一条含有50个字母的消息。在发送时，除了密文本身，消息发送方还会附上未扩展的密钥。若使用的是莎士比亚的作品作为密码本的话，那未扩展的密钥可能就是2.2.4.9。其中第一个2是指当按字母顺序排列时，莎士比亚的第二个戏剧（《皆大欢喜As You Like It》）；第二个2是指该剧的第二幕；4指的是该幕中的第四个场景；9指的是该场景在指定版本中的第九句：“When I was at home, I was in a better place, but travelers must be content”。这句的字母数超过了明文的字母数，所以可以用于之前提到过的tabularecta来加密和解密。通过这种方式，一个相对较短的密钥就可以扩展并适应特定的消息。

注意，这种方案严格来说并不是一次性密码本技术，因为密码本是有限的，因此最终不得不重复使用这些可以作为密钥的句子。但它确实意味着间谍只需记住短密钥，就可以变相地以长密钥的形式去更安全地加密他们的消息。后面你将会看到，由于对密钥的需求量巨大，而同时密钥又需要以较小的形式存储，因此密钥扩展概念在计算机加密领域十分重要。

1.4　高级加密标准

到目前为止，我们已经讨论了换位、替换以及密钥扩展这些技术是如何独立工作的。接下来让我们来看看把这3种技术精心组合起来会为安全数字加密带来怎样的成果。

高级加密标准（Advanced Encryption Standard，AES）是一个开放的标准，这意味着相关规范可以由任何人实现而不需要支付许可费用。无论你之前注意到没有，其实你的大多数数据都在受到AES的保护。例如，如果你的家里或办公室里有一个安全的无线网络，如果你曾为zip归档文件设置过密码保护，如果你在商店使用过信用卡或是从ATM机里取过款，那么很可能，至少从某种程度上来说，你都是在依赖AES。

1.4.1　二进制基础

到目前为止，为了保持示例的简单性，所用的都是文本加密的形式。但是计算机加密的数据，其实都是以二进制数的形式来表示的。如果你之前没有用到过这种二进制数，那么下面是一些介绍。

1．十进制和二进制

在我们成长过程中所接触到的数制都是十进制（decimal，deci表示“10”），因为该数制使用的是0到9这10个数。一个十进制数字中的每个数位，都表示了10倍于其右边相邻数位的单位数量。例如十进制数23 065的单位和数量如图1-10所示，其中左侧第五位的2代表2个“万”，而6代表6个“十”。

图1-10　十进制数23 065的每个数位代表了不同的单位和数量

但在二进制（binary）数制中，只有两个可用的数字：0或1。它们也被称作位（bits），表示二进制数位。二进制数中的每个位，都表示了一个比其右侧相邻位大2倍的单位。例如二进制数110101的单位和数量如图1-11所示，我们有以下每个单位的其中一个：32、16、4和1。因此，二进制数110101表示的就是这4个单位值的总和，相当于十进制数53。

图1-11　二进制数110101的每一位代表了不同的单位和数量

二进制数通常会被写成固定位长的形式，其中最常见的位长是8位，被称为一个字节（byte）。虽然十进制数53可以被写成二进制110101，但是由于把53写成一个字节的话需要8位，因此用0填满其他位，即00110101的形式。最小的字节值是00000000，表示十进制0；最大的字节值是11111111，表示十进制255。

2．按位运算

与通常加法和乘法这种数学运算一样，在软件中也会使用到一些独特的二进制数运算。这些运算被称为按位运算（bitwise operations），因为它们是单独作用于二进制数的每个位，而不是整个二进制数。

按位运算中的异或（exclusive-or或XOR）运算，在加密中是很常见的。当两个二进制数进行异或运算时，第二个数中那些为1的位，会翻转第一个数中相应的位，如图1-12所示。

图1-12　异或运算。第二个字节中为1的位，表示第一个字节中的哪些位会被“翻转”， 如阴影列所示

需要牢记的是，加密必须是可逆的。异或在某种程度上改变了数据位的内容，在不知道相关二进制数的情况下无法去预测，不过该操作很容易进行逆转。将之前的异或结果与第二个数再进行异或，就会将那些改变的位翻转回其原始状态，如图1-13所示。

图1-13　如果用相同的字节去异或另一个字节两次，那么被异或字节将会回到初始状态

3．将数据转换成二进制格式

计算机使用二进制数来表示各种各样的数据。明文文件可能是一条文本信息、一个电子表格、一个图片、一个音频文件，或者其他形式，但是最终，每个文件实际上都是一串字节序列。由于大多数计算机内的数据已经是数字型了，因此可以直接转换成二进制数。但在某些情况下，还是需要用一种特殊的编码系统将非数字型的数据转换成二进制形式。

为了弄清如何将一个文本信息转换为一个字节序列，以如下消息为例：

Send more money!

该消息有16个字符，包括字母、空格和感叹号。我们可以通过一个系统将每个字符转成一个字节，如美国标准信息交换码（American Standard Code for Information Interchange），该系统通常简写为其首字母的缩写ASCII，发音为“as-key”。在ASCII中，数字65代表大写字母A，66代表B，以此类推，90代表字母Z。表1-2展示了一些从ASCII表中节选的条目。

表1-2　从ASCII表中节选的条目

1.4.2　AES加密：概述

在解释AES加密的细节之前，先来概述一下AES加密的处理流程。

AES使用的密钥是二进制数，密钥大小不是固定的，不过我们将讨论的是使用固定128位密钥的最简单版AES。它在处理时可以通过数学上的密钥扩展，将原始的128位密钥转换为11个128位密钥。

AES在处理时会将明文数据切分成16个字节的小块并放入4×4的格子中，以Send more money!为例，切分结果如图1-14所示，其中的粗线用来切分16个字节，细线用来切分字节中的每个位。

图1-14　示例信息Send more money!被切分成字节格，为AES加密做准备

明文数据会被按需切分成多个16字节的数据块，如果最后一个数据块不足16字节，则剩余位用随机的二进制数来补全。

接下来，AES会对明文数据的每个16字节的数据块都进行10轮加密处理。在每轮加密中，数据块内的字节会被调换顺序，并且会用一个表来替换其内容。然后，再将数据块内的字节与块内其他字节以及那11个128位密钥中的某一个进行异或运算。

以上是对AES的简要概述，接下来让我们来看看其中的一些详细步骤。

1.4.3　AES中的密钥扩展

在数字加密系统中，密钥扩展与我们之前讨论过的“密码本”的概念略有不同。AES密钥扩展不是从一本书中找出一个长点的密钥就行了，它在扩展密钥时，还会使用到那些在后面加密过程中也会使用到的同样的技术。这些技术分别是：二进制异或运算、换位以及简单替换。

图1-15展示了密钥扩展流程的初始几个阶段。图中的每个数据块都是32位，每行相当于一个128位的密钥。原始的128位密钥就是最上面4个数据块，也就是图中的阴影部分，其他的每个数据块都是其前面两个数据块进行异或运算的结果。异或运算由带圆圈的加号来表示。例如，数据块6是数据块2和数据块5进行异或运算的结果。

图1-15　AES的密钥扩展流程

如你所见，在图1-15的右边，每4个数据块都会经过一个带有“附加混淆（Extra Scrambling）”标签的处理，该处理过程会对数据块内的字节进行换位处理，还会根据一个被称为S-box的表去替换每个字节的数据内容。

S-box表在密钥扩展以及后面的加密本身中都会用到，它是被精心设计出来的，用于加强明文间的差异。换句话说，即使是两个相似的明文字节，在经过S-box替换处理后也会呈现出很大的不同。该表的前8个条目如表1-3所示。

表1-3　节选自S-box表

1.4.4　AES加密处理流程

一旦AES拥有了所有需要的密钥，真正的加密便可以开始了。回想一下，二进制的明文数据是被切分存储在多个16字节，即128位的格子中的，每块的大小正好与原始密钥的大小一致，其实这并不是一个巧合。实际加密的第一步是把格子中的128位数据与原始的128位密钥进行异或运算。此刻加密就真正开始了，格子中的数据将会进行10轮数字运算，其中每轮运算又都有4个步骤。

1．替换

使用与密钥扩展处理流程中用到的同样的S-box表，对格子中16个字节的每一个都进行替换处理。

2．行换位

然后，将格子中的行内字节移动到不同位置。

3．列组合

接下来，针对格子中的每个字节，将其所在列的全部4个字节组合起来，并计算出一个新的字节。该计算需要再次用到异或运算，以及二进制形式的换位。为了使你更清楚地了解该过程，图1-16展示了格子中最底行最左侧字节的计算过程。首先对最左侧列中的顶部和底部字节分别进行换位运算，然后再将该列的4个字节异或到一起。顶部和底部字节的这种换位也被称为循环移位（bitwise rotation），字节中的每位向左平移一个位置，而最左侧的那个位将会移动到右侧末尾。

图1-16　AES列混淆运算步骤中的一部分

格子中的每个字节都会进行类似的计算处理，使用异或运算组合其所在列中的所有字节，唯一不同之处是有些字节在异或运算前会先进行循环移位。

4．使用密钥进行异或运算

最后，再将前面几步的计算结果，与该轮处理对应的那个密钥进行异或运算。这就是为什么需要进行密钥扩展，这样每轮处理就可以使用一个不同的密钥来进行异或运算。

AES的解密处理流程，与加密处理流程的步骤相同，只不过是逆序执行而已。由于加密用到的运算只有异或、通过S-box表进行简单替换、以及字节换位，所以在密钥已知的情况下，一切都是可逆的。

1.4.5　数据块链接

AES加密可以单独作用于一个文件的每16字节数据块，但这将导致密文容易受到攻击。就像我们之前所讨论过的那样，加密密钥的使用次数越多，攻击者发现并利用这种加密模式的可能性就越大。由于计算机文件往往都是很庞大的，因此若使用相同的密钥去加密数百万个数据块的话，将会是一种很大规模的密钥重用，导致密文将会被暴露在频率分析以及其他相关技术之下。

出于这个原因，类似AES这种基于数据块的加密系统会做出改进，使明文中即使相同的数据块，也能产生不同的密文数据块。其中一种这样的改进称为数据块链接（block chaining）。

当使用数据块链接时，明文中的首个数据块，会在加密前先与一个随机的128位数进行异或运算。这个随机数被称为初始变量（starting variable），并与密文一同存储。由于每次加密都有一个随机的初始变量，所以起始数据块相同的两个文件，即便使用的是相同的密钥，也会被加密成不同的密文。

随后的每个明文数据块，都会在加密开始前，与前面生成的密文数据块进行异或运算，加密“链接”如图1-17所示。链接确保了明文中即使内容相同的数据块，也会产生不同的密文数据块。这意味着任意大小的文件都可以放心地去加密，而不必担心频率分析的问题。

图1-17　使用数据块链接进行AES加密

1.4.6　AES为什么是安全的

如你所见，尽管AES存在许多步骤，但其每个步骤仅仅是换位或简单替换，那么为何AES会被认为强大到足以保护世界上的数据呢？虽然攻击者可以使用暴力攻击、cribs以及利用密文中隐含的加密模式，但实际上，AES针对上述的所有攻击方式都有极其优异的防御效果。

对AES来说，暴力攻击意味着对每个可能的密钥来说，攻击者都需要将密文进行一遍解密处理流程，直到找出明文为止。在AES中，密钥可以是128位、192位或256位，即使是最小的密钥长度，也存在大约300 000 000 000 000 000 000 000 000 000 000 000 000种可能的密钥，暴力攻击需要尝试大约一半的数量才有望得出正确结果。假设攻击者的计算机每秒可以尝试1百万个密钥，那么每天就可以尝试1 000 000个密钥 × 60秒 × 60分钟 × 24小时 = 86 400 000 000个密钥，1年就可以尝试31 536 000 000 000个密钥。尽管这已经是个很大的数字了，但这甚至连所有可能的100亿分之一都没达到。也许攻击者会有更强大的计算能力，但想要以此就尝试更多的密钥也未必可行，而这还只是128位的版本而已。

AES还会使cribs或想要利用密文中隐含的模式都更困难。因为AES在每轮加密过程中，对数据格中每行的字节都进行了循环移位，并将每列的字节组合到了一起。在经过了多轮这种处理后，字节被充分混合在了一起，使得密文格中任一字节的最终值都取决于明文数据格中的所有字节的初始值。这种加密特性也被称为扩散（diffusion）。

此外，字节经过一轮又一轮的S-box处理后，进一步加大了扩散的效果，然后数据块链接还会将每个数据块的扩散效果传递给后面的数据块。最终，这些运算使AES产生了雪崩（avalanche）效应——明文的任何细微变化，都会导致整个密文产生巨大的变化。

所以无论攻击者有多么了解明文的总体结构，AES都可以阻挠他们。例如，一家公司可能会基于一个通用模板来给顾客发送电子邮件，邮件中唯一的不同之处仅在于顾客的账号以及未付欠款。但通过AES的扩散、雪崩效应和数据块链接处理后，这些邮件的密文将会有很大的不同。扩散和雪崩效应还有助于减少可能会被频率分析所利用的模式。即使某个庞大的明文文件是由相同的16字节数据块反复重复所构成的，通过带有数据块链接的AES加密，也能够产生出非常随机的结果。

1.4.7　AES可能遭受的攻击

AES似乎对传统的加密攻击有很强的抵抗力，但它是否存在某些未知的弱点，使得可以通过一些旁门左道来找出正确的密钥呢？答案不能十分确定，因为举反例是很困难的，只是陈述不存在已知的捷径或漏洞是一回事，但要证明它们不可能存在就是另外一回事了。密码学是一门科学，而科学总是在不断发展的，我们根本无法确定在密码学以及相关的数学发展到何种程度时，我们才能明确说不可能。

想要分析像AES这种开放标准的漏洞是很困难的，难点之一，就在于开发者在其代码中实现标准的时候，可能会在无意中带来安全隐患。例如，某些AES实现，在时序攻击（timing attack）面前就会比较脆弱。时序攻击是指攻击者通过搜集数据加密处理占用时长的相关信息的一种攻击方式，不过攻击者必须能够访问到执行了加密处理的那台特定计算机，所以这并非真正意义上的缺陷。但无论如何，只要安全有可能会受到威胁，那就不能高枕无忧。

目前AES已知最容易遭受的攻击是相关密钥攻击（related-key attack）。当两个密钥存在某种特殊形式的数学相关性，攻击者有时就可以使用从用了一个密钥加密的数据里收集到的信息，去恢复使用另一个密钥加密的数据。研究人员已经发现了某种方法，可以用比暴力攻击更短的时间，恢复某种特殊密文的AES加密使用的密钥。但该方法需要密文是由相同的明文加密而来，并且所使用的密钥也必须与原始密钥存在某些特定的相关性。

虽然这种捷径被看成是一种漏洞，不过对攻击者来说也许并没有实际意义。首先，虽然它极大地减少了恢复原始密钥所需的工作量，但它并不是在任意的某个本地计算机或网络计算机上都可行。其次，想要获得使用了相关密钥加密过的其他密文并不容易，只有当代码的实现上或密钥在使用时存在漏洞的情况下才有可能。因此，这种漏洞目前还仅限于理论上，并非是这种系统实际上的弱点。

不过这种漏洞最令人担忧的一面，是据说它只对加密性更强的AES的256位密钥版有效，而不是本章中所描述的128位密钥版。这或许在某种程度上也反映出了现代加密技术的最大弱点——本身的复杂性。尽管有研究专家们的不断努力，缺陷也可以隐藏多年不被发现。但由于任何设计上的细微变化，都会对安全性带来很大的影响，所以那些试图增加安全性的某些特性，可能就会导致相反的效果。

1.5　私钥加密的限制

像AES这种加密技术的真正限制，其实与其潜在的隐患并无直接关系。

本章中所有介绍到的加密方法，包括AES，都被称为对称密钥（symmetric-key）加密。这就是说加密一条消息或文件时所使用的密钥，与解密时用到的那个密钥是同一个。如果你想通过AES来加密你的台式机硬盘里的某个文件，或者是加密你手机里的通讯录，这并没有问题，因为只有你会去加密或解密这些数据。但是当你需要安全地传输数据时会出现什么情况呢？比如当你在一个零售网站上输入你的信用卡卡号时，虽然你可以使用AES把加密后的数据发送给网站，但是在没有密钥的情况下，网站上的软件是无法解密密文的。

这就是所谓的密钥共享问题（shared key problem），这也是密码学的核心问题之一。若没有一个安全的方式来共享密钥，那对称密钥加密就只能用来加密个人的私有数据。所以针对传输的数据加密，需要使用一种不同的方法，使得可以通过不同的密钥来分别进行加密和解密，这些具体细节将会在第3章中详细介绍。

因为在介绍这些具体细节之前，我们首先需要解决另外一个问题：由于AES需要使用一个很长的二进制数作为密钥，但你不能期望每个用户都能记住一个128位长的字符串，因此我们通过使用密码来解决这个问题。不过事实证明，密码的安全存储和使用也有其自己的问题，而这些也正是下一章的主题。

第2章　密码

软件最重要的任务之一就是保护密码。你也许会很奇怪，密码不就是那些提供（provide）保护的系统的一部分吗？难道密码不能为我们在银行、网络商城以及在线游戏中的账户提供安全保护吗？

事实上，由于密码是计算机安全的基石，所以它也就成了攻击者的重点关注对象。如果远程计算机根据你的密码来接受你的身份（该过程称为身份认证authentication），那它就必然会拥有一份用户密码列表用来进行验证，这个密码列表对攻击者来说便是一个诱人的攻击目标。近年来发生了多起用户账户数据大规模失窃的事件，这是如何发生的？怎么做才能降低此类事件出现的概率？这些便是本章要讲述的主要内容。

在学习如何保护密码之前，先来看一下如何将密码转换成二进制数，该过程对于密码的存储和加密都有重要意义。

2.1　将密码转成数字

在第1章中，你已经学到了如何将单个字符替换成ASCII表中的数字。在本章中，你将会学到如何将一个字符串替换成一个较大的数字，比如AES需要用到的长度为128位的密钥。在计算机中，将某种数据转换成指定范围的数字被称为散列（hashing），转换生成的数字被称为散列码（hash code）、散列值（hash value）或者就叫散列（hash）。

在这里，散列（hash）这个词的意思是指，像做土豆煎饼那样，把材料切碎后再把碎块塞回到一起。一个特定的散列方法被称为一个散列函数（hash function）。在散列一个密码时，总是先把密码中的每个字符，通过像ASCII这样的编码系统转换成数字。而如何把这些数字再组合到一起，每个散列函数却各不相同。在加密和身份验证系统中用到的那些散列函数必须经过精心的设计，否则便无法保障其安全性。

好的散列函数的特征

要设计出一个好的散列函数并不容易。为了理解散列函数将会面临到的诸多问题，我们以一个短密码dog为例。在该密码中含有3个ASCII字节，所以也可以说它是一个长度只有24位的数据。然而由于AES密钥至少需要128位，因此一个好的散列函数必须能够将这24位数据，转换成拥有以下特征的128位散列码。

1．充分利用所有数据位

像AES这种基于计算机的加密系统的加密强度主要在于其密钥大小（key size），使得存在大量的可能性以此来抵御攻击者。但是，如果在实际的使用过程中，并未充分利用到所有的可能性的话，则其加密强度也将不复存在。因此，一个好的散列函数所产生的散列码必须能够充分利用到所有的可能性。即使对于我们的短密码dog来说，虽然其只含有24个数据位，但是每个数据位也必须能够影响到最终生成的那个散列码的全部128个数据位。

2．不可逆性

在第1章中，你已经知道了加密方法必须是可逆的。但与此相反，一个好的散列函数，却不应该是可逆的，本章稍后将讨论这点的重要性。现在，知道对于一个给定的散列码，不应该有直接的方法可以恢复产生它的某个密码就行了。注意，这里我说的是某个密码，而不是那个密码，这是因为可能会有多个密码可以产生同样的散列码，这也被称为散列碰撞（hash collision）。由于密码的可能性比散列码更多，所以碰撞是无法避免的。一个好的散列函数，应该使攻击者难以找出任何一个可以产生给定散列码的密码。

3．雪崩特性

加密中至关重要的雪崩特性，对散列来说同等重要。密码的任何细微变化，都会使散列码产生巨大的改变。尤其是当许多人重置密码时，新密码往往仅比旧密码有一点细微差异，那么这点就显得更重要了。例如dog产生的散列码，应该完全不同于如doge、Dog或odg等这些近似密码产生的那些散列码。

2.2　MD5散列函数

要达到上述所有这些标准并不容易，而好的散列函数会以一种很巧妙的方式来解决这个问题。这些好的散列函数往往会用到一段无规则的数据，并使用密码中的位布局，进一步修改这段数据。而这也是广泛使用的被称为MD5的散列函数所使用的方法。MD5即消息摘要（message digest）散列函数第5版。

2.2.1　密码编码

首先，MD5将密码转换成一个长度为512位的数据块，我将其称为密码编码（encoded password）。该编码的起始部分，由密码中字符的ASCII编码来组成。例如，假设密码是BigFunTime，第一个字符是B，对应的ASCII字节是01000010，所以密码编码的前8位就是01000010。接下来的8位是i对应的ASCII字节，也就是01101001，以此类推。因此，本例中密码BigFunTime的10个字母，将会占用512个数据位中的前80个位。

然后剩余的数据位需要被填满。将下一位设置为1，剩下的除了最后那64个位都设置为0，最后那64个位以二进制形式存储原始密码的位长。在本例中，密码有10个字符，即80个位长。80的64位二进制形式如下：

00000000 00000000 00000000 00000000 00000000 00000000 00000000 01010000

显然，不需要用64个位来存储密码的位长。不过用64个位来存储位长，使MD5可以散列任意长度的数据。稍后我们将会看到这样做的好处。

图2-1展示了示例密码的编码，组织成16行、每行32位的形式。

图2-1　将密码BigFunTime转换成512位作为MD5散列函数的输入

由图2-1可以看出，这个密码的编码中到处充斥着0，因此并不符合一个好的散列函数应该“充分利用到所有数据位”的特征，不过没关系，这只不过是开始，并不是最终的散列码。

2.2.2　按位运算

MD5散列函数用到了一些我之前没有讲过的运算，下面先来简单地来了解一下它们。

1．二进制加法

第1个新的运算是二进制加法（binary addition）。该运算很像你已经知道的十进制加法，只不过它用的是二进制数。例如，数字5的32位形式是：

00000000 00000000 00000000 00000101

数字46的32位形式是：

00000000 00000000 00000000 00101110

如果把5和46加到一起，结果是51。同理，这两个数的二进制形式相加的结果，就是51的二进制形式：

00000000 00000000 00000000 00110011

与普通加法不同的是，该运算的结果有时会比参与运算的对象本身有更多的数位。在二进制加法中，位的数量是固定的，如果两个32位的二进制数相加后，结果超过了32位，那么就忽略掉左侧超出的部分，只保留右侧的32位。这就像是你在使用一个廉价的计算器时，由于它最多只能显示2位数，所以当75和49相加时，将只会显示最后的两位数24，而不是124。

2．按位非

接下来的新运算被称为“非（not）”，该运算通常写成大写NOT的形式。如图2-2所示，非“翻转”了所有的数据位，把每个1替换成0，把每个0替换成1。

图2-2　按位非运算。所有位都被翻转，为清晰所见，高亮显示了所有为1的位

3．按位或

下一个新运算是或（OR），有时也称之为同或（inclusive-OR），以便与第1章介绍的异或（exclusive-or，XOR）有所区分。或运算是将两个具有相同位数的二进制数对齐摆放，然后依次比较二者的每个位，只要有任意一个数的某位是1，那结果中该位就是1，否则就是0，如图2-3所示。

图2-3　按位或运算。两个输入数只要有任意一个的某位是1，则结果中的该位就是1

注意，该运算与异或不同，不能通过两次或运算来得回原始数据，这是个单向操作。

4．按位与

最后一个新运算是与（AND）。对齐摆放的两个二进制数，若某位都为1，那结果中该位就是1，否则就是0。所以结果中的1，意味着两个数的该位都是1，如图2-4所示。该运算和或运算一样，也是不可逆的。

图2-4　按位与运算。若两个输入数的某位都是1，则结果中的该位也是1

2.2.3　MD5散列流程

现在可以开始进行一部分散列处理了。在MD5的处理流程中，密码编码块仅会短暂登场使用，不过正是这短暂登场，使得一切大不相同。MD5在处理时会用到一个固定的128位数据作为开始，这128位从概念上可以分为4个32位的数据段，如图2-5中标签A到D所示。

图2-5　MD5散列码的起始128位结构

从这里开始，接下来都是关于循环移位并翻转的处理，并且重复处理次数高达64次。从这点来说，这个处理过程很像AES，不过它有更多的处理次数。图2-6是这64次处理中某次的概括性示意图。

图2-6　MD5散列函数的某轮处理。结果中有3个数据段只是原数据段换了一下位置，
而剩下的那个是由原来的所有4个数据段组合在一起新生成的

如图2-6所示，B、C、D数据段只是由原数据段经过简单的调换位置生成的，所以一轮处理中的D数据段，会变成下一轮处理中的A数据段。在MD5的每轮处理中都含有一个“额外混淆”的处理，其主要功能是用前一轮的所有4个数据段生成出一个新的数据段。它使用与、或、非等不可逆运算，把这4个数据段与密码编码中的某一行进行组合，并且在不同轮的处理中会使用密码编码的不同行，所以最终密码编码的每一行都会被多次使用到。另外由于在每轮的处理中会对其中3个数据段分别调换位置，所以仅需要4轮处理，就可以在额外混淆的作用下，替换掉原始4个数据段中的每一个。这样一来，在经过64轮的处理后，原始数据段中的所有位，都将和密码编码彻底混在一起。

2.2.4　达到好的散列函数的标准

由于MD5始于各式各样的数据位，然后又一遍又一遍地改变这些位，并混合了密码编码，所以可以确定所有位都会受到影响，最终产生出真正的128位散列码。其中大量的运算都是不可逆的，并且处理流程有64次之多，这意味着整个散列函数都是不可逆的。此外每轮的额外混淆都会移动并修改数据位，并使其相互组合在一起，这样一来，通过不断传递的数据位和字节，最终就能达到我们希望的雪崩特性。

因此，MD5达到了一个好的散列函数的所有基本需求。不过，它确实也存在一些小缺点，这些稍后便可以看到。

2.3　数字签名

散列函数除了可以为密码创建密钥外，在安全领域还可以有其他多种用途，其中最重要的用途之一就是用来创建文件签名（signatures）。如前所述，MD5可以处理任意大小的输入数据，如果输入数据大于512位，则首先将其切分成多个512位的数据块，然后MD5再去分别处理每个数据块。首个数据块使用那个固定的128位数据进行处理，随后的每个数据块都使用上一个数据块产生的散列码进行处理。通过这种方式，可以将该散列函数作用于本书的全部文本、某个音频文件、视频文件或是其他任何数字文件，最终得到一个单独的128位散列码。而这个散列码就可以作为对应文件的签名。

为何一个文件需要有签名？假设你已经决定要下载FreeWrite这个（虚构的）免费文字处理应用程序，你可能会很谨慎，因为下载的免费软件可能是假冒的，甚至其中还可能会含有恶意软件，你可能有过这种不愉快的经历。为了避免这种情况，你希望可以有办法来确定你下载的FreeWrite文件与开发者上传的是同一个文件。这时开发者就可以使用MD5来散列该文件，并将生成的散列码，也就是文件签名，发布到他们的网站上——freewrite.com。如此一来你就可以使用MD5散列程序来散列你下载的文件，并将散列结果与开发者网站上的散列码进行比较。如果你生成的散列码与网站上的签名不匹配，那就说明有什么东西已经被修改了，可能是文件本身，也可能是签名，或者两者皆是。

2.3.1　身份问题

不过，通过匹配开发者发布的散列码来验证FreeWrite文件合法性的这种做法，仅在散列码确实是由开发者发布的时候才有效。但问题在于，攻击者可以复制开发者的freewrite.com网站，并将其发布到一个相似的域名，如free-write.com，然后再上传一个有害的文件以及该有害文件的散列码。如果攻击者真这么做了，该怎么办？由于数字签名和开发者本身是唯一可以信任的，若是两者都不可信，是不是就没有办法去处理了呢？我们将在第3章中进一步探索此类问题的具体细节。

2.3.2　碰撞攻击

即使匹配的散列码来自于一个合法的来源，文件也还是可能会有问题。由于许多不同的文件可能会产生相同的散列码，这意味着如果攻击者恶意修改一个文件，使新修改的文件能与原文件产生相同的散列码，就可以避免被检测出来。

想要生成两个具有相同散列码的文件并不困难，这就是所谓的碰撞攻击（collision attack）——随机生成一些文件，直到有两个文件的散列码相匹配。所幸的是，想要生成第二个文件来匹配另一个文件的特定（particular）的散列码就困难多了。若攻击者真想这么做的话，那么能够匹配散列码的这个文件就不能只是一些随机的字节，而必须由满足攻击者意图的恶意程序来产生。

不幸的是，确实有一些方法可以用来生成具有相同散列码的第二个文件，而且还能做到与第一个文件非常相似。发现MD5散列函数的这一缺陷后，研究人员建议使用其他散列函数来进行签名。这些更高级的散列函数，通常会产生更长的散列码（长达512位）、更多的散列处理流程以及每轮处理流程中更复杂的二进制数学运算。不过就像加密一样，并不能保证这些更复杂的散列函数就不会存在漏洞。由于攻击者会无情地利用漏洞，故妥善使用签名就意味着可以比这些已知的设计上的漏洞领先一步。数字加密就像是猫和老鼠的游戏，好人就像老鼠，试图避免被猫吃掉，但永远也不可能打败猫，只能希望可以生存得更久一些。

2.4　身份认证系统中的密码

在身份认证系统中，这种猫和老鼠的游戏更为突出。每处你输入密码的地方，服务器端都需要有一个密码列表来进行比较，所以该列表需要格外小心去保护。

2.4.1　危险的密码表

让我们来看看以最简单的方式存储的密码表。在本例中，Northeast Money Bank （NEMB）保存了每一位客户的用户名、密码、账号以及当前余额。其中节选出来的一段密码表如表2-1所示。

表2-1　设计糟糕的密码表

就像柯克霍夫原则（Kerckhoffs’s principle）所说的那样，我们不能依赖于加密方法来保证加密，同理，我们也不能依赖于密码列表来保证加密。NEMB信息技术部门里的某个心怀不轨的员工，可能很轻易就能获得这个密码列表文件，即使是外部的攻击者说不定也能绕过公司的防御系统并获得密码列表文件。

这就是所谓的单点防御（single point of defense），即一旦有人看到了这个表，那就没什么秘密可言了。原因很简单，首先，该表列出了所有客户的账号和余额，一旦暴露，至少这将是客户隐私的重要损失。更糟糕的是，该表还存储了所有客户输入的密码。攻击者利用这个密码列表，就可以冒充任何一位客户的身份进行登录，这将是一场灾难。

幸运的是，这种存储系统存在的问题可以很容易改进。你也许会认为，既然知道了这种系统存在的诸多问题以及其危险性，那它们应该永远不会被使用。遗憾的是，这次你想错了。现实中真的有很多公司就是这样存储用户密码的。有很多非常大的公司，可能花了很多钱用于开发他们的网站，但后来被发现就是这么做的。

2.4.2　对密码进行散列

如果表2-1展示的是错误的做法，那正确的做法应该是怎样的呢？改进方法之一，就是不要在表里存储密码，而是存储密码的散列码，如表2-2所示（在该例中，我展示的是十进制数形式的散列码，以便控制它们的长度）。

表2-2　存储了密码散列码的密码表

当用户尝试登录的时候，系统会先把用户提交的密码散列成散列码，然后再用这个散列码与表中存储的散列码进行比较，如果二者匹配成功，那么用户就可以登录。由于散列函数是不可逆的，拿到了这个表并不代表就能拿到密码，所以攻击者是不可能通过使用散列码去登录某个账户的。

不过，账号和余额仍然是以明文形式存储的，把它们也加密起来会是个不错的做法，这样表中就只有散列码和密文了。问题是，如果我们把密码的散列码作为加密的密钥的话，其实也不能提供什么额外的保护，因为密钥就在表中，任何人只要获得了这个表，也就能够解密密文了。

有很多方法可以解决这个问题，其中一种解决方案是，使用一个散列函数来为身份认证系统转换密码，然后使用另外一个散列函数来将密码转换成用于加密账号和余额的密钥。这样一来，只要散列函数是不可逆的，那么即使攻击者得到了密码表，该解决方案仍然可以为账户数据提供安全保护。

2.4.3　字典式攻击

对密码进行散列，能够有效地防御攻击者。但这还不够，身份认证系统在字典式攻击（dictionary attacks）面前仍然很脆弱。

在一个基本的字典式攻击里，由于攻击者无法获得密码表，所以就不得不去猜测密码。若只是去尝试一些随机拼凑出来的字符，成功率必然不高，但如果使用了字典（dictionary）加以辅助的话，成功率就会更高一些。在软件世界里，字典就是一个简单的单词列表，而在字典式攻击里，字典就是一些最常用的密码的列表，就像下面这样：

• password。
• 123456。
• football。
• mypassword。
• abcdef。

为了抵御这种基本的字典式攻击，大多数网站都会统计登录失败的次数，在失败一定次数后（也许只有3次），就会暂时阻止从这台特定计算机发起的后续登录。这就使得那些想要通过反复尝试来获取正确密码的攻击变得不切实际。

在攻击者已经获得了散列过并加密过的密码表时，往往会用到字典式攻击的另一种形式。在这种情况下，攻击者会对字典中的每个密码进行散列处理，然后再将散列结果与窃取的密码表中的每个散列码做对比，一旦发现了匹配，攻击者就知道字典中的这个密码会生成用户的散列码。为了节约时间，攻击者会选用一个散列函数，把字典中的所有密码一次性全部散列，然后将散列结果存储在表2-3所示的字典中。

表2-3　存储了散列码的字典

字典式攻击说明了为何在设置密码时选择那些不常用的密码是如此重要，因为密码越复杂，出现在攻击者字典中的概率就越低。

2.4.4　散列表

不幸的是，攻击者可以完全抛弃字典，构建一个含有随机生成的密码以及对应散列码的表，我们将这种表称为预计算散列表（precomputed hash table）。当然了，由于潜在的密码数量是很庞大的，所以，如果攻击者希望拥有良好的匹配概率的话，那么该散列表也需要很庞大。要构建出一个预计算散列表，需要消耗大量的计算能力和时间，不过只需要构建一次，然后就可以无限重复使用了。

该表的缺点之一，是它庞大的规模使得搜索匹配速度极低。我这么说你可能会觉得很奇怪，因为文字处理软件不就可以快速地从一个大文档里找到特定的单词吗？但是你要知道，这种预计算表将会比你计算机上的任何文件都大得多。假设攻击者的某个这样的表中所有的密码都是由10个或更少的大小写字母和数字组成的，那么即使存在这些限制，潜在的密码数量也有62¹⁰之多，也就是839 299 365 868 340 224种可能性。虽然预计算散列表不需要全部的这些潜在的密码，但至少也需要其中相当大的一部分。由于这个表如此庞大，以至于无法存储在计算机的内存中，甚至无法存储在硬盘上。更直接点来说，它太大了，可能需要存储到上百万个硬盘里。而这还仅仅是存储上的问题，如何对其进行搜索呢？除非你有像Google这样的分布式计算能力，否则想要在如此庞大的表中进行搜索基本不可能（即使是Google，想要在如此庞大的数据中进行搜索也很难，我们将在第7章中探索搜索上的具体细节）。

2.4.5　散列链

由于预计算散列表对于存储和搜索来说都太庞大了，所以攻击者使用了一种被称为散列链（hash chaining）的更巧妙的技术，从而能够极大地减少预计算散列表中存储条目的数量，同时又不会降低它的功效。这种技术使用了一种不同类型的函数，被称为归约函数（reduction function）。该函数与散列函数有着同样的数学变换，但作用目的却相反。它并不是将密码转换成散列码，而是将散列码转换成密码。不过这里所说的密码并不是用来生成该散列码的那个原始密码，而只是一种简单的保持了有效密码形式的字符序列。

接下来我们来看一个散列链的例子。首先将glopp26taz使用MD5进行散列处理，生成了如下所示的散列码：

22,964,925,579,257,552,835,515,378,304,344,866,835

然后使用归约函数将此散列码转换成一个新的有效形式的密码，如7HGupp2tss。接着反过来，对这个新密码进行散列处理，以便生成另一个新散列码，然后对这个新的散列码进行归约处理，从而生成另一个新密码，以此类推。这种密码和散列码的交替序列就是散列链，如图2-7所示。

通过使用散列链，攻击者就不必去保存所有可能的密码和对应的散列码。相反，攻击者会生成一系列长度相同的散列链，然后仅将每个散列链的首尾部分存入表中。图2-7所示的散列链，对应的就是表2-4中所展示的第3条。虽然在该表中总共只有5条数据，但由于每条数据都对应了一个含有3个密码-散列码对的散列链，所以最终算来，该表实际上等价于一个简单的有15条数据的表。

图2-7　在散列链中，散列函数（H）和可以用散列码生成任意密码的归约函数（R）交替进行处理

表2-4　存储散列链的表

图2-8展示了使用该表的一个例子。假设攻击者试图恢复散列码117,182,660,124, 686,473,413,705,332,853,526,309,255的密码，那么就必须先判断出表中的哪条散列链含有目标散列码。首先，攻击者将目标散列码与表的末尾列中的每个数字都进行比较，由于在该列中没有找到匹配，随后攻击者使用归约函数，将目标散列码转换成一个新的密码，接着再使用散列函数将此新密码转换成另一个新的散列码，然后再从表的末尾列中查找这个新的散列码。上述处理过程将会持续进行，直到找到匹配，或者处理次数达到3次为止（该表中散列链的长度为3）。

在该例中，初始的目标散列码先被归约成密码pRh7T63y，然后对这个密码进行散列处理，生成一个新的散列码。随后发现表的第3条，即以密码glopp26taz开始的那个散列链中含有此散列码，这就说明该散列链可能会含有目标密码，但是攻击者必须迭代散列链才能获得想要的密码。由于该散列链的起始密码的散列值与目标散列值并不匹配，所以只能通过归约函数生成一个新密码7HGupp2tss，并再次散列，而这次新生成的散列码与我们的目标散列码匹配成功，这意味着7HGupp2tss就是我们要找的密码。

图2-8　使用存储了散列链的表来查找能生成特定散列码的密码。无论是目标密码还是对应的
散列码都未列在该表中

通过使用散列链，可以极大地减少预计算密码表的大小，并且仍然提供了同样规模的可用于查找匹配的数据量。例如，如果一个散列链中含有100个密码和100个散列码，那么匹配其中任意一个散列码的密码，都可以间接地通过该散列链被找到，尽管该散列链在表中只存有1个密码和1个散列码。因此我们可以说这个存储了散列链的表，效用是普通预计算散列表的100倍。

不过，使用散列链也存在一些潜在的问题。其中一个问题就是使用散列链进行查找带来了更大的计算量。另外，由于存在多个密码可能会生成同样的散列码这种碰撞问题，因此即便是一个匹配的散列链，也不一定就含有那个查找的散列码以及与之匹配的密码。该问题也被称为散列链合并（chain merging），这对于我们这些关注数据安全的人来说也算是些许安慰。实际上，有一些方法可以减少散列链合并的问题，但即使没有这些方法，无疑还可以针对那些特定的散列函数去建立有效的预计算散列表，那些使用了相应散列函数的密码将很容易受到威胁。

2.4.6　迭代式散列

阻止构造预计算散列表的方法之一，是多次使用散列函数。由于一个散列函数的输出结果也是可以被散列的，所以可以使用同样的散列函数，将原始密码进行任意次数的散列。不巧的是，该技术也被称为散列链，不过为了避免概念上的混淆，我将其称为迭代式散列（iterative hashing）。图2-9展示了对密码football的5次迭代式散列。

图2-9　多次使用同一个散列函数进行散列

通过该技术，在存储密码时或是用户登录验证时，密码会被多次散列。为了攻破该技术，攻击者需要基于同样的概念，将选定的散列函数运行同样的次数，以此来构造预计算散列表。根据柯克霍夫原则，我们知道加密系统不应依赖于其加密方法本身的加密。所以迭代式散列的目的，不是去掩盖密码的散列次数，而是使攻击者在构造预计算散列表时变得十分困难。在图2-9的例子中，密码被散列函数散列了5次，这就使攻击者构造预计算散列表的时间可能会加长5倍。在真正投入使用时，密码可以被散列函数散列成百上千次。这样做足以阻止攻击者构造可用的预计算散列表吗？可能吧，我也无法给你确切的答案。因为计算机的运行速度日新月异、越来越快，在绝大多数情况下，这种持续提升的计算能力非常棒。不过有盈就有缺，计算能力在提升的同时也在不断地打破一些原本存在的实际限制，而我们绝大多数的信息安全正是建立在这些实际限制之上。

人们在构建这种基于迭代式散列的密码系统时，往往会面临迭代次数选择的问题。为当前来选择迭代次数以提供良好的安全保护相当容易，难的是预测1年后、2年后甚至10年后所需的迭代次数。

你也许会认为，最佳选择是用极大的迭代次数以防御未来计算机的计算能力。但问题在于，若真这么做的话，当前的计算机在处理合法登录时就会面临困难。你愿意等待5分钟来访问你的某个网络账户吗?

2.4.7　为密码“加盐”

身份认证系统需要一种方法，使其可以在强化散列效果的同时，又没有迭代式散列的性能损失。换句话说，该系统需要一种存储密码的方法，使其可以在大幅度增加攻击者投入时间的同时，又不会妨碍正常登录。这种方法被称为“加盐（salt）”。“加盐”是对此概念的一个很形象的术语，我真想为当初想出该词的那个人点赞。在烹饪时，一撮盐可以极大地改变一道菜的味道，而在密码学中，为一个密码“撒一小撮盐”可以显著地改变它的散列码。

下面是它的工作原理：当一个新用户在注册账户并设定用户名和密码时，系统自动地为该账户生成“盐”。“盐”是一个字符串，就像一个短的随机密码，在散列前先与用户的密码组合起来。例如，用户mrgutman使用falcon作为他的密码，然后系统生成了h38T2作为“盐”。

“盐”和密码可以使用任何方式组合到一起，最简单的方式就是将“盐”附加到密码的末尾，在该例中，组合后的结果就是falconh38T2。然后对组合后的结果进行散列，并把生成的散列码与用户名和“盐”一起存入身份认证表中，如表2-5所示。

表2-5　使用了“盐”的密码表

每次用户请求登录时，都会在散列处理前，把“盐”附加到用户输入的密码的末尾。攻击者即使获得了该身份认证表，也不会有多大用处。因为尽管该表中可能会含有可以散列成给定散列码的密码，但这些密码都是与“盐”组合后的密码，因此不会生成原密码对应的散列码。相反，攻击者需要根据特定的“盐”来构造预计算表，这也许可行，不过别忘了“盐”也是随机生成的，如果这份窃取的身份认证表中含有100 000个用户，并且“盐”足够多，在表中没有重复，那么攻击者就需要构造100 000个预计算表。基于这点来说，我们甚至不能将它们称为预计算表，因为攻击者在每次攻击时都需要构造它们。

2.4.8　密码表安全吗

“加盐”和迭代式散列通常会一起使用，给攻击者创造真正的难题，使其头痛不已。迭代式散列增加了构造预计算散列表的所需时间，“加盐”意味着攻击者不得不构造大量的表。但是这样的组合就足够了吗？

这个问题没有明确的答案。加密研究人员和安全专家在继续开发新的防御技术，以防止未经授权的登录访问，与此同时，攻击者也在持续寻找新的攻击方法来突破防御。先进的计算能力和编程理论会帮助优先利用了它们的那一方。

也许关于此节讨论的最重要的结论就是，安全通常不受用户所控制。生活中总会有漏洞，但用户并没有途径去知道一个特定的网站或服务是否采用了最佳的安全实践。例如“加盐”技术，只有使用了它的那些系统才能受惠，但并不是每个系统都会这么做。

2.5　密码存储服务

以上讲述的都是关于密码是如何在远程身份认证系统上存储的。但在用户端又是怎样处理的呢？我们又该如何安全地存储密码呢？

在以前，我只有几个密码，所以我可以放心地将它们委托给我的记忆，但最终我意识到我必须通过其他方式来存储密码。不过若是把密码写到一张纸上的话，那只不过是安全隐患的另外一种形式罢了。有一段时间，我使用了一个精心设计的自制解决方案，它使用一个由AES加密的.txt文件，然后将其存储在一个记忆卡中，最后再将该记忆卡放置到一个可能不是100%防火的铁盒里。这样的设计安排可以安全地存储密码，只不过每当我需要查找一个密码时，我就不得不打开铁盒，拿出记忆卡，并将其插入到我的计算机上，然后再双击这个.txt文件，输入密码（我必须记住的那个密码），最后在表中找到我需要的那个密码。

最终我放弃了这种方式，并注册了一个基于网络的密码存储服务。当我为该服务创建账户时，我设置了一个主密码，然后将我所有其他的用户名和密码都存到了这个网站上。这些数据信息使用了一种特殊的方式存储，任何人即使得到了原始数据，也不会有太大的用处。假如我的Amazon密码是chickenfat（实际上并不是），密码存储服务并不会将单词chickenfat存储在服务器的任何地方，相反的，我的浏览器中的某个程序，会在密码被发送给密码存储网站之前，使用我设置的主密码将这个将要发送出去的密码加密并生成密钥。因此，即使该密码存储服务被攻击者攻破了，他们在没有主密码的情况下，也无法获取我的这些个人密码。

主密码本身也不会被保存到密码存储网站中。当需要对密钥加密或解密以便进行个人登录时，主密码会被“加盐”处理，并根据我指定的迭代次数进行多次反复散列。

可以这么说，使用密码存储服务就像是把所有的蛋放到了一个篮子里，这使我可以随心所欲地为我的每次登录实施最佳安全实践。之前我可能需要使用一些我认为我记得住的单词和数字来拼凑成我的密码，而现在我的密码可以是很长的随机组合，并且它们可以各不相同，因为我不再需要去全部记住它们了。

2.6　小结

在本章讨论的关于身份认证系统的所有内容中，我避开了一个至关重要的细节。由于身份认证系统会将存储的用户密码和登录系统提供的密码进行比较，但是用来进行身份认证的那台远程计算机，是如何获得用户在初始时设置的那个密码的？数据若想安全传输就需要进行加密，这就意味着在用户端需要对密码进行加密，但远程身份认证系统在没有密钥的情况下，如何才能解开这个加密后的密码呢？这将我们带回了密钥共享的问题，如果这个问题不解决，那我们在本章中讨论的所有内容都会变得没有意义。所以这些问题就是我们在第3章中所要讨论的主题。