Cryptology ePrint Archive: Report 2015/802

Ciphertext-only attack on d*d Hill in O(d13^d)

Shahram Khazaei and Siavash Ahmadi

Abstract: Hill is a classical cipher which is generally believed to be resistant against ciphertext-only attack. In this paper, by using a divide-and-conquer technique, it is first shown that Hill with d*d key matrix over Z_26 can be broken with computational complexity of O(d26^d), for the English language. This is much less than the only publicly known attack, i.e., the brute-force with complexity of O(d^3(26)^(d^2)). Then by using the Chinese Remainder Theorem, it is shown that the computational complexity of the proposed attack can be reduced to O(d13^d). Using an information-theoretic approach, supported by extensive simulation results, it is shown that the minimum ciphertext length required for a successful attack increases by a factor of about 7 and 9.8, respectively for these two attacks in comparison with the brute-force attack. This is the only serious attack on Hill since its invention in 1929.

Category / Keywords: secret-key cryptography / Hill cipher, ciphertext-only attack, classical ciphers, Chinese Remainder Theorem, entropy, redundancy

Date: received 10 Aug 2015

Contact author: siavashaaa32002 at yahoo com

Available format(s): PDF | BibTeX Citation

Version: 20150810:183233 (All versions of this report)

Short URL: ia.cr/2015/802

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]