WEBVTT - This file was automatically generated by VIMEO

0
00:00:07.200 --> 00:00:10.700
In the previous videos, we have seen plain versions

1
00:00:10.700 --> 00:00:13.500
 of RSA encryption and signature.

2
00:00:14.200 --> 00:00:17.700
And we understood why they are correct and

3
00:00:17.700 --> 00:00:17.800
 secure.

4
00:00:18.700 --> 00:00:21.300
However, we cannot choose This Plane versions

5
00:00:21.300 --> 00:00:24.100
 directly in reroute applications.

6
00:00:24.800 --> 00:00:27.700
As we have seen in the last video for instance

7
00:00:27.700 --> 00:00:30.400
 plane RSA signature suffers from

8
00:00:30.400 --> 00:00:31.700
 several vulnerabilities.

9
00:00:33.400 --> 00:00:36.100
In this video, we will see how we move from

10
00:00:36.100 --> 00:00:39.700
 a plane RSA algorithms to more practical and

11
00:00:39.700 --> 00:00:42.700
 secure versions that become the

12
00:00:42.700 --> 00:00:44.400
 RSS standards.

13
00:00:45.200 --> 00:00:48.500
We'll start by looking at RSA encryption standard then

14
00:00:48.500 --> 00:00:51.000
 we will cover RSA signature standard.

15
00:00:53.300 --> 00:00:56.600
First what are the limitations of plane RC encryptions?

16
00:00:56.600 --> 00:00:59.300
 The first limitation is the fact

17
00:00:59.300 --> 00:01:02.900
 that with plane RSA the input to

18
00:01:02.900 --> 00:01:05.600
 encrypt the x is an integer module

19
00:01:05.600 --> 00:01:08.800
 n but in real world applications, the

20
00:01:08.800 --> 00:01:11.400
 messages can be anything. It's not

21
00:01:11.400 --> 00:01:13.800
 necessarily an integer module way.

22
00:01:14.700 --> 00:01:17.500
Next limitations are more religious security.

23
00:01:17.500 --> 00:01:20.400
 Let me cover the first limitation first. The

24
00:01:20.400 --> 00:01:24.000
 first is due to what we call the homomorphic

25
00:01:23.500 --> 00:01:25.500
 property of RSA.

26
00:01:26.500 --> 00:01:28.900
the moving property means that

27
00:01:30.200 --> 00:01:32.300
by having two ciphertexts

28
00:01:32.900 --> 00:01:35.500
of two plain texts x and x

29
00:01:35.500 --> 00:01:39.400
 Prime the attacker is able to apply some

30
00:01:39.400 --> 00:01:42.900
 processing on the ciphertext some operation

31
00:01:42.900 --> 00:01:43.700
 of the ciphertext.

32
00:01:44.400 --> 00:01:47.600
And that operation will be translated on the plaintext.

33
00:01:48.700 --> 00:01:51.400
So for RSA encryption, we have

34
00:01:51.400 --> 00:01:54.500
 two separate X Y and Y Prime by multiplying them

35
00:01:54.500 --> 00:01:58.800
 the up the attacker obtains ciphertext corresponding

36
00:01:57.800 --> 00:02:00.500
 to the product

37
00:02:00.500 --> 00:02:02.200
 X and X Prime.

38
00:02:02.400 --> 00:02:05.900
So this is in some situation you heard

39
00:02:05.900 --> 00:02:08.100
 probably about homomorphic encryption. It's

40
00:02:08.100 --> 00:02:12.000
 very useful, but in general encryption scheme

41
00:02:11.300 --> 00:02:14.600
 having such property can be dangerous in

42
00:02:14.600 --> 00:02:15.900
 some use cases.

43
00:02:16.900 --> 00:02:20.300
The second security limitation is related

44
00:02:19.300 --> 00:02:21.600
 to CPA security.

45
00:02:23.100 --> 00:02:26.800
So security is an ocean of security that we expect

46
00:02:26.800 --> 00:02:29.300
 encryption schemes to be

47
00:02:29.300 --> 00:02:30.600
 CPA secure.

48
00:02:31.600 --> 00:02:34.500
So let me maybe explain first. What

49
00:02:34.500 --> 00:02:37.700
 is this CPA security? So it's basically sort

50
00:02:37.700 --> 00:02:39.400
 of a game or challenge that we

51
00:02:40.400 --> 00:02:43.800
make an attacker do and if

52
00:02:43.800 --> 00:02:46.800
 the attacker succeeds in this challenge, then

53
00:02:46.800 --> 00:02:49.800
 we know that the encryption scheme that we used is

54
00:02:49.800 --> 00:02:51.600
 not a CPA secure.

55
00:02:52.200 --> 00:02:55.200
So in CPA security channel, the attacker gets

56
00:02:55.200 --> 00:02:58.300
 to choose two different plain text messages to be

57
00:02:58.300 --> 00:02:58.800
 encrypted.

58
00:02:59.800 --> 00:03:03.100
And then he receives one of them encrypted and

59
00:03:02.100 --> 00:03:05.000
 he needs to guess which one it is.

60
00:03:06.500 --> 00:03:09.300
The attacker can do that with probability significantly higher than

61
00:03:09.300 --> 00:03:12.500
 one half which is just random guessing we say

62
00:03:12.500 --> 00:03:15.300
 that the encryption system is not cpsq.

63
00:03:15.800 --> 00:03:19.000
Because plane RSA encryption is deterministic.

64
00:03:20.300 --> 00:03:23.600
Because it's also public key, which means that everybody including the

65
00:03:23.600 --> 00:03:26.700
 attacker knows the public key and is able to encrypt messages.

66
00:03:26.700 --> 00:03:30.100
 We need the CPA game

67
00:03:29.100 --> 00:03:33.100
 or challenge against playing RSA

68
00:03:32.100 --> 00:03:33.600
 is trivial.

69
00:03:34.500 --> 00:03:37.400
The flu will be as follows. Okay, so

70
00:03:37.400 --> 00:03:41.000
 the attacker chooses to distinct plain

71
00:03:40.100 --> 00:03:44.200
 text messages. Let's say A and

72
00:03:43.200 --> 00:03:46.200
 B and submits them to the Challenger.

73
00:03:46.800 --> 00:03:49.600
And then he receives an encrypted ciphertext

74
00:03:49.600 --> 00:03:51.700
 see from their Challenger.

75
00:03:52.300 --> 00:03:55.900
And what he can do using these I mean

76
00:03:55.900 --> 00:03:59.600
 using the public key, which is known he encrypts.

77
00:04:00.500 --> 00:04:02.400
The original plain text A and B.

78
00:04:02.900 --> 00:04:05.200
To obtain two separatex and he checks which one

79
00:04:05.200 --> 00:04:08.400
 is equal to the ciprotec that he

80
00:04:08.400 --> 00:04:11.400
 received from the Challenger and because the encryption

81
00:04:11.400 --> 00:04:14.400
 scheme is deterministic then one of them should match.

82
00:04:16.100 --> 00:04:19.800
So to make RSA secure against such

83
00:04:19.800 --> 00:04:23.400
 attacks, we need to introduce some Randomness

84
00:04:22.400 --> 00:04:26.700
 in the encryption mechanism, and

85
00:04:25.700 --> 00:04:28.400
 that's what we'll see in the

86
00:04:28.400 --> 00:04:28.900
 next slide.

87
00:04:31.400 --> 00:04:35.300
Okay, this is the RSA encryption Standard

88
00:04:34.300 --> 00:04:38.400
 pkcs 1 and

89
00:04:37.400 --> 00:04:41.400
 it is the version 1.5. There

90
00:04:40.400 --> 00:04:44.800
 are other versions of the encryption

91
00:04:43.800 --> 00:04:46.600
 if the RC

92
00:04:46.600 --> 00:04:50.400
 encryption standard, but I found for

93
00:04:50.400 --> 00:04:53.900
 educational purpose that looking at this version is

94
00:04:53.900 --> 00:04:56.400
 interesting and the other

95
00:04:56.400 --> 00:04:59.400
 reference are publicly available. So if

96
00:04:59.400 --> 00:05:01.200
 you are interested to look at

97
00:05:02.400 --> 00:05:05.400
The evolution of those versions and what are

98
00:05:05.400 --> 00:05:08.600
 the changes? You can look at that on Internet

99
00:05:08.600 --> 00:05:11.800
 by just Googling a PCS? Okay, so

100
00:05:11.800 --> 00:05:14.500
 I'll pkcs works first. We have

101
00:05:14.500 --> 00:05:17.500
 PCS version 1.5. We have

102
00:05:17.500 --> 00:05:21.300
 a modulus of our RSA algorithm, which

103
00:05:20.300 --> 00:05:23.600
 is n and that modulus is

104
00:05:23.600 --> 00:05:26.300
 of length K bytes.

105
00:05:27.300 --> 00:05:30.800
With this I say encryption a standard we

106
00:05:30.800 --> 00:05:34.200
 can encrypt any message of length

107
00:05:33.200 --> 00:05:36.600
 at most K minus 11

108
00:05:36.600 --> 00:05:39.400
 bytes. So we see that there will

109
00:05:39.400 --> 00:05:42.300
 be some 11 bytes that are dedicated to

110
00:05:42.300 --> 00:05:42.600
 other.

111
00:05:43.800 --> 00:05:46.400
Information and K minus 11

112
00:05:46.400 --> 00:05:49.500
 will be at most are dedicated for

113
00:05:49.500 --> 00:05:50.400
 the message.

114
00:05:51.200 --> 00:05:54.400
Okay, so for the encryption processes as follows

115
00:05:54.400 --> 00:05:57.600
 first, we generate episode random string.

116
00:05:58.600 --> 00:06:01.900
Called PS such that the concussion concatenation

117
00:06:01.900 --> 00:06:04.400
 of PS and the bytes of

118
00:06:04.400 --> 00:06:08.200
 the message is of length k-3

119
00:06:07.200 --> 00:06:08.600
 bytes.

120
00:06:09.500 --> 00:06:12.700
So the PS is at least 8 bytes if

121
00:06:12.700 --> 00:06:15.200
 the the message fits in

122
00:06:15.200 --> 00:06:18.400
 K minus 11 bytes exactly. Then the PS is

123
00:06:18.400 --> 00:06:21.900
 8 bytes if it is less than

124
00:06:21.900 --> 00:06:24.800
 the PS will have a more additional

125
00:06:24.800 --> 00:06:25.600
 by.

126
00:06:27.500 --> 00:06:30.600
Then we construct a string of length

127
00:06:30.600 --> 00:06:33.200
 exactly kbites. This string is

128
00:06:33.200 --> 00:06:36.500
 as follows. We first byte is zero zero then the

129
00:06:36.500 --> 00:06:39.500
 second is 02 then we have the bytes of

130
00:06:39.500 --> 00:06:40.500
 PS.

131
00:06:41.200 --> 00:06:44.000
Then we have a null byte 0 0.

132
00:06:44.600 --> 00:06:48.700
and then we have the bytes of the plaintext

133
00:06:47.700 --> 00:06:50.700
 and this byte string

134
00:06:50.700 --> 00:06:53.200
 is exactly of land Key by so

135
00:06:53.200 --> 00:06:56.500
 we can convert it as an integer module n

136
00:06:57.300 --> 00:07:01.200
we compute the plane RSA encryption that

137
00:07:00.200 --> 00:07:03.000
 we have seen in the previous videos.

138
00:07:04.200 --> 00:07:07.400
We convert then the result into a string

139
00:07:07.400 --> 00:07:08.600
 of K bytes.

140
00:07:09.700 --> 00:07:13.300
Okay. So with this RSA version,

141
00:07:12.300 --> 00:07:15.400
 we fixed all

142
00:07:15.400 --> 00:07:19.000
 the limitations that we have seen previously. So

143
00:07:18.400 --> 00:07:21.800
 first we can now encrypt any

144
00:07:21.800 --> 00:07:25.100
 data as log as it is represented by.

145
00:07:26.100 --> 00:07:29.400
K minus 11 it can be represented as

146
00:07:29.400 --> 00:07:31.100
 a k minus 11 bytes.

147
00:07:32.100 --> 00:07:37.400
We don't have any more the homomorphism property.

148
00:07:38.900 --> 00:07:41.500
You can this is can be a good exercise. You

149
00:07:41.500 --> 00:07:44.300
 can try to see why we don't have that.

150
00:07:45.300 --> 00:07:48.600
And we introduced some Randomness in the process

151
00:07:48.600 --> 00:07:52.200
 by through this string PS.

152
00:07:51.200 --> 00:07:55.000
 So the attacker cannot

153
00:07:57.200 --> 00:08:00.500
trivial manner The ncpa Challenge and

154
00:08:00.500 --> 00:08:04.100
 this algorithm is CPA secure.

155
00:08:06.100 --> 00:08:08.100
Okay, this is the process of the decryption.

156
00:08:08.800 --> 00:08:11.400
So we receive a ciphertext.

157
00:08:12.200 --> 00:08:15.800
When we receive it, we need to convert it into an integer. We expect

158
00:08:15.800 --> 00:08:18.500
 that integer to be greater than the model to

159
00:08:18.500 --> 00:08:21.100
 be a smaller than the modulus if it is greater than

160
00:08:21.100 --> 00:08:25.000
 the modulus then we should reject this ciphertext. We

161
00:08:24.100 --> 00:08:26.400
 know that something wrong happened.

162
00:08:27.700 --> 00:08:30.200
We perform plane RC decryption on that

163
00:08:30.200 --> 00:08:33.600
 integer and we obtain another

164
00:08:33.600 --> 00:08:34.400
 integer.

165
00:08:35.200 --> 00:08:38.500
The output it integer is then converted back

166
00:08:38.500 --> 00:08:40.300
 as a byte string?

167
00:08:41.300 --> 00:08:44.500
And if everything was fine, there was

168
00:08:44.500 --> 00:08:47.300
 no error or no malicious modification of the

169
00:08:47.300 --> 00:08:50.300
 ciphertext. Then the string that

170
00:08:50.300 --> 00:08:54.600
 you obtained should have the expected format with zero

171
00:08:53.600 --> 00:08:56.300
 zero zero first and

172
00:08:56.300 --> 00:08:59.700
 zero two Etc and bytes of PS. So

173
00:08:59.700 --> 00:09:02.900
 if it is not of this format, we should discard the

174
00:09:02.900 --> 00:09:05.400
 we should reject the self text.

175
00:09:05.400 --> 00:09:08.800
 If this is this format, we extract

176
00:09:08.800 --> 00:09:11.700
 the bytes of M and that

177
00:09:11.700 --> 00:09:13.800
 will be our original plaintext.

178
00:09:17.200 --> 00:09:21.600
Is now switch to the RSA signature standard first.

179
00:09:20.600 --> 00:09:23.600
 Let's have a reminder

180
00:09:23.600 --> 00:09:26.800
 of the security concerns of

181
00:09:26.800 --> 00:09:30.200
 playing RSA signature.

182
00:09:29.200 --> 00:09:32.400
 So we have covered that in the previous video

183
00:09:32.400 --> 00:09:35.600
 feel free to stop the video and

184
00:09:35.600 --> 00:09:39.100
 look at the details of the security concerns, which

185
00:09:38.100 --> 00:09:41.300
 were mainly the capability of

186
00:09:41.300 --> 00:09:45.100
 the attacker to forge new signatures, or you

187
00:09:44.100 --> 00:09:47.900
 can even return to video 5.1.

188
00:09:47.900 --> 00:09:51.300
 So the previous video and study again

189
00:09:50.300 --> 00:09:53.800
 what what are the security

190
00:09:53.800 --> 00:09:54.500
 Concepts?

191
00:09:56.600 --> 00:10:00.000
We saw in the previous video that

192
00:09:59.800 --> 00:10:02.500
 we can use the hash and

193
00:10:02.500 --> 00:10:05.000
 sign approach to fix the security concerns.

194
00:10:05.700 --> 00:10:09.000
So instead of directly signing the message X

195
00:10:08.700 --> 00:10:11.300
 we hash it first to obtain

196
00:10:11.300 --> 00:10:14.700
 a digest H. And we send the pair X and

197
00:10:14.700 --> 00:10:17.300
 S to the receiver and the

198
00:10:17.300 --> 00:10:20.400
 receiver first has to recompute the digest

199
00:10:20.400 --> 00:10:24.000
 H from X before verifying that S and

200
00:10:23.100 --> 00:10:26.700
 H is a valid version and this

201
00:10:26.700 --> 00:10:29.500
 Action Sign approach fix the

202
00:10:29.500 --> 00:10:33.100
 forgially vulnerabilities that we

203
00:10:32.100 --> 00:10:34.500
 discussed previously.

204
00:10:37.300 --> 00:10:40.900
Okay, let's see in detail. Now the RSA signature

205
00:10:40.900 --> 00:10:43.700
 standard that implements the hash and

206
00:10:43.700 --> 00:10:46.500
 sign approach similar to encryption will be

207
00:10:46.500 --> 00:10:50.100
 looking at the version 1.5 of

208
00:10:49.100 --> 00:10:53.000
 the pkcs one. So

209
00:10:52.900 --> 00:10:55.600
 we start by assuming

210
00:10:55.600 --> 00:10:58.400
 that we have modulus and modulus n of

211
00:10:58.400 --> 00:10:59.300
 K bytes.

212
00:11:00.100 --> 00:11:04.000
The first separation is to Hash the message to obtain a

213
00:11:03.300 --> 00:11:06.500
 message digest obviously here.

214
00:11:06.500 --> 00:11:09.900
 We have to use a secure cryptographic hash

215
00:11:09.900 --> 00:11:12.800
 function for example, lush256 or

216
00:11:12.800 --> 00:11:15.200
 share 3 then we encode the

217
00:11:15.200 --> 00:11:18.300
 message digest and the identifier of

218
00:11:18.300 --> 00:11:21.200
 the hash in the field D. So we can

219
00:11:21.200 --> 00:11:25.200
 imagine that the first byte of of D

220
00:11:24.200 --> 00:11:27.700
 is for the identifier of the

221
00:11:27.700 --> 00:11:30.200
 hash algorithm. For example, we can

222
00:11:30.200 --> 00:11:34.800
 use any Convention of identifiers.

223
00:11:33.800 --> 00:11:36.300
 So for example, zero one

224
00:11:36.300 --> 00:11:36.600
 is for

225
00:11:37.800 --> 00:11:41.700
shawan02 is Porsche 256

226
00:11:41.700 --> 00:11:44.400
 with the first length Etc.

227
00:11:45.700 --> 00:11:48.700
But anyway, the message Ledges and this identifier go

228
00:11:48.700 --> 00:11:49.800
 into the filthy.

229
00:11:50.400 --> 00:11:53.800
Then we pad with 0 byte to

230
00:11:53.800 --> 00:11:56.400
 the left and as many bytes

231
00:11:56.400 --> 00:11:59.800
 FF to reach K minus

232
00:11:59.800 --> 00:12:02.600
 2 bytes, then we add the

233
00:12:02.600 --> 00:12:05.500
 bytes 0 1 and

234
00:12:05.500 --> 00:12:06.800
 the byte 0 0.

235
00:12:07.300 --> 00:12:11.000
So the format is actually very similar to the format that

236
00:12:10.500 --> 00:12:14.300
 we had for the encryption the difference

237
00:12:14.300 --> 00:12:17.300
 is that for the encryption the we have a random

238
00:12:17.300 --> 00:12:20.600
 a bit string PS. Now this random bit

239
00:12:20.600 --> 00:12:23.200
 string is just a string of

240
00:12:23.200 --> 00:12:23.700
 FF.

241
00:12:24.400 --> 00:12:28.200
Then this now string of

242
00:12:28.200 --> 00:12:31.600
 length Okay bytes is converted as an integer module

243
00:12:31.600 --> 00:12:34.900
 n we compute the plane RSA signature

244
00:12:34.900 --> 00:12:37.500
 on that integer to obtain another

245
00:12:37.500 --> 00:12:40.200
 integer the result.

246
00:12:41.100 --> 00:12:44.100
That result is converted back as a string of

247
00:12:44.100 --> 00:12:45.200
 kbites.

248
00:12:48.900 --> 00:12:51.200
Okay, the verification is as follows.

249
00:12:52.200 --> 00:12:55.600
First we convert the signature into an

250
00:12:55.600 --> 00:12:55.800
 integer.

251
00:12:56.700 --> 00:12:59.300
We rejected if it is greater than

252
00:12:59.300 --> 00:13:00.300
 the modulus.

253
00:13:01.100 --> 00:13:04.600
We perform the plane RSA verification.

254
00:13:05.400 --> 00:13:08.700
On that integer to obtain another integer.

255
00:13:09.600 --> 00:13:12.500
The output it integer is then

256
00:13:12.500 --> 00:13:15.300
 converted as a byte string?

257
00:13:16.300 --> 00:13:19.700
We check that. It has the correct format. So

258
00:13:19.700 --> 00:13:22.600
 with the 0001 then different

259
00:13:22.600 --> 00:13:25.300
 bytes of FF then

260
00:13:25.300 --> 00:13:29.000
 noodle bite, then probably the identifier

261
00:13:28.200 --> 00:13:29.700
 of the hash.

262
00:13:30.800 --> 00:13:33.300
We decode so the D as I

263
00:13:33.300 --> 00:13:36.900
 said with identifier and the bytes of message Digest.

264
00:13:37.700 --> 00:13:40.800
And if the hash algorithm is acceptable then

265
00:13:40.800 --> 00:13:43.100
 we know this is a valid signature.

266
00:13:44.100 --> 00:13:47.900
And we extract the bytes and

267
00:13:47.900 --> 00:13:50.300
 then we hash the

268
00:13:50.300 --> 00:13:53.700
 message and we check that we have the

269
00:13:53.700 --> 00:13:55.200
 matching message.

270
00:13:58.700 --> 00:14:01.700
So we reach the end of our video in

271
00:14:01.700 --> 00:14:04.700
 this video. We covered the RC standards

272
00:14:04.700 --> 00:14:07.400
 for encryption and signature and we also

273
00:14:07.400 --> 00:14:10.400
 discussed. What are the limitations of the

274
00:14:10.400 --> 00:14:13.600
 plane or say encryption signature

275
00:14:13.600 --> 00:14:16.100
 and why it cannot be used.

276
00:14:16.900 --> 00:14:19.500
So with this video we finish

277
00:14:19.500 --> 00:14:23.000
 these section and this video

278
00:14:22.200 --> 00:14:26.000
 is also the last study material.

279
00:14:25.600 --> 00:14:29.800
 So see you in the next section where

280
00:14:28.800 --> 00:14:31.100
 we'll conclude the

281
00:14:31.100 --> 00:14:34.800
 course, we'll review briefly what we have learned

282
00:14:34.800 --> 00:14:37.800
 together and we will discuss

283
00:14:37.800 --> 00:14:41.200
 what are the other topics

284
00:14:40.200 --> 00:14:43.700
 of cryptography that

285
00:14:43.700 --> 00:14:47.200
 now you can look at as

286
00:14:46.200 --> 00:14:50.200
 you acquired good understanding

287
00:14:49.200 --> 00:14:52.800
 of conventional cryptography. So

288
00:14:52.800 --> 00:14:53.800
 see you in the next video.
