An automatic cryptanalysis of simple substitution ciphers using compression

Research output: Contribution to journalArticle

Electronic versions

Documents

DOI

Automatic recognition of correct solutions as a result of a ciphertext only attack of simple ciphers is not a trivial issue and still remains a taxing problem. A new compression based method for the automatic cryptanalysis of simple substitution ciphers is introduced in this paper. In particular, this paper presents how a Prediction by Partial Matching (PPM) text compression scheme, a method that shows a high level of performance when applied to different natural language processing tasks, can also be used for the automatic decryption of simple substitution ciphers. Experimental results showed that approximately 92% of the cryptograms were decrypted correctly without any errors and 100% with just three errors or less. Extensive investigations are described in this paper, in order to determine which is the most appropriate type of PPM scheme that can be applied to the problem of automatically breaking substitution ciphers. This paper shows how a new character-based PPM variant significantly outperforms other schemes including the standard Gzip and Bzip2 compression schemes. We also apply a word-based variant which when combined with the character-based method leads to further improved results.
Original languageEnglish
Pages (from-to)57-75
JournalInformation Security Journal: A Global Perspective
Volume27
Issue number1
Early online date25 Jan 2018
DOIs
Publication statusPublished - 2018

Total downloads

No data available
View graph of relations