Hello everyone. Welcome to Week 9
of Carmen's Core Concepts, my name is Carmen Bruni.
In this video, this is part 1 of Week 9,
we're going to talk about RSA
which is an encryption scheme, a public key cryptography scheme,
and it's very well-known, very well-used still, even though it's
somewhat…40 years old or so.
RSA stands for Rivest, Shamir, and Aldeman,
the 3 people who created the algorithm.
Something to keep in mind, so I do want to say something, that
this is an RSA video. There are lots out there, this isn't
unique by any stretch of the imagination.
I don't even claim that this is the best video on RSA out there.
There are probably others that are much, much more well…
practiced, rehearsed, well-informed, whatever.
What I do want to say though is that I don't know of any video that does exactly this approach,
and the approach that I'm going to take is that I'm going to talk about why
RSA needs two primes as opposed to just having one.
So I'm going to try to - so what I'm going to do is I'm going to explain
like an RSA with one prime,
that's going to be called an exponentiation cipher,
and then I'm going to talk about what happens when we have 2 primes.
So let's get started, let's actually start by recalling
the public key cryptography scheme.
So suppose Alice and Bob want to share a message, but there's an eavesdropper, Eve,
watching their communications, okay,
and in our situation, we're going to assume that Eve is just looking
at the insecure channel between Alice and Bob.
So Alice will publish some public information,
and Bob will try to send Alice a message by
encrypting this message using the public information,
and Eve will be able to see the public information and the encrypted message, C.
And Alice’s job is going to be to create a scheme where she can decode
the message sent from Bob, and so that Eve also cannot
decode the message.
How are we going to do it? We're going to try to do that
first by an exponentiation cipher, okay?
And in an exponentiation cipher, so maybe
a little bit of thought before we go into this, exponentiation cipher
you should be thinking, “Okay, I need to take
exponents somewhere. I need to do
an exponentiation at some point,”
and it turns out that that's true. We do need to do exponentiation, which we will
see where that comes into play in a minute.
So in this encryption scheme,
Alice is going to choose a large prime p,
and an integer e satisfying e is between 1 and p minus 1,
and the gcd of e and p minus 1 is 1, okay?
So e’s a co-prime to p minus 1,
and it's between 1 and p minus 1.
Alice then makes the pair, e and p, public
and she's going to compute her private key, d,
and her private key, d, satisfies 1 is less than d is less than p minus 1,
and e d is congruent to 1 mod p minus 1.
So why do we not want to choose p minus 1 here for e?
And the reason why is because of this. So if you choose e to be p minus 1,
then d is also p minus 1 and you'd like e and d to be distinct. So,
we're going to just avoid that by just not choosing e to be p minus 1.
We also don't want to choose e to be 1, because then we're not
actually going to be encrypting anything. We're going to be taking
a message to the power of e, and so if e is 1, that's kind of boring.
Okay.
Something to note, that even if p is a large prime,
the inverse of e can be computed very quickly using the Extended Euclidean Algorithm.
The reason why we require the gcd of e and p minus 1 to be 1
is so that e is invertible mod p minus 1, so that's something to keep in mind as well.
So we need the inverse of e mod p minus 1 to exists, we'll see why
in a minute.
To send a message, M, Alice - to Alice… to send a message,
M, to Alice, and this message, M, is going to be
an integer between 0 and p minus 1 inclusive.
Bob is going to compute a ciphertext,
C, satisfying 0 is less than or equal to C is less than p,
and C is congruent to M to the e mod p,
and Bob will send C to Alice.
So keep in mind, what can Eve see? Eve
can see e, p, and C, which we'll see in the next diagram.
Now what is Alice going to do to decrypt?
Alice is going to take that message, C,
and compute C to the d mod p with 0 less than or equal to R is less than p.
So...
here's the encryption scheme. What things do we need to know?
So first thing we need to do is we need to prove something about R. So R is
congruent to C to the d, we need to prove that R is congruent to M,
that’s something we need to do. It's not too hard, but we will need to actually compute that.
If Bob chooses C equals 0, then
M to the e is 0. If Bob chooses C is 1, then M to the e is 1.
Those are kind of bad messages to pick, so maybe you want to restrict those, maybe you don’t.
The scheme works with those two things, so I'm going to just
include them just for a theoretical sense.
but you probably want to avoid them in practice.
Okay, so, let's head to the proof.
Oh let's head to the diagram before we head to the proof. So
I like to draw the diagram just to remind us of
what the situation is. So Alice computed e and p, made that public,
computed a private d which is the inverse of e mod p minus 1.
e and p is public, Eve and Bob know it, Bob computes…
Bob takes his message, M, his private message, M,
an integer between 0 and p minus 1,
and computes C, which is M to the e mod p.
Bob and sends C across the insecure channel,
so Eve knows e, p, and C.
Now Alice gets the C, and Alice knows d, so Alice is going to
compute R is congruent to C to the d mod p.
Now something to think about in this scheme,
so Eve gets e, p, and C, so something to note is okay well
if Eve has C, can she compute M?
She knows C and e, so can she compute -
basically what she's trying to ask is, “Can I compute the e-th root of C mod p?”
And it turns out that this happens to be a difficult problem.
Just to see an example,
suppose I told you that
M to the [6] was congruent to 9 mod 11,
and I asked you to determine what M was, okay? How would you do that?
I mean really the only way that you're going to be able to even try it is
by just plugging in values for M.
There's a lot of possible values for M if p is large,
so this doesn't seem like a very efficient attack, okay?
Now 11 is small enough that you could probably reason that I believe the answer should be 2.
2 to the 6 is 64, and 64 is congruent to 9 mod 11.
So that one's fairly easy, but you could imagine, like I mean if I ask you the same question
M to the power of 6 is congruent to…
who knows… 5 mod 11.
What's the answer? I don't know. I mean so you can imagine the situation being very difficult.
This is a tough problem to solve; computing e-th roots mod p.
At least that’s what we believe.
Okay.
So, big proposition here. So we're going to
prove that R is congruent to M mod p,
and from this we're going to conclude that R equals M
because of the restrictions on R and M.
R and M are both less than p and non-negative,
okay, so that will force them to be equal if they're congruent mod p.
Take a minute, pause the video here, try to prove this.
If you can prove this, it shows that you - if you prove this without going back in the
slides, it shows that you really understand exponentiation ciphers,
so hopefully you can do that. If not, go back to the previous slides,
check out exponentiation ciphers, and see if you can prove that R is congruent to M mod p.
Now that you’ve paused the video, hopefully tried it,
let's take a look at the proof.
The proof, it needs to be split up into 2 cases,
which might not be obvious at first but it will be obvious once we do it, okay?
If p divides M, everything is 0 and we're done.
So we might as well assume that p doesn't divide M;
get to the interesting case.
So from here, recall that e d is congruent to 1 mod p minus 1,
and using this, what do we have?
So we have that R is congruent to C to the d mod p,
which is congruent to M to the e to the d mod p, by the definition of C,
remember C is the same as M to the e mod p.
M to the e the d is the same as M to the e d mod p,
and M to the e d, well e d was congruent to 1 mod p minus 1,
so we can actually use one of the corollaries to Fermat's Little Theorem
which says that well if e d is congruent to 1 mod p minus 1, then M
to the e d is congruent to M mod p, provided that the gcd of M and p is 1,
which is the case if p doesn't divide M.
And we're done.
So it's actually a really, really short proof
and it uses Fermat's Little Theorem, which is cool. This is one of the reasons why we needed it.
So here we have it, okay, maybe I'll just end it at that, okay?
So then therefore, R equals M by that argument that I mentioned at the beginning.
This proves that exponentiation ciphers work. Okay?
So they work.
Bob can send a message, Alice can decrypt it.
So that's the good news, the good news is that this works.
The bad and the ugly is that well…
the bad and the ugly actually are kind of the same thing I guess.
Eve can compute d just as easily as Alice, right?
If Eve knows p and e, there's no reason why
Eve can't compute the inverse of e mod p minus 1,
right, because Eve knows p, so therefore she knows p minus 1. That's not hard.
So our scheme is not secure, this is pretty bad.
So you actually wouldn't want to use this scheme in practice because well…
it's not secure.
So how do we rectify this problem? How do we solve this problem?
What we can do is we can include information instead of about one prime,
we can include information about two primes.
It might not be obvious why that matters, right? So before we used
one prime, the scheme works but it's not secure,
and if we include two primes, how does that make the scheme secure?
Something to think about. Think about it while we're going through the scheme, okay,
that's what RSA does though. It's a single prime exponentia-
so a single prime exponentiation cipher that we saw.
RSA is like a dual prime or two prime
exponentiation cipher.
So let's think about why this is going to work.