1
00:00:00,566 --> 00:00:03,000
Hello everyone. In this video, we have a

2
00:00:03,000 --> 00:00:07,100
very, very tedious and 
fun problem with RSA. 

3
00:00:07,100 --> 00:00:11,733
So consider the RSA scheme
with public key e n equals 23, 407.

4
00:00:11,733 --> 00:00:13,033


5
00:00:13,033 --> 00:00:18,333
Using the scheme, encrypt
the message M equals 321.

6
00:00:18,333 --> 00:00:21,100
So at this point in the exam, 
I think I've realized that

7
00:00:21,100 --> 00:00:25,000
they definitely had calculators on this, but I'm 
going to do this without a calculator because I'm

8
00:00:25,000 --> 00:00:28,466
feeling optimistic tonight.

9
00:00:28,466 --> 00:00:32,300
So what's our goal? Well we really want to 
compute M to the power of e and reduce modulo n, 

10
00:00:32,300 --> 00:00:36,900
and we want to reduce this thing, so 
this value, to a value between 1 and n,

11
00:00:36,900 --> 00:00:39,133
probably not including the endpoints.

12
00:00:39,133 --> 00:00:40,000


13
00:00:40,000 --> 00:00:42,933
So essentially what are we trying 
to do? We're trying to compute

14
00:00:42,933 --> 00:00:47,800
the value of 321 to the power of 
23 mod 407 as a congruence.

15
00:00:47,800 --> 00:00:49,900
Now from here, you have 
a couple of choices. Now 

16
00:00:49,900 --> 00:00:52,333
could try some sort of 
square multiply algorithm,

17
00:00:52,333 --> 00:00:55,166
you could try to find some sort of trick.

18
00:00:55,166 --> 00:00:59,000
What I'm going to do because I - like I said,
I actually did this without a calculator,

19
00:00:59,000 --> 00:01:03,633
so I'm going to show you how to reduce these
monstrous numbers without a calculator,

20
00:01:03,633 --> 00:01:07,700
and what I'm going to do is, because I know 
this is an RSA scheme, I know I can factor n.

21
00:01:07,700 --> 00:01:09,933
So I'm going to do that, I'm going to factor n,

22
00:01:09,933 --> 00:01:14,400
I'm going to split the modulus, and then I'm going 
to pray that something good is going to happen.

23
00:01:14,400 --> 00:01:18,533
And it turns out that something good did 
happen. So that's my plan for this question.

24
00:01:18,533 --> 00:01:22,400
So it is difficult to compute without a
calculator, but I'm going to do it anyways

25
00:01:22,400 --> 00:01:26,100
So I'm going to split the modulus and
then use CRT to put it back, okay?

26
00:01:26,100 --> 00:01:28,000


27
00:01:28,000 --> 00:01:32,900
So note that 407, so notice that 
4 plus 7 is 11, minus 0 is 11,

28
00:01:32,900 --> 00:01:37,033
so the number’s divisible by 11. That's 
clear from that little computation, so...

29
00:01:37,033 --> 00:01:40,200
By the way, if you haven't
seen that type in divisibility…

30
00:01:40,200 --> 00:01:45,333
divisibility rule for 11, and you'll see a nice 
little alternating sum rule, which is pretty cool.

31
00:01:45,333 --> 00:01:47,433
So I know this rule, so I 
found that 11 was a factor

32
00:01:47,433 --> 00:01:50,233
and it turns out that 11 times 37 is 407.

33
00:01:50,233 --> 00:01:52,366
37 happens to be prime, which is great.

34
00:01:52,366 --> 00:01:55,266
We actually have a valid RSA scheme.

35
00:01:55,266 --> 00:01:59,500
Thus, it suffices to compute 
3 to the 21 mod 11 and - 

36
00:01:59,500 --> 00:02:04,933
sorry, 321 to the power of 23 mod 11, 
and 321 to the power of 23 mod 37.

37
00:02:04,933 --> 00:02:07,233
So we'll see how I do that in a second.

38
00:02:07,233 --> 00:02:09,133
Let's do the one for 11, so

39
00:02:09,133 --> 00:02:12,600
the one for 11, 321 to the power of 23.

40
00:02:12,600 --> 00:02:16,566
I'm going to use the fact that 
330 is pretty close to 321,

41
00:02:16,566 --> 00:02:19,833
so if I reduce 321 mod 11,

42
00:02:19,833 --> 00:02:22,600
I get negative 9, which is 
the same as 2 mod 11.

43
00:02:22,600 --> 00:02:25,300
So I'm going to replace 321 with 2.

44
00:02:25,300 --> 00:02:27,266
2 to the 23, now I'm going to use FLT,

45
00:02:27,266 --> 00:02:30,400
right, so 11 minus 1 is 10, 
so let's write this as…

46
00:02:30,400 --> 00:02:35,200
oh I should write this as 2 to the 10
squared, so let's fix that. So 2 to the 10

47
00:02:35,200 --> 00:02:37,466


48
00:02:37,466 --> 00:02:40,766
squared. Let's actually write that properly.

49
00:02:40,766 --> 00:02:42,200


50
00:02:42,200 --> 00:02:46,133
So that's great, so 2 to the 10 is
congruent to 1 mod 11, by FLT,

51
00:02:46,133 --> 00:02:50,100
and 2 cubed is 8. So maybe 
I'll even include that step.

52
00:02:50,100 --> 00:02:50,133


53
00:02:50,133 --> 00:02:50,366


54
00:02:50,366 --> 00:02:52,766
And so I get 8,

55
00:02:52,766 --> 00:02:55,100
and I'm going to write this

56
00:02:55,100 --> 00:02:58,133
as 30 for a reason that we'll see later.

57
00:02:58,133 --> 00:03:00,666
So I wrote this as 30 after the fact, but

58
00:03:00,666 --> 00:03:03,700
I'll show you where 30 comes 
from and why I wanted that.

59
00:03:03,700 --> 00:03:06,366
8 happens to be congruent 
to 30 mod 11, okay,

60
00:03:06,366 --> 00:03:11,000
and now let's reduce mod 37. So now we have 
to reduce 321 to the power of 23 mod 37.

61
00:03:11,000 --> 00:03:13,966
So I've written down a couple 
of multiples of 37 here.

62
00:03:13,966 --> 00:03:17,766
These I just actually did by 
hand. So 37 times 3 is 111,

63
00:03:17,766 --> 00:03:21,400
37 times 4 is 148, and 37 times 5 is 185.

64
00:03:21,400 --> 00:03:22,233


65
00:03:22,233 --> 00:03:23,866
So...

66
00:03:23,866 --> 00:03:25,400
So...

67
00:03:25,400 --> 00:03:29,500
321, when I did this computation,

68
00:03:29,500 --> 00:03:32,400
is the same as 25. How did I do that? 

69
00:03:32,400 --> 00:03:33,666


70
00:03:33,666 --> 00:03:36,166
Well what I did was I did…I took -

71
00:03:36,166 --> 00:03:40,466
so 370, so 10 times [37] is close to 321.

72
00:03:40,466 --> 00:03:43,766
321 minus 370 gives me negative 49,

73
00:03:43,766 --> 00:03:46,600
if I add 74 to 49, I get 25.

74
00:03:46,600 --> 00:03:51,100
So I didn't show that computation, or I didn't 
type it out, but that's what I did to get the 25.

75
00:03:51,100 --> 00:03:54,800
So now I have 25 to the 
23, well 25 is not great,

76
00:03:54,800 --> 00:03:57,333
but 25 is 5 squared

77
00:03:57,333 --> 00:04:00,900
which helps me out a little bit, which we'll see 
in a second. So why is this not great? Well

78
00:04:00,900 --> 00:04:05,466
I want to use FLT again, but 37 minus 
1 is 36, which is bigger than 23,

79
00:04:05,466 --> 00:04:09,166
but I have 25 which is 5 squared 
and that's going to help me 

80
00:04:09,166 --> 00:04:12,133
actually - so making the exponent bigger 
actually helps me to make it smaller

81
00:04:12,133 --> 00:04:15,933
because I can write 5 to the 46 
as 5 to the 36 times 5 to the 10,

82
00:04:15,933 --> 00:04:19,900
and I get rid of 5 to the 36. So now I
just have to compute 5 to the 10 mod 37.

83
00:04:19,900 --> 00:04:24,166
That's not too bad 5 to the 10 is actually pretty
small so I'm just going to compute it by hand.

84
00:04:24,166 --> 00:04:28,500
So 5 to the 10 is the 
same as 5 cubed cubed,

85
00:04:28,500 --> 00:04:30,200
times 5, right? So that's

86
00:04:30,200 --> 00:04:34,033
5 to the power of 9 times 
5, so that's 125 cubed.

87
00:04:34,033 --> 00:04:35,600


88
00:04:35,600 --> 00:04:40,733
So now 125 that's close to 111, so if 
I reduce that I get 14 cubed times 5.

89
00:04:40,733 --> 00:04:41,733


90
00:04:41,733 --> 00:04:46,900
14 cubed I'm going to write this as 
14 squared, so 196 times 14 times 5.

91
00:04:46,900 --> 00:04:47,633


92
00:04:47,633 --> 00:04:50,166
14 times 5, that's 70.

93
00:04:50,166 --> 00:04:52,466
196 is close to 185,

94
00:04:52,466 --> 00:04:56,533
the remainder happens to be 11, 
or the difference is 11, sorry.

95
00:04:56,533 --> 00:05:01,000
So that's great, now 70, 70 is 
close to 74, which is 2 times 37,

96
00:05:01,000 --> 00:05:03,533
so that's negative 4. So 
if I do a little arithmetic,

97
00:05:03,533 --> 00:05:07,166
so 11 times negative 4 is
negative 44, add 74, I get 30.

98
00:05:07,166 --> 00:05:08,166


99
00:05:08,166 --> 00:05:10,500
30 should look familiar to you.

100
00:05:10,500 --> 00:05:13,066
So I've reduced C to 
congruent to 30 mod 27,

101
00:05:13,066 --> 00:05:16,333
but up here I got that C was 
also congruent to 30 mod 11.

102
00:05:16,333 --> 00:05:19,200
Easy application of Chinese
Remainder Theorem now.

103
00:05:19,200 --> 00:05:21,700
So now if I combine using the Chinese 
Remainder Theorem, I get that

104
00:05:21,700 --> 00:05:25,700
C is congruent to 30 mod 407 is the 
entire set of solutions, and hence,

105
00:05:25,700 --> 00:05:29,266
C is equal to 30 because C 
must be between 1 and n.

106
00:05:29,266 --> 00:05:31,866
Crazy, crazy computation, so

107
00:05:31,866 --> 00:05:35,433
we do not expect this sort of level
of computation on the exam,

108
00:05:35,433 --> 00:05:38,300
but I wanted to show you that hey 
you can be creative and you can

109
00:05:38,300 --> 00:05:40,000
tackle these problems
without a calculator.

110
00:05:40,000 --> 00:05:42,800
If your name happens to be Tom 
Hanks and you're in Castaway and

111
00:05:42,800 --> 00:05:45,066
you're on an island and you
need to do these computations,

112
00:05:45,066 --> 00:05:48,133
you actually can do 
them without a calculator.

113
00:05:48,133 --> 00:05:52,200
So I just wanted to show you a little bit 
of how you can manipulate these things.

114
00:05:52,200 --> 00:05:55,466
So clearly on the exam they expected you 
to use a calculator and just pound it out,

115
00:05:55,466 --> 00:05:58,366
but I'm going to be creative once 
in a while and I'm going to try to

116
00:05:58,366 --> 00:06:02,133
combine the Splitting the Modulus, 
Chinese Remainder Theorem arguments

117
00:06:02,133 --> 00:06:04,600
that are…that you are supposed to know. 

118
00:06:04,600 --> 00:06:07,066
So you don't need to know 
all these crazy computations,

119
00:06:07,066 --> 00:06:09,933
but just know that there are ways 
to do it. So you've seen in this

120
00:06:09,933 --> 00:06:12,133
computation like 7 or 8 tricks

121
00:06:12,133 --> 00:06:15,700
to help you get to the answer, which I think are 
cool, and I think they're worth knowing, but I mean,

122
00:06:15,700 --> 00:06:16,533


123
00:06:16,533 --> 00:06:19,233
who does these things,
right? I guess only me,

124
00:06:19,233 --> 00:06:22,433
but I think it's cool. So hopefully 
you learned something from that.

125
00:06:22,433 --> 00:06:24,533
Okay now you're going to do the 
second part, determine the private key

126
00:06:24,533 --> 00:06:27,466
corresponding to the public key 23 and 407.

127
00:06:27,466 --> 00:06:29,833
So this is where you need to know 
what the private key is, right?

128
00:06:29,833 --> 00:06:33,133
So if you think back to 
RSA, the private key…

129
00:06:33,133 --> 00:06:34,233


130
00:06:34,233 --> 00:06:35,900
the private key

131
00:06:35,900 --> 00:06:39,166
is the solution to e d is 
congruent to 1 mod phi of n.

132
00:06:39,166 --> 00:06:41,533
And what are these things?
So phi of n is equal to

133
00:06:41,533 --> 00:06:44,166
p minus 1 times q minus 1. 
So if you didn't do that,

134
00:06:44,166 --> 00:06:47,066
so maybe I'll write that in here
just in case you didn't do that.

135
00:06:47,066 --> 00:06:50,566
This is equal to p minus 1 q minus 1.

136
00:06:50,566 --> 00:06:52,566


137
00:06:52,566 --> 00:06:54,800
So maybe you saw it like 
that, that's fine too, right?

138
00:06:54,800 --> 00:06:58,366
So if you want to - instead of using phi of n 
you use p minus 1 q minus 1, that's fine.

139
00:06:58,366 --> 00:07:00,200


140
00:07:00,200 --> 00:07:02,166
So in other words, what
am I trying to do? Well I'm

141
00:07:02,166 --> 00:07:06,900
trying to find the inverse of 23 modulo 360.

142
00:07:06,900 --> 00:07:10,633
Unlike in the previous examples, 
so unlike in question 1 or 2,

143
00:07:10,633 --> 00:07:13,733
I think I found the inverse by inspection.

144
00:07:13,733 --> 00:07:14,466


145
00:07:14,466 --> 00:07:17,666
Here I'm just going to use the 
Extended Euclidean Algorithm, okay?

146
00:07:17,666 --> 00:07:18,733


147
00:07:18,733 --> 00:07:21,633
So I'm going to set it up - oh I
guess I shouldn't call these x and y,

148
00:07:21,633 --> 00:07:24,566
I should call these d and k.

149
00:07:24,566 --> 00:07:26,033


150
00:07:26,033 --> 00:07:28,866
So we're going to solve this using the Extended 
Euclidean Algorithm. How are we going to do this?

151
00:07:28,866 --> 00:07:34,033
Well set up d, k, r, 360 is the bigger one,
so I put the 1 there, put the 1 here.

152
00:07:34,033 --> 00:07:39,133
23 goes into 360, so it turns 
out that 23 times 15 is 345,

153
00:07:39,133 --> 00:07:39,866


154
00:07:39,866 --> 00:07:42,066
so it goes in there 15 times. 

155
00:07:42,066 --> 00:07:46,933
So throw that through, the
remainder of 360 minus 345 is 15.

156
00:07:46,933 --> 00:07:47,900


157
00:07:47,900 --> 00:07:51,400
Now my numbers are manageable, so now I 
can just do the computation very quickly. So

158
00:07:51,400 --> 00:07:54,833
15 goes into 23 once, when I
subtract these two, I get 8.

159
00:07:54,833 --> 00:07:57,066
So I subtract these two rows.

160
00:07:57,066 --> 00:08:03,566
1 minus 15 is - 1 minus negative 15 
is 16, and 0 minus 1 is negative 1.

161
00:08:03,566 --> 00:08:07,166
8 goes into 15 once, remainder
7, when I subtract the two.

162
00:08:07,166 --> 00:08:09,133
So take the subtraction that's 2.

163
00:08:09,133 --> 00:08:11,700
Take the subtraction here, that’s negative 31.

164
00:08:11,700 --> 00:08:14,066
7 goes into 8 once, my remainder is 1,

165
00:08:14,066 --> 00:08:16,533
and so on and so forth.

166
00:08:16,533 --> 00:08:20,833
So 16 minus negative 31 is 47, 
negative 1 minus 2 is negative 3. 

167
00:08:20,833 --> 00:08:24,933
So thus 23 times 47 plus 360 
times negative 3 is equal to 1,

168
00:08:24,933 --> 00:08:28,066
and thus d equals 47 is the inverse

169
00:08:28,066 --> 00:08:31,833
of e mod 360, okay?

170
00:08:31,833 --> 00:08:35,000
So d equals 47 is my private key, okay?

171
00:08:35,000 --> 00:08:39,300
Again, your textbook uses d comma 
n equals 47 and 407, whatever.

172
00:08:39,300 --> 00:08:41,700
d is really the private key here, okay?

173
00:08:41,700 --> 00:08:44,766
The fact that it's d comma n in the
textbook’s not super important,

174
00:08:44,766 --> 00:08:49,033
the real important value is the d, right, 
because everyone knows n anyways.

175
00:08:49,033 --> 00:08:50,966
So enough said about that.

176
00:08:50,966 --> 00:08:53,733
Okay, so this is a computation that 
you would actually be expected to do,

177
00:08:53,733 --> 00:08:56,333
that's not too, too bad. The first 
step's a little bit gruesome,

178
00:08:56,333 --> 00:08:58,466
but other than that it's pretty straightforward. 

179
00:08:58,466 --> 00:08:59,500


180
00:08:59,500 --> 00:09:01,633
Okay, so hopefully you learned 
something from this video.

181
00:09:01,633 --> 00:09:05,066
Thank you for listening and 
tune in for question 6 later.