The two-message problem in the Hill cryptographic system with unknown cipher alphabet

The Hill two-message Problem assumes given two ciphertexts obtained by the encipherment of a single plaintext by two different key matrices K 1, K 2. The problem is to determine the (unknown) K 1, K 2 and the cipher alphabet if unknown. Levine and Brawley (Journal fur die reine und angewandte Mathematik 224 (1966): 20–43; 227 (1967): 1–24) and Nance (Doctoral dissertation, N. C. State University) analyzed this problem for the case in which the cipher alphabet is known. In this paper we continue with the problem and consider the (more difficult) case in which the cipher alphabet is unknown. The method used depends in part on some results obtained by Levine and Chandler (Cryptologia 13: 1–28) which determine the matrix A=K 1 K 2. The basic equation AXA=X is then solved for matrix X by use of the row-reduced echelon form of the system of linear equations in the unknown elements of X, the key matrices being among these solutions.