Now we're going to look at whether RSA has the security properties we need.
We've seen that it has the correctness property,
that encryption with a public key and decryption with a private key are indeed inverses.
But we want to know also the most important property--
that it's difficult for an attacker who doesn't have access to the private key
to perform the decryption.
This is the property that we need that given e and n, which is the public key,
it's hard for an attacker to find d.
We actually need stronger properties than just this.
We want to also know that the attacker can't learn anything about the message.
This is not strong enough by itself to know that an attacker can't learn
anything about the message.
In fact, we'll see there are cases where an attacker could learn something
about the message without learning d soon.
The first thing we know is that this would be easy for someone who knows
the factors p and q--the two large primes that we multiplied to get n.
We know that because such an attacker could compute the multiplicative inverse
of e mod the totient of n.
If you know the factors of n, you know the totient,
because that would be the totient of p times the totient of q, which are both primes.
So easily solved.
Our security argument relies on two things.
The first is that showing that all ways of breaking RSA
would allow some easy way to factor n.
If we could use that way of breaking RSA to factor n,
the we could always use that to factor large numbers.
That would contradict our second claim that factoring large numbers
constructed by multiplying two large primes is hard.
We're going to show the first thing first--that other ways of breaking RSA,
other ways of finding d, would allow us to factor n.
Then we're going to argue from experience and historical effort
that factoring seems to be hard.
The first question is whether it's easier to compute the totient of n
than it is to factor n.
Our goal is to show that that's not the case.
What should we do to show that?
Here are the choices.
Give p and q, show that it's hard to compute the totient of n.
Given the totient of n, show that there is no easy way to compute p and q.
Or given the totient of n, show that there is an easy way to compute p and q.
