The RSA comes from the initials of its three inventors--
Ronald Rivest, Adi Shamir, and Len Adleman.
One thing you'll notice in cryptography is many of the most important ideas
are named after groups of people.
We have Diffie-Hellman. We have RSA. We have Needham-Schroeder.
We'll see lots of other examples.
This is different from what we tend to see in mathematics
where most of the big ideas have just one name.
Cryptography is a very collaborative process.
The way Rivest, Shamir, and Adleman worked together--
Rivest and Shamir came up with lots of ideas, trying to come up with
ways to provide this public-key property,
and Adleman would find the flaws in them.
They kept trying this and eventually came up with the one idea that Adleman
couldn't find any flaws in, and that's the one that we know of today as RSA.
RSA was the first successful public-key encryption system.
It's also one of the most widely used crypto systems
and continues to be the most widely used public-key system today.
The way it works is actually quite simple.
We have the public key as a pair of two numbers, e and n,
where n is the product of two primes.
The secret key is a pair of two numbers.
The n is the modulus, which is the same in both the public and the private keys.
The difference is in the public key we have e.
In the secret key we have a secret number d.
To perform encryption of some message m,
we raise m to the e power mod n.
To perform decryption using the secret key, we have some ciphertext,
which we raise to the d power mod n.
That means encryption and decryption are the same functions,
just with different powers that we're using, depending on whether we're using
the public key or the secret key.
RSA is a very important cryptosystem, but it's simple enough
that we can fit the whole thing on one screen
or even on a license plate.
Unfortunately, in the state of Virginia,
the license plates don't allow you to have exponents in them.
If you live somewhere where you're DMV allows you to have exponents in license plates,
that's great. You can get a much better version of this than I have.
Actually understanding why it works and the argument that it's secure,
require understanding some more things,
and in particular, the we choose the values of e, d, n.
In fact, we have to be careful how we choose the message as well.
