Issuu

CHAPTER 3: STUDY OF SOME CLASSICAL AND MODERN CRYPTOSYSTEMS

Introduction Most encryption algorithms apply a technique to perform. Traditional (classical) symmetric ciphers use substitution and/or transposition techniques while modern ones use exponentiation and discrete logarithm. Substitution techniques map plaintext elements (characters, bits) into ciphertext elements. Transposition techniques systematically transpose the positions of plaintext elements. Therefore a cipher is composed of its encryption and decryption algorithms applying a specific technique and its key(s).

1. Classical encryption techniques 1.1.

Substitution techniques

A substitution technique is one in which the letters of plaintext are replaced by other letters or by numbers or symbols. If the plaintext is viewed as a sequence of bits, then substitution involves replacing plaintext bit patterns with ciphertext bit patterns. There are four types of substitution ciphers: -

Simple

substitution ciphers: they replace

each

character

plaintext

with

corresponding character of ciphertext; a single one-to-one mapping from plaintext to ciphertext characters is used to encipher an entire message. E.g Caesar and Substitution Ciphers -

Homophonic substitution ciphers: they are similar, except that the mapping is one-tomany, and each plaintext character is enciphered with a variety of ciphertext characters. E.g Beale Cipher

Polyalphabetic substitution ciphers: they use multiple mappings from plaintext to ciphertext characters; the mappings are usually one-to-one as in simple substitution. E.g VigenĂ¨re and Beaufort Ciphers

Polygram

substitution ciphers: they are

the most

general,

substitutions for groups of characters. E.g Playfair and Hill Ciphers

1.2.

Transposition techniques

permitting

arbitrary

Transposition ciphers rearrange characters according to some scheme. This rearrangement was classically done with the aid of some type of geometric figure. Encipherment proceeded in two steps as shown below: plaintext

figure

ciphertext

write - in

take - off

First, the plaintext was written into the figure according to some "write-in" path. Second, the ciphertext was taken off the figure according to some "take-off'' path. The key consisted of the figure together with the write-in and take-off paths. The geometrical figure was often a 2-dimensional array (matrix). In columnar transposition the plaintext was written into a matrix by rows. The ciphertext was obtained by taking off the columns in some order. Example: Suppose that the plaintext FUNDAMENTAL is written into a 3 × 4 matrix by rows as follows: 1

N D

A M E T

If the columns are taken off in the order 2-4-1-3, the resulting ciphertext is UMADNFATNEL. Many transposition ciphers permute the characters of the plaintext with a fixed period d. Let Zd be the integers 1 through d, and let f:Zd  Zd be a permutation over Zd. The key for the cipher is given by the pair K = (d, f). Successive blocks of d characters are enciphered by permuting the characters according to f. Thus, a plaintext message M = ml...rnd md+1...m2d … is enciphered as: EK(M) = mf(1)… mf(d) md+f(1 ) ... md+f(d) .... Decipherment uses the inverse permutation. Example: Suppose that d = 4 and f gives the permutation:

i: f(i):

1234 2413

thus, the first plaintext character is moved to the third position in the ciphertext, the second plaintext character to the first position, and so forth. The plaintext FUNDAMENTAL is enciphered as: M = FUND AMEN TAL EK(M) = UDFN MNAE ATL. The preceding ciphertext is broken into groups of four letters only for clarity; the actual ciphertext would be transmitted as a continuous stream of characters to hide the period. The short block at the end is enciphered by moving the characters to their relative positions in the permutation. Like columnar transposition, periodic permutation ciphers can be viewed as transpositions of the columns of a matrix in which the plaintext is written in by rows. With periodic permutations, however, the ciphertext is also taken off by rows. This is more efficient for computer

applications,

independently.

With

because columnar

each

row

(block) can

transposition, the

entire

enciphered

matrix

must

and

deciphered

generated

for

encipherment and decipherment.

Block ciphers and Stream ciphers

A block cipher is an encryption/decryption scheme in which a block of plaintext is treated as a whole and used to produce a ciphertext block of equal length. Let M be a plaintext message. A block cipher breaks M into successive blocks M1, M2 ..... and enciphers each Mi with the same key K; that is, EK(M ) = EK(M1)EK(M2)....

Many block ciphers have a Feistel structure. Such a structure consists of a number of identical rounds of processing. In each round, a substitution is performed on one half of the data being processed, followed by a permutation that interchanges the two halves. The original key is expanded so that a different key is used for each round. Examples: The Data Encryption Standard (DES) and the Advanced Encryption Standard (AES).

Two important methods of cryptanalysis are differential cryptanalysis and linear cryptanalysis. DES has been shown to be highly resistant to these two types of attack.

A stream cipher is one that encrypts a digital data stream one bit or one byte at a time. Examples of classical stream ciphers are the autokeyed VigenĂ¨re cipher and the Vernam cipher.

Block cipher modes of operation A mode of operation is a technique for enhancing the effect of a cryptographic algorithm or adapting the algorithm for an application, such as applying a block cipher to a sequence of data blocks or a data stream. Five modes of operation have been standardized by NIST for use with symmetric block ciphers such as DES and AES: electronic codebook mode, cipher block chaining mode, cipher feedback mode, output feedback mode, and counter mode. Table 1 presents each mode.

3. Multiple encryption technique Multiple encryption is a technique in which an encryption algorithm is used multiple times. In the first instance, plaintext is converted to ciphertext using the encryption algorithm. This ciphertext is then used as input and the algorithm is applied again. This process may be repeated through any number of stages. Example: Triple DES makes use of three stages of the DES algorithm, using a total of two or three distinct keys.

Product ciphers

A product cipher E is the composition of t functions (ciphers) F1, F2, â€Ś, Ft, where each Fi may be a substitution or transposition. Examples of product ciphers include Substitution-Permutation Ciphers (such as the LUCIFER cipher) and the DES. Note: The LUCIFER cipher was designed at IBM by Fiestel. It uses a transformation that alternatively applies substitutions and transpositions. Figure 4 below illustrates how the basic principle is applied to 12-bits blocks (in practice, longer blocks should be used). The cipher alternatively applies substitutions Si and transpositions Pi, giving

Where each Si is a function of the key K (of size 128 bits). The substitutions Si are broken into 4 smaller substitutions Si1, â€Ś, Si4, each operating on a 3-bits subblock to reduce the complexity of the microelectronic circuits.

Table 1 : Block cipher modes of operation

Figure 1 : Substitution-Permutation cipher

The Data Encryption Standard (DES) The DES encryption algorithm was developed by IBM and was the outgrowth of the LUCIFER cipher. DES enciphers 64-bit blocks of data with 56-bit key. The algorithm which is used both to encipher and decipher is summarized in figure 5 below.

Figure 2 : DES encryption algorithm

An input block T is first transposed under an initial permutation IP, giving T0 = IP(T). After it has passed through 16 iterations of a function f, it is transposed under the inverse permutation IP-1 to give the final result. The permutations IP and IP-1 are given in the tables below. Note that these tables should be read left-to-right, top-to-bottom. For example, IP transposes T = t1t2â€Śt64 into To = t58t50â€Śt7.

Between the initial and final transpositions, the algorithm performs 16 iterations of a function f that combines substitution and transposition. Let Ti denote the result of the ith iteration, and let Li and Ri denote the left and right halves of Ti respectively, that is Ti = LiRi, where Li = t1…t32 and Ri = t33…t64 Then Li = Ri-1 and Ri = Li-1 Where

f(Ri-1, Ki)

is the exclusive-or operation and Ki is 48-bit key. Note after the last iteration, the left and

right halves are are not exchanged.

5. Exponential ciphers An exponential cipher is one that has an encryption scheme based on the computing of exponentials over a finite field. In 1978 Pohlig-Hellman published such a scheme. At about the same time Rivest, Shamir and Adleman published a similar scheme, but with a slight twist. The Pohlig-Hellman and RSA schemes both encipher a message M є [0, n-1] by computing the exponential C = Me mod n where e and n are the key to the enciphering transformation. M is restored by the same operation, but using a different exponent d for the key: M = Cd mod n Example of exponential ciphers: Pohlig-Hellman Scheme, RSA scheme, ElGamal scheme