The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
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,

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 

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

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.