Paper 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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Hill cipherciphertext-only attackclassical ciphersChinese Remainder Theorementropyredundancy
Contact author(s)
siavashaaa32002 @ yahoo com
History
2015-08-10: received
Short URL
https://ia.cr/2015/802
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/802,
      author = {Shahram Khazaei and Siavash Ahmadi},
      title = {Ciphertext-only attack on d*d Hill in O(d13^d)},
      howpublished = {Cryptology ePrint Archive, Paper 2015/802},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/802}},
      url = {https://eprint.iacr.org/2015/802}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.