1
00:00:00,000 --> 00:00:02,000
[RSA]

2
00:00:02,000 --> 00:00:04,000
[Rob Bowden] [Tommy MacWilliam] [Harvard University]

3
00:00:04,000 --> 00:00:07,000
[This is CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:11,000
Let's take a look at RSA, a widely used algorithm for encrypting data.

5
00:00:11,000 --> 00:00:16,000
Encryption algorithms like Caesar and Vigenère ciphers aren't very secure.

6
00:00:16,000 --> 00:00:20,000
With the Caesar cipher, an attacker only needs to try 25 different keys

7
00:00:20,000 --> 00:00:22,000
to get the message's plain text.

8
00:00:22,000 --> 00:00:25,000
While the Vigenère cipher is more secure than the Caesar cipher

9
00:00:25,000 --> 00:00:28,000
because of the larger search space for keys, once an attacker

10
00:00:28,000 --> 00:00:30,000
knows the length of the key in a Vigenère cipher,

11
00:00:30,000 --> 00:00:34,000
which can be determined via an analysis of patterns in the encrypted text,

12
00:00:34,000 --> 00:00:38,000
the Vigenère cipher is not that much more secure than the Caesar cipher.

13
00:00:38,000 --> 00:00:42,000
RSA, on the other hand, isn't vulnerable to attacks like this.

14
00:00:42,000 --> 00:00:45,000
The Caesar cipher and Vigenère cipher use the same key

15
00:00:45,000 --> 00:00:47,000
to both encrypt and decrypt a message.

16
00:00:47,000 --> 00:00:51,000
This property makes these ciphers symmetric key algorithms.

17
00:00:51,000 --> 00:00:54,000
A fundamental problem with symmetric key algorithms

18
00:00:54,000 --> 00:00:57,000
is that they rely on the one encrypting and sending the message

19
00:00:57,000 --> 00:00:59,000
and the one receiving and decrypting the message

20
00:00:59,000 --> 00:01:03,000
to have already agreed upfront on the key they will both use.

21
00:01:03,000 --> 00:01:06,000
But we have a bit of a startup problem here.

22
00:01:06,000 --> 00:01:10,000
How do 2 computers that want to communicate establish a secret key between them?

23
00:01:10,000 --> 00:01:16,000
If the key must be secret, then we need a way to encrypt and decrypt the key.

24
00:01:16,000 --> 00:01:18,000
If all we have is symmetric key cryptography

25
00:01:18,000 --> 00:01:21,000
then we've just come back to the same problem.

26
00:01:21,000 --> 00:01:25,000
RSA, on the other hand, uses a pair of keys,

27
00:01:25,000 --> 00:01:28,000
one for encryption and another for decryption.

28
00:01:28,000 --> 00:01:32,000
One is called the public key, and the other is the private key.

29
00:01:32,000 --> 00:01:34,000
The public key is used to encrypt messages.

30
00:01:34,000 --> 00:01:38,000
As you might guess by its name, we can share our public key with

31
00:01:38,000 --> 00:01:43,000
anyone we want without compromising the security of an encrypted message.

32
00:01:43,000 --> 00:01:45,000
Messages encrypted using a public key

33
00:01:45,000 --> 00:01:49,000
can only be decrypted with its corresponding private key.

34
00:01:49,000 --> 00:01:53,000
While you can share your public key, you should always keep your private key secret.

61
00:01:55,000 --> 00:01:58,000
and only the private key can be used to decrypt messages

62
00:01:58,000 --> 00:02:02,000
if 2 users want to send messages encrypted with RSA

63
00:02:02,000 --> 00:02:07,000
back and forth both users need to have their own public and private key pair.

64
00:02:07,000 --> 00:02:10,000
Messages from user 1 to user 2

65
00:02:10,000 --> 00:02:15,000
only use user 2's key pair, and messages from user 2 to user 1

66
00:02:15,000 --> 00:02:17,000
only use user 1's key pair.

67
00:02:17,000 --> 00:02:21,000
The fact that there are 2 separate keys to encrypt and decrypt messages

68
00:02:21,000 --> 00:02:24,000
makes RSA an asymmetric key algorithm.

69
00:02:24,000 --> 00:02:28,000
We don't need to encrypt the public key in order to send it to another computer

70
00:02:28,000 --> 00:02:31,000
since the key is public anyway.

71
00:02:31,000 --> 00:02:33,000
This means that RSA doesn't have the same startup problem

72
00:02:33,000 --> 00:02:36,000
as the symmetric key algorithms.

73
00:02:36,000 --> 00:02:39,000
So if I want to send a message using RSA encryption

74
00:02:39,000 --> 00:02:42,000
to Rob, I'll first need Rob's public key.

75
00:02:42,000 --> 00:02:47,000
To generate a pair of keys, Rob needs to pick 2 large prime numbers.

76
00:02:47,000 --> 00:02:50,000
These numbers will be used in both the public and private keys,

77
00:02:50,000 --> 00:02:54,000
but the public key will only use the product of these 2 numbers,

78
00:02:54,000 --> 00:02:56,000
not the numbers themselves.

79
00:02:56,000 --> 00:02:59,000
Once I've encrypted the message using Rob's public key

80
00:02:59,000 --> 00:03:01,000
I can send the message to Rob.

81
00:03:01,000 --> 00:03:05,000
For a computer, factoring numbers is a hard problem.

82
00:03:05,000 --> 00:03:09,000
The public key, remember, used the product of 2 prime numbers.

83
00:03:09,000 --> 00:03:12,000
This product must then have only 2 factors,

84
00:03:12,000 --> 00:03:16,000
which happen to be the numbers that make up the private key.

85
00:03:16,000 --> 00:03:20,000
In order to decrypt the message, RSA will use this private key

86
00:03:20,000 --> 00:03:25,000
or the numbers multiplied together in the process of creating the public key.

87
00:03:25,000 --> 00:03:28,000
Because it's computationally hard to factor the number

88
00:03:28,000 --> 00:03:32,000
used in a public key into the 2 numbers used in the private key

89
00:03:32,000 --> 00:03:36,000
it's difficult for an attacker to figure out the private key

90
00:03:36,000 --> 00:03:39,000
that will be necessary to decrypt the message.

91
00:03:39,000 --> 00:03:43,000
Now let's go into some lower level details of RSA.

92
00:03:43,000 --> 00:03:46,000
Let's first see how we can generate a pair of keys.

93
00:03:46,000 --> 00:03:49,000
First, we'll need 2 prime numbers.

94
00:03:49,000 --> 00:03:52,000
We'll call these 2 numbers p and q.

95
00:03:52,000 --> 00:03:56,000
In order to pick p and q, in practice we would pseudorandomly generate

96
00:03:56,000 --> 00:03:59,000
large numbers and then use a test for determining whether or not

97
00:03:59,000 --> 00:04:02,000
those numbers are probably prime.

98
00:04:02,000 --> 00:04:05,000
We can keep generating random numbers over and over again

99
00:04:05,000 --> 00:04:08,000
until we have 2 primes that we can use.

100
00:04:08,000 --> 00:04:15,000
Here let's pick p = 23 and q = 43.

101
00:04:15,000 --> 00:04:19,000
Remember, in practice, p and q should be much larger numbers.

102
00:04:19,000 --> 00:04:22,000
As far as we know, the larger the numbers, the harder it is

103
00:04:22,000 --> 00:04:25,000
to crack an encrypted message.

104
00:04:25,000 --> 00:04:29,000
But it's also more expensive to encrypt and decrypt messages.

105
00:04:29,000 --> 00:04:33,000
Today it's often recommended that p and q are at least 1024 bits,

106
00:04:33,000 --> 00:04:37,000
which puts each number at over 300 decimal digits.

107
00:04:37,000 --> 00:04:40,000
But we'll pick these small numbers for this example.

108
00:04:40,000 --> 00:04:43,000
Now we'll multiply p and q together to get a 3rd number,

109
00:04:43,000 --> 00:04:45,000
which we'll call n.

110
00:04:45,000 --> 00:04:55,000
In our case, n = 23 * 43, which = 989.

111
00:04:55,000 --> 00:04:58,000
We have n = 989.

112
00:04:58,000 --> 00:05:02,000
Next we'll multiply p - 1 with q - 1

113
00:05:02,000 --> 00:05:05,000
to obtain a 4th number, which we'll call m.

114
00:05:05,000 --> 00:05:15,000
In our case, m = 22 * 42, which = 924.

115
00:05:15,000 --> 00:05:18,000
We have m = 924.

116
00:05:18,000 --> 00:05:22,000
Now we'll need a number e that is relatively prime to m

117
00:05:22,000 --> 00:05:25,000
and less than m.

118
00:05:25,000 --> 00:05:28,000
Two numbers are relatively prime or coprime

119
00:05:28,000 --> 00:05:33,000
if the only positive integer that divides them both evenly is 1.

120
00:05:33,000 --> 00:05:37,000
In other words, the greatest common divisor of e and m

121
00:05:37,000 --> 00:05:39,000
must be 1.

122
00:05:39,000 --> 00:05:44,000
In practice, it's common for e to be the prime number 65537

123
00:05:44,000 --> 00:05:48,000
as long as this number doesn't happen to be a factor of m.

124
00:05:48,000 --> 00:05:53,000
For our keys, we'll pick e = 5

125
00:05:53,000 --> 00:05:57,000
since 5 is relatively prime to 924.

126
00:05:57,000 --> 00:06:01,000
Finally, we'll need one more number, which we'll call d.

127
00:06:01,000 --> 00:06:11,000
D must be some value that satisfies the equation de = 1(mod m).

128
00:06:11,000 --> 00:06:17,000
This mod m signifies we'll use something called modular arithmetic.

129
00:06:17,000 --> 00:06:21,000
In modular arithmetic, once a number gets higher than some upper bound

130
00:06:21,000 --> 00:06:24,000
it will wrap back around to 0.

131
00:06:24,000 --> 00:06:27,000
A clock, for example, uses modular arithmetic.

132
00:06:27,000 --> 00:06:31,000
One minute after 1:59, for example, is 2:00,

133
00:06:31,000 --> 00:06:33,000
not 1:60.

134
00:06:33,000 --> 00:06:36,000
The minute hand has wrapped around to 0

135
00:06:36,000 --> 00:06:39,000
upon reaching an upper bound of 60.

136
00:06:39,000 --> 00:06:46,000
So, we can say 60 is equivalent to 0 (mod 60)

137
00:06:46,000 --> 00:06:57,000
and 125 is equivalent to 65 is equivalent to 5 (mod 60).

138
00:06:57,000 --> 00:07:02,000
Our public key will be the pair e and n

139
00:07:02,000 --> 00:07:09,000
where in this case e is 5 and n is 989.

140
00:07:09,000 --> 00:07:15,000
Our private key will be the pair d and n,

141
00:07:15,000 --> 00:07:22,000
which in our case is 185 and 989.

142
00:07:22,000 --> 00:07:25,000
Notice that our original primes p and q don't appear

143
00:07:25,000 --> 00:07:29,000
anywhere in our private or public keys.

144
00:07:29,000 --> 00:07:33,000
Now that we have our pair of keys, let's take a look at how we can encrypt

145
00:07:33,000 --> 00:07:36,000
and decrypt a message.

146
00:07:36,000 --> 00:07:38,000
I want to send a message to Rob,

147
00:07:38,000 --> 00:07:42,000
so he will be the one to generate this key pair.

148
00:07:42,000 --> 00:07:46,000
Then I'll ask Rob for his public key, which I'll use

149
00:07:46,000 --> 00:07:48,000
to encrypt a message to send to him.

150
00:07:48,000 --> 00:07:53,000
Remember, it's totally okay for Rob to share his public key with me.

151
00:07:53,000 --> 00:07:56,000
But it would not be okay to share his private key.

152
00:07:56,000 --> 00:08:00,000
I don't have any idea what his private key is.

153
00:08:00,000 --> 00:08:03,000
We can break our message m up into several chunks

154
00:08:03,000 --> 00:08:07,000
all smaller than n and then encrypt each of those chunks.

155
00:08:07,000 --> 00:08:12,000
We'll encrypt the string CS50, which we can break up into 4 chunks,

156
00:08:12,000 --> 00:08:14,000
one per letter.

157
00:08:14,000 --> 00:08:17,000
In order to encrypt my message, I'll need to convert it into

158
00:08:17,000 --> 00:08:20,000
some kind of numeric representation.

159
00:08:20,000 --> 00:08:25,000
Let's concatenate the ASCII values with the characters in my message.

160
00:08:25,000 --> 00:08:28,000
In order to encrypt a given message m

161
00:08:28,000 --> 00:08:37,000
I'll need to compute c = m to the e (mod n).

162
00:08:37,000 --> 00:08:40,000
But m must be smaller than n,

163
00:08:40,000 --> 00:08:45,000
or else the full message can't be expressed modulo n.

164
00:08:45,000 --> 00:08:49,000
We can break m up into several chunks, all of which are smaller than n,

165
00:08:49,000 --> 00:08:52,000
and encrypt each of those chunks.

166
00:08:52,000 --> 00:09:03,000
Encrypting each of these chunks, we get c1 = 67 to the 5 (mod 989)

167
00:09:03,000 --> 00:09:06,000
which = 658.

168
00:09:06,000 --> 00:09:15,000
For our second chunk we have 83 to the 5 (mod 989)

169
00:09:15,000 --> 00:09:18,000
which = 15.

170
00:09:18,000 --> 00:09:26,000
For our third chunk we have 53 to the 5 (mod 989)

171
00:09:26,000 --> 00:09:30,000
which = 799.

172
00:09:30,000 --> 00:09:39,000
And finally, for our last chunk we have 48 to the 5 (mod 989)

173
00:09:39,000 --> 00:09:43,000
which = 975.

174
00:09:43,000 --> 00:09:48,000
Now we can send over these encrypted values to Rob.

175
00:09:54,000 --> 00:09:58,000
Here you go, Rob.

176
00:09:58,000 --> 00:10:01,000
While our message is in flight, let's take another look

177
00:10:01,000 --> 00:10:07,000
at how we got that value for d.

178
00:10:07,000 --> 00:10:17,000
Our number d needed to satisfy 5d = 1 (mod 924).

179
00:10:17,000 --> 00:10:24,000
This makes d the multiplicative inverse of 5 modulo 924.

180
00:10:24,000 --> 00:10:28,000
Given 2 integers, a and b, the extended Euclidean algorithm

181
00:10:28,000 --> 00:10:33,000
can be used to find the greatest common divisor of these 2 integers.

182
00:10:33,000 --> 00:10:37,000
It will also give us 2 other numbers, x and y,

183
00:10:37,000 --> 00:10:47,000
that satisfy the equation ax + by = the greatest common divisor of a and b.

184
00:10:47,000 --> 00:10:49,000
How does this help us?

185
00:10:49,000 --> 00:10:52,000
Well, plugging in e = 5 for a

186
00:10:52,000 --> 00:10:56,000
and m = 924 for b

187
00:10:56,000 --> 00:10:59,000
we already know that these numbers are coprime.

188
00:10:59,000 --> 00:11:03,000
Their greatest common divisor is 1.

189
00:11:03,000 --> 00:11:09,000
This gives us 5x + 924y = 1

190
00:11:09,000 --> 00:11:17,000
or 5x = 1 - 924y.

191
00:11:17,000 --> 00:11:22,000
But if we only care about everything modulo 924

192
00:11:22,000 --> 00:11:25,000
then we can drop the - 924y.

193
00:11:25,000 --> 00:11:27,000
Think back to the clock.

194
00:11:27,000 --> 00:11:31,000
If the minute hand is on 1 and then exactly 10 hours pass,

195
00:11:31,000 --> 00:11:35,000
we know the minute hand will still be on the 1.

196
00:11:35,000 --> 00:11:39,000
Here we start at 1 and then wrap around exactly y times,

197
00:11:39,000 --> 00:11:41,000
so we'll still be at 1.

198
00:11:41,000 --> 00:11:49,000
We have 5x = 1 (mod 924).

199
00:11:49,000 --> 00:11:55,000
And here this x is the same as the d we were looking for before,

200
00:11:55,000 --> 00:11:58,000
so if we use the extended Euclidean algorithm

201
00:11:58,000 --> 00:12:04,000
to get this number x, that's the number we should use as our d.

202
00:12:04,000 --> 00:12:07,000
Now let's run the extended Euclidean algorithm for a = 5

203
00:12:07,000 --> 00:12:11,000
and b = 924.

204
00:12:11,000 --> 00:12:14,000
We'll use a method called the table method.

205
00:12:14,000 --> 00:12:21,000
Our table will have 4 columns, x, y, d, and k.

206
00:12:21,000 --> 00:12:23,000
Our table starts off with 2 rows.

207
00:12:23,000 --> 00:12:28,000
In the first row we have 1, 0, then our value of a, which is 5,

208
00:12:28,000 --> 00:12:37,000
and our second row is 0, 1, and our value for b, which is 924.

209
00:12:37,000 --> 00:12:40,000
The value of the 4th column, k, will be the result

210
00:12:40,000 --> 00:12:45,000
of dividing the value of d in the row above it with the value of d

211
00:12:45,000 --> 00:12:49,000
on the same row.

212
00:12:49,000 --> 00:12:56,000
We have 5 divided by 924 is 0 with some remainder.

213
00:12:56,000 --> 00:12:59,000
That means we have k = 0.

214
00:12:59,000 --> 00:13:05,000
Now the value of every other cell will be the value of the cell 2 rows above it

215
00:13:05,000 --> 00:13:09,000
minus the value of the row above it times k.

216
00:13:09,000 --> 00:13:11,000
Let's start with d in the 3rd row.

217
00:13:11,000 --> 00:13:19,000
We have 5 - 924 * 0 = 5.

218
00:13:19,000 --> 00:13:25,000
Next we have 0 - 1 * 0 which is 0

219
00:13:25,000 --> 00:13:30,000
and 1 - 0 * 0 which is 1.

220
00:13:30,000 --> 00:13:33,000
Not too bad, so let's move on to the next row.

221
00:13:33,000 --> 00:13:36,000
First we need our value of k.

222
00:13:36,000 --> 00:13:43,000
924 divided by 5 = 184 with some remainder,

223
00:13:43,000 --> 00:13:46,000
so our value for k is 184.

224
00:13:46,000 --> 00:13:54,000
Now 924 - 5 * 184 = 4.

225
00:13:54,000 --> 00:14:05,000
1 - 0 * 184 is 1 and 0 - 1 * 184 is -184.

226
00:14:05,000 --> 00:14:07,000
All right, let's do the next row.

227
00:14:07,000 --> 00:14:10,000
Our value of k will be 1 because

228
00:14:10,000 --> 00:14:15,000
5 divided by 4 = 1 with some remainder.

229
00:14:15,000 --> 00:14:17,000
Let's fill in the other columns.

230
00:14:17,000 --> 00:14:21,000
5 - 4 * 1 = 1.

231
00:14:21,000 --> 00:14:25,000
0 - 1 * 1 = -1.

232
00:14:25,000 --> 00:14:33,000
And 1 - -184 * 1 is 185.

233
00:14:33,000 --> 00:14:35,000
Let's see what our next value of k would be.

234
00:14:35,000 --> 00:14:40,000
Well, it looks like we have 4 divided by 1, which is 4.

235
00:14:40,000 --> 00:14:43,000
In this case where we're dividing by 1 such that k is equal to

236
00:14:43,000 --> 00:14:50,000
the value of d in the above row means that we're done with our algorithm.

237
00:14:50,000 --> 00:14:58,000
We can see here that we have x = 185 and y = -1 in the last row.

238
00:14:58,000 --> 00:15:00,000
Let's now come back to our original goal.

239
00:15:00,000 --> 00:15:04,000
We said that the value of x as a result of running this algorithm

240
00:15:04,000 --> 00:15:08,000
would be the multiplicative inverse of a (mod b).

241
00:15:08,000 --> 00:15:15,000
That means that 185 is the multiplicative inverse of 5 (mod 924)

242
00:15:15,000 --> 00:15:20,000
which means that we have a value of 185 for d.

243
00:15:20,000 --> 00:15:23,000
The fact that d = 1 in the last row

244
00:15:23,000 --> 00:15:26,000
verifies that e was coprime to m.

245
00:15:26,000 --> 00:15:30,000
If it weren't 1 then we would have to pick a new e.

246
00:15:30,000 --> 00:15:33,000
Now let's see if Rob has received my message.

247
00:15:33,000 --> 00:15:35,000
When someone sends me an encrypted message

248
00:15:35,000 --> 00:15:38,000
as long as I've kept my private key a secret

249
00:15:38,000 --> 00:15:41,000
I'm the only one who can decrypt the message.

250
00:15:41,000 --> 00:15:46,000
To decrypt a chunk c I can calculate the original message

251
00:15:46,000 --> 00:15:53,000
is equal to the chunk to d power (mod n).

252
00:15:53,000 --> 00:15:57,000
Remember that d and n are from my private key.

253
00:15:57,000 --> 00:16:01,000
To get a full message from its chunks we decrypt each chunk

254
00:16:01,000 --> 00:16:04,000
and concatenate the results.

255
00:16:04,000 --> 00:16:08,000
Exactly how secure is RSA?

256
00:16:08,000 --> 00:16:10,000
The truth is, we don't know.

257
00:16:10,000 --> 00:16:14,000
Security is based on how long it would take an attacker to crack a message

258
00:16:14,000 --> 00:16:16,000
encrypted with RSA.

259
00:16:16,000 --> 00:16:19,000
Remember that an attacker has access to your public key,

260
00:16:19,000 --> 00:16:21,000
which contains both e and n.

261
00:16:21,000 --> 00:16:26,000
If the attacker manages to factor n into its 2 primes, p and q,

262
00:16:26,000 --> 00:16:30,000
then she could calculate d using the extended Euclidean algorithm.

263
00:16:30,000 --> 00:16:35,000
This gives her the private key, which can be used to decrypt any message.

264
00:16:35,000 --> 00:16:38,000
But how quickly can we factor integers?

265
00:16:38,000 --> 00:16:41,000
Again, we don't know.

266
00:16:41,000 --> 00:16:43,000
Nobody has found a fast way of doing it,

267
00:16:43,000 --> 00:16:46,000
which means that given large enough n

268
00:16:46,000 --> 00:16:49,000
it would take an attacker unrealistically long

269
00:16:49,000 --> 00:16:51,000
to factor the number.

270
00:16:51,000 --> 00:16:54,000
If someone revealed a fast way of factoring integers

271
00:16:54,000 --> 00:16:57,000
RSA would be broken.

272
00:16:57,000 --> 00:17:01,000
But even if integer factorization is inherently slow

273
00:17:01,000 --> 00:17:04,000
the RSA algorithm could still have some flaw in it

274
00:17:04,000 --> 00:17:07,000
that allows for easy decryption of messages.

275
00:17:07,000 --> 00:17:10,000
Nobody has found and revealed such a flaw yet,

276
00:17:10,000 --> 00:17:12,000
but that doesn't mean one doesn't exist.

277
00:17:12,000 --> 00:17:17,000
In theory, someone could be out there reading all data encrypted with RSA.

278
00:17:17,000 --> 00:17:19,000
There's another bit of a privacy issue.

279
00:17:19,000 --> 00:17:23,000
If Tommy encrypts some message using my public key

280
00:17:23,000 --> 00:17:26,000
and an attacker encrypts the same message using my public key

281
00:17:26,000 --> 00:17:29,000
the attacker will see that the 2 messages are identical

282
00:17:29,000 --> 00:17:32,000
and thus know what Tommy encrypted.

283
00:17:32,000 --> 00:17:36,000
In order to prevent this, messages are typically padded with random bits

284
00:17:36,000 --> 00:17:39,000
before being encrypted so that the same message encrypted

285
00:17:39,000 --> 00:17:44,000
multiple times will look different as long as the padding on the message is different.

286
00:17:44,000 --> 00:17:47,000
But remember how we have to split messages into chunks

287
00:17:47,000 --> 00:17:50,000
so that each chunk is smaller than n?

288
00:17:50,000 --> 00:17:52,000
Padding the chunks means that we might have to split things up

289
00:17:52,000 --> 00:17:57,000
into even more chunks since the padded chunk must be smaller than n.

290
00:17:57,000 --> 00:18:01,000
Encryption and decryption are relatively expensive with RSA,

291
00:18:01,000 --> 00:18:05,000
and so needing to break up a message into many chunks can be very costly.

292
00:18:05,000 --> 00:18:09,000
If a large volume of data needs to be encrypted and decrypted

293
00:18:09,000 --> 00:18:12,000
we can combine the benefits of symmetric key algorithms

294
00:18:12,000 --> 00:18:16,000
with those of RSA to get both security and efficiency.

295
00:18:16,000 --> 00:18:18,000
Although we won't go into it here,

296
00:18:18,000 --> 00:18:23,000
AES is a symmetric key algorithm like the Vigenère and Caesar ciphers

297
00:18:23,000 --> 00:18:25,000
but much harder to crack.

298
00:18:25,000 --> 00:18:30,000
Of course, we can't use AES without establishing a shared secret key

299
00:18:30,000 --> 00:18:34,000
between the 2 systems, and we saw the problem with that before.

300
00:18:34,000 --> 00:18:40,000
But now we can use RSA to establish the shared secret key between the 2 systems.

301
00:18:40,000 --> 00:18:43,000
We'll call the computer sending the data the sender

302
00:18:43,000 --> 00:18:46,000
and the computer receiving the data the receiver.

303
00:18:46,000 --> 00:18:49,000
The receiver has an RSA key pair and sends

304
00:18:49,000 --> 00:18:51,000
the public key to the sender.

305
00:18:51,000 --> 00:18:54,000
The sender generates an AES key,

306
00:18:54,000 --> 00:18:57,000
encrypts it with the receiver's RSA public key,

307
00:18:57,000 --> 00:19:00,000
and sends the AES key to the receiver.

308
00:19:00,000 --> 00:19:04,000
The receiver decrypts the message with its RSA private key.

309
00:19:04,000 --> 00:19:09,000
Both the sender and the receiver now have a shared AES key between them.

310
00:19:09,000 --> 00:19:14,000
AES, which is much faster at encryption and decryption than RSA,

311
00:19:14,000 --> 00:19:18,000
can now be used to encrypt the large volumes of data and send them to the receiver,

312
00:19:18,000 --> 00:19:21,000
who can decrypt using the same key.

313
00:19:21,000 --> 00:19:26,000
AES, which is much faster at encryption and decryption than RSA,

314
00:19:26,000 --> 00:19:30,000
can now be used to encrypt the large volumes of data and send them to the receiver,

315
00:19:30,000 --> 00:19:32,000
who can decrypt using the same key.

316
00:19:32,000 --> 00:19:36,000
We just needed RSA to transfer the shared key.

317
00:19:36,000 --> 00:19:40,000
We no longer need to use RSA at all.

318
00:19:40,000 --> 00:19:46,000
It looks like I've got a message.

319
00:19:46,000 --> 00:19:49,000
It doesn't matter if anyone read what's on the paper airplane before I caught it

320
00:19:49,000 --> 00:19:55,000
because I'm the only one with the private key.

321
00:19:55,000 --> 00:19:57,000
Let's decrypt each of the chunks in the message.

322
00:19:57,000 --> 00:20:07,000
The first chunk, 658, we raise to the d power, which is 185,

323
00:20:07,000 --> 00:20:18,000
mod n, which is 989, is equal to 67,

324
00:20:18,000 --> 00:20:24,000
which is the letter C in ASCII.

325
00:20:24,000 --> 00:20:31,000
Now, onto the second chunk.

326
00:20:31,000 --> 00:20:35,000
The second chunk has value 15,

327
00:20:35,000 --> 00:20:41,000
which we raise to the 185th power,

328
00:20:41,000 --> 00:20:51,000
mod 989, and this is equal to 83

329
00:20:51,000 --> 00:20:57,000
which is the letter S in ASCII.

330
00:20:57,000 --> 00:21:06,000
Now for the third chunk, which has value 799, we raise to 185,

331
00:21:06,000 --> 00:21:17,000
mod 989, and this is equal to 53,

332
00:21:17,000 --> 00:21:24,000
which is the value of the character 5 in ASCII.

333
00:21:24,000 --> 00:21:30,000
Now for the last chunk, which has value 975,

334
00:21:30,000 --> 00:21:41,000
we raise to 185, mod 989,

335
00:21:41,000 --> 00:21:51,000
and this is equal to 48, which is value of the character 0 in ASCII.

336
00:21:51,000 --> 00:21:57,000
My name is Rob Bowden, and this is CS50.

337
00:21:57,000 --> 00:22:00,000
[CS50.TV]

338
00:22:06,000 --> 00:22:08,000
RSA at all.

339
00:22:08,000 --> 00:22:14,000
RSA at all. [laughter]

340
00:22:14,000 --> 00:22:17,000
At all.