The word cryptography comes from the Greek words κρυπτο (hidden or secret) and γραφη (writing). Oddly enough, cryptography is the art of secret writing. More generally, people think of cryptography as the art of mangling information into apparent unintelligibility in a manner allowing a secret method of unmingling. The basic service provided by cryptography is the ability to send information between participants in a way that prevents others from reading it. In this book we will concentrate on the kind of cryptography that is based on representing information as numbers and mathematically manipulating those numbers. This kind of cryptography can provide other services, such as • integrity checking—reassuring the recipient of a message that the message has not been altered since it was generated by a legitimate source • authentication—verifying someone’s (or something’s) identity But back to the traditional use of cryptography. A message in its original form is known as plaintext or clear text. The mangled information is known as ciphertext. The process for producing ciphertext from plaintext is known as encryption. The reverse of encryption is called decryption. While cryptographers invent clever secret codes, cryptanalysts attempt to break these codes. These two disciplines constantly try to keep ahead of each other.
Cryptographic systems tend to involve both an algorithm and a secret value. The secret value is known as the key. The reason for having a key in addition to an algorithm is that it is difficult to keep devising new algorithms that will allow reversible scrambling of information, and it is difficult to quickly explain a newly devised algorithm to the person with whom you’d like to start communicating securely. With a good cryptographic scheme it is perfectly OK to have everyone, including the bad guys (and the cryptanalysts) know the algorithm because knowledge of the algorithm without the key does not help unmingle the information. The concept of a key is analogous to the combination for a combination lock. Although the concept of a combination lock is well known (you dial in the secret numbers in the correct sequence and the lock opens), you can’t open a combination lock easily without knowing the combination.
2. Computational Difficulty
It is important for cryptographic algorithms to be reasonably efficient for the good guys to compute. The good guys are the ones with knowledge of the keys.1 Cryptographic algorithms are not impossible to break without the key. A bad guy can simply try all possible keys until one works. The security of a cryptographic scheme depends on how much work it is for the bad guy to break it. If the best possible scheme will take 10 million years to break using all of the computers in the world, then it can be considered reasonably secure. Going back to the combination lock example, a typical combination might consist of three numbers, each a number between 1 and 40. Let’s say it takes 10 seconds to dial in a combination. That’s reasonably convenient for the good guy. How much work is it for the bad guy?
There are 403 possible combinations, which is 64000. At 10 seconds per try, it would take a week to try all combinations, though on average it would only take half that long (even though the right number is always the last one you try!). Often a scheme can be made more secure by making the key longer. In the combination lock analogy, making the key longer would consist of requiring four numbers to be dialed in. This would make a little more work for the good guy. It might now take 13 seconds to dial in the combination. But the bad guy has 40 times as many combinations to try, at 13 seconds each, so it would take a year to try all combinations. (And if it took that long, he might want to stop to eat or sleep).
With cryptography, computers can be used to exhaustively try keys. Computers are a lot faster than people, and they don’t get tired, so thousands or millions of keys can be tried per second. Also, lots of keys can be tried in parallel if you have multiple computers, so time can be saved by spending money on more computers. Sometimes a cryptographic algorithm has a variable-length key. It can be made more secure by increasing the length of the key. Increasing the length of the key by one bit makes the good guy’s job just a little bit harder, but makes the bad guy’s job up to twice as hard (because the number of possible keys doubles). Some cryptographic algorithms have a fixed-length key, but a similar algorithm with a longer key can be devised if necessary. If computers get 1000 times faster, so that the bad guy’s job becomes reasonably practical, making the key 10 bits longer will make the bad guy’s job as hard as it was before the advance in computer speed. However, it will be much easier for the good guys (because their computer speed increase far outweighs the increment in key length). So the faster computers get, the better life gets for the good guys. Keep in mind that breaking the cryptographic scheme is often only one way of getting what you want. For instance, a bolt cutter works no matter how many digits are in the combination.
3. Secret Codes
We use the terms secret code and cipher interchangeably to mean any method of encrypting data. Some people draw a subtle distinction between these terms that we don’t find useful. The earliest documented cipher is attributed to Julius Caesar. The way the Caesar cipher would work if the message were in English is as follows. Substitute for each letter of the message, the letter which is 3 letters later in the alphabet (and wrap around to A from Z). Thus an A would become a D, and so forth. For instance, DOZEN would become GRCHQ. Once you figure out what’s going on, it is very easy to read messages encrypted this way (unless, of course, the original message was in Greek). A slight enhancement to the Caesar cipher was distributed as a premium with Oval tine in the 1940s as Captain Midnight Secret Decoder rings. (Where this done today, Oval tine would probably be in violation of export controls for distributing cryptographic hardware!) The variant is to pick a secret number n between 1 and 25, instead of always using 3. Substitute for each letter of the message, the letter which is n higher (and wrap around to A from Z of course). Thus if the secret number was 1, an A would become a B, and so forth. For instance HAL would become IBM. If the secret number was 25, then IBM would become HAL. Regardless of the value of n, since there are only 26 possible ns to try, it is still very easy to break this cipher if you know it’s being used and you can recognize a message once it’s decrypted. The next type of cryptographic system developed is known as a monoalphabetic cipher, which consists of an arbitrary mapping of one letter to another letter. There are 26! possible pairings of letters, which is approximately 4×1026. [Remember, n!, which reads “n factorial”, means n(n−1)(n−2)⋅⋅⋅1.] This might seem secure, because to try all possibilities, if it took 1 microsecond to try each one, would take about 10 trillion years. However, by statistical analysis of language (knowing that certain letters and letter combinations are more common than others), it turns out to be fairly easy to break. For instance, many daily newspapers have a daily cryptogram, which is a monoalphabetic cipher, and can be broken by people who enjoy that sort of thing during their subway ride to work. An example is Cflqr’xsxsnyctm n eqxxqgsyiqulqfwdcpeqqh, erllqrxqgtiqul!