Hill cipher analysis

The Hill cipher as discussed in the book on cryptography by William Stallings uses a square matrix K as a key in the encryption process. During decryption, however the inverse of the key matrix K is used. The author's explanation of finding out the inverse under modulo 26 is insufficient. Thus, in this article I will show you how to find out the inverse. In page 56 of the book the example matrix K is:

                                                                             17 17 05
                                                                             21 18 21
                                                                            02 02 19

Finding the inverse of a matrix can be illustrated as a three step process:

1.Replace the original elements by the adjoint of that element in the matrix,
2.Transpose the matrix,
3.Divide every element by the determinant of the original matrix.

The adjoint of an element is the determinant of the submatrix that is formed on deleting the row and column in which the element. For example adjoint of 17 in the above matrix is:

                                                                    (18*19)-(21*2)=300

Similarly on calculating the adjoint of other elements we get the following:

                                                                      +300 -357 +006
                                                                      -313 +313 +000
                                                                      +267 -252 -051

We now transpose the above matrix to get the following:

                                                                    +300 -313 +267
                                                                    -357 +313 -252
                                                                   +006 +000 -051

The determinant of the original matrix is -939. Now this is where hill cipher differs because all arithmetic must be done mod 26. The modulo operation can be defined as:

                                                                   x mod y = x - y * floor(x/y)

Here floor(x) is the greatest integer lesser than or equal to x. Thus floor(13.5) is 13 and floor(-13.5) is -14. Thus,

                                               -939 mod 26 = -939 - 26 * floor(-939/26) = 23.

Thus the final step now is to find the multiplicative inverse of 23 under mod 26 and multiply the result with every element of the transposed adjoint matrix. Suppose if the multiplicative inverse of 23 is x then by the definition of multiplicative inverse 23*x = 1 mod 26. That is if 23 is multiplied by x and then divided by 26 to yield a remainder of 1 then x is said to be the multiplicative inverse of 23 under mod 26.

Thus we need to find x such that:
                                                                     23 * x = 1 mod 26.

This is equivalent to: 
                                                                    23 * x - 26 * y = 1 .........(1)

                                                                 Here both x and y are integers.

Dividing (1) by 2 we get, 
                                                               12*x - x/2 - 13*y = 1/2 .........(2)

This can be rewritten as: 
                                                              12*x - 13*y -(x+1)/2 = 0 ..........(3)

The quantity (x+1)/2 must be and integer say 't'. Then x = 2t-1.

Substituting for x in (1) we get,

                                                                       46*t - 23 - 26*y = 1
                                                                                    or
                                                                       46*t - 26 *y = 24 
                                                                                    or
                                                                        23*t-13*y= 12. 

Now we start subsituting values for t starting from 1 until y is an integer.
For ex, if t=1 above then y = 11/13 which is not an integer. We see that when t=9 then y=15 an integer.

Thus we have,
                                23*x-26*15=1
                                         or
                               x = 391/15 = 17.

Thus 17 is the multiplicative inverse of -939 under mod 26.

Now 300 (which is the adjoint of the first element of the original matrix i.e. 17) must be mulitplied by the multiplicative inverse of -939.

                                                                       300 * 17 = 5100.

5100 mod 26 = 4. The first element of the inverse matrix. Other elements of the inverse matrix can be found similarly. The inverse matrix is thus:

                                                                              04 09 15
                                                                              15 17 06
                                                                              24 00 17.

Thank you for reading. Hope you have gained a better understanding of the Hill cipher.