Otokar Grošek (Slovak University of Technology, Slovakia) and Pavol Zajac (Slovak University of Technology, Slovakia)

DOI: 10.4018/978-1-59904-849-9.ch029

Chapter Preview

TopCryptanalysis 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

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 _{0} K_{1} K_{2}…K_{n}.* If P = C = K is a group, then simply

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*∈ E, and a corresponding decryption algorithm_{K}*d*∈ D such that_{K}*d*for every input_{K}(e_{K}(x)) = x*x*∈ P and*K*∈ K..*5.*The ciphering algorithm assigns to any finite string

*x*from P_{0}x_{1}x_{2}…x_{n}***the resulting ciphertext string*y*from C_{0}y_{1}y_{2}…y_{n}**,*where*y*The actual key may, or need not depend on the index_{i}= e_{K}(x_{i}) .*i*.

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..

Search this Book:

Reset