So RSA. Now Alice chooses two large primes, p and q,
and selects any integer, e, satisfying 1 is less than e is less than p minus 1 times q minus 1.
So before it was just p minus 1, now we have the product p minus 1 times q minus 1,
and e is co-prime to p minus 1 and q minus 1.
So here's where the two primes are coming in.
Alice then makes the pair e and n public,
so n is p times q. So she makes the product and e public,
and computes her private key, d, satisfying
1 is less than d is less than p minus 1 times q minus 1,
and e d is congruent to 1 mod p minus 1 times q minus 1.
Again, Alice can compute this quickly because she knows p,
she knows q, so she knows p minus 1 and q minus 1, and so she can
compute the inverse of e very quickly using the Extended Euclidean Algorithm.
This is a key, key fact. Alice knows p and q
so she can compute p minus 1 and q minus 1 quickly.
Remember that sentence.
So what does Bob do? Well Bob sends his message.
His message, M, is between 0 and n minus 1 or p q minus 1 inclusive.
Bob then computes a ciphertext, C, satisfying
0 is less than equal to C is less than p q,
and C is congruent to M to the e mod p q.
So we're basically reducing m to the e to the least non-negative residue.
And we're going to send C across the channel. So Eve knows
e, n, and C.
Bob then sends C to Alice and Alice then computes
R is congruent to C to the d mod p q.
Now just like before, we’d like to prove that R is equal to M.
It's going to take a little bit of effort, but we can do it.
But this is the scheme, okay? So it's basically just like the one prime situation
except we use two primes.
Let's take a look at the diagram.
So again, you can see the difference. Eve knows e and p q which is n.
Alice chooses the p and the q
and chooses the e and computes the d satisfying
d is the inverse of e mod p minus 1 times q minus 1.
Bob takes his message, C -
Bob takes his message, M, and encrypts it using M to the e mod p q
and sends C across the insecure channel,
and Alice is trying to compute R is congruent to C the d mod p q.
So just like before, computing the e-th root of C is going to be difficult
mod p q.
Again something you can try on your own, but here's the main idea.
Let's see the proof of the major proposition here; R equals M.
What's the idea that we're going to use here? We're actually going to
piggyback off of the exponentiation cipher proof from before.
So step 1 is to reduce to that case twice,
and step 2 is to put that together.
So since e d is congruent to 1 mod p minus 1 times q minus 1,
Transitivity of Divisibility tells us that e d is congruent to 1 mod p minus 1,
and e d is congruent to 1 mod q minus 1.
Since e d…
since the gcd of e d and p minus 1 and q minus 1 is 1,
GCD From
Prime Factorization tells us that the gcd of e d and p minus 1 is 1,
and the gcd of e d and q minus 1 is 1.
In particular, we're really interested in the fact that the gcd of e and p minus 1 is 1,
and the gcd of e and q minus 1 is 1,
okay, but we get both so I might as well mention it.
So thus, as C is congruent to M to the e mod p q,
Spitting the Modulus states that C is congruent to M to the e mod p,
and C is congruent to M to the e mod q.
Similarly by Splitting the Modulus again, we have that R is congruent to
C to the d mod p, and R is congruent to C to the d mod q.
So now if we look at the situation, pretend you're dividing your screen in half
along those “and” symbols, okay?
If you look at the left hand side, you have everything
mod p or mod p minus 1 that we had in the previous theorem,
and if you look at the other side we have everything mod q or
q minus 1 that we had in the previous theorem.
So if I apply that proposition twice, what am I going to get?
I'm going to get that R is congruent to M mod p,
and R is congruent to M mod q.
So that was our goal here. We took the general situation of RSA,
split it up into like two single prime situations,
and then brought them back by using the previous proposition.
We now did - we might have needed to reduce this a little bit more, but that's okay.
I'm not going to get into small, small details like that.
This is the big picture idea, okay?
So now we have R is congruent to M mod p, and R is congruent to M mod q.
We can put it together using
Splitting the Modulus or Chinese Remainder Theorem.
So you put them together, what do we get? We get that R is congruent to M mod p q,
but 0 is less than or equal to M is…
0 is less than or equal to R and M which is less than p q
and that shows us that R is equal to M,
And that finishes the proof.
So that's the idea behind RSA. So RSA:
exponentiation cipher with two primes. If you remember it like that, it might help you to
remember this in practice.