1
00:00:00,000 --> 00:00:04,133
Hello everyone. In this video, 
we're going to talk about RSA. 

2
00:00:04,133 --> 00:00:04,766


3
00:00:04,766 --> 00:00:05,933
Now

4
00:00:05,933 --> 00:00:09,566
here, again, I'm using 
Sage Math Cloud as my

5
00:00:09,566 --> 00:00:10,233


6
00:00:10,233 --> 00:00:12,666
LaTeX editor, but here I'm actually using the

7
00:00:12,666 --> 00:00:15,233
Sage version of it. So I can 
actually have access to

8
00:00:15,233 --> 00:00:18,233
Python and Sage and all of the
mathematical commands,

9
00:00:18,233 --> 00:00:21,100
which I'll use to do some of the 
computations in this video.

10
00:00:21,100 --> 00:00:22,100


11
00:00:22,100 --> 00:00:25,233
So in order to do RSA, let's talk
about the framework again.

12
00:00:25,233 --> 00:00:27,433
So over here we're going to have our Alice -

13
00:00:27,433 --> 00:00:29,700
so I'm going to use the 
paintbrush to do a little bit.

14
00:00:29,700 --> 00:00:32,000
So Alice,

15
00:00:32,000 --> 00:00:35,166


16
00:00:35,166 --> 00:00:37,166
and over here we're going to have Bob

17
00:00:37,166 --> 00:00:40,000


18
00:00:40,000 --> 00:00:44,200


19
00:00:44,200 --> 00:00:49,033
over here, and over here we're 
going to put Eve in the middle.

20
00:00:49,033 --> 00:00:52,733
Eve for eavesdropper. Some people 
use Oscar I'm going to use Eve.

21
00:00:52,733 --> 00:00:54,833


22
00:00:54,833 --> 00:00:55,333


23
00:00:55,333 --> 00:00:58,200
So the idea is that Alice and 
Bob want to share messages.

24
00:00:58,200 --> 00:01:02,400
So Alice wants to - Bob wants to 
send a message to Alice, okay,

25
00:01:02,400 --> 00:01:05,466
but now Bob can't just send a message 
across the unsecured stream,

26
00:01:05,466 --> 00:01:08,566
or unsecured line, think of 
this as like the internet

27
00:01:08,566 --> 00:01:10,533
because then Eve can read it and see it.

28
00:01:10,533 --> 00:01:13,433
So Bob needs to encrypt it
somehow, so that when Eve sees

29
00:01:13,433 --> 00:01:15,633
the encrypted message, she won't 
know what's going on, but

30
00:01:15,633 --> 00:01:17,866
Alice somehow knows how to decrypt it.

31
00:01:17,866 --> 00:01:20,166


32
00:01:20,166 --> 00:01:22,600
So...

33
00:01:22,600 --> 00:01:24,800
let's go over to the Sage worksheet

34
00:01:24,800 --> 00:01:27,933
and let’s summarize this. So Bob 
wants to send Alice a message,

35
00:01:27,933 --> 00:01:29,300


36
00:01:29,300 --> 00:01:32,166
and Bob wants to send Alice a 
secure message using RSA.

37
00:01:32,166 --> 00:01:34,533


38
00:01:34,533 --> 00:01:36,700
So what's going to happen?

39
00:01:36,700 --> 00:01:37,966


40
00:01:37,966 --> 00:01:40,266
So Alice…

41
00:01:40,266 --> 00:01:41,366


42
00:01:41,366 --> 00:01:44,666
Alice is going to do what? Alice 
is going to, in the RSA scheme,

43
00:01:44,666 --> 00:01:47,566
she's going to choose a public key,

44
00:01:47,566 --> 00:01:49,000


45
00:01:49,000 --> 00:01:51,966
e comma n, satisfying

46
00:01:51,966 --> 00:01:52,466


47
00:01:52,466 --> 00:01:54,633
n is equal to p q,

48
00:01:54,633 --> 00:01:55,866


49
00:01:55,866 --> 00:01:57,800
and what do we have to have about e?

50
00:01:57,800 --> 00:02:01,100
So I guess we don't need
a period here, and e

51
00:02:01,100 --> 00:02:03,466
satisfies…

52
00:02:03,466 --> 00:02:06,866


53
00:02:06,866 --> 00:02:09,500
positive integer satisfying

54
00:02:09,500 --> 00:02:09,766


55
00:02:09,766 --> 00:02:10,133


56
00:02:10,133 --> 00:02:15,066
gcd of e and p minus 1 q minus 1

57
00:02:15,066 --> 00:02:17,100
equals 1

58
00:02:17,100 --> 00:02:19,200
for distinct

59
00:02:19,200 --> 00:02:20,366


60
00:02:20,366 --> 00:02:24,166
primes p and q.

61
00:02:24,166 --> 00:02:24,633


62
00:02:24,633 --> 00:02:27,533
Okay, so Alice is going to
choose a public key, e and n,

63
00:02:27,533 --> 00:02:30,533
satisfying n equals p q for 
distinct primes p and q,

64
00:02:30,533 --> 00:02:32,466
and e is a positive integer satisfying

65
00:02:32,466 --> 00:02:35,400
the gcd of e and p minus 1 q minus 1,

66
00:02:35,400 --> 00:02:38,966
also known as phi of n, is equal to 1.

67
00:02:38,966 --> 00:02:40,733
So let's go to our picture. 

68
00:02:40,733 --> 00:02:44,100
So Alice, Eve, and Bob, so everyone's 
going to have this public key.

69
00:02:44,100 --> 00:02:46,400
This public is going to be given by

70
00:02:46,400 --> 00:02:48,833
e comma n.

71
00:02:48,833 --> 00:02:50,033


72
00:02:50,033 --> 00:02:52,633
Everyone knows the public key e n.

73
00:02:52,633 --> 00:02:53,266


74
00:02:53,266 --> 00:02:56,033
I know it, you know it, Eve knows it,

75
00:02:56,033 --> 00:02:56,866


76
00:02:56,866 --> 00:02:59,266
grandma knows it, everyone knows it.

77
00:02:59,266 --> 00:03:00,666


78
00:03:00,666 --> 00:03:02,633
Okay, excellent.

79
00:03:02,633 --> 00:03:03,900


80
00:03:03,900 --> 00:03:05,566
So what do we do this? Okay, so

81
00:03:05,566 --> 00:03:09,500
here's the situation. Let's actually 
pick some examples of n, p, and q.

82
00:03:09,500 --> 00:03:12,633
So what am I going to pick? 
I'm going to pick p is equal to -

83
00:03:12,633 --> 00:03:17,466
I'm going to use this command called next 
prime because I want an actual large prime.

84
00:03:17,466 --> 00:03:20,400
So I'm going to pick the 
first prime after 12345.

85
00:03:20,400 --> 00:03:22,833


86
00:03:22,833 --> 00:03:24,800
q is going to be

87
00:03:24,800 --> 00:03:27,800
the next prime after 54321.

88
00:03:27,800 --> 00:03:29,766


89
00:03:29,766 --> 00:03:32,466
Again remember these are all 
Sage commands, next prime and

90
00:03:32,466 --> 00:03:36,900
everything will be written - if you know Python, 
it's kind of like Python with a little bit more to it.

91
00:03:36,900 --> 00:03:38,366


92
00:03:38,366 --> 00:03:40,266
If not, that's okay. Hopefully 
this is still pretty reasonable.

93
00:03:40,266 --> 00:03:42,900
So next prime will print the 
first prime after…will pick -

94
00:03:42,900 --> 00:03:47,733
will set p to be the next prime after 12345, 
and q will be the next prime after 54321.

95
00:03:47,733 --> 00:03:48,433


96
00:03:48,433 --> 00:03:50,633
n is going to be p times q,

97
00:03:50,633 --> 00:03:53,533


98
00:03:53,533 --> 00:03:57,066
and we need to pick an integer e, 

99
00:03:57,066 --> 00:03:59,666


100
00:03:59,666 --> 00:04:02,166
so, I don’t know, I'm going 
to pick e equals 17.

101
00:04:02,166 --> 00:04:03,833


102
00:04:03,833 --> 00:04:09,033
And I'm going to print the…just to 
make sure that the gcd of e and

103
00:04:09,033 --> 00:04:11,800
p minus 1 times q minus 1…

104
00:04:11,800 --> 00:04:12,366


105
00:04:12,366 --> 00:04:12,500


106
00:04:12,500 --> 00:04:15,600
I'm going to just print out this gcd. I
want to make sure that the gcd is 1.

107
00:04:15,600 --> 00:04:17,000


108
00:04:17,000 --> 00:04:18,700
So I'm going to - you know 
what? I'll print out e as well,

109
00:04:18,700 --> 00:04:20,700
so I'm going to print out e and the gcd 
of p minus 1 [times q minus 1 and e].

110
00:04:20,700 --> 00:04:22,966
So let's see what happens
when I run this code.

111
00:04:22,966 --> 00:04:23,800


112
00:04:23,800 --> 00:04:27,500
So p is the value 12347, okay,

113
00:04:27,500 --> 00:04:30,666
and q is the value 54323,

114
00:04:30,666 --> 00:04:33,166
apparently those two numbers 
are prime, so that's great.

115
00:04:33,166 --> 00:04:34,233


116
00:04:34,233 --> 00:04:37,233
n is equal to p times q 
print n, so the product of

117
00:04:37,233 --> 00:04:42,166
p and q is 670726081,

118
00:04:42,166 --> 00:04:46,466
so something along lines of 670 million-ish.

119
00:04:46,466 --> 00:04:48,333
Okay so it's a pretty big number,

120
00:04:48,333 --> 00:04:49,333


121
00:04:49,333 --> 00:04:52,933
and e is 17, and the gcd 
we verified to be 1.

122
00:04:52,933 --> 00:04:55,833
Oh I guess I should put the 
bracket here and make sure that

123
00:04:55,833 --> 00:04:59,400
this is actually correct. Let's 
rerun this, yeah okay.

124
00:04:59,400 --> 00:05:01,633
The gcd is 1, okay excellent.

125
00:05:01,633 --> 00:05:05,166


126
00:05:05,166 --> 00:05:09,700
And so with this, I guess I mean I've already done 
it on the picture but maybe I should mention here.

127
00:05:09,700 --> 00:05:12,066
Alice publishes

128
00:05:12,066 --> 00:05:13,900
e comma n.

129
00:05:13,900 --> 00:05:14,533


130
00:05:14,533 --> 00:05:17,133
So notice that e comma n 
is what's published, it's not

131
00:05:17,133 --> 00:05:21,333
p and q, it's not the - it's the product, it's 
just the product, whatever number this is.

132
00:05:21,333 --> 00:05:24,433
So in our case, we're going to publish…

133
00:05:24,433 --> 00:05:28,766
so in our example, maybe I'll put the 
numbers here. We're going to publish

134
00:05:28,766 --> 00:05:30,733
17,

135
00:05:30,733 --> 00:05:35,633
and this huge number. What is this? 6, 7,

136
00:05:35,633 --> 00:05:37,600
0,

137
00:05:37,600 --> 00:05:38,566


138
00:05:38,566 --> 00:05:41,966
7, 2,

139
00:05:41,966 --> 00:05:45,166
6, 0,

140
00:05:45,166 --> 00:05:46,133


141
00:05:46,133 --> 00:05:47,966
8, 1.

142
00:05:47,966 --> 00:05:52,333


143
00:05:52,333 --> 00:05:54,466
So that's what's being published.

144
00:05:54,466 --> 00:05:55,966


145
00:05:55,966 --> 00:05:58,466
Now Bob wants to send a message.

146
00:05:58,466 --> 00:06:01,133
So what’s Bob's message? 
So let's talk about Bob now.

147
00:06:01,133 --> 00:06:04,966


148
00:06:04,966 --> 00:06:07,766
Bob wants to send his message,

149
00:06:07,766 --> 00:06:09,066
M,

150
00:06:09,066 --> 00:06:11,033
an integer

151
00:06:11,033 --> 00:06:14,466
strictly between 1 and n.

152
00:06:14,466 --> 00:06:18,466


153
00:06:18,466 --> 00:06:21,400
So Bob wants to send his message, M,

154
00:06:21,400 --> 00:06:25,800
an integer strictly - not an integers,
an integer strictly between 1 and n.

155
00:06:25,800 --> 00:06:26,733


156
00:06:26,733 --> 00:06:29,366
So what's Bob going to do? 
Well Bob's going to compute -

157
00:06:29,366 --> 00:06:32,500
Bob's going to encrypt M. How 
is Bob going to encrypt M?

158
00:06:32,500 --> 00:06:34,733
Bob computes

159
00:06:34,733 --> 00:06:35,566


160
00:06:35,566 --> 00:06:39,033
C to the power -oops, 
M to the power of e.

161
00:06:39,033 --> 00:06:42,466
C which is equivalent to M 
to the power of e, I got it, 

162
00:06:42,466 --> 00:06:43,000


163
00:06:43,000 --> 00:06:44,733
mod n.

164
00:06:44,733 --> 00:06:47,733


165
00:06:47,733 --> 00:06:50,666
And we want 0 to be less 
than C to be less than n.

166
00:06:50,666 --> 00:06:54,600


167
00:06:54,600 --> 00:06:56,533
Capital C.

168
00:06:56,533 --> 00:06:58,066


169
00:06:58,066 --> 00:07:00,500
So Bob's going to compute this C,

170
00:07:00,500 --> 00:07:01,200


171
00:07:01,200 --> 00:07:03,633
and Bob's going to send it over.

172
00:07:03,633 --> 00:07:05,400


173
00:07:05,400 --> 00:07:07,400
Okay?

174
00:07:07,400 --> 00:07:08,400


175
00:07:08,400 --> 00:07:12,266
So let's do a couple of things, so
Bob's going to compute some…

176
00:07:12,266 --> 00:07:14,100


177
00:07:14,100 --> 00:07:17,066
so C, which is going to be congruent

178
00:07:17,066 --> 00:07:18,400


179
00:07:18,400 --> 00:07:21,766
to M to the e

180
00:07:21,766 --> 00:07:23,066


181
00:07:23,066 --> 00:07:24,766
mod n.

182
00:07:24,766 --> 00:07:29,300


183
00:07:29,300 --> 00:07:31,333
Alright, so

184
00:07:31,333 --> 00:07:34,533
we've added this to our picture and we're 
going to try to send C over in a minute,

185
00:07:34,533 --> 00:07:37,600
but first let's actually take an example. 
So here we're going to take M

186
00:07:37,600 --> 00:07:43,733
equals, I don't know, 1, 2, 3, 4,
5, 6, 7, let's say eight 1’s, okay?

187
00:07:43,733 --> 00:07:44,466


188
00:07:44,466 --> 00:07:47,833
For whatever reason he likes this 
number and he's going to send it, okay?

189
00:07:47,833 --> 00:07:49,066


190
00:07:49,066 --> 00:07:54,466
C we're going to compute to be M to the e mod n, so 
we can do that with this command called power mod.

191
00:07:54,466 --> 00:07:55,433


192
00:07:55,433 --> 00:07:59,566
M comma e comma n. So what 
will this do? This will produce 

193
00:07:59,566 --> 00:08:02,433
M to the e mod n. It's sort of intuitive,

194
00:08:02,433 --> 00:08:04,433
and we're going to print C.

195
00:08:04,433 --> 00:08:06,066


196
00:08:06,066 --> 00:08:11,033
Great, so C is this number 5120174[56],

197
00:08:11,033 --> 00:08:13,500
so 512 ish million. 

198
00:08:13,500 --> 00:08:15,400


199
00:08:15,400 --> 00:08:20,400
Okay, so Bob's computed this, 
now Bob's going to send C to Alice.

200
00:08:20,400 --> 00:08:24,033
Bob sends C to Alice.

201
00:08:24,033 --> 00:08:27,400
Oops sense C to Alice? How 
about sends C to Alice.

202
00:08:27,400 --> 00:08:30,133


203
00:08:30,133 --> 00:08:32,300
Bob sends C to Alice, so let's do that. So

204
00:08:32,300 --> 00:08:35,233
in our picture, Bob's going to send over

205
00:08:35,233 --> 00:08:36,166


206
00:08:36,166 --> 00:08:38,300
C.

207
00:08:38,300 --> 00:08:40,700


208
00:08:40,700 --> 00:08:43,800
So Bob sends over C,

209
00:08:43,800 --> 00:08:46,466
and remember here C is equal to

210
00:08:46,466 --> 00:08:47,900


211
00:08:47,900 --> 00:08:50,066
5, 1,

212
00:08:50,066 --> 00:08:54,033
2, 0, 1,

213
00:08:54,033 --> 00:08:57,266
7, 4, 5, 6.

214
00:08:57,266 --> 00:09:01,800


215
00:09:01,800 --> 00:09:06,700
So again notice that Eve gets to see 
C. So Eve doesn't know what M is,

216
00:09:06,700 --> 00:09:11,233
but Eve gets to see C, this 9 digit
number, and she gets to see e and n.

217
00:09:11,233 --> 00:09:11,800


218
00:09:11,800 --> 00:09:13,033
Okay?

219
00:09:13,033 --> 00:09:16,766
Notice that from this weird 
number 5120174[56], it's not 

220
00:09:16,766 --> 00:09:20,433
immediately obvious that the 
message was eight 1’s, okay?

221
00:09:20,433 --> 00:09:21,866


222
00:09:21,866 --> 00:09:25,233
Now Alice is over here, so now Alice has C, 
but Alice knows a couple other things, right?

223
00:09:25,233 --> 00:09:27,733
she knows p and q, she knows e, and

224
00:09:27,733 --> 00:09:31,833
she knows these things. These 
are part of her private keys.

225
00:09:31,833 --> 00:09:34,166


226
00:09:34,166 --> 00:09:37,500
So Alice receives…so what's
Alice going to do now?

227
00:09:37,500 --> 00:09:40,233


228
00:09:40,233 --> 00:09:44,500
Alice receives C and computes

229
00:09:44,500 --> 00:09:50,466
d such that e d is equivalent 
to 1 mod p minus 1

230
00:09:50,466 --> 00:09:51,333


231
00:09:51,333 --> 00:09:53,233
q minus 1.

232
00:09:53,233 --> 00:09:56,100


233
00:09:56,100 --> 00:09:58,333
So Alice receives C and computes this

234
00:09:58,333 --> 00:10:00,900
d. We'll see why this d is
important in a minute.

235
00:10:00,900 --> 00:10:04,233
d is going to be the inverse 
of e mod p minus 1 q minus 1.

236
00:10:04,233 --> 00:10:07,333
By the way, sanity check, 
right? Why does this exist?

237
00:10:07,333 --> 00:10:08,833


238
00:10:08,833 --> 00:10:10,700
Hopefully you've answered the question.

239
00:10:10,700 --> 00:10:14,300
This exists because the gcd of
e and p minus 1 q minus 1 is 1.

240
00:10:14,300 --> 00:10:16,633
Okay, so excellent.

241
00:10:16,633 --> 00:10:18,466
So let's throw this in.

242
00:10:18,466 --> 00:10:22,866
So she's going to compute 
d, d is the inverse.

243
00:10:22,866 --> 00:10:24,666
So let's - 

244
00:10:24,666 --> 00:10:27,500
d is going to be equal to power mod

245
00:10:27,500 --> 00:10:29,766


246
00:10:29,766 --> 00:10:33,466
e, minus 1, and

247
00:10:33,466 --> 00:10:36,233
p minus 1 times q minus 1.

248
00:10:36,233 --> 00:10:40,666


249
00:10:40,666 --> 00:10:44,800
d happens to be 118351661. So

250
00:10:44,800 --> 00:10:48,500
in our picture, e - Alice has this private key,

251
00:10:48,500 --> 00:10:51,700
d, so I'll write down private…

252
00:10:51,700 --> 00:10:58,233


253
00:10:58,233 --> 00:11:00,566
private d,

254
00:11:00,566 --> 00:11:01,733


255
00:11:01,733 --> 00:11:05,100
and again in our example it's 1, 1,

256
00:11:05,100 --> 00:11:06,566


257
00:11:06,566 --> 00:11:08,566
8,

258
00:11:08,566 --> 00:11:11,533
3, 5, 1,

259
00:11:11,533 --> 00:11:12,566


260
00:11:12,566 --> 00:11:15,700
6, 6, 1.

261
00:11:15,700 --> 00:11:19,200


262
00:11:19,200 --> 00:11:23,500
Now what's Alice going to do? 
Well Alice is going to compute…

263
00:11:23,500 --> 00:11:24,900


264
00:11:24,900 --> 00:11:27,933
Alice is going to compute 
C to the d. So then...

265
00:11:27,933 --> 00:11:30,666


266
00:11:30,666 --> 00:11:33,033
Alice now computes

267
00:11:33,033 --> 00:11:36,566
R, which is equivalent to 
C to the power of d,

268
00:11:36,566 --> 00:11:37,533


269
00:11:37,533 --> 00:11:40,000
and she's going to do this mod n.

270
00:11:40,000 --> 00:11:41,466


271
00:11:41,466 --> 00:11:44,333
Alice now computes R is 
congruent to C to the d mod n.

272
00:11:44,333 --> 00:11:45,533


273
00:11:45,533 --> 00:11:49,800
So I'm going to compute 
R is equal to power mod 

274
00:11:49,800 --> 00:11:53,266
C, d, and n.

275
00:11:53,266 --> 00:11:54,600


276
00:11:54,600 --> 00:11:58,333
Print R. Okay now is a 
good time to ask yourself,

277
00:11:58,333 --> 00:11:58,866


278
00:11:58,866 --> 00:12:02,800
“What value is the computer 
going to print out here for R?”

279
00:12:02,800 --> 00:12:06,466
So if you understand everything, you should know 
exactly what's going to happen here, okay? So

280
00:12:06,466 --> 00:12:09,600
pause the video, think about 
it, and then come back.

281
00:12:09,600 --> 00:12:11,500
Hopefully you're back,

282
00:12:11,500 --> 00:12:13,833
and what should the the answer 
be? The answer should be M.

283
00:12:13,833 --> 00:12:16,600
So if I did everything correctly, 
the answer should be eight 1’s. 

284
00:12:16,600 --> 00:12:17,266


285
00:12:17,266 --> 00:12:20,366
Let's hope for the best. Okay, there we go,

286
00:12:20,366 --> 00:12:22,233
okay, that's fantastic.

287
00:12:22,233 --> 00:12:23,100


288
00:12:23,100 --> 00:12:25,566
So this R that you compute 
when you compute C to the d - 

289
00:12:25,566 --> 00:12:28,466
so maybe I'll just put this in the 
picture so that it’s complete.

290
00:12:28,466 --> 00:12:29,933


291
00:12:29,933 --> 00:12:32,666
R is congruent to

292
00:12:32,666 --> 00:12:35,066
C to the d

293
00:12:35,066 --> 00:12:37,300


294
00:12:37,300 --> 00:12:39,366
mod

295
00:12:39,366 --> 00:12:40,466


296
00:12:40,466 --> 00:12:42,300
n,

297
00:12:42,300 --> 00:12:44,533


298
00:12:44,533 --> 00:12:46,266
and everything…

299
00:12:46,266 --> 00:12:49,466
and this R that she computes is going 
to be the original message. So Eve

300
00:12:49,466 --> 00:12:52,266
is going to have a very 
difficult time figuring out

301
00:12:52,266 --> 00:12:56,133
what the original message is.
She has to solve some sort of

302
00:12:56,133 --> 00:12:59,000
discrete log problem, or she has to try to

303
00:12:59,000 --> 00:13:02,733
figure out what d is. Either 
way, it's going to be tricky.

304
00:13:02,733 --> 00:13:06,400
Given this number, it's tough 
to know that it came from

305
00:13:06,400 --> 00:13:11,366
11111111, right? It's not easy to
solve the problem - basically,

306
00:13:11,366 --> 00:13:14,266
right, if you could take logarithms, 
this would be easy to do,

307
00:13:14,266 --> 00:13:17,333
but you can't do that with
congruences. It's not that

308
00:13:17,333 --> 00:13:20,766
obvious because of the 
periodicity properties.

309
00:13:20,766 --> 00:13:21,566


310
00:13:21,566 --> 00:13:26,600
This gcd of e and p minus 1 q minus 1 
equals 1, that's important in the proof, right?

311
00:13:26,600 --> 00:13:29,033
The reason why this R 
works out is because

312
00:13:29,033 --> 00:13:32,466
this gcd is 1, p and q are co-prime, 
you use a combination of

313
00:13:32,466 --> 00:13:36,466
Chinese Remainder Theorem and 
Fermat's Little Theorem to get this going.

314
00:13:36,466 --> 00:13:39,100


315
00:13:39,100 --> 00:13:42,600
And that's that. So by the way, notice 
that all these computations took like

316
00:13:42,600 --> 00:13:45,633
instantly, right, and it didn't matter…

317
00:13:45,633 --> 00:13:46,600


318
00:13:46,600 --> 00:13:49,700
it didn't matter what numbers I used, 
right? I mean like here if I changed 17,

319
00:13:49,700 --> 00:13:52,866
let me change 17 to something 
maybe a little bit bigger.

320
00:13:52,866 --> 00:13:57,133
Next prime 12345678, I don’t know, 
let’s use another new prime, 

321
00:13:57,133 --> 00:13:59,166
because it's going to be co-prime, okay?

322
00:13:59,166 --> 00:14:05,966
So there you go. So this is going to be a huge number, 
right? So 12345701 happens to be the next prime.

323
00:14:05,966 --> 00:14:08,933
So now if we run these computations,

324
00:14:08,933 --> 00:14:11,933
so M to the e, very quick. 

325
00:14:11,933 --> 00:14:16,133
That happened instantly even though the 
number was some huge 8  digit number,

326
00:14:16,133 --> 00:14:18,633
it's still computed M to
the e mod n in a second.

327
00:14:18,633 --> 00:14:19,433


328
00:14:19,433 --> 00:14:22,233
d is the power mod. Boom instantly, okay?

329
00:14:22,233 --> 00:14:26,600
So this inverse is really quick to compute. 
How do we compute the inverse quickly?

330
00:14:26,600 --> 00:14:28,833
The Extended Euclidean Algorithm.

331
00:14:28,833 --> 00:14:31,000
And that's - I don't actually 
know what's going on.

332
00:14:31,000 --> 00:14:33,000
You can actually look what's
going on under the hood in Sage,

333
00:14:33,000 --> 00:14:36,200
but I presume that's what's happening, 
some sort of nice algorithm like that,

334
00:14:36,200 --> 00:14:36,700


335
00:14:36,700 --> 00:14:38,733
and then

336
00:14:38,733 --> 00:14:41,000
the R value is still the same, okay? So

337
00:14:41,000 --> 00:14:44,366
you can change the e to make it more
complicated or simpler it doesn't matter.

338
00:14:44,366 --> 00:14:46,633
The math is still going to work out.

339
00:14:46,633 --> 00:14:48,966
Just so that we have a nice

340
00:14:48,966 --> 00:14:50,266


341
00:14:50,266 --> 00:14:53,633
matching with the picture, 
I'm going to go back to 17.

342
00:14:53,633 --> 00:14:54,766


343
00:14:54,766 --> 00:14:56,966
We talked a little bit in class 
about which e’s to use.

344
00:14:56,966 --> 00:14:59,733
You probably want to use 
something bigger than 17.

345
00:14:59,733 --> 00:15:02,733
You probably want something so
that 2 to the e is bigger than n,

346
00:15:02,733 --> 00:15:06,166
just so that you can't take nth roots of 
the message that would be kind of silly.

347
00:15:06,166 --> 00:15:07,266


348
00:15:07,266 --> 00:15:09,833
So you actually want to do a 
reduction is what I'm saying,

349
00:15:09,833 --> 00:15:11,100


350
00:15:11,100 --> 00:15:13,166
but that's it. That's RSA.

351
00:15:13,166 --> 00:15:15,933
So hopefully this gives you an idea of

352
00:15:15,933 --> 00:15:18,300
how to use

353
00:15:18,300 --> 00:15:22,333
RSA effectively, and how you can go about 

354
00:15:22,333 --> 00:15:24,033
sending messages using RSA.

355
00:15:24,033 --> 00:15:27,633
This is basically the entire encryption scheme.
The only thing that's missing is the proof

356
00:15:27,633 --> 00:15:29,200
that R is equal to M,

357
00:15:29,200 --> 00:15:33,500
but hopefully the example gives you a little bit 
of an insight as to why that might be the case.

358
00:15:33,500 --> 00:15:34,433


359
00:15:34,433 --> 00:15:36,733
Alright thank you very much 
for your time, hope this helped.