hillcipher.py

import math

import numpy as np


M = 26
dim = 3


# Generate a random encryption matrix. It might turn out to be unusable.
Ke = np.random.randint(0, M-1, size=(dim,dim))

# Check that the encryption matrix is invertible over the finite field. If so,
# find the inverse of the determinant.
Ke_det = int(round(np.linalg.det(Ke)))
assert math.gcd(M, Ke_det) == 1  # det has a multiplicative inverse mod M
Ke_det_inv = pow(Ke_det, -1, M)

# Find the adjugate of the encryption matrix
Ke_adj = (Ke_det * np.linalg.inv(Ke)).round().astype(int)

# Find the decryption matrix
Kd = (Ke_det_inv * Ke_adj) % M


# Evaluate
encrypt = lambda m: (Ke @ m) % M
decrypt = lambda m: (Kd @ m) % M

test = np.random.randint(0, M-1, size=dim)
assert np.array_equal(decrypt(encrypt(test)), test)


# Try to solve for the encryption key, creating system of linear equations from
# a handful of known (plaintext, ciphertext) associations:
#
#     Ke @ P = C  mod M
#     Ke = Ke @ P @ inv(P) = C @ inv(P)  mod M
P = np.random.randint(0, M-1, size=(dim,dim))  # arranged in columns
C = np.apply_along_axis(encrypt, axis=0, arr=P)

# Same steps as finding Ke above
P_det = int(round(np.linalg.det(P)))
P_det_inv = pow(P_det, -1, M)
P_inv = (P_det_inv * P_det * np.linalg.inv(P)).round().astype(int) % M

# Solve for Ke again
Ke_prime = (C @ P_inv) % M
assert np.array_equal(Ke, Ke_prime)