The fundamentals ofcodes,ciphers, andauthentication

The most frequently confused, and misused, terms in the lexicon of cryptology arecode andcipher. Even experts occasionally employ these terms as though they were synonymous.

A code is simply an unvarying rule for replacing a piece of information (e.g., letter, word, or phrase) with another object, but not necessarily of the same sort;Morse code, which replacesalphanumeric characters with patterns of dots and dashes, is a familiar example. Probably the most widely known code in use today is the American Standard Code for Information Interchange (ASCII). Employed in allpersonal computers and terminals, it represents 128 characters (and operations such as backspace and carriage return) in the form of seven-bit binary numbers—i.e., as a string of seven 1s and 0s. In ASCII a lowercasea is always 1100001, an uppercaseA always 1000001, and so on.Acronyms are also widely known and used codes, as, for example, Y2K (for “Year 2000”) and COD (meaning “cash on delivery”). Occasionally such a code word achieves an independent existence (and meaning) while the original equivalent phrase is forgotten or at least no longer has the precise meaning attributed to the code word—e.g.,modem (originally standing for “modulator-demodulator”).

Ciphers, as in the case of codes, also replace a piece of information (an element of the plaintext that may consist of a letter, word, or string of symbols) with another object. The difference is that the replacement is made according to a rule defined by a secret key known only to the transmitter and legitimate receiver in the expectation that an outsider, ignorant of the key, will not be able to invert the replacement to decrypt the cipher. In the past, the blurring of the distinction between codes and ciphers was relatively unimportant. In contemporary communications, however, information is frequently bothencoded and encrypted so that it is important to understand the difference. A satellite communications link, for example, may encode information in ASCII characters if it is textual, or pulse-code modulate and digitize it in binary-coded decimal (BCD) form if it is ananalog signal such as speech. The resulting coded data is then encrypted into ciphers by using theData Encryption Standard or theAdvanced Encryption Standard (DES or AES; described in the sectionHistory of cryptology). Finally, the resulting cipher stream itself is encoded again, using error-correcting codes for transmission from the ground station to the orbiting satellite and thence back to another ground station. These operations are then undone, in reverse order, by the intended receiver to recover the original information.

In the simplest possible example of a true cipher,A wishes to send one of two equally likely messages toB, say, to buy or sell a particular stock. The communication must take place over a wireless telephone on which eavesdroppers may listen in. It isvital toA’s andB’s interests that others not be privy to the content of their communication. In order to foil any eavesdroppers,A andB agree in advance as to whetherA will actually say what he wishesB to do, or the opposite. Because this decision on their part must be unpredictable, they decide by flipping a coin. If heads comes up,A will sayBuy when he wantsB to buy andSell when he wantsB to sell. If tails comes up, however, he will sayBuy when he wantsB to sell, and so forth. (The messages communicate only one bit of information and could therefore be 1 and 0, but the example is clearer usingBuy andSell.)

With this encryption/decryptionprotocol being used, an eavesdropper gains no knowledge about the actual (concealed) instructionA has sent toB as a result of listening to their telephone communication. Such a cryptosystem is defined as “perfect.” The key in this simple example is the knowledge (shared byA andB) of whetherA is saying what he wishesB to do or the opposite. Encryption is the act byA of either saying what he wants done or not as determined by the key, while decryption is the interpretation byB of whatA actually meant, not necessarily of what he said.

This example can be extended to illustrate the second basic function of cryptography, providing a means forB toassure himself that an instruction has actually come fromA and that it is unaltered—i.e., a means of authenticating the message. In the example, if the eavesdropper interceptedA’s message toB, he could—even without knowing the prearranged key—causeB to act contrary toA’s intent by passing along toB the opposite of whatA sent. Similarly, he could simply impersonateA and tellB to buy or sell without waiting forA to send a message, although he would not know in advance which actionB would take as a result. In either event, the eavesdropper would be certain of deceivingB into doing something thatA had not requested.

To protect against this sort ofdeception by outsiders,A andB could use the following encryption/decryption protocol.

They secretly flip a coin twice to choose one of four equally likely keys, labeled HH, HT, TH, and TT, with both of them knowing which key has been chosen. The outcome of the first coin flip determines the encryption rule just as in the previous example. The two coin flips together determine an authentication bit, 0 or 1, to be appended to the ciphers to form four possible messages: Buy-1, Buy-0, Sell-1, and Sell-0.B will only accept a message as authentic if it occurs in the row corresponding to the secret key. The pair of messages not in that row will be rejected byB as non-authentic.B can easily interpret thecipher in an authentic message to recoverA’s instructions using the outcome of the first coin flip as the key. If a third partyC impersonatesA and sends a message without waiting forA to do so, he will, with probability1/2, choose a message that does not occur in the row corresponding to the keyA andB are using. Hence, the attempted deception will be detected byB, with probability1/2. IfC waits and intercepts a message fromA, no matter which message it is, he will be faced with a choice between two equally likely keys thatA andB could be using. As in the previous example, the two messages he must choose betweenconvey different instructions toB, but now one of the ciphers has a 1 and the other a 0 appended as the authentication bit, and only one of these will be accepted byB. Consequently,C’s chances of deceivingB into acting contrary toA’s instructions are still1/2; namely, eavesdropping onA andB’s conversation has not improvedC’s chances of deceivingB.

Clearly, in either example, secrecy or secrecy with authentication, the same key cannot be reused. IfC learned the message by eavesdropping and observedB’s response, he could deduce the key and thereafter impersonateA with certainty of success. If, however,A andB chose as many random keys as they had messages to exchange, the security of the information would remain the same for all exchanges. When used in this manner, these examples illustrate the vital concept of a onetime key, which is the basis for the only cryptosystems that can be mathematically proved to be cryptosecure. This may seem like a “toy” example, but it illustrates the essential features of cryptography. It is worth remarking that the first example shows how even a child can create ciphers, at a cost of making as many flips of a fair coin as he has bits of information to conceal, that cannot be “broken” by even national cryptologic services with arbitrary computing power—disabusing the lay notion that the unachieved goal of cryptography is to devise a cipher that cannot be broken.