Hill Cipher
May 26, 2017
We begin by modifying the matrix operations of previous exercises to work using modular arithmetic; if you are interested in how these work, refer to the previous exercises:
(define (inverse x m) ; inverse of x (mod m)
(let loop ((x x) (a 0) (b m) (u 1))
(if (zero? x)
(if (= b 1) (modulo a m) 0)
(let ((q (quotient b x)))
(loop (modulo b x) u x
(modulo (- a (* q u)) m))))))
(define (matrix-map f a)
(let ((r (matrix-rows a))
(c (matrix-cols a)))
(let ((b (make-matrix r c)))
(for (i r)
(for (j c)
(matrix-set! b i j
(f (matrix-ref a i j)))))
b)))
(define (matrix-multiply-modulo a b m) (define (modm n) (modulo n m)) (matrix-map! modm (matrix-multiply a b)))
(define (matrix-inverse-modulo a m)
(define (modm n) (modulo n m))
(matrix-map! modm
(matrix-scalar-multiply
(inverse (modulo (matrix-determinant a) m) m)
(matrix-transpose (matrix-cofactors a)))))
Next we write functions that convert between text strings and numeric matrices, in both directions:
(define (c->i c) (- (char->integer (char-upcase c)) 65))
(define (i->c i) (integer->char (+ i 65)))
(define (string->matrix str blocksize)
(let* ((len (string-length str))
(rows (ceiling (/ len blocksize)))
(m (make-matrix rows blocksize #\Z)))
(for (k len)
(let ((i (quotient k blocksize))
(j (remainder k blocksize)))
(matrix-set! m i j (string-ref str k))))
m))
(define (matrix->string m)
(let ((r (matrix-rows m))
(c (matrix-cols m)))
(let ((cs (list)))
(for (i r)
(for (j c)
(set! cs (cons (matrix-ref m i j) cs))))
(list->string (reverse cs)))))
All that’s left is functions that perform encryption and decryption:
(define (encrypt str key blocksize modulus)
(matrix->string
(matrix-map i->c
(matrix-multiply-modulo
(matrix-map c->i (string->matrix str blocksize))
(matrix-map c->i (string->matrix key blocksize))
modulus))))
(define (decrypt str key blocksize modulus)
(matrix->string
(matrix-map i->c
(matrix-multiply-modulo
(matrix-map c->i (string->matrix str blocksize))
(matrix-inverse-modulo
(matrix-map c->i (string->matrix key blocksize))
modulus)
modulus))))
Here is our example, with blocksize 3 and modulus 26:
> (encrypt "PROGRAMMINGPRAXIS" "GYBNQKURP" 3 26) "TMFXAUYSSONMQTYCVR" > (decrypt "TMFXAUYSSONMQTYCVR" "GYBNQKURP" 3 26) "PROGRAMMINGPRAXISZ"
You can run the program at http://ideone.com/Cf9pZq, where you will also see the contributions from previous exercises.
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]