Cracking Hill Ciphers with Goodness-of-Fit Statistics

Abstract

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 3x3 matrix and from 4027.78 to 1220.38 for 4x4 matrix. Second, we show how to apply our attacks to the Hill cipher without knowing the numeric equivalents of the letters of the plaintexts.