https://blog.wolfram.com/2021/03/24/the-solution-of-the-zodiac-killers-340-character-cipher/ * WolframAlpha.com * WolframCloud.com * All Sites & Public Resources... [spike] Wolfram Computation Meets Knowledge Products & Services * Wolfram|One * Mathematica * Wolfram|Alpha Notebook Edition * Programming Lab * Finance Platform * SystemModeler * Wolfram Player * Wolfram Engine * WolframScript * + Enterprise Private Cloud + Enterprise Mathematica + Wolfram|Alpha Appliance * Enterprise Solutions + Corporate Consulting + Technical Consulting + Wolfram|Alpha Business Solutions * Data Drop * Resource System + Data Repository + Neural Net Repository + Function Repository * Wolfram|Alpha + Wolfram|Alpha Pro + Problem Generator + API * Data Drop * Products for Education * Mobile Apps + Wolfram Player + Wolfram Cloud App + Wolfram|Alpha for Mobile + Wolfram|Alpha-Powered Apps * Services + Paid Project Support + Wolfram U + Summer Programs * Products for Education * Mobile Apps + Wolfram Player + Wolfram Cloud App + Wolfram|Alpha for Mobile + Wolfram|Alpha-Powered Apps * Services + Paid Project Support + Wolfram U + Summer Programs All Products & Services Technologies Wolfram Language Revolutionary knowledge-based programming language. Wolfram Notebooks The preeminent environment for any technical workflows. Wolfram Data Framework Semantic framework for real-world data. Wolfram Cloud Central infrastructure for Wolfram's cloud products & services. Wolfram Engine Software engine implementing the Wolfram Language. Wolfram Universal Deployment System Instant deployment across cloud, desktop, mobile, and more. Wolfram Science Technology-enabling science of the computational universe. Wolfram Natural Language Understanding System Knowledge-based, broadly deployed natural language. Wolfram Knowledgebase Curated computable knowledge powering Wolfram|Alpha. All Technologies Solutions * Engineering, R&D + Aerospace & Defense + Chemical Engineering + Control Systems + Electrical Engineering + Image Processing + Industrial Engineering + Mechanical Engineering + Operations Research + More... * Education + All Solutions for Education * Finance, Statistics & Business Analysis + Actuarial Sciences + Bioinformatics + Data Science + Econometrics + Financial Risk Management + Statistics + More... * Software & Web + Software Development + Authoring & Publishing + Interface Development + Web Development * Education + All Solutions for Education * Trends + Machine Learning + Multiparadigm Data Science + Internet of Things + High-Performance Computing + Hackathons * Sciences + Astronomy + Biology + Chemistry + More... * Software & Web + Software Development + Authoring & Publishing + Interface Development + Web Development * Sciences + Astronomy + Biology + Chemistry + More... All Solutions Learning & Support * + Learning o Wolfram Language Documentation o Fast Introduction for Programmers o Wolfram U o Videos & Screencasts + o Wolfram Language Introductory Book o Webinars & Training o Summer Programs o Books * Need Help? + Support FAQ + Wolfram Community + Contact Support * Premium Support + Paid Project Support + Technical Consulting All Learning & Support Company * About + Company Background + Wolfram Blog + Events + Contact Us * Work with Us + Careers at Wolfram + Internships + Other Wolfram Language Jobs * + Initiatives o Wolfram Foundation o MathWorld o Computer-Based Math o A New Kind of Science o Wolfram Technology for Hackathons o Student Ambassador Program + o Wolfram for Startups o Demonstrations Project o Wolfram Innovator Awards o Wolfram + Raspberry Pi o Summer Programs o More... All Company Search * [ ] [blog-lo] News, Views & Insights Browse by Topic * Best of Blog (60) * Astronomy (23) * Books (16) * Computational Thinking (57) * Current Events (25) * Data Analysis and Visualization (124) * Data Repository (9) * Design (24) * Developer Insights (67) * Digital Humanities (3) * Education (143) * Events (33) * Finance (23) * Function Repository (9) * Geosciences (12) * High-Performance Computing (12) * History (11) * Image Processing (47) * Machine Learning (16) * Mathematica News (62) * Mathematica Q&A (13) * Mathematics (114) * New Technology (17) * Other Application Areas (77) * Raspberry Pi (18) * Recreational Computation (140) * Software Development (32) * System Modeler (43) * Wolfram Cloud (22) * Wolfram Community (15) * Wolfram Demonstrations Project (31) * Wolfram Language (188) * Wolfram News (222) * Wolfram Notebooks (32) * Wolfram U (15) * Wolfram|Alpha (37) * Wolfram|One (7) Related Topics * Current Events (25) * Data Analysis and Visualization (124) * High-Performance Computing (12) * History (11) * Recreational Computation (140) Related Posts * Florida Spring Break 2021: February COVID-19 Data Forecasts the March of the Variants * 3D-Printed Jewelry Made with the Wolfram Language Showcases the Beauty of Mathematics * Classifying Cough Sounds to Predict COVID-19 Diagnosis The Solution of the Zodiac Killer's 340-Character Cipher March 24, 2021 Sam Blake, Guest Author 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. The Solution of the Zodiac Killer's 340-Character Cipher 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 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 ✕ 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. Period-19 transposition 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 [sb32] 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 ✕ 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] ✕ 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 ✕ 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: Examples of 1- and 2-step transpositions 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 ✕ Select[Range[340], CoprimeQ[#, 340] &] % // Length For two-dimensional enumerations, we have the following 128 proper decimations: Join @@ Outer ✕ Join @@ Outer[List, Select[Range[19], CoprimeQ[#, 20] &], Range[16]] % // Length For example, the 3,4-decimation generates the following transposition: Partition[decimate2D ✕ 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 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: Examples of splitting the cipher Then we used Reduce to compute all possible # segments, which resulted in proper two-dimensional decimations: Reduce[a ✕ 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: 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): Cipher split into three vertical segments 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: The plaintext solution for the first segment of the Zodiac Killer 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: Plaintext without transposition Including some spaces, the cipher's candidate plaintext gives: The cipher's candidate plaintext gives Then, reversing a few words: The candidate plaintext with some reversed 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: Cribbed legible text 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": LIFEIS plaintext Then the second segment becomes: The second segment becomes The cipher key and transposition that we discovered for the Z340 cipher are given by: The cipher key for Zodiac Killer The transposition for Zodiac Killer 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. The FBI confirmation of 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. --------------------------------------------------------------------- Sam Blake has a PhD in mathematics from Monash University in Australia and is a research fellow at the University of Melbourne. He's been an avid Mathematica user since 2004 and worked for Wolfram Research for four years. He is broadly interested in research related to numerical modeling, data science, symbolic computation, steganography and cryptography. Get full access to the latest Wolfram Language functionality with a Mathematica 12.2 or Wolfram|One trial. Posted in: * Current Events (25) * Data Analysis and Visualization (124) * High-Performance Computing (12) * History (11) * Recreational Computation (140) Comments Join the discussion [ ] [ ] [ ] [ ] Leave a comment [ ] !Please enter your comment (at least 5 characters). Name [ ] !Please enter your name. Email [ ] !Please enter a valid email address. Website (optional) [ ] [Submit comment] [Cancel] 2 comments 1. Thanks Sam, that was a brilliant piece of sleuthing on yours and David's part. It is especially intriguing how the use of Mathematica's visualizations allowed you to determine the between the appropriate transpositions and substitutions. It is also significant that after being able to translate 3 phrases from the first crib you were quickly able to reduce the number of possibilities by fixing those specific translations. This was also part of the success with Turing's original Bombe translator when he recognized that "Heil Hitler" and other stock phrases were being used in the Enigma transmissions from the German high command. Again congrats! Michael Reply Michael Kelly March 24, 2021 at 12:05 pm 03/24/2021 at 12:05 pm 2. Very nice analysis! Thanks for sharing. Have you looked at this function: https://resources.wolframcloud.com/FunctionRepository/ resources/LatticePointsArrangement Perhaps useful to generate the various grids. Reply Sander Huisman March 24, 2021 at 12:54 pm 03/24/2021 at 12:54 pm Related Posts Current Events & History Florida Spring Break 2021: February COVID-19 Data Forecasts the March of the Variants [covid-spring-break-tree-tile] Current Events & History 3D-Printed Jewelry Made with the Wolfram Language Showcases the Beauty of Mathematics [spikey-earrings-tile] Current Events & History Classifying Cough Sounds to Predict COVID-19 Diagnosis [2021-02-10-covid-cough-audio] Enable JavaScript to interact with content and submit forms on Wolfram websites. Learn how >> * Products * Wolfram|One * Mathematica * Wolfram|Alpha Notebook Edition * Programming Lab * Wolfram|Alpha Pro * Mobile Apps * Finance Platform * SystemModeler * Wolfram Player * Wolfram Engine * WolframScript * Wolfram Workbench * Volume & Site Licensing * Enterprise Private Cloud * View all... * Services * Technical Consulting * Corporate Consulting * Services * Technical Consulting * Corporate Consulting * For Customers * Online Store * Product Registration * Product Downloads * Service Plans Benefits * User Portal * Your Account * Support * Support FAQ * Customer Service * Contact Support * Public Resources * Wolfram|Alpha * Demonstrations Project * Resource System * Connected Devices Project * Wolfram Data Drop * Wolfram + Raspberry Pi * Wolfram Science * Computer-Based Math * MathWorld * Hackathons * Computational Thinking * View all... * Support * Support FAQ * Customer Service * Contact Support * Learning * Wolfram Language Documentation * Wolfram Language Introductory Book * Fast Introduction for Programmers * Fast Introduction for Math Students * Webinars & Training * Wolfram U * Summer Programs * Videos * Books * Public Resources * Wolfram|Alpha * Demonstrations Project * Resource System * Connected Devices Project * Wolfram Data Drop * Wolfram + Raspberry Pi * Wolfram Science * Computer-Based Math * MathWorld * Hackathons * Computational Thinking * View all... * Company * Events * About Wolfram * Careers * Contact * Connect * Wolfram Community * Wolfram Blog * Newsletter * (c) 2021 Wolfram. All rights reserved. * Legal & Privacy Policy * Site Map * WolframAlpha.com * WolframCloud.com [Translate this page] Enable JavaScript to interact with content and submit forms on Wolfram websites. Learn how