Encryption. The word alone makes us think of something we’d rather not know. It sounds too hard. Too mysterious. Like something the cat dragged in. Enter the Internet. Bring on e-commerce. Suddenly we recognize our vulnerability and our need for veracity.

Because we want to keep our information secure, we have to implement some kind of encryption or use a PKI or contact a vendor for certificates or… But wait. Before you rush off and implement an unsound or unnecessarily expensive strategy, let’s discuss cryptography, the science of creating cryptographic algorithms. Cryptoanalysis is the science of breaking or cracking messages that have been encrypted using those algorithms. Encryption is the process of changing the appearance of a message by applying a cryptographic algorithm.

Aww, Yeech. It’s Mathematics

Long, Long Ago, and Far, Far Away…

Caesar has been credited with the use of the first algorithms for obscuring data. The earliest attempts were to disguise—you guessed it—troop movements. A strip of papyrus was wrapped around a stick of wood, spiraling from one end to the other. The message was written down the length of the stick on the paper. The papyrus was unwound and, behold, the message was unreadable. A runner was dispatched with the message. A general at the receiving side had a stick of wood with exactly the same dimensions. Winding the papyrus back around the stick made the message clear. If the runner was captured, the enemy would have a hard time understanding the message. The name of the stick? A cipher. This is an example of encryption where the algorithm is unknown.

Later, Roman troop movements and other secrets of state were disguised by using simple replacement algorithms. Each letter in a message was replaced by the next character in the alphabet, or some other simple character-for-character substitution. The monoalphabetic substitution cipher was born.

Fast forward. In the 1700s letters were replaced with numbers and values were added to the numbers to make the task of deciphering the message much harder. For example, replace each letter of the alphabet with a number. A becomes 01, b becomes 02, etc. Use this key to replace each letter in a message. Then add 3 to each number in the message. So the letter A becomes 04, B becomes 05, Z becomes 29, and so on. A simple message such as, “I am going to kill the king.” becomes:

12 0416 1018121710 2318 14121515 231108 14121710

Decryption reverses the process. Subtract three from each number and look them up on your alpha-to-numeric-to-alpha conversion table.

This simple encryption algorithm uses the same number (three) or key in the process (look up the letter on the chart , add three, or reverse), so it’s said to be a symmetrical key cryptographic algorithm.

Next, letters were substituted by using two alphabets. One alphabet was used for the odd characters in the message, another alphabet to replace the even characters. These combinations are known as polyalphabetic ciphers. To see how this might work, number the letters of the alphabet from 1 to 26. Next, for the odd position alphabet change each number by adding 3 to the number before. (1 stays as 1, 2 becomes 4, 3 becomes 7, 4 becomes 10, and so on.) For each letter take the results and find the modulus 26 (or mod 26) of this number. The modulus is the remainder left after simple division. Let’s do a few. 1 mod 26 is 1, 4 mod 26 is 4, 28 mod 26 is 2. Replace each letter of the alphabet with the letter represented by this result. So A remains A, B becomes D, J becomes B. The alphabet for odd positions becomes:

To create the even alphabet, use the number 5 instead of the number 3 and add 13 to the result before taking the modulus 26. A or (1+13) mod 26 becomes 14 or N. B or (6+13) mod 26 becomes 19 or S. The alphabet for even positions becomes:

NSXCHMRWBGLQVAFKPUZEJOTYDI

Many variations of these algorithms have been used in history.

Like the papyrus cipher, the alphabetical algorithms relied on the fact that the algorithm was unknown.

Its Power Is in Its Exposure

Like the ancient ciphers, modern encryption uses numbers as keys. The numbers are just larger—very much larger—and the algorithms are known. Well-known algorithms can be examined by everyone, and everyone has a chance to find problems with it. Over time the successful algorithms (those that keep private data private) are easily identifiable—they’re still used and discussed. You don’t have to know higher mathematics to determine if the algorithm you’re choosing is a good one; you can rely on people who know the math as well as how to test the algorithm to help you identify the one you need. But the algorithms are known? How can that be? Doesn’t that mean others could decrypt the messages? The well-known algorithms used today rely on something else, some quantity that must be used with the algorithm for it to work. That something else is either something both parties know—a shared secret—or something each has a part of—key pairs.

Shared Secrets and Key Pairs

If we wish to send confidential documents between my city and yours, we could invest in a lock box with two identical keys. Each of us has a key. I place my documents in the box, lock it with my key, and send the box your way. On its journey, no one else can unlock the box and get at its secrets. (Well , they could hack in, but that’s another discussion.) When it arrives, you unlock it with your key and retrieve the documents. The algorithm, a locked box that requires a key, is well known. The item that keeps our documents private is the shared secret—the key. We each have the identical key. This is, of course, just a modern version of Caesar’s cipher—a symmetrical key cryptographic algorithm. The difference: The algorithm is known.

But what if I don’t want us to have the same key? We have a lock box with two keys. One locks it and one opens it. I lock the box with my key; only your key can open it. You lock it with your key; only my key can open it. We each have a key, but they’re different. One key is the inverse of the other. This is known as an asymmetrical key cryptographic algorithm. It’s the basis for public key cryptography. Since binary numbers don’t come with padlocks, how is this done? Here’s where the mathematics comes in.

Our modern-day key pairs are factors. As you recall, if I multiply two numbers, I get a product. If I know the product and one of the numbers, I can get the other number. If that other number were used in an encryption scheme, I could then decrypt the message. Since we all know the multiplication table, what makes the key secure? If the product has as its factors sufficiently large prime numbers, the knowledge of the product’s factors is sufficiently obtuse to keep it secret. But if I know one of them, I can discover the other.

Modern Algorithms and Implementations: DES

Unlike early algorithms, the Data Encryption Standard (DES) algorithm (a symmetrical key algorithm) is published and available to anyone. The security of messages using this standard is similar to the security of the locks on your car or house—they rely on the protection of the key.

The DES key is 56 bits long. No one, it seems, could ever guess which key you’re using.

Wrong. In June 1997 some folks used a brute force approach, in which every possible key was tried, one after another; the attack put a large number of computers working in parallel for 140 days to find the correct key. DES is now considered to be fairly easy to break with modern computers.

Of 963 security products examined in a recent survey by Trusted Information Systems, 466 use DES.

A variant of DES, Triple-DES, uses DES three times with three different unrelated keys, thereby strengthening the encryption.

R2D2, er… RC2 and RC4

Modern cryptography recognizes that computers can break symmetrical key algorithms. RC2 and RC4 use key pairs and are asymmetrical key cryptographic algorithms. Each key pair consists of a public key and a private key.

These proprietary and until recently unknown algorithms are owned by RSA Data Security, Inc. Keys of selectable varying length may be used.

RC4 is the algorithm used in Netscape’s Secure Sockets Layer (SSL) communication protocol (the one used to encrypt your credit card when you purchase items over the Web). Up to 128 bits can be used in the key.

A message encrypted with a 40-bit key was decrypted after using a brute-force attack to recover the key. This took only 3.5 hours.

The algorithm uses very large prime numbers to generate a public and a private key. When very large prime numbers are used, it’s almost impossible to factor out the private key if you know the public key. Since the RSA algorithm is very slow, it’s often used to encrypt a symmetrical key; then the encrypted key is used to encrypt the rest of the data. The symmetrical key is randomly generated; therefore, only the private key can be used to determine it.

Other symmetrical and asymmetrical key algorithms in use include IDEA, SkipJack, El Gamal, Blowfish and Diffie-Hellman. A newer type of algorithm, Elliptic curve public key cryptosystems, is in testing. See www.ssh.fi/tech/crypto/algorithms.html.

Public Key Cryptography

Say you want to securely communicate with members of your company and trading partners over the Internet. How do you set up a secure transfer of keys? How can you implement a strategy that doesn’t overwhelm you with its details? Public key cryptography allows the secure exchange of messages in a public environment. It relies on the use of two keys that are the inverse of each other.

Your public key is published—available to everyone. Your private key is held by you alone. I’ll use your public key to encrypt (using RSA or El Gamal) my message before sending it to you. Only you know your private key, so only you can decrypt the message. Want to be sure I really sent the message and that nobody changed it? I use my private key to seal the message—you can use my public key to unseal it. (See, “Integrity Protection” on the following page.) So how do you publish your private key? How do I find it? Where do I get a public and private key pair? Some companies have chosen to implement their own Public Key Infrastructure (PKI); but you can obtain a key pair and make your public key available by contacting Verisign at www.verisign.com. (I’ll cover PKI in a future column.)

Kerberos

Kerberos (in classical mythology, Kerberos the three-headed dog guards the gates of Hades) was originally developed to guard the resources of MIT from its creative students. A Kerberos server or Key Distribution Center (KDC) is used to authenticate users. Only the server and the user know the password. The Kerberos server can set up a secure communications channel between two authenticated users by issuing Kerberos tickets, one for each user. Each ticket identifies both parties, is time-stamped (to prevent its use or misuse—such as a replay attack), and contains a time duration (how long the ticket is valid) and a session key. Tickets are encrypted using the users’ passwords; thus only the users can read the tickets and obtain the session key. The session key is then used to encrypt a message. The first message includes the ticket key for the recipient. When both users have the session key, secure communications can proceed. [For a technical explanation of Kerberos, read Michael Chacon’s column, “A Matter of Security,” in the May/June 1997 issue.—Ed.]

Choices, Certificates, and the Spy

So,where’s the beef? You know you don’t want to clutter up your system with all these keys or key pairs. Isn’t the question for most of us not which algorithm to use but which product to choose? And can’t all of these fancy, schmantzy algorithms be broken?

You’re right on all accounts. But, you still have to put the lock on the box. The question of whose lock and where to store the keys isn’t easy to answer, nor can it be resolved in this column. On the other hand, the implementation of your chosen strategy may be easier than you think. The processing and key storage and sharing happens under the hood, and you may have as little to do with it as you choose. Keys can be stored in certificates, which can be handled by third-party trusted organizations. You can implement a Public Key Infrastructure or your own as well and become part of a certificate hierarchy in which certificate authorities trust other certificate authorities. To share data within your organization or simply to protect data on digital devices, use a product that implements the algorithms I’ve discussed here.

The reality is, you and your peers will be using these technologies very soon now, especially PKI, and the time to learn more is now.

As the spy whispered to me when last we tangoed, “In the future I see three types of computer professionals: Those who develop and implement PKI, those who use PKI to their advantage, and those whose biggest challenge will be to ask, ‘Would you like some fries with that burger?’”