Attacking Letter Substitution Ciphers with Integer Programming
Sujith Ravi, Kevin K. Knight · Cryptologia · 2009
We introduce a method for solving substitution ciphers using low-order letter n-gram models. This method enforces global constraints using integer programming, and it guarantees that no decipherment key is overlooked. We carry out extensive empirical experiments showing how decipherment accuracy varies as a function of cipher length and n-gram order. We also make an empirical investigation of Shannon's [12 Shannon , C. E. 1949 . “Communication Theory of Secrecy Systems,” Bell System Technical Journal , 28 : 656 – 715 .[Crossref] , [Google Scholar]] theory of uncertainty in decipherment.