Automated Cryptanalysis of Classical Ciphers

Background

Cryptanalysis can be seen as an effort to translate a ciphertext (an encrypted text) to a human language. Cryptanalysis can thus be related to the computational linguistics. This area originated with efforts in the United States in the 1950s to have computers automatically translate texts from foreign languages into English, particularly Russian scientific journals. Nowadays it is a field of study devoted to developing algorithms and software for intelligently processing language data. Systematic (public) efforts to automate cryptanalysis using computers can be traced to first papers written in late ’70s (see e.g. Schatz, 1977). However, the research area has still many open problems, closely connected to an area of Artificial Intelligence. It can be concluded from the current state-of-the-art, that although computers are very useful in many cryptanalytic tasks, a human intelligence is still essential in complete cryptanalysis.

For convenience of a reader we recall some basic notions from cryptography. Very thorough survey of classical ciphers is written by Kahn (1974). A message to be encrypted (plaintext) is written in the lowercase alphabet P = {a, b, c… x, y, z}. The encrypted message (ciphertext) is written in uppercase alphabet C = {A, B, C… X, Y, Z}. Different alphabets are used in order to better distinguish plaintext and ciphertext, respectively. In fact these alphabets are the same.

There is a reversible encryption rule (algorithm) how to transform the plaintext to the ciphertext, and vice-versa. These algorithms depend on a secret parameter K called the key. The set of possible keys K is called the key-space. Input and output of these algorithms is a string of letters from respective alphabets, P* and C*. Both, sender as well as receiver, uses the same secret key, and the same encryption and decryption algorithms.

There are three basic classical systems to encrypt a message, namely a substitution, a transposition, and a running key. In a substitution cipher a string of letters is replaced by another string of letters using prescribed substitution of single letters, e.g. left ‘a’ to ‘A’, replacing letter ‘b’ by letter ‘N’, letter ‘c’ by letter ‘G’, etc. A transposition cipher rearranges order of letters according to a secret key K. Unlike substitution ciphers the frequency of letters in the plaintext and ciphertext remains the same. This characteristic is used in recognizing that the text was encrypted by some transposition cipher. A typical running key cipher is to derive from a main key K the running key K₀ K₁ K₂…K_n. If P = C = K is a group, then simply y_i = e_K(x_i) = x_i + K_i .

Thus it is convenient to define a ciphering algorithm for classical ciphers as follows:

Definition 1: A classical cipher system is a five-tuple (P,C,K,E,D), where the following conditions are satisfied:

• 1.

  P is a finite set of a plaintext alphabet, and P* the set of all finite strings of symbols from P.

• 2.

  C is a finite set of a ciphertext alphabet, and C* the set of all finite strings of symbols from C..

• 3.

  K is a finite set of possible keys.

• 4.

  For each K ∈ K, there is an encryption algorithm e_K ∈ E, and a corresponding decryption algorithm d_K ∈ D such that d_K (e_K(x)) = x for every input x∈ P and K ∈ K..

• 5.

  The ciphering algorithm assigns to any finite string x₀ x₁ x₂…x_n from P* the resulting ciphertext string y₀ y₁ y₂…y_n from C*, where y_i = e_K(x_i) . The actual key may, or need not depend on the index i.