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

本系列文章的译文：

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

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

在我开始写这一系列文章时，我希望能够写出一篇能真正让外行人了解随机预言（ Random Oracle）模型的系列文章。 我在前面那几篇不太专业的文章中把这个问题已经解决了。 然而，现在我已经在三号位了，还有一大堆技术问题需要解决。

在接下来的本系列文章中，我们将讨论一些可靠、实用的密码学问题。

快速回顾一下

在前两篇文章中，我们已经讨论了一些内容。 我们讨论了加密哈希函数及其性质，并讨论了为什么密码学家的“理想”哈希函数是一个随机函数。 我们注意到，随机函数在现实生活中永远不会起作用(存储太大，计算太慢) ，因此我们得出了一个奇怪的结论: 我们假装我们的哈希是随机函数，只是为了安全分析的目的。 然后当然我们会使用真正的哈希函数，比如 SHA。

当然，即使是这样，我们也需要改变宇宙的结构，因为我们想要限制我们的“对手”在合理的时间内运行，而如果他们忙于评估随机函数，他们就无法做到这一点。因此，我们创造了一种新的计算模型(又名“思想实验”) ，称为随机预言模型。 在这个模型中，所有的哈希都是由一个叫做预言的神奇的第三方计算出来的。

如果你对随机预言模型有一点了解，比如说在阅读前面的文章时，你可以原谅自己认为它并没有那么糟糕。 基本上，我们假设哈希函数是超级“随机”函数。 可能比一个真正的函数要多一点，但是很重要。

但不幸的是，远不止这些。

这可能是世界上最短的可证明的安全课程

为了解释我的意思，我们首先需要了解一点可证明的安全性，特别是一种叫做约简证明的证明。

当我们说一个加密方案是“可证明的安全”时，我们通常指的是在某种假设下它是安全的。 对于大多数实际的方案来说，这个假设本质上是数学性质的。 例如，我们可以假设很难分解大的复合数，或者很难在格中找到最短的向量，从而找到一个加密方案。 在这种情况下，“难搞”并不意味着“我不知道该怎么做”。它的意思是: 没有(有效的)算法可以做到这一点。1

现在，我提到这些都是假设。 我们并不完全知道这些问题是困难的。 然而，我们倾向于认为，如果一些聪明的人已经注意到这个问题有一段时间了，但是没有人在解决这个问题上取得任何进展，那就意味着这可能并不容易。 在某些情况下，问题甚至可能属于一类有用的问题，例如，它可能是一个 NP-Hard 问题（译者注：NP-hard 请参见百度百科的解释）。

即使你不愿盲目相信这些假设，安全性证据仍然是有用的。 分析一个新的密码系统可以消耗大量的时间和精力。 如果我们至少可以将每个新方案“简化”为少数几个数学问题中的一个，我们就可以倾注我们的脑力来解决这些问题，因为我们知道我们的工作将适用于每个使用这些问题的方案。

所有这些带出了我的主要观点，即，这些证明是如何工作的。 具体来说，这种证明的一般流程如下:

1. 假设问题 X 很难。1

2. 证明如果存在一个(有效的)算法来“破坏”我们的加密方案，那么就存在一个(有效的)算法来解决问题X。

3. 含蓄地指出(2)意味着如果方案可以被打破，那么问题X就不会很难。

如果第(1)点为真，那么第(3)点显然不可能为真。 根据这个逻辑，我们可以得出这样的结论: 如果问题 X 很难，那么就不可能有算法破解我们的加密方案。

当然，我还没有解释如何实际完成步骤(2) ，这是非常重要的。 这也是最美妙的部分。 你看，在大多数简化中，步骤(2)实际上包括编写一个解决问题 X 的有效算法。

你可能觉得我疯了。 我刚刚声称 X 问题不能有效地解决，现在我又告诉你们，我们写了一个算法可以解决这个问题。 但它的天才之处在于，我们的求解算法不能很好地工作。 它缺少一个重要的子程序。

这个子例程在 API 级别上与“破解”我们的加密方案的算法是一样的。

因此，这就是争论的症结所在:假设有一种算法有效地“破坏”了我们的加密方案，那么我们可以把它塞进我们的“求解器”算法留下的洞里。这将产生一个有效地解决 X 问题的算法，因此，它完全满足我们在点(2)中所要求的。

黑匣子

有了这个基础，我只需要再说一点。 有一个基本的简化证明必须遵守的限制。 我们的“问题 X 解决程序”算法必须使用“加密方案破坏程序”的子程序作为一个黑盒。它无法对破坏程序算法的内部工作方式做出假设。

让我更清楚地说明这一点。例如，我们不能在“求解器”算法中对破坏程序算法进行反编译，或者窥视它的内部内存寄存器，然后假定它们将包含我们需要的部分结果。

这是因为我们的简化只有当它与打破方案的每一个可能的算法一起工作时才有效。 因为我们不能预先猜测这样的算法在内部是如何工作的，我们不能依赖于它的内部工作。 破解加密程序的算法会被可怕地混淆，以至于我们无法理解它，即使我们把代码握在手中。

因此，在传统的黑盒简化中，我们可以指望破坏程序算法有一个标准的“ API”(我们将在某个时候进行定义)。 它通常接受公钥和密文(或签名等) ，并输出一些有用的信息，这些信息构成了我们对“破坏”的定义。 尽管它并不总是需要成功，但我们希望它能够以合理的概率成功。 但是算法中发生的所有事情都必须对我们隐瞒。

脏衣服的故事

你不会认为这和可证明的安全性有任何关系。

让我们暂停一下，来考虑一下名人新闻领域的一些相关问题。

想象一下，你是一个揭发丑闻的名人记者，被指派去挖掘布拉德 · 皮特和安吉丽娜 · 朱莉最近收养的孩子的独家新闻。 皮特和乔利夫妇非常注重隐私，他们甚至不愿意承认自己正在领养孩子。 你是个聪明的记者，更重要的是，你没有道德。

你知道，如果你能看一眼家里的洗衣房，你就能知道整个故事了。 性别，大小，体重，最喜欢的颜色。 甚至饮食(安吉丽娜坚持使用环保的布尿布)。 在一个完美的世界里，你可以开车去皮特 / 朱莉的洗衣公司，塞给某人500美元，你的整个故事就会写在衣服上。 如果你真的很狡猾，你可以开始自己的名人洗衣服务，骗他们直接寄给你。

但这都是一厢情愿的想法。 皮特和朱莉不会把要洗的衣服送出去——他们在家里洗衣服。 事实上，你甚至不确定他们是否会洗衣服。 你听说过安吉丽娜每次用完衣服都要烧掉的传言。

如果你看不出它的相关性，可以琢磨一下这个类似于简化证明的例子。对你来说，“破解程序”算法是一个黑匣子。你可以看到输入进去，也可以看到输出，但你却看不到它在这两者之间做了什么。如果你的降价取决于看它的脏衣服，你最好拿出一个更好的削减。它自己洗衣服。

回到随机预言模型

随机预言模型是不同的。 在我之前的文章中，我解释说这就像现实世界一样，只有一个例外: 没有人能够自己计算哈希。 每一方——包括敌方(“破解程序”算法的同义词)——都必须通过向特定的外部方发送消息来进行哈希。 该方使用随机函数计算哈希，并将其发送回调用方。

为了使这一点非常清楚，在 Random Oracle 模型中，每个人都要送洗的衣服。

在随机预言模型中，预言为包括敌方在内的所有各方计算哈希。

如果我们建立一个简化，则意味着我们可以利用从这些调用中泄露的额外信息，就像我们的八卦记者可以利用名人的洗衣房。 我们知道算法必须进行这些哈希调用，因此必须在 API 中存在一个“端口”来进行这些调用。 一旦我们制定了这个规定，我们的简化就可以进入这个端口，拦截敌方的哈希调用，查看它要求的消息，甚至可能篡改它返回的结果。更正式地说，在随机预言模型中，对手(也就是我们的“破解程序”算法)不再完全是一个黑盒子。 在一个非常重要的方面，我们可以看到它。 如果它想要进行哈希操作，它就必须在自身之外进行调用。

在一个极端的情况下，我们的简化甚至可以运行自己的假“预言”(又名洗衣服务) ，只要我们始终回复令人信服的答复。

虽然这看起来没什么大不了的，但实际上却很重要。 就像布拉德·皮特和安吉丽娜·朱莉的丑闻可以揭示明星们私生活的主要细节一样，“破解程序”算法选择哪些信息来哈希可以揭示明星们内心想法的主要细节。 通过篡改这些响应，我们也可以从根本上改变它的操作。 这些细节可以区分证明的还原是有效的还是无效的。

评估

在这一点上，我认为值得深呼吸一下，问问我们自己到底陷入了什么境地。 当我们开始做这些无意义的事情时，我们想要的只是一个更好的哈希函数。 这个函数看起来比我们构造的任何实际函数都要随机一些。

在这个过程中，我们意识到随机函数是完全不切实际的。 甚至为了假装我们可以使用它们，我们不得不篡改我们的计算模型，把随机函数放到各个参与方之外。 毕竟，它们是在多项式时间内运行的，不可能求出这样的函数。

这些步骤似乎都是完全合理的，然而我们在某个地方遇到了麻烦。 我们违背了最神圣的还原主义安全原则。 我们现在不再说“我们的论点对任何对手都有效” ，而是说“我们的论点只对那些善意地告诉我们任何他们需要解决的问题的对手有效”。

真正的对手不是这样的。 如果有人想出一个算法来破坏真正使用了哈希函数(比如 SHA256)的 RSA-OAEP 实现，那么该算法不需要告诉我们它是什么哈希算法。 它只是在内部做这件事。 如果它的代码是模糊的，我们甚至不能连接到我们的简化，如果我们的简化依赖于知道(或篡改)哈希调用。