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.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
2 Comments »

2 Responses to “Hill Cipher”

  1. Paul said
    May 26, 2017 at 11:54 AM

    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))
  2. Paul said
    May 28, 2017 at 4:56 AM

    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]

Leave a comment