Chapter 5 

Combinatorics, Probability, and Information Theory

  考虑到密码系统的有用性和实用性，有必要测量其对各种形式攻击的抵抗力。此类攻击包括通过密钥或消息空间进行简单的暴力搜索，通过碰撞或中间相遇算法进行更快的搜索，以及用于计算离散对数、因子整数和在格中查找短向量的更复杂的方法。我们已经在第2章和第3章中研究了其中一些算法。我们将在本章和后面的章节中看到其他内容。在研究这些算法时，能够分析解决目标问题所需的时间非常重要。这种分析通常需要组合学、概率论和信息论的工具。在本章中，我们以一种基本独立的形式介绍了这些主题。

  我们从计数的基本原理开始，然后学习概率论基础。后续章节介绍（离散）随机变量、概率密度函数、条件概率和贝叶斯公式。概率论在密码学中的应用有很多。我们将详细介绍蒙特卡罗算法和碰撞算法及其在加密技术中的应用。我们还包括一节关于历史上有趣的多表置换密码（称为Vigenere密码）的统计密码分析（在 5.2 一节），但本书其他地方并没有使用 Vigenare 密码的材料，所以希望更快阅读到现代密码材料的读者可以直接略过。

  本章最后简要介绍了复杂度的概念以及多项式时间和不确定多项式时间算法的概念。这一部分如果讲的全面细致些就可以另写一本书了，因此我们只能对这一主题中使用的强大思想和技术给出一点提示。

5.1 计数的基本原理

As I was going to St. Ives,
I met a man with seven wives,
Each wife had seven sacks,
Each sack had seven cats.
Each cat had seven kits.
Kits, cats, sacks, and wives,
How many were going to St. Ives?

  这个古老谜语的答案是，只有一个人去 St. Ives，即叙述者，因为他在诗歌中遇到的所有其他人、动物和物体都不是去圣艾夫斯，而是从 St. Ives 出发。然而，如果我们比较死脑筋，我们可能会问一个问题：叙述者会遇到多少人、动物和物体？答案是 

  这个数字的计算采用了基本的计数原则，是密码学和许多其他数学领域中使用的概率计算的基础。我们已经在 1.1.1 一节中看到了一个例子，其中我们计算了不同简单替换密码的数量。

  如果通过检查每个可能的密钥来破坏密码系统是不可行的话，则我们称密码是组合安全的。这在一定程度上取决于检查每个钥匙所需的时间，但更重要的是，这取决于钥匙的数量。在本节中，我们将介绍一些基本的计数技术，这些技术以多种方式用于分析密码构造的安全性。

例 5.1 （一个基础的计数原则） Bob 在一家餐厅就餐，餐厅有两道开胃菜：蛋卷和炸馄饨，以及二十道主菜。假设他计划点一份开胃菜和一道主菜，那么 Bob 有多少种方案可以选择？

  我们需要记录不同数对  的数量，其中，  为蛋卷或者扎混沌， 则代表一道主菜。通过让  在2种可能性上变化， 在20种可能性上改变，然后对总对数进行计数。

  答案是有 40 种可能性。

  在这个例子中，我们首先计算了将开胃菜（蛋卷或炸馄饨）分配给变量  的方法的数量。我们也可以将此分配视为实验的结果。也就是说，我们进行了一个实验，其结果是“蛋卷”或“炸馄饨”，我们将结果的值指定给 。同样，我们进行第二个独立实验，其可能的结果是20道主菜中的任何一道，我们将该值指定给 。两个实验的结果总数是每个实验的结果数的乘积。这导致以下基本计数原则

如果独立进行两个实验，其中一个有n个可能的结果，另一个有m个可能的结论，那么进行这两个实验就有nm个可能性的结果。

  更一般地说，如果进行了  个独立实验，并且第 个实验的可能结果数为 ，那么所有实验的结果总数就是乘积 。通过为第  个实验的结果写 ，那么所有  个实验的结果是可以表示为  元组，可能的  元组总数是乘积 。

例 5.2 假设 Bob 也想吃甜点，而菜单上有五种甜点。我们现在计算三元组，其中  是两种开胃菜之一， 是20种主菜之一， 是五种甜点之一。因此，总可能数为 

基本计数原理也可以用于解决 St.Ives 问题的 “死脑筋” 版本。例如，遇见的猫的数量为：

5.1.1 排列

  数字  通常按递增顺序列出，但假设我们允许扰乱顺序。那么列出这十个整数有多少种不同的方法呢？每一种可能都被称为  的排列。在数学中，计算给定对象列表的可能排列数的问题以多种形式和背景出现。

   的每个排列都是按一定顺序排列的所有十个不同整数的序列。例如，这里有一个随机选择：。我们列出所有的可能性？列出它们最简单的方法是一次列出一个数字，比如从左到右。于是，我们首先为第一个位置指定一个数字。有十种选择。接下来，我们给第二个位置分配一个数字，但对于第二个位置，只有九个选择，因为我们已经用完了第一个位置的一个整数。（请记住，我们不允许两次使用一个整数。）然后，第三个位置可能还有八个整数，因为我们已经在前两个位置使用了两个整数。因此， 的置换总数为

  注意我们是如何使用基本计数原理的。唯一微妙之处是，第一个实验的结果减少了第二个实验可能的结果数量，前两个实验的结论进一步减少了第三个实验可能结果的数量，依此类推。（也就是这里每一次实验并不相互独立）

定义 设  是一个包含  个不同对象的集合。 的排列是  中对象的有序列表。集合 的排列简单地称为  的排列。

命题 5.3 设  是一个包含  个不同对象的集合，则  种有  种不同的排列。

证明：是我们前面对  排列讨论的推广。因此，假设  包含  个对象，并且我们要列出  的排列。第一个位置有  个选项，然后第二个位置有 个选项，然后第三个位置有 个选项，等等。因此总共会有 个可能的排列。

注 5.4 （排列和简单替换密码）根据定义，集合  的一个排列是其元素按照某个顺序组成的列表。我们也可以用下面的说双射函数去定义

函数  决定了排列为

现在假设我们有一个集合 ，排列  其实就是简单替换密码的别称，其中 就是加密函数。因此根据 ，字母  映射为  字母， 映射为  字母，以此类推。而对于解密，我们则需要逆函数 。

例 5.5 当某些对象不同，然后我们需要计算其排列的个数。比如，对于  来说，有六种排列

  但如果有两个对象是等价的，比如 ，那么就只有三种不同的排列

  为了在更复杂的情况下说明这个想法，我们计算了五个字母  排列的数量。如果这五个字母是可区分的，比如它们被标记为，那么就会有  个排列。然而，如果诸如  和  ，如果不考虑下标，其就是一样的。因此我们计算的  就太多了。那么有多少排列被重复计算了呢？例如，在任何特定的排列中，两个  都被放置到特定的位置，但我们总是可以切换它们，得到相同的列表。这意味着我们需要  以除去关于  的重复计算。同理，一旦三个  被放置到特定的位置，我们就可以将它们排列，共  种排列，所以我们需要除  以除去 关于 的重复计算。因此，对于  来说，共有  种不同的排列。

5.1.2 组合

  排列是将一组对象排列到列表中的一种方式。组合类似，只是现在列表的顺序不再重要。我们从一个涉及组合的典型问题开始：五个人（Alice、Bob、Carl、Dave和Eve）正在一家中国餐馆点餐。菜单包含20个不同的菜。每个人都可以选择一道菜，任何菜都不能点两次。那么总共有多少种不同的点菜方案？

  爱丽丝先点菜，她有20种选择。然后 Bob 从剩下的19道菜中点菜，然后 Carl 从剩下的18道菜中选择，以此类推。这样看来，可能有 道菜。然而，菜的顺序并不重要。如果爱丽丝点的是炒饭，鲍勃点的是蛋卷，或者爱丽丝要的是蛋卷，而鲍勃点的是炒饭，则最后的餐并没有什么区别。

  我们给菜做上标记 ，然后，比如，两个可能的选择

  是一样的，尽管点菜的顺序不同。为了去除过度计数，请注意，在计算时，任何一组五道菜的每一个排列都是单独计算的，但我们确实希望将这些排列计算为提供同一顿饭。因此，我们应该将  除以 五种不同菜肴排列方法的数量，即，我们应该除以 。因此，不同菜肴的总数为

  我们可以通过将分子和分母乘以，完全用阶乘重写这个值

定义 设  有  个不同的对象，那么  的  个对象的组合是由  的  个不同元素组成的子集，其中对象在子集中的顺序无关紧要。

命题 5.7 从一组  个对象中选择的  个对象的组合数等于

注 5.8 符合  称为组合符号或二项式系数。读作 “n choose r”，注意，按照惯例，零阶乘被设置为等于1，所以 ，这是有意义的，即从集合里取 0 个对象只有一种方法。

命题 5.7 的证明：如果您理解 例 5.6 中的讨论，那么证明起来是简单的。从集合  中生成  个不同元素的有序列表的方法的数量是

  因为第一个元素有  个选择，那么第二个元素有 个选择，以此类推，直到我们选择了  个元素。然后我们需要除以  以去除在我们的子集中排列  个元素的方式。除以  说明我们不关心  个元素的选择顺序。因此，组合的总数为

例 5.9 回到在中餐厅点餐的五个人，假设他们想要点两道素食菜和三道肉类菜，假设菜单上有5种素食选择和15种肉类菜。现在他们多少种点餐方案？有 种，两种素食菜的可能性，还有  种肉类菜的选择。因此，根据我们的基本计数原则，总共有

种点餐方案。

5.1.3 二项式定理

  你可能已经看到了二项式定理中出现的组合数，它给出了两个数之和的  次方的公式。

定理 5.10 （二项式定理）

  证明：我们从一个特例开始，设 ，

  多项式的结果会是  项的和。这里只有一个  项，因为我们必须在 5.2 式种的每一项取出一个  来。那么有多少个  呢？我们可以从两项取一个 ，在最后一项取 。或者我们可以在第一个和第三个项取 ，在第二项取 。因此，获取 ，我们需要在 5.2 式种三项的两项取 ，然后剩下的一项取 。那么总共有  个方法取出 。同样的，总共有  种方法取出 ；只有一种方法取出 。因此

  对于一般情况也是这样，把  次方展开为乘积

  则为项  的和。我们可以从 5.3 式中的  项取  ，从剩下的  取  就可以得到很多 ，具体就是  个。把所有  的可能求和我们就得到了式 5.1，即完成了二项式定理的证明。

例 5.11 使用二项式定理计算