ISSN: 2229-371X

All submissions of the EM system will be redirected to Online Manuscript Submission System. Authors are requested to submit articles directly to Online Manuscript Submission System of respective journal.

A Modern Advanced Hill Cipher Involving a Permuted Key and Modular Arithmetic Addition Operation

V.U.K.Sastry1, Aruna Varanasi*2 and S.Udaya Kumar3
  1. Department of computer Science and Engineering,SNIST Hyderabad, India,
  2. Department of computer Science and Engineering,SNIST Hyderabad, India
  3. Department of computer Science and Engineering,SNIST Hyderabad, India,
Corresponding Author: Aruna Varanasi, E-mail: varanasi.aruna2002@gmail.com
Related article at Pubmed, Scholar Google

Visit for more related articles at Journal of Global Research in Computer Sciences

Abstract

In this paper we have devoted our attention to the study of a block cipher by generalizing advanced Hill cipher by including a permuted key. In this analysis we find that the iteration process, the mix operation and the modular arithmetic operation involved in the cipher mixes the binary bits of the key and the plaintext in a thorough manner. The avalanche effect and the cryptanalysis markedly indicate that the cipher is a strong one.

Keywords

symmetric block cipher, cryptanalysis, avalanche effect, cipher text, key, permuted key.

INTRODUCTION

The study of the advanced Hill cipher [1], which depends mainly upon the concept of an involutory matrix (a matrix which is equal to its inverse), has roused the interest of researchers in the areas of cryptography and image cryptography. In a recent investigation, we [2-5] have studied several aspects of the advanced Hill cipher by including iteration process and a process of permutation in each round of the iteration. In all these analyses, we have established that the strength of the cipher is quite significant. The basic relations supporting the development of the advanced Hill cipher can be mentioned as follows:
image
where A is a square matrix of size n, A-1 is the modular arithmetic inverse of A, and N is any non zero positive integer chosen appropriately.
image
image
is obtained by permuting the sub matrices of A. In this analysis, we include iteration process, and a process of mixing in each round of the iteration.
Now let us mention the plan of the paper. In section 2, we have introduced the development of the cipher and presented the flow charts and algorithms for the encryption and the decryption. We have illustrated the cipher with a suitable example in section 3. Further, we have studied the avalanche effect in this section. Then we have carried out the cryptanalysis in section 4. Finally in section 5, we have devoted our attention to computations and conclusions.

DEVELOPMENT OF THE CIPHER

Let us consider a plaintext, P. On using EBCDIC code, let P be written in the form of a matrix given by
image
image
In this, the function involute() includes the procedure, given by the relations (1.4) – (1.8), for obtaining the involutory matrix A. Here, we have included iteration process and the function mix() in each round of the iteration process to achieve thorough confusion and diffusion in arriving at the ciphertext. Further, here we have used the function permute() for obtaining A0. The function Imix() denotes the reverse process of mix(). The detailed discussion of mix is given later.
The algorithms for encryption and decryption are written 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 + A0) mod 256
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)
4. for i= 1 to r
{
C = Imix(C)
C= ( A (C-A0 ))mod 256
}
P = C
4. Write (P)
In the above algorithms „r‟ indicates the number of rounds.
Let us now consider the process of mixing, represented by the function mix(), in the encryption algorithm. In each stage of the iteration process, the plaintext matrix P is of size nxn, where each element can be represented in terms of eight binary bits. Thus the entire matrix can be written in the form of a string of binary bits containing 8n2 bits. Here, this string is divided into four substrings wherein each one is of size 2n2 binary bits. These strings can be written in the form
image
Here, the mixing is done by arranging the binary bits of the different substrings as shown below:
image
Then this is decomposed into n2 substrings by considering 8 bits at a time in order. On writing each substring in the form of a decimal number, we get a square matrix of size n.

ILLUSTRATION OF THE CIPHER

Consider the plaintext given below:
“Dear! Where are you? How are you? I have been waiting for your arrival with wide open eyes. Your mother and father are visiting several houses and seeing several matches for you. Of course I have got my belief in you and our love and affection are eternal. I know this fact and wait for you.”
We focus our attention on the first sixty four characters of the plaintext (3.1). This is given by
“Dear! Where are you? How are you? I have been waiting for your a”
On using the EBCDIC code, the plaintext under consideration can be written in the form
image
On using the relations (1.4) - (1.8) and taking d=99, we get
image
On using (3.5), (3.6) and (3.7), and applying the decryption algorithm, we get back the original plaintext given by (3.3).
Let us now focus our attention on the avalanche effect, which yields a measure regarding the strength of the cipher. To carry out this one, firstly we replace the ninth character „e‟ of the plaintext (3.2) by„d‟. The EBCDIC codes of„d ‟ and „e ‟ are 132 and 133 . On converting these two numbers into their binary form, we find that they differ by one bit. On using the plaintext, including afore mentioned modification, the A and A0 given by (3.5) and (3.6), we apply the encryption algorithm, and find the ciphertext C. Thus we have
image
On comparing (3.7) and (3.8), in their binary form, we notice that the two ciphertexts differ by 260 binary bits (out of 512 bits). This indicates that the cipher is a strong one.
Let us now focus our attention on a one bit change in the key K. In order to achieve this one, we replace the first row fourth column element “ 67 ” of (3.4), by “ 66 ”. After obtaining A and the corresponding A0, we perform the encryption (using the original plaintext). Thus we get the ciphertext given by
image
Now on comparing (3.7) and (3.9), in their binary form, we find that they differ by 278 bits (out of 512 bits). This also thoroughly suggests that the cipher is a potential one.
Let us now consider, firstly, the ciphertext only attack. In this analysis the key K, given by (3.4), is consisting of 16 numbers wherein each number can be represented in the form of 8 binary bits. In addition to this key, we have made use of an integer„d‟, which can be considered as an additional key, in the development of the involutory matrix, A. This key requires eight more binary bits, and hence the total length of the key, which controls the cipher, is 136 bits. Thus the size of
image
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 for carrying out the determination of the plaintext with all the possible keys in the key space is
image
As this number is a formidable one, it is simply impossible to break the cipher by this attack.
In the case of the known plaintext attack, we have as many pairs of plaintext and ciphertext as we wish. In this analysis, as we have the prominent features, namely, iteration, mixing and modular arithmetic addition operation, involving A0, by the time we reach the final stage of the iteration process, we get a relation between the ciphertext, the involutory matrix A ( including the key K) and the original plaintext P in the form
image
In the above relation, A0 is obtained by permuting A, see (1.13), and the M() stands for the function mix(). In (4.1) the matrix A (containing the key K) is multiplied with the plaintext P, and it is added to A0. Then mixing is carried out after performing the mod 256. On account of this sort of operations, the binary bits of the key and the plaintext are thoroughly mixed at various stages, and hence it is impossible to decipher the key or a function of the key, which enables the cryptanalyst to break the cipher. From this we conclude that the cipher cannot be broken by the known plaintext attack.
With all effort, basing upon intuition, no special choice of either the plaintext or the ciphertext appears to yield a scope for breaking the cipher.
In the light of the above discussion of cryptanalysis, we firmly conclude that the cipher is a strong one, and it cannot be broken by any means.

COMPUTATIONS AND CONCLUSIONS

In this paper, we have developed a block cipher called modern advanced Hill cipher. In this the Hill cipher has taken a very refined shape from the view point of the analysis and the strength of the cipher.
Here the computations are carried out by writing programs for encryption and decryption in Java.
The ciphertext corresponding to the complete plaintext, given by (3.1), is obtained in the form
image
In obtaining this ciphertext, we have divided the plaintext (3.1) into five blocks. Of course, in the last block we have added twenty nine blank characters to make it a complete block.
From the significance of the avalanche effect and the consideration of the cryptanalysis, here it is interesting to note that this block cipher is a strong one, and it is quite comparable with any other block cipher in all respects. In this analysis A0 is obtained by permuting A in a particular manner. Here it is to be noted that A0 can be obtained in many other ways by permuting A. For example A0 can be taken as AT(transpose of A) or it can be obtained by interchanging rows and or columns in any desired fashion.

References

  1. 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.
  2. 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.
  3. V.U.K.Sastry, Aruna Varanasi, S.Udaya Kumar, “Advanced Hill Cipher Handling the Entire Plaintext as a Single Block”, International Journal of Advanced Research in Computer Science, Vol.1, No.4, pp. 180-184, Nov-Dec. 2010.
  4. V.U.K.Sastry, Aruna Varanasi, S.Udaya Kumar, “Advanced Hill Cipher Involving a Key Applied on Both the Sides of the Plaintext”, International Journal of Computational Intelligence and Information Security,Vol. 1 No. 9, pp. 70-78, November 2010.
  5. V.U.K.Sastry, Aruna Varanasi, S.Udaya Kumar,” Advanced Hill Cipher Involving a Pair of Keys”, International Journal of Computational Intelligence and Information Security, Vol.2 No.1, pp 100-108, January 2011.
  6. V.U.K.Sastry, Aruna Varanasi, S.Udaya Kumar,” A Modern Hill Cipher Involving a Permuted Key and Modular Arithmetic Addition Operation”, International Journal of Advanced Research in Computer Science, Vol.2, No.1, pp.162-165, Jan-Feb 2011.
  7. V.U.K.Sastry, Aruna Varanasi, S.Udaya Kumar,” A Modern Hill Cipher Involving XOR operation and a Permuted Key ”, International Journal of Advanced Research in Computer Science, Vol.2, No.1, pp.153-155, Jan-Feb 2011.