Solving Historical Dictionary Codes with a Neural Language Model

Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, pages 5845–5854, November 16–20, 2020. c⃝2020 Association for Computational Linguistics 5845 Solving Historical Dictionary Codes with a Neural Language Model Christopher Chu, Raphael Valenti, and Kevin Knight DiDi Labs 4640 Admiralty Way Marina del Rey, CA 90292 {chrischu,kevinknight}@didiglobal.com Abstract We solve difficult word-based substitution codes by constructing a decoding lattice and searching that lattice with a neural language model. We apply our method to a set of enciphered letters exchanged between US Army General James Wilkinson and agents of the Spanish Crown in the late 1700s and early 1800s, obtained from the US Library of Congress. We are able to decipher 75.1% of the cipher-word tokens correctly. 1 Introduction Cryptography has been used since antiquity to en- code important secrets. There are many unsolved ciphers of historical interest, residing in national libraries, private archives, and recent corpora col- lection projects (Megyesi et al., 2019; Pettersson and Megyesi, 2019). Solving classical ciphers with automatic methods is a needed step in ana- lyzing these materials. In this work, we are concerned with automatic algorithms for solving a historically-common type of book code, in which word tokens are systemat- ically replaced with numerical codes. Encoding and decoding are done with reference to a dic- tionary possessed by both sender and recipient. While this type of code is common, automatic de- cipherment algorithms do not yet exist. The con- tributions of our work are: • We develop a algorithm for dictionary-based substitution codes.solving The algorithm uses a known-plaintext attack (ex- ploiting small samples of decoded material), a neural language model, and beam search. • We apply our algorithm to decipher previously-unread messages exchanged between US Army General James Wilkinson and agents of the Spanish Crown in the late 1700s and early 1800s, obtaining 72.1% decipherment word accuracy. Table-based key Book-based key Cipher Caesar cipher Beale cipher (character) Simple substitution Zodiac 408 Copiale cipher Code Rossignols’ Mexico-Nauen code (word) Grand Chiffre Scovell code Wilkinson code (this work) Figure 1: Simplified typology of substitution-based cryptosystems, with some examples. Ciphers involve character-level substitutions (e.g, f → q), while codes involve word-level substitutions (e.g., forest → 5731). 2 Related Work Figure 1 gives a simplified typology of classical, substitution-based cryptosystems.1 Table-based Ciphers involve character-based substitutions. The substitution may take the form of a simple offset, as in the Caesar substitution sys- tem, e.g., (a → d), (b → e), (c → f), etc. The Cae- sar cipher can be easily solved by algorithm, since there are only 26 offsets to check. The algorithm need only be able to recognize which of the 26 candidate plaintexts form good English. Since 25 of the candidates will be gibberish, even the sim- plest language model will suffice. A simple substitution cipher uses a substitution table built by randomly permuting the alphabet. Since there are 26! ≈ 4 · 1026 possible tables, algorithmic decipherment is more difficult. How- ever, there are many successful algorithms, e.g., (Hart, 1994; Knight and Yamada, …

Content truncated to 500 words