Associated Topics || Dr. Math Home || Search Dr. Math

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/
```
Associated Topics:
College Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search