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

Florent Dewez 1 Valentin Montmirail 2
1 MODAL - MOdel for Data Analysis and Learning
Inria Lille - Nord Europe, LPP - Laboratoire Paul Painlevé - UMR 8524, CERIM - Santé publique : épidémiologie et qualité des soins-EA 2694, Polytech Lille - École polytechnique universitaire de Lille, Université de Lille, Sciences et Technologies
Abstract : 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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

https://hal.univ-cotedazur.fr/hal-02271395
Contributor : Valentin Montmirail <>
Submitted on : Monday, August 26, 2019 - 5:39:00 PM
Last modification on : Wednesday, August 28, 2019 - 1:18:55 AM

File

ecp19158002.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02271395, version 1

Collections

Citation

Florent Dewez, Valentin Montmirail. Decrypting the Hill Cipher via a Restricted Search over the Text-Space. Proceedings of the 2nd International Conference on Historical Cryptology, HistoCrypt 2019, June 23-26, 2019, Mons, Belgium, 2019. ⟨hal-02271395⟩

Share

Metrics

Record views

33

Files downloads

27