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

2 Responses to “Hill Cipher”

  1. Paul said

    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

    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 Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: