现代密码学概论（3 Edition）

by Jonathan Katz and Yehuda Lindell

1.1 密码学和现代密码学

​ 简明牛津英语词典（第9版）定义密码学为“编码或解码的艺术”。这在历史上是准确的，但是没有捕捉到该领域的广度或其现代科学基础。这个定义只关注了几个世纪以来一直用于实现秘密通信的代码。但如今的密码学包含的远不止这些：它处理确保完整性的机制、交换密钥的技术、进行用户身份验证的协议、电子投票、加密货币等等。在不试图提供一个完整的描述的情况下，我们会说，现代密码学涉及到保护数字信息、数字系统和分布式计算免受对抗攻击的数学技术的研究。

​ 字典中也将密码学定义为一门艺术。实际上，直到20世纪末，密码学都还是一门艺术。构建好的代码，或者打破现有的代码，依赖于创造力和对代码运作方式的深刻理解。几乎没有什么理论可以依赖，并且很长一段时间内，都没有关于什么能构成一个好代码的有效定义。从20世纪七八十年代开始，密码学景象从根本上发生了改变。一个丰富的理论开始出现，这有可能将密码学作为一门科学和一门数学学科来进行严格研究。这一观点反过来又影响了研究人员对计算机安全中更广泛领域的看法。

​ 古典密码（或者说20世纪八十年代之前的）与现代密码中另外一个非常重要的区别在于它的适用性。在历史上，密码学的主要消费者是军事组织和政府。现在，密码学无处不在！如果你曾经通过输入密码来证明自己，通过信用卡在网上购买东西，或者下载了你的操作系统的验证更新，你就使用了密码学。越来越常见的是，经验相对较少的程序员被要求通过结合加密机制来“保护”他们编写的应用程序。

​ 简而言之，密码学已经从一种为少数特定应用场景提供加密通信的启发式技术，发展成为一门帮助全世界普通人保护系统的广泛化的科学。

1.2 私钥加密的设置

​ 经典密码学关注点在于设计和使用密码，使得通信双方能够发送消息，同时保证对能够监听他们之间所有通信的监听者隐藏这些消息。在现代说法中，密码被叫作加密方案，也是我们要使用的专业术语。所有经典加密方案的安全性依赖于密钥–即通信方事先共享而窃听者不知道。在此场景中，通信方提前共享的秘密信息，称作私钥(private-key、shared-key、secret-key)。在描述一些历史加密方案中，我们更常讨论私钥加密。在私钥加密情景里，双方共享一把钥匙并且在他们想进行秘密通信时使用这个密钥。一方使用这个共享密钥加密(encrypt)消息（也即明文，plaintext），并将其以密文(ciphertext)形式发送给接收方。接收方使用相同密钥解密(decrypt)密文并恢复原始消息。使用相同的密钥可以将明文转换为密文并转换回来；这也就是为什么这种状况也叫做对称密钥(symmetric-key)，这依赖于双方在加密和解密时使用相同的密钥这一事实。与之相反的是非对称加密(asymmetric-key)也即公钥(public-key)加密，加密与解密使用不同的密钥。

​ 如前所述，加密的目标是保持明文对窃听者来说是隐藏的，而窃听者可以监视通信信道并且观察到密文。

​ 对于对称密码系统有两个规范化应用。首先，通信双方在空间上是分开的，假定这两个用户能在通信前安全地共享密钥（需要注意的是，如果一方通过公共通信信道向另一方发送密钥，则窃听者也能获得密钥）。这是可以实现的，比如说可以通过让双方在分离前在一个安全地点进行物理相见来共享密钥。在其他情况下，安全共享密钥是比较困难的。（空间上，同一时间内两不同地点的通信双方可使用对称密码满足保密通信的要求）

​ 对称密钥系统的第二个广泛的应用场景涉及到同一方随着时间推移与自己通信。（时间上，同一地点的不同时间维度的双方使用对称密码进行保密通信）。比如思考一下磁盘加密，使用者加密一些明文并且在他的硬盘驱动上存储生成的密文；同一用户可在稍后的一个时间点内返回来解密密文并且重新获得原始数据。这里的硬盘充当了通信信道，如果攻击者可以获得硬盘并且可以读取其内容时就可能窃听。虽然用户依然需要一个安全可靠的方式来记录/存储密钥以供日后使用，但“共享”密钥现在已经很常见了。

加密的语法：正式地说，私钥加密方案是通过指定消息空间M（Message Space）和三种算法来定义的：生成密钥的过程（Gen）、加密的过程（Enc）和解密的过程（Dec）。消息空间M定义了一组“合法”消息，即方案支持的消息。方案中的算法有以下功能：

1、密钥生成算法Gen：是一个概率性算法，输出根据某种分布选择的密钥k

2、加密算法Enc：输入明文m和密钥k，输出密文c。我们用Enck(m)来表示使用密钥k对明文m加密

3、解密算法Dec：输入密钥k和密文c，输出明文m。我们用Deck(c)来表示使用密钥k对密文c解密

加密方案必须满足以下正确性要求：对于Gen输出的每个密钥k和每条消息m∈M，必须满足：Deck(Enck(m)) = m 即：加密一条消息，然后使用相同的密钥解密生成的密文，能够得到原始消息

由密钥生成算法产生的所有可能密钥的集合叫做密钥空间记作K。Gen几乎总是从密钥空间中统一地选择一个密钥；事实上，人们可以在不丧失一般性的情况下假设情况就是这样。

​ 回顾我们之前的讨论，一个加密方案被希望安全通信的双方使用。首先，Gen运行来获得通信方共享的密钥k；然后，当一方想发送明文m给另一方时，计算c := Enck(m)并且把生成的密文c通过公共信道发送给另一方。收到密文c，另一方计算m := Deck(c)来获得原始明文。

**密钥和Kerckhoffs原理：**就像之前提到的，如果一个窃听敌手知道Dec以及通信双方共享的密钥k，那敌手就能解密通信方传送的任何密文。为此，通信方必须安全共享密钥k,并且保证k对其他所有人完全隐蔽。可能也需要保证Dec安全？就此而言，他们对加密方案的所有细节保密不是更好吗？

在19世纪末阐明军用密码的几个设计原则时，Auguste Kerckhoffs提出了相反的观点。其中一个重要观点，被称作Kerckhoffs原理，内容：**密码方案并不需要保密，而且它必须很容易被敌方获取。**也就是说，一个加密方案应该被设计为即使窃听者知道方案的所有细节，但只要他不知道所用密钥，就是安全的。换句话说，安全性不能依赖于加密方案的保密性，而应该仅仅依赖于密钥的隐秘性

支持该原则的主要依据有三个：①保证短的密钥的隐秘性比保证整个复杂的密码方案的安全性容易很多。尤其是当加密被广泛使用时这一点尤为重要。比如说，当一些组织中的所有雇员之间需要加密通信时，除非每一对参与方都使用自己的、唯一的方案，否则一些参与方会知道其他参与方正在使用的方案。而且，关于加密方案的信息可能会被一些雇员泄露，或者被攻击者采用逆向工程获得。简言之，假定加密方案能保持安全性是不现实的。

②如果诚实的共享方的秘密信息被泄露，**更换密钥比更换整个加密方案要容易得多。**此外，生成一个新的随机密钥相对简单，而设计一个新的加密方案则是一项巨大的任务。

③在加密方案广泛应用之前，鼓励大家对方案进行评判可以检查出其中的弱点。往长远来说，加密方案的标准化是很有必要的，使得（1）不同用户兼容（2）公众可使用经过大量审查后的强方案。总的来说，也许与直觉相反，广泛地、公开地传播加密方案的全部细节是有利的，这与保守方案的秘密正好相反

​ 如今，Kerckhoffs原则被理解为主张将整个密码设计过程完全公开，这与隐密安全的概念形成鲜明对比，隐密安全建议将算法保密可以提高安全性。事实上，使用一个专有的、自制的算法(即秘密设计的非标准化算法)是非常危险的。由于公开的设计要经过公开的同行评审，因此可能更强大。多年的经验表明，很难构建出好的加密方案。如果专家（水平在方案的设计者之上）进行了广泛的研究，并且没有发现缺陷，我们对方案安全性的信心会高得多。尽管听起来简单而明显，但开放密码设计原则（即Kerckhoffs原则）被一次又一次地忽视，带来了灾难性的后果。幸运地是，现在有几种安全的、标准化的、广泛可用的密码系统，没有理由使用其他任何密码系统。

1.3 历史密码及其密码分析

在我们对“经典”密码学的研究中，我们将研究一些历史加密方案，并表明它们是不安全的。我们展示这些材料的主要目的是(1)强调密码学启发式方法的弱点，从而引出将在书的其余部分中采取的现代、严格的方法，以及(2)证明实现安全加密的简单方法不太可能成功。在此过程中，我们将提出一些受这些历史方案的弱点启发的密码学的中心原则。

为清楚表示，明文用小写字母，密文用大写字母。

（1）Caeser’s cipher

​ 核心在于：移动字母表中的字母，向前移动3位。比如a被D取代。在最后进行环绕，也就是z被C取代，Y被b取代。比如，加密明文begin the attack now,移除空格，得到EHJLQWKHDWWDFNQRZ。这种方法的直接问题就是加密方法固定，没有密钥。因此，任何一个了解凯撒密码加密方法的人都能毫不费力地解密。

​ 有趣的是，这种密码的变体ROT-13（转换移位是13位而不是3位）现在仍然在各种在线论坛上使用。据了解，这并不提供任何密码安全；它仅仅是用来确保文本（例如，一个电影剧透）是不可理解的，除非一个信息的读者有意识地决定解密它。

（2）移位密码与充分密钥空间原则

​ 移位密码可以看作是凯撒密码的对密钥的变体。具体来说，在移位密码中，密钥k是一个介于0到25之间的数字。为了加密，字母会像凯撒密码一样移动，但现在移动了k个位置。将其映射到前面描述的加密语法，消息空间由任意长度的英文字母字符串组成，去掉了标点符号、空格和数字，并且没有区分大写字母和小写字母。算法Gen输出一个统一的密钥k∈{0，……，25}；算法Enc取一个密钥k和一个明文，并将明文中的每个字母向前移动k个位置；算法Dec取一个密钥k和一个密文，并将密文的每个字母反向移动k位置。

​ 一个数学描述是通过将英语字母表与集合{0，…，25}（a= 0，b = 1等）。消息空间M是这个集合中任意有限的整数序列。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-cJIoTs8Z-1669000637343)(C:\Users\tongtong\AppData\Roaming\Typora\typora-user-images\image-20221107134543218.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xLpZYF3I-1669000637343)(C:\Users\tongtong\AppData\Roaming\Typora\typora-user-images\image-20221107134632873.png)]

​ 这也是不安全的。因为可能的密钥只有26个，因此，人们可以尝试使用每个可能的密钥来解密密文，从而获得一个包含26个候选明文的列表。正确的明文肯定会在这个列表上；此外，如果密文“足够长”，那么正确的明文很可能是列表上唯一“有意义”的候选文本。通过扫描候选文本列表，可以很容易地恢复原始明文。（这不一定是正确的，但大多数时候都是真的。即使不是，这种攻击也将潜在明文缩小到最多26种可能性。）

​ 一种涉及尝试所有可能的密钥的攻击被称为暴力攻击brute-force或穷尽搜索攻击exhaustive-search。显然，对于一个安全的加密方案来说，它必须不容易受到这种攻击。这种结果被称为充分密钥空间原理：任何安全加密方案都必须有一个足够大的密钥空间，才能使穷举搜索攻击不可行。

人们争论什么程度的努力使一项任务“不可行”，而可行性的确定取决于潜在攻击者的资源和发送方和接收方希望确保其通信保密的时间长度。如今，攻击者可以使用超级计算机、数千台云服务器或图形处理单元（GPU）来加速暴力攻击。为了防止这类攻击，密钥空间必须非常大——比如说，至少2⁸⁰，在许多设置下甚至更大。

​ 充分密钥空间原理给出了安全性的必要条件，但不是充分条件。

（3）单字母替换密码

在移位密码中，密钥定义了从（明文）字母表中的某个字母到（密文）字母表中的某个字母的映射，其中映射是由密钥决定的固定移位。在单字母替换密码中，密钥也定义了字母表上的映射，但是现在允许映射是任意的，只要满足一对一的约束（因此解密是可能的）。因此，密钥空间由字母表中的所有双射或排列组成。这个密码的名称来自于这样一个事实，即该密钥为明文中的单个字符定义了一个（固定的）替换。

​ 假设使用英文字母，密钥空间大小是26！= 26·25·24···2·1，或约2⁸⁸，则蛮力攻击是不可行的。然而，这并不意味着密码是安全的！事实上，正如我们接下来将展示的，即使这个方案有很大的密钥空间，也很容易破解它。

​ 假设英语文本是被加密的（即，文本是语法上正确的英语书写，而不仅仅是使用英语字母表中的字符书写的文本）。利用英语语言的统计特性，可以攻击单字母替代密码。（当然，同样的想法也适用于任何一种语言。）：①对于任何密钥，每个字母的映射都是固定的，因此如果e映射到D，那么e在明文中的每一次出现都会导致D在密文中的出现。②英语文本中单个字母的频率分布是已知的。当然，非常短的文本可能会偏离这种分布，但即使是只有几个句子组成的文本，也往往会有非常接近它的分布。

​ 该攻击的工作原理是将密文中字符的频率分布制成表，然后将这些频率与普通英语文本的已知字母频率进行比较。然后，人们可以根据观察到的频率来猜测由该密钥定义的部分映射。有些猜测可能是错误的，但足够的猜测是正确的，以实现相对快速的解密（特别是利用其他英语知识，比如q通常跟着u，他可能出现在t和e之间）。我们的结论是，虽然单字母替换密码有一个很大的密钥空间，但它仍然是不安全的。单字母替代密码可以很快被打破，这并不奇怪，因为基于这个密码的谜题很常见。

解密得到：cryptographic systems are extremely difficult to build nevertheless for some reason many non experts insist on designing new encryption schemes that seem to them to be more secure than any other scheme on earth the unfortunate truth however is that such schemes are usually trivial to break

（4）对移位密码的改良攻击

我们可以使用字母-频率表来改进对移位密码的攻击。我们之前对移位密码的攻击需要使用每个可能的密钥解密密文，然后检查哪个密钥会产生“有意义”的明文。这种方法的一个缺点是，要实现自动化有点困难，因为计算机很难检查一个给定的明文是否“有意义”。(我们并不说这是不可能的，因为攻击可以使用有效的英语单词词典自动进行。）更重要的是，可能会有一些情况，即使明文本身不是有效的英语，但也遵循与英语文本相同的分布，在这种情况下，保证解密出来的明文合理已经毫无作用。

我们现在描述的是一种没有这些缺点的攻击。用 0-25 分别表示英文字母 a-z，p_i表示普通文本中第 i 个字母出现的频率，则可得到以下结论：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-F6GPb2W8-1669000637344)(C:\Users\tongtong\AppData\Roaming\Typora\typora-user-images\image-20221107152459507.png)]

现在，假设我们得到一些密文，让q_i表示字母表中第i个字母的频率；也就是说，q_i仅仅是字母表中第i个字母在密文中出现的次数除以密文的长度。如果密钥是k，那么p_i应该大致等于所有i的q_i+k，因为第i个字母映射到第（i+k）个字母。（我们使用i+k而不是更麻烦的[i+k mod26]）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vka3Dnyy-1669000637345)(C:\Users\tongtong\AppData\Roaming\Typora\typora-user-images\image-20221107153433351.png)]

因此如果我们对于j{0-25}的每个值进行计算,当得到的I_j和I_k ≈ 0.065最接近时便可认为j = k。这导致了一个很容易自动化的密钥恢复攻击：计算所有j的I_j，然后输出I_k最接近0.065的值k。

（5）维吉尼亚密码（多字母移位密码）

​ 可以对单字母替换密码进行统计攻击，因为密钥定义了一个固定的映射，并逐字母地应用到明文中。这种攻击可以通过使用多字母移位密码来阻止，其中密钥定义了一个应用于明文字符块的映射。明文字符不会被映射到一个固定的密文字符。多字母移位密码**“平滑”了密文中字符的频率分布**，使统计分析的进行更加困难。

​ 维吉尼亚密码是一种多字母移位密码，是上述的一种特殊情况，可以看作是将移位密码的不同实例应用到明文的不同部分。密钥现在被视为一串字母；加密是通过移动每个明文字符的下一个字符所指示的数量，必要时重复密钥。（如果密钥的长度为1，则会退化为移位密码。）密钥不需要是一个英文单词。一个明文被映射为不同的明文，一个密文可以由多个明文得到。因此，密文的字符频率被“平滑”。

​ 如果密钥足够长，破解这个密码似乎会令人生畏。事实上，许多人一直认为它是“牢不可破的”，尽管它是在16世纪发明的，但直到数百年后才对该计划进行了有系统的攻击。

（6）攻击维吉尼亚密码

​ 攻击维吉尼亚密码的第一个观察结果是，如果密钥的长度已知，那么攻击密码相对容易。具体来说，比如说密钥的长度，也称为period，是t。将密钥k写成k = k₁···k_t，其中每个k_i都是字母表中的一个字母。观察到的密文c = c₁c₂···可以被分为t部分，每个部分可以被视为已经使用移位加密了。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-OFdX6BCK-1669000637346)(C:\Users\tongtong\AppData\Roaming\Typora\typora-user-images\image-20221108094027218.png)]

所有这些是通过将明文的相应字符移动K_j位置得到的。我们将上述字符序列称为第j个流。

剩下的就是确定，对于每一个t流，26个可能的移位中的哪一个被使用。这并不像移位密码的情况那么简单，因为不再可能简单地尝试不同的移位，试图确定流的解密何时“有意义”。（回想一下，一个流并不对应于明文中的连续字母。）此外，试图一次猜测整个密钥k需要通过26^t不同的可能性进行穷尽搜索，这对于大数t是不可行的。然而，我们仍然可以使用字母频率分析来独立地分析每个流。也就是说，对于每个流，我们将每个密文字符的频率制成表格，然后检查26个可能的移位中哪一个产生了该流的“正确”概率分布。由于这可以对每个流独立执行（即对密钥中的每个字符），因此该攻击需要时间26·t，而不是时间26^t。

​ 一种更有原则、更容易自动化的方法是将改进后的攻击应用到移位密码（前面讨论过的）中的每个流。这种攻击并不依赖于检查一个“有意义”的明文，而是只依赖于明文中字符的潜在频率分布。

​ 当密钥长度已知时，上述任何一种方法都能成功地进行攻击。如果密钥长度未知怎么办？

​ 首先要注意，只要密钥的最大长度T不是太大，我们就可以简单地重复上述攻击T次（对于每个可能的值t∈{1，……，T}一次）。这导致最多有T个不同的候选明文，其中真正的明文可能很容易识别。所以一个未知的密钥长度并不是一个严重的障碍。

​ 还有一些更有效的方法可以从观察到的密文中确定密钥长度。一种是使用19世纪中期出版的卡西斯基的方法。这里的第一步是识别密文中长度为2或3的重复模式。这些可能是明文中经常出现的某些字母或字母组合的结果。例如，考虑一下常见的单词“the”。这个单词将被映射到不同的密文字符，这取决于它在明文中的位置。但是，如果它在相同的相对位置出现两次，那么它将被映射到相同的密文字符。因此，对于足够长的明文，很有可能“t”将重复映射到相同的密文字符。卡西斯基的观察是，这种重复出现（假设它们不是巧合）之间的距离是这个密钥长度的倍数。因此，重复序列之间距离的最大公约数（假设它们不是巧合）将产生密钥长度t或它们的倍数。

​ 另一种方法，称为符合指数方法，更有系统性，因此更容易自动化。回想一下，如果密钥长度为t，那么在第一个流中的密文字符c₁，c_1+t，c_1+2t，…，都是使用相同移位加密造成的。这意味着在这个序列中的字符的频率应该与标准英语文本的字符频率相同。更详细地说：让q_i表示在这条流中观察到的第i个字母的频率；这只是字母表中第i个字母出现的次数除以流中字母的总数。如果这里使用的移位是j (即,如果密钥的第一个字符k₁等于j)，那么对于所有的i，我们期望q_i+j ≈ p_i，其中p_i是字母表的第i个字母在标准英文文本中出现的频率。(再次,我们使用q_i+j代替q[i+jmod 26])。但这意味着序列q₀，……，q₂₅只是序列p₀，……，p₂₅移动了j个位置。因此，如方程式所示：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FUcgp8g5-1669000637347)(C:\Users\tongtong\AppData\Roaming\Typora\typora-user-images\image-20221108111143237.png)]

这就得到了一个确定密钥长度t的好方法。对于τ = 1，2，…，T，观察密文字符序列c₁，c_1+τ，c_1+2τ，…，并列出该序列的q₀，…，q₂₅。然后计算

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8sK89kJX-1669000637351)(C:\Users\tongtong\AppData\Roaming\Typora\typora-user-images\image-20221108111743431.png)]

​ 如上所述，当τ = t时，我们期望Sτ≈为0.065。另一方面，如果τ不是t的倍数，我们期望所有字符在序列c₁、c_1+τ、c_1+2τ、…，中出现的概率大致相等，因此我们期望所有i的q_i≈1/26。在这种情况下，我们得到[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tdJO8vAD-1669000637352)(C:\Users\tongtong\AppData\Roaming\Typora\typora-user-images\image-20221108112010170.png)]

​ 因此，Sτ≈0.065的最小值可能是密钥长度。我们可以通过使用第二个流c₂、c_2+τ、c_2+2τ、…，等进行类似的计算来进一步验证一个猜测的τ。

（7）密文长度和密码分析攻击

​ 上述对维吉尼亚密码的攻击需要比对以前方案的攻击更长的密文。例如，符合指数法要求c₁、c_1+t、c_1+2t（其中t为实际密钥长度）足够长，以确保观察到的频率接近预期的频率；那么密文本身必须大约大t倍。类似地，我们在单字母替换密码上显示的攻击比攻击移位密码（它甚至可以对单个单词进行加密）需要更长的密码文。这说明，一个较长的密钥通常需要密码分析人员获得更多的密文来进行攻击。(事实上，如果密钥和被加密的内容一样长，那么维吉尼亚密码就可以被证明是安全的。)

（8）结论

​ 我们只展示了少数的历史密码。除了他们的历史兴趣之外，我们展示他们的目的是说明一些重要的教训。也许最重要的是，**设计安全的密码是很困难的。**维吉尼亚密码有很长一段时间没有破解。还使用了更复杂的方案。但是一个复杂的方案不一定是安全的，所有的历史方案都被破解了。

1.4 现代密码学原理

​ 从前一节中可以清楚地看出，密码学在历史上更像是一门艺术，而不是一门科学。密码方案以启发式的方式设计，并根据其感知到的复杂性或聪明之处进行评估。分析一个方案，看看是否可以发现任何攻击；如果是，该方案将被“修补”以阻止攻击，这个过程将不断重复。虽然人们可能一致认为一些方案是不安全的（由一次特别具有破坏性的攻击证明），但对于“安全”方案应该满足什么要求没有一致的概念，也没有证据证明任何具体方案是安全的。在过去的几十年里，密码学已经发展成为一门科学。密码方案现在以一种更系统的方式开发和分析，最终目标是给出一个“给定的结构是安全的”严格证明。为了清楚地描述这样的证明，我们首先需要正式的定义来确定“安全”的确切含义；这样的定义本身是有用和有趣的。事实证明，大多数密码学证明都依赖于目前关于某些数学问题的算法困难性的未经证实的假设；任何这样的假设都必须明确和准确地说明。强调定义、假设和证明，将现代密码学与经典密码学区分开来；现在我们将更详细地讨论这三个原则。

1.4.1 原则1—正式定义

​ 现代密码学的关键贡献之一是认识到安全的正式定义对于正确地设计、研究、评估和使用密码原语至关重要。坦率地说：如果你不明白你想要实现什么，你怎么可能知道你是什么时候（或是否）实现了它呢？正式的定义通过明确描述范围内存在的威胁以及需要的安全保证来提供这种理解。因此，定义可以帮助指导加密方案的设计。实际上，最好是在设计过程开始之前形式化所需要的内容，而不是在设计完成后再事后提出一个定义。后一种方法的风险是当设计者的耐心耗尽(而不是当目标已经达到时)时，设计阶段就结束了，或者可能导致以牺牲效率为代价后一种方法面临着在耗尽设计者的耐心时（而不是在达到目标时）结束设计阶段的风险，或者可能以牺牲效率为代价导致实现的结构超过所需要的目标。

​ **定义也提供了一种评估和分析结构的方法。**有了定义，就可以研究一个给定方案，看看它是否达到了期望的保证；在某些情况下，甚至可以通过证明它符合定义来证明给定的构造是安全的。另一方面，定义可以用来确切证明一个给定的方案是不安全的，只要该方案不满足该定义。特别是，请注意，前一节中的攻击并不能明确证明所显示的任何方案都是“不安全的”。例如，对维吉尼亚密码的攻击是假设足够长的英文文本被加密，但如果短的英文文本或压缩文本（具有大致统一的字母频率）被加密，也许维吉尼亚密码是“安全的”呢？如果没有一个正式的定义，这一点很难说。

​ **定义使得能够对方案进行有意义的比较。**正如我们将看到的，可以有多种（有效的）方法来定义安全性；“正确的”一个取决于使用方案的背景。一个满足较弱定义的方案可能比另一个满足较强定义的方案更有效；有了精确的定义，我们就可以正确地评估这两种方案之间的权衡。同样地，定义也支持方案的安全使用。考虑决定对一些更大的应用程序使用哪个加密方案。解决这个问题的一个合理方法是，首先了解该应用程序需要什么安全要求，然后找到一个满足该要求的加密方案。这种方法的一个好处是模块化：设计者可以“换出”一种加密方案，并替换为另一种加密方案（也满足必要的安全定义），而不必担心影响整个应用程序的安全性。

​ 编写一个正式的定义迫使人们思考什么对手头的问题至关重要，什么属性是无关的。通过这个过程，往往会揭示出问题的微妙之处，但乍一看并不明显。接下来，我们将为加密的情况进行说明。

一个例子：安全加密

​ 一个常见的错误是：认为正式的定义是不需要的，或者是微不足道的，因为“每个人都对安全有一个直观的想法。”但事实并非如此。作为一个例子，我们考虑了加密的情况。虽然我们将安全加密的正式定义推迟到后续的章节，但我们在这里非正式地描述这样的定义应该包括什么。

​ 一般来说，安全定义有两个组成部分：安全保证（或者，从攻击者的角度来看，是什么构成了成功的攻击）和威胁模型。安全保证定义了防止攻击者的方案，而威胁模型描述了对手的力量，即假设攻击者能够执行什么行动。

我们先来看第一个。一个安全的加密方案应该保证什么呢？以下是一些想法：

**①攻击者应该无法恢复密钥。**我们之前观察到，如果攻击者可以使用某种方案确定双方共享的密钥，那么该方案就不是安全的。然而，很容易提出密钥恢复的方案，但该方案明显不安全。例如，考虑Enck ( m ) = m的方案。密文没有泄露关于密钥(因此,如果密钥足够长,则无法恢复)的任何信息，但消息是以明文发送的!因此，我们看到，无法恢复密钥是必要的，但不足以确保安全。这是有道理的：加密的目的是保护消息；密钥的保密是实现这一目标的一种手段，但它本身并不是目标。

**②攻击者不能从明文恢复密文。**这个定义更好，但仍然远不能令人满意。特别是，如果密文显示了90%的明文，只要10%的明文仍然难以识别，那么这个定义将认为加密方案是安全的。这在大多数常见的加密应用中显然是不可接受的；例如，当加密一个工资数据库时，如果90%的员工工资被泄露，我们将有理由感到不安！

**③攻击者应该不可能从密文中恢复明文的任何字符。**这看起来是一个很好的定义，但仍然不够。回到加密工资数据库的例子，如果一个加密方案显示了一个员工的工资是否高于或低于10万，即使它没有透露该员工工资的任何特定数字，我们就不会认为它是安全的。同样，我们不希望加密方案揭示一个特定员工是否比另一个多。

另一个问题是如何形式化敌手"恢复明文的一个字符"意味着什么。如果攻击者通过纯粹的运气或外部信息，正确地猜测出某人的薪水中最不重要的数字是0呢？显然，这不应该使加密方案不安全，因此任何可行的定义都必须以某种方式排除这种行为作为成功攻击。

**最终版：无论攻击者已经拥有的任何信息如何，密文都不应该泄露有关底层明文的其他信息。**这个非正式的定义包含了上面概述的所有问题。特别注意，它没有试图定义关于明文的哪些信息是“有意义的”；它只是要求不泄露任何信息。这一点很重要，因为这意味着安全加密方案适用于所有需要保密的潜在应用程序。这里缺少的是一个精确的数学定义公式。我们应该如何捕获攻击者对明文的先验知识？（不）泄露信息意味着什么？

​ 既然我们已经确定了一个安全目标，它仍然需要指定一个威胁模型。这指定了攻击者假设拥有的“权力”，但不对对手的策略进行任何限制。这是一个重要的区别：我们具体说明了我们对对手能力的假设，但我们没有对它如何使用这些能力的任何假设。我们不可能预见在攻击中可能使用什么策略，而历史已经证明，这样做的尝试注定要失败。

​ 在加密的背景中，威胁模型有几个合理的选项；为了增加攻击者的能力，标准的选项有：

​ **①唯密文攻击：**这是最基本的攻击，即对手只观察一个密文（或多个密文），并试图确定关于底层明文（或明文）的信息。这是我们在前一节中讨论经典加密方案时隐式假设的威胁模型。

**②已知明文攻击：**在这里，对手能够获得一个或多个使用某些密钥生成的明文/密文对。然后，对手的目的是推断出关于使用相同的密钥产生的一些其他密文的潜在明文的信息。我们所看到的所有经典加密方案，使用已知明文攻击都是常见的。

**③选择明文攻击：**如上所述，在这种攻击中，敌手可以获得其选择的明文的明文/密文对。

**④选择密文攻击：**最后一种攻击是攻击者还能够获得(有关的一些信息)对其选择的密文的解密，例如，攻击者选择的某些密文的解密是否产生有效的英文消息。再说一次，敌手的目标是学习关于使用相同密钥生成的一些其他密文（对手无法直接获得其解密）的底层明文的信息。

​ 尽管威胁模型是根据强度增加的顺序列出的，但没有一个天生比其他模型更好；正确的使用取决于部署加密方案的环境。

​ 前两种攻击类型是最容易进行的。在唯密文攻击中，对手唯一需要做的事情就是窃听发送加密消息的通信通道。在一个已知明文攻击中，假定对手也获得与已知明文相对应的密文。这通常很容易实现，因为不是所有加密的消息都是秘密的，至少不是无限期的。作为一个平常的例子，双方可能总是在他们开始通信时加密一个“你好”消息。作为一个更复杂的例子，加密可能被用来保密季度收益报告，直到其发布日期；在这种情况下，任何窃听密文的人以后都会获得相应的明文。

​ 在后两种攻击中，假定对手能够获得其所选择的明文/密文的加密和/或解密。这一开始看起来很奇怪，我们以后对这些攻击及其实用性进行更详细的讨论。

1.4.2 原则2—精确假设

​ 大多数现代密码学结构不能被无条件地证明是安全的；这样的证明将需要解决计算复杂性理论中的问题，而这些问题在今天似乎还远未得到回答。这种不幸的情况的结果是，安全的证明通常依赖于假设。现代密码学要求任何这样的假设都必须得到明确的和数学上的精确化。在最基本的层面上，这是因为安全证明需要这一点。但还有其他原因：

**1、假设的有效性：**就其本质而言，假设是指没有被证明，而是被推测为真实的陈述。为了加强我们对某些假设的信任，研究它是很重要的：这个假设被检验而不被反驳的次数越多，我们就越相信这个假设是正确的。此外，对一个假设的研究可以提供其有效性的证据，表明它是由其他一些被广泛认为的假设所暗示的。如果所依赖的假设没有被精确地陈述，它就不能被有效地研究和（潜在地）驳斥。因此，增加我们对假设的信心的先决条件是对假设有一个精确的陈述。

2、假设间的比较：通常在密码学中，我们会遇到两种方案，它们都可以被证明满足某些定义，每个方案都基于不同的假设。假设其他条件都相等，哪种方案更好？如果第一个方案所基于的假设比第二个方案所基于的假设(也就是说,如果第二个假设隐含第一个假设)更弱，那么第一个方案是可取的，因为如果第一个假设是真的，第二个假设就是假的。如果两种方案使用的假设没有可比性，那么一般规则是选择基于研究更多的假设的方案，该假设可能有更大的可信度。

**3、理解必要假设：**加密方案可能基于某些底层架构（逻辑块？）。如果后来在架构（逻辑块？）中发现了一些弱点，我们如何知道加密方案是否仍然安全？如果明确说明关于架构（逻辑块？）的基本假设是证明方案安全性的一部分，那么我们只需要检查所需的假设是否受到所发现的新弱点的影响。

​ 有时会出现的一个问题是：为什么不简单地假设方案本身是安全的，而不是基于其他一些假设来证明方案是安全的?在某些情况下——例如，当定义很简单，并且一个方案已经成功地抵抗了攻击多年时——这可能是一种可以接受的方法。但这种方法并不是首选，而且当引入一种新的结构时，它是很危险的。以上的原因有助于解释原因。首先，一个已经研究了几年的假设，比与一个新的结构一起引入的一个新的、任意的假设更可取。其次，一般倾向于"更简单"的假设- -即一个明确的数学问题的困难性假设与一个满足详细的安全定义的复杂方案的假设- -因为更简单的假设通常更容易理解和研究。依赖"低层次"假设(而不是仅仅假设一个方案是安全的)的另一个好处是，这些低层次的假设通常可以用于其他构式。最后，低层次假设使模块化成为可能。考虑一个加密方案，其安全性依赖于它的一个构建块的某些假定属性。如果底层构建块不满足所述的假设，则可以使用满足必要要求的不同组件来实例化加密方案。

1.4.3 原则3—安全性证明

​ 刚才描述的两个原则允许我们实现我们的目标，即提供严格的证明，证明一个结构在某些假设下满足给定的定义。这样的证明在密码学中尤其重要，因为有一个攻击者正在积极地试图“破坏”某种方案。根据定义和假设，可靠的安全证据可以保证攻击者不会成功；这比采取无原则或启发式的方法来解决问题要好得多。如果没有证据证明拥有指定资源的对手能够破坏某些方案，我们就只能凭直觉知道这就是情况。经验表明，在密码学和计算机安全方面的直觉是灾难性的。有无数个未经证实的方案被打破的例子，有时是立即出现的，有时是在开发了几年之后。

总结：对安全的严格的vs启发式的方法

​ 依赖于定义、假设和证明构成了一种严格的密码学方法，它不同于经典密码学的非正式方法。不幸的是，仍然有一些希望快速解决问题的人，或者无知的人设计和部署一些没有原则的“即兴”解决方案。我们希望这本书将有助于人们认识到严格的方法及其在发展可证明的安全方案方面的重要性。

1.4.4 可证明安全与现实安全

​ 现在，许多现代密码学都建立在健全的数学基础上。但这并不意味着这个领域也不再是部分的艺术。攻击部署的密码系统的艺术也将永远存在，即使它们被证明是安全的。接下来我们将扩展这一点。现代密码学所采取的方法已经彻底改变了这一领域，并有助于为在现实世界中部署的密码学方案的安全性提供信心。但重要的是不要夸大安全证明的含义。安全性的证明总是与正在考虑的定义和正在使用的假设有关。如果安全保证与需要的东西不匹配，或者威胁模型没有捕获对手的真正能力，那么证明可能是不相关的。同样地，如果所依赖的假设被证明是错误的，那么安全的证明就没有意义了。

​ 关键是，一个方案的可证明安全性并不一定意味着该方案在现实世界中的安全性。虽然有些人认为这是可证明的安全性的一个缺点，但我们乐观地认为这说明了这种方法的优势。为了攻击现实世界中可证明的安全方案，攻击者被迫将注意力集中在定义（即，探索理想化定义与现实世界需求的不同）或潜在假设（即，看看它们是否成立）。反过来，密码学家的工作是不断完善他们的定义以更接近现实世界，并调查他们的假设来测试它们的有效性。可提供的安全性并没有结束攻击者和防御者之间由来已久的战斗，但它确实提供了一个框架，帮助防御者获胜。
方案在现实世界中的安全性**。虽然有些人认为这是可证明的安全性的一个缺点，但我们乐观地认为这说明了这种方法的优势。为了攻击现实世界中可证明的安全方案，攻击者被迫将注意力集中在定义（即，探索理想化定义与现实世界需求的不同）或潜在假设（即，看看它们是否成立）。反过来，密码学家的工作是不断完善他们的定义以更接近现实世界，并调查他们的假设来测试它们的有效性。可提供的安全性并没有结束攻击者和防御者之间由来已久的战斗，但它确实提供了一个框架，帮助防御者获胜。