How to break homophonic substitutions and nomenclators with too many symbols?

Question

Early attempts to thwart frequency analysis attacks on ciphers involved using homophonic substitutions, i.e., some letters map to more than one ciphertext symbol.

The earliest known example of this, from 1401, is shown below:

[Source: “Quadibloc” cryptography blog]

One variant is the nomenclator, where codewords are used to substitute many common words and names. The example below was used by Mary Queen of Scots in 1586.

[Source: Simon Singh]

According to Wikipedia,

By the late eighteenth century, when the system was beginning to die out, some nomenclators had 50,000 symbols.

What is the best way to go about cracking those kinds of ciphers as the number of symbols used increases?

Answer 1

Regarding the first part of the question, I will just link to another answer I wrote in the past: Why don't homophones hide multiple-letter patterns?

Summary: If you adjust the frequencies so that every single symbol is equally likely, then bigrams can be used for frequency analysis because they won't be uniform distributed. The structure of language is much more complex than frequencies of single symbols.

The second one is probably much easier to break: Let's assume you know that this kind of cipher is used. The list of the most common words in English should be fairly easy to generate. And then just pick arbitrary plaintexts and calculate the frequencies. When you consider the most common words as one symbol that will change the frequencies of the other letters to some degree, but the symbols for most likely words are between the most likely symbols of the alphabet.

To further improve this process:

• Look at bigram frequencies. If you consider the symbols for (of, the), that is surely one of the most likely bigrams in such a cipher.
• Adding more and more words as single symbols has no meaningful effect: Language is very, very non-uniform over words. See These lists on Wikipedia to get an idea:
  • In the "TV list", first is you with $1,222,421$ counts, 1000th is worst with a mere $2276$. That's a factor of $537$ times higher. Total count was $29,213,800$ for that list.
  • In the "Project Gutenberg list", first is the with $56,271,872$ per billion words, 1000th is names with $79,366.6$ per billion words. That's a factor of $709$ in those frequencies.
  • In the first list, the 1000th word has frequency $\approx 0.0000779$, and in the second list it's $\approx 0.0000794$. So if you consider every word a single symbol, this is the frequency. If you use multiple symbols of the normal alphabet for other words, the frequency of this special word would be even less.

On the nomenclators, there is also the problem: Since you assign one symbol per word, if you change the key you need to update the entire lists for both parties.

Frequency analysis can be applied to more than just single letters, and not all patterns of natural language can be hidden at the same time. This makes substitution ciphers really weak, especially if you use the same key (in the nomenclator this is the entire list) for more than a single, very short message.

Answer 2

I suppose one could say that in the limit such a system would approach a one-time pad and actually be secure.

In practice it is probably easy to write a computer program to brute force such substitutions if you can easily check if the resulting substitutions make the output look like English text and if that text makes sense.

In a way you are not only looking at the frequency of individual words (which the homophonic substitution obscures) but the frequency of pairs of words and triples of words, etc.