Introduction to Cryptology: Hill Cipher Remarks

• The core of Hill cipher is matrix manipulations. Both encryption and decryption are nothing more than matrix multiplications. So I suggest you first to write some code for basic matrix operations. In Java or C++, this may be a matrix class (in Z26). In C, you could have a matrix structure and a set of functions for creation, deletion and multiplication and so on. You could of course just stay with plain 2D integer array. At any rate, write the classes/routines and fully test them. Now you have solid foundation to go further.
• Encryption and decryption with known keys using your (bug-free) matrix code are now trivial. Try encrypt some piece of text and then decrypt it. See if you get the original text back.
• Decryption with known plain text needs matrix inversion. This seems to be the most difficult part for most of you. The adjoint method is okey, though it's slower than Gauss-Jordan. You need a general method to compute matrix determinant to deal with matrices larger than 3x3. If you have problem to implement Gauss-Jordan all by your self, you can adapt someone else's code. A good starting point is the code from Numerical Recipes. Note that we are doing inversion in Zn, not in R. But that's not really an issue. You just change the regular +,-,*,/ operations to those in Zn. Some of you used a regular division in their Gauss-Jordan implementations and complained not getting whole numbers. Of course not. You should do the division in Z26. In other words, a/b is in fact a * b^{-1}, where b^{-1} is the multiplicative inverse of b in Z26. The same thing if you use the adjoint method. If the determinant you computed is not zero, doesn't mean the matrix is invertible. The determinant must have multiplicative inverse (So, if the determinant is an even number or a multiple of 13, the matrix is not invertible). Here are a few points to clear some confusion around Gauss-Jordan:
  1. You do need full pivoting. Consider the following matrix

     12 1
     13 2
     

     with only row pivoting, we can't find a pivot.
  2. There is not numerical stability in our version whatsoever. In R, if the pivot element is small, say, 1e-20, there's numerical concern. But in Zn, we are fine.
• Now that you have a way to do matrix inversion, you can do known plain text attack. You should come up with a strategy to find an invertible matrix composed by plain text. One simple way is to slide across the plain text and pick up m m-substrings, m being the block size of the Hill cipher.
• If you have the matrix inversion work right, the extra credit part (5x5 key matrix) shouldn't be hard.
• The difficult part of this project is the cipher text only attack. Even for known block size, 3x3 in our case, it's not easy. Again, it's easy in theory. But to actaully break some code, you need some work. The trigram attack is probably our own weapon. However, among all comman trigrams, 'the' is the only stable one, in the sense that it'll (almost) always appear. So you can safely associate the most frequent trigram in the cipher text to 'the'. For all other trigrams, it's not guaranteed they are in the order of standard English statistics. E.g., the second most frequent trigram might not correspond to 'ing'. In fact, what 'ing' was encrypted may not appear in the cipher text at all. The 'the' case puts constraints to the 3x3 key matrix. Now the size of the key space is reduced from 26^9 to 26^6, which is about 3 billion and still a very large number. So we need other heuristics. One is that no row/column can be all even numbers. Yet no matter how many heuristics we apply, we still have many admissible keys. Each key will produce a plain text. Of course, most will be gibberish. So we need an automatic way to sift through the produced plain text and only check the more sensible pieces.
• So we need a program to tell us if a given string is sensible English text or not. This is something many of you want since the first project. We can do this, without linguistic knowledge at all. Just use the statistics of English. Find the statistics of the given string, compare it with the standard statistics of English. If the two match, there's a good chance that the string is some sensible English. Now here's what you do. The statistics of uni-, di- and tri-gram define a vector. We can compute this vector for the string. That is, we count the frequency of, e.g., 'at' or 'the' in the string. Once we have this vector, we can compute the similarity to the reference vector defined by standard statistics. The angle between the two vectors give us the similarity. We know how to calcuate the cosine of the angle between two vectors, don't we? The cosine of the angle is also know as normalized correlation of the two vectors. It's a value between 0 and 1. The closer the correlation is to 1, the more similar the two vectors. I show here some code for your convenience. The code is in C++. The same task can be done in Perl much more easily (try it as a practice). It works very well for such a simple program. 0.9 is about the threshold, i.e., if we feed in a piece of English text, it'll return a value bigger than 0.9. If we instead input some random bits, we usually get much lower values (less than 0.8).