 Open Access
 Total Downloads : 703
 Authors : Prof.Sana F Amin, Prof. Nilofar S Hunnergi
 Paper ID : IJERTV2IS90575
 Volume & Issue : Volume 02, Issue 09 (September 2013)
 Published (First Online): 28092013
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Hill Cipher algorithm with Self Repetitive Matrix for Secured Data Communication
1 Prof.Sana F Amin 2 Prof. Nilofar S Hunnergi
1 Assistant Professor
Ashokrao Mane Group of Institutions, Vathar
2Assistant Professor
Sanjay bhokre college of engineering, Miraj
ABSTRACT
The core of Hillcipher is matrix manipulations It is a multiletter cipher,for Decryption the inverse of matrix requires and Inverse of the matrix doesnt always exist. Then if the matrix is not invertible then encrypted text cannot be decrypted. However, a drawback of this algorithm is over come by use of self repetitive matrix.This matrix if multiplied with itself for a given mod value (i.e. mod value of the matrix is taken after every multiplication) will eventually result in an identity mat rix after N multiplications. So, after N+ 1 multiplication the matrix will repeat itself. Hence, it derives its name i.e. self repetitive matrix. It should be non singular square matrix.
KEYWORDS Cryptography , encryption, Decryption, Hillcipher

INTRODUCTION
Cryptography is defined as the science or study of the techniques of secret writing, esp. code and cipher systems, methods, and the like. Cryptography is needed so that text can be kept secret. It is easy to imagine situations in ancient
times where a writer who sent a message via courier would want to make sure that if the runner were intercepted, the interceptors could not read the message.
Recently, the uses of cryptography have grown drastically. Becuase advent of computers and with it the vast amount of information being shared on the internet, there has been a need to create better, more efficient encryption strategies to protect private information, such as credit card numbers, private communications, and so on.

PRESENT THEORY & PRACTICES
HILL CIPHER
It is a multiletter cipher, developed by the mathematician Lester Hill in 1929.For encryption, algorithm takes m successive plaintext letters and instead of that substitutes m cipher letters. In Hill cipher each character is assigned a numerical value
Like: a=0, b=1,
..
.. z=25.
The substitution of cipher text letters in place of plaintext leads to m linear equations. For m=3, the system can be described as follows:
C1= (K11P1+K12P2+K13P3) MOD26 C2= (K21P1+K22P2+K23P3) MOD26 C3= (K31P1+K32P2+K33P3) MOD26
This can be expressed in terms of column vectors and matrices: C=KP
Where C and P are column vectors of length 3, representing the plaintext and the cipher text and K is a 3*3 matrix, which is the encryption key. All operations are performed mod 26 here. Decryption requires the inverse of matrix K. The inverse K1 of a matrix K is defined by the equation. K K1= I where I is the Identity matrix.
K1 is applied to the cipher text, and then the plain text is recovered. In general terms we can
write as follows:
For encryption: C= Ek (P) = KP
For decryption: P= Dk (C) =K1 C= K1KP=P

PROPOSED THEORY & PRACTICES Modification to the Algorithm
As we have seen in Hill cipher decryption, it requires the inverse of a matrix. So while one problem arises that is: Inverse of the matrix doesnt always exist. Then if the matrix is not invertible then encrypted text cannot be decrypted. In order to overcome this problem we suggest the use of self repetitive matrix. This matrix if multiplied with itself for a given mod value (i.e. mod value of the matrix is taken after every multiplication) will eventually result in an identity matrix after N multiplications. So, after N+ 1 multiplication the matrix will repeat itself. Hence, it derives its name i.e. self repetitive matrix. It should be non singular square matrix.
MODIFIED HILL CIPHER ALGORITHM:
This algorithm generates the different key matrix for each block encryption instead of keeping the key matrix constant. This increases the secrecy of data. Also algorithm checks the matrix used for encrypting the plaintext, whether that is invertible or not. If the encryption matrix is not invertible, then the algorithm modifies the matrix such a way that its inverse exist. The new matrix we obtain after modification of key matrix is called as Encryption matrix and with the help of this matrix encryption operation is performed. In order to generate different key matrix each time, the encryption algorithm randomly generates the seed number and from this key matrix is generated.
Key matrix,
K K11 K12 K13 K21 K22 K23
K31 K23 K33
Where, K11 = seed number
K12 = (seed number * m) mod n K13 = (12 K * m) mod n
K21 = (13 K * m) mod n
. .
K33 = (32 K * m) mod n
Where m is successive numbers of plaintext letters taken at a time for encryption and n is length of the lookup table (total characters used for encryption and decryption) or we can set this n value as per requirement. Then with the help of key matrix, encryption matrix E is generated.
Steps for encryption matrix generation are as follows:

Check whether the matrix K is invertible or not.

If inverse of matrix K does not exist, then adjust the diagonal elements (Increment the values of diagonal elements, one element at a time) so that the inverse of the resultant matrix (matrix obtained after changing diagonal elements) is invertible. This matrix becomes the Encryption matrix E.
In this algorithm it takes m successive plaintext characters and substitutes for then m cipher text characters. The substitution is determined by m linear equations in which each character is assigned a numerical value (we can take the characters ASCII equivalent number or we can assign a lookup table like a = 0, b = 1 … z = 25) Here for m = 3, the
System can be described as follows: C1= (E11 P1+E12 P2+E13 P3) mod n C2= (E11 P1+E12 P2+E13 P3) mod n C3= (E11 P1+E12 P2+E13 P3) mod n
This case can be expressed in term of column vectors and matrices: C1 E11 E12 E1 P1
C2 = E21 E22 E23 P2 mod n
C3 E31 E32 E33 P3
or C = EP mod n , where C and P are column vectors of length 3 , representing the Cipher text and plaintext respectively, and E is a 3 Ã— 3 encryption matrix. All operations are performed mod n.
Steps for Decryption Matrix:
For decryption, from the seed number once again similar way E matrix is generated. Decryption required using the modulo inverse of the matrix E. The inverse E1 of matrix E is defined by the equation
E.E1 = E1.E = I
Where I is the matrix that is all zeros expect for ones along the main diagonal from upper left to lower right. Hence decryption matrix D is generated by doing modulo inverse of encryption matrix. Multiply decryption matrix D with received cipher text number vector C and then do modulo operation. Then operate on the output resultant vector, substitute its equivalent characters and which is the plaintext. We can explain this as
Plaintext = P = D.C = E 1C. In general, the algorithm can be expressed as follows:
Cipher text = C = EP mod n
Plain text = P = E 1C mod n = E 1EP = P
Generation of a self repetitive Matrix A for a Given N:
The initial conditions for the existence of a self repetitive matrix are: 1.The matrix should be square.
2.It should be nonsingular.
But trying to find out the value of N (the value where the matrix becomes a identity matrix) through the method of brute force may not be the best idea always; because the matrix is of dimension greater than 5*5 and with mod index (i.e.)greater than 91 then the brute force technique might take very long time and N value may be in the range of millions. A normal Pentium 4 machine might hang if asked to do the computations for 15*15 matrixes or more. Hence, it would be comfortable to know the value of N and then generate a random matrix accordingly.
This can be done as follows:
1 .First a diagonal matrix A is chosen, and then the values powers of each individual element when they reach unity is calculated and denoted as n1, n2, n3…. Now
LCM of these values is taken to given the value of N.

Now the next step is generate a random square matrix whose N value is same as the N calculated in the previous step.

Pick up any random invertible square matrix B 4.Generate C=B1AB
5.The N value of C is also N Mathematical proof:
(B1AB)N= (B1)N *(A)N*(B)N AN=I
as calculated before as it is a diagonal matrix and N is the LCM of all elements (B1B)*(B1*B)…….n times=I

RESULTS
Let us see the result with the case study for an array of 5 elements .
Let, m = 5, n = 97 and Seed number S = 141
Then,
K11 = 141
K22 = (K11*2) mod n
. .
. .
K55 = (K44*5) mod n Hence Key Matrix:
141
0
0
0
0
0
90
0
0
0
K =
0
0
78
0
0
0
0
0
24
0
0
0
0
0
24
Consider the plaintext to be encrypted is event. Letters of the plaintext are represented by their equivalent number vector (30 47 30 39 45)
ENCRYPTION MATRIX
Then with the help of key matrix, encryption matrix is generated. Encryption matrix we get as
62
0
0
0
0
0
6
0
0
0
K =
0
0
22
0
0
0
0
0
35
0
0
0
0
0
35
Then, Cipher text for the plaintext is [17 88 78 7 23]
Decryption is done by doing inverse method of above and the cipher text is converted to the original as event
30
36
0
0
0
0
17
47
0
81
0
0
0
88
30
=
0
0
75
0
0
78
mod (97)
39
0
0
0
61
0
7
45
0
0
0
0
61
23
Decrypted Plain text output.
Thus replacing the vector numbers (30 47 30 39 45) by their ASCII values we get the word event.
Avalanche Effect:
Here avalanche parameter is used to evaluate performance of the proposed system. The proposed system is built on Mat lab platform, Comparison of results performed between proposed algorithm and two existing algorithms. At the time of results evaluation, plain text and key value both were written randomly. To calculate total effect proposed system run so many times on
Differentdifferent text file with the same key value and then final results were observed. Thus in the case of avalanche effect evaluation, after running proposed systems several times, the final results are the same i.e. in numeric form.

Avalanche Effect Comparisons: Avalanche Effect is the important property in cryptographic algorithms where, if an input is changed slightly (changing a single bit) the output changes significantly. In our case, we have chosen two different input plain text as welcometomycolle and welcometomycollewelcometomycolle Because of key length used in existing algorithm, proposed algorithm and A Block Cipher Having a Key on One Side of the Plain Text Matrix and its Inverse on the Other Side are using 128 bits key length where A Modified Hill Cipher Involving a Pair of Keys and a Permutation is using 256 bits key length. And proposed algorithm is using 56 bit key length.

A Block Cipher Having a Key on one side of the Plain Text Matrix and its Inverse on the other side
Plain Text: welcometomycolle 000011000000111000001010101000100000010011000000000000001001100000001010001000
11010110000010100000000000011110000100000000000000
Change in Plain Text: welcometomycolla 000010000001010000010101010011000000000101010001000000000011000000001100010011
1011100000110100000000000001110000110000001000000
Avalanche Effect: 18

A Modified Hill Cipher Involving a Pair of Keys and a Permutation
Plain Text: welcometomycollewelcometomycolle
000000000000000000000000000000000000000000000000000000000000100000000000000000
000000000000001000000000000110100000000000000000000010011000000000010100110000
000001010110000000000010000000100011010001100010000010000000011010000001011100
1010010111110010110010
Change in Plain Text: welcometomycollewelcometomycolla
100000010000001000000100000010000111000000000111000110000011100010100011000110
000001111100001001111111100110100000000000000000000010011000000000010100110110
000111010110000001111110000000111111010001100010110010111100011010011111011100
1011111111110010110010
C) Proposed Algorithm
Plain Text: welcometomycollegewe
011000010101011001110011000100000000010101001001100100000001000101000000000101
011001000100010111000100000001010000110011010110000000010110000001010101000001
010000000000000000000000000000000000000000000000000000000000000000000000000000
00
Change in Plain Text: walcometomycollegewe
100000010010000100000100011100010100010001110010000101010001000100010001000101
010001001101100110000101000001000100100001010001100110000101000011100110010001
000110010101000101010100000101000000000000000000000000000000000000000000000000
000000000000000000000000000000
Avalanche Effect: 79
ENCRYPTION TECHNIQUE
AVALANCHE EFFECT
A Modified Hill Cipher Involving a Pair of Keys and a Permutation
18
A Block Cipher Having a Key on One Side of the Plain Text Matrix and its Inverse on the Other Side.
59
Proposed Algorithm
79
90
79
80
70
59
60
50
40
30
20 18
Avalanche Effect
10
0
A Modified Hill A block Cipher Proposed
Algorithm
X Axis Selected Algorithms, Y Axis – Bit Difference
Figure : Avalanche effect

CONCLUSION
This modified Hill Cipher method is easy to implement and difficult to crack.

The cipher is considered secure, as it supports strong substitution techniques along with modular arithmetic.

The block size which is specified as 64 bit is expandable as per requirement, thus gives flexibility n message string length.

Possible ASCII printable character keys are 957 and key combinations are 256.

As per our findings time required checking all possible keys at 50 billion keys per second for a 56 bit key: would approximately be 400 days.



o The above performance will be appropriate for the following kind of applications

In ATMs for pin numbers to maintain its secrecy and security of ATM card.

In Email applications for military and civilian purpose where security is of prime importance in terms of records and authentication of messages.

In SMS services, ecommerce, pay TV, computer passwords and touches many aspects of our daily lives.
REFERENCES

Blakley, G.R.; Twenty years of cryptography in the open literature Security and Privacy, 1999. Proceedings of the 1999 IEEE Symposium on Digital Object Identifier: 10.1109/SECPRI.1999.766903

Secure Hill cipher modifications and key exchange protocol ,Mahmoud, Ahmed Y.; Chefranov, Alexander G.; Automation Quality and Testing Robotics (AQTR), 2010 IEEE International Conference on Volume: 2 Digital Object Identifier.

The Design of Boolean Functions by Modified Hill Climbing Method ,Izbenko, Y.; Kovtun, V.; Kuznetsov, A.; Information Technology: New Generations, 2009. ITNG '09. Sixth International Conference on ,Digital Object Identifier: Publication Year: 2009 , Publication Year: 2010

A secure variant of the Hill Cipher ,Toorani, M.; Falahati, A.; on, Digital Object Identifier: 10.1109/ISCC.2009.5202241 ,Publication Year: 2009.

Invertible, Involutory and Permutation Matrix Generation Methods for Hill Cipher System
,Acharya, B.; Jena, D.; Patra, S.K.; Panda, G.; Advanced Computer Control, 2009. ICACC '09. International Conference on ,Digital Object Identifier: Publication Year: 2009.

Bruce Schneir: Applied Cryptography, 2nd edition, John Wiley & Sons, 1996

Piper,F Encryption. Security and Detection, Ecos 97. European Conference;

Abrams, M., and Podell, H. Cryptography Potentials, IEEE Page No 3638. Issue:1,Volume: 20, FebMar,2001

Eskiciogiu,A. Litwin,L Cryptography and Network Security LOS Alamitos,CA:IEEE computer society press,1987

Garfinkel, S.L; Public Key Cryptography , Computer, IEEE, Volume: 29, Issue:6, June 1996.

W.Diffie; M.E.Hell man, New Directions in Cryptography IEEE Transactions Information Theory, Nov, pp 644654

E.Biham and A.Shmir; Differential C for Cryptanalysis of the Encryption Standard; Springer Verilag,1993