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.
Advertisements
Pages: 1 2
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]