Article | Proceedings of the 1st International Conference on Historical Cryptology HistoCrypt 2018 | Hidden Markov Models for Vigenère Cryptanalysis Linköping University Electronic Press Conference Proceedings
Göm menyn

Title:
Hidden Markov Models for Vigenère Cryptanalysis
Author:
Mark Stamp: Department of Computer Science, San Jose State University, San Jose, California, USA Fabio Di Troia: Department of Computer Science, San Jose State University, San Jose, California, USA Miles Stamp: Los Gatos High School, Los Gatos, California, USA Jasper Huang: Lynbrook High School, San Jose, California, USA
Download:
Full text (pdf)
Year:
2018
Conference:
Proceedings of the 1st International Conference on Historical Cryptology HistoCrypt 2018
Issue:
149
Article no.:
011
Pages:
39-46
No. of pages:
8
Publication type:
Abstract and Fulltext
Published:
2018-06-13
ISBN:
978-91-7685-252-1
Series:
Linköping Electronic Conference Proceedings
ISSN (print):
1650-3686
ISSN (online):
1650-3740
Publisher:
Linköping University Electronic Press, Linköpings universitet


Export in BibTex, RIS or text

Previous work has shown that hidden Markov models (HMM) can be effective for the cryptanalysis of simple substitution and homophonic substitution ciphers. Although computationally expensive, an HMM-based attack that employs multiple random restarts can offer a significant improvement over classic cryptanalysis techniques, in the sense of requiring less ciphertext to recover the key. In this paper, we show that HMMs are also applicable to the cryptanalysis of the well-known Vigenère cipher. We compare and contrast our HMM-based approach to recent research that uses Vigenère cryptanalysis to supposedly illustrate the strength of a type of neural network known as a generative adversarial network (GAN). In the context of Vigenère cryptanalysis, we show that an HMM can succeed with much less ciphertext than a GAN, and we argue that the model generated by an HMM is considerably more informative than that produced by a GAN.

Proceedings of the 1st International Conference on Historical Cryptology HistoCrypt 2018

Author:
Mark Stamp, Fabio Di Troia, Miles Stamp, Jasper Huang
Title:
Hidden Markov Models for Vigenère Cryptanalysis
References:

Taylor Berg-Kirkpatrick and Dan Klein. 2013. Decipherment with a million random restarts. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, pages 874–878.

Robert L. Cave and Lee P. Neuwirth. 1980. Hidden Markov models for English. In J. D. Ferguson, editor, Hidden Markov Models for Speech, IDA-CRD, Princeton, NJ, October 1980, pages 16–56. https://www.cs.sjsu.edu/~stamp/RUA/CaveNeuwirth/index.html.

W. Nelson Francis and Henry Kucera. 1969. The Brown Corpus: A standard corpus of present-day edited American English. http://www.nltk.org/nltk_data/.

William F. Friedman. 1987. The Index of Coincidence and Its Applications in Cryptography. Aegean Park Press.

Aidan N. Gomez, Sicong Huang, Ivan Zhang, Bryan M. Li, Muhammad Osama, and Lukasz
Kaiser. 2018. Unsupervised cipher cracking using discrete GANs. https://arxiv.org/abs/1801.04883.

Thomas Jakobsen. 1995. A fast method for the cryptanalysis of substitution ciphers. Cryptologia, 19:265–274.

Friedrich W. Kasiski. 1863. Die Geheimschriften und die Dechiffrirkunst (Cryptography and the Art of Decryption). Mittler und Sohn, Berlin. http://pages.mtu.edu/~shene/NSF-4/Tutorial/VIG/Vig-Kasiski.html.

Dar-Shyang Lee. 2002. Substitution deciphering based on HMMs with applications to compressed document processing. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(12):1661–1666, December.

Lawrence R. Rabiner. 1989. A tutorial on hidden Markov models and selected applications in speech recognition. Proceedings of the IEEE, 77(2):257–286.

Mark Stamp. 2004. A revealing introduction to hidden Markov models. https://www.cs.sjsu.edu/~stamp/RUA/HMM.pdf.

Rohit Vobbilisetty, Fabio Di Troia, Richard M. Low, Corrado Aaron Visaggio, and Mark Stamp. 2017. Classic cryptanalysis using hidden Markov models. Cryptologia, 41(1):1–28.

WingWong and Mark Stamp. 2006. Hunting for metamorphic engines. Journal in Computer Virology, 2(3):211–229.

Proceedings of the 1st International Conference on Historical Cryptology HistoCrypt 2018

Author:
Mark Stamp, Fabio Di Troia, Miles Stamp, Jasper Huang
Title:
Hidden Markov Models for Vigenère Cryptanalysis
Note: the following are taken directly from CrossRef
Citations:
No citations available at the moment


Responsible for this page: Peter Berkesand
Last updated: 2019-11-06