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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.