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.
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.