Editor’s note: The Zodiac Killer (an unidentified American serial killer active during the 1960s and 70s) sent numerous taunting letters to the press in the San Francisco area with regard to a local murder spree. In these letters, the killer took responsibility for the crimes and threatened to commit further murders. He also included three ciphers, each containing one-third of a 408-character cryptogram. The killer claimed that this cryptogram would reveal his identity when deciphered. The killer sent the fourth and final cipher (discussed in this blog post) to the San Francisco Chronicle after the 408-character cryptogram, deciphered in 1969, did not reveal the killer’s identity.

In 2020, Melbourne, Australia, had a 112-day lockdown of the entire city to help stop the spread of COVID-19. The wearing of masks was mandatory and we were limited to one hour a day of outside activity. Otherwise, we were stuck in our homes. This gave me lots of time to look into interesting problems I’d been putting off for years.

I was inspired by a YouTube video by David Oranchak, which looked at the Zodiac Killer’s 340-character cipher (Z340), which is pictured below. This cipher is considered one of the holy grails of cryptography, as at the time the cipher had resisted attacks for 50 years, so any attempts to find a solution were truly a moonshot.

The Zodiac Killer’s 340-character cipher

In his presentation, David explored the idea that the cipher is both a homophonic substitution cipher and a transposition cipher. Highly efficient programs for solving homophonic substitution ciphers exist, the best of which is AZdecrypt. Experiments suggest that AZdecrypt can solve all homophonic substitution ciphers of the same length and symbol distribution as the Z340. However, AZdecrypt cannot be used to solve the Z340 because when you run it on the Z340, it does not produce a solution. Perhaps solving the Z340 is a case of finding by trial and error the correct transposition, then using AZdecrypt to solve the homophonic substitution cipher.

David outlined one particular transposition, which was discovered independently and posted to zodiackillersite.com by user “daikon” and Jarl van Eycke (the author of AZdecrypt): the “period-19,” which had some interesting statistical properties that would suggest that they were closer to the correct transposition. Just for fun, I decided to plot this transposition using Mathematica:

Partition[
   Table[1 + Mod[19 i, 340] -> i, {i, 0, 339}] // SparseArray // 
    Normal, 17] // drawTransposition;
Magnify[%, 0.5]

However, this looked nothing like daikon and Jarl’s period-19 transposition. To my surprise, it turned out their transposition used a period-18 when wrapping around (periodically) vertically.

While this transposition was visually interesting, it didn’t strike me as a very natural pencil-and-paper construction. It should be noted that Z340 was created in 1969, and therefore was almost certainly constructed using pencil and paper.

I saw a connection between the period-19 transposition and a 1,2-decimation of the  cipher. That is, starting from the top-left corner and moving one vertical step, then two horizontal steps, wrapping periodically both horizontally and vertically, like the cipher is wrapped around a torus. This transposition takes similar diagonals to the period-19 transposition:

decimate2D[array_, {n_, m_}] := Module[{d0, d1},
  {d0, d1} = Dimensions[array]; 
  (Table[array[[Mod[n i, d0] + 1, Mod[m i, d1] + 1]], {i, 0, 
      d0 d1 - 1}]) /; 
   CoprimeQ[d0, n] && CoprimeQ[d1, m] && CoprimeQ[d0, d1]
  ];

z12decimation = 
  Partition[decimate2D[Partition[Range[0, 340 - 1], 17], {1, 2}], 17];

Running the 1,2-decimation transposition of the Z340 through AZdecrypt did not produce a solution.

One way to investigate the likelihood of finding the correct transposition of a homophonic substitution cipher is by counting the number of repeating bigrams (pairs of symbols). In Mathematica, it’s easy to write up this code for arbitrary -grams:

countngrams[l_List, n_Integer] := 
 Total[Map[Last, Tally[Partition[l, n, 1]], 1] - 1]

Then we can construct a large number of Z340-like ciphers and compare their bigram count distribution to a large number of random shuffles of the Z340:

Histogram[{randomShuffle340, z340CiphersBigrams}, {1}, 
 ChartBaseStyle -> EdgeForm[Thin], Frame -> True, Axes -> False, 
 FrameLabel -> {Style["repeating bigram count", 12], 
   Style["frequency", 12]}, 
 ChartLegends -> {"random shuffles of Z340", 
   "random Z340-like ciphers"}, 
 ChartStyle -> {RGBColor[0.514366, 0.731746, 0.415503], 
   RGBColor[0.996414, 0.825742, 0.330007]}]

The mean number of bigrams for the random shuffles was 19.8, and for random Z340-like ciphers was 34.5. The Z340 has 25 repeating bigrams, while the daikon and Jarl period-19 transposition and the 1,2-decimation has 37 repeating bigrams. Thus, statistically, we thought we were on the right track.

After the 1,2-decimation transposition did not produce a solution we decided to work on a large search through candidate transpositions. It was difficult to find out what transpositions had been tested in the past, so I decided to enumerate all reasonable 1- and 2-step transpositions, sort them by their bigram count and run them through AZdecrypt. Some of these transpositions, for example, included:

I also included all proper one-dimensional and two-dimensional decimation transpositions. For one-dimensional enumerations, we have the following 128 proper decimations:

Select[Range[340], CoprimeQ[#, 340] &]
% // Length

For two-dimensional enumerations, we have the following 128 proper decimations:

Join @@ Outer[List, Select[Range[19], CoprimeQ[#, 20] &], Range[16]]
% // Length

For example, the 3,4-decimation generates the following transposition:

Partition[decimate2D[Partition[Range[0, 339], 17], {3, 4}], 17] // 
   invert // drawTransposition;
Magnify[%, 0.5]

Using AZdecrypt, we tested all row–major, column–major, alternating row–column, alternating column–row, inward spirals, outward spirals, diagonals and proper one-dimensional and two-dimensional decimation transpositions. This experiment didn’t yield anything looking like a solution, so we tested all pairs of transpositions. Then we considered testing all 3-tuples of transpositions; however, this would require testing 155,929,364,660,224 candidate ciphers. Naively checking one a second would take over five million years. So we limited our experiments to decimations which would be reasonable to write out by hand and then only tested candidates with a high bigram count. Once again, this search turned up nothing.

Perhaps there’s another step we are missing? Given the way the Zodiac Killer’s 408-character cipher (pictured below) was sent in three equally sized sections, we conjectured the Z340 was constructed from a number of distinct segments, then encrypted with a transposition and a homophonic substitution:

The Zodiac Killer’s 408-character cipher

We considered splitting the cipher horizontally into two and three segments, vertically into two and three segments, and both horizontally and vertically into  and  segments. For example:

Then we used Reduce to compute all possible  segments, which resulted in proper two-dimensional decimations:

Reduce[a > 0 && b > 0 && c > 0 && d > 0 && a + b == 17 && 
  c + d == 20 && GCD[a, c] == 1 && GCD[a, d] == 1 && GCD[b, c] == 1 &&
   GCD[b, d] == 1, {a, b, c, d}, Integers]

Given the high bigram count of the 1,2-decimation transposition, we started our search with two-dimensional decimations, with each segment having the same (single) transposition. As we had seen so many times before, this experiment didn’t turn up anything.

The next search for compositions of multiple transpositions and all combinations of transpositions for all sections would be a significantly larger undertaking. So we decided to reanalyse the results from the initial search.

Out of the 650,000 transpositions we tested, one contained a few particularly interesting segments of plaintext:

This was even more interesting as the transposition that produced this candidate decryption was the 1,2-decimation, with the cipher split into three vertical segments (pictured below):

Investigating this result further, David used our 9,9,2-vertical segment, 1,2-decimation transposition and AZdecrypt to crib the phrases “HOPE YOU ARE,” “TRYING TO CATCH ME” and “THE GAS CHAMBER.” With these cribs locked in place, AZdecrypt found the following solution of the first segment:

Eureka! After 51 years, we had decrypted some of the Z340. This was a very special moment. The discovery of the 9,9,2-vertical segment, 1,2-decimation transposition and the power of AZdecrypt for solving homophonic substitution ciphers had produced a partial decrypt of the Z340.

What about the remaining two segments? It was possible that we had found just one correct vertical split of 9 rows and the remaining 11 rows required a different segmentation, or it was possible that a different transposition was needed, or even a different key for the substitution cipher, or any two combinations of these possibilities, or even all three possibilities. Our work was far from over.

David discovered that we could use the key from the first segment on the last segment to produce the following plaintext—without any transposition:

Including some spaces, the cipher’s candidate plaintext gives:

Then, reversing a few words:

This seemed to be a pretty reasonable decryption of the last segment.

What about the second segment? If we crib all the legible text from the first section we get the following decryption:

Some parts of this kind of made sense, but we certainly weren’t there yet. We asked Jarl van Eycke, the author of AZdecrypt, to help us with this segment. He made the following brilliant observations:

• The LIFEIS plaintext (the second segment) is read left to right.
• The LIFEIS plaintext is excluded from the 1,2-decimation transposition and read left to right.
• Numerous spelling mistakes are corrected if “H” on row six is moved to the fourth column.
• Apply the 1,2-decimation transposition, skipping the positions containing “LIFEIS”:

Then the second segment becomes:

The cipher key and transposition that we discovered for the Z340 cipher are given by:

Fifty-one years after the Zodiac Killer mailed this cipher to the San Francisco Chronicle, we had a solution. David submitted this solution to the FBI Cryptanalysis and Racketeering Records Unit (CRRU) on Saturday, December 5, 2020. Shortly after, the FBI was able to officially confirm the validity of our solution.

Essentially all my work on the Z340 was done in Mathematica. I used the Spartan high-performance computing cluster at the University of Melbourne to eliminate candidate transpositions using zkdecrypto and David used AZdecrypt. Otherwise, all the statistical analysis of the Z340 and the creation and analysis of the millions of candidate transpositions was done using Mathematica. The reason for my use of Mathematica is simple; it is by far the most time-efficient language I could use for such a task.