Now let's get to the issue of security.
Is this scheme more secure than single prime…
exponentiation cipher?
The answer is yes, of course.
Not just because of its name but because it's actually secure.
Can Eve compute d?
And before we said, “Well Eve had e and p, and so Eve
could compute p minus 1, so Eve could compute the inverse of e mod p minus 1.”
But now, Eve only has the product p q,
so computing p minus 1 times q minus 1
when you only have p q is actually quite difficult.
You either have to factor n,
which is a very hard problem, or do something else that nobody's thought of at this point.
Nobody knows how to do this problem. To get p minus 1 times q minus 1 from p q.
This problem we believe is hard. There's no proof of this fact.
There's evidence there’s…you know, we believe that it's hard,
but proving that a problem is hard is not…
it's not easy.
Basically the proof that a problem is hard is that it hasn't been done before,
is basically the proof.
It's not a great proof, but
anyways we do believe that factoring numbers is hard.
Eve could also break RSA if she can solve the problem of
computing M given M to the e mod n,
but again we know this is a hard problem as well, right? Computing
the e-th root of M to the e is not so easy mod n.
So let phi of n be the Euler Phi Function.
Sometimes this is denoted by varphi, sometimes it's just denoted by phi.
I think I denote it by phi later instead of varphi in LaTex.
Either way is fine, people will know what you mean.
Note that, in this case - so I'm not going to define what the Euler Phi Function is,
but I am going to say that in the case when n equals p q is a product of distinct primes,
then phi of n is equal to p minus 1 times q minus 1.
It's important that they're distinct.
This isn't true about this function if they're not distinct primes.
How does Alice choose primes p and q?
Well we know that they must be distinct, okay?
That’s something that we saw in the algorithm - in the proof before, right?
We'd split the modulus at the end, or use the Chinese Remainder Theorem,
so we needed p and q to be distinct.
How does Alice choose these primes? Well it turns out that the way
to choose them is actually be very silly.
If you want to choose a large prime number, turns out that
you should just choose a large number.
We should be a little bit smarter,
let's choose a large odd number, since we know that large even numbers aren’t prime.
So we choose a large odd number,
it turns out that if we choose enough of these numbers, that
we're going to eventually pick a prime. Now how many we have to choose?
There's an argument using the Prime Number Theorem
which off the top of my head I believe says
if you have…let's say p is 100, and you want to know if you can find it a hundred digit prime.
If you pick about…I think it's around the 75 mark,
it's not exact, but if you pick around 75 big odd numbers,
that's going to be enough to have like a 50/50 chance that one of them is prime.
That’s pretty good, and it's not too hard to pick 75 large odd numbers.
The one thing you might want to ask is, “Well how hard is it to check if a number is prime?”
So clearly it must not be too hard based on
what I just told you, right, and it turns out that it's not. There's actually
quick-ish algorithms that will determine if a large number is prime or not.
They're not insanely fast, but they're good.
So…maybe let me say this,
in fact they're even better if you allow for something called probable primes,
which are primes that are highly likely to be prime,
let’s say 99.9999% likely to be prime,
whatever that means. I'm not going to justify what that means, but
this is an active area of research: probable primes things like this. Check this out online.
There's some pretty interesting stuff. I believe all of that is true though.
My numbers might be off a little bit, especially with the
Prime Number Theorem argument off the top my head,
but I believe that's roughly correct. Again you should check that out, if you want you can google
that argument. I'm sure somebody's done it.
What if Eve wasn't just a passive eavesdropper?
So what if Eve could change the data?
So instead, let's say Alice publishes her public key
and Eve says, “No, no, I don't like that public key. I'm going to publish my public key
and pretend that I'm Alice,” and then Bob's going to encrypt using
Eve's public key,
and then Eve is going to take Bob's message and be like,
“Ha I'm going to decrypt it,” and then send the
encrypted message to Alice using Alice's public key.
So Alice and Bob think everything's working, but
actually Eve's in the middle attacking everything, okay?
So there are ways to circumvent that. They involve things…
certificates, and identity checks, and things like this.
This is a huge active area, I believe for example,
Verisign, a company which produces certificates,
they're like a billion dollar company I believe,
and it just involves the idea of just verifying identities,
which is pretty cool and crazy to think that, you know, such a…
it's an important idea but it's not too hard mathematically,
and it's actually worth a lot of money. So,
this is a big active area of research and a big active area of interest for people.
What are some advantages to RSA? We believe it's secure, it's pretty quick,
encryption and decryption can be done with the same sort of black box, right?
Just taking powers of numbers,
and they can be done very quickly using the Square and Multiply Algorithm.
I didn't mention that, but we can use the Square and Multiply Algorithm to do it pretty quickly.
Alright let's take a look at an example.
Let p be 2, q be 11, and e be 3. Compute n, phi of n, and d.
So here I used just the normal phi, that's fine.
Compute C is congruent to M to the e mod n when M is 8.
Compute R is congruent to C to the d mod n when C is 6.
Pause the video, take a chance - take a minute.
Try to solve these three problems.
And now that you're back, we can see the solutions.
n, phi of n and d are pretty simple. n is the product of p and q,
that's 22. Phi of n is p minus 1 times q minus 1, so that's 10.
d is the inverse of e mod phi of n.
It turns out if you do that computation, so you want to solve 3d is congruent to 1 mod 10.
Check out all 10 numbers, so 3, 6, 9,
12, which is 2, 15 which is 5, 18, which is 8, 21 which is 1 mod 10.
So how did I get from 3 to 21? I multiplied by 7,
so d is congruent to 7 mod 10.
So for part 2, we’d like to compute M to the e mod n, when M is 8.
So let's do that, we have 8 cubed which is 8 times 64,
64 is the same as minus 2 mod 22,
8 times minus 2 is negative 16, which is 6.
How did I do this? Well again I split up 8 cubed is 8 times 8 squared.
It seemed like the most logical thing to do,
and then I just simplify. You could just compute 8 cubed
which is some relatively big number, 512 I believe,
and then go through it, that's fine as well, but I prefer to do
a little bit of the computation then reduce, then do a little bit more and reduce.
It's kind of like the Square and Multiply Algorithm except you do it somewhat randomly.
You do it in the way that makes the computation easier.
Great, so C is congruent to 6 mod 22.
Now to solve part 3, there's the easy way to do it, right?
We know that C is congruent to 6,
so C is 6, then if I’m decrypting, I get R and
we already proved that R is the same as M, so
C to the d should be congruent to 8 mod n,
but if you don't want to do it that way, we can actually just compute it by hand,
and I should probably do one more computation just so that you see.
I don't know if this is standard notation to write the equivalent signs in two rows like this
and then read it left to right, but that's what I'm going to do.
So C to the d is congruent to 6 to 7 mod 22 -
this is just so that it fits on one slide by the way.
6 to the 7 is big,
one way we can split this up is using the Square and Multiply Algorithm.
One way to split it up is we can take like 6 squared cubed
and multiply it by 6,
6 squared is 36, 36 mod 22 is 14,
14 is still kind of big…
maybe it's not the best way to do it.
If you're brave and if you know a little bit about…
small powers,
you’ll know 6 cubed is the same as 216,
and that's going to help us here. So 6 cubed is 216, and 216 mod 22
is minus 4. 216 is very close to [220],
that's why I use 6 cubed here, because 216 is close to [220].
Now you might argue how do I know that in hindsight? Well okay, I mean,
you practice, you gamble, you take chances, and
sometimes you're rewarded by taking a chance and computing 6 cubed.
Anyway so based on that, now we have 6 times negative 4 squared, 6 times 16,
the same as 6 times minus 6, which is negative 36, which is
the same as 8 as we expect.
And that's it. So hopefully this video gave you a little bit of insight
to the RSA algorithm.
Hopefully the example helps you to understand a little bit,
and hopefully you understand how to go from a single prime exponentiation cipher
to a two prime RSA algorithm.
So that’s great, that's all I have to say. Thank you very much for your time and good luck.