你必须知道的密码学理论：随机预言模型（一）

这是随机预言模型系列文章中的第一篇。 对于某些人来说，这可能有点不靠谱，所以如果你对可证明安全不感兴趣，没问题。 一旦我把它从我的博客中删除，我会发布更多关于软件和物理安全的内容。

碰巧我今天计划教一门关于可证明安全的课程，还有一门叫做“随机预言模型（Random Oracle Model）”的课程。 在整理我的想法的时候，我突然想到: a)这个主题可能会引起那些不是我的研究生的人的兴趣; b)对于这个知识点似乎还没有一个好的给“外行人”学习的介绍文章。 在大多数情况下，我喜欢谈论加密是如何实现的。 但是，如果你从不安全的原语开始，那么实现就无关紧要了。

因此，冒着疏远我那些微不足道的读者群的风险，我打算暂停一下我们定期安排的“密码系统是如何变坏的”编程内容，来谈谈这个学究般的话题——正如我们稍后会看到的，这本身就是密码如何变坏的另一种味道。

傻瓜式哈希函数

在我们讨论随机预言之前，我们首先需要讨论哈希函数。 这些函数接受(可能)长的输入，并将输入经“哈希”处理得到固定大小的值，我们称之为“消息摘要”。

我们在密码学中经常使用哈希函数。 在数字签名方案中，它们的出现受到了极大的关注，但也出现在许多加密方案中。 事实上，在整个球场上，扔一块石头而没有接触到它则是很难的事情。

在大多数情况下，密码哈希函数必须至少满足以下一些属性。 首先，我们希望它是“单向的” ，这意味着很难“颠倒”函数，也就是说，只给出一个消息摘要就可以找到原始消息。

其次，哈希函数应该是“防碰撞”的。 换句话说，应该很难找到两个不同的消息(M，M’) ，也就是Hash(M) == Hash(M’)。 此属性对于数字签名非常重要，因为我们通常不直接对消息签名，而是对消息的哈希进行签名。 如果攻击者能够找到两个哈希值相同的消息，那么一个消息上的签名(哈希)也就是另一个消息上的签名。 实际上，这可能会导致不好的后果。

有时候我们对哈希函数的要求甚至更高。 棘手的部分是知道我们还能要求多少。 为了说明这一点，让我先举一个例子。

Delphia 中的加密技术

想象一下你生活在 Delphia，一个禁止所有加密算法的国家。 尽管如此，你还是有秘密要保守。 你注意到你的政府并没有禁止哈希函数。 这给了你一个想法: 也许你可以从哈希函数中‘黑掉’一个加密方案。

这并不疯狂。 许多哈希算法的输出看起来非常随机。 也许你可以使用哈希函数来构建流密码。 基本上，你将使用一个哈希函数来哈希一个秘密密钥(以及某种计数器值) ; 这将产生一个“随机查找”的字节流，然后你可以使用明文进行 XOR。

问题是: “单向”和“防碰撞”哈希函数是否足以确保该方案是安全的？ 我给你一个直截了当的提示: 否。 从技术上讲，这两个属性都不意味着哈希函数的输出是“随机查找”的。 你可以设想满足这些保证的哈希函数，但是产生的输出对于构建流密码毫无用处(比如，它们可能包含由可预测值组成的长字符串)。 如果你使用这些来构建密码，那么你将非常失望。

球形马

当密码学家第一次开始思考类似上面的问题时，他们的问题是他们想从“理想”哈希函数中得到什么。 对于一位数学家来说，答案显而易见。 他们希望它表现得像一个随机函数。 这个术语有一个非常具体的数学定义; 为了这次讨论的目的，我们将使用一个更容易讨论的等价术语。

假设我们想要实现一个理想的哈希函数。 与其设计一个使用混淆与扩散的小算法(就像我们对大多数真正的哈希函数所做的那样) ，我们还不如创建一个大的硬编码表。 该表的某一列中包含输入消息，另一列中包含相应的输出。

关于这个表，重要的是每个输出值都是一个独立的随机字符串。

       Input (binary)                  Output                      
       0                               Totally random bitstring 1
       1                               Totally random bitstring 2
       00                              Totally random bitstring 3
       01                              Totally random bitstring 4
       10                              Totally random bitstring 5
       11                              Totally random bitstring 6
       ...

显然，一个有用的哈希函数的完整表非常的大。 有多大呢？ 好吧， SHA1 最多可以接受长度为2 ^ 64字节的消息。 所以答案是: 太大了，这篇博文都放不下。 事实上，整个表格中的条目比宇宙中原子的数量还要多。

即使我们有足够的空间存储这样一个表，查找输入并找到输出的哈希过程也会非常耗时。 如果我们将哈希表存储在图灵机的磁带上(quintisdential 计算机) ，那么仅仅将磁带头移动到正确的位置(平均而言)就需要一系列的时间步骤，这些步骤与输入的大小呈指数级增长。

当我在我的入门课程中提到这些的时候，一些雄心勃勃的学生试图想出一个聪明的方法，把桌子缩小成我们可以随身携带的东西。 但问题是: 输出字符串的集合是完全随机的。 找到一种在紧凑哈希中表示它们的方法就相当于压缩随机数据。 不幸的是，信息理论告诉我们，这是一大禁忌。

双倍下注

让我们来盘点一下。 到目前为止，我希望我至少说服了你两件事。 首先，密码学家希望他们的哈希函数表现得像随机函数。

其次，“真正的”哈希函数不可能是随机函数，因为那是完全不可行和不切实际的。 如果你看看 SHA1、 SHA512和 RIPEMD160等实用的哈希函数——所有这些函数都有漂亮的、简短的实现，由几个 KB 的代码组成——很明显，不管输出看起来多么’随机’ ，它们都不是随机函数。

马萨诸塞州，剑桥，上午10:35

那么，如果我们在实践中不能使用随机函数，那么有没有另一种方法呢？ 也许我们可以将哈希函数建模为随机函数，仅仅为了安全证明的目的。 然后在现实生活中，我们可以用 SHA 或 RIPEMD 或者一些实用的哈希函数来代替。 现在还不能完全确定安全证明是否还有意义，但至少我们可以做点什么。

我将描述好莱坞所呈现的一个场景: 麻省理工学院一间灯光不切实际的办公室。 由 Steve Buscemi 扮演的著名密码学家，刚刚提出将哈希函数建模为随机函数。 他的同事，由凯特 · 温斯莱特扮演，直截了当地告诉了他：

“我做不到，”她解释道，并且悲伤地摇了摇着头，“评估一个随机函数不仅仅是不方便的，还要花上指数级的时间进行计算。 如果我们允许在我们的安全证明中使用这种哈希方法，那么我们将不得不让各方(包括对手)以指数级的时间步长运行。 但我们不能这么做。 我们的整个安全证明是基于这样的想法，即各方只能执行有限的计算，特别是那些可以在多项式时间进行的计算。 如果让各方以指数级的方式进行任意的计算，那么对手可以做任何事情: 他甚至可以暴力破解密钥。”

(好莱坞可能会加强这个对话。)

这个突破来自一个路过的看门人(马特 · 达蒙，重演了他在《心灵捕手》中的角色) : “如果你只是创造一个虚构的世界，其中每个人都被限制在多项式时间的计算上，但哈希方法有一个特殊的例外。 仅仅使用哈希表，根本不需要花费任何时间。 当你试图解决问题的时候，时钟就停止了。”

一个范式

这就是我们现在的处境。 完美哈希是一个随机函数。 但是，随机函数是不切实际的——我们不能在现实生活中使用它们，甚至不能在我们的安全证明中使用它们而不破坏它们。

密码学家是很顽固的人，我们有很好的想象力。 因此，我们想出了一个白日梦，一种假装随机函数是实用的方法——只是为了证明我们的安全性。

这个白日梦的含义既美妙又可怕。 一方面，它允许我们证明那些不能用其他方法证明的方案的安全性。 此外，我们可以非常有效地做到这一点。 另一方面，它导致的安全证明，在技术意义上，是完全没有意义的。

毕竟，我们最终将不得不用一个真正的哈希函数来实现这个方案，比如 SHA，它决不是随机的。 那么一个随机预言安全证明能给我们带来什么呢？ 这是自从这个想法产生以来困扰密码学家的一个大问题。

如果你认为这完全是学术性的，那你就错了。 该模型给出了一些应用最广泛的密码原语的安全证明: 包括大多数 RSA 签名和加密，以及 DSA 所基于的 Elgamal 签名方案。

如果你没有从这篇文章中得到任何其他的东西，你应该注意到上面列出的计划是非常重要的事情。 如果我们在做一些有趣的安全证明，人们应该明白它是什么。

在我的下一篇文章中，我将解释什么是“随机预言” ，以及它是如何与我们上面做出的疯狂假设相联系的。 我还将解释我们如何在这个模型中证明事物，并讨论为什么密码学家如此热衷于讨厌它。

关于本系列的下一篇文章，请点击这里。