The process of "scrambling" a message is called encryption, a word that is related to the word crypt. The meaning of the message is buried deep within a (metaphorical) vault underground. The process of unscrambling is called decryption; the meaning is pulled out of the crypt and into the light of day.
Here is a scheme that might work. Alice asks her friend Mary to translate the message into Navaho, who broadcasts it over the radio to Frank, who translates it back into English for Bob. This is a great scheme, as long as nobody else speaks Navaho. In fact this was the case on the battlefield in World War II, where the United States employed some 400 code talkers, speaking languages that were unrelated to any European or Asian tongues. These codes were never penetrated.
This is good for a start, but Alice wants her voice encrypted and decrypted directly, without having to rely on a bilingual friend. Also, as we move in to the digital age, Alice wants to encrypt text documents and images. We need to encrypt numbers, thousands of them per second, and decrypt them on the fly. A mathematical algorithm is called for.
Bob runs an online store, and Alice wants to purchase something from his website. She needs to transmit her credit card number in an encrypted format, so that anybody listening in on the conversation will be denied any real information. This is where public key cryptography comes in. When you see the lock icon on your browser, your computer is encrypting your information, so that nobody except the intended party can receive it.
When you visit Bob's website, he provides a public key, which your computer uses to encrypt your messages. Bob can decrypt these transmissions, but only with his private key, which is held secret. The public key and the private key complement each other. They work together to encrypt and decrypt a message.
How do we know Charlie hasn't taken over a router on the internet, and produced a website just like Bob's? He can create his own public and private key, and hand you the public key, and decrypt your information using his private key. The encryption is perfect, and impenetrable, yet Charlie has obtained your credit card number. This problem is known as key management, and it is central to the success of any encryption scheme. However, it is not a problem in mathematics per se. Rather, it is a problem of organization. Often a trusted authority is established, who can confirm that Bob does indeed have this particular public key, and if he says otherwise, it isn't really him; it's an impostor. The internet uses a system similar to this, though I am oversimplifying it just a bit.
Let's assume we are sure this is Bob's website, and this is Bob's public key. How can we encrypt traffic, using the public key, so that only Bob can read it with his private key? There are several methods, but the most popular, and the one employed by the internet, is rsa encryption.
The public key is a modulus m and an exponent e. A message is represented by a number c between 0 and m-1. (If the message is longer, chop it up into pieces and encrypt each piece.) Raise c to the e power mod m and transmit the result.
The private key is the same modulus m and the inverse exponent d, such that e×d is 1 mod φ(m). As you recall from the previous page, c to the e to the d gives c back again. Raising to the e encrypts, and raising to the d decrypts.
In a typical aplication, m is the product of two large primes p and q. Thus φ(m) = (p-1)×(q-1). Given an exponent e, find the modular inverse relative to φ(m), and call it d. This builds the public and private keys.
The security lies in the difficulty of factoring m into its primes. Without p and q, Charlie cannot derive φ(m), and cannot compute d. Anybody can send encrypted data to Bob, but only Bob can decrypt.
As factoring algorithms improve, we are forced to use larger values of m. At the dawn of e-commerce, 40 bit encryption was sufficient, but in just a few short years the internet has advanced to 128 bit encryption, and is considering 1024 bits, to keep ahead of the evolving factoring algorithms running on ever faster computers. Some people believe factoring is an intractable problem that becomes exponentially more difficult to solve as the numbers grow large. If we chose large values of m, such as 5000 bits, we'll be fine for the next billion years. Others believe an efficient factoring algorithm exists; it just hasn't been discovered yet. To guard against this possibility, mathematicians are developing other forms of public key cryptography, such as elliptic curves and discrete logs, that have nothing to do with factoring. These may gain widespread acceptance in the future, but for now, rsa reigns supreme.
If Alice encrypts her message with her own private key, then reencrypts with Bob's public key, only Bob can read it, and he knows it came from Alice. This is private, signed communication in the digital age.