什么是随机Oracle模型，您为什么要关心它？

这是关于随机甲骨文模型的一系列帖子中的第一篇。*对于一些人的品味来说，这可能会有点不稳定，所以如果你对可证明的安全不感兴趣，没问题。“一旦我把这件事从我的系统中拿出来，我会带回更多关于软件和物理安全的信息。

碰巧今天我计划讲授一门关于可证明安全和“随机Oracle模型”的课程。“在整理我的想法时，我突然想到，a)这门课可能会让不是我研究生的人感兴趣，b)似乎没有一个很好的”门外汉“介绍它。在很大程度上，我喜欢谈论密码学是如何实现的。但是，如果您从不安全的原语开始，实现并不重要。

因此，冒着疏远我小小的读者的风险，我将从我们定期安排的“密码系统如何变坏”节目中抽出时间来谈谈这个书呆子的话题-正如我们稍后将看到的，这本身就是密码如何出错的另一种味道。

在讨论随机预言之前，我们首先需要讨论散列函数。这些函数接受(潜在的)长输入，并将其‘散列’成一个固定大小的值，我们称之为消息摘要。

我们在密码学中经常使用哈希函数。虽然他们因出现在数字签名方案中而受到最多的关注，但他们也出现在许多加密方案中。事实上，在整个球场上，扔一块石头而不击中一块是相当困难的。

在很大程度上，密码学散列函数必须至少满足以下属性中的一部分。首先，我们预计它是“单向的”，也就是说很难“反转”函数，也就是说，如果只给出一个消息摘要，就很难找到原来的消息。

其次，散列函数应该是“抗冲突的”。换句话说，应该很难找到两个不同的消息(M，M‘)，使得Hash(M)==Hash(M’)。此属性对于数字签名非常重要，因为我们通常不直接对消息进行签名，因此我们会对消息进行哈希签名。*如果对手可以找到两条散列为相同值的消息，那么一条消息上的签名(散列)也是另一条消息上的签名。但在实践中，这可能会导致更糟糕的社会后果。

有时，我们对散列函数的要求甚至更高。但棘手的部分是知道我们可以再要求多少。为了说明这一点，让我举一个例子。

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

这不是疯了。许多散列算法的输出看起来相当随机。也许你可以使用散列函数来构建流密码。基本上，你只需要使用散列函数来散列一个密钥(以及某种计数器值)；这将产生一串“随机寻找”的比特流，然后你可以用你的明文进行异或运算。

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

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

假设我们想要实现一个理想的散列函数。我们可能会创建一个大的硬编码表，而不是设计一个使用混淆和扩散的小算法(就像我们对大多数真正的散列函数所做的那样)。该表将输入消息放在一栏中，相应的输出放在另一栏中。

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

输入(二进制)位串：输入(二进制)位串；输出位串；输出位串；完全随机位串；完全随机位串；0位完全随机位串；1位完全随机位串；2位完全随机位串；00位完全随机位串；3位完全随机位串；01位完全随机位串；4位完全随机位串；10位完全随机位串；5位完全随机位串；11位完全随机位串；6位随机位串；以此类推……。

显然，一个有用的散列函数的整个表会相当大。多大?。嗯，SHA1可以接受最大长度为2^64字节的消息。所以答案是：太大了，放不进这个博客。事实上，整个表格中的条目会比宇宙中的原子还多。

即使我们有空间存储这样的表，散列过程-查找输入并找到输出-也会非常耗时。*如果我们将哈希表存储在图灵机(五分计算机)的磁带上，仅将磁头移动到正确的位置就会(平均)花费大量的时间步长，这是输入大小的指数倍。

时不时地，当我在入门课程中提到所有这些时，一些雄心勃勃的学生试图想出一个聪明的方法，把桌子缩小到我们可以随身携带的东西。但问题是：这组输出字符串并不是完全随机的。找到一种用紧凑散列表示它们的方法等同于压缩随机数据。“不幸的是，信息论告诉我们，这是一个很大的禁忌。

让我们盘点一下。到目前为止，我希望我至少说服了你两件事。首先，密码学家确实希望他们的散列函数的行为类似于随机函数。

其次，“真正的”散列函数不能是随机函数，因为这是完全不可行和不切实际的。*如果你看看像SHA1、SHA512和RIPEMD160这样的实用散列函数-所有这些函数都有很好的、由几KB代码组成的简短实现-应该很明显，这些都不是随机函数，无论输出看起来有多“随机”。

那么，如果我们在实践中不能使用随机函数，那么另一种方法呢？也许我们可以将我们的散列函数建模为随机函数，只是为了安全证明的目的。然后在现实生活中，我们会用SHA或RIPEMD或一些实用的散列函数代替。*目前还不完全清楚安全证明是否仍然意味着什么，但至少我们会做一些事情。

我将描述一个好莱坞将呈现的场景：麻省理工学院一间光线明亮的不切实际的办公室。史蒂夫·布塞米(Steve Buscemi)扮演的一位著名密码学家刚刚提出将哈希函数建模为随机函数。他的同事，由凯特·温斯莱特扮演，纠正了他的错误。

“我做不到，”她伤心地摇摇头解释道，“计算一个随机函数需要指数级的时间，这不仅仅是不方便。“如果我们在安全证明中允许这种散列，我们将不得不让各方-包括对手-运行指数级的时间步长。但我们不能只这样做。我们的整个安全证明都是基于这样一种想法，即当事人只能进行有限的计算，特别是那些可以在多项式时间内进行的计算。“如果让双方进行任意的指数时间计算，那么对手可以做任何事情：他甚至可以暴力破解密钥。”

突破来自一位路过的看门人(马特·达蒙，重新扮演他在“善意猎杀”中的角色)：“如果你只是创造一个虚构的世界，每个人都被限制在多项式时间计算，但哈希有一个特殊的例外。散列，单独散列，根本不需要任何时间。“当你试图散列一些东西时，时钟就会停止。”

这就是我们现在的处境。那么完美的散列函数应该是随机函数。但是随机函数是不切实际的-我们不能在现实生活中使用它们，甚至在我们的安全证明中都不能不打破它们。

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

这个白日梦的影响结果是既美好又可怕。一方面，它让我们可以证明那些无法用其他方式证明的计划的安全性。此外，我们可以非常有效地做这件事。另一方面，它导致的安全证据在技术意义上是完全没有意义的。

毕竟，我们最终将不得不使用像SHA这样的真正的散列函数来实施该方案，这肯定不是随机的。那么随机的甲骨文安全证明能给我们带来什么呢？这是自这个想法产生以来一直困扰着密码学家的大问题之一。

如果你认为这一切都是学术性的，那你就大错特错了。*一些最广泛使用的密码原语的安全证明设置在此模型中：这包括大多数RSA签名和加密，以及DSA所基于的ElGamal签名方案。

如果你没有从这篇文章中拿走其他东西，你应该注意到上面列出的计划很重要。如果我们在安全证明中做了一些有趣的事情，人们应该理解这是什么。

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