0:00:00.000,0:00:02.951
在我们开始应用密码学之前，我想说说

0:00:02.951,0:00:06.487
什么是密码学，以及密码学应用的不同领域。

0:00:06.487,0:00:10.487
密码学的核心当然是安全的通信，它

0:00:10.487,0:00:14.539
由两部分组成。第一部分是安全密钥构造，第二是当我们

0:00:14.539,0:00:18.697
有了共享密钥后，如何进行安全通信。我们已经说过，

0:00:18.697,0:00:22.854
安全密钥构造方法是 Alice和Bob相互发送消息，

0:00:22.854,0:00:26.906
在协议结束时，他们能获得同一的

0:00:26.906,0:00:30.906
共享密钥 K。而除此之外，

0:00:30.906,0:00:35.274
Alice会知道她确实是在跟Bob说话，而Bob也确定和他对话的

0:00:35.274,0:00:39.964
是Alice。而攻击者就算可以窃听他们的会话，也不知道

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

0:00:44.011,0:00:47.657
拥有了共享密钥，他们就希望能通过密钥加密，从而安全通信

0:00:47.657,0:00:51.698
我们将谈论能使他们这样做的加密方法，

0:00:51.698,0:00:55.491
并且攻击者无法得知传输的消息。

0:00:55.491,0:00:59.630
此外，如果攻击者篡改了消息，那么一定会被发现。

0:00:59.630,0:01:03.227
换句话说，这些加密方案不仅仅提供了机密性，还有

0:01:03.227,0:01:06.774
完整性。但加密还有许许多多别的用处。

0:01:06.774,0:01:10.519
我来举几个例子吧。第一个例子，那就是

0:01:10.519,0:01:14.468
所谓的 数字签名。数字签名 是

0:01:14.468,0:01:18.892
是对现实世界签名的模拟。

0:01:18.892,0:01:23.372
在现实世界，当签名文档时，你把名字签在文档上就行了。

0:01:23.372,0:01:27.740
并且，你的签名几乎始终是相同的。也就是说，

0:01:27.740,0:01:32.164
你的签名有自己的特点。而在数字世界中，这不可能

0:01:32.164,0:01:36.812
奏效，因为只要攻击者获得一个由我签过名的文档，

0:01:36.812,0:01:41.180
他就可以剪切我的签名，并粘贴到另外一些可能我并不愿意

0:01:41.180,0:01:45.247
签名的文档上。所以在数字世界中，实际上我为不同文件

0:01:45.247,0:01:49.590
的签名也是不同的。因此，我们要谈谈

0:01:49.590,0:01:53.830
如何构建安全的数字签名，这是课程后半部分的内容。

0:01:53.830,0:01:58.123
构造数字签名会非常有趣。现在我只

0:01:58.123,0:02:02.098
给你们一个提示，数字签名的工作方式基本上是通过

0:02:02.098,0:02:06.232
基于内容的签署函数来实现的。那么就算攻击者

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

0:02:10.313,0:02:14.541
因为该签名在新文档由于内容不同，

0:02:14.541,0:02:18.526
是无法通过验证的。正如我所说，

0:02:18.526,0:02:22.608
我们将在今后的某个时间学习构造数字签名，然后再

0:02:22.608,0:02:27.193
证明这样构造是安全的。密码学的

0:02:27.193,0:02:31.096
另一个应用是 匿名通信。试想，

0:02:31.096,0:02:35.828
Alice想与聊天服务器那边的Bob交谈。并且，也许她想说

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

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

0:02:45.113,0:02:49.946
mixnet，这将允许Alice一系列的代理最终与Bob交谈，

0:02:49.946,0:02:54.856
而在交谈结束后，Bob完全不清楚刚刚到底是在跟谁说话。

0:02:54.856,0:02:59.537
Mixnets 基本是这样工作的：Alice将消息发送

0:02:59.537,0:03:03.818
Bob时，消息通过了一系列代理服务器，这些消息通过适当的

0:03:03.818,0:03:08.271
加解密后，最后传给Bob时，不仅Bob不知道谁在跟他说话，

0:03:08.271,0:03:12.724
那些代理服务器甚至也不清楚Alice的通话对象是Bob，

0:03:12.724,0:03:16.750
或者说，谁都不知道对方是谁。有趣的是，匿名通信

0:03:16.750,0:03:20.498
的通道实际上是一个双向通道。换句话说，

0:03:20.498,0:03:24.743
虽然Bob不知道对方是谁，他仍然可以向对方做出回答，

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

0:03:29.153,0:03:33.784
构造其他隐私的机制了。另一个例子， 匿名数字现金

0:03:33.784,0:03:37.643
在现实世界中，如果我有实实在在的1美元，

0:03:37.643,0:03:42.108
我可以去书店，并买了一本书，而老板并不知道我是谁。

0:03:42.108,0:03:46.876
问题是我们是否可以在数字世界做同样的事情呢？

0:03:46.876,0:03:50.963
在数字世界里，假设Alice有虚拟的1美元硬币，

0:03:50.963,0:03:55.984
她想要在网上书店花掉这虚拟的1美元，

0:03:55.984,0:04:00.760
现在，我们想做同现实世界一样，那就是

0:04:00.760,0:04:05.539
当Alice用这1美元在网上书店买书时，书店也会知道她是谁。

0:04:05.539,0:04:10.629
这样，我们就提供了与现实中相同的匿名服务。

0:04:10.629,0:04:15.470
现在的问题是在数字世界里，Alice可以做一些邪恶的事情，

0:04:15.470,0:04:20.250
在她花掉这虚拟1美元之前，她可以做几份拷贝，

0:04:20.250,0:04:24.086
突然之间Alice就不止只有1美元了

0:04:24.093,0:04:27.936
她有了3个1美元硬币，并且它们是一模一样的。

0:04:27.936,0:04:31.828
没人能组织她做这样的拷贝，或者在其他网络商家

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

0:04:35.819,0:04:39.849
但同时，也防止Alice做刚刚我们说过的那些事？

0:04:39.849,0:04:43.760
在某种意义上，有一个悖论，那就是

0:04:43.760,0:04:47.879
匿名是与安全是冲突的。因为如果Alice有了匿名现金，

0:04:47.879,0:04:51.999
那么没人可以阻止她拷贝硬币了。而正因为

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

0:04:56.244,0:05:00.394
那我们如何解决呢？事实证明，完全是有办法的。

0:05:00.394,0:05:04.757
稍后我们会详述匿名数字现金。现在只是给个提示，

0:05:04.757,0:05:09.173
我们可以这么做：如果 Alice 花同一枚硬币仅仅一次，

0:05:09.173,0:05:13.764
那么没人知道她是谁；但如果她花同一个硬币超过一次，

0:05:13.764,0:05:17.878
那么突然之间，她的身份就被暴露了，然后估计就会被警察

0:05:17.878,0:05:22.096
请去公安局坐坐了。这就是匿名数字现金的工作方式。

0:05:22.096,0:05:26.158
我们将在后面的课程中尝试实现它。

0:05:26.158,0:05:30.219
另一个密码学应用是与一些抽象的协议结合的，

0:05:30.219,0:05:34.333
在我告诉你这是什么之前，先举两个例子。

0:05:34.333,0:05:38.343
第一个例子与选举系统有关。

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

0:05:42.656,0:05:47.101
在这个例子中，选民可能支持党0，也可能支持党1。

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

0:05:52.313,0:05:56.590
2票。所以，党0在此次选举中获胜。

0:05:56.590,0:06:01.579
因为一般说来得到大多数选票的党成为选举中的胜者。

0:06:01.579,0:06:06.453
现在，投票的问题如下：选民希望

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

0:06:11.720,0:06:16.797
具体票数。那么应该怎么做呢？

0:06:16.797,0:06:21.493
为了达到这个目的，我们引进“选举中心”，它将帮助我们

0:06:21.493,0:06:26.633
计算票数，但不泄露其他信息。

0:06:26.633,0:06:32.027
参与竞选的党派将把票数通过加密送入竞选中心，

0:06:32.027,0:06:36.949
在竞选结束后，竞选中心

0:06:36.949,0:06:41.615
计算票数并宣布获胜方，而其他的所有

0:06:41.615,0:06:46.580
信息都不会泄露，也就是说单独的

0:06:46.580,0:06:51.366
票数仍然保密。选举中心当然也需要

0:06:51.366,0:06:56.331
对选民进行验证，例如选民是否有权投票，以及

0:06:56.331,0:07:00.818
是否只投了一次。但是除此之外，选举中心和

0:07:00.818,0:07:05.484
其他所有人或组织都只知道选举结果。

0:07:05.484,0:07:10.104
这是一种涉及六个对象的协议，

0:07:10.104,0:07:14.430
在这种情况下，有5个选民，1个选举中心。

0:07:14.430,0:07:19.417
他们将计算选票，而在计算结束时，

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

0:07:24.404,0:07:29.156
类似的问题也出现了私人拍卖会上。假设一个私人卖家

0:07:29.156,0:07:34.160
对自己想要的商品进行竞标。

0:07:34.160,0:07:39.356
拍卖机制使用的是“维克瑞拍卖”，即

0:07:39.356,0:07:45.287
出价最高者是这件商品竞标的获胜者，但

0:07:45.287,0:07:50.099
他只需要按第二高的出价支付。

0:07:50.099,0:07:54.850
这就是所谓的“维克瑞拍卖”。

0:07:54.850,0:08:00.028
现在我们想做的是，第一

0:08:00.028,0:08:04.779
要弄清楚出价最高者是谁，其次这个人要支付多少钱，

0:08:04.779,0:08:09.165
除此之外的其他个人竞标信息都要保密。

0:08:09.165,0:08:14.160
例如，出价最高的实际金额

0:08:14.160,0:08:19.225
应保密，唯独要公开的是第二高的出价金额，

0:08:19.225,0:08:23.526
以及出价最高的人的身份。所以在此，

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

0:08:28.172,0:08:32.588
每人将向拍卖中心发送加密的竞标书。拍卖中心将

0:08:32.588,0:08:37.119
计算的获胜者身份，以及第二高的出价，

0:08:37.119,0:08:41.822
但除了这两个值以外，其他信息仍然保密。

0:08:41.822,0:08:46.126
现在，举一个更普遍问题的例子，即

0:08:46.126,0:08:50.264
安全多方计算。那么安全多方计算到底是什么呢？

0:08:50.264,0:08:54.618
简单地说，参与者有一个秘密输入。

0:08:54.618,0:08:58.649
所以，在选举中，输入即为投票；

0:08:58.649,0:09:02.787
在拍卖会上，输入即为秘密的投标书。

0:09:02.787,0:09:06.959
参与者希望以某种函数，以他们的输入来计算结果。

0:09:06.959,0:09:10.840
在选举中，函数即为计算大多数票数，输出获胜者。

0:09:10.840,0:09:15.088
在拍卖中，该函数计算第二高的金额，以及最高者金额的编号

0:09:15.088,0:09:19.179
可他们该怎么做，才能只输出函数计算的值，

0:09:19.179,0:09:23.375
而其他信息维持保密呢？

0:09:23.375,0:09:27.675
一种比较呆板的、 不安全的方法是，我们引进一个

0:09:27.675,0:09:31.774
可信组织。然后，这个可信组织将收集所有的个人输入。

0:09:31.774,0:09:36.223
并且，它承诺对各个输入保密，也就只有它

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

0:09:40.510,0:09:44.742
这样一来，我们得到了结果，但

0:09:44.742,0:09:48.812
其他信息未被泄露。当然，你必须

0:09:48.812,0:09:52.990
要信任这个可信组织，如果你觉得它会搞名堂，

0:09:52.990,0:09:57.168
那就没用了。所以，密码学中有一个

0:09:57.168,0:10:01.001
让人很吃惊的中心理论：任何你想要

0:10:01.001,0:10:05.204
做的计算或者函数，如果你能把这个计算交给

0:10:05.204,0:10:09.302
可信组织做，那么你也一定可以不需要可信组织来得到结果。

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

0:10:13.559,0:10:17.816
任何事情都可以不要可信组织插手。所以实际上参与者不需要

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

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

0:10:26.011,0:10:30.567
其他参与者交换信息。而在结束后，

0:10:30.567,0:10:34.890
每个人都只知道最终结果是什么。

0:10:34.890,0:10:39.390
换句话说，

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

0:10:43.639,0:10:47.867
只是通过另一种方式来获得最终的输出。

0:10:47.867,0:10:51.846
这是一个普遍的结果，虽然有些难以置信，但却是可行的。

0:10:51.846,0:10:56.024
事实上，在课程快结束时，我们就会知道如何做啦！

0:10:56.024,0:11:00.577
还有一些我不能将它们归类的密码学应用，

0:11:00.577,0:11:05.560
但它们确实很神奇。

0:11:05.560,0:11:10.240
举两个例子。第一个称之为“私下外包计算”。

0:11:10.240,0:11:15.224
为了方便说明，就以谷歌搜索为例子吧。

0:11:15.224,0:11:20.329
假设Alice有一串搜索关键词想要查询，

0:11:20.329,0:11:25.434
并且有一些特殊的加密方案使得她可以将加密的查询

0:11:25.434,0:11:30.368
信息发送给谷歌。由于这种特殊加密方案的某个特性，

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

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

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

0:11:44.903,0:11:49.242
发送加密的结果给Alice，Alice解密信息后得到查询的结果。

0:11:49.242,0:11:53.689
神奇的地方在于，谷歌只知道加过密的查询内容，

0:11:53.689,0:11:57.493
所以，谷歌也不知道什么Alice到底想要搜索什么，

0:11:57.493,0:12:01.672
以及Alice到底得到了什么结果。

0:12:01.672,0:12:05.812
这些就是神奇的加密方案。

0:12:05.812,0:12:09.985
它们是最近才发展的，大约从两年或三年前开始。

0:12:09.985,0:12:14.436
它使我们能够计算加密的数据，即使我们不知道

0:12:14.436,0:12:18.667
加密的内容是什么。现在，在你飘飘然之前想想如何实现。

0:12:18.667,0:12:22.470
虽然现在来说只是理论，

0:12:22.470,0:12:26.422
也许到那谷歌实现这个技术的那一天还要很久很久，

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

0:12:30.521,0:12:34.473
并且，就一些相对简单的计算而言，它是非常有用的。

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

0:12:38.671,0:12:42.474
应用，是所谓的“零知识”。

0:12:42.474,0:12:46.080
我先说说“零知识证明”。

0:12:46.080,0:12:50.177
假设Alice知道一个确定的数N，

0:12:50.177,0:12:54.169
数字 N 是由两个大素数构造的。试想一下，

0:12:54.169,0:12:58.835
我们有两个素数 P 和 Q。它们很大很大，比如一千位。

0:12:58.835,0:13:03.892
我们知道两个1000位的数字想成很容易。

0:13:03.892,0:13:08.235
但如果我给你一个乘积的结果，让你把它分解为两个质数，

0:13:08.235,0:13:12.427
其实是相当困难的。事实上，我们要利用因数难分解的特点，

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

0:13:16.566,0:13:20.968
现在，Alice有此数字 N，并且她也知道的构成N的因子。

0:13:20.968,0:13:24.898
而Bob只知道数字N，他不知道构成N的因子是什么。

0:13:24.898,0:13:28.723
现在就是见证奇迹的时刻：根据“零知识证明”，

0:13:28.723,0:13:33.144
Alice可以向Bob证明她知道的 N 的因子，

0:13:33.144,0:13:37.457
Bob也可以做一些验证，证实Alice没有骗他，

0:13:37.457,0:13:42.386
最终，Bob却只知道N的值是什么，不知道因子P和Q的值。

0:13:42.386,0:13:47.034
这就是可证明的。Bob绝对不知道因子P和Q的值是什么。

0:13:47.034,0:13:50.997
实际上这个论证是很普遍的，一般的。

0:13:50.997,0:13:55.275
它不仅仅能证明N的因式分解，还能证明你所知道的任何难题

0:13:55.275,0:13:59.606
的答案都是你的知识。因此，如果

0:13:59.606,0:14:03.831
你解决了字谜拼图，好吧，我承认字谜这个例子不太好。

0:14:03.831,0:14:07.845
如果你解决了一个数独难题，你想证明你解决了它，

0:14:07.845,0:14:12.282
那么你可以证明给Bob看，虽然Bob不知道答案，

0:14:12.282,0:14:16.718
但却能坚信你确实知道这个数独难题的答案。

0:14:16.718,0:14:20.930
看看，密码学的这个应用神奇吧！

0:14:20.930,0:14:25.000
最后我想说，现代密码学是一个非常

0:14:25.000,0:14:29.015
严谨的科学。事实上，我们描述的每个概念都将

0:14:29.015,0:14:33.129
严格的按照三个步骤，我们将反反复复地遵循这三个步骤

0:14:33.129,0:14:37.338
所以我想要解释它们是什么。首先，

0:14:37.338,0:14:41.493
象介绍什么是数字签名那样，

0:14:41.493,0:14:45.540
我们先说说什么是威胁模型。数字签名中的威胁模型是攻击者

0:14:45.540,0:14:49.534
如何对数字签名发动攻击，以及攻击者为什么要伪造签名？

0:14:49.534,0:14:53.851
对于数字签名这个例子，我们一定要了解，签名必须是

0:14:53.851,0:14:57.760
无法伪造的。三个步骤是，

0:14:57.760,0:15:01.998
对于每一个基元，我们要描述需要

0:15:01.998,0:15:06.464
精确定义的威胁模型是什么。接着，提出一种方案。

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

0:15:10.931,0:15:15.955
一旦攻击者成功了，那么攻击者也可以解决相对应的一些

0:15:15.955,0:15:20.150
根本的复杂的难题。如果难题够复杂攻击者无法破解，

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

0:15:24.350,0:15:27.843
以上的三个步骤实际上相当重要。就签名这个例子而言，

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

0:15:31.928,0:15:35.914
接着给出一个方案，并指出任何一个可以破解我们的方案

0:15:35.914,0:15:39.801
的人都能解决因子整数分解，而因子整数分解被普遍认为

0:15:39.801,0:15:43.541
是一个很难的问题。在今后，我们将遵循这三个步骤，

0:15:43.541,0:15:47.331
就能得到证明的结果了。这些就是本节的内容。

0:15:47.331,0:15:51.218
在下一节，我们将谈谈 密码学的历史。

0:15:51.218,0:15:52.006
End