1
00:00:00,000 --> 00:00:02,866
Now let's get to the issue of security.

2
00:00:02,866 --> 00:00:06,466
Is this scheme more
secure than single prime…

3
00:00:06,466 --> 00:00:07,366


4
00:00:07,366 --> 00:00:08,633
exponentiation cipher?

5
00:00:08,633 --> 00:00:10,766
The answer is yes, of course.

6
00:00:10,766 --> 00:00:13,400
Not just because of its name 
but because it's actually secure.

7
00:00:13,400 --> 00:00:14,100


8
00:00:14,100 --> 00:00:16,466
Can Eve compute d?

9
00:00:16,466 --> 00:00:20,000
And before we said, “Well Eve 
had e and p, and so Eve

10
00:00:20,000 --> 00:00:24,966
could compute p minus 1, so Eve could 
compute the inverse of e mod p minus 1.”

11
00:00:24,966 --> 00:00:28,000
But now, Eve only has the product p q,

12
00:00:28,000 --> 00:00:31,600
so computing p minus 1 times q minus 1

13
00:00:31,600 --> 00:00:34,500
when you only have p q 
is actually quite difficult.

14
00:00:34,500 --> 00:00:36,566
You either have to factor n,

15
00:00:36,566 --> 00:00:41,300
which is a very hard problem, or do something 
else that nobody's thought of at this point.

16
00:00:41,300 --> 00:00:42,833


17
00:00:42,833 --> 00:00:46,900
Nobody knows how to do this problem. To 
get p minus 1 times q minus 1 from p q.

18
00:00:46,900 --> 00:00:47,766


19
00:00:47,766 --> 00:00:50,533
This problem we believe is hard. 
There's no proof of this fact.

20
00:00:50,533 --> 00:00:55,266
There's evidence there’s…you 
know, we believe that it's hard,

21
00:00:55,266 --> 00:00:58,466
but proving that a 
problem is hard is not…

22
00:00:58,466 --> 00:00:59,933
it's not easy.

23
00:00:59,933 --> 00:01:03,333
Basically the proof that a problem is 
hard is that it hasn't been done before,

24
00:01:03,333 --> 00:01:05,133
is basically the proof.

25
00:01:05,133 --> 00:01:06,466


26
00:01:06,466 --> 00:01:08,400
It's not a great proof, but

27
00:01:08,400 --> 00:01:11,900
anyways we do believe that
factoring numbers is hard.

28
00:01:11,900 --> 00:01:14,233
Eve could also break RSA if 
she can solve the problem of

29
00:01:14,233 --> 00:01:16,300
computing M given 
M to the e mod n,

30
00:01:16,300 --> 00:01:18,366
but again we know this is a hard 
problem as well, right? Computing

31
00:01:18,366 --> 00:01:20,466
the e-th root of M to the 
e is not so easy mod n.

32
00:01:20,466 --> 00:01:22,200


33
00:01:22,200 --> 00:01:26,066
So let phi of n be the
Euler Phi Function.

34
00:01:26,066 --> 00:01:26,833


35
00:01:26,833 --> 00:01:30,600
Sometimes this is denoted by varphi, 
sometimes it's just denoted by phi.

36
00:01:30,600 --> 00:01:33,966
I think I denote it by phi later 
instead of varphi in LaTex.

37
00:01:33,966 --> 00:01:36,466
Either way is fine, people 
will know what you mean.

38
00:01:36,466 --> 00:01:39,866
Note that, in this case - so I'm not going 
to define what the Euler Phi Function is,

39
00:01:39,866 --> 00:01:44,133
but I am going to say that in the case when 
n equals p q is a product of distinct primes,

40
00:01:44,133 --> 00:01:47,533
then phi of n is equal to p 
minus 1 times q minus 1.

41
00:01:47,533 --> 00:01:48,600


42
00:01:48,600 --> 00:01:50,500
It's important that they're distinct.

43
00:01:50,500 --> 00:01:53,400
This isn't true about this function 
if they're not distinct primes.

44
00:01:53,400 --> 00:01:54,400


45
00:01:54,400 --> 00:01:58,133
How does Alice choose primes p and q?

46
00:01:58,133 --> 00:02:00,533
Well we know that they 
must be distinct, okay?

47
00:02:00,533 --> 00:02:01,266


48
00:02:01,266 --> 00:02:04,000
That’s something that we saw in the 
algorithm - in the proof before, right?

49
00:02:04,000 --> 00:02:06,900
We'd split the modulus at the end, or use
the Chinese Remainder Theorem,

50
00:02:06,900 --> 00:02:09,766
so we needed p and q to be distinct.

51
00:02:09,766 --> 00:02:11,966
How does Alice choose these primes? 
Well it turns out that the way

52
00:02:11,966 --> 00:02:14,200
to choose them is 
actually be very silly.

53
00:02:14,200 --> 00:02:16,566
If you want to choose a large 
prime number, turns out that

54
00:02:16,566 --> 00:02:18,966
you should just choose a large number.

55
00:02:18,966 --> 00:02:20,600
We should be a little bit smarter,

56
00:02:20,600 --> 00:02:24,300
let's choose a large odd number, since we 
know that large even numbers aren’t prime.

57
00:02:24,300 --> 00:02:24,933


58
00:02:24,933 --> 00:02:27,900
So we choose a large odd number,

59
00:02:27,900 --> 00:02:31,100
it turns out that if we choose 
enough of these numbers, that

60
00:02:31,100 --> 00:02:34,700
we're going to eventually pick a prime. 
Now how many we have to choose?

61
00:02:34,700 --> 00:02:35,866


62
00:02:35,866 --> 00:02:37,500
There's an argument using 
the Prime Number Theorem

63
00:02:37,500 --> 00:02:40,200
which off the top of my 
head I believe says

64
00:02:40,200 --> 00:02:45,300
if you have…let's say p is 100, and you want to 
know if you can find it a hundred digit prime.

65
00:02:45,300 --> 00:02:48,800
If you pick about…I think 
it's around the 75 mark,

66
00:02:48,800 --> 00:02:53,100
it's not exact, but if you pick 
around 75 big odd numbers,

67
00:02:53,100 --> 00:02:53,700


68
00:02:53,700 --> 00:02:58,100
that's going to be enough to have like a
50/50 chance that one of them is prime.

69
00:02:58,100 --> 00:02:58,866


70
00:02:58,866 --> 00:03:02,100
That’s pretty good, and it's not too 
hard to pick 75 large odd numbers.

71
00:03:02,100 --> 00:03:06,000
The one thing you might want to ask is, “Well 
how hard is it to check if a number is prime?”

72
00:03:06,000 --> 00:03:08,933
So clearly it must not 
be too hard based on

73
00:03:08,933 --> 00:03:12,000
what I just told you, right, and it turns 
out that it's not. There's actually

74
00:03:12,000 --> 00:03:16,800
quick-ish algorithms that will determine 
if a large number is prime or not.

75
00:03:16,800 --> 00:03:20,000
They're not insanely fast, but they're good.

76
00:03:20,000 --> 00:03:21,566


77
00:03:21,566 --> 00:03:23,566
So…maybe let me say this,

78
00:03:23,566 --> 00:03:26,266
in fact they're even better if you allow 
for something called probable primes,

79
00:03:26,266 --> 00:03:28,500
which are primes that are 
highly likely to be prime,

80
00:03:28,500 --> 00:03:31,833
let’s say 99.9999% likely to be prime,

81
00:03:31,833 --> 00:03:35,266
whatever that means. I'm not going 
to justify what that means, but

82
00:03:35,266 --> 00:03:39,866
this is an active area of research: probable 
primes things like this. Check this out online.

83
00:03:39,866 --> 00:03:42,933
There's some pretty interesting stuff. 
I believe all of that is true though.

84
00:03:42,933 --> 00:03:44,833
My numbers might be off a 
little bit, especially with the

85
00:03:44,833 --> 00:03:46,533
Prime Number Theorem 
argument off the top my head,

86
00:03:46,533 --> 00:03:49,933
but I believe that's roughly correct. Again you 
should check that out, if you want you can google

87
00:03:49,933 --> 00:03:52,000
that argument. I'm sure somebody's done it.

88
00:03:52,000 --> 00:03:53,033


89
00:03:53,033 --> 00:03:56,166
What if Eve wasn't just 
a passive eavesdropper?

90
00:03:56,166 --> 00:03:58,300
So what if Eve could change the data?

91
00:03:58,300 --> 00:04:01,066
So instead, let's say Alice 
publishes her public key

92
00:04:01,066 --> 00:04:04,800
and Eve says, “No, no, I don't like that public 
key. I'm going to publish my public key

93
00:04:04,800 --> 00:04:07,800
and pretend that I'm Alice,” and 
then Bob's going to encrypt using

94
00:04:07,800 --> 00:04:09,533
Eve's public key,

95
00:04:09,533 --> 00:04:11,433
and then Eve is going to take
Bob's message and be like,

96
00:04:11,433 --> 00:04:13,400
“Ha I'm going to decrypt 
it,” and then send the

97
00:04:13,400 --> 00:04:16,433
encrypted message to Alice 
using Alice's public key.

98
00:04:16,433 --> 00:04:18,466
So Alice and Bob think
everything's working, but

99
00:04:18,466 --> 00:04:21,433
actually Eve's in the middle 
attacking everything, okay?

100
00:04:21,433 --> 00:04:22,933


101
00:04:22,933 --> 00:04:26,866
So there are ways to circumvent
that. They involve things…

102
00:04:26,866 --> 00:04:30,000
certificates, and identity 
checks, and things like this.

103
00:04:30,000 --> 00:04:30,433


104
00:04:30,433 --> 00:04:33,833
This is a huge active area, 
I believe for example,

105
00:04:33,833 --> 00:04:37,500
Verisign, a company which
produces certificates,

106
00:04:37,500 --> 00:04:39,866
they're like a billion 
dollar company I believe,

107
00:04:39,866 --> 00:04:42,633
and it just involves the idea 
of just verifying identities,

108
00:04:42,633 --> 00:04:46,000
which is pretty cool and crazy to
think that, you know, such a…

109
00:04:46,000 --> 00:04:47,100


110
00:04:47,100 --> 00:04:49,600
it's an important idea but it's
not too hard mathematically,

111
00:04:49,600 --> 00:04:51,700
and it's actually worth 
a lot of money. So,

112
00:04:51,700 --> 00:04:55,633
this is a big active area of research and 
a big active area of interest for people.

113
00:04:55,633 --> 00:04:56,400


114
00:04:56,400 --> 00:04:59,866
What are some advantages to RSA?
We believe it's secure, it's pretty quick,

115
00:04:59,866 --> 00:05:02,766
encryption and decryption can be done
with the same sort of black box, right?

116
00:05:02,766 --> 00:05:06,566
Just taking powers of numbers,

117
00:05:06,566 --> 00:05:09,500
and they can be done very quickly
using the Square and Multiply Algorithm.

118
00:05:09,500 --> 00:05:12,833
I didn't mention that, but we can use the Square 
and Multiply Algorithm to do it pretty quickly.

119
00:05:12,833 --> 00:05:14,100


120
00:05:14,100 --> 00:05:16,566
Alright let's take a look at an example.

121
00:05:16,566 --> 00:05:21,000
Let p be 2, q be 11, and e be 3. 
Compute n, phi of n, and d.

122
00:05:21,000 --> 00:05:23,766
So here I used just the
normal phi, that's fine.

123
00:05:23,766 --> 00:05:26,566
Compute C is congruent to M 
to the e mod n when M is 8.

124
00:05:26,566 --> 00:05:30,300
Compute R is congruent to C 
to the d mod n when C is 6.

125
00:05:30,300 --> 00:05:31,133


126
00:05:31,133 --> 00:05:33,300
Pause the video, take a 
chance - take a minute.

127
00:05:33,300 --> 00:05:36,000
Try to solve these 
three problems.

128
00:05:36,000 --> 00:05:38,400
And now that you're back, 
we can see the solutions.

129
00:05:38,400 --> 00:05:41,966
n, phi of n and d are pretty simple. 
n is the product of p and q,

130
00:05:41,966 --> 00:05:45,900
that's 22. Phi of n is p minus 1
times q minus 1, so that's 10.

131
00:05:45,900 --> 00:05:46,833


132
00:05:46,833 --> 00:05:50,333
d is the inverse of e mod phi of n.

133
00:05:50,333 --> 00:05:51,333


134
00:05:51,333 --> 00:05:56,200
It turns out if you do that computation, so you 
want to solve 3d is congruent to 1 mod 10.

135
00:05:56,200 --> 00:05:57,133


136
00:05:57,133 --> 00:05:59,866
Check out all 10 numbers, so 3, 6, 9,

137
00:05:59,866 --> 00:06:04,100
12, which is 2, 15 which is 5, 
18, which is 8, 21 which is 1 mod 10.

138
00:06:04,100 --> 00:06:04,766


139
00:06:04,766 --> 00:06:07,266
So how did I get from 3 
to 21? I multiplied by 7,

140
00:06:07,266 --> 00:06:09,633
so d is congruent to 7 mod 10.

141
00:06:09,633 --> 00:06:10,766


142
00:06:10,766 --> 00:06:14,600
So for part 2, we’d like to compute 
M to the e mod n, when M is 8.

143
00:06:14,600 --> 00:06:15,333


144
00:06:15,333 --> 00:06:18,600
So let's do that, we have 8 
cubed which is 8 times 64,

145
00:06:18,600 --> 00:06:22,200
64 is the same as minus 2 mod 22,

146
00:06:22,200 --> 00:06:25,400
8 times minus 2 is negative 16, which is 6.

147
00:06:25,400 --> 00:06:29,600
How did I do this? Well again I split 
up 8 cubed is 8 times 8 squared.

148
00:06:29,600 --> 00:06:32,300
It seemed like the most logical thing to do,

149
00:06:32,300 --> 00:06:34,666
and then I just simplify. You 
could just compute 8 cubed

150
00:06:34,666 --> 00:06:38,266
which is some relatively
big number, 512 I believe,

151
00:06:38,266 --> 00:06:40,500
and then go through it, that's 
fine as well, but I prefer to do

152
00:06:40,500 --> 00:06:43,666
a little bit of the computation then reduce, 
then do a little bit more and reduce.

153
00:06:43,666 --> 00:06:47,833
It's kind of like the Square and Multiply Algorithm 
except you do it somewhat randomly.

154
00:06:47,833 --> 00:06:48,600


155
00:06:48,600 --> 00:06:52,666
You do it in the way that 
makes the computation easier.

156
00:06:52,666 --> 00:06:55,000


157
00:06:55,000 --> 00:06:57,066
Great, so C is congruent to 6 mod 22.

158
00:06:57,066 --> 00:07:00,000
Now to solve part 3, there's 
the easy way to do it, right?

159
00:07:00,000 --> 00:07:02,800
We know that C is congruent to 6,

160
00:07:02,800 --> 00:07:06,200
so C is 6, then if I’m decrypting, I get R and

161
00:07:06,200 --> 00:07:08,333
we already proved that 
R is the same as M, so

162
00:07:08,333 --> 00:07:11,533
C to the d should be congruent to 8 mod n,

163
00:07:11,533 --> 00:07:13,166


164
00:07:13,166 --> 00:07:16,133
but if you don't want to do it that way, we
can actually just compute it by hand,

165
00:07:16,133 --> 00:07:19,200
and I should probably do one more
computation just so that you see.

166
00:07:19,200 --> 00:07:22,800
I don't know if this is standard notation to
write the equivalent signs in two rows like this 

167
00:07:22,800 --> 00:07:25,966
and then read it left to right,
but that's what I'm going to do.

168
00:07:25,966 --> 00:07:28,366
So C to the d is congruent to 6 to 7 mod 22 -

169
00:07:28,366 --> 00:07:31,066
this is just so that it fits 
on one slide by the way.

170
00:07:31,066 --> 00:07:32,966
6 to the 7 is big,

171
00:07:32,966 --> 00:07:36,233
one way we can split this up is 
using the Square and Multiply Algorithm.

172
00:07:36,233 --> 00:07:39,400
One way to split it up is we 
can take like 6 squared cubed

173
00:07:39,400 --> 00:07:41,400
and multiply it by 6,

174
00:07:41,400 --> 00:07:44,400
6 squared is 36, 36 mod 22 is 14,

175
00:07:44,400 --> 00:07:46,533
14 is still kind of big…

176
00:07:46,533 --> 00:07:48,866
maybe it's not the best way to do it.

177
00:07:48,866 --> 00:07:51,633
If you're brave and if you 
know a little bit about…

178
00:07:51,633 --> 00:07:52,866


179
00:07:52,866 --> 00:07:54,666
small powers,

180
00:07:54,666 --> 00:07:58,333
you’ll know 6 cubed is the same as 216,

181
00:07:58,333 --> 00:08:02,666
and that's going to help us here. So 
6 cubed is 216, and 216 mod 22

182
00:08:02,666 --> 00:08:05,933
is minus 4. 216 is very close to [220],

183
00:08:05,933 --> 00:08:09,300
that's why I use 6 cubed here, 
because 216 is close to [220].

184
00:08:09,300 --> 00:08:09,933


185
00:08:09,933 --> 00:08:13,666
Now you might argue how do I know 
that in hindsight? Well okay, I mean,

186
00:08:13,666 --> 00:08:14,466


187
00:08:14,466 --> 00:08:16,666
you practice, you gamble, 
you take chances, and

188
00:08:16,666 --> 00:08:20,333
sometimes you're rewarded by taking 
a chance and computing 6 cubed.

189
00:08:20,333 --> 00:08:24,833
Anyway so based on that, now we have 
6 times negative 4 squared, 6 times 16,

190
00:08:24,833 --> 00:08:27,700
the same as 6 times minus 6, 
which is negative 36, which is

191
00:08:27,700 --> 00:08:29,633
the same as 8 as we expect.

192
00:08:29,633 --> 00:08:30,400


193
00:08:30,400 --> 00:08:33,566
And that's it. So hopefully this video 
gave you a little bit of insight

194
00:08:33,566 --> 00:08:35,366
to the RSA algorithm.

195
00:08:35,366 --> 00:08:38,966
Hopefully the example helps 
you to understand a little bit,

196
00:08:38,966 --> 00:08:42,000
and hopefully you understand how to go 
from a single prime exponentiation cipher

197
00:08:42,000 --> 00:08:44,900
to a two prime RSA algorithm.

198
00:08:44,900 --> 00:08:48,433
So that’s great, that's all I have to say. Thank 
you very much for your time and good luck.