ICTCM 12  •  Burlingame, CA, 1999

The Cracking Theorem

Suppose the alphabet length m is prime.  Let (Subscript[p, 1]), (Subscript[p, 2]), …, (Subscript[p, n ])be n plaintext vectors for a Hill n-cipher having (unknown) key matrix A and let (Subscript[c, 1]), (Subscript[c, 2]), …, (Subscript[c, n ])be the corresponding ciphertext vectors.
Suppose these plaintext vectors are linearly independent.  Form the matrices
P = [(Subscript[p, 1])| (Subscript[p, 2]) | ⋯| (Subscript[p, n ])]  and  C = [(Subscript[c, 1])| (Subscript[c, 2]) | ⋯| (Subscript[c, n ])]
having the plaintext vectors and ciphertext vectors, respectively, as their columns.
Then the same sequence of elementary row operations that reduces (C^T)to the identity matrix reduces (P^T) to the transpose ((((A^(-1))))^T) of the inverse key matrix (A^(-1)).

Solution to 4

Copyright © 1999 by Murray Eisenberg