Automated Cryptanalysis of Classical Ciphers

Automated Cryptanalysis of Classical Ciphers

Otokar Grošek (Slovak University of Technology, Slovakia) and Pavol Zajac (Slovak University of Technology, Slovakia)
Copyright: © 2009 |Pages: 6
DOI: 10.4018/978-1-59904-849-9.ch029
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

Classical ciphers are used to encrypt plaintext messages written in a natural language in such a way that they are readable for sender or intended recipient only. Many classical ciphers can be broken by brute-force search through the key-space. Methods of artificial intelligence, such as optimization heuristics, can be used to narrow the search space, to speed-up text processing and text recognition in the cryptanalytic process. Here we present a broad overview of different AI techniques usable in cryptanalysis of classical ciphers. Specific methods to effectively recognize the correctly decrypted text among many possible decrypts are discussed in the next part Automated cryptanalysis – Language processing.
Chapter Preview
Top

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 K0 K1 K2…Kn. If P = C = K is a group, then simply yi = eK(xi) = xi + Ki .

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 eK ∈ E, and a corresponding decryption algorithm dK ∈ D such that dK (eK(x)) = x for every input x∈ P and K ∈ K..

  • 5.

    The ciphering algorithm assigns to any finite string x0 x1 x2…xn from P* the resulting ciphertext string y0 y1 y2…yn from C*, where yi = eK(xi) . The actual key may, or need not depend on the index i.

Key Terms in this Chapter

Key-Space: Set of all possible keys for a given ciphertext. Key-space can be limited to a subspace of the whole K by some prior knowledge.

Brute-Force Attack: Exhaustive cryptanalytic technique that searches the whole key-space to find the correct key.

Plaintext: The unencrypted text, a string of letters from alphabet P of a given cryptosystem.

Classical Cipher: A classical cipher system is a five-tuple (P,C,K,E,D), where P, C, define plaintext and ciphertext alphabet, K is the set of possible keys, and for each K ? K, there exists an encryption algorithm eK ? E, and a corresponding decryption algorithm dK ? D such that dK (eK(x)) = x for every input x? P and K ? K..

Cryptanalysis: Is a process of trying to decrypt given ciphertext and/or find the key without, or with only partial knowledge of the key. It is also a research area studying techniques of cryptanalysis.

Relaxation Attack: Cryptanalytic technique that searches the key-space by incremental updates of the candidate key(s). It usually applies the knowledge of previous trial decryption(s) to change some parts of the key.

Ciphertext: The encrypted text, a string of letters from alphabet C of a given cryptosystem by a given key K ? K..

Complete Chapter List

Search this Book:
Reset