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

### 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))) % 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]
```