Modern cryptography

Secure cryptosystems

As mentioned before, most of the ciphers we have examined are not really cryptographically secure, although they may have been adequate prior to the widespread availability of computers. A cryptosystem is called secure, if a good cryptanalyst, armed with knowledge the details of the cipher (but not the key used), would require a prohibitively large amount of computation to decipher a plaintext. At first, this may seem like an unreasonably strong definition; you may be thinking that, given a mass of encrypted data, how is the cryptanalyst to know how it was encrypted? If you are encrypting your own files, for personal use, this is probably so. But today, most encryption is done by software or hardware that the user did not produce himself. One can reverse engineer a piece of software (or hardware) and make the cryptographic algorithm apparent, so we cannot rely on the secrecy of the method as a good measure of security.

There are several widely used ciphers which are believed to be fairly secure. We will not go into the details of any of these; most of the algorithms are quite involved and require manipulations at the bit level-- maple is not really the appropriate tool for them. Implementations are widely available, both commercially and as free public software (see, for example, the International Cryptography page).

Probably the most commonly used cipher today is DES (the Data Encryption Standard), which was developed in the 1970s and has been adopted as a standard by the US government. The standard implementation of DES operates on 64-bit blocks (that is, it uses an alphabet of length 2⁶⁴-- each ``character'' is 8 bytes long), and uses a 56-bit key. Unfortunately, the 56-bit key means that DES, while secure enough to thwart the casual cryptanalyst, is attackable with special hardware by governments, major corporations, and probably well-heeled criminal organizations. One merely needs to try a large number of the possible 2⁵⁶ keys.^3.19 This is a formidable, but not insurmountable, computational effort. A common variation of DES, called Triple-DES, uses three rounds of regular DES with three different keys (so the key length is effectively 168 bits), and is considerably more secure.

Other commonly used ciphers are IDEA (the International Data Encryption Algorithm, developed at the ETH Zurich in Switzerland), which uses 128-bit keys, and Blowfish (developed by Bruce Schneier), which uses variable length keys of up to 448 bits. Both of these are currently believed to be secure. Another common cipher, RC4 (developed by RSA Data Security) can use variable length keys and, with sufficiently long keys, is believed to be secure. Some versions the Netscape web browser used RC4 with 40 bit keys for secure communications. A single encrypted session was broken during 1995 in about 8 days using 112 networked computers (see Damien Doligez's web page about cracking SSL for more details). Even though this algorithm has been ``cracked'', it seems that this scheme is certainly good enough for everyday use considering the resources required to decrypt a single session. In any case, current web browsers offer much more security-- a 40-bit key is the weakest offered. For example, most online banking applications use 128-bit keys.

There are, of course, many other ciphers in common use, and more being developed all the time.

   
Message digests

Related to encryption are ``Message Digests'', or cryptographic hash functions. A message digest takes an arbitrary length string and computes a number, or hash, from it. Changing the string changes the value of the hash. Hashing functions also play a major role in searching and sorting, and hence in computer databases. While it is obvious that several plaintexts must correspond to the same hash value, it is a difficult problem in general to construct such a plaintext from the value of the hash alone. Thus, one can use a good message digest to authenticate a message-- appending an encrypted version of the hash to an otherwise clear text message can act as a seal, showing that the message was not otherwise tampered with, since it would be infeasably hard to construct a message with the same hash.

Some commonly used Message digests are MD5 (developed by RSA Data Security), and SHA or SHS (the Secure Hash Algorithm/Standard, developed by the US government).

   
Public Key cryptography

All of the ciphers so far discussed are symmetric encryption routines (also called ``secret-key'' or ``traditional'' ciphers): if one knows the key used to encode the message, one also can decrypt the message without too much work. For example, in an affine cipher (§7) x $\mapsto$ ax + b mod p, if we know the values of a and b used to encode the message, we can quickly compute the deciphering key 1/a mod p, - b/a mod p. Also, decrypting the message usually also yields the key.^3.20

This was true of all cryptosystems up until the mid 1970s: knowledge of how to encode a message allowed one also to decipher it. However, in 1976 W. Diffie and M. Hellman invented ``public key cryptography''. In a public key system, someone who knows how to encipher a message cannot determine how to decipher the message without a prohibitively large computation. That is, given the enciphering transformation f_key : $\cal{P}$ $\mapsto$ $\cal{C}$, discovering f_key^-1 is not computationally realistic. It is important to realize that there may be a procedure for doing so, but to carry out this process would take a prohibitively long time (say, hundreds of years on the fastest known computers).

What good is a public key cryptosystem? Since knowledge of the encoding key K_E does not give information about the decoding key K_D, the encoding key K_E can be made public (hence the name ``public key''). This allows anyone to encode messages that only the recipient can decode. For example, suppose you want to make a credit card purchase over the Internet. Data sent across the Internet unencrypted is not secure: someone with access to the transmission lines can listen in and capture sensitive data.^3.21 However, if the merchant provides a public key, you can encrypt your credit card number and transmit it without worry. Only the merchant can decrypt the message, even though anyone may send one.^3.22

Another feature of public key cryptography is ``authentication''. In many public key systems, either the enciphering key K<sub>E</sub> or the deciphering key K<sub>D</sub> may be made public without revealing the other one. In order to ``digitally sign'' a message, I could append my name encrypted with my enciphering key, which I keep secret. I could also make public the deciphering key K_D. Then anyone can check that I was the actual sender, because only I could have encoded my name. Of course, to stop someone from merely appending a valid encrypted signature to a forged message, I should also encrypt something specific to that message, such as a message digest (see §9.2) computed on its contents. This feature is commonly used to ``digitally sign'' email by software such as PGP.

Public-key cryptography is very computationally intensive, so typically its use is limited to allow for the secure transmission of a ``secret key''; this secret key is then used to encrypt the rest of the message using a symmetric encryption method such as triple-DES or IDEA.

A common public key system in current use is RSA (named for its inventors: Rivest, Shamir and Adelman), which we will look at in detail in §11. Others are the Diffie-Hellman key exchange system, El Gamal, Subset-sum (or Knapsack) systems, and systems based on elliptic curves. We will not discuss these here.

Footnotes

... keys.^3.19

that is, 72,057,594,037,927,936 keys.

... key.^3.20

A story related to this appears in Casanova's memoirs (1757). He was given an encrypted manuscript by a Madame d'Urfé, which he deciphered. Later, upon learning this, Madame d'Urfé was incredulous, believing he must know the keyword to do so.

I then told her the key-word, which belonged to no language, and I saw her surprise. She told me that it was impossible, for she believed herself the only possessor of that word which she kept in her memory and which she had never written down.

I could have told her the truth-- that the same calculation which had served me for deciphering the manuscript had enabled me to learn the word-- but on a caprice it struck me to tell her that a genie had revealed it to me. This false disclosure fettered Madame d'Urfé to me. That day, I became the master of her soul, and I abused my power. Every time I think of it, I am distressed and ashamed, and I do penance now in the obligation under which I place myself of telling the truth in writing my memoirs.

... data.^3.21

This is not as hard as you might expect. In many places, such as universities, portions of the network backbone pass through public places like dormitories or classrooms. One merely needs to attach a computer to the network lines to ``sniff'' the network traffic. This will, of course, be limited to users communicating to or from that location, but that can be quite a lot. Also, there are many segments of the Internet which consist of microwave links. To listen in on a huge part of network traffic, all you need is an appropriately placed receiver.

... one.^3.22

Of course, you should still only deal with reputable merchants. You probably wouldn't give your credit card number to a guy selling stuff on the street; neither should you automatically trust anyone with a web site.