密码学是什么? (15 分钟)

语言：简体中文

在我们开始应用密码学之前，我想说说

什么是密码学，以及密码学应用的不同领域。

密码学的核心当然是安全的通信，它

由两部分组成。第一部分是安全密钥构造，第二是当我们

有了共享密钥后，如何进行安全通信。我们已经说过，

安全密钥构造方法是 Alice和Bob相互发送消息，

在协议结束时，他们能获得同一的

共享密钥 K。而除此之外，

Alice会知道她确实是在跟Bob说话，而Bob也确定和他对话的

是Alice。而攻击者就算可以窃听他们的会话，也不知道

共享密钥是什么。这些我将在以后的课程中详细介绍。当他们

拥有了共享密钥，他们就希望能通过密钥加密，从而安全通信

我们将谈论能使他们这样做的加密方法，

并且攻击者无法得知传输的消息。

此外，如果攻击者篡改了消息，那么一定会被发现。

换句话说，这些加密方案不仅仅提供了机密性，还有

完整性。但加密还有许许多多别的用处。

我来举几个例子吧。第一个例子，那就是

所谓的 数字签名。数字签名 是

是对现实世界签名的模拟。

在现实世界，当签名文档时，你把名字签在文档上就行了。

并且，你的签名几乎始终是相同的。也就是说，

你的签名有自己的特点。而在数字世界中，这不可能

奏效，因为只要攻击者获得一个由我签过名的文档，

他就可以剪切我的签名，并粘贴到另外一些可能我并不愿意

签名的文档上。所以在数字世界中，实际上我为不同文件

的签名也是不同的。因此，我们要谈谈

如何构建安全的数字签名，这是课程后半部分的内容。

构造数字签名会非常有趣。现在我只

给你们一个提示，数字签名的工作方式基本上是通过

基于内容的签署函数来实现的。那么就算攻击者

试图将我的签名从一个文档复制到另一个上，他也不会成功

因为该签名在新文档由于内容不同，

是无法通过验证的。正如我所说，

我们将在今后的某个时间学习构造数字签名，然后再

证明这样构造是安全的。密码学的

另一个应用是 匿名通信。试想，

Alice想与聊天服务器那边的Bob交谈。并且，也许她想说

诸如医疗状况这类隐私话题。她希望能匿名交谈，这样一来

服务器完全不知道她是谁。实现这个有一个标准方法，叫

mixnet，这将允许Alice一系列的代理最终与Bob交谈，

而在交谈结束后，Bob完全不清楚刚刚到底是在跟谁说话。

Mixnets 基本是这样工作的：Alice将消息发送

Bob时，消息通过了一系列代理服务器，这些消息通过适当的

加解密后，最后传给Bob时，不仅Bob不知道谁在跟他说话，

那些代理服务器甚至也不清楚Alice的通话对象是Bob，

或者说，谁都不知道对方是谁。有趣的是，匿名通信

的通道实际上是一个双向通道。换句话说，

虽然Bob不知道对方是谁，他仍然可以向对方做出回答，

而Alice也能获得这些消息。一旦我们有了匿名通信，就可以

构造其他隐私的机制了。另一个例子， 匿名数字现金

在现实世界中，如果我有实实在在的1美元，

我可以去书店，并买了一本书，而老板并不知道我是谁。

问题是我们是否可以在数字世界做同样的事情呢？

在数字世界里，假设Alice有虚拟的1美元硬币，

她想要在网上书店花掉这虚拟的1美元，

现在，我们想做同现实世界一样，那就是

当Alice用这1美元在网上书店买书时，书店也会知道她是谁。

这样，我们就提供了与现实中相同的匿名服务。

现在的问题是在数字世界里，Alice可以做一些邪恶的事情，

在她花掉这虚拟1美元之前，她可以做几份拷贝，

突然之间Alice就不止只有1美元了

她有了3个1美元硬币，并且它们是一模一样的。

没人能组织她做这样的拷贝，或者在其他网络商家

花掉这拷贝的钱。所以问题是我们如何提供匿名数字现金，

但同时，也防止Alice做刚刚我们说过的那些事？

在某种意义上，有一个悖论，那就是

匿名是与安全是冲突的。因为如果Alice有了匿名现金，

那么没人可以阻止她拷贝硬币了。而正因为

现金是匿名的，我们也没有办法找出谁做出了这种欺诈行为。

那我们如何解决呢？事实证明，完全是有办法的。

稍后我们会详述匿名数字现金。现在只是给个提示，

我们可以这么做：如果 Alice 花同一枚硬币仅仅一次，

那么没人知道她是谁；但如果她花同一个硬币超过一次，

那么突然之间，她的身份就被暴露了，然后估计就会被警察

请去公安局坐坐了。这就是匿名数字现金的工作方式。

我们将在后面的课程中尝试实现它。

另一个密码学应用是与一些抽象的协议结合的，

在我告诉你这是什么之前，先举两个例子。

第一个例子与选举系统有关。

我们有两个党，党0和党1。选民为他们心宜的党投票。

在这个例子中，选民可能支持党0，也可能支持党1。

就像这样...在这次选举中，党0得到了3票，而另一个当得到了

2票。所以，党0在此次选举中获胜。

因为一般说来得到大多数选票的党成为选举中的胜者。

现在，投票的问题如下：选民希望

知道哪个党得到了大部分选票，但与此同时并不会泄露

具体票数。那么应该怎么做呢？

为了达到这个目的，我们引进“选举中心”，它将帮助我们

计算票数，但不泄露其他信息。

参与竞选的党派将把票数通过加密送入竞选中心，

在竞选结束后，竞选中心

计算票数并宣布获胜方，而其他的所有

信息都不会泄露，也就是说单独的

票数仍然保密。选举中心当然也需要

对选民进行验证，例如选民是否有权投票，以及

是否只投了一次。但是除此之外，选举中心和

其他所有人或组织都只知道选举结果。

这是一种涉及六个对象的协议，

在这种情况下，有5个选民，1个选举中心。

他们将计算选票，而在计算结束时，

除了得知结果，其他的一切信息，诸如个人输入都未被泄露。

类似的问题也出现了私人拍卖会上。假设一个私人卖家

对自己想要的商品进行竞标。

拍卖机制使用的是“维克瑞拍卖”，即

出价最高者是这件商品竞标的获胜者，但

他只需要按第二高的出价支付。

这就是所谓的“维克瑞拍卖”。

现在我们想做的是，第一

要弄清楚出价最高者是谁，其次这个人要支付多少钱，

除此之外的其他个人竞标信息都要保密。

例如，出价最高的实际金额

应保密，唯独要公开的是第二高的出价金额，

以及出价最高的人的身份。所以在此，

我们引进“拍卖中心”，并以和选举例子类似的方法执行，即

每人将向拍卖中心发送加密的竞标书。拍卖中心将

计算的获胜者身份，以及第二高的出价，

但除了这两个值以外，其他信息仍然保密。

现在，举一个更普遍问题的例子，即

安全多方计算。那么安全多方计算到底是什么呢？

简单地说，参与者有一个秘密输入。

所以，在选举中，输入即为投票；

在拍卖会上，输入即为秘密的投标书。

参与者希望以某种函数，以他们的输入来计算结果。

在选举中，函数即为计算大多数票数，输出获胜者。

在拍卖中，该函数计算第二高的金额，以及最高者金额的编号

可他们该怎么做，才能只输出函数计算的值，

而其他信息维持保密呢？

一种比较呆板的、 不安全的方法是，我们引进一个

可信组织。然后，这个可信组织将收集所有的个人输入。

并且，它承诺对各个输入保密，也就只有它

知道那些具体输入情况。最后，它计算函数的值后公布结果。

这样一来，我们得到了结果，但

其他信息未被泄露。当然，你必须

要信任这个可信组织，如果你觉得它会搞名堂，

那就没用了。所以，密码学中有一个

让人很吃惊的中心理论：任何你想要

做的计算或者函数，如果你能把这个计算交给

可信组织做，那么你也一定可以不需要可信组织来得到结果。

让我在较高级别上解释这意味着什么。也就是说，我们做的

任何事情都可以不要可信组织插手。所以实际上参与者不需要

将输出提供给可信组织。并且，事实上，在系统中也没有

什么权威组织。那些参与者需要的仅仅只是使用某种协议与

其他参与者交换信息。而在结束后，

每个人都只知道最终结果是什么。

换句话说，

个体的输入仍然是保密的。但在此之中也没有可信权威组织

只是通过另一种方式来获得最终的输出。

这是一个普遍的结果，虽然有些难以置信，但却是可行的。

事实上，在课程快结束时，我们就会知道如何做啦！

还有一些我不能将它们归类的密码学应用，

但它们确实很神奇。

举两个例子。第一个称之为“私下外包计算”。

为了方便说明，就以谷歌搜索为例子吧。

假设Alice有一串搜索关键词想要查询，

并且有一些特殊的加密方案使得她可以将加密的查询

信息发送给谷歌。由于这种特殊加密方案的某个特性，

谷歌可以基于这些加过密的信息计算搜索，而无需知道

原始的文本是什么。也就是说，谷歌可以基于加密的信息，运

运行其大规模的搜索算法，并得到加密的结果。之后，谷歌将

发送加密的结果给Alice，Alice解密信息后得到查询的结果。

神奇的地方在于，谷歌只知道加过密的查询内容，

所以，谷歌也不知道什么Alice到底想要搜索什么，

以及Alice到底得到了什么结果。

这些就是神奇的加密方案。

它们是最近才发展的，大约从两年或三年前开始。

它使我们能够计算加密的数据，即使我们不知道

加密的内容是什么。现在，在你飘飘然之前想想如何实现。

虽然现在来说只是理论，

也许到那谷歌实现这个技术的那一天还要很久很久，

但尽管如此，这个方案可行的事实已经令人无比兴奋了，

并且，就一些相对简单的计算而言，它是非常有用的。

事实上，我们将在稍后看到一些这样的应用。另外一个神奇的

应用，是所谓的“零知识”。

我先说说“零知识证明”。

假设Alice知道一个确定的数N，

数字 N 是由两个大素数构造的。试想一下，

我们有两个素数 P 和 Q。它们很大很大，比如一千位。

我们知道两个1000位的数字想成很容易。

但如果我给你一个乘积的结果，让你把它分解为两个质数，

其实是相当困难的。事实上，我们要利用因数难分解的特点，

来构造公共密钥的密码系统，这个我们将在课程后半部分讲到

现在，Alice有此数字 N，并且她也知道的构成N的因子。

而Bob只知道数字N，他不知道构成N的因子是什么。

现在就是见证奇迹的时刻：根据“零知识证明”，

Alice可以向Bob证明她知道的 N 的因子，

Bob也可以做一些验证，证实Alice没有骗他，

最终，Bob却只知道N的值是什么，不知道因子P和Q的值。

这就是可证明的。Bob绝对不知道因子P和Q的值是什么。

实际上这个论证是很普遍的，一般的。

它不仅仅能证明N的因式分解，还能证明你所知道的任何难题

的答案都是你的知识。因此，如果

你解决了字谜拼图，好吧，我承认字谜这个例子不太好。

如果你解决了一个数独难题，你想证明你解决了它，

那么你可以证明给Bob看，虽然Bob不知道答案，

但却能坚信你确实知道这个数独难题的答案。

看看，密码学的这个应用神奇吧！

最后我想说，现代密码学是一个非常

严谨的科学。事实上，我们描述的每个概念都将

严格的按照三个步骤，我们将反反复复地遵循这三个步骤

所以我想要解释它们是什么。首先，

象介绍什么是数字签名那样，

我们先说说什么是威胁模型。数字签名中的威胁模型是攻击者

如何对数字签名发动攻击，以及攻击者为什么要伪造签名？

对于数字签名这个例子，我们一定要了解，签名必须是

无法伪造的。三个步骤是，

对于每一个基元，我们要描述需要

精确定义的威胁模型是什么。接着，提出一种方案。

再证明在特定威胁模型条件下，任何攻击者都能攻击这个方案

一旦攻击者成功了，那么攻击者也可以解决相对应的一些

根本的复杂的难题。如果难题够复杂攻击者无法破解，

那么也就证明了在这个威胁模型下没有攻击者能破解这个方案

以上的三个步骤实际上相当重要。就签名这个例子而言，

我们要定义数字签名意味着什么，那就是不可伪造性。

接着给出一个方案，并指出任何一个可以破解我们的方案

的人都能解决因子整数分解，而因子整数分解被普遍认为

是一个很难的问题。在今后，我们将遵循这三个步骤，

就能得到证明的结果了。这些就是本节的内容。

在下一节，我们将谈谈 密码学的历史。

End