Search

The Hill cipher, also known as matrix encryption, is a polygraphic substitution cipher, developed by the mathematician Lester S. Hill in 1929. While various attacks had been known on the Hill cipher, the ciphertext-only attack without assumptions about the encryption matrix or probable plaintext words was introduced only recently by Bauer and Millward. They obtained high efficiency of attack by recovering the decryption matrix row by row rather than all rows at once. In this paper, we extend their ciphertext-only attack in two ways. First, we present a better scoring system for cryptanalysis based on the goodness-of-fit statistics. Specifically, we reduce the average number of candidate rows from 24.83 to 7.00 for 3 × 3 matrix and from 4027.78 to 1220.38 for 4 × 4 matrix. Second, we show how to apply our attacks to the Hill cipher without knowing the numeric equivalents of the letters of the plaintexts.

This paper presents a non-numerical polygraphic substitution cipher which appears more efficient than Hill's algebraic system. For instance, by using the same number of “operations” per message as a 6-graphic algebraic substitution cipher, the present cipher can achieve 4096-graphic substitution. Less dramatically, a 16-graphic application of the present cipher requires only one-eighth as many operations as a 16-graphic algebraic cipher. The source of the greater efficiency of the proposed cipher is that the number of letters which can be jointly enciphered is exponential, rather than linear, with respect to the number of operations performed.