Hill Cypher

Date: 03/19/2001 at 11:03:48
From: Peter D'Amore
Subject: Encryption "Hill Cypher"

I'm struggling with a math problem and I hope you may be able to help 
me figure it out or steer me in the right direction.  Thanks!

I need to find out what the Hill Cypher is.  I haven't been able to 
find much information on it. Once I know what it is, I need to decode 
the Hill Cypher by finding the inverse of a matrix with all its 
elements in mod n arithmetic. Can this even be done?  I have to prove 
it is not possible or show how it can be done.

I can't thank you enough for taking the time to try to help me.
Thanks again,
Pete

Date: 03/19/2001 at 13:48:08
From: Doctor Rob
Subject: Re: Encryption "Hill Cypher"

Thanks for writing to Ask Dr. Math, Peter.

The Hill Cypher uses a k-by-k matrix M with entries modulo n. The
plain text P is expressed as a column vector of length k whose entries 
are integers modulo n. Then the cypher text C is obtained by matrix 
multiplication

   C = M*P.

It, too, will be a column vector of length k of integers modulo n.

To decode, you need

   P = M^(-1)*C.

That means that the matrix M must be invertible. That happens if and
only if det(M) is relatively prime to n. To find the inverse, use your 
favorite algorithm to invert M as a matrix with integer entries. 
Reduce the resulting matrix modulo n, either at the end, or as you
go. Some denominators may appear, but instead of dividing by them,
multiply by their inverses mod n, which will always exist.

The matrix M is kept secret, and used by the encoder. The matrix
M^(-1) is also kept secret, and used by the decoder. If both parties
encode and decode, then both need to have both matrices.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/