Hello everyone. In this video, we're going to talk about RSA.
Now
here, again, I'm using Sage Math Cloud as my
LaTeX editor, but here I'm actually using the
Sage version of it. So I can actually have access to
Python and Sage and all of the mathematical commands,
which I'll use to do some of the computations in this video.
So in order to do RSA, let's talk about the framework again.
So over here we're going to have our Alice -
so I'm going to use the paintbrush to do a little bit.
So Alice,
and over here we're going to have Bob
over here, and over here we're going to put Eve in the middle.
Eve for eavesdropper. Some people use Oscar I'm going to use Eve.
So the idea is that Alice and Bob want to share messages.
So Alice wants to - Bob wants to send a message to Alice, okay,
but now Bob can't just send a message across the unsecured stream,
or unsecured line, think of this as like the internet
because then Eve can read it and see it.
So Bob needs to encrypt it somehow, so that when Eve sees
the encrypted message, she won't know what's going on, but
Alice somehow knows how to decrypt it.
So...
let's go over to the Sage worksheet
and let’s summarize this. So Bob wants to send Alice a message,
and Bob wants to send Alice a secure message using RSA.
So what's going to happen?
So Alice…
Alice is going to do what? Alice is going to, in the RSA scheme,
she's going to choose a public key,
e comma n, satisfying
n is equal to p q,
and what do we have to have about e?
So I guess we don't need a period here, and e
satisfies…
positive integer satisfying
gcd of e and p minus 1 q minus 1
equals 1
for distinct
primes p and q.
Okay, so Alice is going to choose a public key, e and n,
satisfying n equals p q for distinct primes p and q,
and e is a positive integer satisfying
the gcd of e and p minus 1 q minus 1,
also known as phi of n, is equal to 1.
So let's go to our picture.
So Alice, Eve, and Bob, so everyone's going to have this public key.
This public is going to be given by
e comma n.
Everyone knows the public key e n.
I know it, you know it, Eve knows it,
grandma knows it, everyone knows it.
Okay, excellent.
So what do we do this? Okay, so
here's the situation. Let's actually pick some examples of n, p, and q.
So what am I going to pick? I'm going to pick p is equal to -
I'm going to use this command called next prime because I want an actual large prime.
So I'm going to pick the first prime after 12345.
q is going to be
the next prime after 54321.
Again remember these are all Sage commands, next prime and
everything will be written - if you know Python, it's kind of like Python with a little bit more to it.
If not, that's okay. Hopefully this is still pretty reasonable.
So next prime will print the first prime after…will pick -
will set p to be the next prime after 12345, and q will be the next prime after 54321.
n is going to be p times q,
and we need to pick an integer e,
so, I don’t know, I'm going to pick e equals 17.
And I'm going to print the…just to make sure that the gcd of e and
p minus 1 times q minus 1…
I'm going to just print out this gcd. I want to make sure that the gcd is 1.
So I'm going to - you know what? I'll print out e as well,
so I'm going to print out e and the gcd of p minus 1 [times q minus 1 and e].
So let's see what happens when I run this code.
So p is the value 12347, okay,
and q is the value 54323,
apparently those two numbers are prime, so that's great.
n is equal to p times q print n, so the product of
p and q is 670726081,
so something along lines of 670 million-ish.
Okay so it's a pretty big number,
and e is 17, and the gcd we verified to be 1.
Oh I guess I should put the bracket here and make sure that
this is actually correct. Let's rerun this, yeah okay.
The gcd is 1, okay excellent.
And so with this, I guess I mean I've already done it on the picture but maybe I should mention here.
Alice publishes
e comma n.
So notice that e comma n is what's published, it's not
p and q, it's not the - it's the product, it's just the product, whatever number this is.
So in our case, we're going to publish…
so in our example, maybe I'll put the numbers here. We're going to publish
17,
and this huge number. What is this? 6, 7,
0,
7, 2,
6, 0,
8, 1.
So that's what's being published.
Now Bob wants to send a message.
So what’s Bob's message? So let's talk about Bob now.
Bob wants to send his message,
M,
an integer
strictly between 1 and n.
So Bob wants to send his message, M,
an integer strictly - not an integers, an integer strictly between 1 and n.
So what's Bob going to do? Well Bob's going to compute -
Bob's going to encrypt M. How is Bob going to encrypt M?
Bob computes
C to the power -oops, M to the power of e.
C which is equivalent to M to the power of e, I got it,
mod n.
And we want 0 to be less than C to be less than n.
Capital C.
So Bob's going to compute this C,
and Bob's going to send it over.
Okay?
So let's do a couple of things, so Bob's going to compute some…
so C, which is going to be congruent
to M to the e
mod n.
Alright, so
we've added this to our picture and we're going to try to send C over in a minute,
but first let's actually take an example. So here we're going to take M
equals, I don't know, 1, 2, 3, 4, 5, 6, 7, let's say eight 1’s, okay?
For whatever reason he likes this number and he's going to send it, okay?
C we're going to compute to be M to the e mod n, so we can do that with this command called power mod.
M comma e comma n. So what will this do? This will produce
M to the e mod n. It's sort of intuitive,
and we're going to print C.
Great, so C is this number 5120174[56],
so 512 ish million.
Okay, so Bob's computed this, now Bob's going to send C to Alice.
Bob sends C to Alice.
Oops sense C to Alice? How about sends C to Alice.
Bob sends C to Alice, so let's do that. So
in our picture, Bob's going to send over
C.
So Bob sends over C,
and remember here C is equal to
5, 1,
2, 0, 1,
7, 4, 5, 6.
So again notice that Eve gets to see C. So Eve doesn't know what M is,
but Eve gets to see C, this 9 digit number, and she gets to see e and n.
Okay?
Notice that from this weird number 5120174[56], it's not
immediately obvious that the message was eight 1’s, okay?
Now Alice is over here, so now Alice has C, but Alice knows a couple other things, right?
she knows p and q, she knows e, and
she knows these things. These are part of her private keys.
So Alice receives…so what's Alice going to do now?
Alice receives C and computes
d such that e d is equivalent to 1 mod p minus 1
q minus 1.
So Alice receives C and computes this
d. We'll see why this d is important in a minute.
d is going to be the inverse of e mod p minus 1 q minus 1.
By the way, sanity check, right? Why does this exist?
Hopefully you've answered the question.
This exists because the gcd of e and p minus 1 q minus 1 is 1.
Okay, so excellent.
So let's throw this in.
So she's going to compute d, d is the inverse.
So let's -
d is going to be equal to power mod
e, minus 1, and
p minus 1 times q minus 1.
d happens to be 118351661. So
in our picture, e - Alice has this private key,
d, so I'll write down private…
private d,
and again in our example it's 1, 1,
8,
3, 5, 1,
6, 6, 1.
Now what's Alice going to do? Well Alice is going to compute…
Alice is going to compute C to the d. So then...
Alice now computes
R, which is equivalent to C to the power of d,
and she's going to do this mod n.
Alice now computes R is congruent to C to the d mod n.
So I'm going to compute R is equal to power mod
C, d, and n.
Print R. Okay now is a good time to ask yourself,
“What value is the computer going to print out here for R?”
So if you understand everything, you should know exactly what's going to happen here, okay? So
pause the video, think about it, and then come back.
Hopefully you're back,
and what should the the answer be? The answer should be M.
So if I did everything correctly, the answer should be eight 1’s.
Let's hope for the best. Okay, there we go,
okay, that's fantastic.
So this R that you compute when you compute C to the d -
so maybe I'll just put this in the picture so that it’s complete.
R is congruent to
C to the d
mod
n,
and everything…
and this R that she computes is going to be the original message. So Eve
is going to have a very difficult time figuring out
what the original message is. She has to solve some sort of
discrete log problem, or she has to try to
figure out what d is. Either way, it's going to be tricky.
Given this number, it's tough to know that it came from
11111111, right? It's not easy to solve the problem - basically,
right, if you could take logarithms, this would be easy to do,
but you can't do that with congruences. It's not that
obvious because of the periodicity properties.
This gcd of e and p minus 1 q minus 1 equals 1, that's important in the proof, right?
The reason why this R works out is because
this gcd is 1, p and q are co-prime, you use a combination of
Chinese Remainder Theorem and Fermat's Little Theorem to get this going.
And that's that. So by the way, notice that all these computations took like
instantly, right, and it didn't matter…
it didn't matter what numbers I used, right? I mean like here if I changed 17,
let me change 17 to something maybe a little bit bigger.
Next prime 12345678, I don’t know, let’s use another new prime,
because it's going to be co-prime, okay?
So there you go. So this is going to be a huge number, right? So 12345701 happens to be the next prime.
So now if we run these computations,
so M to the e, very quick.
That happened instantly even though the number was some huge 8 digit number,
it's still computed M to the e mod n in a second.
d is the power mod. Boom instantly, okay?
So this inverse is really quick to compute. How do we compute the inverse quickly?
The Extended Euclidean Algorithm.
And that's - I don't actually know what's going on.
You can actually look what's going on under the hood in Sage,
but I presume that's what's happening, some sort of nice algorithm like that,
and then
the R value is still the same, okay? So
you can change the e to make it more complicated or simpler it doesn't matter.
The math is still going to work out.
Just so that we have a nice
matching with the picture, I'm going to go back to 17.
We talked a little bit in class about which e’s to use.
You probably want to use something bigger than 17.
You probably want something so that 2 to the e is bigger than n,
just so that you can't take nth roots of the message that would be kind of silly.
So you actually want to do a reduction is what I'm saying,
but that's it. That's RSA.
So hopefully this gives you an idea of
how to use
RSA effectively, and how you can go about
sending messages using RSA.
This is basically the entire encryption scheme. The only thing that's missing is the proof
that R is equal to M,
but hopefully the example gives you a little bit of an insight as to why that might be the case.
Alright thank you very much for your time, hope this helped.