Hill Cipher
May 26, 2017
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 × Kinv (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.
Programming Praxis 
In Python using the LU decomposition from last exercise. The results are the same as from Programming Praxis.
def matconst(A, m): return [[round(ai*m) for ai in row] for row in A] def matmod(A, m): return [[ai % m for ai in row] for row in A] def matconstmod(A, x, mod): return [[round(ai*x) % mod for ai in row] for row in A] def mod_inv(A, m): LU, P = lu_decompose(A) det = round(lu_determinant(LU, P)) Ai = lu_invert(LU, P) Aid = matconstmod(Ai, det, m) mi = modular_div(1, det, m) return matconstmod(Aid, mi, m) def matmulmod(A, B, mod): AB = matmul(A, B) return matmod(AB, mod) def txt_nums(txt, chars=string.ascii_uppercase): it = iter(chars.index(t) for t in txt) return [list(c) for c in zip_longest(it, it, it, fillvalue=len(chars)-1)] def nums_txt(nums, chars=string.ascii_uppercase): return "".join(chars[i] for i in sum(nums, [])) E = [[6, 24, 1], [13, 16, 10], [20, 17, 15]] # encryption key D = mod_inv(E, 26) # decryption key txt = "PROGRAMMINGPRAXIS" nums = txt_nums(txt) enc = matmulmod(nums, E, 26) dec = matmulmod(enc, D, 26) print(nums) print(enc) print(nums_txt(enc)) print(dec) print(nums_txt(dec))Another method to get the modular inverse of the encryption matrix is to use a Gaussian elimination process. First add an identity matrix as extra columns (gives n rows by 2n columns matrix B. Then make element B[i][i] equal to one by multiplying row i by the modular inverse of B[i][i]. Then subtract row i from the other rows to make the rest of column i zero. After doing this for all rows the end result is an identity matrix in columns [0, n-1] and the inverted matrix in columns [n, 2n-1]. This method only works if for all numbers x in the matrix gcd(x, mod) == 1, so mod has to be a prime.
def extended_gcd(a, b): """Return (r, s, d) where a*r + b*s = d and d = gcd(a,b)""" x, y = 0, 1 lastx, lasty = 1, 0 while b: a, (q, b) = b, divmod(a, b) x, lastx = lastx - q * x, x y, lasty = lasty - q * y, y return (lastx, lasty, a) def modular_div(a, b, n): """Return a/d (mod n) assuming gcd(b,n) = 1""" return (a * (extended_gcd(b, n)[0])) % n def mod_inv(A, mod): n = len(A) B = [A[i] + [int(i==j) for j in range(n)] for i in range(n)] for i in range(n): fac = modular_div(1, B[i][i], mod) B[i] = [(fac*bik) % mod for bik in B[i]] for j in range(n): if i==j: continue fac = -B[j][i] % mod B[j] = [(fac*bik+bjk) % mod for bjk, bik in zip(B[j], B[i])] return [bi[n:] for bi in B]