 Open Access
 Total Downloads : 375
 Authors : Ashwin Ramesh
 Paper ID : IJERTV4IS070560
 Volume & Issue : Volume 04, Issue 07 (July 2015)
 DOI : http://dx.doi.org/10.17577/IJERTV4IS070560
 Published (First Online): 23072015
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Enhancing the Security of Hill Cipher using Columnar Transposition
Ashwin Ramesh
BTech Student: Dept. of Computer Science & Engineering Manipal Institute of Technology
Manipal, India
AbstractHill cipher algorithm is based on polygraphic substitution technique centered on linear algebra. The algorithm takes m successive plaintext letters and replaces them with m cipher text letters. This technique involves representing the plaintext as a matrix before undergoing encryption which produces another matrix, from which the cipher text is extracted. Through this paper the author wishes to propose a technique to deal with a loophole which compromises the security of the algorithm. The examination of the attack involves looking for repetitions of substrings in the cipher text. If the distance between the two substrings happen to be a multiple of n, where n is the size of the invertible square matrix representing the key, then their respective cipher texts would also be the same. This can predict the size of the key matrix used. The key can be then be discovered with more ease.
KeywordsEncryption, Decryption, Hill cipher, Cryptography, Cryptanalysis, Plaintext, Cipher text, Security, Transposition, Substitution, Modified Hill Cipher.

INTRODUCTION
With increasing emphasis on network security in the modern world, the need to keep and transmit data in an encrypted form has become really important. Cryptography, the discipline of securing important data [1] has become more of an inevitability than a luxury. A lot of information is sent via public network channels [2], and is important that the data maintains authenticity, integrity, confidentiality and nonrepudiation [3] throughout. Cryptography can be divided into three categories [4] secret key cryptography, publickey cryptography [5] and hash functions. Hill cipher falls under the first category.
In cryptography, substitution is a method where units of a plaintext are encoded by replacing them with new units. This is usually facilitated by a substitution cipher algorithm. A substitution process is much different from a transposition process, where the letters are merely shuffled [6]. Hill cipher is a polygraphic [7] encryption substitution cipher which involves the usage of the concepts of linear algebra to produce the cipher text for a given plaintext. The basic technique behind the cipher algorithm is that of matrix multiplication. The first step involves representing each letter with a unique number. A simple representation is represented in Table 1.
TABLE I. ALPHABET MATRIX.
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
G
H
I
J
10
11
12
13
14
15
16
17
18
19
K
L
M
N
O
P
Q
R
S
T
20
21
22
23
24
25
U
V
W
X
Y
Z
The encryption process involves selecting a cipher key [8], and representing it as a square matrix any size n, by replacing the letters with their respective numbers. This square matrix should be an invertible matrix [9]. Filler elements can be used to fill the matrix in case the letters arent enough. For instance, a key BDBBBCCDE, can be represented in a 3×3 matrix K as,
Fig. 1. An example of the key matrix.
The plaintext to be encrypted is divided into blocks of n letters. Each represented as Pi, where i represents the index of a block. For instance, let the plaintext be ABCDEFABCXYZ. It can be divided into blocks of size 3, such that there are 4 blocks, ABC (P0), DEF (P1), ABC (P2) and XYZ (P3). The individual blocks are then multiplied with the key matrix. Modulo 26 of that product is the required cipher text. The mathematical representation is: Ci
= (Pi.K) mod 26. The following would be the encryption procedure of the first 3 letters of the plaintext.
Fig. 2. The encryption procedure.
The decryption process requires the inverse of the key matrix, K1 = (K)1 mod 26. The inverse matrix [9] is then multiplied with the cipher text. Modulo 26 of this product gives us back the plaintext. The mathematical representation is: Pi = (Ci.K1) mod 26. The following would be the decryption procedure of the first 3 letters of the cipher text.
Fig. 3. The decryption procedure.
The cipher text of the above mentioned plaintext would be FHKRCFFHKTMP. As one can notice that the cipher text of the same plaintext substrings at an interval of n are the same. This major security lapse can be used as a stepping stone by a cryptanalyst to guess the size of the key matrix taken during the encryption process and launch an attack on the security system.
In this paper, the author introduces a method to deal with such a situation by dealing it in an effective manner. This paper suggests 4 stages to remove this potential threat. The first stage involves a permutation process on the plain text, using columnar transposition. The second involves application of the Hill cipher algorithm. The third stage applies another round of columnar transposition using a key different to the one used in stage 1. In the last stage, the Hill
cipher algorithm is applied again. The paper attempts to prove that the 4 stage encryption method removes the above mentioned threat and increase the security level of the algorithm. The two stages of columnar transposition protect the algorithm from a knownplaintext attack [10]. The original algorithm is vulnerable because of being a completely linear algorithm. Hence, a lot of research work has taken place to improve the security of the Hill cipher algorithm [1115].
Columnar transposition involves writing the plaintext out in fixed sized rows. Then depending on a key value, it is read out column by column. The alphabetical order of the letters in the key decides the order in which the columns have to be read in. A double columnar transposition involves applying the same procedure twice using the same or different keys.

METHODOLOGY

Encryption
Stage 1: First Double Columnar Transposition. Algorithm: Double Columnar Transposition.
The algorithm performs double columnar transposition on the plaintext.
Input: Plaintext (P), keys (K1, K2), size of key K1 (m), size of K2 (n).
Output: Intermediate cipher text (C). Initialize: i 0.
1: Place the letters in P rowwise in the table with m elements in one row.
2: Add filler characters, if necessary, to fill all the elements of the last row.
3: Read the table columnwise depending on the order of the alphabets in K1.
4: Store as Ptemp.
5: Place the letters in Ptemp rowwise in the table with n elements in one rw.
6: Repeat step 2.
7: Read the table columnwise depending on the order of the alphabets in K2.
8: Store as C. 9: end
Stage 2: First Application of Hill Cipher.
Algorithm: Hill Cipher Encryption.
The algorithm applies the Hill cipher encryption technique.
Input: Intermediate cipher text (P), key (key), size of key square matrix (n).
Output: Intermediate cipher text (C). Initialize: i 0.
1: Represent letters of key with their respective numbers in the matrix K.
2: Divide P into blocks of size n. Add filler to complete the last block, if necessary.
3: while i < n:
4: Ci = (Pi.K) mod 26
5: i i + 1
6: Replace the numbers with their respective letters. 7: Store the cipher text as C.
8: end
Stage 3: Second Double Columnar Transposition.
Repeat the algorithm mentioned in stage 1 on the intermediate cipher text obtained after stage 2.
Stage 4: Second Application of Hill Cipher.
Repeat the algorithm mentioned in stage 2 on the intermediate cipher text obtained after stage 3. The result after the stage is final cipher text which is free from the hazard under consideration.

Decryption
The decryption process involves applying the reverse of all of the 4 stages in the reverse order.
Stage 1: First Application of Hill Cipher Decryption. Algorithm: Hill Cipher Decryption.
The algorithm decrypts a cipher text encrypted by Hill cipher.
Input: Cipher text (C), inverse of the key (invkey), size of invkey square matrix (n).
Output: Intermediate plaintext (P). Initialize: i 0.
.
1: Represent letters of invkey with their respective numbers in the matrix K1
2: Divide C into blocks of size n. 3: while i < n:
4: Pi = (Ci.K1) mod 26
5: i i + 1
6: Replace the numbers with their respective letters. 7: Store the plaintext as P.
8: end
Stage 2: First Application of Columnar Transposition Decryption.
Algorithm: Columnar Transposition Decryption.
The algorithm decrypts a cipher text encrypted by columnar transposition.
Input: Intermediate plaintext (C), size of cipher text (size), keys (K1, K2), size of key K1 (m), size of K2 (n).
Output: Intermediate plaintext (P). Initialize: i 0.
1: Place the letters in P columnwise in the table with (size/n) elements in one column.
2: Read the table rowwise depending on the order of the alphabets K2.
3: Store as Ctemp.
4: Place the letters in Ctemp columnwise in the table with (size/m) elements in one column.
5: Read the table rowwise depending on the order of the alphabets K1.
6: Store as P. 7: end
Stage 3: Second Application of Hill Cipher Decryption.
Repeat the algorithm mentioned in stage 1 on the intermediate plaintext obtained after stage 2.
Stage 4: Second Application of Columnar Transposition Decryption.
Repeat the algorithm mentioned in stage 2 on the intermediate plaintext obtained after stage 3. The result after the stage is final plaintext.


RESULTS Plaintexts taken during experiments:
TABLE 2. RESULTS OF TEST CASE I.
Plaintext
CATHERINEISACAT
K1 (Columnar Transposition)
BANGLE
K2 (Columnar Transposition)
SQUARE
K3 (Hill Cipher)
HYPNOTISE
Stage 1
ANACICRAZHIXESYTET
Stage 2
NANEOIHARZSLMAEZWV
Stage 3
EZZILVAAAOSWNHMNRE
Stage 4
HMLDWXAAAOWQSMUGYO
TABLE 3. RESULTS OF TEST CASE II.
Plaintext
MATHSDOESMATTER
K1 (Columnar Transposition)
PERSON
K2 (Columnar Transposition)
NOTICE
K3 (Hill Cipher)
TRIANGLES
Stage 1
AEEDTZSAYMOTTSRHMX
Stage 2
SQSUIQIMEVUCCBULDE
Stage 3
IUDQCEUVLSICQMNSEU
Stage 4
DSEKCEHHQACUDQKQWI

ANALYSIS
TABLE 4. COMPARISON OF THE REULSTS OF THE HILL CIPHER ALGORITHM AND THE 4STAGE ALGORITHM (TEST CASE I).
Hill Cipher Algorithm
HMLDWXAAAOWQSMUGYO
4 Stage Algorithm
KACDKPXETECUKAC
TABLE 5. COMPARISON OF THE REULSTS OF THE HILL CIPHER ALGORITHM AND THE 4STAGE ALGORITHM (TEST CASE II).
Hill Cipher Algorithm
DSEKCEHHQACUDQKQWI
4 Stage Algorithm
VUWKBKWYSVUWCBO
In both the examples taken in the previous section, it can be clearly noticed that applying the Hill cipher encryption algorithm results in repetition of a substring (KAC in test case 1, and VUW in test case 2) at an interval which is equal to the length of the key used. But, applying the 4 stage algorithm on the given plaintexts shows that such a pattern is not generated in the cipher text. Hence, no information about the size of the key square matrix could be attained by just looking at the cipher text, unlike the old method.

CONCLUSION
The above results clearly show that 4 stage algorithm introduced in the paper eliminates the possibility of repetition of substrings at an interval which is a multiple of the size of the key square matrix. The two stages of transposition generate permutations of the text which makes cryptanalysis on the cipher text even more tedious. The potential loophole in the Hill cipher algorithm discussed in the paper is also eliminated by transposition of the text before applying the Hill cipher encryption algorithm.
REFERENCES

Kahate, A. Cryptography and Network Security, 2nd Edition.

Tanenbaum, A. S.; Wetherall, D. J.; Computer Networks, 5th Edition.

Forouzan, B. A.; Cryptography and Network Security.

Kessler, G. C.; An overview of cryptography. Retrieved on June 21, 2015, from http://www.garykessler.net/library/crypto.html

Ayushi. A symmetric key cryptographic algorithm. International Journal of Computer Applications (0975 – 8887), 1, 15.

Malay B. Pramanik; Implementation of Cryptography Technique using Columnar Transposition, International Journal of Computer Applications (0975 8887) Second National Conference on Recent Trends in Information Security, GHRCE, Nagpur, India, Jan2014.

Kumar, N.; Panduranga, H. T.; Advanced Partial Image Encryption using Twostage Hill Cipher Technique. International Journal of Computer Applications (0975 8887), 60, 16.

Stallings, W.; Cryptography and Network Security: Principles and Practice, 5th Edition

Chirgaiya, S.; & Sharma, N.; A Novel Approach to Hill Cipher. International Journal of Computer Applications (0975
8887), 108, 11

Borissov, Y.; Lee, M. H.; Bounds on Key Appearance Equivocation for Substitution Ciphers. IEEE transactions on information theory, 53(6), 22942296.

Saeednia, S.; How to Make Hill Cipher Secure. Cryptologia, 24(4), 353360.

Bhowmick, A.; & Maiya, G.; Enhancing Resistance of Hill Cipher using Columnar and Myszkowski Transposition. International Journal of Computer Sciences and Engineering, 3(2), 23472693.

Chefranov, A. G.; Secure Hill Cipher Modification. Proc. Of the First International Conference on Security of Information and Network (SIN2007) 710 May 2007, Gazimagusa (TRNC) North Cyprus, Elci, A., Ors, B., and Preneel, B (Eds) Trafford Publishing, Canada, 2008: pp 3437, 2007.

P. L. Sharma; M. Rehan; On ecurity of Hill Cipher using Finite Fields, International Journal of Computer Applications (0975 8887) Volume 71 No.4, May 2013.

Kondwani Magamba,; Solomon Kadaleka, Ansley Kasambara,; Variablelength Hill Cipher with MDS Key Matrix, International Journal of Computer Applications (0975
8887) Volume 57 No.13, November 2012.