WEBVTT - This file was automatically generated by VIMEO

0
00:00:07.100 --> 00:00:10.900
In this video we see in detail the RSA crypto

1
00:00:10.900 --> 00:00:11.100
 system.

2
00:00:11.800 --> 00:00:14.200
RC is probably the most

3
00:00:14.200 --> 00:00:17.100
 popular public key cryptographic algorithm.

4
00:00:18.700 --> 00:00:22.200
RC algorithm provides us with method for public encryption

5
00:00:21.200 --> 00:00:24.700
 and method for digital signature.

6
00:00:24.700 --> 00:00:26.900
 So it's very useful algorithm.

7
00:00:27.500 --> 00:00:30.500
As we did for different element key agreement

8
00:00:30.500 --> 00:00:33.600
 protocol in the previous video will first cover

9
00:00:33.600 --> 00:00:36.700
 the mathematical background. We need to understand the

10
00:00:36.700 --> 00:00:37.300
 algorithm.

11
00:00:38.200 --> 00:00:41.500
Then we'll detail the cryptographic algorithm and how

12
00:00:41.500 --> 00:00:42.200
 we can use it.

13
00:00:44.400 --> 00:00:47.500
Currency was proposed in a publication

14
00:00:47.500 --> 00:00:50.600
 by Ronald reversed addition year

15
00:00:50.600 --> 00:00:52.500
 and learned admin.

16
00:00:53.200 --> 00:00:56.800
And that publication appeared in 1978. So two

17
00:00:56.800 --> 00:00:59.200
 years after the invention of

18
00:00:59.200 --> 00:01:01.600
 public key cryptography by defiant hermit.

19
00:01:02.700 --> 00:01:05.900
And RSA is today the

20
00:01:05.900 --> 00:01:08.600
 oldest public key crypto system that

21
00:01:08.600 --> 00:01:12.100
 is still secure. So between 1976

22
00:01:11.100 --> 00:01:14.900
 when the public key

23
00:01:14.900 --> 00:01:17.500
 cryptography was invented in 1978. They

24
00:01:17.500 --> 00:01:21.100
 were other proposals of encryption systems.

25
00:01:20.100 --> 00:01:23.900
 But all of them were broken or

26
00:01:23.900 --> 00:01:27.600
 were found out with a strong variabilities,

27
00:01:26.600 --> 00:01:29.300
 but RSA is

28
00:01:29.300 --> 00:01:31.900
 today still considered secure.

29
00:01:33.400 --> 00:01:36.600
RC was widely adopted and transformed into several

30
00:01:36.600 --> 00:01:39.600
 standards today. It is used in

31
00:01:39.600 --> 00:01:42.500
 browsers in iot mobile

32
00:01:42.500 --> 00:01:45.500
 applications and in many other systems and

33
00:01:45.500 --> 00:01:46.300
 services.

34
00:01:49.400 --> 00:01:52.400
Okay, so now let's look together at the

35
00:01:52.400 --> 00:01:54.300
 mathematics of RSA.

36
00:01:55.100 --> 00:01:58.800
the next three slides will introduce all the mathematical

37
00:01:58.800 --> 00:02:01.700
 Concepts that we need to understand our say

38
00:02:02.400 --> 00:02:05.900
These concepts are not a very straightforward

39
00:02:05.900 --> 00:02:09.200
 or easy to understand. So please

40
00:02:08.200 --> 00:02:11.200
 take the time to stop the video

41
00:02:11.200 --> 00:02:14.600
 if needed or to watch it

42
00:02:14.600 --> 00:02:17.600
 a few times to to understand

43
00:02:17.600 --> 00:02:18.500
 this Concepts.

44
00:02:20.300 --> 00:02:24.000
We have seen with different element protocol that

45
00:02:23.600 --> 00:02:26.300
 we need to define a prime field

46
00:02:26.300 --> 00:02:29.800
 to Define such field. We choose prime number

47
00:02:29.800 --> 00:02:30.100
 P.

48
00:02:30.900 --> 00:02:34.900
With RSA, we will work modulo a

49
00:02:34.900 --> 00:02:37.700
 number and that is semi Prime.

50
00:02:37.700 --> 00:02:40.600
 So first, what does it need to be surprised?

51
00:02:41.600 --> 00:02:44.600
Semi Prime member is a number that is the product of two

52
00:02:44.600 --> 00:02:45.900
 prime numbers.

53
00:02:46.700 --> 00:02:49.900
So here the N is written as P

54
00:02:49.900 --> 00:02:52.500
 times q and both p and Q are prime

55
00:02:52.500 --> 00:02:52.700
 numbers.

56
00:02:54.100 --> 00:02:57.400
So for example 15 is a semi Prime

57
00:02:57.400 --> 00:02:59.900
 because 15 is written as 3 times 5.

58
00:03:00.700 --> 00:03:02.500
Both 3 and 5 are prime numbers.

59
00:03:03.500 --> 00:03:07.300
While 42 is not the semi Prime because 42

60
00:03:06.300 --> 00:03:09.100
 is written as 2 times

61
00:03:09.100 --> 00:03:12.600
 3 times 7 and the so it's the product of three

62
00:03:12.600 --> 00:03:13.600
 prime numbers.

63
00:03:14.500 --> 00:03:17.800
Like we did with different animal protocol.

64
00:03:17.800 --> 00:03:20.300
 We will work modulo this number.

65
00:03:21.200 --> 00:03:23.900
So we will Define what is called the ring.

66
00:03:24.600 --> 00:03:27.700
So the ring is just the integers module.

67
00:03:28.500 --> 00:03:31.300
This number n so all the integers from 0

68
00:03:31.300 --> 00:03:32.200
 to n minus 1.

69
00:03:33.300 --> 00:03:34.700
For example, is it 15?

70
00:03:35.400 --> 00:03:38.600
Corresponds to all the integers between 0 and

71
00:03:38.600 --> 00:03:41.200
 14 and we would like

72
00:03:41.200 --> 00:03:44.700
 to have arithmetic module this number

73
00:03:44.700 --> 00:03:47.400
 n so we need operations such as

74
00:03:47.400 --> 00:03:50.300
 addition subtraction, which

75
00:03:50.300 --> 00:03:53.800
 is the inverse of addition, but we

76
00:03:53.800 --> 00:03:55.000
 also need multiplication.

77
00:03:55.800 --> 00:03:59.000
And the inverse of multiplication is usually the

78
00:03:58.500 --> 00:04:01.100
 operation called inversion when we

79
00:04:01.100 --> 00:04:06.300
 worked on a prime field all the numbers support

80
00:04:04.300 --> 00:04:08.000
 the inversion module

81
00:04:07.700 --> 00:04:10.300
 composite number or semi prime

82
00:04:10.300 --> 00:04:14.000
 number like here for RSA. We don't always support

83
00:04:13.200 --> 00:04:16.500
 inversion. Not all the numbers can

84
00:04:16.500 --> 00:04:17.600
 support inversion.

85
00:04:18.700 --> 00:04:21.900
So we need to identify a

86
00:04:21.900 --> 00:04:22.400
 subset.

87
00:04:23.200 --> 00:04:23.900
from The Ring

88
00:04:24.600 --> 00:04:26.700
subset of the invertible

89
00:04:27.400 --> 00:04:31.400
elements. So let's first review formerly what

90
00:04:31.400 --> 00:04:32.800
 this mean to be invertible.

91
00:04:33.600 --> 00:04:36.700
So number is invertible number

92
00:04:36.700 --> 00:04:39.800
 of the ring is invertible if

93
00:04:39.800 --> 00:04:42.200
 there exists another value of the

94
00:04:42.200 --> 00:04:44.700
 Ring such that the product.

95
00:04:45.600 --> 00:04:48.500
Their product is equal to one module 1

96
00:04:48.500 --> 00:04:51.000
 so for example in z15.

97
00:04:52.200 --> 00:04:53.600
4 is invertible

98
00:04:54.200 --> 00:04:57.000
because 4 times 4 module 15

99
00:04:57.600 --> 00:05:00.200
is equal to 16 module of 15, which is

100
00:05:00.200 --> 00:05:02.100
 equal to 1 while 6

101
00:05:03.300 --> 00:05:06.500
in the same ring inside 15 is not invertible. You can

102
00:05:06.500 --> 00:05:09.400
 stop the video and try yourself to multiply

103
00:05:09.400 --> 00:05:12.300
 6 by all the integers from 0 to

104
00:05:12.300 --> 00:05:15.300
 14. But of course 0 and 1 they cannot be

105
00:05:15.300 --> 00:05:18.300
 good candidates, but you can start from 2

106
00:05:18.300 --> 00:05:21.900
 to 14 and you will find yourself that six

107
00:05:21.900 --> 00:05:24.500
 multiplied by all of these numbers is

108
00:05:24.500 --> 00:05:25.900
 always different from one.

109
00:05:27.500 --> 00:05:30.500
And the reason we kind of expected from

110
00:05:30.500 --> 00:05:33.700
 the mathematics because six is

111
00:05:33.700 --> 00:05:36.500
 multiple of three so six cannot be

112
00:05:36.500 --> 00:05:39.500
 invertible why this statement actually we

113
00:05:39.500 --> 00:05:39.900
 know that

114
00:05:40.800 --> 00:05:43.800
this composite number that is defining the

115
00:05:43.800 --> 00:05:46.000
 ring is the product as we said

116
00:05:46.200 --> 00:05:49.400
 of p and Q. So 15 is the product of 3 and

117
00:05:49.400 --> 00:05:49.500
 5.

118
00:05:50.500 --> 00:05:53.100
So we know that to be invertible. You should

119
00:05:53.100 --> 00:05:56.000
 not be multiple of neither three or five.

120
00:05:57.300 --> 00:06:01.100
And 6 is a multiple of 3, so 6 is

121
00:06:00.100 --> 00:06:02.000
 not invertible.

122
00:06:03.200 --> 00:06:06.600
We know this result from the mathematic. That's why

123
00:06:06.600 --> 00:06:09.600
 when we worked with prime fields. We didn't

124
00:06:09.600 --> 00:06:12.500
 have this problem of invertible elements.

125
00:06:12.500 --> 00:06:14.900
 All the elements were invertible.

126
00:06:16.400 --> 00:06:19.700
Because the p of the Prime field does

127
00:06:19.700 --> 00:06:22.600
 not have any factors that that's exactly definition of

128
00:06:22.600 --> 00:06:25.200
 prime number. That's why all the

129
00:06:25.200 --> 00:06:28.000
 elements from 0 to P. Minus

130
00:06:28.200 --> 00:06:31.900
 1 if we are working module P. They don't share

131
00:06:31.900 --> 00:06:34.800
 any factors with B. So

132
00:06:34.800 --> 00:06:37.900
 that's why they are all invertible while

133
00:06:37.900 --> 00:06:40.300
 for working module in

134
00:06:40.300 --> 00:06:43.400
 we need to remove for this card

135
00:06:43.400 --> 00:06:46.300
 the elements that are multiples of

136
00:06:46.300 --> 00:06:47.500
 P or Q.

137
00:06:48.200 --> 00:06:52.600
So we will Define formally this subset. This

138
00:06:51.600 --> 00:06:54.900
 subset is called the multiplicative group

139
00:06:54.900 --> 00:06:57.600
 and the notation is set and

140
00:06:57.600 --> 00:06:58.500
 star like here.

141
00:06:59.200 --> 00:07:02.500
So this Z and star it contains all the

142
00:07:02.500 --> 00:07:03.300
 invertible elements.

143
00:07:04.500 --> 00:07:07.300
Which means all the elements that are not multiples of

144
00:07:07.300 --> 00:07:10.900
 P or Q. We can Define that

145
00:07:10.900 --> 00:07:13.400
 using the gcd function. So this is

146
00:07:13.400 --> 00:07:15.100
 the greatest common divisor.

147
00:07:15.600 --> 00:07:19.200
so if an element has gcd

148
00:07:18.200 --> 00:07:22.200
 equal to 1 with another element means

149
00:07:21.200 --> 00:07:24.800
 they don't have any common factor greater

150
00:07:24.800 --> 00:07:25.500
 than 1

151
00:07:26.100 --> 00:07:29.500
so X here is cannot be multiple of b or

152
00:07:29.500 --> 00:07:30.800
 multiple of Q.

153
00:07:32.400 --> 00:07:35.300
So for example, let's go back to Z 15.

154
00:07:36.200 --> 00:07:40.100
And Z 15 let's try to remove all the multiples

155
00:07:39.100 --> 00:07:42.700
 of three and five. So

156
00:07:42.700 --> 00:07:45.400
 zero is of course multiple of them.

157
00:07:46.300 --> 00:07:47.800
Free is multiple of 3.

158
00:07:48.900 --> 00:07:51.600
5 is multiple of 5 6 is

159
00:07:51.600 --> 00:07:53.700
 multiple of 3 9 is multiple of 3.

160
00:07:54.800 --> 00:07:58.100
10 is multiple of 5 12

161
00:07:57.100 --> 00:07:59.100
 is multiple of 3.

162
00:07:59.900 --> 00:08:03.200
So all these are numbers that

163
00:08:02.200 --> 00:08:05.600
 are not invertible all the

164
00:08:05.600 --> 00:08:09.500
 others that we write here are invertible

165
00:08:08.500 --> 00:08:10.300
 elements.

166
00:08:10.900 --> 00:08:14.300
So whenever we need to use the

167
00:08:13.300 --> 00:08:16.300
 inversion operation, we have

168
00:08:16.300 --> 00:08:19.600
 to work in this multiplicative group

169
00:08:19.600 --> 00:08:23.000
 that end star and not in ZN.

170
00:08:24.300 --> 00:08:27.900
Let's now summarize the arithmetic operations

171
00:08:27.900 --> 00:08:30.300
 that we can have in the ring of

172
00:08:30.300 --> 00:08:31.800
 residuous module n

173
00:08:32.400 --> 00:08:35.700
So there are some operations arithmetic operations

174
00:08:35.700 --> 00:08:39.100
 which are very efficient to apply. Even when

175
00:08:38.100 --> 00:08:42.300
 the modulo N is large

176
00:08:41.300 --> 00:08:44.500
 enough so large it can

177
00:08:44.500 --> 00:08:48.100
 be like thousands of bits or even larger. These operations

178
00:08:47.100 --> 00:08:49.100
 are still very efficient.

179
00:08:50.100 --> 00:08:53.400
So we have the addition the addition is just

180
00:08:55.100 --> 00:08:58.600
the regular addition followed by a reduction module

181
00:08:58.600 --> 00:08:58.800
 n

182
00:08:59.400 --> 00:09:03.300
so for example 9 plus 13 is equal

183
00:09:02.300 --> 00:09:05.800
 to 22 or 0

184
00:09:05.800 --> 00:09:07.300
 15 that's equal to 7.

185
00:09:08.600 --> 00:09:12.100
We also have the multiplication which is

186
00:09:11.100 --> 00:09:14.500
 also a regular multiplication for rule by

187
00:09:14.500 --> 00:09:17.900
 reduction module n for instance 9 times

188
00:09:17.900 --> 00:09:21.400
 13 is equal to 100

189
00:09:20.400 --> 00:09:23.200
 17 that we

190
00:09:23.200 --> 00:09:26.400
 reduce module 15 and 117 is

191
00:09:26.400 --> 00:09:29.700
 can be written as 12 plus 7 times

192
00:09:29.700 --> 00:09:33.000
 15. That's the largest multiple of

193
00:09:32.800 --> 00:09:36.900
 15 that is close to 117. So

194
00:09:36.900 --> 00:09:39.500
 the reduction gives

195
00:09:39.500 --> 00:09:42.300
 exactly 12. So 9 times 13 is equal

196
00:09:42.300 --> 00:09:44.400
 to 12 in Z50.

197
00:09:45.600 --> 00:09:48.200
And as we have seen in the

198
00:09:48.200 --> 00:09:51.900
 previous slide we can do the inverse operation on

199
00:09:51.900 --> 00:09:54.400
 certain Elements which are invertible.

200
00:09:55.200 --> 00:09:58.800
So we inset 15 we have exactly 8

201
00:09:58.800 --> 00:10:01.800
 Elements which are invertible for instance.

202
00:10:01.800 --> 00:10:04.700
 Four four. We have seen it's invertible

203
00:10:04.700 --> 00:10:07.700
 and it's inverse is itself because

204
00:10:07.700 --> 00:10:11.100
 4 times 4 module 15

205
00:10:10.100 --> 00:10:13.900
 is equal to of course 16 module

206
00:10:13.900 --> 00:10:17.400
 of 10 is equal to 1 so for is the

207
00:10:17.400 --> 00:10:20.300
 inverse of 4 in Z 15 star.

208
00:10:21.800 --> 00:10:24.700
And 7 for example is

209
00:10:24.700 --> 00:10:28.400
 also invertible and it's inverse

210
00:10:27.400 --> 00:10:30.500
 is 13 because 7 times 13 is

211
00:10:30.500 --> 00:10:33.300
 equal to 1 as well, as we

212
00:10:33.300 --> 00:10:37.000
 Define multiplication. We can also Define power or

213
00:10:36.400 --> 00:10:39.400
 exponentiation. So for

214
00:10:39.400 --> 00:10:42.700
 an element X we can raise it to exponent

215
00:10:42.700 --> 00:10:45.600
 e and then we reduce module

216
00:10:45.600 --> 00:10:48.400
 n so seven, for example the cube

217
00:10:48.400 --> 00:10:51.900
 of seven in Z 15 is

218
00:10:51.900 --> 00:10:54.800
 equal to 300 43 module

219
00:10:54.800 --> 00:10:55.900
 15, which

220
00:10:57.300 --> 00:11:01.400
Is written as 13 plus 22 times 15. So module

221
00:11:00.400 --> 00:11:03.200
 of 15 is equal to 30.

222
00:11:04.100 --> 00:11:07.500
All these operations can be computed very efficiently.

223
00:11:08.300 --> 00:11:12.700
And there are some operation that is competitionally

224
00:11:11.700 --> 00:11:14.500
 hard to apply when n is

225
00:11:14.500 --> 00:11:17.600
 big enough. That's the inverse of

226
00:11:17.600 --> 00:11:18.600
 the power.

227
00:11:19.400 --> 00:11:22.800
So given an element Y,

228
00:11:22.800 --> 00:11:26.000
 which is X raised to

229
00:11:25.300 --> 00:11:29.700
 power e finding X from X

230
00:11:28.700 --> 00:11:31.300
 power e which is

231
00:11:31.300 --> 00:11:34.400
 called finding the eth root for E, which

232
00:11:34.400 --> 00:11:37.500
 is public is computationally hard operation.

233
00:11:38.500 --> 00:11:41.500
And as you know for public key cryptography, we

234
00:11:41.500 --> 00:11:44.500
 always need an operation that is easy

235
00:11:44.500 --> 00:11:48.000
 to apply and hard to inverse. That's

236
00:11:47.300 --> 00:11:50.300
 the one-way function and the power and

237
00:11:50.300 --> 00:11:53.900
 the finding e throughout will be the one-way function

238
00:11:53.900 --> 00:11:55.600
 that we need for RSA.

239
00:11:56.900 --> 00:11:59.800
We need one more mathematical concept

240
00:11:59.800 --> 00:12:02.400
 before looking at the details of

241
00:12:02.400 --> 00:12:06.300
 our secret to system. That's the earlier tuition

242
00:12:05.300 --> 00:12:06.500
 function.

243
00:12:07.500 --> 00:12:10.800
The older potion function is just the

244
00:12:10.800 --> 00:12:13.900
 number of invertible elements module M

245
00:12:13.900 --> 00:12:17.100
 and the mathematics the gigas

246
00:12:16.100 --> 00:12:20.300
 of formula to compute this alert

247
00:12:19.300 --> 00:12:22.800
 ocean function. We denoted by

248
00:12:22.800 --> 00:12:25.300
 the Greek letter Phi so

249
00:12:25.300 --> 00:12:26.200
 Phi of n

250
00:12:26.900 --> 00:12:30.100
The mathematics tell us that for semi

251
00:12:29.100 --> 00:12:32.300
 Prime n so which is written as

252
00:12:32.300 --> 00:12:36.100
 P times Q the file then is p

253
00:12:35.100 --> 00:12:37.700
 minus 1 times Q minus 1.

254
00:12:38.600 --> 00:12:41.500
We can verify it for our example of

255
00:12:41.500 --> 00:12:42.700
 n equal to 15.

256
00:12:43.300 --> 00:12:46.200
So this is the this the set of

257
00:12:46.200 --> 00:12:49.400
 invertible elements z15 star.

258
00:12:50.300 --> 00:12:51.700
It contains eight elements.

259
00:12:52.500 --> 00:12:55.200
And we can check that the formulas correct.

260
00:12:56.100 --> 00:12:59.100
For 15 the p is equal

261
00:12:59.100 --> 00:13:02.800
 to 3 and the Q is equal to 5. So 5 of

262
00:13:02.800 --> 00:13:05.400
 15 is equal to 3 minus 1 times

263
00:13:05.400 --> 00:13:08.700
 5 minus 1 and that's eight. So

264
00:13:08.700 --> 00:13:11.600
 the formula is correct and

265
00:13:11.600 --> 00:13:14.200
 it is correct. Not only for n equal

266
00:13:14.200 --> 00:13:17.100
 15. It's correct for any assembly Prime

267
00:13:17.100 --> 00:13:17.500
 and

268
00:13:19.100 --> 00:13:22.600
another important result about earlier tuition

269
00:13:22.600 --> 00:13:26.200
 function is the following for every invertible

270
00:13:25.200 --> 00:13:28.400
 element or any element of the

271
00:13:28.400 --> 00:13:32.000
 zden star when it is raised to

272
00:13:33.500 --> 00:13:33.800
fire then

273
00:13:34.400 --> 00:13:37.300
it is equal to 1 actually we can verify it

274
00:13:37.300 --> 00:13:40.700
 in our example of n equal to 15. Maybe

275
00:13:40.700 --> 00:13:43.400
 the easiest to verify is for two two power

276
00:13:43.400 --> 00:13:46.800
 eight module 15. That's 256 module

277
00:13:46.800 --> 00:13:49.400
 15 and 256 can be written as

278
00:13:49.400 --> 00:13:52.700
 one plus 255 which is multiple of

279
00:13:52.700 --> 00:13:55.800
 15. So the result is one as expected

280
00:13:55.800 --> 00:13:57.200
 by the math.

281
00:13:57.900 --> 00:14:00.500
And you can also do it on 13.

282
00:14:00.500 --> 00:14:03.400
 Of course. We cannot like do it manually, but

283
00:14:03.400 --> 00:14:06.900
 you can check or using the calculator that the result

284
00:14:06.900 --> 00:14:09.600
 of 13 Power 8 module 15

285
00:14:09.600 --> 00:14:12.900
 is exactly 1. This is very important result

286
00:14:12.900 --> 00:14:15.500
 that every invertible element when it's

287
00:14:15.500 --> 00:14:18.300
 raised to the fire van is equal to 1

288
00:14:18.300 --> 00:14:21.900
 and we will use this result to understand the

289
00:14:21.900 --> 00:14:23.700
 mathematics of RSA.

290
00:14:26.200 --> 00:14:30.500
Okay, a reminder of the scheme of

291
00:14:30.500 --> 00:14:32.200
 public encryption.

292
00:14:32.900 --> 00:14:35.400
So we have two parties a decent

293
00:14:35.400 --> 00:14:35.500
 pop.

294
00:14:36.100 --> 00:14:40.300
And there is a generator that provides Bob with

295
00:14:39.300 --> 00:14:43.000
 a pair of public key that

296
00:14:42.500 --> 00:14:46.000
 he can share with everyone and

297
00:14:45.900 --> 00:14:48.200
 a private key or secret key

298
00:14:48.200 --> 00:14:49.100
 SK here.

299
00:14:50.100 --> 00:14:53.500
So Alice will use the public key of Pop

300
00:14:53.500 --> 00:14:55.800
 to encrypt some message X.

301
00:14:56.800 --> 00:14:59.600
That's how she obtains a ciphertext y.

302
00:15:00.200 --> 00:15:04.500
And up uses his secret key to decrypt

303
00:15:03.500 --> 00:15:07.100
 the ciphertext and

304
00:15:06.100 --> 00:15:08.500
 retrieve the plaintext.

305
00:15:09.300 --> 00:15:12.700
And of course the adversary who is intercepting their

306
00:15:12.700 --> 00:15:15.700
 messages is unable to retrieve the plaintext

307
00:15:15.700 --> 00:15:19.000
 from the ciphertext without having

308
00:15:18.600 --> 00:15:20.700
 access to the secret key.

309
00:15:23.500 --> 00:15:24.200
first step

310
00:15:24.800 --> 00:15:27.700
are secure to system is to generate

311
00:15:27.700 --> 00:15:30.700
 public key and the secret key for

312
00:15:30.700 --> 00:15:31.600
 Bob.

313
00:15:32.800 --> 00:15:35.200
So the generator will do it as

314
00:15:35.200 --> 00:15:35.500
 follows.

315
00:15:36.500 --> 00:15:39.900
It will pick two prime numbers p and

316
00:15:39.900 --> 00:15:40.000
 Q.

317
00:15:40.800 --> 00:15:44.000
And compute their multiplication as an

318
00:15:43.900 --> 00:15:46.300
 N is the product of P times Q.

319
00:15:47.300 --> 00:15:51.200
then we as we know the factorization of

320
00:15:50.200 --> 00:15:53.800
 n we can compute the fire

321
00:15:53.800 --> 00:15:54.100
 n

322
00:15:54.700 --> 00:15:57.500
As using the formula that we have seen a

323
00:15:57.500 --> 00:16:00.900
 couple of slides ago, then the generator chooses

324
00:16:00.900 --> 00:16:03.600
 some e which is

325
00:16:03.600 --> 00:16:06.300
 what we call Co Prime with fire event

326
00:16:06.300 --> 00:16:09.300
 Co prime. It just means that the E

327
00:16:09.300 --> 00:16:10.000
 does not have

328
00:16:10.900 --> 00:16:14.000
Any other diseaser with fire van except

329
00:16:13.000 --> 00:16:14.000
 one?

330
00:16:15.300 --> 00:16:17.900
This is a very important you'll see why.

331
00:16:19.300 --> 00:16:19.700
because

332
00:16:20.600 --> 00:16:23.700
the E will be the the end

333
00:16:23.700 --> 00:16:25.800
 end will be the public key of Bob.

334
00:16:26.700 --> 00:16:29.200
And his private key will be

335
00:16:29.200 --> 00:16:32.300
 the inverse of e module 5

336
00:16:32.300 --> 00:16:34.700
 event not modular n but module 5n.

337
00:16:35.500 --> 00:16:39.300
So to be able to compute these inverse operation,

338
00:16:39.300 --> 00:16:42.900
 we need e and 5 1 to be Co

339
00:16:42.900 --> 00:16:46.100
 prime or to not share any common

340
00:16:45.100 --> 00:16:48.400
 divisors. So at this

341
00:16:48.400 --> 00:16:51.900
 step we have distributed the public key and private key D

342
00:16:51.900 --> 00:16:52.900
 to pop.

343
00:16:53.500 --> 00:16:56.300
And of course his public key can be

344
00:16:56.300 --> 00:16:59.100
 shared with anyone including Alice here.

345
00:17:00.300 --> 00:17:03.600
so to encrypt some element X which

346
00:17:03.600 --> 00:17:06.500
 is represented as an integer

347
00:17:06.500 --> 00:17:07.900
 module n

348
00:17:08.900 --> 00:17:11.400
this is missing in slime, but let's keep

349
00:17:11.400 --> 00:17:12.100
 that in mind.

350
00:17:13.100 --> 00:17:14.000
to encrypt

351
00:17:14.800 --> 00:17:17.800
Alice has to raise her plain

352
00:17:17.800 --> 00:17:18.300
 text X.

353
00:17:19.300 --> 00:17:22.600
Power e so she will compute X

354
00:17:22.600 --> 00:17:24.000
 power e on Julian.

355
00:17:25.100 --> 00:17:27.900
And that will be her ciphertext. Why?

356
00:17:29.300 --> 00:17:33.200
To decrypt Bob will need to

357
00:17:32.200 --> 00:17:36.300
 raise the ciphertext Y

358
00:17:36.300 --> 00:17:39.400
 power is secret key or

359
00:17:39.400 --> 00:17:42.000
 private key to retrieve X.

360
00:17:42.300 --> 00:17:42.600
Okay.

361
00:17:43.500 --> 00:17:46.400
Two important questions here why this

362
00:17:46.400 --> 00:17:50.300
 is correct and why this is secure this are

363
00:17:49.300 --> 00:17:52.400
 the questions that we need to focus on

364
00:17:52.400 --> 00:17:56.300
 first why it is correct to

365
00:17:55.300 --> 00:17:59.300
 understand that let's first look

366
00:17:58.300 --> 00:18:01.900
 at how we computed the D

367
00:18:01.900 --> 00:18:04.500
 from E. What's the relationship between D and

368
00:18:04.500 --> 00:18:04.600
 D?

369
00:18:05.500 --> 00:18:08.300
so the D is the inverse of e module five

370
00:18:08.300 --> 00:18:08.600
 n

371
00:18:09.300 --> 00:18:12.400
which means that e times D

372
00:18:12.400 --> 00:18:15.200
 or D times e is equal to one module five n

373
00:18:15.900 --> 00:18:18.200
So this means that

374
00:18:18.200 --> 00:18:21.500
 their product the times e is equal

375
00:18:21.500 --> 00:18:24.200
 to 1 plus some multiple of 5.

376
00:18:25.300 --> 00:18:29.100
Let's keep this result first and let's look

377
00:18:28.100 --> 00:18:31.300
 at how a computed the

378
00:18:31.300 --> 00:18:34.300
 how Bob computed the plain text

379
00:18:34.300 --> 00:18:36.000
 from the ciphertext.

380
00:18:37.500 --> 00:18:40.600
So this is what Bob did

381
00:18:40.600 --> 00:18:43.300
 erased y to D. Would you

382
00:18:43.300 --> 00:18:43.400
 go ahead?

383
00:18:44.400 --> 00:18:47.500
And the Y is actually the power of x.

384
00:18:48.400 --> 00:18:52.600
To the exponent e which you n so I just plugged that

385
00:18:52.600 --> 00:18:53.600
 value here.

386
00:18:55.200 --> 00:18:58.500
And because we are we have here we have two module n

387
00:18:58.500 --> 00:19:01.700
 we can just keep one of them and this

388
00:19:01.700 --> 00:19:04.500
 x power E power D.

389
00:19:04.500 --> 00:19:07.500
 I just write it as x times a power

390
00:19:07.500 --> 00:19:08.500
 e times d

391
00:19:10.300 --> 00:19:14.700
This is just I mean regular result about

392
00:19:14.700 --> 00:19:15.700
 powers.

393
00:19:16.800 --> 00:19:18.300
And as we have seen here.

394
00:19:19.500 --> 00:19:22.600
E times D or D times e is equal to 1 plus

395
00:19:22.600 --> 00:19:25.900
 some multiple of five n so we will plug

396
00:19:25.900 --> 00:19:29.000
 this into this e

397
00:19:28.100 --> 00:19:31.300
 times D to obtain this result.

398
00:19:33.300 --> 00:19:36.600
So and now we have X

399
00:19:36.600 --> 00:19:39.400
 power 1 plus some multiple of five n

400
00:19:39.400 --> 00:19:40.800
 we will break this.

401
00:19:42.300 --> 00:19:46.600
into x and x power five

402
00:19:45.600 --> 00:19:47.600
 n times k

403
00:19:48.500 --> 00:19:51.400
and that X power five n

404
00:19:51.400 --> 00:19:54.900
 times K can be written as X power 5 5

405
00:19:54.900 --> 00:19:55.100
 1

406
00:19:55.900 --> 00:19:58.500
and everything is our case.

407
00:20:00.400 --> 00:20:03.100
and this is where we will use the

408
00:20:03.100 --> 00:20:06.700
 important result about alert ocean function, which is

409
00:20:06.700 --> 00:20:09.600
 that X power 5 n is

410
00:20:09.600 --> 00:20:10.100
 equal to 1

411
00:20:10.700 --> 00:20:13.700
so all this is equal to 1 so

412
00:20:13.700 --> 00:20:16.800
 the whole result is equal to X modular n

413
00:20:17.300 --> 00:20:20.400
and as we said X is chosen to

414
00:20:20.400 --> 00:20:23.300
 be z n so X module n is

415
00:20:23.300 --> 00:20:27.300
 equal to X. So that's why the R6

416
00:20:26.300 --> 00:20:29.400
 description is correct and gives

417
00:20:29.400 --> 00:20:31.800
 us back the original plane text.

418
00:20:35.300 --> 00:20:37.500
Important question is why this is secure.

419
00:20:38.500 --> 00:20:41.400
Okay, what the adversary will see

420
00:20:41.400 --> 00:20:44.500
 the adversary will see the power

421
00:20:44.500 --> 00:20:47.500
 of the plaintext to the public

422
00:20:47.500 --> 00:20:50.800
 key. So these three forward

423
00:20:50.800 --> 00:20:53.400
 operation that the adversary would like

424
00:20:53.400 --> 00:20:56.600
 to do to retrieve X is to compute the year

425
00:20:56.600 --> 00:20:59.200
 throat. So to extract the X from this

426
00:20:59.200 --> 00:20:59.700
 power.

427
00:21:00.400 --> 00:21:03.500
And as we have seen a few slides cool,

428
00:21:03.500 --> 00:21:07.400
 this is a computationally difficult operation

429
00:21:06.400 --> 00:21:09.000
 if n is big enough.

430
00:21:09.400 --> 00:21:13.700
So this way is not possible for adversary unless

431
00:21:12.700 --> 00:21:15.200
 he has the deal. Of course if he has

432
00:21:15.200 --> 00:21:18.000
 the D he can do exactly what Bob did here.

433
00:21:19.300 --> 00:21:22.300
So the second approach for the

434
00:21:22.300 --> 00:21:25.400
 adversary would be first to compute the D. And once

435
00:21:25.400 --> 00:21:28.200
 he computes the D. He can do what Bob has

436
00:21:28.200 --> 00:21:28.400
 done.

437
00:21:29.300 --> 00:21:32.100
To compute the D the adversary of course knows e

438
00:21:32.100 --> 00:21:35.200
 has to use that e to compute the T.

439
00:21:36.100 --> 00:21:39.700
But in order to do that, he needs

440
00:21:39.700 --> 00:21:40.400
 the fire van.

441
00:21:41.800 --> 00:21:45.300
And that's why I said it's very important to keep

442
00:21:44.300 --> 00:21:47.500
 the factorization of n

443
00:21:47.500 --> 00:21:48.300
 Secret.

444
00:21:49.300 --> 00:21:51.600
So the secret key here is the D.

445
00:21:52.300 --> 00:21:54.600
but we need also to

446
00:21:56.400 --> 00:21:59.700
not reveal the factorization of

447
00:21:59.700 --> 00:22:02.400
 n because if we do that.

448
00:22:03.200 --> 00:22:06.600
Then the adversary can compute fire

449
00:22:06.600 --> 00:22:09.900
 n very easily and then can retrieve

450
00:22:09.900 --> 00:22:10.200
 the D.

451
00:22:10.900 --> 00:22:14.200
So these are the two

452
00:22:13.200 --> 00:22:16.500
 main approaches of attack that

453
00:22:16.500 --> 00:22:17.800
 the adversary can do.

454
00:22:18.900 --> 00:22:21.300
And until today our say

455
00:22:21.300 --> 00:22:25.200
 is secure because there is no other way to break the

456
00:22:24.200 --> 00:22:27.400
 system. The adversary has either to

457
00:22:27.400 --> 00:22:31.500
 compute the EF root or two factorize n

458
00:22:30.500 --> 00:22:34.200
 and a factorizing n

459
00:22:33.200 --> 00:22:36.600
 when n is big enough is also a

460
00:22:36.600 --> 00:22:39.600
 heart problem. So these are two hard

461
00:22:39.600 --> 00:22:42.600
 problems that keep our say

462
00:22:42.600 --> 00:22:46.900
 secure. If one of these problems is

463
00:22:46.900 --> 00:22:49.600
 found out to not be hard enough like

464
00:22:49.600 --> 00:22:53.100
 we find an efficient algorithm either

465
00:22:52.100 --> 00:22:55.600
 to factorize or to compute or to

466
00:22:55.600 --> 00:22:59.200
 extract eighth Roots. Then RSA is

467
00:22:58.200 --> 00:23:00.200
 no longer secure.

468
00:23:03.600 --> 00:23:06.700
Okay to get used to the mechanics of

469
00:23:06.700 --> 00:23:10.400
 RSA. Let's take an example

470
00:23:10.400 --> 00:23:13.500
 but keep in mind. This is a toy

471
00:23:13.500 --> 00:23:16.200
 example. This is definitely not secure. It should

472
00:23:16.200 --> 00:23:20.100
 not be used in real life. We use bigger values

473
00:23:19.100 --> 00:23:22.200
 of primes and this is

474
00:23:22.200 --> 00:23:25.700
 just to illustrate which kind of operations that

475
00:23:25.700 --> 00:23:26.000
 we have.

476
00:23:27.200 --> 00:23:30.900
So let's assume that the generator choose the

477
00:23:30.900 --> 00:23:33.900
 primes 3 and 5 then the

478
00:23:33.900 --> 00:23:35.200
 N is equal to 15.

479
00:23:36.200 --> 00:23:39.800
The file 15 is as we computed before is equal

480
00:23:39.800 --> 00:23:40.200
 to 8.

481
00:23:41.500 --> 00:23:44.300
Then the generator chooses the

482
00:23:44.300 --> 00:23:47.700
 value 3 as the exponent of

483
00:23:47.700 --> 00:23:48.700
 the public key.

484
00:23:49.400 --> 00:23:52.900
As three and eight are copyright.

485
00:23:52.900 --> 00:23:56.300
 They don't share any cover divisor rather

486
00:23:56.300 --> 00:23:57.800
 than accept one.

487
00:23:58.800 --> 00:24:02.400
so the public key will be composed

488
00:24:01.400 --> 00:24:04.500
 of the exponent 3 and

489
00:24:04.500 --> 00:24:07.900
 the module n equal to 15 and the

490
00:24:07.900 --> 00:24:11.600
 private key is the inverse of three module 515

491
00:24:10.600 --> 00:24:12.700
 which is 8

492
00:24:13.900 --> 00:24:16.600
the inverse of 3 module eight is actually 3

493
00:24:16.600 --> 00:24:19.200
 because 3 times 3 that's equal to

494
00:24:19.200 --> 00:24:21.900
 9 0 8 that's equal to 1.

495
00:24:23.300 --> 00:24:26.500
You might be surprised to see that the pub exponent of

496
00:24:26.500 --> 00:24:29.600
 the public key is 3 and the private

497
00:24:29.600 --> 00:24:32.800
 key is also three. This is just because

498
00:24:32.800 --> 00:24:34.700
 we are working on the small example.

499
00:24:36.500 --> 00:24:41.000
In real life when we have large modular. This

500
00:24:40.100 --> 00:24:42.200
 is unlikely to happen.

501
00:24:43.200 --> 00:24:48.200
So to encrypt a value 7 at

502
00:24:46.200 --> 00:24:50.100
 least reads that seven to

503
00:24:49.100 --> 00:24:52.500
 the power to the two

504
00:24:52.500 --> 00:24:52.800
 to three.

505
00:24:53.600 --> 00:24:56.400
So she computes 7 power 3 module

506
00:24:56.400 --> 00:24:59.500
 15, which is equal to 13. We

507
00:24:59.500 --> 00:25:02.600
 have seen this example a few slides ago.

508
00:25:03.100 --> 00:25:04.700
The several text is then 13.

509
00:25:05.700 --> 00:25:09.700
And 2 decrypt Bob raises 13 power

510
00:25:08.700 --> 00:25:11.700
 3 module 15 and he

511
00:25:11.700 --> 00:25:12.700
 can obtain 7.

512
00:25:13.900 --> 00:25:16.800
So this is a small example test for

513
00:25:16.800 --> 00:25:19.100
 you to get used to this kind of

514
00:25:19.100 --> 00:25:19.500
 operations.

515
00:25:22.400 --> 00:25:25.500
the security of RSA crypto system relies on

516
00:25:25.500 --> 00:25:27.600
 the hardness of integer factorization

517
00:25:28.500 --> 00:25:31.800
if an adversary invents method to factor integers

518
00:25:31.800 --> 00:25:32.300
 efficiently.

519
00:25:33.100 --> 00:25:36.700
Then he or she will be able to break RC to be

520
00:25:36.700 --> 00:25:37.000
 secure.

521
00:25:37.700 --> 00:25:41.000
You have to use today you

522
00:25:40.300 --> 00:25:43.900
 have to use an module for RSA, which

523
00:25:43.900 --> 00:25:46.600
 is at least 1024 bitlock.

524
00:25:47.900 --> 00:25:50.900
On February 2020 a

525
00:25:50.900 --> 00:25:54.300
 team of researchers computed or

526
00:25:53.300 --> 00:25:56.400
 broke the record of

527
00:25:56.400 --> 00:25:59.300
 integer factorization and they

528
00:25:59.300 --> 00:26:03.300
 managed to factorize a semi prime number which

529
00:26:02.300 --> 00:26:06.400
 was 829 bit

530
00:26:05.400 --> 00:26:06.600
 long.

531
00:26:07.500 --> 00:26:10.200
But obviously they didn't know the factorization of

532
00:26:10.200 --> 00:26:12.200
 this integer.

533
00:26:13.100 --> 00:26:16.300
This is this integer is part of the

534
00:26:16.300 --> 00:26:19.900
 challenges that RSA company published.

535
00:26:19.900 --> 00:26:22.900
 So RC company choose

536
00:26:22.900 --> 00:26:25.400
 this list of SUNY Prime

537
00:26:25.400 --> 00:26:29.200
 members and they never disclosed their factorizations

538
00:26:28.200 --> 00:26:31.600
 and it's up to the community of

539
00:26:31.600 --> 00:26:34.700
 research to try to factorize this

540
00:26:34.700 --> 00:26:37.600
 Embers. That's how we increased out

541
00:26:37.600 --> 00:26:40.300
 trust in our secret to

542
00:26:40.300 --> 00:26:44.100
 system. And these are the intentary 29 was

543
00:26:43.100 --> 00:26:46.100
 a factored by

544
00:26:46.100 --> 00:26:49.600
 this team of researchers using an open source

545
00:26:49.600 --> 00:26:53.100
 tool and some servers. So any

546
00:26:52.100 --> 00:26:55.800
 attacker that is motivated enough

547
00:26:55.800 --> 00:26:58.500
 to allocate resources can

548
00:26:58.500 --> 00:26:59.800
 repeat this attack.

549
00:27:00.500 --> 00:27:01.100
That's why.

550
00:27:01.900 --> 00:27:04.700
even 1,024-bit is still

551
00:27:04.700 --> 00:27:07.800
 considered secure, but maybe for just

552
00:27:08.500 --> 00:27:11.200
A few more years after that it want to

553
00:27:11.200 --> 00:27:12.500
 be considered secure anymore.

554
00:27:13.400 --> 00:27:17.800
We rather recommend lands that are 2K 3K

555
00:27:17.800 --> 00:27:21.400
 and 4K long for RC.

556
00:27:23.800 --> 00:27:26.200
So on this video, we covered the

557
00:27:26.200 --> 00:27:29.300
 arithmetics in the ring of

558
00:27:29.300 --> 00:27:32.500
 residues module Sony Prime

559
00:27:32.500 --> 00:27:36.200
 and we also discussed the details

560
00:27:35.200 --> 00:27:38.900
 of RSL crypto system why it

561
00:27:38.900 --> 00:27:41.100
 is correct. White is also

562
00:27:41.100 --> 00:27:41.700
 secure.

563
00:27:42.400 --> 00:27:45.700
And this is the last video of the

564
00:27:45.700 --> 00:27:48.700
 section in the next section. We

565
00:27:48.700 --> 00:27:51.400
 will continue with the public key

566
00:27:51.400 --> 00:27:54.700
 cryptography and we'll revisit our say in

567
00:27:54.700 --> 00:27:57.500
 particular to see how we can derive digital

568
00:27:57.500 --> 00:28:01.400
 signatures from the RSA one-way

569
00:28:00.400 --> 00:28:01.500
 function.

570
00:28:02.500 --> 00:28:05.100
So stay tuned see you on the next video.
