1
00:00:00,000 --> 00:00:02,951
在我们开始应用密码学之前，我想说说

2
00:00:02,951 --> 00:00:06,487
什么是密码学，以及密码学应用的不同领域。

3
00:00:06,487 --> 00:00:10,487
密码学的核心当然是安全的通信，它

4
00:00:10,487 --> 00:00:14,539
由两部分组成。第一部分是安全密钥构造，第二是当我们

5
00:00:14,539 --> 00:00:18,697
有了共享密钥后，如何进行安全通信。我们已经说过，

6
00:00:18,697 --> 00:00:22,854
安全密钥构造方法是 Alice和Bob相互发送消息，

7
00:00:22,854 --> 00:00:26,906
在协议结束时，他们能获得同一的

8
00:00:26,906 --> 00:00:30,906
共享密钥 K。而除此之外，

9
00:00:30,906 --> 00:00:35,274
Alice会知道她确实是在跟Bob说话，而Bob也确定和他对话的

10
00:00:35,274 --> 00:00:39,964
是Alice。而攻击者就算可以窃听他们的会话，也不知道

11
00:00:39,964 --> 00:00:44,011
共享密钥是什么。这些我将在以后的课程中详细介绍。当他们

12
00:00:44,011 --> 00:00:47,657
拥有了共享密钥，他们就希望能通过密钥加密，从而安全通信

13
00:00:47,657 --> 00:00:51,698
我们将谈论能使他们这样做的加密方法，

14
00:00:51,698 --> 00:00:55,491
并且攻击者无法得知传输的消息。

15
00:00:55,491 --> 00:00:59,630
此外，如果攻击者篡改了消息，那么一定会被发现。

16
00:00:59,630 --> 00:01:03,227
换句话说，这些加密方案不仅仅提供了机密性，还有

17
00:01:03,227 --> 00:01:06,774
完整性。但加密还有许许多多别的用处。

18
00:01:06,774 --> 00:01:10,519
我来举几个例子吧。第一个例子，那就是

19
00:01:10,519 --> 00:01:14,468
所谓的 数字签名。数字签名 是

20
00:01:14,468 --> 00:01:18,892
是对现实世界签名的模拟。

21
00:01:18,892 --> 00:01:23,372
在现实世界，当签名文档时，你把名字签在文档上就行了。

22
00:01:23,372 --> 00:01:27,740
并且，你的签名几乎始终是相同的。也就是说，

23
00:01:27,740 --> 00:01:32,164
你的签名有自己的特点。而在数字世界中，这不可能

24
00:01:32,164 --> 00:01:36,812
奏效，因为只要攻击者获得一个由我签过名的文档，

25
00:01:36,812 --> 00:01:41,180
他就可以剪切我的签名，并粘贴到另外一些可能我并不愿意

26
00:01:41,180 --> 00:01:45,247
签名的文档上。所以在数字世界中，实际上我为不同文件

27
00:01:45,247 --> 00:01:49,590
的签名也是不同的。因此，我们要谈谈

28
00:01:49,590 --> 00:01:53,830
如何构建安全的数字签名，这是课程后半部分的内容。

29
00:01:53,830 --> 00:01:58,123
构造数字签名会非常有趣。现在我只

30
00:01:58,123 --> 00:02:02,098
给你们一个提示，数字签名的工作方式基本上是通过

31
00:02:02,098 --> 00:02:06,232
基于内容的签署函数来实现的。那么就算攻击者

32
00:02:06,232 --> 00:02:10,313
试图将我的签名从一个文档复制到另一个上，他也不会成功

33
00:02:10,313 --> 00:02:14,541
因为该签名在新文档由于内容不同，

34
00:02:14,541 --> 00:02:18,526
是无法通过验证的。正如我所说，

35
00:02:18,526 --> 00:02:22,608
我们将在今后的某个时间学习构造数字签名，然后再

36
00:02:22,608 --> 00:02:27,193
证明这样构造是安全的。密码学的

37
00:02:27,193 --> 00:02:31,096
另一个应用是 匿名通信。试想，

38
00:02:31,096 --> 00:02:35,828
Alice想与聊天服务器那边的Bob交谈。并且，也许她想说

39
00:02:35,828 --> 00:02:40,382
诸如医疗状况这类隐私话题。她希望能匿名交谈，这样一来

40
00:02:40,382 --> 00:02:45,113
服务器完全不知道她是谁。实现这个有一个标准方法，叫

41
00:02:45,113 --> 00:02:49,946
mixnet，这将允许Alice一系列的代理最终与Bob交谈，

42
00:02:49,946 --> 00:02:54,856
而在交谈结束后，Bob完全不清楚刚刚到底是在跟谁说话。

43
00:02:54,856 --> 00:02:59,537
Mixnets 基本是这样工作的：Alice将消息发送

44
00:02:59,537 --> 00:03:03,818
Bob时，消息通过了一系列代理服务器，这些消息通过适当的

45
00:03:03,818 --> 00:03:08,271
加解密后，最后传给Bob时，不仅Bob不知道谁在跟他说话，

46
00:03:08,271 --> 00:03:12,724
那些代理服务器甚至也不清楚Alice的通话对象是Bob，

47
00:03:12,724 --> 00:03:16,750
或者说，谁都不知道对方是谁。有趣的是，匿名通信

48
00:03:16,750 --> 00:03:20,498
的通道实际上是一个双向通道。换句话说，

49
00:03:20,498 --> 00:03:24,743
虽然Bob不知道对方是谁，他仍然可以向对方做出回答，

50
00:03:24,743 --> 00:03:29,153
而Alice也能获得这些消息。一旦我们有了匿名通信，就可以

51
00:03:29,153 --> 00:03:33,784
构造其他隐私的机制了。另一个例子， 匿名数字现金

52
00:03:33,784 --> 00:03:37,643
在现实世界中，如果我有实实在在的1美元，

53
00:03:37,643 --> 00:03:42,108
我可以去书店，并买了一本书，而老板并不知道我是谁。

54
00:03:42,108 --> 00:03:46,876
问题是我们是否可以在数字世界做同样的事情呢？

55
00:03:46,876 --> 00:03:50,963
在数字世界里，假设Alice有虚拟的1美元硬币，

56
00:03:50,963 --> 00:03:55,984
她想要在网上书店花掉这虚拟的1美元，

57
00:03:55,984 --> 00:04:00,760
现在，我们想做同现实世界一样，那就是

58
00:04:00,760 --> 00:04:05,539
当Alice用这1美元在网上书店买书时，书店也会知道她是谁。

59
00:04:05,539 --> 00:04:10,629
这样，我们就提供了与现实中相同的匿名服务。

60
00:04:10,629 --> 00:04:15,470
现在的问题是在数字世界里，Alice可以做一些邪恶的事情，

61
00:04:15,470 --> 00:04:20,250
在她花掉这虚拟1美元之前，她可以做几份拷贝，

62
00:04:20,250 --> 00:04:24,086
突然之间Alice就不止只有1美元了

63
00:04:24,093 --> 00:04:27,936
她有了3个1美元硬币，并且它们是一模一样的。

64
00:04:27,936 --> 00:04:31,828
没人能组织她做这样的拷贝，或者在其他网络商家

65
00:04:31,828 --> 00:04:35,819
花掉这拷贝的钱。所以问题是我们如何提供匿名数字现金，

66
00:04:35,819 --> 00:04:39,849
但同时，也防止Alice做刚刚我们说过的那些事？

67
00:04:39,849 --> 00:04:43,760
在某种意义上，有一个悖论，那就是

68
00:04:43,760 --> 00:04:47,879
匿名是与安全是冲突的。因为如果Alice有了匿名现金，

69
00:04:47,879 --> 00:04:51,999
那么没人可以阻止她拷贝硬币了。而正因为

70
00:04:51,999 --> 00:04:56,244
现金是匿名的，我们也没有办法找出谁做出了这种欺诈行为。

71
00:04:56,244 --> 00:05:00,394
那我们如何解决呢？事实证明，完全是有办法的。

72
00:05:00,394 --> 00:05:04,757
稍后我们会详述匿名数字现金。现在只是给个提示，

73
00:05:04,757 --> 00:05:09,173
我们可以这么做：如果 Alice 花同一枚硬币仅仅一次，

74
00:05:09,173 --> 00:05:13,764
那么没人知道她是谁；但如果她花同一个硬币超过一次，

75
00:05:13,764 --> 00:05:17,878
那么突然之间，她的身份就被暴露了，然后估计就会被警察

76
00:05:17,878 --> 00:05:22,096
请去公安局坐坐了。这就是匿名数字现金的工作方式。

77
00:05:22,096 --> 00:05:26,158
我们将在后面的课程中尝试实现它。

78
00:05:26,158 --> 00:05:30,219
另一个密码学应用是与一些抽象的协议结合的，

79
00:05:30,219 --> 00:05:34,333
在我告诉你这是什么之前，先举两个例子。

80
00:05:34,333 --> 00:05:38,343
第一个例子与选举系统有关。

81
00:05:38,343 --> 00:05:42,656
我们有两个党，党0和党1。选民为他们心宜的党投票。

82
00:05:42,656 --> 00:05:47,101
在这个例子中，选民可能支持党0，也可能支持党1。

83
00:05:47,101 --> 00:05:52,313
就像这样...在这次选举中，党0得到了3票，而另一个当得到了

84
00:05:52,313 --> 00:05:56,590
2票。所以，党0在此次选举中获胜。

85
00:05:56,590 --> 00:06:01,579
因为一般说来得到大多数选票的党成为选举中的胜者。

86
00:06:01,579 --> 00:06:06,453
现在，投票的问题如下：选民希望

87
00:06:06,453 --> 00:06:11,720
知道哪个党得到了大部分选票，但与此同时并不会泄露

88
00:06:11,720 --> 00:06:16,797
具体票数。那么应该怎么做呢？

89
00:06:16,797 --> 00:06:21,493
为了达到这个目的，我们引进“选举中心”，它将帮助我们

90
00:06:21,493 --> 00:06:26,633
计算票数，但不泄露其他信息。

91
00:06:26,633 --> 00:06:32,027
参与竞选的党派将把票数通过加密送入竞选中心，

92
00:06:32,027 --> 00:06:36,949
在竞选结束后，竞选中心

93
00:06:36,949 --> 00:06:41,615
计算票数并宣布获胜方，而其他的所有

94
00:06:41,615 --> 00:06:46,580
信息都不会泄露，也就是说单独的

95
00:06:46,580 --> 00:06:51,366
票数仍然保密。选举中心当然也需要

96
00:06:51,366 --> 00:06:56,331
对选民进行验证，例如选民是否有权投票，以及

97
00:06:56,331 --> 00:07:00,818
是否只投了一次。但是除此之外，选举中心和

98
00:07:00,818 --> 00:07:05,484
其他所有人或组织都只知道选举结果。

99
00:07:05,484 --> 00:07:10,104
这是一种涉及六个对象的协议，

100
00:07:10,104 --> 00:07:14,430
在这种情况下，有5个选民，1个选举中心。

101
00:07:14,430 --> 00:07:19,417
他们将计算选票，而在计算结束时，

102
00:07:19,417 --> 00:07:24,404
除了得知结果，其他的一切信息，诸如个人输入都未被泄露。

103
00:07:24,404 --> 00:07:29,156
类似的问题也出现了私人拍卖会上。假设一个私人卖家

104
00:07:29,156 --> 00:07:34,160
对自己想要的商品进行竞标。

105
00:07:34,160 --> 00:07:39,356
拍卖机制使用的是“维克瑞拍卖”，即

106
00:07:39,356 --> 00:07:45,287
出价最高者是这件商品竞标的获胜者，但

107
00:07:45,287 --> 00:07:50,099
他只需要按第二高的出价支付。

108
00:07:50,099 --> 00:07:54,850
这就是所谓的“维克瑞拍卖”。

109
00:07:54,850 --> 00:08:00,028
现在我们想做的是，第一

110
00:08:00,028 --> 00:08:04,779
要弄清楚出价最高者是谁，其次这个人要支付多少钱，

111
00:08:04,779 --> 00:08:09,165
除此之外的其他个人竞标信息都要保密。

112
00:08:09,165 --> 00:08:14,160
例如，出价最高的实际金额

113
00:08:14,160 --> 00:08:19,225
应保密，唯独要公开的是第二高的出价金额，

114
00:08:19,225 --> 00:08:23,526
以及出价最高的人的身份。所以在此，

115
00:08:23,526 --> 00:08:28,172
我们引进“拍卖中心”，并以和选举例子类似的方法执行，即

116
00:08:28,172 --> 00:08:32,588
每人将向拍卖中心发送加密的竞标书。拍卖中心将

117
00:08:32,588 --> 00:08:37,119
计算的获胜者身份，以及第二高的出价，

118
00:08:37,119 --> 00:08:41,822
但除了这两个值以外，其他信息仍然保密。

119
00:08:41,822 --> 00:08:46,126
现在，举一个更普遍问题的例子，即

120
00:08:46,126 --> 00:08:50,264
安全多方计算。那么安全多方计算到底是什么呢？

121
00:08:50,264 --> 00:08:54,618
简单地说，参与者有一个秘密输入。

122
00:08:54,618 --> 00:08:58,649
所以，在选举中，输入即为投票；

123
00:08:58,649 --> 00:09:02,787
在拍卖会上，输入即为秘密的投标书。

124
00:09:02,787 --> 00:09:06,959
参与者希望以某种函数，以他们的输入来计算结果。

125
00:09:06,959 --> 00:09:10,840
在选举中，函数即为计算大多数票数，输出获胜者。

126
00:09:10,840 --> 00:09:15,088
在拍卖中，该函数计算第二高的金额，以及最高者金额的编号

127
00:09:15,088 --> 00:09:19,179
可他们该怎么做，才能只输出函数计算的值，

128
00:09:19,179 --> 00:09:23,375
而其他信息维持保密呢？

129
00:09:23,375 --> 00:09:27,675
一种比较呆板的、 不安全的方法是，我们引进一个

130
00:09:27,675 --> 00:09:31,774
可信组织。然后，这个可信组织将收集所有的个人输入。

131
00:09:31,774 --> 00:09:36,223
并且，它承诺对各个输入保密，也就只有它

132
00:09:36,223 --> 00:09:40,510
知道那些具体输入情况。最后，它计算函数的值后公布结果。

133
00:09:40,510 --> 00:09:44,742
这样一来，我们得到了结果，但

134
00:09:44,742 --> 00:09:48,812
其他信息未被泄露。当然，你必须

135
00:09:48,812 --> 00:09:52,990
要信任这个可信组织，如果你觉得它会搞名堂，

136
00:09:52,990 --> 00:09:57,168
那就没用了。所以，密码学中有一个

137
00:09:57,168 --> 00:10:01,001
让人很吃惊的中心理论：任何你想要

138
00:10:01,001 --> 00:10:05,204
做的计算或者函数，如果你能把这个计算交给

139
00:10:05,204 --> 00:10:09,302
可信组织做，那么你也一定可以不需要可信组织来得到结果。

140
00:10:09,302 --> 00:10:13,559
让我在较高级别上解释这意味着什么。也就是说，我们做的

141
00:10:13,559 --> 00:10:17,816
任何事情都可以不要可信组织插手。所以实际上参与者不需要

142
00:10:17,816 --> 00:10:21,807
将输出提供给可信组织。并且，事实上，在系统中也没有

143
00:10:21,807 --> 00:10:26,011
什么权威组织。那些参与者需要的仅仅只是使用某种协议与

144
00:10:26,011 --> 00:10:30,567
其他参与者交换信息。而在结束后，

145
00:10:30,567 --> 00:10:34,890
每个人都只知道最终结果是什么。

146
00:10:34,890 --> 00:10:39,390
换句话说，

147
00:10:39,390 --> 00:10:43,639
个体的输入仍然是保密的。但在此之中也没有可信权威组织

148
00:10:43,639 --> 00:10:47,867
只是通过另一种方式来获得最终的输出。

149
00:10:47,867 --> 00:10:51,846
这是一个普遍的结果，虽然有些难以置信，但却是可行的。

150
00:10:51,846 --> 00:10:56,024
事实上，在课程快结束时，我们就会知道如何做啦！

151
00:10:56,024 --> 00:11:00,577
还有一些我不能将它们归类的密码学应用，

152
00:11:00,577 --> 00:11:05,560
但它们确实很神奇。

153
00:11:05,560 --> 00:11:10,240
举两个例子。第一个称之为“私下外包计算”。

154
00:11:10,240 --> 00:11:15,224
为了方便说明，就以谷歌搜索为例子吧。

155
00:11:15,224 --> 00:11:20,329
假设Alice有一串搜索关键词想要查询，

156
00:11:20,329 --> 00:11:25,434
并且有一些特殊的加密方案使得她可以将加密的查询

157
00:11:25,434 --> 00:11:30,368
信息发送给谷歌。由于这种特殊加密方案的某个特性，

158
00:11:30,368 --> 00:11:35,304
谷歌可以基于这些加过密的信息计算搜索，而无需知道

159
00:11:35,304 --> 00:11:40,368
原始的文本是什么。也就是说，谷歌可以基于加密的信息，运

160
00:11:40,368 --> 00:11:44,903
运行其大规模的搜索算法，并得到加密的结果。之后，谷歌将

161
00:11:44,903 --> 00:11:49,242
发送加密的结果给Alice，Alice解密信息后得到查询的结果。

162
00:11:49,242 --> 00:11:53,689
神奇的地方在于，谷歌只知道加过密的查询内容，

163
00:11:53,689 --> 00:11:57,493
所以，谷歌也不知道什么Alice到底想要搜索什么，

164
00:11:57,493 --> 00:12:01,672
以及Alice到底得到了什么结果。

165
00:12:01,672 --> 00:12:05,812
这些就是神奇的加密方案。

166
00:12:05,812 --> 00:12:09,985
它们是最近才发展的，大约从两年或三年前开始。

167
00:12:09,985 --> 00:12:14,436
它使我们能够计算加密的数据，即使我们不知道

168
00:12:14,436 --> 00:12:18,667
加密的内容是什么。现在，在你飘飘然之前想想如何实现。

169
00:12:18,667 --> 00:12:22,470
虽然现在来说只是理论，

170
00:12:22,470 --> 00:12:26,422
也许到那谷歌实现这个技术的那一天还要很久很久，

171
00:12:26,422 --> 00:12:30,521
但尽管如此，这个方案可行的事实已经令人无比兴奋了，

172
00:12:30,521 --> 00:12:34,473
并且，就一些相对简单的计算而言，它是非常有用的。

173
00:12:34,473 --> 00:12:38,671
事实上，我们将在稍后看到一些这样的应用。另外一个神奇的

174
00:12:38,671 --> 00:12:42,474
应用，是所谓的“零知识”。

175
00:12:42,474 --> 00:12:46,080
我先说说“零知识证明”。

176
00:12:46,080 --> 00:12:50,177
假设Alice知道一个确定的数N，

177
00:12:50,177 --> 00:12:54,169
数字 N 是由两个大素数构造的。试想一下，

178
00:12:54,169 --> 00:12:58,835
我们有两个素数 P 和 Q。它们很大很大，比如一千位。

179
00:12:58,835 --> 00:13:03,892
我们知道两个1000位的数字想成很容易。

180
00:13:03,892 --> 00:13:08,235
但如果我给你一个乘积的结果，让你把它分解为两个质数，

181
00:13:08,235 --> 00:13:12,427
其实是相当困难的。事实上，我们要利用因数难分解的特点，

182
00:13:12,427 --> 00:13:16,566
来构造公共密钥的密码系统，这个我们将在课程后半部分讲到

183
00:13:16,566 --> 00:13:20,968
现在，Alice有此数字 N，并且她也知道的构成N的因子。

184
00:13:20,968 --> 00:13:24,898
而Bob只知道数字N，他不知道构成N的因子是什么。

185
00:13:24,898 --> 00:13:28,723
现在就是见证奇迹的时刻：根据“零知识证明”，

186
00:13:28,723 --> 00:13:33,144
Alice可以向Bob证明她知道的 N 的因子，

187
00:13:33,144 --> 00:13:37,457
Bob也可以做一些验证，证实Alice没有骗他，

188
00:13:37,457 --> 00:13:42,386
最终，Bob却只知道N的值是什么，不知道因子P和Q的值。

189
00:13:42,386 --> 00:13:47,034
这就是可证明的。Bob绝对不知道因子P和Q的值是什么。

190
00:13:47,034 --> 00:13:50,997
实际上这个论证是很普遍的，一般的。

191
00:13:50,997 --> 00:13:55,275
它不仅仅能证明N的因式分解，还能证明你所知道的任何难题

192
00:13:55,275 --> 00:13:59,606
的答案都是你的知识。因此，如果

193
00:13:59,606 --> 00:14:03,831
你解决了字谜拼图，好吧，我承认字谜这个例子不太好。

194
00:14:03,831 --> 00:14:07,845
如果你解决了一个数独难题，你想证明你解决了它，

195
00:14:07,845 --> 00:14:12,282
那么你可以证明给Bob看，虽然Bob不知道答案，

196
00:14:12,282 --> 00:14:16,718
但却能坚信你确实知道这个数独难题的答案。

197
00:14:16,718 --> 00:14:20,930
看看，密码学的这个应用神奇吧！

198
00:14:20,930 --> 00:14:25,000
最后我想说，现代密码学是一个非常

199
00:14:25,000 --> 00:14:29,015
严谨的科学。事实上，我们描述的每个概念都将

200
00:14:29,015 --> 00:14:33,129
严格的按照三个步骤，我们将反反复复地遵循这三个步骤

201
00:14:33,129 --> 00:14:37,338
所以我想要解释它们是什么。首先，

202
00:14:37,338 --> 00:14:41,493
象介绍什么是数字签名那样，

203
00:14:41,493 --> 00:14:45,540
我们先说说什么是威胁模型。数字签名中的威胁模型是攻击者

204
00:14:45,540 --> 00:14:49,534
如何对数字签名发动攻击，以及攻击者为什么要伪造签名？

205
00:14:49,534 --> 00:14:53,851
对于数字签名这个例子，我们一定要了解，签名必须是

206
00:14:53,851 --> 00:14:57,760
无法伪造的。三个步骤是，

207
00:14:57,760 --> 00:15:01,998
对于每一个基元，我们要描述需要

208
00:15:01,998 --> 00:15:06,464
精确定义的威胁模型是什么。接着，提出一种方案。

209
00:15:06,464 --> 00:15:10,931
再证明在特定威胁模型条件下，任何攻击者都能攻击这个方案

210
00:15:10,931 --> 00:15:15,955
一旦攻击者成功了，那么攻击者也可以解决相对应的一些

211
00:15:15,955 --> 00:15:20,150
根本的复杂的难题。如果难题够复杂攻击者无法破解，

212
00:15:20,150 --> 00:15:24,350
那么也就证明了在这个威胁模型下没有攻击者能破解这个方案

213
00:15:24,350 --> 00:15:27,843
以上的三个步骤实际上相当重要。就签名这个例子而言，

214
00:15:27,843 --> 00:15:31,928
我们要定义数字签名意味着什么，那就是不可伪造性。

215
00:15:31,928 --> 00:15:35,914
接着给出一个方案，并指出任何一个可以破解我们的方案

216
00:15:35,914 --> 00:15:39,801
的人都能解决因子整数分解，而因子整数分解被普遍认为

217
00:15:39,801 --> 00:15:43,541
是一个很难的问题。在今后，我们将遵循这三个步骤，

218
00:15:43,541 --> 00:15:47,331
就能得到证明的结果了。这些就是本节的内容。

219
00:15:47,331 --> 00:15:51,218
在下一节，我们将谈谈 密码学的历史。

220
00:15:51,218 --> 00:15:52,006
End