Composition of ciphers
In order to describe product ciphers, the concept of composition of functions is introduced. Compositions are a convenient way of constructing more complicated functions from simpler ones.
Composition of functions
1.33 Definition Let S, T, and U be finite sets and let f: S —» T and g: T —> U be functions. The composition of g with /, denoted g о f (or simply gf), is a function from S to U as illustrated in Figure 1.8 and defined by (g о f)(x) = g(f(x)) for all x e S.
Figure 1.8: The composition g о f of functions g and f.
Composition can be easily extended to more than two functions. For functions Л, /2, ... , ft, one can define ft о ■ ■ ■ о /2 о fx, provided that the domain of ft equals the codomain of /t_j and so on.
Compositions and involutions
Involutions were introduced in §1.3.3 as a simple class of functions with an interesting property: Ek(El,, (x)) = x for all x in the domain of Ek; that is, Ek о Ek is the identity function.
1.34 Remark (composition of involutions) The composition of two involutions is not necessarily an involution, as illustrated in Figure 1.9. However, involutions may be composed to get somewhat more complicated functions whose inverses are easy to find. This is an important feature for decryption. For example if Ek,, Ek2,... , Ek, are involutions then the inverse of Ek = Ek, Ek2 • • • Ek, is Efl = Ek, Ek,_, ■ ■ ■ Ek,, the composition of the involutions in the reverse order.
Figure 1.9: The composition g о f of involutions g and f is not an involution.
Simple substitution and transposition ciphers individually do not provide a very high level of security. However, by combining these transformations it is possible to obtain strong ciphers. As will be seen in Chapter 7 some of the most practical and effective symmetric-key systems are product ciphers. One example of a product cipher is a composition of t > 2 transformations £*, Ek2 ■ • • Ekt where each Ek,, 1 < i < t, is either a substitution or a transposition cipher. For the purpose of this introduction, let the composition of a substitution and a transposition be called a round.
1.35 Example (product cipher) Let M = С = K, be the set of all binary strings of length six. The number of elements hi M is 2G = 64. Let m = (m 11112 ■ • • m0) and define
Here, ф is the exclusive-OR (XOR) operation defined as follows: 000 = 0, 001 = 1, 100=1, 101 = 0. E];1* is a polyalphabetic substitution cipher and E(2) is a transposition cipher (not involving the key). The product E[1) E[2^ is a round. While here the transposition cipher is very simple and is not determined by the key, this need not be the case. □
1.36 Remark (confusion and diffusion) A substitution in a round is said to add confijsion to the encryption process whereas a transposition is said to add diffusion. Confusion is intended to make the relationship between the key and ciphertext as complex as possible. Diffusion refers to rearranging or spreading out the bits in the message so that any redundancy in the plaintext is spread out over the ciphertext. A round then can be said to add both confusion and diffusion to the encryption. Most modern block cipher systems apply a number of rounds in succession to encrypt plaintext.