"黄道十二宫杀手"的340个字符密码的 Wolfram 解决方案

  

编者注："黄道十二宫杀手（Zodiac Killer，又译星座杀手、黄道杀人魔，以下简称黄道带杀手）"（在20世纪60年代和70年代活跃的美国身份不明的连环杀手）向旧金山地区的新闻界发出了许多关于当地凶杀案的嘲讽信。在这些信中，凶手对罪行负责，并威胁要进一步谋杀。他还包括三个密码，每个密码包含一个408个字符的密码的三分之一。凶手声称，这种密码在解密后会揭示他的身份。凶手在1969年408个字符的密码被解密后，将第四个和最后一个密码（在本博客文章中讨论）发送给了《旧金山纪事报》，但这并未揭示凶手的身份。

2020年，澳大利亚墨尔本对整个城市进行了为期112天的封城，以帮助阻止COVID-19的传播。戴口罩是强制性的，我们每天只能进行一小时的户外活动。否则，我们将被困在家里。这给了我很多时间来研究这多年来一直拖延的有趣问题。

我受到David Oranchak的油管视频（https://wolfr.am/UfAgAzsz）的启发，该视频查看了“黄道带杀手”（Zodiac Killer）的340个字符密码（Z340），如下图所示。该密码被认为是密码学的圣杯之一，因为该密码已抵御了50年的攻击，因此，寻找解决方案的任何尝试都好比登天。

在他的演讲中，David 探索了密码既是谐音替代密码又是换位密码的思想。存在用于求解谐音替换密码的高效程序，其中最好的程序是AZdecrypt。实验表明，AZdecrypt 可以解决所有长度和符号分布与Z340相同的谐音替换密码。但是，AZdecrypt无法用于解决Z340，因为当您在Z340上运行它时，它不会产生解决方案。解决Z340的情况可能是通过反复试验找到正确的换位，然后使用AZdecrypt解决谐音替换密码的情况。

David概述了一个特殊的变位，该变位是独立发现的，并由用户“ daikon ”和Jarl van Eycke（AZdecrypt的作者）发布到了 zodiackillersite.com：“ period-19 ”，它具有一些有趣的统计特性，表明它们更接近正确的换位。只是为了好玩，我决定使用Mathematica 绘制这种转置：

但是，这看起来与daikon和Jarl的19周期换位没有任何关系。令我惊讶的是，事实证明，他们的换位在垂直（周期性地）环绕时使用了一个周期18。

尽管这种换位在视觉上很有趣，但它并没有让我印象深刻，因为它是一种非常自然的铅笔和纸质结构。应当指出，Z340创建于1969年，因此几乎可以肯定是使用铅笔和纸建造的。

我看到了19周期换位与 20x17 密码的1,2-抽取之间的联系。也就是说，从左上角开始，先移动一个垂直步长，然后再移动两个水平步长，并在水平和垂直方向上定期包裹，就像将密码包裹在圆环上一样。此换位采用与19周期换位类似的对角线：

通过AZdecrypt运行Z340的1,2抽取转置不会产生解决方案。

研究找到谐音 (homophonic) 替换密码正确换位的可能性的一种方法是通过计算重复的双字母组（符号对）的数量。在Mathematica中，可以很容易地为任意 n-grams 编写以下代码：

然后，我们可以构造大量类似Z340的密码，并将它们的二元组计数分布与大量Z340的随机改组进行比较：

随机混洗的平均二元组数量为19.8，而类似于Z340的随机数为34.5。Z340具有25个重复的二元组，而daikon和Jarl 19 周期换位以及1,2-抽取具有37个重复的二元组。因此，从统计学上讲，我们认为自己走在正确的轨道上。

 

在1,2抽取转置没有产生解决方案之后，我们决定通过候选转置进行大型搜索。很难找出过去曾经测试过哪些换位，因此我决定枚举所有合理的1步和2步换位，并按其双字母组计数对其进行排序，然后通过AZdecrypt对其进行处理。例如，其中一些换位包括：

我还包括所有适当的一维和二维抽取转置。对于一维枚举，我们有以下128个适当的抽取：

对于二维枚举，我们有以下128个适当的抽取：

例如，3,4-抽取产生以下转置：

使用AZdecrypt，我们测试了所有行优先，列优先，交替行-列，交替列-行，向内螺旋，向外螺旋，对角线以及真一维和二维抽取转置。该实验未产生任何看起来像解决方案的结果，因此我们测试了所有对换位。然后，我们考虑测试所有三元组的换位；但是，这将需要测试155,929,364,660,224个候选密码。天真地检查一秒钟将花费五百万年。因此，我们将实验限制在可以手工写出的合理抽取条件下，然后仅测试具有较高双字母组计数的候选者。再次，此搜索没有发现任何结果。

也许我们还缺少一个步骤？考虑到Zodiac Killer的408个字符的密码（如下图）以三个相等大小的部分发送的方式，我们推测Z340是由许多不同的片段构成的，然后用转置和谐音替换进行加密：

黄道带杀手的408个字符的密码

我们考虑将密码水平分为两个和三个部分，垂直分为两个和三个部分，水平和垂直分为 2x2 和 3x3 部分。例如：

然后，我们使用Reduce来计算所有可能的 2x2 细分，从而导致真二维抽取：

鉴于1,2抽取转置的二元数很高，我们从二维抽取开始搜索，每个片段都具有相同的（单个）转置。正如我们之前多次看到的那样，该实验并没有带来任何结果。

对所有部分的多个转置和所有转置组合的下一个搜索将是一项更大的工作。因此，我们决定重新分析最初搜索的结果。

在我们测试的650,000个换位中，其中一个包含一些特别有趣的纯文本段：

这更加有趣，因为产生此候选解密的换位是1,2-抽取，并且密码被分为三个垂直段（如下图所示）：

进一步调查这个结果，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-抽取转置的发现以及 AZdecrypt求解谐音替换密码的能力已经对Z340进行了部分解密。

剩下的两个部分呢？可能我们只发现了9行的正确垂直分割，其余11行需要不同的分割，或者可能需要不同的换位，或者甚至是替换密码的密钥，或者任意两种组合这些可能性，甚至是所有三种可能性。我们的工作还远远没有结束。

David发现我们可以使用最后一段的第一段中的密钥来产生以下明文，而无需进行任何换位：

这种理解的某些部分是合理的，但是我们当然还没有解决。我们要求AZdecrypt的作者Jarl van Eycke帮助我们完成这一部分。他做了以下出色的观察：

• 从左到右读取LIFEIS纯文本（第二段）。

• LIFEIS纯文本从1,2抽取转置中排除，并从左到右读取。

• 如果将第六行中的“ H”移至第四列，则会纠正许多拼写错误。

• 应用1,2抽取转置，跳过包含“ LIFEIS”的位置：

?

我们为Z340密码发现的密码密钥和换位由下式给出：

在“黄道带杀手“将此密码邮寄给《旧金山纪事报》五十一年后，我们有了解决方案！David于2020年12月5日星期六将此解决方案提交给FBI密码分析和诈骗记录部门（CRRU）。此后不久，FBI 正式确认我们解决方案的有效性。(译者注：Z340 也就是第二道密码目前已被澳洲数学家Sam Blake - 本文原作者，比利时程序员Jarl Van Eycke及美国软件开发人David Oranchak于2020年12月破解。）

基本上，我在Z340上所做的所有工作都是在Mathematica中完成的。我使用了墨尔本大学的Spartan高性能计算集群，使用zkdecrypto消除了候选换位，而David使用了AZdecrypt。Z340的所有统计分析以及数百万个候选换位的创建和分析都是使用 Mathematica 完成的。我使用 Mathematica的原因很简单：这是迄今为止我可以用于此类任务的最省时的语言。

Sam Blake拥有澳大利亚莫纳什大学的数学博士学位，并且是墨尔本大学的研究员。自2004年以来，他一直是Mathematica的狂热用户，并在 Wolfram Research工作了四年。他对与数值建模，数据科学，符号计算，隐写术和密码学有关的研究感兴趣。