11 - 2 - Constructions (11 min) .srt

1
00:00:00,000 --> 00:00:03,827
上一节我们解释了什么是公钥加密系统
In the last segment, we explained what is
a public key encryption system. And we

2
00:00:03,827 --> 00:00:07,557
我们定义了安全的公钥加密系统是什么意思
defined what it means for a public key
encryption system to be secure. If you

3
00:00:07,557 --> 00:00:11,142
如果大家记得，我们要求对抗主动攻击的安全性。特别地
remember, we required security against
active attacks. And in particular, we

4
00:00:11,142 --> 00:00:15,211
我们定义了选择密文安全，作为我们的目标。
本周，我们组建两个
defined chosen cipher text security as our
goal. This week, we're gonna construct two

5
00:00:15,211 --> 00:00:19,281
公钥加密系统的家族，它们都是选择密文安全的
families of public key encryption systems
that are chosen cipher text secure. And in

6
00:00:19,281 --> 00:00:22,914
本节我们开始构建公钥加密
this segment, we're gonna start by
constructing public key encryptions from,

7
00:00:23,059 --> 00:00:27,124
从一个叫做陷门置换的概念出发
a concept called a trapdoor
permutation. So let's start by defining a

8
00:00:27,124 --> 00:00:31,064
那么我们先定义一个广义的概念叫做陷门函数。
什么是陷门函数？
general concept called a trapdoor
function. So what is a trapdoor function?

9
00:00:31,064 --> 00:00:35,484
陷门函数是一个函数，从集合X映射到集合Y
Well, a trapdoor function basically is a
function that goes from some set X to some

10
00:00:35,484 --> 00:00:39,585
它定义为三个算法
set Y. And it's really defined by a triple
of algorithms. There's a generation

11
00:00:39,585 --> 00:00:43,685
它们是：一个通用的算法，函数f，和函数f的逆
algorithm, the function f, and the inverse
of the function f. So the generation

12
00:00:43,685 --> 00:00:47,892
那么这个通用算法，当你运行它时，它会生成一对密钥
algorithm, basically what it does when you
run it, it will generate a key pair, a

13
00:00:47,892 --> 00:00:52,098
一个公钥和私钥。这个公钥定义了一个
public key and a secret key. The public
key is gonna define a specific function

14
00:00:52,098 --> 00:00:56,869
从集合X映射到集合Y的特定函数。然后私钥定义了
from the set X to the set Y. And then the
secret key is going to define the inverse

15
00:00:56,869 --> 00:01:01,639
这个函数的逆，从集合Y映射到集合X。那么这里的想法是
function now from the set Y to the set
X. So the idea is that you can evaluate

16
00:01:01,639 --> 00:01:06,588
你可以使用公钥PK计算这个函数在任意点的值，
你可以使用私钥SK来计算函数的逆
the function at any point using a public key
PK and then you can invert that function

17
00:01:06,588 --> 00:01:12,443
我说逆是什么意思？更为精确地
using the secret key, SK. So what do I
mean by inversion? More precisely, if we

18
00:01:12,443 --> 00:01:17,255
如果我们看这个密钥生成算法G生成的公钥、私钥对
look at any public key and secret key pair
generated by the key generation algorithm

19
00:01:17,255 --> 00:01:21,727
如果我计算函数在点X的值
G, then it so happens that if I evaluate
the function at the point X, and then I

20
00:01:21,727 --> 00:01:26,142
然后我计算所得点的逆，我应该获得原点X
evaluate the inverse at the resulting
point, I should get the original point X

21
00:01:26,142 --> 00:01:30,670
大家应该想象出，有这么个大集合X
back. So the picture you should have in
your mind, is there is this big set X and

22
00:01:30,670 --> 00:01:35,857
和大集合Y，然后这个函数会把X中的任意点映射成Y中的点
this big set Y And then, this function
will map any point in X to a point in Y,

23
00:01:35,857 --> 00:01:41,508
这一步可以使用公钥完成。那么X中的任一点
and this can be done using the public key.
So again any point in X can be mapped, to

24
00:01:41,508 --> 00:01:46,897
可被映射到Y中的一个点。然后如果某人有私钥
a point in Y. And then if someone has the
secret key, then basically they can go in

25
00:01:46,897 --> 00:01:53,758
就可以用这个私钥SK做相反的方向
the reverse direction by applying, this
secret key sk. So now that we

26
00:01:53,758 --> 00:01:58,289
现在我们理解了什么是陷门函数，我们来定义
understand what a trapdoor function is,
let's define what it means for a trapdoor

27
00:01:58,289 --> 00:02:02,652
安全的陷门函数的意思。那么我们说这个三元组
(G,F,F^-1)是安全的
function to be secure. And so we'll say
that this triple, (G, F, F inverse), is secure

28
00:02:02,652 --> 00:02:06,903
如果事实上这个函数F(PK,.)是所谓的单向函数
if in fact this function F(PK, .) is what's
called a one way function. And let me

29
00:02:06,903 --> 00:02:10,986
我们来解释什么是单向函数。其想法是
explain what a, what is a one way
function. The idea is that basically the

30
00:02:10,986 --> 00:02:15,516
这个函数可以在任一点计算，但求它的逆是困难的
function can be evaluated at any point,
but inverting it is difficult without the

31
00:02:15,516 --> 00:02:19,639
如果没有私钥SK的话。那么我们来更为精确地定义，
通常我们使用一个游戏来定义之
secret key SK. So let's define that more
precisely. As usual we define that using a

32
00:02:19,639 --> 00:02:23,764
这里我们有我们的游戏，在挑战者和攻击者之间
game. So here we have our game between the
challenger and the adversary. And the game

33
00:02:23,764 --> 00:02:27,496
游戏如下进行。挑战者生成一个公钥和私钥
proceeds as follows. Basically the
challenger will generate a public key and

34
00:02:27,496 --> 00:02:31,622
他们会生成一个随机X，挑战者把公钥发给攻击者
a secret key. And then they will generate
a random X. It will send the public key

35
00:02:31,622 --> 00:02:36,116
它会计算函数在点X的值
over to the adversary and then it will
evaluate the function at the point X and

36
00:02:36,116 --> 00:02:40,160
然后把所得结果Y也发给攻击者
send the resulting Y also to the
adversary. So all the adversary gets to

37
00:02:40,160 --> 00:02:44,653
那么攻击者看到一个公钥，定义了这个函数是什么
see is just a public key, which defines
what the function is, and then he gets to

38
00:02:44,653 --> 00:02:49,483
然后攻击者看到这个函数在一个随机点X处的像，他的目标是求
see the image of this function on a random
point X and is goal is basically to invert

39
00:02:49,483 --> 00:02:54,097
这个函数在这个点Y处的逆。那么他输出某个X'
the function at this point Y. Okay, so he
outputs some X prime. And we said that the

40
00:02:54,097 --> 00:02:58,507
我们说过，这个陷门函数是安全的，如果
攻击者求出在点Y处的逆的概率
trapdoor function is secure if the
probability that the ad, adversary inverts

41
00:02:58,507 --> 00:03:03,143
是可以忽略的。换句话说，给定Y
the given at point y is negligible. In
other words, given y the probability that

42
00:03:03,143 --> 00:03:07,271
攻击者能够算出Y的原像的概率事实上是可忽略的
the adversary's able to alter the pre
image of y is in fact a negligible

43
00:03:07,271 --> 00:03:11,907
如果这点对所有有效算法都成立，那么我们说
probability and if that's true for all
efficient algorithms then we say that this

44
00:03:11,907 --> 00:03:17,882
这个陷门函数是安全的。那么再抽象点
trapdor function is secure. So again
abstractly, it's a really interesting

45
00:03:17,882 --> 00:03:21,885
这是个有趣的概念，你可以非常容易地从正向计算这个函数
concept in that you can evaluate the
function in the forward direction very

46
00:03:21,885 --> 00:03:26,150
但没人能从反方向计算这个函数
easily. But then no one can evaluate the
function in the reverse direction unless

47
00:03:26,150 --> 00:03:30,311
除非他们有这个陷门私钥SK，有了SK
they have this trapdoor, the secret key
SK, which then all of a sudden lets them

48
00:03:30,311 --> 00:03:35,424
使得他们突然间就能很容易地求这个函数的逆了。
那么使用陷门函数的概念
invert the function very, very easily. So
using the concept of a trapdoor function,

49
00:03:35,424 --> 00:03:39,552
不难构建一个公钥加密系统，我来告诉大家怎么做
it's not too difficult to build a public key encryption system, and let me show you how

50
00:03:39,552 --> 00:03:43,528
这里我们有我们的陷门函数(G,F,F^-1)
to do it. So here we have we our trapdoor
function, (G, F, and F inverse). The other

51
00:03:43,528 --> 00:03:47,605
我们需要的另一个工具是一个对称加密机制
tool that we are going to need is a symmetric encryption scheme, and I'm going to

52
00:03:47,605 --> 00:03:51,531
我要假设这个加密机制对主动攻击是安全的
assume that this encryption scheme is actually
secure against active attacks, so in

53
00:03:51,531 --> 00:03:55,350
那么特别地，我需要提供认证加密
particular I needed to provide
authenticated encryption. Notice that the

54
00:03:55,350 --> 00:04:00,726
注意对称加密系统取K中的密钥，陷门函数取X中的元素为输入
symmetric encryption system takes keys in
K and the trapdoor function takes inputs

55
00:04:00,726 --> 00:04:05,790
这是两个不同的集合，所以我们需要哈希函数
in X. Those are two different sets and so
we're also gonna need the hash function.

56
00:04:05,790 --> 00:04:09,937
从X映射到K。换句话说，它把集合X中的元素映射成密钥
That goes from X to K. In other words, it
maps elements in the set X into keys for

57
00:04:09,937 --> 00:04:14,033
用于对称加密系统。现在我们一旦有了这3个原件
the symmetric encryption systems. And now
once we have these three components, we

58
00:04:14,033 --> 00:04:17,821
我们就可以如下构建公钥加密系统
can actually construct the public key encryption system as follows: so the key

59
00:04:17,821 --> 00:04:21,764
公钥加密系统的密钥生成，与陷门函数的密钥生成
generation for the public key encryption
system is basically exactly the same as

60
00:04:21,764 --> 00:04:25,655
是完全一样的。那么我们为陷门函数运行算法G
the key generation for the trap door
function. So we run G for the trap door

61
00:04:25,655 --> 00:04:29,956
我们获得一个公钥和私钥，这些将是
function, we get a public key and a secret
key. And those are gonna be the public and

62
00:04:29,956 --> 00:04:34,171
公钥加密系统的公钥和私钥。那我们怎么加、解密？
secret keys for the public key encryption
system. And how do we encrypt and decrypt? Let's

63
00:04:34,171 --> 00:04:38,978
我们从加密开始。加密算法取一个公钥和明文为输入
start with encryption. So the encryption
algorithm takes a public key and a message

64
00:04:38,978 --> 00:04:43,898
它会生成一个集合X里的随机元素x
as input. So what it will do is it will
generate a random X from the set capital

65
00:04:43,898 --> 00:04:48,545
然后它会对随机元素x应用这个陷门函数，获得y
X. It will then apply the trapdoor
function to this random X, to obtain Y. So

66
00:04:48,545 --> 00:04:53,130
那么y是x在陷门函数下的像
Y is the image of X under the trapdoor
function. Then it will go ahead and

67
00:04:53,130 --> 00:04:58,272
然后它会生成一个对称密钥，通过取x的哈希值。
那么这是对称加密系统的对称密钥
generate a symmetric key by hashing X. So
this is a symmetric key for the symmetric

68
00:04:58,272 --> 00:05:03,290
最终它加密明文m，使用刚刚生成的密钥
key system. And then finally it encrypts
the plain text message 'm' using this key that was

69
00:05:03,290 --> 00:05:08,123
然后它输出它刚刚计算得到的值y
just generated. And then it outputs the
value Y that it just computed, which is

70
00:05:08,123 --> 00:05:13,260
也就是x的像，与m在对称密码下的加密结果一并输入
the image of X, along the encryption under
the symmetric system of the message M. So

71
00:05:13,260 --> 00:05:18,366
那么这就是加密的工作流程。我想再强调一次
that's how encryption works. And I want to
emphasize again that the trapdoor function

72
00:05:18,366 --> 00:05:23,112
这个陷门函数只用于随机值x，而信息本身
is only applied to this random value X,
whereas the message itself is encrypted

73
00:05:23,112 --> 00:05:28,098
是用对称密钥系统加密的，使用根据我们随机选的x推出的密钥
using a symmetric key system using a key
that was derived from the value X that we

74
00:05:28,098 --> 00:05:32,959
那么现在我们理解了加密，我们再看解密
chose at random. So now that we understand
encryption, let's see how to decrypt.

75
00:05:32,959 --> 00:05:37,366
解密算法取私钥和密文作为输入
While the decryption algorithm takes a
secret key as input, and the ciphertext.

76
00:05:37,366 --> 00:05:41,551
密文本身包含两个部分，值y和C
The ciphertext itself contains two
components, the value Y and the value C.

77
00:05:41,551 --> 00:05:46,070
首先我们应用陷门函数的逆变换
So the first step we're gonna do, is we're
gonna apply the inverse transformation,

78
00:05:46,070 --> 00:05:50,366
逆向陷门函数作用于值y，会返回给我们
the inverse trap door function to the
value Y, and that will give us back the

79
00:05:50,366 --> 00:05:54,495
在加密时选择的随机x。那么现在我问大家
original X that was chosen during
encryption. So now let me ask you, how do

80
00:05:54,495 --> 00:06:00,042
我们如何从这个刚刚得到的x推导出对称的解密密钥K？
we derive the symmetric decryption key K
from this X that we just obtained? Well,

81
00:06:00,042 --> 00:06:04,736
这是个简单问题。我们再次对x取哈希值
so that's an easy question. We basically
hash X again. That gives us K just as

82
00:06:04,736 --> 00:06:09,372
就能给我们与加密时得到的一样的密钥K。现在
我们有了这个对称加密密钥
during encryption. And now that we have
this symmetric encryption key we can apply

83
00:06:09,372 --> 00:06:13,783
我们就可以应用对称解密算法来解密密文C了
the, the symmetric decryption algorithm to
decrypt the ciphertext C. We get the

84
00:06:13,783 --> 00:06:17,741
我们获得了最初的明文M，作为我们的解密输出
original message M and that's what we
output. So, that's how the public key

85
00:06:17,741 --> 00:06:22,321
这就是公钥加密系统的工作过程，这个陷门函数
encryption system works were this trap
door function is only used for encrypting

86
00:06:22,321 --> 00:06:26,788
只用于加密一个随机值x，而实际的明文信息
some sort of a random value X and the
actual message is encrypted using the

87
00:06:26,788 --> 00:06:31,244
是使用对称系统加密的。用图来看，我们有明文M
symmetric system. So in pictures here, we
have the message M obviously the plain

88
00:06:31,244 --> 00:06:35,545
显然明文可以很长，那么我们这里的密文部分
text could be quite large. So, here we
have the body of the deciphered text which

89
00:06:35,545 --> 00:06:39,953
可以是很长的，它是使用对称系统加密的
can be quite long is actually encrypted
using the symmetric system. And then again

90
00:06:39,953 --> 00:06:44,039
然后我再强调一下，对称系统的密钥是x的哈希
I emphasize that the key for the
symmetric system is simply the hash of X.

91
00:06:44,039 --> 00:06:48,232
然后密文的开头就是我们选的随机数x的陷门函数值
And then the header of ciphertext is simply
this application of the trapdoor

92
00:06:48,232 --> 00:06:52,641
而在解密过程中
function to this random X that we picked.
And so during decryption what happens is

93
00:06:52,641 --> 00:06:56,888
我们首先解密密文开头，获得x，然后我们解密
we first decrypt the header to get X and
then we decrypt the body using the

94
00:06:56,888 --> 00:07:01,829
密文部分，使用对称系统，获得最初的明文M
symmetric system to actually get the
original plain text M. So as usual when I

95
00:07:01,829 --> 00:07:06,542
通常当我给大家看一个像这样的系统时，
大家显然想验证，解密的确是
show you a system like this, obviously you
want to verify that decryption in fact is

96
00:07:06,542 --> 00:07:10,605
加密的逆。但更重要地，大家想问
the inverse of encryption. But more
importantly you want to ask why is this

97
00:07:10,605 --> 00:07:14,963
为什么这个系统是安全的。事实上有一个漂亮的安全性定理
system secure. And in fact there's a nice
security theorem here that says. That if

98
00:07:14,963 --> 00:07:18,900
告诉我们，如果开始的陷门函数是安全的，换句话说
the trap door function that we started
with is secure. In other words, that's a

99
00:07:18,900 --> 00:07:22,634
这是个单向函数，如果攻击者没有私钥的话
one way function if the adversary doesn't
have a secret key. The symmetric

100
00:07:22,634 --> 00:07:26,621
对称加密系统提供了认证加密
encryption system provides authenticated
encryption. And the hash function is a

101
00:07:26,621 --> 00:07:30,558
哈希函数是一个随机神谕，意思是它是个随机函数
random oracle, which simply means that
it's a random function from the set X to

102
00:07:30,558 --> 00:07:34,696
从集合X映射到密钥空间K。那么随机神谕是某种理想化的模型
the set of keys K. So a random oracle is
some sort of an idealization of, what a

103
00:07:34,696 --> 00:07:38,280
也是一个哈希函数应具备的性质。当然在实际中
hash function is supposed to be. In
practice, of course, when you come to

104
00:07:38,280 --> 00:07:42,317
当你要实现一个像这样的系统时，你就使用SHA-256
implement a system like this, you would
just use, SHA-256, or any of the

105
00:07:42,317 --> 00:07:47,252
或任何本课程里讨论过的其他哈希函数。
那么在这三个条件下
other hash functions that we discussed in
class. So, under those three conditions in

106
00:07:47,252 --> 00:07:51,863
事实上，我们刚刚讨论的系统是选择密文安全的
fact the system that we just described is
chosen cipher text secure so it is CCA

107
00:07:51,863 --> 00:07:56,416
所以它是CCA安全的。这个ro表示这个安全性
secure, the little ro here just denote the
fact that security is set in what's called

108
00:07:56,416 --> 00:08:00,572
是建立在所谓的随机神谕模型上的。但这只是一个细节，
对我们这里的讨论来说并不重要
a random oracle model. But, that's a detail
that's actually not so important for

109
00:08:00,572 --> 00:08:05,012
我想让大家记住的是，如果陷门函数
discussion here, what I want you to
remember is that if the trap door function

110
00:08:05,012 --> 00:08:09,000
是安全的陷门函数，对称加密系统是安全的
is in fact a secure trap door function. The
symmetric encryption system is secure

111
00:08:09,000 --> 00:08:13,017
能抵抗篡改，所以它提供了认证加密
against tampering so it provides
authenticated encryption. And H

112
00:08:13,017 --> 00:08:17,468
而H某种意义上讲是个好哈希函数，它是一个随机函数
is in some sense a good hash function.
It's a random function, which in practice

113
00:08:17,468 --> 00:08:22,245
在实际中你就使用SHA-256，那么事实上我们刚刚展示的系统
you would just use SHA-256, then in
fact the system that we just showed is CCA

114
00:08:22,245 --> 00:08:27,615
是CCA安全的，选择密文安全的。我应该告诉大家
secure, is chosen ciphertext secure. I should
tell you that there's actually an ISO

115
00:08:27,615 --> 00:08:31,752
实际上有一个ISO标准，定义了这种公钥加密模式
standard that, defines this mode of
encryption, of public encryption. ISO

116
00:08:31,752 --> 00:08:35,781
ISO代表国际标准组织。事实上
stands for International Standards
Organization. So in fact this particular

117
00:08:35,781 --> 00:08:40,456
这个特定的系统已经被标准化了，是个好东西可以用
system has actually been standardized, and
this is a fine thing to use. I'll refer to

118
00:08:40,456 --> 00:08:44,947
我会在未来几节里提到这个ISO加密。为了总结本节
this as the ISO encryption in the next few
segments. To conclude this segment, I want

119
00:08:44,947 --> 00:08:48,925
我想警告大家，有一种错误使用陷门函数来构建的
to warn you about an incorrect way of
using a trapdoor function to build a

120
00:08:48,925 --> 00:08:53,328
公钥加密系统。事实上这种方法可能是人们第一个想到的
public key encryption system. And in fact
this method might be the first thing that

121
00:08:53,328 --> 00:08:57,572
但是它是完全不安全的。那么我来告诉大家
comes to mind, and yet it's completely
insecure. So let me show you, how not to

122
00:08:57,572 --> 00:09:01,762
为什么不要用陷门函数来加密。我们首先能想到的是
encrypt using a trapdoor function. Well
the first thing that might come to mind

123
00:09:01,762 --> 00:09:05,696
直接对明文M使用陷门函数
is, well, let's apply the trapdoor
function directly to the message M. So we

124
00:09:05,696 --> 00:09:10,047
那么我们就使用陷门函数来加密明文M
encrypt simply by applying a function to
the message M, and we decrypt simply by

125
00:09:10,047 --> 00:09:14,180
然后使用F的逆函数来解密密文C，以还原明文M
applying F inverse to the ciphertext C to
recover the original message M. So

126
00:09:14,180 --> 00:09:18,639
那么事实上，解密是加密的逆过程
functionally, this is in fact, decryption
is the inverse of encryption, and yet this

127
00:09:18,639 --> 00:09:22,881
然而这是完全不安全的，有很多的原因
is completely insecure for many, many
different reasons. The easiest way to see

128
00:09:22,881 --> 00:09:26,960
最简单的方法来证明它不安全，在于这是一个确定的加密
that this is insecure, is that it's
simply, this is deterministic encryption.

129
00:09:26,960 --> 00:09:30,944
大家注意这里没有随机性被使用到。当我们加密一个明文M
You notice there is no randomness being
used here. When we encrypt a message

130
00:09:30,944 --> 00:09:34,154
由于算法是确定的
M, and since it is deterministic, it's cannot possibly be

131
00:09:34,154 --> 00:09:37,948
它不可能是语义安全的。但事实上，如我所说，
当我们将这个陷门函数具象化
semantically secure. But in fact, as I
said, when we instantiate this trap door

132
00:09:37,948 --> 00:09:41,644
使用特定的实现，例如RSA陷门函数
function with particular implementations,
for example with the RSA trap door

133
00:09:41,644 --> 00:09:44,951
那么这种机制会有很多可能的攻击
function, then there are many, many
attacks that are possible on this

134
00:09:44,951 --> 00:09:48,794
所以大家永远不要使用它
particular construction, and so you should
never, ever, ever use it, and I'm gonna

135
00:09:48,794 --> 00:09:52,830
本章我将反复重申这一点，事实上在下一节里
repeat this throughout this module, and in
fact in the next segment I'll show you a

136
00:09:52,830 --> 00:09:56,699
我会给大家看很多针对这种实现的攻击
number of attacks on this particular
implementation. Okay so, what I would like

137
00:09:56,699 --> 00:10:00,717
我想让大家记住，你应该使用像ISO标准这样的加密系统
you to remember is that you should be
using an encryption system like the ISO

138
00:10:00,717 --> 00:10:04,992
永远不要对明文M直接使用陷门函数
standard, and you should never apply the
trap door function directly to the message M.

139
00:10:04,992 --> 00:10:09,010
尽管在下节我们会看到其他加密方法
Although in the next segment we'll
see other ways to encrypt using a trap

140
00:10:09,010 --> 00:10:13,233
使用了陷门函数，而且也是正确的。但这种方法
door function that are also correct, but
this particular method is clearly, clearly

141
00:10:13,233 --> 00:10:17,560
显然是错误的。那么现在我们理解了怎样构建公钥加密
incorrect. Okay, so now that we understand
how to build public key encryption

142
00:10:17,560 --> 00:10:21,423
基于一个陷门函数。下一个问题是如何构建陷门函数
given a trap door function, the next
question is how to construct trap door

143
00:10:21,423 --> 00:10:24,360
我们下节讨论之
functions, and we're going to do that in
the next segment.