Information Technology Journal

Year: 2007 | Volume: 6 | Issue: 3 | Page No.: 396-404
DOI: 10.3923/itj.2007.396.404

A Block Cipher Involving Interlacing and Decomposition

S. Udaya Kumar, V.U.K. Sastry and A. Vinaya babu

Abstract: In this study, we have developed a block cipher for a block of size 112 bits by introducing the basic concepts interlacing and decomposition. Here, we have taken the key in terms of a set of matrices and the plaintext also in the form of matrices, wherein all the matrices are containing binary bits. In the process of encryption, we have employed an iterative procedure. In the process of decryption, we have used the modular arithmetic inverses of the key matrices. The cryptanalysis carried out in this paper clearly shows that the cipher cannot be broken by any cryptanalytic attack.

Keywords: ciphertext, plaintext, key matrix, modular arithmetic inverse and Block cipher

INTRODUCTION

In the classical literature of cryptography, Hill cipher (Stalling, 2002) occupies a prominent place. In this, the characters A to Z are represented by the numbers 0 to 25 and the ciphertext is written in terms of the numbers. A secret key is taken in the form of a matrix, which contains numbers, wherein each number is less than 26. Here, we get the ciphertext by operating with the key matrix on the plaintext matrix and performing mod 26.

Following Hill, (Feistel, 1973; Feistel et al., 1975), made an attempt to develop a block cipher, wherein both the plaintext and the key matrix are represented in terms of binary bits and mod 2 operation is carried out on the result obtained by multiplying the plaintext vector with the key matrix. However, he has found that the cipher can be broken by the known plaintext attack.

In the present research, our objective is to develop a block cipher, wherein we employ a process involving iteration, interlacing and decomposition. In this, the plaintext and the key are represented in terms of matrices consisting of binary bits. Here, we take that the number of key matrices is equal to the number of plaintext matrices. In this, our interest is to develop a cipher, which cannot be broken by any cryptanalytic attack.

Interlacing and decomposition: Let us illustrate the process of interlacing by considering a typical example. Let x_i, i = 1 to 4 be four matrices given by

where i is the matrix number, j, the row number and k is the column number.

Now (1) can be written as

The process of interlacing can be described as follows.

The last element of the fourth column of the fourth matrix i.e., x₄₇₄ is placed as the first element of the first row of a new first matrix. The last but one element of the fourth column of the fourth matrix (x₄₆₄) is placed as the first element of the first row of a new second matrix. Then the x₄₅₄ and the x₄₄₄ are placed as the first elements of the first rows of the new third and the new fourth matrices respectively. In a similar manner all the other elements of the four matrices x_i, i = 1 to 4, are placed in the four new matrices <x_i>. Here, the symbol < > denotes interlacing.

Now let us discuss the process of decomposition, which is a reverse process to that of interlacing. Consider the matrices y_i, i = 1 to 4 given by

Here i is the number of the matrix, j, the row number and k is the column number.

Let us consider the matrices y_i, i = 1 to 4, given by

Let y_i = < x_i >, i = 1 to 4. Thus

We know that x_i = [x_ijk]. On using the relations (6), we get

Thus we have x_i = >y_i<, where > < denotes decomposition.

Development of the cipher: Let us consider a block of a plaintext consisting of 16 characters. By using the ASCII code, each character can be represented in terms of seven binary bits. Then the block comprising 112 binary bits is represented as four matrices, wherein each matrix is of size 7x4. In these matrices, the first column of the first matrix contains the seven binary bits corresponding to the first character of the plaintext; the second column of the matrix contains the binary bits corresponding to the second character and so on.

Let us take a key containing twenty-eight numbers, wherein each number lies between 0 and 127. Thus each number can be represented in the form of seven binary bits. Then we can have four matrices each of size 7x7, formed from the given key. Let us denote the key matrices by K_i, I = 1 to 4 and the plaintext matrices by P_i, i = 1 to 4.

Before we proceed to the process of iteration, let P_i⁰ (P_i⁰ = P⁰), i = 1 to 4, be the initial (given) plaintext matrices. In the process of encryption, after the first iteration, on multiplying P_i⁰ by K_i, we get

where each one of the Q¹_i s is a matrix (consisting of binary bits) of size 7x4.

On adopting the process of interlacing, we get

On performing the second iteration and interlacing we have

Thus the process of encryption, which includes iteration and interlacing, can in general be written as follows.

where i = 1 to 4 and j = 1 to m, in which m denotes the number of iterations.

Let us now concatenate the elements of the four matrices of C_i in a column wise manner as follows.

The above string of binary bits is the ciphertext C corresponding to the given plaintext P. Now let us consider the process of decryption. This depends upon iteration and decomposition (a procedure opposite to that of interlacing) is carried out by reversing all the above steps, one after another, starting from the last step. Consider the ciphertext C. Divide this into four matrices, namely, C_i, i = 1 to 4 (each matrix is of size 7x4), by placing the first twenty-eight elements of (15) in the first matrix, the second twenty-eight elements of (15) in the second matrix and so on. The matrices assume the form given by

We may now write

On obtaining the modular arithmetic inverse (Sastry and Janaki, 2005) of each K_i, denoted by K^-1_i, i = 1 to 4 and using the Eq. (12), we get

It may be noted that K_i K_i^-1 mod 2 = K_i K_i^-1 mod 2 = I. Now the process of iteration governing decryption, which involves the decomposition procedure, can be written as follows.

where i = 1 to 4 and j = m to 1.

At the end of the iteration, we get the plaintextP⁰_i.

Let us now design algorithms for the encryption and the decryption and write a procedure for obtaining the modular arithmetic inverse of the key matrix.

Algorithms
Algorithm for encryption:

Algorithm for decryption:

Algorithm for the modular arithmetic inverse:

Here it is to be noted that the modular arithmetic inverse of a matrix A exists only when A is non-singular and Δ is relatively prime to N. In the present analysis, we take N = 2 and obtain the modular arithmetic inverse of A such that AB mod 2 = BA mod 2 = I.

Illustration of the cipher: Let us take a key K₀ in the form

This key consists of 28 numbers, wherein each number lies between 0 and 127. Here, repetition of the numbers is allowed. Let us divide this key into four sub-keys, wherein each sub-key consists of 7 numbers. We form the first sub-key K₁ by taking the first seven numbers of (21) and the second sub-key K₂ by taking the second seven numbers and so on till we exhaust all the 28 numbers.

On writing each number in terms of binary bits, the first sub-key can be written in the form of a matrix of size 7x7. Similarly, we can write the other sub-keys also in terms of matrices of size 7x7. Thus we have four matrices, K_i, i = 1 to 4, given by

Let us now take the first sixteen characters of the plaintext namely, All the enemies into consideration. This includes three blank spaces.

On using the ASCII code, the above sixteen characters can be represented as four matrices each of size 7x4. Here P⁰₁ includes the first four characters of the plaintext, wherein the first column represents the ASCII code of the first character in its binary form, the second column represents the ASCII code of the second character in its binary form and so on. In a similar manner P⁰₂ P⁰₃ and P⁰₄ are formed. The four matrices are given by

On applying the encryption algorithm described earlier, taking m = 16 and carrying out sixteen iterations, we get the ciphertext given by

On adopting the procedure for obtaining the modular arithmetic inverse
we get

We can readily find that K_i K_i ^-1mod 2 = K^-1_i K_i mod 2 = I.

On using the decryption algorithm presented earlier

we get back the plaintext All the enemies .

On applying the encryption algorithm for the entire plaintext given by (23), we get the corresponding ciphertext as

Then by applying the decryption algorithm on (27), we get back the plaintext given by (23).

Cryptanalysis: The various cryptanalytic attacks available in the literature depend upon the facts that the ciphertext is known or pairs of plaintext-ciphetrext are known or they are chosen in a special manner.

When the ciphetext only is known, the breaking of the cipher depends upon the size of the key space and this is carried out by brute force attack. When the pairs of plaintext and ciphertext are known, the cipher can be broken if the key can be determined.

In what follows, we examine the brute force attack and the known plaintext attack, wherein we show that the brute force attack is formidable and the known plaintext attack leads to a system of nonlinear equations from which the key cannot be determined.

Brute force attack: In this cipher, the key K₀ consists of twenty-eight numbers, given by (21), wherein each number lies between 0 and 127. Thus the key is represented in terms of 196 bits (four matrices, each of size 7x7). Thus the search space of the key under consideration is of size

Hence, the cipher cannot be broken by brute force attack.

Known plaintext attack: In the process of encryption, from (12), we have

When i = 1 and j = 1, we have

where r = 1 to 7, s = 1 to 7 and t = 1 to 4.

Here, it is to be noted that the expression K_1rs P⁰_1st represents the summation given by

Similarly, we can write Q¹_i, i = 2 to 4.

Thus on interlacing the four matrices Q¹_i, i = 1 to 4, we get

Fof j = 2, from (28) and (25) we have

On applying the process of interlacing on the matrices D_i, i = 1 to 4, we have

The elements of the above matrices are given by the equations

From the Eq. (33) to (35), we get

If we take m = 2 and carryout only two iterations, we get 112 equations (since we have four matrices, each of size 7x4) connecting the elements of the plaintext (P⁰_i) and the ciphertext (P²_i). All these equations are of second degree in the elements of the key matrices and contain mod 2. On solving the system of equations, it must be possible for us to obtain the solution for the elements of the key matrices purely in terms of 0s and 1s. However, this is not possible by any approach, including the brute force attack, as there are 112 elements of the key in the four key matrices.

If we continue the process of iteration and assign a higher number for m, say m = 16, then we get 112 non-linear equations of degree 16. As it is totally impossible to solve such a system of 112 non-linear equations, breaking the cipher is completely ruled out, in this process, either by the known plaintext attack or by any special choice of ciphertext or plaintext. Thus the cipher cannot be broken by the known plaintext attack.

Avalanche effect: Taking the first sixteen characters of the plaintext namely, All the enemies (23), we have obtained the ciphertext given by (5.5). On changing the first character of the above plaintext from A to C (the ASCII codes of A and C in their binary form differ in one bit), we obtain the corresponding ciphertext as

Comparing (25) and (39), we notice that the two ciphertexts differ in 63 bits out of 112 bits. This shows that the algorithm exhibits a strong avalanche effect.

Now we change the key in one bit. This is achieved by changing the number 91 to 90 in the key K₀ given by (5.1). Then we obtain the corresponding ciphertext for the plaintext -All the enemies . This is given by

On comparing (39) and (25), we readily notice that the ciphertexts differ in 62 bits out of 112 bits. It may be noted here that though the change in the key is only one bit out of 196 bits, the change in the corresponding ciphertext containing 112 bits is 62 bits. This also shows that the algorithm has a pronounced avalanche effect.

Computational experiments and conclusions: In this research, we have developed a block cipher for a block of size 112 bits. The length of the key is 196 bits and it is represented as four matrices, wherein each matrix is of size 7x7. The plaintext is represented by four matrices, wherein each one is of size 7x4. The development of the cipher essentially depends upon an iterative method involving interlacing and decomposition and the modular arithmetic inverse of each of the key matrices.

The algorithms for the encryption and the decryption, are implemented in C language.

From the cryptanalysis presented earlier, we have found that the cipher cannot be broken by any cryptanalytic attack.

Based on the analysis presented in this research, we have seen that the cipher exhibits a strong avalanche effect.

Keeping all the above aspects in view, we conclude that the cipher is a very interesting one and it cannot be broken by any cryptanalytic attack.

REFERENCES