Fall 2000 Exam Question 5

Hello everyone. In this video, we have a very, very tedious and fun problem with RSA.

Question: Consider the RSA scheme with public key $(e,n)=(23,407)$ .

Using this scheme, encrypt the message $M=321$ .

Solution

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^e$ and reduce $\bmod 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

$C\equiv M^e\equiv321^{23}\pmod{407}$

Now from here, you have a couple of choices. Now you could try some sort of square multiply algorithm, you could try to find some sort of trick. 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.

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.

So notice that with $407$ , $4-0+7=11$ , so the number’s divisible by $11$ . That's clear from that little computation. By the way, if you haven't seen that type in 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\cdot 37=407$ . $37$ happens to be prime, which is great. We actually have a valid RSA scheme.

Thus, it suffices to compute $321^{23}\pmod{11}$ , and $321^{23}\pmod{37}$ . So we'll see how I do that in a second.

Let's do the one for $11$ , so I'm going to use the fact that $30\cdot 11=330$ so $321\equiv 2 \pmod{11}$ .

$\begin{align*} C&\equiv 321^{23}\pmod{11}\\ &\equiv 2^{23}\pmod{11}\\ &\equiv (2^{10})^2 2^3\pmod{11}\\ &\equiv (1)8\pmod{11}&&\text{By FLT}\\ &\equiv 8\pmod{11}\\ &\equiv 30\pmod{11} \end{align*}$

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.

Now let's reduce $\bmod {37}$ . So now we have to reduce $321^{23}\bmod{37}$ . So I've written down a couple of multiples of $37$ here. These I just actually did by hand. $37\cdot 3=111$ , $37\cdot 4=148$ , and $37\cdot 5=185$ .

To get the $25$ , so $10\cdot 37$ is close to $321$ . $321-370=-49+74=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 as you saw from the third to fourth line, making the exponent bigger actually helps me to make it smaller because I can use FLT to get rid of the $5^{36}$ .

So now I just have to compute $5^{10}\bmod{10}$ . That's not too bad $5^{10}$ is actually pretty small so I'm just going to compute it by hand.

$\begin{align*} C&\equiv 321^{23}\pmod{37}\\ &\equiv 25^{23}\pmod{37}\\ &\equiv (5^2)^{23}\pmod{37}\\ &\equiv 5^{46}\pmod{37}\\ &\equiv 5^{36}5^{10}\pmod{37}\\ &\equiv 5^{10}\pmod{37}&&\text{By FLT}\\ &\equiv 125^3\cdot 5\pmod{37}\\ &\equiv 14^3\cdot 5\pmod{37}\\ &\equiv 196\cdot 14\cdot 5\pmod{37}\\ &\equiv 11\cdot 70\pmod{37}\\ &\equiv 11\cdot (-4)\pmod{37}\\ &\equiv -44\pmod{37}\\ &\equiv 30\pmod{37}\\ \end{align*}$

$30$ should look familiar to you. So I've reduced to $C\equiv 30\bmod{37}$ , but up here I got that $C\equiv 30\bmod{11}$ . Easy application of Chinese Remainder Theorem now.

So now if I combine using the Chinese Remainder Theorem, I get that $C\equiv 30\bmod{407}$ is the entire set of solutions, and hence, $C=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 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 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.

Question: Determine the private key corresponding to the public key $(23,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 is the solution to $ed\equiv 1\bmod{\phi(n)}$ .

Now what are these things? So $\phi(n)=(p-1)(q-1)$ . So if you want to instead of using $\phi(n)$ you use $(p-1)(q-1)$ , that's fine.

So in other words, what am I trying to do? Well I'm trying to find $23^{-1}\bmod{360}$ . Unlike in the previous examples, so unlike in question $1$ or $2$ where I found the inverse by inspection, here I'm just going to use the Extended Euclidean Algorithm.

$d$	$k$	$r$	$q$
$0$	$1$	$360$
$1$	$0$	$23$
$-15$	$1$	$15$	$15$
$16$	$-1$	$8$	$1$
$-31$	$2$	$7$	$1$
$47$	$-3$	$1$	$1$

So how did I do this? $23$ goes into $360$ , so it turns out that $23\cdot 15=345$ , so it goes in there $15$ times. So throw that through, the remainder of $360-345=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 the second and third rows. $1-(-15)=16$ , and $0-1=-1$ .

$8$ goes into $15$ once, remainder $7$ , when I subtract the two. So subtract the third and fourth rows to get $-31$ and $2$ .

$7$ goes into $8$ once, my remainder is $1$ , and so on and so forth. So $16-(-31)=47$ , $-1-2=-3$ . So thus $23(47)+360(-3)=1$ , and thus $d=47$ is the inverse of $e \bmod {360}$ . So $d=47$ is my private key.

Again, your textbook uses $(d,n)=(47,407)$ , whatever. $d$ is really the private key here, okay? The fact that it's $(d,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.