Noor R. Al-Kazaz
School of Computer Science, Bangor University, Bangor, UK
Sean A. Irvine
Real Time Genomics, Hamilton, New Zealand
William J. Teahan
School of Computer Science, Bangor University, Bangor, UK
Download article
Published in: Proceedings of the 1st International Conference on Historical Cryptology HistoCrypt 2018
Linköping Electronic Conference Proceedings 149:21, p. 115-124
NEALT Proceedings Series 34:21, p. 115-124
Published: 2018-06-13
ISBN: 978-91-7685-252-1
ISSN: 1650-3686 (print), 1650-3740 (online)
This paper introduces a new compression-based approach to the automatic cryptanalysis of Playfair ciphers. More specifically, it shows how the Prediction by Partial Matching (‘PPM’) data compression model, 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 very short Playfair ciphers with no probable word. Our new method is the result of an efficient combination between data compression and simulated annealing. The method has been tried on a variety of cryptograms with different lengths (starting from 60 letters) and a substantial majority of these ciphers are solved rapidly without any errors with 100% of ciphers of length over 120 being solved. In addition, as the spaces are omitted from the ciphertext traditionally, we have also tried a compression-based approach in order to achieve readability by adding spaces automatically to the decrypted texts. The PPM compression model is used again to rank the solutions and almost all the decrypted examples were effectively segmented with a low average number of errors. Furthermore, we have also been able to break a Playfair cipher for a 6×6 grid using our method.
Noor R Al-Kazaz, Sean A Irvine, and William J Teahan. 2016. An automatic cryptanalysis of transposition ciphers using compression. In Int. Conference on Cryptology and Network Security, pages 36–52.
Springer, Springer Int. Publishing. Timothy C Bell, John G Cleary, and Ian H Witten. 1990. Text compression. Prentice-Hall, Inc.
John Cleary and Ian Witten. 1984. Data compression using adaptive coding and partial string matching. IEEE Transactions on Communications, 32(4):396–402.
Michael J Cowan. 2008. Breaking short playfair ciphers with the simulated annealing algorithm. Cryptologia, 32(1):71–83.
Dalal Abdulmohsin Hammood. 2013. Breaking a playfair cipher using memetic algorithm. Journal of Engineering and Development, 17(5).
Swati Hans, Rahul Johari, and Vishakha Gautam. 2014. An extended playfair cipher using rotation and random swap patterns. In Computer and Communication Technology (ICCCT), 2014 International Conference on, pages 157–160. IEEE.
Paul Glor Howard. 1993. The design and analysis of efficient lossless data compression systems. Ph.D. thesis, Brown University, Providence, Rhode Island.
Sean A Irvine. 1997. Compression and cryptology. Ph.D. thesis, University of Waikato, New Zealand.
Richard E Klima and Neil P Sigmon. 2012. Cryptology: classical and modern with maplets. CRC Press.
Vladimir I Levenshtein. 1966. Binary codes capable of correcting deletions, insertions, and reversals. In Soviet physics doklady, volume 10, pages 707–710.
James Lyons. 2012. Cryptanalysis of the playfair cipher. http://practicalcryptography.com/cryptanalysis/stochastic-searching/cryptanalysis-playfair/.
Joseph Oswald Mauborgne. 1914. An advanced problem in cryptography and its solution. Fort Leavenworth, Kansas: Leavenworth Press.
Packirisamy Murali and Gandhidoss Senthilkumar. 2009. Modified version of playfair cipher using linear feedback shift register. In Information Management and Engineering, 2009. ICIME’09. International Conference on, pages 488–490. IEEE.
G Negara. 2012. An evolutionary approach for the playfair cipher cryptanalysis. In Proc. of the Int. Conference on Security and Management (SAM), page 1. The Steering Committee of The World Congress in Computer Science, Computer Engineering and Applied Computing (WorldComp).
K Ravindra Babu, S Uday Kumar, A Vinay Babu, IVN S Aditya, and P Komuraiah. 2011. An extension to traditional playfair cryptographic method. International Journal of Computer Applications, 17(5):34–36.
Benjamin Rhew. 2003. Cryptanalyzing the playfair cipher using evolutionary algorithms. Available: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.129.4325&rep=rep1&type=pdf.
Laurence Dwight Smith. 1955. Cryptography: The science of secret writing. Courier Corporation.
Shiv Shakti Srivastava and Nitin Gupta. 2011. Security aspects of the extended playfair cipher. In Communication Systems and Network Technologies (CSNT), 2011 International Conference on, pages 144–147. IEEE.
Jan Stumpel. 2017. Fast playfair programs. www.jw-stumpel.nl/playfair.html. last accessed December 13, 2017.
William J Teahan and John G Cleary. 1996. The entropy of English using PPM-based models. In Data Compression Conference, 1996. DCC’96. Proceedings, pages 53–62. IEEE.
William J Teahan. 1998. Modelling English text. Ph.D. thesis, University of Waikato, New Zealand.
