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. This idea (that the potential cryptanalyst knows everything but the key) is called Kerckhoff's Law or sometimes Shannon's Maxim.

Kerckhoff's Law at first seems unreasonably strong rule; you may be
thinking that, given a mass of encrypted data, how is
the cryptanalyst to know *by what means* it was encrypted?
If you are encrypting your own files for personal use and writing your own
software which you keep under lock and key, this assumption is not
unreasonable. 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 alone as a good measure of security. For example, when you make a
purchase over the internet, the encryption method that is used between your
browser and the seller's web server is public knowledge. Indeed, it must be
public: if not, only those privy to the secret could create web browsers or
web servers. The security of the transaction depends on the security of the
keys.

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^{64}-- 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^{56} keys.^{4.27} 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.

DES was originally expected to be used for ``only a few years'' when it was first designed. However, due to its surprising resistance to attack it was generally unassailable for nearly 25 years. The powerful methods of linear and differential cryptanalysis were developed to attack block ciphers like DES.

In the January of 1997, the National Institute for Standards and Technology
(NIST) issued a call for a new encryption standard to be developed, called
AES (the Advanced Encryption Standard). The requirements were that they
operate on 128-bit blocks and support key sizes of 128, 192, and 256 bits.
There were five ciphers which advanced to the second round: MARS, RC6,
Rijndael, Serpent, and Twofish. All five were stated to have ``adequate
security''- Rijndael was adopted as the standard in October of 2000.
Rijndael was created by the Belgian cryptographers Joan Daemen and Vincent
Rijmen; the underlying mathematics is the algebra of polynomials in the finite
field *GF*(2).

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 in early 1995 in about 8
days using 112 networked computers (see
Damien Doligez's web page about cracking
SSL
for more details); later in
the same year a second session was broken in under 32 hours. Given the speed
increases in computing since then, it is reasonable to believe that a 40-bit
key can be cracked in a few hours. Notice, however, that both of these
attacks were essentially brute-force, trying a large fraction of the 2^{40}
possible keys. Increasing the key size resolves that problem. Nearly all
browsers these days use at least 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 different 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).

It is worth remarking here that computer systems can use a cryptographic
hash function as a way to store a password (for example, Linux allows the
use of MD5 for passwords). A computer password never need be decrypted; it
only needs to be verified. Instead of storing the password itself, or an
encrypted version of it, the computer stores the corresponding hash. Then,
when a user signs in, the password is hashed and compared to the stored
value. If they match, the user typed the right password (or managed to find
another password with the same hash, which is computationally impossible).

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
*x* *ax* + *b* mod *p*
(see §7), 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*. By the same token, the ability to decrypt the message
usually also yields the key used for encryption.^{4.28}

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 Whitfield
Diffie and Martin Hellman invented public key cryptography
[DH76]. 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} : ,
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). Such a function is sometimes called a
one-way function. However, to be usable for public key
cryptography, it must be possible to find the inverse of the function provided
you have some extra information. This extra information is referred
to as a trapdoor (like a trapdoor that a magician would use to
escape from a ``sealed'' box), resulting in a
trapdoor one-way function.

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.^{4.29}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.^{4.30}

Another feature of public key cryptography is authentication. In many
public key systems, either the enciphering key *K*_{E} or the deciphering key
*K*_{D} 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 AES, triple-DES or IDEA.

A common public key system in current use is RSA (named for its inventors: Ronald Rivest, Adi Shamir and Leonard 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.

- ... keys.
^{4.27} - that is, 72,057,594,037,927,936 keys.
- ... encryption.
^{4.28} - A story related to this appears in Casanova's memoirs (1757)
(quoted in [Kahn]).
He was given an encrypted manuscript by a Madame d'Urfé, which he
deciphered. From deciphering, he determined the key used to
encipher the manuscript. Later, upon learning this, Madame d'Urfé
was incredulous, believing he must have learned the keyword in order
to decode the message.
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.
^{4.29} - 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. This same problem occurs with some cable-modem providers: appropriate software can detect the network traffic of one's neighbors. 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.
^{4.30} - 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.

2002-08-29