Читать книгу Cryptography, Information Theory, and Error-Correction - Aiden A. Bruen - Страница 43

While Julius Caesar was building his empire, he needed a method to transmit vital messages without risk of the enemy obtaining any crucial information. To achieve this goal, he employed one of the first known ciphering methods. The idea was to substitute each letter of the plain text with the letter appearing three spaces to the right in the alphabet, i.e. a is enciphered to D, b is enciphered to E, and z is enciphered to C (the alphabet wraps around). Thus, “six” is enciphered to “VLA.”

In practice, this can be easily achieved using a simple device consisting of two disks, such as the one shown in Figure 2.1. Both disks have the alphabet engraved on their perimeter, and they can rotate with respect to each other. If we assign the inner disk to represent the plain text alphabet and the outer disk to represent the cipher text alphabet, enciphering is accomplished simply by rotating the outer disk by three letters counter clockwise and reading off the cipher text corresponding to the plain text. To decipher the message, one must only reverse the procedure. The “key” of the cipher is just the number of letters that the outer disk is shifted by, and is denoted by k. Both sender and recipient are in possession of this common secret key.

For a numerical explanation, suppose we label by the numbers . Using Caesar's key of three, the plain text message “six” is enciphered as follows:

Figure 2.1 Caesar cipher wheel.

Note that in the above example, . We replace 26 by which is the remainder when we divide by 26 (see Chapter 19 for details). In this case, the remainder is 0, corresponding to the letter A. Similarly, becomes . The number 9 corresponds to the letter J.

To decipher the message, reverse the operation (shift left by spaces):

In this case, we have . If is a negative number, then it is replaced by . So, for example gets replaced by . The reasoning is that since . Alternatively, (see Chapter 19) we have .

The Caesar cipher is a simple example of a type of cipher known as a monoalphabetic cipher. Monoalphabetic ciphers belong to a class of ciphers known as substitution ciphers, in which all of the plain text characters in the message are substituted for another letter. Mathematically speaking, the enciphering process of a monoalphabetic cipher can be represented by the mapping of a plain text character to a cipher text character:

Similarly, deciphering is represented by the mapping

where is the cipher key, with . In the case of the Caesar cipher, . If is negative, then, as explained above, .

To break such a cipher, one can decrypt the message by trying all 26 keys (this is referred to as an exhaustive search). For long messages, the likelihood of a cipher text decrypting to two intelligible messages is small.

We mention here briefly affine ciphers. They are similar to Caesar ciphers in that they are simple substitution ciphers, but they differ in that enciphering involves not only addition, but also multiplication as well.