Programming Praxis

The Hill Cipher was invented by Lester Hill in 1929. A block cipher based on modular matrix multiplication, it was rather advanced for its time. The diffusion inherent in the algorithm makes it difficult to break manually, though it is easy to work back to the key if you have some known plaintext.

The Hill Cipher uses arithmetic, so you will need to convert the alphabetic plaintext to numbers using a polybius square, a straddling checkboard, or the simple expedient of mapping A to 0, B to 1, and so on, until Z is 25, which we will adopt here. Our alphabet has 26 characters, which can be a problem since 26 = 2 × 13 is composite; the alphabet size becomes the modulus of the cipher system, and some keys won’t work, though it is easy to find keys that do. If you’re worried, add characters to the alphabet until it has a prime number of elements; for instance, you might choose a 29-character alphabet with the letters A to Z, a space character, a period, and a slash for a digit shift.

Let’s look at an example. We will send the message PROGRAMMINGPRAXIS with blocksize 3. The plaintext is padded with a Z, forming a 6 × 3 matrix:

    P R O   15 17 14
    G R A    6 17  0
P = M M I = 12 12  8
    N G P   13  6 15
    R A X   17  0 23
    I S Z    8 18 25

We must choose a key that is invertible; that is, a key that has an inverse (some textbooks call such keys non-singular). For a normal matrix to be invertible, the discriminant must be non-zero. Since we are using modular arithmetic instead of normal integer arithmetic, we have the additional requirement that the determinant and modulus must be coprime. If the first key you choose doesn’t work, try another. The key that we choose, and its mod 26 inverse, are:

    G Y B    6 24  1               8  5 10   I F K
K = N Q K = 13 16 10    inverse = 21  8 21 = V I V
    U R P   20 17 15              21 12  8   V M I

Encryption is performed by modular matrix multiplication, with C = P × K (mod 26):

    15 17 14              19 12  5   T M F
     6 17  0    6 24  1   23  0 23   X A U
C = 12 12  8 * 13 16 10 = 24 18 18 = Y S S
    13  6 15   20 17 15   14 13 12   O N M
    17  0 23              16 19 24   Q T Y
     8 18 25               2 21 17   C V R

So the ciphertext is TMFXAUYSSONMQTYCVR.

Decryption is also performed by modular matrix multiplication, with P = C × K_inv (mod 26):

    19 12  5              15 17 14   P R O
    23  0 23    8  5 10    6 17  0   G R A
P = 24 18 18 * 21  8 21 = 12 12  8 = M M I
    14 13 12   21 12  8   13  6 15   N G P
    16 19 24              17  0 23   R A X
     2 21 17               8 18 25   I S Z

Your task is to write a program that performs encryption and decryption using the Hill Cipher. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2