Hill Cipher algorithm with Self Repetitive Matrix for Secured Data Communication

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 Hill-cipher is matrix manipulations It is a multi-letter 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, Hill-cipher

1. 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.

2. PRESENT THEORY & PRACTICES

   HILL CIPHER

   It is a multi-letter 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 K-1 of a matrix K is defined by the equation. K K-1= I where I is the Identity matrix.

   K-1 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) =K-1 C= K-1KP=P

3. 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:

1. Check whether the matrix K is invertible or not.

2. 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 E-1 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 non-singular.

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.

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

2. Pick up any random invertible square matrix B 4.Generate C=B-1AB

5.The N value of C is also N Mathematical proof:

(B-1AB)N= (B-1)N *(A)N*(B)N AN=I

as calculated before as it is a diagonal matrix and N is the LCM of all elements (B-1B)*(B-1*B)…….n times=I

1. 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

   Different-different 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.

   1. 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.

      1. 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

      2. 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

      1. 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

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

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

3. In SMS services, e-commerce, pay TV, computer passwords and touches many aspects of our daily lives.

REFERENCES

1. 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

2. 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.

3. 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

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

5. 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.

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

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

8. Abrams, M., and Podell, H. Cryptography Potentials, IEEE Page No 36-38. Issue:1,Volume: 20, Feb-Mar,2001

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

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

11. W.Diffie; M.E.Hell man, New Directions in Cryptography IEEE Transactions Information Theory, Nov, pp 644-654

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