編者注："黃道十二宮殺手（Zodiac Killer，又譯星座殺手、黃道殺人魔，以下簡稱黃道帶殺手）"（在20世紀(jì)60年代和70年代活躍的美國身份不明的連環(huán)殺手）向舊金山地區(qū)的新聞界發(fā)出了許多關(guān)于當(dāng)?shù)貎礆傅某爸S信。在這些信中，兇手對罪行負(fù)責(zé)，并威脅要進(jìn)一步謀殺。他還包括三個密碼，每個密碼包含一個408個字符的密碼的三分之一。兇手聲稱，這種密碼在解密后會揭示他的身份。兇手在1969年408個字符的密碼被解密后，將第四個和最后一個密碼（在本博客文章中討論）發(fā)送給了《舊金山紀(jì)事報(bào)》，但這并未揭示兇手的身份。

2020年，澳大利亞墨爾本對整個城市進(jìn)行了為期112天的封城，以幫助阻止COVID-19的傳播。戴口罩是強(qiáng)制性的，我們每天只能進(jìn)行一小時的戶外活動。否則，我們將被困在家里。這給了我很多時間來研究這多年來一直拖延的有趣問題。

我受到David Oranchak的油管視頻（https://wolfr.am/UfAgAzsz）的啟發(fā)，該視頻查看了“黃道帶殺手”（Zodiac Killer）的340個字符密碼（Z340），如下圖所示。該密碼被認(rèn)為是密碼學(xué)的圣杯之一，因?yàn)樵撁艽a已抵御了50年的攻擊，因此，尋找解決方案的任何嘗試都好比登天。

在他的演講中，David 探索了密碼既是諧音替代密碼又是換位密碼的思想。存在用于求解諧音替換密碼的高效程序，其中最好的程序是AZdecrypt。實(shí)驗(yàn)表明，AZdecrypt 可以解決所有長度和符號分布與Z340相同的諧音替換密碼。但是，AZdecrypt無法用于解決Z340，因?yàn)楫?dāng)您在Z340上運(yùn)行它時，它不會產(chǎn)生解決方案。解決Z340的情況可能是通過反復(fù)試驗(yàn)找到正確的換位，然后使用AZdecrypt解決諧音替換密碼的情況。

David概述了一個特殊的變位，該變位是獨(dú)立發(fā)現(xiàn)的，并由用戶“ daikon ”和Jarl van Eycke（AZdecrypt的作者）發(fā)布到了 zodiackillersite.com：“ period-19 ”，它具有一些有趣的統(tǒng)計(jì)特性，表明它們更接近正確的換位。只是為了好玩，我決定使用Mathematica 繪制這種轉(zhuǎn)置：

但是，這看起來與daikon和Jarl的19周期換位沒有任何關(guān)系。令我驚訝的是，事實(shí)證明，他們的換位在垂直（周期性地）環(huán)繞時使用了一個周期18。

盡管這種換位在視覺上很有趣，但它并沒有讓我印象深刻，因?yàn)樗且环N非常自然的鉛筆和紙質(zhì)結(jié)構(gòu)。應(yīng)當(dāng)指出，Z340創(chuàng)建于1969年，因此幾乎可以肯定是使用鉛筆和紙建造的。

我看到了19周期換位與 20x17 密碼的1,2-抽取之間的聯(lián)系。也就是說，從左上角開始，先移動一個垂直步長，然后再移動兩個水平步長，并在水平和垂直方向上定期包裹，就像將密碼包裹在圓環(huán)上一樣。此換位采用與19周期換位類似的對角線：

通過AZdecrypt運(yùn)行Z340的1,2抽取轉(zhuǎn)置不會產(chǎn)生解決方案。

研究找到諧音 (homophonic) 替換密碼正確換位的可能性的一種方法是通過計(jì)算重復(fù)的雙字母組（符號對）的數(shù)量。在Mathematica中，可以很容易地為任意 n-grams 編寫以下代碼：

然后，我們可以構(gòu)造大量類似Z340的密碼，并將它們的二元組計(jì)數(shù)分布與大量Z340的隨機(jī)改組進(jìn)行比較：

隨機(jī)混洗的平均二元組數(shù)量為19.8，而類似于Z340的隨機(jī)數(shù)為34.5。Z340具有25個重復(fù)的二元組，而daikon和Jarl 19 周期換位以及1,2-抽取具有37個重復(fù)的二元組。因此，從統(tǒng)計(jì)學(xué)上講，我們認(rèn)為自己走在正確的軌道上。

 

在1,2抽取轉(zhuǎn)置沒有產(chǎn)生解決方案之后，我們決定通過候選轉(zhuǎn)置進(jìn)行大型搜索。很難找出過去曾經(jīng)測試過哪些換位，因此我決定枚舉所有合理的1步和2步換位，并按其雙字母組計(jì)數(shù)對其進(jìn)行排序，然后通過AZdecrypt對其進(jìn)行處理。例如，其中一些換位包括：

我還包括所有適當(dāng)?shù)囊痪S和二維抽取轉(zhuǎn)置。對于一維枚舉，我們有以下128個適當(dāng)?shù)某槿。?/p>

對于二維枚舉，我們有以下128個適當(dāng)?shù)某槿。?/p>

例如，3,4-抽取產(chǎn)生以下轉(zhuǎn)置：

使用AZdecrypt，我們測試了所有行優(yōu)先，列優(yōu)先，交替行-列，交替列-行，向內(nèi)螺旋，向外螺旋，對角線以及真一維和二維抽取轉(zhuǎn)置。該實(shí)驗(yàn)未產(chǎn)生任何看起來像解決方案的結(jié)果，因此我們測試了所有對換位。然后，我們考慮測試所有三元組的換位；但是，這將需要測試155,929,364,660,224個候選密碼。天真地檢查一秒鐘將花費(fèi)五百萬年。因此，我們將實(shí)驗(yàn)限制在可以手工寫出的合理抽取條件下，然后僅測試具有較高雙字母組計(jì)數(shù)的候選者。再次，此搜索沒有發(fā)現(xiàn)任何結(jié)果。

也許我們還缺少一個步驟？考慮到Zodiac Killer的408個字符的密碼（如下圖）以三個相等大小的部分發(fā)送的方式，我們推測Z340是由許多不同的片段構(gòu)成的，然后用轉(zhuǎn)置和諧音替換進(jìn)行加密：

黃道帶殺手的408個字符的密碼

我們考慮將密碼水平分為兩個和三個部分，垂直分為兩個和三個部分，水平和垂直分為 2x2 和 3x3 部分。例如：

然后，我們使用Reduce來計(jì)算所有可能的 2x2 細(xì)分，從而導(dǎo)致真二維抽?。?/p>

鑒于1,2抽取轉(zhuǎn)置的二元數(shù)很高，我們從二維抽取開始搜索，每個片段都具有相同的（單個）轉(zhuǎn)置。正如我們之前多次看到的那樣，該實(shí)驗(yàn)并沒有帶來任何結(jié)果。

對所有部分的多個轉(zhuǎn)置和所有轉(zhuǎn)置組合的下一個搜索將是一項(xiàng)更大的工作。因此，我們決定重新分析最初搜索的結(jié)果。

在我們測試的650,000個換位中，其中一個包含一些特別有趣的純文本段：

這更加有趣，因?yàn)楫a(chǎn)生此候選解密的換位是1,2-抽取，并且密碼被分為三個垂直段（如下圖所示）：

進(jìn)一步調(diào)查這個結(jié)果，David 用我們的9,9,2垂直段，1,2-抽取換位和AZdecrypt到嬰兒床短語（已知明文攻擊）“HOPE YOU ARE,” “TRYING TO CATCH ME” 和 “THE GAS CHAMBER.”。將這些嬰兒床鎖定到位后，AZdecrypt 找到了第一段的以下解決方案：

Eureka! 51年后，我們解密了一些Z340。這是一個非常特殊的時刻。9,9,2-垂直段，1,2-抽取轉(zhuǎn)置的發(fā)現(xiàn)以及 AZdecrypt求解諧音替換密碼的能力已經(jīng)對Z340進(jìn)行了部分解密。

剩下的兩個部分呢？可能我們只發(fā)現(xiàn)了9行的正確垂直分割，其余11行需要不同的分割，或者可能需要不同的換位，或者甚至是替換密碼的密鑰，或者任意兩種組合這些可能性，甚至是所有三種可能性。我們的工作還遠(yuǎn)遠(yuǎn)沒有結(jié)束。

David發(fā)現(xiàn)我們可以使用最后一段的第一段中的密鑰來產(chǎn)生以下明文，而無需進(jìn)行任何換位：

這種理解的某些部分是合理的，但是我們當(dāng)然還沒有解決。我們要求AZdecrypt的作者Jarl van Eycke幫助我們完成這一部分。他做了以下出色的觀察：

• 從左到右讀取LIFEIS純文本（第二段）。

• LIFEIS純文本從1,2抽取轉(zhuǎn)置中排除，并從左到右讀取。

• 如果將第六行中的“ H”移至第四列，則會糾正許多拼寫錯誤。

• 應(yīng)用1,2抽取轉(zhuǎn)置，跳過包含“ LIFEIS”的位置：

?

我們?yōu)閆340密碼發(fā)現(xiàn)的密碼密鑰和換位由下式給出：

在“黃道帶殺手“將此密碼郵寄給《舊金山紀(jì)事報(bào)》五十一年后，我們有了解決方案！David于2020年12月5日星期六將此解決方案提交給FBI密碼分析和詐騙記錄部門（CRRU）。此后不久，F(xiàn)BI 正式確認(rèn)我們解決方案的有效性。(譯者注：Z340 也就是第二道密碼目前已被澳洲數(shù)學(xué)家Sam Blake - 本文原作者，比利時程序員Jarl Van Eycke及美國軟件開發(fā)人David Oranchak于2020年12月破解。）

基本上，我在Z340上所做的所有工作都是在Mathematica中完成的。我使用了墨爾本大學(xué)的Spartan高性能計(jì)算集群，使用zkdecrypto消除了候選換位，而David使用了AZdecrypt。Z340的所有統(tǒng)計(jì)分析以及數(shù)百萬個候選換位的創(chuàng)建和分析都是使用 Mathematica 完成的。我使用 Mathematica的原因很簡單：這是迄今為止我可以用于此類任務(wù)的最省時的語言。

Sam Blake擁有澳大利亞莫納什大學(xué)的數(shù)學(xué)博士學(xué)位，并且是墨爾本大學(xué)的研究員。自2004年以來，他一直是Mathematica的狂熱用戶，并在 Wolfram Research工作了四年。他對與數(shù)值建模，數(shù)據(jù)科學(xué)，符號計(jì)算，隱寫術(shù)和密碼學(xué)有關(guān)的研究感興趣。