Cryptography, Information Theory, and Error-Correction. Aiden A. Bruen

Чтение книги онлайн.

СКАЧАТЬ taking the first, fifth, ninth, characters, one can reconstruct the columns. Upon completion, the message can be read off, column by column.

      The Scytale concept can be modified to create very complex ciphers. By arranging the plain text in varying matrix patterns and “unwrapping” in different ways, messages can be scrambled very effectively. The Scytale cipher, along with its variants, belongs to a class of ciphers called transposition ciphers, in which all plain text characters are present in the cipher text, but they appear in a substantially different order.

2.4 The Vigenère Cipher

      The next classical cipher of great interest is known as the Vigenère cipher. Although it is a relatively simple concept, it has influenced many ciphers used throughout history, including some that are still in use today. The idea is to modify the notion of Caesar ciphers, which were covered in Section 2.2. Instead of a single cipher key, we make use of an entire keyword, which is a key in the form of a string of letters chosen by the user. For example, suppose we decide to use the word “encode” as our keyword. The enciphering process is carried out as follows. The keyword is repeated as many times as necessary to span the length of the message. Each letter corresponds to a number between 0 and 25 (so , , , ). Then, to encipher, we add the corresponding numbers of the keyword and the message, subtracting 26 if the sum is bigger than 25. Then we switch back to letters to get the cipher text. For example, if the message letter is (), and the keyword letter is (), then the cipher text letter corresponds to . However, 28 is larger than 26, so we subtract 26 to get 2, which is . Thus, enciphers to .

Keyword:

E

N

C

O

D

E

E

N

C

O

D

E

E

N

C

Message:

t

h

e

s

k

y

i

s

f

a

l

l

i

n

g

Cipher text:

X

U

G

G

N

C

M

F

H

O

O

P

M

A

I

Notice that each letter of the cipher text is shifted by varying amounts, unlike the Caesar cipher. Interpreting this as many monoalphabetic ciphers acting on individual characters, it is easy to see why the Vigenère cipher is referred to as a polyalphabetic cipher.

      To decipher, simply subtract the value of the respective key letters from each cipher text letter. For example, to decrypt the cipher text “XUGGNCMFHOOPMAI” from above, we use the keyword “ENCODE” as follows:

      Repeat the process until all plain text characters have been determined. This enciphering process is easy if one has knowledge of the key. However, it can be difficult to break the cipher without such information. This will be investigated in Section 2.6.

      The Vigenère cipher is known as a type of block cipher, where the block length is equivalent to the key length. In a block cipher procedure, the plain text or message is encrypted block by block, rather than character by character.

      There are a few important remarks to be made regarding the use of the Vigenère cipher. First, because the same plain text character enciphers to different characters depending on the position, the cryptanalysis of such a cipher is much more complex than for a simple monoalphabetic substitution cipher. We also point out that the Vigenère cipher was invented to hide the frequencies of letters in the English language. The Caesar cipher, for example, does not do this. Also, if the key phrase “VIGENERECIPHERX” had been used instead of “ENCODE,” in our previous example, the encrypted message would have had perfect secrecy. Perfect secrecy is achieved if the cipher text yields no information about the plain text, and this occurs, roughly speaking, when the keyword is as long as the message itself. Such a secure system can be obtained using one‐time pads, which we investigate later in the book.

2.5 Frequency Analysis

The idea behind the use of frequency analysis in cryptanalysis is that all human languages have underlying statistical patterns and redundancies that can be exploited to help break a variety of ciphers. For the English language, it is well documented that the distribution of the most frequent characters is remarkably similar throughout texts of diverse style and length, as indicated in Table 2.1.

Table 2.1 Approximate frequencies of letters in the English language.

Letter

Frequency СКАЧАТЬ В начало < 19 20 21 22 23 24 25 26 27 28 > В конец