Florent Dewez
INRIA, Modal team-project, Lille-Nord Europe research center, France
Valentin Montmirail
Universite Cote dAzur, I3S, CNRS, Nice, France
Download article
Published in: Proceedings of the 2nd International Conference on Historical Cryptology, HistoCrypt 2019, June 23-26, 2019, Mons, Belgium
Linköping Electronic Conference Proceedings 158:2, p. 13-22
NEALT Proceedings Series 37:2, p. 13-22
Published: 2019-06-12
ISBN: 978-91-7685-087-9
ISSN: 1650-3686 (print), 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.
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.
