A Modern Advanced Hill Cipher Involving XOR Operation and a Permuted Key

Abstract

In this paper, we have developed a block cipher by extending the analysis of the advanced Hill cipher. In this, besides the u sual involutory matrix, which contains the key, we have included another matrix, which is obtained by permuting the original involutory matrix. This analysis is strengthened by using the xor operation, modular arithmetic and a function called mix(), which mixes the binary bits of the plaintext and the involutory matrix, which includes the key. The avalanche effect and the cryptanalysis carried out in this investigation clearly indicate that the strength of the cipher is quite significant.

Keywords

symmetric block cipher, cryptanalysis, avalanche effect, ciphertext, key, permuted key, xor operation.

INTRODUCTION

In a recent investigation [1], we have developed a block cipher, called modern advanced Hill cipher, by modifying the advanced Hill cipher [2]. In this we have included a matrix A0, which is obtained by permuting an involutory matrix A, which contains the key K. In this process, the basic relations governing the cipher are

where P is a plaintext matrix, N a positive integer, chosen appropriately, and C is the corresponding ciphertext matrix. In this analysis, we have shown that the addition of A0 plays a vital role in strengthening the cipher. In the present paper our objective is to modify the modern advanced Hill cipher by replacing the addition operation with XOR operation. Our interest here is to show that the xor operation is quite comparable to the addition operation in strengthening the cipher. The relations governing the block cipher under consideration are

In this analysis also we have introduced the iteration process, and the mix() function in each round of the iteration. The departure between the previous paper and the present one is the addition (+) in the previous paper is replaced by the xor in the present one. These two operations are expected to be of equal importance.

Let us now mention the plan of the paper. In section 2, we have introduced the development of the cipher and presented the algorithms for encryption and decryption. In section 3, we have illustrated the cipher and mentioned the avalanche effect. Section 4 is devoted to cryptanalysis. Finally in section 5, we have discussed the computations and drawn conclusions.

DEVELOPMENT OF THE CIPHER

In the development of the cipher, the plaintext P, the key K (basing upon which the involutory matrix A is found) and the ciphertext C are of the form

Here n is an even positive integer and each element of P, K and C are decimal numbers, lying between 0 and 255, as we have made use of EBCDIC code. On using the key K, the involutory matrix A can readily be obtained by applying the following relations:

where N=256.

In order to have a detailed discussion for obtaining A, we refer to [3].

The A0, which is obtained by permuting the terms in A can be written in the form

The algorithms for encryption and decryption are given below.

Algorithm for Encryption

1. Read n,P,K,r,d

2. A11=K

3. A= involute(A11,d)

4. A0= permute(A)

5. for i = 1 to r

{

P = (A P)mod 256 A0

P= mix(P)

}

C = P

6. Write( C )

Algorithm for Decryption

1. Read n,C,K,r,d

2. A11=K

3. A= involute(A11,d)

4. A0= permute(A)

5. for i= 1 to r

{

C = Imix(C)

C= ( A (C A0 )) mod 256

}

P = C

4. Write (P)

Algorithm for inverse(K)

1. Read A, n, N

// A is an n x n matrix. N is a positive integer with which modular arithmetic is carried out. Here N= 256.

2. Find the determinant of A. Let it be denoted by Δ, where Δ ≠ 0.

3. Find the inverse of A. The inverse is given by [Aji]/ Δ, i= 1 to n , j = 1 to n

// [Aij] are the cofactors of aij, where aij are the elements of A

for i = 1 to N

{

// Δ is relatively prime to N

if((iΔ) mod N == 1) break;

}

d= i;

B = [dAji] mod N. // B is the modular arithmetic inverse of A.

In this analysis, we have taken r=16. The function mix() can be written in the form P= mix(P). For a detailed discussion of the functions mix() (that is how the binary bits are mixed) and involute() (used for obtaining the involutory matrix, A), we refer to [2]. The function Imix(), used in decryption, denotes the reverse process of mix().

`ILLUSTRATION OF THE CIPHER

Consider the plaintext given below: “As we came across, unfortunately, all selfish and greedy people, we are residing in wilderness in the forests. But we are having several scientists and engineers among us. We must be able to light our own lamp so that we drive away the gloom in our life, and fight a battle with the society.” (3.1) Let us focus our attention on the first sixty four characters of the plaintext given by (3.1). Thus we have “As we came across, unfortunately, all selfish and greedy people,”

On adopting the EBCDIC code, (3.2) can be written in the form

Let us now construct the involutory matrix A by using the relations (2.4) to (2.9). Here we take d= 99. Thus we have

On adopting the decryption algorithm, with the required inputs, we get back the original plaintext given by (3.3). Let us now study the avalanche effect, which tells us about the strength of the cipher. To achieve this one, we replace the thirteenth character „c‟ by „b‟ in the plaintext (3.2). The EBCDIC codes of „b‟ and „c‟ are 130 and 131, which differ by one bit in their binary form. Now, on using the modified plaintext along with (3.5) and (3.6) and applying the encryption algorithm, we have the ciphertext C in the form

On comparing (3.7) and (3.8), in their binary form, we notice that the two ciphertexts differ by 260 bits (out of 512 bits). This indicates that the strength of the cipher is very good. Let us now change the first row first column element of the key K, given by (3.3), from 215 to 214. This will lead to a change of one bit in their binary form. After obtaining the modified A and the A0, corresponding to the modified key, we apply the encryption algorithm (by taking the original plaintext), and obtain the corresponding ciphertext C. Thus we get

Now on comparing (3.7) and (3.9) in their binary form, we find that they differ by 269 bits (out of 512 bits). This also exhibits the strength of the cipher. Though the avalanche effect is indicating the strength of the cipher, let us now consider the cryptanalysis which establishes very firmly the strength of the cipher.

CRYPTANALYSIS

The cryptanalytic attacks which are generally considered in the literature of Cryptography are

1) Ciphertext only attack (Brute force attack), 2) Known plaintext attack,

3) Chosen plaintext attack, and

4) Chosen ciphertext attack.

The key matrix K, given by (3.3), contains 16 decimal numbers. In this analysis, we have taken an integer d in the construction of the involutory matrix, A. As this also is to be treated as an additional key, the total length of the key can be considered as 17 decimal numbers, which is equal to 136 binary bits. Thus the size of the key space is

If we assume that the time required for computation with each one of the keys is 10-7 seconds, then the time required for carrying out the computation with all keys in the key space is

As this is very large, we conclude that this cipher cannot be broken by the brute force attack.

Let us now examine the known plaintext attack. In this we know pairs of the plaintext and the ciphertext as many as we require. In the development of this cipher we have an iterative process and mix function. Denoting the mix function as M, for clarity and convenience, the relation between the ciphertext and the original plaintext, obtained at the end of the iteration process (for r=16), can be written in the form

On focusing our attention on the equation (4.1), we notice several interesting factors. After multiplying A and P we have carried out mod 256. Then the elements of A0 are xored with the result of (AP) mod 256. After this, the resulting value is converted into binary bits and then the mix process is carried out. In the light of all these operations, the binary bits of the key (included in A) and the plaintext P are totally mixed and they have undergone diffusion. As this process continues in each round, we do not have any scope for the determination of the key or a function of the key so that we can break the cipher. Thus the cipher cannot be broken by the known plaintext attack.

Generally every encryption algorithm is designed to withstand against the first two attacks. The latter two cryptanalytic attacks depend totally on intuition and imagination. Here we do not find any such scope for breaking the cipher.

COMPUTATIONS AND CONCLUSIONS

In this paper, we have developed a block cipher, called modern advanced Hill cipher, in which we have included a matrix A0 (obtained by permuting the involuntary matrix A, which includes the key K) and the xor operation. In this cipher the computations are carried out by writing programs for encryption and decryption in Java. The plaintext (3.1) is divided into five blocks by taking 64 characters at a time. Each block is written in the form of a square matrix of size 8. The last block is supplemented with twenty nine characters, so that it becomes a complete one. The ciphertext corresponding to the complete plaintext (3.1) is obtained in the form

The avalanche effect and the cryptanalysis, considered in sections 3 and 4, clearly indicate that the cipher is a strong one and it cannot be broken by any cryptanalytic attack. This generalization of the advanced Hill cipher is markedly an interesting one.

References

V.U.K.Sastry, Aruna Varanasi, and S.Udaya Kumar, “ A modern Advanced Hill cipher Involving a Permuted Key and Modular Arithmetic Addition Operation”, sent for publication in Journal of Global Research in Computer science. Bibhudendra Acharya. Saroj Kumar Panigrahy, Sarat Kumar Patra, and Ganapathi Panda, “ Image Encryption Using Advanced Hill Cipher Algorithm”, International Journal of Recent Trends in Engineering, Vol.1, No.1, May2009. V.U.K.Sastry, Aruna Varanasi, S.Udaya Kumar, “Advanced Hill Cipher Involving Permutation and Iteration”, International Journal of Advanced Research in