WEBVTT - This file was automatically generated by VIMEO

0
00:00:09.200 --> 00:00:12.400
Welcome to section 5 Section 5 is

1
00:00:12.400 --> 00:00:15.300
 the second section dedicated to public key cryptography.

2
00:00:16.400 --> 00:00:19.600
In section 4 we have seen how to build methods

3
00:00:19.600 --> 00:00:21.700
 for encryption and key agreement.

4
00:00:22.600 --> 00:00:25.400
In Section 5 we'll first discuss how

5
00:00:25.400 --> 00:00:28.900
 to create digital signature methods from RSA.

6
00:00:29.700 --> 00:00:32.900
Then we will see pkcs standards

7
00:00:32.900 --> 00:00:36.000
 that will consolidate RSA algorithms

8
00:00:35.200 --> 00:00:38.600
 that we have seen into secure and

9
00:00:38.600 --> 00:00:41.500
 standardized methods for encryption and

10
00:00:41.500 --> 00:00:42.000
 signature.

11
00:00:44.100 --> 00:00:47.000
In video 5.1. We will see how

12
00:00:47.200 --> 00:00:51.500
 to construct in digital signature algorithm from RSA.

13
00:00:50.500 --> 00:00:52.700
 Let's get started.

14
00:00:54.900 --> 00:00:57.500
Let's first review the general scheme of

15
00:00:57.500 --> 00:00:59.300
 digital signature method.

16
00:01:00.500 --> 00:01:03.300
Alice has a pair of keys a public

17
00:01:03.300 --> 00:01:06.500
 APK and a private key or secret

18
00:01:06.500 --> 00:01:07.300
 key Escape.

19
00:01:08.300 --> 00:01:11.700
She uses her secret key to compute

20
00:01:11.700 --> 00:01:14.200
 a signature s that she appended to

21
00:01:14.200 --> 00:01:15.100
 her message X.

22
00:01:15.900 --> 00:01:17.500
and since the pair to Bob

23
00:01:18.500 --> 00:01:21.600
Bob uses Alice's public key PK

24
00:01:21.600 --> 00:01:24.500
 to verify that the pair of message and signature

25
00:01:24.500 --> 00:01:25.400
 is valid.

26
00:01:26.100 --> 00:01:30.000
Functionally Alice would like to prove to pop that

27
00:01:29.700 --> 00:01:33.200
 she is the origin of the message and

28
00:01:32.200 --> 00:01:35.800
 that the data she sent was not modified

29
00:01:35.800 --> 00:01:36.600
 during Transit.

30
00:01:38.100 --> 00:01:39.500
the security guarantees

31
00:01:40.500 --> 00:01:43.900
are that first it is impossible for

32
00:01:43.900 --> 00:01:46.800
 anyone who does not have the private

33
00:01:46.800 --> 00:01:49.800
 key to forge a valid pair access.

34
00:01:51.500 --> 00:01:54.700
Second this guarantee must remain even

35
00:01:54.700 --> 00:01:58.500
 when the attacker has seen several valid

36
00:01:57.500 --> 00:02:01.000
 pairs of messages and

37
00:02:00.800 --> 00:02:02.500
 corresponding signatures.

38
00:02:03.500 --> 00:02:06.400
The attackers should not be able to forge a

39
00:02:06.400 --> 00:02:10.100
 new pair of message and signature

40
00:02:09.100 --> 00:02:12.800
 by manipulating the previous ones.

41
00:02:14.700 --> 00:02:17.800
The way we will proceed to achieve the previous goal

42
00:02:17.800 --> 00:02:20.800
 is by transforming a public encryption method

43
00:02:20.800 --> 00:02:23.300
 into a digital signature method.

44
00:02:24.400 --> 00:02:27.900
This is done by inverting the rules

45
00:02:27.900 --> 00:02:30.600
 of the public key and symmetric

46
00:02:30.600 --> 00:02:30.700
 key.

47
00:02:31.300 --> 00:02:33.400
and the encrypt decrypt routines

48
00:02:34.300 --> 00:02:37.200
the signal release decrypts the message

49
00:02:37.200 --> 00:02:39.700
 and the verifier Bob encrypts it

50
00:02:40.600 --> 00:02:44.000
Alice is obviously the only party authorized

51
00:02:43.200 --> 00:02:46.600
 to do the decrypt operation

52
00:02:46.600 --> 00:02:50.500
 as she is the only party who knows the private

53
00:02:49.500 --> 00:02:52.400
 key SK Bob which

54
00:02:52.400 --> 00:02:55.400
 can be any very verifier can apply the

55
00:02:55.400 --> 00:02:58.000
 encrypt using the public.

56
00:02:59.200 --> 00:03:02.700
We would name the decrypt method assigned and the

57
00:03:02.700 --> 00:03:04.400
 encrypt method as extract.

58
00:03:05.300 --> 00:03:08.300
Just to have meaningful names in the context of digital

59
00:03:08.300 --> 00:03:12.000
 signatures, but the operation performed in

60
00:03:11.800 --> 00:03:14.500
 sign and extract are exactly

61
00:03:14.500 --> 00:03:18.100
 the same as in decrypt encrypt routines

62
00:03:17.100 --> 00:03:20.300
 that we have seen in the previous video.

63
00:03:21.400 --> 00:03:24.400
Notice that the signature method not

64
00:03:24.400 --> 00:03:27.800
 only proves origin authentication and data

65
00:03:27.800 --> 00:03:28.100
 integrity.

66
00:03:28.900 --> 00:03:31.500
It also allows to recover the original

67
00:03:31.500 --> 00:03:33.500
 message from the signature.

68
00:03:34.200 --> 00:03:37.500
So we do not need to send the message with

69
00:03:37.500 --> 00:03:38.400
 the signature.

70
00:03:40.100 --> 00:03:43.900
Let's see detailed description of the operations performed by

71
00:03:43.900 --> 00:03:44.800
 Alison Bob.

72
00:03:45.200 --> 00:03:48.700
First we have a key generation, which

73
00:03:48.700 --> 00:03:51.400
 is identical to what we saw for

74
00:03:51.400 --> 00:03:54.300
 the encryption. So there is generation of

75
00:03:54.300 --> 00:03:57.200
 the modulus and computation of

76
00:03:57.200 --> 00:04:01.700
 the public key e and the corresponding private

77
00:04:00.700 --> 00:04:03.400
 key D to sign

78
00:04:03.400 --> 00:04:06.300
 a message X Alice Rises the

79
00:04:06.300 --> 00:04:09.600
 message to the security key and

80
00:04:09.600 --> 00:04:12.500
 since the signature the result as

81
00:04:12.500 --> 00:04:15.200
 the signature s and Bob raises the

82
00:04:15.200 --> 00:04:18.400
 signature s that he received to the public

83
00:04:18.400 --> 00:04:20.400
 key to extract X.

84
00:04:21.400 --> 00:04:24.400
This method is correct for the same reasons

85
00:04:24.400 --> 00:04:27.700
 that we saw in the previous video. I

86
00:04:27.700 --> 00:04:30.900
 wrote the detailed equalities for

87
00:04:30.900 --> 00:04:34.000
 you if you would like to further check,

88
00:04:33.300 --> 00:04:36.700
 but conceptually it is very

89
00:04:36.700 --> 00:04:39.300
 similar to what we have seen for

90
00:04:39.300 --> 00:04:39.900
 the encryption.

91
00:04:40.600 --> 00:04:43.800
We just inverted the rules of the ENT.

92
00:04:45.500 --> 00:04:49.500
How about security does the digital signature

93
00:04:48.500 --> 00:04:52.000
 method achieve the security guarantees? We

94
00:04:51.300 --> 00:04:54.000
 set a couple of slides ago.

95
00:04:54.900 --> 00:04:57.800
Well, there are at least two security concerns

96
00:04:57.800 --> 00:05:00.400
 here first an attacker can

97
00:05:00.400 --> 00:05:01.500
 select a random s

98
00:05:02.200 --> 00:05:05.800
Which will be a power of some message X

99
00:05:05.800 --> 00:05:09.000
 and the attacker can apply the

100
00:05:08.900 --> 00:05:11.200
 extract routine with the public

101
00:05:11.200 --> 00:05:13.200
 key because the he knows the public key.

102
00:05:14.200 --> 00:05:17.100
So he can also know the message corresponding to

103
00:05:17.100 --> 00:05:18.900
 that signature.

104
00:05:19.600 --> 00:05:23.000
And you would have obtained the valid pair XS so

105
00:05:22.200 --> 00:05:25.600
 he can forge the signatures.

106
00:05:27.600 --> 00:05:31.900
The attacker has another way to forge valid

107
00:05:30.900 --> 00:05:33.300
 signatures. This is

108
00:05:33.300 --> 00:05:36.600
 from what we call a homomorphic property

109
00:05:36.600 --> 00:05:39.400
 of RSA and the explanation is

110
00:05:39.400 --> 00:05:42.400
 actually that from two signatures.

111
00:05:43.500 --> 00:05:47.300
We can multiply them to obtain a third

112
00:05:46.300 --> 00:05:49.900
 valid signature. We

113
00:05:49.900 --> 00:05:52.600
 can see the detailed explanation here.

114
00:05:53.800 --> 00:05:56.600
So when the attacker obtains to

115
00:05:56.600 --> 00:05:59.200
 sincers SNS prime,

116
00:05:59.200 --> 00:06:00.400
 it can be reply them.

117
00:06:01.100 --> 00:06:05.000
And by here writing how these signatures are

118
00:06:04.600 --> 00:06:07.500
 related to some messages x and

119
00:06:07.500 --> 00:06:10.500
 x Prime and we have a result that says that

120
00:06:10.500 --> 00:06:13.300
 the product of two Powers with

121
00:06:13.300 --> 00:06:14.300
 the same exponent.

122
00:06:15.200 --> 00:06:18.900
Is the power of the product of

123
00:06:18.900 --> 00:06:21.900
 X and X Prime to that exponent?

124
00:06:21.900 --> 00:06:24.800
 So this way the attacker obtained

125
00:06:24.800 --> 00:06:28.000
 a new signature corresponding to

126
00:06:27.100 --> 00:06:29.600
 the message X and express.

127
00:06:30.800 --> 00:06:33.900
So this is another way how by manipulating

128
00:06:33.900 --> 00:06:37.100
 a previously sent signatures the

129
00:06:36.100 --> 00:06:39.500
 attacker can forge a new signature.

130
00:06:41.500 --> 00:06:45.000
Previous security issues can be fixed using

131
00:06:44.100 --> 00:06:46.600
 cryptographic hash function.

132
00:06:47.900 --> 00:06:50.700
This is the hush and sign approach.

133
00:06:51.100 --> 00:06:54.200
So instead of directly signing a message.

134
00:06:55.200 --> 00:06:59.200
We first hash it to obtain some digest h.

135
00:07:00.100 --> 00:07:02.900
Then we sign the Digest.

136
00:07:04.200 --> 00:07:06.800
So Alice sends a pair.

137
00:07:07.500 --> 00:07:07.800
of

138
00:07:08.900 --> 00:07:11.800
X the original message before the hashing and

139
00:07:11.800 --> 00:07:13.400
 the signature

140
00:07:14.500 --> 00:07:17.000
Bob has first two recompute the

141
00:07:17.800 --> 00:07:19.000
 digest each from X.

142
00:07:20.300 --> 00:07:23.900
Before verifying that S and

143
00:07:23.900 --> 00:07:26.100
 H is a valid beer.

144
00:07:27.900 --> 00:07:30.800
I think the cryptographic hashing fix

145
00:07:30.800 --> 00:07:32.300
 the security concerns.

146
00:07:33.600 --> 00:07:36.300
For the first attack that we saw in the previous Slide

147
00:07:36.300 --> 00:07:40.200
 the attacker cannot retrieve X from random

148
00:07:39.200 --> 00:07:40.800
 signature.

149
00:07:42.200 --> 00:07:45.900
To be able to do that. He would have inverted the

150
00:07:45.900 --> 00:07:48.400
 hash function which is completely hard.

151
00:07:48.400 --> 00:07:52.200
 That's why it's important that we use a cryptographic

152
00:07:51.200 --> 00:07:54.600
 hash function and not any attraction.

153
00:07:56.100 --> 00:07:59.600
For the second attack that we have seen these forgery of

154
00:07:59.600 --> 00:08:02.900
 signature from previously sent

155
00:08:02.900 --> 00:08:03.800
 signatures.

156
00:08:04.900 --> 00:08:08.000
By multiplying the two signatures the

157
00:08:07.700 --> 00:08:10.300
 attacker can still obtain a

158
00:08:10.300 --> 00:08:11.700
 signature of some message.

159
00:08:12.400 --> 00:08:15.600
But to retrieve the message corresponding to that signature,

160
00:08:15.600 --> 00:08:18.200
 he also has to invert the hash

161
00:08:18.200 --> 00:08:18.400
 function.

162
00:08:19.200 --> 00:08:22.400
And keep in mind that in this scheme. We have

163
00:08:22.400 --> 00:08:25.800
 to send not only the signature but the

164
00:08:25.800 --> 00:08:28.300
 original message and the signature.

165
00:08:30.600 --> 00:08:34.100
In this video we saw how to construct digital signatures

166
00:08:33.100 --> 00:08:35.000
 from RSA.

167
00:08:35.800 --> 00:08:38.000
We also saw the sort of attacks we can

168
00:08:38.200 --> 00:08:39.200
 have with a naive Construction.

169
00:08:40.300 --> 00:08:43.600
We introduced the high level idea of hash and

170
00:08:43.600 --> 00:08:46.300
 sign approach that fixes the security problems.

171
00:08:47.100 --> 00:08:50.700
The next video will adapt this approach to our sacred to

172
00:08:50.700 --> 00:08:54.100
 system. And we also detail the RSA

173
00:08:53.100 --> 00:08:56.900
 standards for both encryption and

174
00:08:56.900 --> 00:08:57.800
 signatures.

175
00:08:58.500 --> 00:08:59.800
So see you in the next video.
