Segmenting Numerical Substitution Ciphers (2022)

Abstract: Deciphering historical substitution ciphers is a challenging problem. Example problems that have been previously studied include detecting cipher type, detecting plaintext language, and acquiring the substitution key for segmented ciphers. However, attacking unsegmented ciphers is still a challenging task. Segmentation (i.e. finding substitution units) is essential for cracking those ciphers. In this work, we propose the first automatic methods to segment those ciphers using Byte Pair Encoding (BPE) and unigram language models. Our methods achieve an average segmentation error of 2% on 100 randomly-generated monoalphabetic ciphers and 27% on 3 real historical homophonic ciphers. We also propose a method for solving non-deterministic ciphers with existing keys using a lattice and a pretrained language model. Our method leads to the full solution of the IA cipher; a real historical cipher that has not been fully solved until this work.

## introduction the contents of thousands of historical documents are still unknown to the contemporary age, even though they are encrypted using classical methods. example documents include books from secret societies, diplomatic correspondences, and pharmacological books. previous work has been done on collecting historical ciphers from libraries and archives and making them available for researchers @xcite . however, decipherment of classical ciphers is an essential step to reveal the contents of those historical documents. methods for deciphering historical substitution ciphers have been proposed by the natural language processing community @xcite @xcite @xcite @xcite . however, † work done prior to jm joining amazon. ## problem definition a substitution cipher is a cipher that is created by substituting each plaintext character with another character according to a substitution table called the key. we define major terms in the following subsections. ## segmenting ciphers with no existing keys we start with the first (and the more challenging) case; segmenting a numerical cipher with no existing key. in this case, all we have is a sequence of digits (see, for example, figure 3 ). to solve the cipher, we need to segment the ciphertext before trying to find the substitution key. in this section, we describe our proposed methods for segmenting numerical ciphers without using a key. ## data to evaluate our methods on monoalphabetic numerical ciphers, we create synthetic ciphers from sample text extracted from english wikipedia. we lowercase all characters and remove all non-alphabetic and non-space symbols. we notice that most historical ciphers in the decode collection are two pages long and contain about 2k characters, so we choose cipher length 2,048 for our experiments. we create 100 english ciphers using randomly generated keys. we use the numbers from 0 to 99 as possible cipher elements. this creates variablelength ciphers when single digits are chosen in the key. we report the average scores of the 100 ciphers for each experiment. for evaluation on real historical ciphers, we use 3 ciphers from the the vatican secret archives, retrieved from the decode database @xcite . figure 3 : three historical ciphers from the vatican secret archives. foot_3 ## experimental evaluation we carry out three types of experiments. first, we start with the simplest cipher type; monoalphabetic ciphers with spaces. the existence of spaces indicates word boundaries, which gives some clues on how to segment the ciphertext. second, we remove spaces and try to segment the same monoalphabetic ciphers, which is expected to be a harder task. third, we experiment with segmenting homophonic ciphers, which is the most challenging case discussed in this paper. we apply our proposed segmentation methods on both synthetic and real historical ciphers. we also study the effect of cipher length on segmentation quality. as an evaluation metric, we use segmentation edit rate (seger). seger is the segment-level levenshtein distance between output and gold segmentations, divided by the number of segments in the gold segmentation. we define seger as: we use the sentencepiece implementation of bpe and unigram language model @xcite . segmenting a 2k-token cipher takes about 0.08s on a 3.6 ghz quad-core intel core i3 processor. for homophonic ciphers, we set the vocabulary size to the maximum number found by the unigram language model. for monoalphabetic ciphers, we set vocabulary size to 36 (26 maximum possible 2-digit elements for 1-1 substitutions + 10 singleton digits). we use the default settings in sentencepiece, but we set character coverage to 100%. we learn subwords from raw unsegmented ciphertext, represented as continuous sequences of digits. we keep line-breaks as they appear on cipher scans since we notice that line-breaks usually do not cut through a cipher element in historical ciphers. ## segmenting non-deterministic ciphers with an existing key we now consider the second case: suppose we have a cipher and a key, but the cipher is nondeterministic. this case can arise in practice when the key of the cipher is found while combing through historical archives, for example. alternatively, the key could have been found by a cryptanalyst by solving a part of the cipher. although the cipher key exists in these scenarios, the nondeterministic segmentation makes it impossible to directly apply the key to recover the plaintext; recall the ambiguous segmentation example of the word and from section 2.4. in this case, it is very challenging to manually recover the whole plaintext, especially when the cipher is very long. figure 6 : example segmentation ambiguity for the ia cipher. a short 8-digit part of the cipher produces 8 possible segmentations according to the key. the number of candidate segmentations increases exponentially with respect to cipher length. ## related work previous decipherment work has mainly been focused on solving substitution ciphers with clearly segmented cipher elements, e.g. @xcite @xcite @xcite @xcite . early decipherment approaches search for the substitution table that gives a highly probable plaintext according to a character lm. more recent approaches incorporate neural models. @xcite use beam search and a neural lm to score candidate plaintext hypotheses from the search space for substitution ciphers. @xcite view decipherment as a sequence-to-sequence translation problem. however, all of these works only deal with ciphers that have clear substitution units. lasry et al. ( 2020 ) present an extensive study on papal ciphers from the 16th to 18th century. those ciphers are numerical substitution ciphers that need to be segmented. for segmentation, lasry et al. (2020) create a set of segmenters (called "parsers" in that work) from a collection of known cipher keys. then they test the cipher in hand to see if any of the previously created segmenters can be a good fit. our method, by contrast, is not limited to existing keys. in fact, our method is completely unsupervised and only uses ciphertext as input. a similar task to learning cipher segments is learning linguistic units (words and morphemes) from unsegmented text, e.g. @xcite @xcite . ## conclusion in this work, we present automatic methods for segmenting numerical substitution ciphers. we propose a novel approach to segment numerical ciphers with no existing keys using subword segmentation algorithms. we use bpe and unigram language models as unsupervised methods to learn substitution units. we add a 2-digit heuristic based on historical cipher analysis. our best method is able to segment 100 randomly generated monoalphabetic ciphers with an average seger of less than 3%, while still being robust to removing spaces. we test our methods on 3 real homophonic ciphers from the 16th-18th centuries. our best method achieves an average seger of 27%, with a seger of 15% on the f283 cipher. to the best of our knowledge, this is the first work on automatically segmenting numerical substitution ciphers. we also propose a method for solving nondeterministic substitution ciphers with existing keys using a lattice and a pretrained language model. our method achieves a ter of 1.12% on the ia cipher, a real historical cipher that has not been fully solved until this work.