| | |
Bob considers mailing the message to Alice in a box with a padlock on it, so that Eve could not inspect the contents -- but quickly realizes that upon receipt of such a package, Alice wouldn't be able to open it either.
However, Bob has an idea. He puts his secret message in a box, and locks the box with a padlock, and then he writes in marker on the outside of the box the following instructions: "Alice, when you get this, don't try to remove my lock. Just put your own lock to the box (so that it is doubly secure) and send the box back to me. Bob then mails the box to Alice. Eve, of course can't get inside to see the message. Alice dutifully follows Bob's instructions, putting her own lock on the box and mailing it back to Bob. When the box comes back to Bob, he removes his initial lock, leaving Alice's lock on the box. Then he mails it one final time back to Alice, who is now able to remove her lock and see the contents inside.
Note, every time the box went through the mail, it had a lock on it -- preventing Eve from seeing what was inside. Further, the keys to the locks never had to be shared with anyone -- which heightens the security of this process all the more.
This method, while secure, requires a lot of back-and-forth communication between Bob and Alice. With a little bit of thought, we can make the process much more efficient. Essentially, the box with Bob's lock on it was just a vehicle to get Alice's lock on the box. What if Alice just sent Bob her lock (in an unlocked state) through the mail first? She would be hanging onto the key, so it doesn't matter if Eve sees the lock. For that matter, Alice could make several (unlocked) copies of this lock and send a whole bunch of them to Bob, so that he would have them on hand any time he needed to send her a secret message. Alice could sell these (unlocked) locks in Walmart and at the Post Office, for anyone to use to send her a secure message. She could even send one to Eve, out of spite, knowing Eve couldn't do anything with it.
Now, obviously, doing this with physical padlocks is not terribly practical -- padlocks are expensive, after all. But what if this padlock took the form of a number (or actually, a pair of numbers), that could be posted on Alice's website for anyone to download and use to encrypt a message they wanted to send to Alice? How can one use numbers in this way to "lock-up" a secret message?
The following describes one way to do this, called the RSA encryption scheme - the most popular of the "public key codes"...
Alice picks two large primes $p$ and $q$, and multiplies them together to get $N=pq$. She then picks another large value, $e$, that is relatively prime to $\phi(N)=(p-1)(q-1)$. Note, to do this, she just picks a random large value and checks with the Euclidean Algorithm if $\gcd(\phi(N),e)=1$. If it should ever be the case that $\gcd(\phi(N),e) \not= 1$, she just keeps picking other random large numbers $e$ until she has one that works (even running the Euclidean Algorithm several times is "computationally cheap"). She then posts $(N,e)$ to her webpage. This pair of values constitutes her "lock".
She keeps the values of $p$ and $q$ secret, keeping their values unknown to anyone, even Bob. These two values will form the "key" to her "lock".
Now suppose Bob wishes to send her a message. He first converts his message into a number $M$. (There are a number of ways to do this - and the method used can be completely public without hurting the security of the system.) Next, using successive squaring, creates an encrypted form of his message, $C$ in the following way:
$$C \equiv M^e \pmod{N}$$
He may now send his encrypted message $C$ to Alice. Eve is unable to undo the exponentiation in any sort of timely way, if the numbers involved are large enough. However, Alice knows the values of $p$ and $q$, and this gives her a leg up on Eve...
Much like a deck shuffled in the same way comes back to its original order eventually, and seeing the result of one of these shuffles allows you to predict how many more shuffles you will need. The same can be said of raising something to a power under a modulus. To be more precise, we would like to be guaranteed that we can find some number $d$ so that
$$C^d \equiv M \pmod{N}$$
However,
$$C^d \equiv M \pmod{N} \quad \quad \textrm{ implies } \quad \quad (M^e)^d \equiv M \pmod{N}$$
So then, under an assumption that $M$ is relatively prime to $N$ (which is an easy assumption to meet provided $N$ is significantly larger than $M$), we can cancel an $M$ from both sides to obtain...
$$M^{ed - 1} \equiv 1 \pmod{N}$$
Now Alice knows (as do we, by Euler's Theorem) that
$$M^{\phi(N)k} \equiv (M^{\phi(N)})^k \equiv 1^k \equiv 1 \pmod{N} \textrm{ for any integer $k$}$$
Further, Alice (unlike Eve) can easily compute $\phi(N)=(p-1)(q-1)$ as she knows the values of $p$ and $q$. So Alice tries to find $d$ so that
$$ed - 1 = \phi(N) \cdot k \quad \textrm{ for some integer $k$}$$
or equivalently
$$ed \equiv 1 \pmod{\phi(N)}$$
Here again, Alice can use the Euclidean Algorithm to find $d$, as it is just the multiplicative inverse of $e \pmod{\phi(N)}$. (Recall, Alice purposefully chose $e$ and $\phi(N)$ to be relatively prime, ensuring that a multiplicative inverse exists.)
Once she has found $d$, using her knowledge of $p$ and $q$, she uses the method of successive squaring to find $C^d \pmod{N}$, and the message $M$ is revealed as a result.
This method of encryption, and ones very similar to it, form the most secure ways of keeping transmitted information secret today. Is this method completely secure? ...or can Eve somehow figure out the values of $p$ and $q$ in an efficient manner even when the numbers involved are large? No one currently knows... but secrets of governments, corporations, terrorists, and commerce on the internet are betting that no such weaknesses exist.