1
00:00:00,000 --> 00:00:03,200
Hello everyone. Welcome to Week 9

2
00:00:03,200 --> 00:00:05,733
of Carmen's Core Concepts, 
my name is Carmen Bruni.

3
00:00:05,733 --> 00:00:09,333
In this video, this is part 1 of Week 9,

4
00:00:09,333 --> 00:00:11,166
we're going to talk about RSA

5
00:00:11,166 --> 00:00:14,833
which is an encryption scheme, a 
public key cryptography scheme,

6
00:00:14,833 --> 00:00:15,733


7
00:00:15,733 --> 00:00:19,800
and it's very well-known, very 
well-used still, even though it's

8
00:00:19,800 --> 00:00:21,800
somewhat…40 years old or so.

9
00:00:21,800 --> 00:00:24,700
RSA stands for Rivest, 
Shamir, and Aldeman,

10
00:00:24,700 --> 00:00:27,766
the 3 people who created the algorithm.

11
00:00:27,766 --> 00:00:29,000


12
00:00:29,000 --> 00:00:32,000
Something to keep in mind, so I 
do want to say something, that

13
00:00:32,000 --> 00:00:34,733
this is an RSA video. There 
are lots out there, this isn't

14
00:00:34,733 --> 00:00:36,766
unique by any stretch
of the imagination.

15
00:00:36,766 --> 00:00:39,366
I don't even claim that this is 
the best video on RSA out there.

16
00:00:39,366 --> 00:00:43,666
There are probably others that 
are much, much more well…

17
00:00:43,666 --> 00:00:45,100


18
00:00:45,100 --> 00:00:47,766
practiced, rehearsed, 
well-informed, whatever.

19
00:00:47,766 --> 00:00:48,933


20
00:00:48,933 --> 00:00:52,300
What I do want to say though is that I don't know 
of any video that does exactly this approach,

21
00:00:52,300 --> 00:00:55,600
and the approach that I'm going to 
take is that I'm going to talk about why

22
00:00:55,600 --> 00:00:59,133
RSA needs two primes as
opposed to just having one.

23
00:00:59,133 --> 00:01:01,966
So I'm going to try to - so what I'm 
going to do is I'm going to explain

24
00:01:01,966 --> 00:01:03,533
like an RSA with one prime,

25
00:01:03,533 --> 00:01:05,733
that's going to be called 
an exponentiation cipher,

26
00:01:05,733 --> 00:01:08,433
and then I'm going to talk about 
what happens when we have 2 primes.

27
00:01:08,433 --> 00:01:09,500


28
00:01:09,500 --> 00:01:12,400
So let's get started, let's
actually start by recalling

29
00:01:12,400 --> 00:01:14,933
the public key cryptography scheme.

30
00:01:14,933 --> 00:01:18,400
So suppose Alice and Bob want to share a 
message, but there's an eavesdropper, Eve,

31
00:01:18,400 --> 00:01:20,366
watching their communications, okay,

32
00:01:20,366 --> 00:01:24,000
and in our situation, we're going to 
assume that Eve is just looking

33
00:01:24,000 --> 00:01:27,600
at the insecure channel
between Alice and Bob.

34
00:01:27,600 --> 00:01:30,100
So Alice will publish some public information,

35
00:01:30,100 --> 00:01:32,266
and Bob will try to send
Alice a message by

36
00:01:32,266 --> 00:01:34,600
encrypting this message 
using the public information,

37
00:01:34,600 --> 00:01:38,800
and Eve will be able to see the public
information and the encrypted message, C.

38
00:01:38,800 --> 00:01:39,700


39
00:01:39,700 --> 00:01:44,000
And Alice’s job is going to be to create 
a scheme where she can decode

40
00:01:44,000 --> 00:01:48,000
the message sent from Bob, 
and so that Eve also cannot

41
00:01:48,000 --> 00:01:49,766
decode the message.

42
00:01:49,766 --> 00:01:51,266


43
00:01:51,266 --> 00:01:53,033
How are we going to do it? 
We're going to try to do that

44
00:01:53,033 --> 00:01:55,233
first by an exponentiation cipher, okay?

45
00:01:55,233 --> 00:01:57,400
And in an exponentiation 
cipher, so maybe

46
00:01:57,400 --> 00:02:00,166
a little bit of thought before we go
into this, exponentiation cipher

47
00:02:00,166 --> 00:02:02,233
you should be thinking, 
“Okay, I need to take

48
00:02:02,233 --> 00:02:05,266
exponents somewhere. I need to do

49
00:02:05,266 --> 00:02:07,466
an exponentiation at some point,”

50
00:02:07,466 --> 00:02:11,133
and it turns out that that's true. We do 
need to do exponentiation, which we will

51
00:02:11,133 --> 00:02:13,266
see where that comes 
into play in a minute.

52
00:02:13,266 --> 00:02:15,366
So in this encryption scheme,

53
00:02:15,366 --> 00:02:17,200
Alice is going to choose a large prime p,

54
00:02:17,200 --> 00:02:20,533
and an integer e satisfying e 
is between 1 and p minus 1,

55
00:02:20,533 --> 00:02:24,000
and the gcd of e and 
p minus 1 is 1, okay?

56
00:02:24,000 --> 00:02:25,500


57
00:02:25,500 --> 00:02:27,833
So e’s a co-prime to p minus 1,

58
00:02:27,833 --> 00:02:30,000
and it's between 1 and p minus 1.

59
00:02:30,000 --> 00:02:30,966


60
00:02:30,966 --> 00:02:33,300
Alice then makes the 
pair, e and p, public

61
00:02:33,300 --> 00:02:36,100
and she's going to compute 
her private key, d,

62
00:02:36,100 --> 00:02:39,766
and her private key, d, satisfies 1 is 
less than d is less than p minus 1,

63
00:02:39,766 --> 00:02:43,266
and e d is congruent 
to 1 mod p minus 1.

64
00:02:43,266 --> 00:02:44,000


65
00:02:44,000 --> 00:02:46,433
So why do we not want to 
choose p minus 1 here for e?

66
00:02:46,433 --> 00:02:49,666
And the reason why is because of this. 
So if you choose e to be p minus 1,

67
00:02:49,666 --> 00:02:54,133
then d is also p minus 1 and you'd
like e and d to be distinct. So,

68
00:02:54,133 --> 00:02:56,866
we're going to just avoid that by 
just not choosing e to be p minus 1.

69
00:02:56,866 --> 00:02:57,600


70
00:02:57,600 --> 00:02:59,766
We also don't want to choose e 
to be 1, because then we're not

71
00:02:59,766 --> 00:03:02,100
actually going to be encrypting 
anything. We're going to be taking

72
00:03:02,100 --> 00:03:05,800
a message to the power of e, and 
so if e is 1, that's kind of boring.

73
00:03:05,800 --> 00:03:06,900


74
00:03:06,900 --> 00:03:08,200
Okay.

75
00:03:08,200 --> 00:03:10,400
Something to note, that 
even if p is a large prime,

76
00:03:10,400 --> 00:03:14,300
the inverse of e can be computed very 
quickly using the Extended Euclidean Algorithm.

77
00:03:14,300 --> 00:03:15,266


78
00:03:15,266 --> 00:03:18,300
The reason why we require the 
gcd of e and p minus 1 to be 1

79
00:03:18,300 --> 00:03:22,233
is so that e is invertible mod p minus 1, so 
that's something to keep in mind as well.

80
00:03:22,233 --> 00:03:23,966


81
00:03:23,966 --> 00:03:27,900
So we need the inverse of e mod
p minus 1 to exists, we'll see why

82
00:03:27,900 --> 00:03:29,500
in a minute.

83
00:03:29,500 --> 00:03:30,666


84
00:03:30,666 --> 00:03:34,566
To send a message, M, Alice - 
to Alice… to send a message,

85
00:03:34,566 --> 00:03:36,600
M, to Alice, and this 
message, M, is going to be

86
00:03:36,600 --> 00:03:39,166
an integer between 0 
and p minus 1 inclusive.

87
00:03:39,166 --> 00:03:41,466
Bob is going to compute a ciphertext,

88
00:03:41,466 --> 00:03:44,900
C, satisfying 0 is less than 
or equal to C is less than p,

89
00:03:44,900 --> 00:03:48,166
and C is congruent to 
M to the e mod p,

90
00:03:48,166 --> 00:03:50,733
and Bob will send C to Alice.

91
00:03:50,733 --> 00:03:51,766


92
00:03:51,766 --> 00:03:54,133
So keep in mind, what 
can Eve see? Eve

93
00:03:54,133 --> 00:03:57,033
can see e, p, and C, which 
we'll see in the next diagram.

94
00:03:57,033 --> 00:03:59,400


95
00:03:59,400 --> 00:04:01,900
Now what is Alice going to do to decrypt?

96
00:04:01,900 --> 00:04:04,966
Alice is going to take that message, C,

97
00:04:04,966 --> 00:04:09,000
and compute C to the d mod p with 0 
less than or equal to R is less than p.

98
00:04:09,000 --> 00:04:10,066


99
00:04:10,066 --> 00:04:11,400
So...

100
00:04:11,400 --> 00:04:13,466
here's the encryption scheme. 
What things do we need to know?

101
00:04:13,466 --> 00:04:16,633
So first thing we need to do is we need 
to prove something about R. So R is

102
00:04:16,633 --> 00:04:18,966
congruent to C to the d, we need 
to prove that R is congruent to M,

103
00:04:18,966 --> 00:04:23,533
that’s something we need to do. It's not too 
hard, but we will need to actually compute that.

104
00:04:23,533 --> 00:04:24,633


105
00:04:24,633 --> 00:04:27,533
If Bob chooses C equals 0, then

106
00:04:27,533 --> 00:04:31,500
M to the e is 0. If Bob chooses 
C is 1, then M to the e is 1. 

107
00:04:31,500 --> 00:04:35,400
Those are kind of bad messages to pick, so maybe 
you want to restrict those, maybe you don’t.

108
00:04:35,400 --> 00:04:37,900
The scheme works with those
two things, so I'm going to just

109
00:04:37,900 --> 00:04:40,233
include them just for a theoretical sense.

110
00:04:40,233 --> 00:04:42,233
but you probably want 
to avoid them in practice.

111
00:04:42,233 --> 00:04:43,800


112
00:04:43,800 --> 00:04:47,400
Okay, so, let's head to the proof.

113
00:04:47,400 --> 00:04:49,966
Oh let's head to the diagram 
before we head to the proof. So

114
00:04:49,966 --> 00:04:52,133
I like to draw the diagram
just to remind us of 

115
00:04:52,133 --> 00:04:55,933
what the situation is. So Alice 
computed e and p, made that public,

116
00:04:55,933 --> 00:05:00,300
computed a private d which is 
the inverse of e mod p minus 1.

117
00:05:00,300 --> 00:05:01,500


118
00:05:01,500 --> 00:05:04,666
e and p is public, Eve and 
Bob know it, Bob computes…

119
00:05:04,666 --> 00:05:07,233
Bob takes his message, M, 
his private message, M,

120
00:05:07,233 --> 00:05:09,066
an integer between 0 and p minus 1,

121
00:05:09,066 --> 00:05:12,233
and computes C, which 
is M to the e mod p. 

122
00:05:12,233 --> 00:05:13,266


123
00:05:13,266 --> 00:05:15,733
Bob and sends C across
the insecure channel,

124
00:05:15,733 --> 00:05:18,266
so Eve knows e, p, and C.

125
00:05:18,266 --> 00:05:19,566


126
00:05:19,566 --> 00:05:23,066
Now Alice gets the C, and Alice
knows d, so Alice is going to

127
00:05:23,066 --> 00:05:25,733
compute R is congruent 
to C to the d mod p.

128
00:05:25,733 --> 00:05:26,666


129
00:05:26,666 --> 00:05:29,966
Now something to think 
about in this scheme,

130
00:05:29,966 --> 00:05:33,500
so Eve gets e, p, and C, so 
something to note is okay well

131
00:05:33,500 --> 00:05:36,733
if Eve has C, can she compute M?

132
00:05:36,733 --> 00:05:39,433
She knows C and e, 
so can she compute -

133
00:05:39,433 --> 00:05:43,466
basically what she's trying to ask is, “Can 
I compute the e-th root of C mod p?”

134
00:05:43,466 --> 00:05:46,066
And it turns out that this happens
to be a difficult problem.

135
00:05:46,066 --> 00:05:48,166
Just to see an example,

136
00:05:48,166 --> 00:05:51,400
suppose I told you that

137
00:05:51,400 --> 00:05:55,433
M to the [6] was congruent to 9 mod 11,

138
00:05:55,433 --> 00:05:59,266
and I asked you to determine what M
was, okay? How would you do that?

139
00:05:59,266 --> 00:06:00,666


140
00:06:00,666 --> 00:06:04,000
I mean really the only way that you're 
going to be able to even try it is

141
00:06:04,000 --> 00:06:06,400
by just plugging in values for M.

142
00:06:06,400 --> 00:06:07,666


143
00:06:07,666 --> 00:06:10,300
There's a lot of possible 
values for M if p is large,

144
00:06:10,300 --> 00:06:12,333
so this doesn't seem like 
a very efficient attack, okay?

145
00:06:12,333 --> 00:06:16,400
Now 11 is small enough that you could probably 
reason that I believe the answer should be 2.

146
00:06:16,400 --> 00:06:20,800
2 to the 6 is 64, and 64 is 
congruent to 9 mod 11.

147
00:06:20,800 --> 00:06:24,966
So that one's fairly easy, but you could imagine, 
like I mean if I ask you the same question

148
00:06:24,966 --> 00:06:28,000
M to the power of 6 is congruent to…

149
00:06:28,000 --> 00:06:28,966


150
00:06:28,966 --> 00:06:31,533
who knows… 5 mod 11.

151
00:06:31,533 --> 00:06:34,966
What's the answer? I don't know. I mean so 
you can imagine the situation being very difficult. 

152
00:06:34,966 --> 00:06:38,466
This is a tough problem to solve;
computing e-th roots mod p.

153
00:06:38,466 --> 00:06:39,466


154
00:06:39,466 --> 00:06:41,133
At least that’s what we believe.

155
00:06:41,133 --> 00:06:42,000


156
00:06:42,000 --> 00:06:43,633
Okay.

157
00:06:43,633 --> 00:06:44,533


158
00:06:44,533 --> 00:06:46,133
So, big proposition here. So we're going to

159
00:06:46,133 --> 00:06:48,366
prove that R is congruent to M mod p,

160
00:06:48,366 --> 00:06:51,500
and from this we're going to
conclude that R equals M

161
00:06:51,500 --> 00:06:53,433
because of the
restrictions on R and M.

162
00:06:53,433 --> 00:06:55,900
R and M are both less 
than p and non-negative,

163
00:06:55,900 --> 00:06:58,733
okay, so that will force them to be 
equal if they're congruent mod p.

164
00:06:58,733 --> 00:06:59,533


165
00:06:59,533 --> 00:07:02,800
Take a minute, pause the
video here, try to prove this.

166
00:07:02,800 --> 00:07:06,500
If you can prove this, it shows that you - 
if you prove this without going back in the

167
00:07:06,500 --> 00:07:09,300
slides, it shows that you really
understand exponentiation ciphers,

168
00:07:09,300 --> 00:07:12,300
so hopefully you can do that. If 
not, go back to the previous slides,

169
00:07:12,300 --> 00:07:16,333
check out exponentiation ciphers, and see if 
you can prove that R is congruent to M mod p.

170
00:07:16,333 --> 00:07:17,666


171
00:07:17,666 --> 00:07:20,000
Now that you’ve paused the 
video, hopefully tried it,

172
00:07:20,000 --> 00:07:22,000
let's take a look at the proof. 

173
00:07:22,000 --> 00:07:22,733


174
00:07:22,733 --> 00:07:25,300
The proof, it needs to 
be split up into 2 cases,

175
00:07:25,300 --> 00:07:28,866
which might not be obvious at first but 
it will be obvious once we do it, okay?

176
00:07:28,866 --> 00:07:31,366
If p divides M, everything 
is 0 and we're done.

177
00:07:31,366 --> 00:07:33,900
So we might as well assume 
that p doesn't divide M;

178
00:07:33,900 --> 00:07:36,000
get to the interesting case.

179
00:07:36,000 --> 00:07:40,533
So from here, recall that e d is
congruent to 1 mod p minus 1,

180
00:07:40,533 --> 00:07:42,466
and using this, what do we have?

181
00:07:42,466 --> 00:07:45,600
So we have that R is congruent 
to C to the d mod p, 

182
00:07:45,600 --> 00:07:46,333


183
00:07:46,333 --> 00:07:49,533
which is congruent to M to the e to 
the d mod p, by the definition of C,

184
00:07:49,533 --> 00:07:52,500
remember C is the same 
as M to the e mod p.

185
00:07:52,500 --> 00:07:56,233
M to the e the d is the same 
as M to the e d mod p,

186
00:07:56,233 --> 00:07:59,633
and M to the e d, well e d was 
congruent to 1 mod p minus 1,

187
00:07:59,633 --> 00:08:02,133
so we can actually use one of the 
corollaries to Fermat's Little Theorem

188
00:08:02,133 --> 00:08:05,466
which says that well if e d is congruent 
to 1 mod p minus 1, then M

189
00:08:05,466 --> 00:08:09,633
to the e d is congruent to M mod p,
provided that the gcd of M and p is 1,

190
00:08:09,633 --> 00:08:12,000
which is the case 
if p doesn't divide M.

191
00:08:12,000 --> 00:08:12,933


192
00:08:12,933 --> 00:08:14,166
And we're done.

193
00:08:14,166 --> 00:08:16,000
So it's actually a really, really short proof

194
00:08:16,000 --> 00:08:19,966
and it uses Fermat's Little Theorem, which is cool. 
This is one of the reasons why we needed it.

195
00:08:19,966 --> 00:08:20,666


196
00:08:20,666 --> 00:08:23,566
So here we have it, okay, maybe 
I'll just end it at that, okay?

197
00:08:23,566 --> 00:08:26,933
So then therefore, R equals M by that 
argument that I mentioned at the beginning.

198
00:08:26,933 --> 00:08:30,300
This proves that exponentiation 
ciphers work. Okay?

199
00:08:30,300 --> 00:08:31,166


200
00:08:31,166 --> 00:08:32,533
So they work.

201
00:08:32,533 --> 00:08:35,633
Bob can send a message, 
Alice can decrypt it.

202
00:08:35,633 --> 00:08:39,166
So that's the good news, the 
good news is that this works.

203
00:08:39,166 --> 00:08:41,766
The bad and the ugly is that well…

204
00:08:41,766 --> 00:08:42,900


205
00:08:42,900 --> 00:08:46,066
the bad and the ugly actually
are kind of the same thing I guess.

206
00:08:46,066 --> 00:08:49,266
Eve can compute d just 
as easily as Alice, right?

207
00:08:49,266 --> 00:08:51,833
If Eve knows p and e, 
there's no reason why

208
00:08:51,833 --> 00:08:55,166
Eve can't compute the 
inverse of e mod p minus 1,

209
00:08:55,166 --> 00:09:00,000
right, because Eve knows p, so therefore 
she knows p minus 1. That's not hard.

210
00:09:00,000 --> 00:09:00,866


211
00:09:00,866 --> 00:09:03,000
So our scheme is not 
secure, this is pretty bad.

212
00:09:03,000 --> 00:09:07,200
So you actually wouldn't want to use 
this scheme in practice because well…

213
00:09:07,200 --> 00:09:09,033
it's not secure.

214
00:09:09,033 --> 00:09:09,833


215
00:09:09,833 --> 00:09:12,666
So how do we rectify this problem?
How do we solve this problem?

216
00:09:12,666 --> 00:09:13,700


217
00:09:13,700 --> 00:09:18,133
What we can do is we can include 
information instead of about one prime,

218
00:09:18,133 --> 00:09:21,400
we can include information about two primes.

219
00:09:21,400 --> 00:09:24,233
It might not be obvious why that 
matters, right? So before we used

220
00:09:24,233 --> 00:09:26,766
one prime, the scheme 
works but it's not secure,

221
00:09:26,766 --> 00:09:31,533
and if we include two primes, how 
does that make the scheme secure?

222
00:09:31,533 --> 00:09:32,333


223
00:09:32,333 --> 00:09:35,133
Something to think about. Think about it while
we're going through the scheme, okay,

224
00:09:35,133 --> 00:09:37,966
that's what RSA does though. 
It's a single prime exponentia-

225
00:09:37,966 --> 00:09:40,933
so a single prime exponentiation 
cipher that we saw.

226
00:09:40,933 --> 00:09:43,900
RSA is like a dual prime or two prime

227
00:09:43,900 --> 00:09:46,066
exponentiation cipher.

228
00:09:46,066 --> 00:09:48,066
So let's think about why 
this is going to work.