译者序

NSA文档解密 05/06/2014

这是一篇NSA文档，关于二战时期使用的ADFGVX加密系统的通解方法，原文为ADFGVX加密系统的通用解决办法，这里虽然是翻译，但主要采用意译的方式，将其中核心的部分解释出来，并加以自己的理解，希望能减轻读者的理解难度，如有必要，可以阅读原文，如有谬误，还请指正。

ADFGVX为棋盘密码+列移位(+转置)的组合，而棋盘密码本质上为替换密码。

文中提到的矩阵，指的是在经过明文消息在经过替换后，进行列移位时所创造的矩阵，详情可查看之前文章在列移位部分进行的变换。

文中提到的key，指列移位时用到的移位密钥。

文中所有的密文消息，均由同一套列移位密码和棋盘密码加密

文中提到的元素，指密文的ADFGVX六个字符，一个字符称一个元素。

原文的附录1没有在此翻译，因为附录1实际上是另一篇文章了，实在太长。

简介

ADFGVX加密算法源于二战时期的德军，该算法整合了替换和移位两种密码学算法，因为其密文中只有ADFGVX六种字符，因此被称为ADFGVX加密，在二战快要结束的时候，一共有三种针对该算法的方法，但都有一些限制，分别为

有两则明文开头部分相同/相似的密文
有两则明文结尾部分相同/相似的密文
有数则密文且这些密文刚好完全将矩阵填充完整

由此我们展开了一项对ADFGVX通解的研究。

此论文旨在介绍我们取得的研究成果，我们也相信该研究能够对其他的密码学工作有所启迪。

正文

讨论

这里给出的通解是基于对加密系统中使用的初始及结束时元素的频率变换分析，并在此假设棋盘没有被刻意地修改以达到元素频率均匀分布的目的。本文假定读者已经知道怎么去解密开头/结尾部分相同的ADFGVX密文。

在附录中给出了12则以相同key加密的消息以供测试。

首先，需要先确定key的长度是奇数还是偶数，也就是矩阵的列长是奇数还是偶数。

因为每个明文字母被替换成两个元素，因此可以得出两个结论:

当列数为偶数时:矩阵的每一行都是棋盘横坐标或纵坐标(也就是类型相同)
当列数为奇数时:矩阵将隔行进行横纵坐标交替变换(也就是奇数行与奇数行类型相同，偶数行与偶数行类型相同)

对于多则消息，他们的第一个元素一定是属于同一类别(或横坐标或纵坐标)，因此这些元素可以合并分析，得到一个简单的频率表。引申一下，他们的第3、5等奇数位置也是和第一个元素属于同一类别的，只要他们是在矩阵的同一列中，那么这些元素也可以添加到那个频率表中。

不过为了保证这些元素在同一列中，我们应该对取得的元素数量做一个限制，具体限制应当取决于消息的大小。考虑到绝大多数情况，我们可以安全地假设转置矩阵的列数不超过25列。

此外，和奇数位词频分析相同，也可以创建一个偶数位的频率表。

如果矩阵有偶数列的话，上述两个频率表应当呈现相似的频率，如果矩阵有奇数列的话，两个频率表应当有所差异。

我们对样本数据进行了测试，如下是他们的元素频率表。

两张表产生了明显的差异--VXF在图一和图二中展现的频率明显不同，元素V和X在奇数位的频率很高，但是在偶数位频率很低，F在奇数位频率很低但是在偶数位频率却很高。

消息3和消息11每个包含了186个元素，如果他们的奇偶位是矩阵横纵坐标交替的话(也就是说第1、3、5位是奇/偶，2、4、6位是偶/奇)，那么由于上述问题，VX很可能在其中一个隔行里出现(比如1 3 5或者2 4 6)，而F则更可能在另一个隔行中出现(假设VX在1 3 5出现，那么F应当在2 4 6中出现)。而如果这种隔行情况在密文消息的某处被逆转了(如果前段密文VX多出现在奇数位，中间某段出现在偶数位，F相反)，那么就说明了这里矩阵某一列的结束和另一列的开始。

基于这个想法，测试一下消息3 11。

在开头的前十个元素里，VX落在了奇数位上，而F落在了偶数位上；此后的十个元素中，F落在了奇数位上而VX落在了偶数位上。通过这种变化可以猜测到，矩阵的第一列在大概第10个元素左右结束。同样的变化也发生在第21~30个元素，但是这次的变化非常明显，VX同时出现在了22和23的位置，这说明22是一列的结束，而23是另一列的开始。如果列1和列2一共有22个元素，那么也就是说每一列都有11个元素，那么一共就有17列(即ceil(186/11))，而且这个矩阵的列长较短(只有11个元素)。

这里还有另一则消息也列长也比较短，即消息7，其有254个元素，(17*15)-1=254。这个消息的列长比消息3 11的列长多了4个元素，现在先假设最后一列为短列(一共有17列，有16列为长列，1列为短列)，那么消息7就可以直接放在消息3和11一起分析，那么就只要考虑消息7每列后面的4个元素就可以了。