细说经典密码学ADFG(V)X(二)

前言

上一篇文章为https://xz.aliyun.com/t/3603,其中在实例部分中给出的解法,是需要已知部分明文和移位密钥为前提的,通过移位密钥,可以破解列移位,再根据已知明文,可以破解棋盘,但这还是一个比较粗略的解法,已知移位密钥和部分明文,这个前置条件是不符合现实的,由此在这里讨论对移位密钥和已知明文的获取分析。

上篇文章中有部分论述条理不够清晰,本文希望尽量避免这个问题。

在上一篇文章中,我提到可以使用CrypTool来获取正确的移位密钥,并提到暂不清楚该运作流程,实际上我当时已经猜到一些端倪了–应该是使用了词频分析,这也是本文准备论述的一些技巧。

这里讨论的分析,都有一个前提条件:使用了同一套移位密钥和棋盘,消息明文为英文。

此外,还有一篇paper论述了一种基于词频分析的通解,下一篇文章将翻译该文。

正文

攻击转置加密

转置加密攻击成功的标准–对密文进行精确分组/恢复矩阵

明文开头相同

思考一下,当明文开头部分相同的情况下,是否会有一些特征存留。

首先设定移位密钥的长度为L,密文长度为2K,ceil(2K / L) 记为C(向上取整,即棋盘行数)

对于有两则明文开头部分相同的消息,现在我们知道,ADFGVX经过了棋盘与带有列移位的转置加密。我们暂时将进行列移位之前的棋盘所获取到的每一行称为一行密码片段,每一列成为一列密码片段,那么不难想到,在转置之前,前几行密码片段应该是一样的,或者说第一则消息与第二则消息的前N行是一样的,引申出来可以得到,第一则消息的第M列的第N行与第二则消息的第M列第N行是一样的,这是在列移位之前。

- - - - -
A D F G V
X A D F G
V X A D F
/ / / / /
/ / / / /
/ / / / /
/ / /

而当列移位之后,这个结论保持不变,只是原来的第M列变成了第(M+Y)列,而第N行还是第N行,但总之,第一则消息中第M列第N行的字符依然与第二则消息的第M列第N行相同。

- - - - -
F G V D A
D F G A X
A D F X V
/ / / / /
/ / / / /
/ / / / /
/ / /

转置之后,每列对应一个分组,从二维棋盘转为一维字符串,第M列就是第M个分组,第N行就是每个分组的第N个字符,则上述转置前的结论可转化为:第一则消息的第M个分组的第N个字符与第二则消息的第M个分组的第N个字符相同。

FDA////GFD///VGF///DAX////AXV////

由于N代表了前N行,M代表的是相同明文开头的所有列,那么可以得到结论:当明文开头相同时,将存在两则密文间断性相同,而相同的部分就是开头的明文,相同部分的间隔等于棋盘行数C(或C-1,当棋盘未填满时)。

这是很容易理解的一件事。

这样我们就可以对密文进行精确分组/恢复矩阵。

实例分析

假设当前拦截到如下两则消息

1
FFDXXXDDXAADXFXVGVFAAGDXVFFVFFVDVFAGFGVADXFGAAXXFGVFAXXDAFFXXXAAVXXFFFGVAVGAADXDFDAXXVVGAXAXGXVVGXXFXXXGAGVDAXAGXGVDXGVXGXVGGGVGAFXXVGVVGAGVGXXDXVFXGGXAXVGDXF
1
FFDXXFXFXGGFGAVAXAAAXVFFVXAXGXAXDXXFGFXXAXXFGVXDVFGGAAGXGXAVFFGVGDXADGXDXVAVAAAAAXGXVXVGAXVXXXGAXXDXXGVDXADVXVAAAAXDXFVDVGAGVGGGFXVGVGAGFGXG

第一则消息记为a,长158,第二则消息记为b,长140,尝试对两则消息进行分组,仔细观察两则消息,可以发现,当每个分组的字符长度达到某一个值的时候,a与b每个分组开头达到相似,如下

  • FFDXXXDDXAADXFXVGVFAAGD XVFFVFFVDVFAGFGVADXFGA AXXFGVFAXXDAFFXXXAAVXXF FFGVAVGAADXDFDAXXVVGAX AXGXVVGXXFXXXGAGVDAXAG XGVDXGVXGXVGGGVGAFXXVGV VGAGVGXXDXVFXGGXAXVGDXF

  • FFDXXFXFXGGFGAVAXAAA XVFFVXAXGXAXDXXFGFXX AXXFGVXDVFGGAAGXGXAV FFGVGDXADGXDXVAVAAAA AXGXVXVGAXVXXXGAXXDX XGVDXADVXVAAAAXDXFVD VGAGVGGGFXVGVGAGFGXG

这就意味着密钥长度为7,并且此时可以将密文精确还原至转置之前/列移位之后的状态了。

明文结尾相同

其实这个限制和明文开头相同是一样的,同样是尝试先对密文进行分组,然后检查不同密文的每个分组的结尾是否有相同之处(或者先观察两则密文的相似程度,再进行分组),有的话就说明其明文的结尾部分是相同的,并且可以此用来对转置加密进行精确划分分组,不再赘述了。

词频分析

对于转置加密的词频分析,我将在下一篇译文中详述。

攻击列移位

列移位被成功攻击的标准应当是被恢复至正确顺序的矩阵,或者说是一个未知棋盘加密过后的棋盘密码

这里假设已经解决了转置加密,即恢复了转置矩阵/密文已被精确分组

分析列移位是一项比较困难的工作,关键需要进行词频分析,因为在此之后还有一个棋盘密码需要处理,所以并不能直接拿到对应的字符,而是拿到不同的词频,然后将词频与该语言的词频进行对应分析。

不过在词频分析之前,还可以做一些微小的工作来降低难度(在样本充足的情况下,这些工作甚至可以直接解出移位密钥)。

密文列数完整填充

在此假设密文已被精确分组/或者得到了一批可能性较高的答案,为每个答案进行列移位攻击测试

如果所有列数都被填充过长列,那么可以精确恢复移位–并不是说矩阵被完整填充,而是说需要有长列(指相对于短列而言)为1、2、3…N-1的样本。即使样本不足,也将为词频分析提供有效帮助。

继续上面分析密钥长度时举的例子,我们得到了最终的结果FDA////GFD///VGF///DAX////AXV////,但是我们注意一下,对于每个分组,有些长度为6,有些长度为7,我们知道在进行填充棋盘的时候,总是按照从上往下/从左往右的顺序填充,很容易可以想到,长度更长的分组应当更加靠前。因此在这个例子中,分组顺序应当是[145][23],其中2与3的顺序不确定,145三者的顺序不确定。

应当注意的是,这里的顺序[145][23]并不是列移位密钥,而是经过移位后的恢复顺序,这里的顺序是以密文为正序,排列至明文顺序,而移位密钥则相反。
比如原文为12345,经过移位密钥45123之后是45123,那么移位后的恢复顺序就是34512
再举个例子,列移位前的明文为clytze,移位密钥为561234,那么移位后的密文则为zeclyt,而此时由密文向明文移位得到的恢复顺序为345612
用工具来表示的话,当拿到移位密钥(明文→密文)的顺序为561234时,执行

1
echo 123456 | tr 561234 123456

得到密文345612,这也就是密文→明文的移位恢复密钥,如果拿到了密文→明文的移位恢复顺序为345612时,同样执行

1
echo 123456 | tr 345612 123456

可以得到正向移位密钥561234
实际上就是一个简单的移位,或者说替换。

由此我们拿到了一个大致的恢复顺序[145][23]

我们由此可以想到,如果有四组密文,恢复分组后的结果为XXX///////XXX//////XXX//////XXX///////XXX///////XXX/////XXX/////XXX////XXX/////XXX/////XXX////////XXX////////XXX////////XXX/////////XXX/////////XXX///XXX///XXX///XXX///XXX////,此时每组及其分段长度为10/9/9/10/108/8/7/8/811/11/11/12/126/6/6/6/7,根据长列置左的原则,分别可以确定下来恢复顺序为[145][23] [1245][3] [45][123] [5][1234],最终得到一个精确的恢复顺序为54123,由此确定移位密钥为34521

词频分析

但是也许我们并没有充足的样本可供参考,那么就要求我们去进行词频分析。

我们在上面无法确定[145]三者以及[23]二者的内部顺序,于是我们可以通过分析词频进行进一步操作,有时候当矩阵被完整的填充了–所有分组长度都相同,那么就不能使用长列置左的原则,即无法确定出一个粗略的顺序,这时依旧需要进行词频分析。

对于词频分析,这里用于恢复列移位,其实这是不算很难理解的事,但是做起来会比较难。

FDFVDFXVXXXGXGXDGFXXXGDAAFAXGXXADDFVDXAAXG为例,已知解决了转置加密,得到精确分组:FDFVDF XVXXXG XGXDGF XXXGDA AFAXGX XADDFV DXAAXG,矩阵如下(列移位乱序)

F X X X A X D
D V G X F A X
F X X X A A A
V X D G X D A
D X G D G F G
F G F A X V G

这时需要注意到一件事:分组被分为7组,也就是说矩阵有7列。这里将用到一个小trick,这里将分开讲。

矩阵有奇数列时(移位密钥长度为奇数)

当奇数列的时候,可以想到,第一行的消息的最后一个元素和第二行的消息的第一个元素将组成一个完整的字符,第三行消息最后一个元素和第四行消息第一个元素将组成完整字符。

也就是说,正确矩阵的第2、4、6行的第一个元素实际上代表的是棋盘密码中的横轴字符(以纵轴-横轴顺序读取的情况下,反之也可以是纵轴,不过这不重要)。

正确矩阵的第1、3、5行的最后一个元素实际上代表的是棋盘密码中的纵轴字符。

引申一下,在正确矩阵中,奇数列的奇数行和偶数列的偶数行应当都是代表棋盘密码的纵轴字符,剩余的(也就是奇数列的偶数行与偶数列的奇数行)是棋盘密码的横轴字符。或者对于列乱序的矩阵来说,对于单列而言,第1、3、5列代表的都是横/纵轴,第2、4、6列代表的都是纵/横轴。

这时候就可以讨论词频的问题了,由于棋盘被分为横轴和纵轴,那么其横轴的频率和纵轴的每个字符频率是不一样的。因此当样本数量充足的情况下,就可以对每一列的奇/偶行进行区别整理,由此可以进一步区别出那些列应该是同样的,此时可以将其恢复至列横纵交替的状态–我们知道了如何为其分组。

举个例子,当我们对样本进行研究分析时,如果发现某一列的D在奇数行出现的频率最高,而在另一列中也出现了同样的情况,那么就表明这两列有很大的机率属于同一分类–同样为奇数列或者同样为偶数列,并且这个D很有可能代表了棋盘中e的横坐标或者纵坐标。

如果在其他列中发现了另一个频率和D频率相近的元素,假设为G,那么可以想到D和G的组合很可能是e。

另外我们可以确定下来,纵坐标D出现的频率比横坐标D出现的频率要高,而在同一列中我们可以区分哪些元素是同一组的。横坐标的G也同理。

如果没有与D频率相近的元素,而D的频率远高于其他元素,可以想到e或许是DD。

我们可以想到由于是奇数列,每列的第一行总是与前/后列的元素组合,第二行总是与后/前的元素组合,形成一种连锁的效果,这样一来又为词频分析提供了一些线索。

此外,我们将随机的两个代表不同坐标的列进行组合,组合后的两个列记为h,得到每一隔行两个元素,将两个元素视为一个整体记为r,我们在h中检查r的频率,在h中检查每一隔行r出现的频率,我们变换不同的列组合,直到频率分布近似语种的语言词频分布,当样本数据越多,得到的结果可能越精确。

此后我们将得到的数个移位密钥以此用来测试,再进行棋盘密码的攻击。

矩阵有偶数列时

偶数列和奇数列差不多,区别在于矩阵为奇数列时,第1、3、5行和第2、4、6行是不一样的,而偶数列时一整列都代表了相同坐标(或横坐标或纵坐标)。

不过偶数列并没有形成奇数列所说的连锁效果。

此外,在进行组合以分析词频时,偶数列并不需要进行隔行。

小结

基于词频分析的研究不太容易讲清楚,对于列移位的词频分析,主要就是尝试不同的列顺序,然后对其中的每个组合进行频率分析,检查其是否符合语言的词频分布,以得到一些近似可能的答案。至于上面的一些如e之类的,主要是缓解一些计算压力,对于计算机而言可能不用,但是对于二战时期的手算还是很有必要的。

总之,词频分析是一个繁琐的事情,而且我们不能精确的得到某一个答案,而是得到一批可能性较高的答案。

攻击棋盘

攻击棋盘的前提是已经解决了列移位/或者以及得到了一批可能性较高的答案,为每个答案进行棋盘攻击测试。

如此一来,就只剩下需要解决棋盘密码了,可以参照棋盘密码的解决方式来解决问题。

已知明文攻击

我们已经知道棋盘密码其实就是一个二维的替换密码,因此很容易知道,如果有了部分明文,直接将密文与明文一一对应,即可解出部分/全部棋盘。在上文中所使用的解决办法,实际上就是采用明文攻击的方式攻击ADFGVX的棋盘。

选择明文攻击

因为不需要寻找已知明文在密文段中所对应的位置(有时已知的明文只是从明文消息中随意摘取的一段),因此选择明文攻击能轻易的恢复全部棋盘,不过也没有细说的必要。

词频分析

词频分析往往是最后一个解决办法,这里有一个知名的词频分析工具。鉴于这是棋盘密码,每一个原字符被替换成了两个字符,因此我们暂时需要将每两个字符替换为一个字符,不过具体怎么操作,我其实也没有一个很好的方案,但总之这并不是一个很难的事情。

此时我们得到了一个恢复的字符串,与真实的字符串相比,这里相当于进行了一个单表替换,这时就可以进行词频分析了。

要将两个字符恢复至一个字符的原因是,许多词频分析工具的默认单元为一个字符,而棋盘密码将一个字符拆分成了两个字符(这个操作被称为Fractionation,直译为分馏,见维基百科,我不知道中文中是否有对应的专有翻译)。

这里的词频分析,交给工具就行了,至于基本原理,也就是单个语种里不同字符在常用句中出现的频率不同,以及组合该语种的一些单词作为字典进行分析等等,不细说了。


所有棋盘均为X924TN17L6YGZBMW5HAJO8CR03QVPFESKIDU,密钥为huangli

a消息的明文为The Hockey World Cup trophy was designed by the Bashir Moojid and created by the Pakistani Army

b消息的明文为The Hockey World Cup consists of a qualification stage and a final tournament stage

文章作者: 期末考第一名
文章链接: https://hundan.org/2018-12-19-细说经典密码学ADFG(V)X(二).html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 期末日记