A MODERN ADVANCED HILL CIPHER INVOLVING A PAIR OF KEYS, MODULAR ARITHMETIC ADDITION AND SUBSTITUTION

Abstract

In this investigation, we have developed a symmetric block cipher which includes iteration process, a pair of keys, modular arithmetic addition, mixing and substitution. The mixing and substitution used in each round of the iteration is strengthening the cipher significantly. The avalanche effect and cryptanalysis carried out in this analysis clearly indicate that the strength of the cipher is considerable and it can be fairly used for the security of information

Keywords

symmetric block cipher, cryptanalysis, avalanche effect, ciphertext, pair of keys, involutory matrix, XOR operation., mixing, substitution.

INTRODUCTION

In a recent investigation [1], we have devoted our attention to the study of a modern advanced Hill cipher involving a pair of keys. In this, we have introduced modular arithmetic addition operation, mixing and substitution in each round of the iteration process. The basic equations governing this cipher are

C = (AP +B) mod N, (1.1)

and

P = (A (C- B) ) mod N, (1.2)

where P is a plaintext matrix, A and B are square matrices of size n, N a positive integer, chosen appropriately, and C is the corresponding ciphertext matrix. In this analysis, matrices A and B are involutory matrices, which include the pair of keys K and L respectively. Here it is to be noted that an involutory matrix is a matrix whose arithmetic inverse is the same as the matrix itself. The equations that are required for obtaining A are given by

where A-1 is the arithmetic inverse of A, I the identity matrix, d a chosen positive integer and is determined from (1.11). Similar equations can be obtained for obtaining B (see [1]). In order to have a detailed discussion concerned to the relations for obtaining an involutory matrix, we refer to [2]. In the present paper our objective is to develop a variant of the modern advanced Hill cipher, discussed in [1], by replacing the addition operation with XOR operation. The relations governing the block cipher that we are going to develop in this analysis are

In this analysis also we have included the iteration process, the functions mix() and substitute() in each round of the iteration. All these features together with the XOR operation are expected to strengthen the cipher significantly. Let us now put forth the plan of the paper. In section 2, we have introduced the development of the cipher, and presented the flowcharts and 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 this cipher, the plaintext P, the pair of keys K and L (basing upon which the involutory matrices A and B are found), and the ciphertext C are given by the relations

Here n is an even positive integer and each element of P, K, L and C are decimal numbers, lying in [0, 255], as we have made use of EBCDIC code. On using the keys K and L, and taking N=256, the involutory matrices A and B can readily be found by using the relations, mentioned in section 1 (see (1.3) to (1.11)). As we have already pointed out in section 1, the relations governing the encryption and the decryption are (1.12) and (1.13). In what follows, we present the flowcharts and the algorithms.

In this analysis, we have denoted the number of rounds as r, and it is taken as 16. The d and e are positive integers which are chosen in finding the involutory matrices A and B. The function involute() is used for obtaining the involutory matrix. The functions mix() and substitute() used in the encryption algorithm can be mentioned as follows: At each stage of the iteration process, the matrix P is of size nxn. It can be written in the form of four binary strings, wherein each string has 2n2 binary bits as shown below:

On taking 8 bits at a time, the above string, containing 8n2 binary bits can be written in the form of a square matrix of size n. Let us now develop the process of substitution. We know that the EBCDIC code, requires the numbers 0-255 for the representation of the characters. These numbers can be written in the form of a matrix E given by

E ( i , j) = 16(i-1)+(j-1), i=1 to 16 and j=1 to 16. (2.5)

Let us now see the development of the substitution table consisting of 16 rows and 16 columns. In order to achieve this one, let us firstly fill up the first two columns of the table with the elements of the keys K and L in order. Then rest of the table is filled with the remaining elements of E, in order in a row wise manner, excluding the numbers contained in K and L. This process yields the substitution table. This table can be represented in the form of a substitution matrix denoted by S(i,j).

For a detailed discussion of the process of substitution, we refer to [1].

It may be noted here that the functions Imix() and Isubstitute(), used in the decryption algorithm, are obtained by reversing the processes of mix() and substitute().

ILLUSTRATION OF THE CIPHER

Consider the plaintext given below:

“Hello X! I am waiting for your email. I have already completed my B. Tech. examinations very well. My father is compelling me to do IAS, and to become a collector in this country. It is unfortunate! When are you completing your PhD program? I would like to come to you and finish there my MS. What about our marriage? I am waiting for your reply.”

Let us now consider the first sixty four characters of the plaintext given by (3.1). Thus we have “Hello X! I am waiting for your email. I have already completed m”

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

On adopting the decryption algorithm, with the required inputs, it can be readily verified that we get back the original plaintext given by (3.3).

Let us now examine the avalanche effect, which gives an idea about the quality of the cipher. To this end, in the plaintext (3.2), we replace the 18th character ‘t’ by ’s‘,. As the EBCDIC codes of ‘t ’ and ‘s ’ are 163 and 162, they differ by one bit in their binary form. Now, on using the modified plaintext along with (3.4) and (3.5), and applying the encryption algorithm, we have the ciphertext C in the form

On converting (3.8) and (3.9), in to their binary form, and comparing the corresponding strings, we notice that the two ciphertexts differ by 271 bits (out of 512 bits). This shows that the strength of the cipher is expected to be up to the mark.

Let us now focus our attention on one bit change in one of the keys, say key K. To achieve this one we change the 2nd row 1st column element of the key K, given by (3.4), from 135 to 134. On using the original plaintext (3.3), the modified key K, keeping the other key L intact, and using the encryption algorithm, we get

Now on comparing (3.8) and (3.10) in their binary form, we find that they differ by 278 bits (out of 512 bits). This also shows that the strength of the cipher is considerable. In what follows, let us now consider the cryptanalysis, which exhibits more firmly about the strength of the cipher.

CRYPTANALYSIS

The different types of 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 matrices K and L, involved in this analysis, contain 16 decimal numbers each. The constants d and e, which are chosen at our will in the construction of the involutory matrices A and B, are two more decimal numbers. In view of these facts, the total length of the keys is 34 decimal numbers, that is 272 binary bits. Hence the size of the key space is

If the time required for obtaining the plaintext with one value of the key in the key space is 10-7 seconds, then the time required for the execution of the cipher with all the possible keys in the key space is

As this number is very large, we can firmly say that this cipher cannot be broken by the brute force attack. Let us now consider the known plaintext attack. In this we know as many pairs of the plaintext and the ciphertext as we desire. In the development of this cipher as we have an iterative process, which involves a pair of keys, functions mix() and substitute(), and XOR operation, at the end of the iteration process, the relation between the plaintext and the ciphertext can be viewed as shown below

In writing (4.1), the function mix() and the function substitute() are represented as M and  for simplicity and elegance. Here we notice that the equation (4.1) cannot be written in the form

where F is a function, depending upon K,L,M and . This amounts to that we cannot find a direct relation between C and P as we could do in the case of the classical Hill cipher. Thus this cipher cannot be broken by the known plaintext attack. The last two cases of cryptanalysis, namely chosen plaintext attack and chosen ciphertext attack are very complicated, and hence we leave them at the present stage. In the light of the above discussion we conclude that this cipher is a strong one.

COMPUTATIONS AND CONCLUSIONS

In this investigation, we have developed a block cipher, called modern advanced Hill cipher, which includes a pair of keys, XOR operation and functions mix() and substitute(). In this cipher the computations are carried out by writing programs for encryption and decryption in Java. The plaintext (3.1) is divided into 6 blocks, wherein each block is containing 64 characters. Nevertheless, as the last block is containing only 26 characters, it is supplemented with 38 blank characters so that it becomes a complete block. On using the encryption algorithm the ciphertext corresponding to the entire 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, and it can be applied comfortably for the transmission of information in a secured manner.

References

Aruna Varanasi, V.U.K.Sastry and S.Udaya Kumar, “ A modern Advanced Hill cipher Involving a Pair of Keys, Modular Arithmetic Addition and Substitution”, sent for publication. V.U.K.Sastry, Aruna Varanasi, S.Udaya Kumar, “Advanced Hill Cipher Involving Permutation and Iteration”, International Journal of Advanced Research in Computer Science, Vol.1, No.4, pp. 141-145, Nov-Dec. 2010.