Hello everyone. In this video, we have a
very, very tedious and fun problem with RSA.
So consider the RSA scheme with public key e n equals 23, 407.
Using the scheme, encrypt the message M equals 321.
So at this point in the exam, I think I've realized that
they definitely had calculators on this, but I'm going to do this without a calculator because I'm
feeling optimistic tonight.
So what's our goal? Well we really want to compute M to the power of e and reduce modulo n,
and we want to reduce this thing, so this value, to a value between 1 and n,
probably not including the endpoints.
So essentially what are we trying to do? We're trying to compute
the value of 321 to the power of 23 mod 407 as a congruence.
Now from here, you have a couple of choices. Now
could try some sort of square multiply algorithm,
you could try to find some sort of trick.
What I'm going to do because I - like I said, I actually did this without a calculator,
so I'm going to show you how to reduce these monstrous numbers without a calculator,
and what I'm going to do is, because I know this is an RSA scheme, I know I can factor n.
So I'm going to do that, I'm going to factor n,
I'm going to split the modulus, and then I'm going to pray that something good is going to happen.
And it turns out that something good did happen. So that's my plan for this question.
So it is difficult to compute without a calculator, but I'm going to do it anyways
So I'm going to split the modulus and then use CRT to put it back, okay?
So note that 407, so notice that 4 plus 7 is 11, minus 0 is 11,
so the number’s divisible by 11. That's clear from that little computation, so...
By the way, if you haven't seen that type in divisibility…
divisibility rule for 11, and you'll see a nice little alternating sum rule, which is pretty cool.
So I know this rule, so I found that 11 was a factor
and it turns out that 11 times 37 is 407.
37 happens to be prime, which is great.
We actually have a valid RSA scheme.
Thus, it suffices to compute 3 to the 21 mod 11 and -
sorry, 321 to the power of 23 mod 11, and 321 to the power of 23 mod 37.
So we'll see how I do that in a second.
Let's do the one for 11, so
the one for 11, 321 to the power of 23.
I'm going to use the fact that 330 is pretty close to 321,
so if I reduce 321 mod 11,
I get negative 9, which is the same as 2 mod 11.
So I'm going to replace 321 with 2.
2 to the 23, now I'm going to use FLT,
right, so 11 minus 1 is 10, so let's write this as…
oh I should write this as 2 to the 10 squared, so let's fix that. So 2 to the 10
squared. Let's actually write that properly.
So that's great, so 2 to the 10 is congruent to 1 mod 11, by FLT,
and 2 cubed is 8. So maybe I'll even include that step.
And so I get 8,
and I'm going to write this
as 30 for a reason that we'll see later.
So I wrote this as 30 after the fact, but
I'll show you where 30 comes from and why I wanted that.
8 happens to be congruent to 30 mod 11, okay,
and now let's reduce mod 37. So now we have to reduce 321 to the power of 23 mod 37.
So I've written down a couple of multiples of 37 here.
These I just actually did by hand. So 37 times 3 is 111,
37 times 4 is 148, and 37 times 5 is 185.
So...
321, when I did this computation,
is the same as 25. How did I do that?
Well what I did was I did…I took -
so 370, so 10 times [37] is close to 321.
321 minus 370 gives me negative 49,
if I add 74 to 49, I get 25.
So I didn't show that computation, or I didn't type it out, but that's what I did to get the 25.
So now I have 25 to the 23, well 25 is not great,
but 25 is 5 squared
which helps me out a little bit, which we'll see in a second. So why is this not great? Well
I want to use FLT again, but 37 minus 1 is 36, which is bigger than 23,
but I have 25 which is 5 squared and that's going to help me
actually - so making the exponent bigger actually helps me to make it smaller
because I can write 5 to the 46 as 5 to the 36 times 5 to the 10,
and I get rid of 5 to the 36. So now I just have to compute 5 to the 10 mod 37.
That's not too bad 5 to the 10 is actually pretty small so I'm just going to compute it by hand.
So 5 to the 10 is the same as 5 cubed cubed,
times 5, right? So that's
5 to the power of 9 times 5, so that's 125 cubed.
So now 125 that's close to 111, so if I reduce that I get 14 cubed times 5.
14 cubed I'm going to write this as 14 squared, so 196 times 14 times 5.
14 times 5, that's 70.
196 is close to 185,
the remainder happens to be 11, or the difference is 11, sorry.
So that's great, now 70, 70 is close to 74, which is 2 times 37,
so that's negative 4. So if I do a little arithmetic,
so 11 times negative 4 is negative 44, add 74, I get 30.
30 should look familiar to you.
So I've reduced C to congruent to 30 mod 27,
but up here I got that C was also congruent to 30 mod 11.
Easy application of Chinese Remainder Theorem now.
So now if I combine using the Chinese Remainder Theorem, I get that
C is congruent to 30 mod 407 is the entire set of solutions, and hence,
C is equal to 30 because C must be between 1 and n.
Crazy, crazy computation, so
we do not expect this sort of level of computation on the exam,
but I wanted to show you that hey you can be creative and you can
tackle these problems without a calculator.
If your name happens to be Tom Hanks and you're in Castaway and
you're on an island and you need to do these computations,
you actually can do them without a calculator.
So I just wanted to show you a little bit of how you can manipulate these things.
So clearly on the exam they expected you to use a calculator and just pound it out,
but I'm going to be creative once in a while and I'm going to try to
combine the Splitting the Modulus, Chinese Remainder Theorem arguments
that are…that you are supposed to know.
So you don't need to know all these crazy computations,
but just know that there are ways to do it. So you've seen in this
computation like 7 or 8 tricks
to help you get to the answer, which I think are cool, and I think they're worth knowing, but I mean,
who does these things, right? I guess only me,
but I think it's cool. So hopefully you learned something from that.
Okay now you're going to do the second part, determine the private key
corresponding to the public key 23 and 407.
So this is where you need to know what the private key is, right?
So if you think back to RSA, the private key…
the private key
is the solution to e d is congruent to 1 mod phi of n.
And what are these things? So phi of n is equal to
p minus 1 times q minus 1. So if you didn't do that,
so maybe I'll write that in here just in case you didn't do that.
This is equal to p minus 1 q minus 1.
So maybe you saw it like that, that's fine too, right?
So if you want to - instead of using phi of n you use p minus 1 q minus 1, that's fine.
So in other words, what am I trying to do? Well I'm
trying to find the inverse of 23 modulo 360.
Unlike in the previous examples, so unlike in question 1 or 2,
I think I found the inverse by inspection.
Here I'm just going to use the Extended Euclidean Algorithm, okay?
So I'm going to set it up - oh I guess I shouldn't call these x and y,
I should call these d and k.
So we're going to solve this using the Extended Euclidean Algorithm. How are we going to do this?
Well set up d, k, r, 360 is the bigger one, so I put the 1 there, put the 1 here.
23 goes into 360, so it turns out that 23 times 15 is 345,
so it goes in there 15 times.
So throw that through, the remainder of 360 minus 345 is 15.
Now my numbers are manageable, so now I can just do the computation very quickly. So
15 goes into 23 once, when I subtract these two, I get 8.
So I subtract these two rows.
1 minus 15 is - 1 minus negative 15 is 16, and 0 minus 1 is negative 1.
8 goes into 15 once, remainder 7, when I subtract the two.
So take the subtraction that's 2.
Take the subtraction here, that’s negative 31.
7 goes into 8 once, my remainder is 1,
and so on and so forth.
So 16 minus negative 31 is 47, negative 1 minus 2 is negative 3.
So thus 23 times 47 plus 360 times negative 3 is equal to 1,
and thus d equals 47 is the inverse
of e mod 360, okay?
So d equals 47 is my private key, okay?
Again, your textbook uses d comma n equals 47 and 407, whatever.
d is really the private key here, okay?
The fact that it's d comma n in the textbook’s not super important,
the real important value is the d, right, because everyone knows n anyways.
So enough said about that.
Okay, so this is a computation that you would actually be expected to do,
that's not too, too bad. The first step's a little bit gruesome,
but other than that it's pretty straightforward.
Okay, so hopefully you learned something from this video.
Thank you for listening and tune in for question 6 later.