Modular Mathematics, RSA Cryptography


Alice wants to send Bob a secret message that would be meaningless if discovered or intercepted by a third party. So Alice scrambles the message, and when Bob receives it he unscrambles the message and reads its contents. If Charlie intercepts the message, he does not know how to unscramble it, so Alice's secret is safe.

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.

One Time Pad

Alice and Bob meet in a cafe, and Alice hands Bob a string of a million random digits. They part company, and later on Alice uses these digits to encrypt her messages. Bob uses the same digits to decrypt. This scheme is virtually impenetrable, but it requires Alice and Bob to meet ahead of time, in a secure setting, and share the "key", i.e. the string of random digits. The scheme also suffers if Alice has a lot to say. A high resolution image consists of a million bytes, which is encrypted via the million digits. How does she send the next picture? Alice can reuse the string of digits, but if you do this three or four times, the enemy will detect patterns. Pretty soon he will reverse engineer the random digits, and with the key in hand, he can read all of Alice's messages, including her prior messages, which he has stored for later analysis. Ideally, the string of random digits should be used only once, hence it is called a one time pad.

Public Key Encryption

In the world of e-commerce, Alice and Bob have never met, and they never will meet. They cannot share a one time pad, or any other "key" in confidence.

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.

RSA Encryption

In 1977, Ron Rivest, Adi Shamir, and Len Adleman developed the public key encryption scheme that is now known as rsa, after their initials. (Apparently Clifford Cocks made a similar discovery in 1973, but this was not known at the time.) The method uses modular exponentiation, which can be performed efficiently by a computer, even when the module and exponent are hundreds of digits long. See the previous page for more details.

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.

Digital Signature

Encrypt a message with your private key, and anyone else can decrypt it using your public key. This is a form of digital signature. Only you could have sent the message.

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.