Decrypting the Hill Cipher via a Restricted Search over the Text-Space

Florent Dewez
INRIA, Modal team-project, Lille-Nord Europe research center, France

Valentin Montmirail
Universite Cote dAzur, I3S, CNRS, Nice, France

Ladda ner artikel

Ingår i: Proceedings of the 2nd International Conference on Historical Cryptology, HistoCrypt 2019, June 23-26, 2019, Mons, Belgium

Linköping Electronic Conference Proceedings 158:2, s. 13-22

NEALT Proceedings Series 37:2, s. 13-22

Visa mer +

Publicerad: 2019-06-12

ISBN: 978-91-7685-087-9

ISSN: 1650-3686 (tryckt), 1650-3740 (online)


Developed by L. S. Hill in 1929, the Hill cipher is a polygraphic substitution cipher based on matrix multiplication. This cipher has been proved vulnerable to many attacks, especially the known-plaintext attack, while only few ciphertext-only attacks have been developed. The aim of our work is to study a new kind of ciphertext-only attack for the Hill cipher which is based on a restricted search over an explicit set of texts, called orbits, and not on a search over the key-space; it is called Orbit-Based Attack (OBA). To explain in a convenient setting this approach, we make use of basic notions from group action theory; we present then in details an algorithm for this attack and finally results from experiments. We demonstrate experimentally that this new method can be efficient in terms of time-execution and can even be faster on average than the classical Brute-Force Attack in the considered settings.


Hill Cipher Group Action Theory Experiments Ciphertext-only Attack


Michael Artin. 2011. Algebra, volume 2. Pearson Prentice Hall, Advanced Mathematics Series edition.

Craig P. Bauer and Katherine Millward. 2007. Cracking Matrix Encryption Row by Row. Cryptologia, 31(1):76-83.

Gene H. Golub and Charles F. Van Loan. 2012. Matrix computations, volume 3. JHU Press.

Lester Sanders Hill. 1929. Cryptography in an Algebraic Alphabet. The American Mathematical Monthly, 36(6):306-312.

Lester Sanders Hill. 1931. Concerning Certain Linear Transformation Apparatus of Cryptography. The American Mathematical Monthly, 38:135-154.

I. A. Ismail, Mohammed Amin, and Hossam Diab. 2006. How to Repair the Hill Cipher. Journal of Zhejiang University-Science A, 7(12):2022-2030, Dec.

Shahram Khazaei and Siavash Ahmadi. 2017. Ciphertext-only Attack on d X d Hill in O(d X 13d). Inf. Process. Lett., 118:25-29.

Tom Leap, Tim McDevitt, Kayla Novak, and Nicolette Siermine. 2016. Further Improvements to the Bauer-Millward Attack On the Hill Cipher. Cryptologia, 40(5):452-468.

Ahmed Y. Mahmoud and Alexander G. Chefranov. 2009. Hill Cipher Modification Based on Eigenvalues HCM-EE. In Proc. of SIN’09, pages 164-167.

Tim McDevitt, Jessica Lehr, and Ting Gu. 2018. A parallel time-memory tradeoff attack on the hill cipher. Cryptologia, 42(5):408-426.

Jeffrey Overbey, William Traves, and Jerzy Wojdylo. 2005. On the Keyspace of the Hill Cipher. Cryptologia, 29(1):59-72.

Christos H. Papadimitriou. 1994. Computational complexity. Addison-Wesley.

J. Rotman. 1965. The Theory of Groups. Boston: Allyn and Bacon.

Jonathan D.H. Smith. 2008. Introduction to Abstract Algebra. Textbooks in Mathematics. Chapman and Hall/CRC.

Douglas Stinson. 2002. Cryptography: Theory and Practice. CRC/C&H, second edition.

Mohsen Toorani and Abolfazl Falahati. 2009. A Secure Variant of the Hill Cipher. In Proc. of 14th IEEE Symposium on Computers and Communications (ISCC’09), pages 313-316.

Mohsen Toorani and Abolfazl Falahati. 2011. A Secure Cryptosystem Based on Affine Transformation. Security and Communication Networks, 4(2):207-215.

Samuel S. Wagstaff. 2002. Cryptanalysis of Number Theoretic Ciphers. CRC Press, Inc., Boca Raton, FL, USA.

Dae Hyun Yum and Pil Joong Lee. 2009. Cracking Hill Ciphers with Goodness-of-Fit Statistics. Cryptologia, 33(4):335-342.

Citeringar i Crossref