When working with substitution ciphers, it is useful to have quantitative measures for several things that we otherwise tend to describe rather loosely. How different is one candidate key from another? How well does a candidate key actually decode a particular message? And, in a homophonic cipher, how much additional obfuscation is being produced by assigning multiple cipher symbols to the same plaintext letter?
Those are different questions, and they require different metrics. In developing machine-learning models for solving homophonic ciphers, I needed both to generate large quantities of training data and to evaluate the quality of candidate solutions. To support those tasks, I defined three metrics for analyzing simple and homophonic substitution ciphers:
- Distance, which measures how different two cipher keys are.
- Clarity, which measures how much of a particular ciphertext is decoded correctly by a candidate key.
- Homophonicity, which measures the degree to which a cipher distributes plaintext letters across multiple cipher symbols.
The Zodiac ciphers provide convenient concrete examples, particularly the Z408, because its plaintext and key are known and because its key makes extensive use of homophones.
A little terminology first
A cipher key can be regarded as a collection of symbol-to-letter mappings, which I will abbreviate as SLMs. Each SLM says, in effect, “this cipher symbol represents this plaintext letter.”
In a simple substitution cipher, each plaintext letter is represented by one unique cipher symbol. If the plaintext alphabet contains 26 letters, a complete simple-substitution key therefore contains 26 cipher symbols and 26 corresponding SLMs.
A homophonic substitution cipher relaxes the one-symbol-per-letter rule. Each cipher symbol still represents one and only one plaintext letter, but a plaintext letter may be represented by several different cipher symbols. In that case,
The reason for doing this is straightforward: common plaintext letters can be spread across several cipher symbols, reducing the very conspicuous frequency peaks that make ordinary substitution ciphers vulnerable to frequency analysis.
For some of the statistical calculations below, we also need an estimate of plaintext letter frequencies. The examples here use a language model built from a large corpus of English text together with a corpus of the Zodiac Killer's writings. The resulting frequency distribution differs somewhat from ordinary English, as would be expected when material from a particular writer is deliberately included.
Distance: how far apart are two keys?
The most direct way to compare two cipher keys is simply to ask how many SLMs would have to be changed before the keys agreed.
I define the distance between two cipher keys as the total number of cipher symbols for which the mapping in one key is either absent from the other key or maps to a different plaintext letter.
When both keys contain exactly the same cipher-symbol alphabet, this is particularly simple. Suppose one candidate key maps 60 of 63 symbols to the same plaintext letters as the true key, while three symbols are mapped incorrectly. The distance between the two keys is 3. Three mapping changes are required to turn one key into the other.
If the keys do not contain exactly the same symbol set, missing mappings count as well. A mapping that exists in one key but not the other must be added or removed before the two keys can agree.
So, in practical terms, distance is the minimum number of SLM changes, additions, or removals required to transform one key into another.
This makes distance useful when evaluating a cipher-solving process. If the correct key is known, we can measure whether successive candidate keys are genuinely approaching it, even when the resulting plaintext is not yet readable.
Clarity: how much of the message is decoded correctly?
Distance measures agreement between keys. It does not directly measure how well a key decodes a particular message. For that, a more useful metric is what I call clarity.
Clarity is the proportion of plaintext characters that are decoded correctly when a candidate key is applied to a particular ciphertext:
A clarity of 0% means that the candidate key fails to decode any character correctly. A clarity of 100% means that every character in that particular message is decoded correctly.
The distinction between clarity and distance is important. A candidate key can have 100% clarity without having distance 0 from the true key.
Suppose, for example, that a cipher key contains mappings for 63 different symbols, but only 58 of those symbols actually occur in the ciphertext being tested. If the candidate key has all 58 of those mappings correct, the message will decode perfectly: clarity is 100%. The mappings for the five unused symbols could still be wrong, however, so the candidate key would not be identical to the true key.
Thus:
- Distance tells us how close two keys are.
- Clarity tells us how well a key decodes a particular ciphertext.
They are related, but they are not interchangeable.
Homophonicity: how much does the key distribute information?
The third metric concerns the structure of a homophonic cipher itself.
A simple substitution cipher assigns one cipher symbol to each plaintext letter. A homophonic cipher may assign two, three, four, or more symbols to a letter. The more aggressively those additional symbols are used - particularly for common letters - the more the plaintext frequency distribution is dispersed across the ciphertext alphabet.
I use the term homophonicity for a measure of that effect.
Specific homophonicity
For a particular encoded message, define
- \(C_a\) as the number of occurrences of plaintext letter \(a\) in the decoded message,
- \(n_a\) as the number of cipher symbols assigned to encode letter \(a\), and
- \(L\) as the length of the encoded message.
The specific homophonicity of the cipher is
where the sum is taken over the letters used in the message.
The behavior of the measure is the important part.
If every plaintext letter has exactly one cipher symbol, then \(n_a=1\) for each letter. The expression inside the logarithm evaluates to 1, producing a homophonicity of 0. A conventional simple substitution cipher therefore has homophonicity 0.
As additional symbols are assigned to plaintext letters, the value increases. Importantly, adding a homophone to a common letter raises the value more than adding one to a rare letter. That is exactly what we want from the measure: splitting the occurrences of a very common letter such as e across several symbols does more to obscure the underlying frequency distribution than splitting the occurrences of a very rare letter.
This version of the metric is specific because it depends on both the cipher key and the particular message being encoded.
General homophonicity
Sometimes we want to characterize the cipher key itself, independently of any one plaintext message. For that purpose we can replace the observed relative frequency \(C_a/L\) with the expected probability \(P_a\) of the letter in the source language.
The resulting general homophonicity is
Here, \(P_a\) is the probability of plaintext letter \(a\) in the language model.
General homophonicity can therefore be interpreted as the expected homophonicity of the key across the range of messages that might reasonably be drawn from that language.
The addition of 1 in the denominator provides a consistent form for both the specific and general measures, while also accommodating letters in the source-language alphabet that do not occur in a particular cipher message. It also makes the simple-substitution case reduce cleanly to zero.
One other point is worth making explicitly: homophonicity is not normalized to a 0-to-1 scale. Zero has a clear interpretation - simple substitution - but sufficiently large and well-distributed homophonic alphabets can produce values greater than 1.
A minor terminological aside: I briefly considered calling this measure obfiscuity. Neither homophonicity nor obfiscuity exactly rolls off the tongue, but homophonicity at least says what is actually being measured.
The Z408 as an example
The Zodiac's Z408 cipher uses 54 cipher symbols to encode 23 plaintext letters. The letters j, q, and z do not occur in the plaintext and consequently have no cipher symbols assigned to them.
The allocation of symbols is quite revealing. The most frequent letter in the language model, e, is represented by seven different symbols. Several other common letters - including t, o, a, i, n, and s - have four symbols each. Less common letters tend to receive fewer.
For the actual Z408 message, the specific homophonicity is:
If we evaluate the key more generally over the 23-letter alphabet actually used by Z408, its general homophonicity is:
Those two numbers are close, as we would expect if the letter frequencies in the actual Z408 plaintext are reasonably representative of the underlying language model.
There is, however, a complication if we want to compare the Z408 key with arbitrary full-alphabet cipher keys. The actual key cannot encode j, q, or z. One reasonable way to make the comparison consistent is to extend the Z408 key by assigning one additional cipher symbol to each of those three letters. The extended key therefore contains 57 symbols and can encode all 26 letters.
Under that full-alphabet treatment, its general homophonicity is:
The change in value is not a contradiction. We have changed the question: the first figure characterizes the 23-letter key that Z408 actually uses; the second characterizes an extended 26-letter key that can be compared directly with arbitrary full-alphabet keys.
What range of homophonicity is possible?
Homophonicity is influenced by the number of cipher symbols, but it is not determined by that number alone.
With 26 cipher symbols encoding 26 letters, there is essentially no choice: each letter receives one symbol and the homophonicity is 0. Once the cipher alphabet grows beyond 26 symbols, however, the excess symbols can be distributed among the letters in many different ways. Different distributions produce different amounts of obfuscation.
For a given number of cipher symbols, we can therefore ask for the minimum and maximum possible general homophonicity.
The minimum
To minimize homophonicity, the extra symbols should be assigned where they accomplish the least.
Assume that every letter must have at least one symbol. Give one symbol to each of the 26 letters, and then assign every remaining symbol to the rarest letter in the language model. In ordinary English-like text, that is q.
For a 63-symbol cipher alphabet, for example, this pathological minimum would give one symbol to each of 25 letters and all 38 remaining symbols to q.
No sensible cipher designer is likely to do this. But that is not the point. It establishes the theoretical lower boundary.
The maximum
The maximum is found by doing essentially the opposite. Starting with one symbol per letter, assign each remaining symbol, one at a time, to whichever plaintext letter produces the greatest increase in homophonicity at that step. Continue until all available cipher symbols have been allocated.
This produces the upper boundary for a given cipher-alphabet size.
Using the Zodiac-specific letter distribution, the approximate ranges are:
- 54 symbols: 0.00083 to 0.83342
- 63 symbols: 0.00084 to 1.00906
The lower boundary barely moves because extra symbols can always be wasted on an extremely rare letter. The upper boundary rises much more substantially, although at a decreasing rate as the cipher alphabet becomes larger.
The lower boundary is almost invisible at the scale of Figure 3. Enlarging it makes its behavior clearer.
Where does Z408 fall within that range?
A direct comparison has to use equivalent alphabets. Comparing the original 54-symbol Z408 key, which covers only 23 letters, against the possible range for 54-symbol keys that cover all 26 letters mixes two different cases.
The cleaner comparison uses the extended Z408 key described above: 57 symbols covering all 26 letters. For a 57-symbol full-alphabet key, the maximum general homophonicity is approximately 0.89342. The extended Z408 value is 0.83677.
That placement is informative. It strongly suggests that the Z408 designer was intentionally making substantial use of homophonic obfuscation rather than assigning the additional symbols without regard to plaintext frequency. The allocation is much closer to the high-obfuscation end of the possible range. At the same time, it is not mathematically optimal. There was still room to distribute the available symbols in a way that would have produced a higher homophonicity value.
Generating cipher keys with a target homophonicity
Once homophonicity has been defined as a numerical property of a key, another useful operation becomes possible: we can deliberately construct cipher keys that have approximately specified homophonicity values.
This is useful when testing cipher-solving methods. Instead of generating test ciphers with vaguely defined levels of “difficulty,” we can produce families of keys that differ in a measurable structural characteristic.
A practical iterative procedure works as follows:
- Generate a random cipher key using the desired total set of cipher symbols, with at least one symbol assigned to every plaintext letter.
- Calculate its general homophonicity.
- Consider every legal one-step reassignment in which a cipher symbol is moved from one plaintext letter to another. No letter is permitted to lose its final remaining symbol.
- Calculate the homophonicity that would result from each possible reassignment.
- Select the reassignment that moves the key closest to the requested target value.
- Repeat until the target is reached within a specified tolerance, or until the attainable boundary is reached if the requested value lies outside the possible range.
The key point is that the procedure does not attempt to construct the final allocation in one step. It repeatedly makes the single local change that most productively moves the current key toward the desired value.
As a first example, a target homophonicity equal to the Z408's specific value was requested:
The generated key reached:
In a second example, the requested value was higher:
and the generated key reached:
The identities of the individual cipher symbols in such randomly generated examples are arbitrary; what matters structurally is how many symbols are assigned to each plaintext letter. The figures therefore emphasize those allocations rather than the particular glyphs chosen for them.
Putting the three metrics together
Distance, clarity, and homophonicity describe three different aspects of a substitution cipher problem.
Distance is a key-to-key measure. It tells us how many mapping changes separate one candidate key from another.
Clarity is a key-and-message measure. It tells us what proportion of a particular ciphertext is being decoded correctly.
Homophonicity is primarily a measure of cipher-key structure. Specific homophonicity describes the obfuscation actually realized in a particular encoded message, while general homophonicity describes the expected behavior of the key across possible messages drawn from a language model.
The distinctions matter because cipher-solving results can otherwise be surprisingly difficult to compare. A candidate key may be structurally close to the true key while still producing poor plaintext. Another may decode a particular message perfectly while retaining incorrect mappings for symbols that never occur in that message. And two homophonic ciphers using the same number of symbols can differ substantially in how effectively those symbols are allocated.
Putting numerical measures on these properties does not solve a cipher. It does, however, give us a much more precise vocabulary for describing what a cipher key is doing, how a solver is progressing, and how strongly a homophonic design is actually obscuring the statistical structure of its plaintext.
Comments