前言

ADFGVX和ADFGX本质没有什么区别,只是棋盘大小从25格变成了36格

特征

ADFGX 特征

总览 -
标准密文字符种类数量 5
标准密文字符种类 ADFGX
标准密文分组
标准密文分组最小单位 2个字符
密文区分大小写字母
标准输入数量 3
标准输入 密码表/Keysquare, 移位密钥/transposition key, 密文/ciphertext|明文/message
标准明文字符种类支持数量 25
标准明文字符种类 26个字母中删减一个或ij不分
明文区分大小写字母
公开密码表 / Keysquare -
标准密码表
phqgmeaynofdxkrcvszwbutil http://practicalcryptography.com/ciphers/adfgx-cipher/
phqgmeaynofdxkrcvszwbutjl http://practicalcryptography.com/ciphers/adfgx-cipher/
btalpdhozkqfvsngicuxmrewy https://en.wikipedia.org/wiki/ADFGVX_cipher
btalpdhozkqfvsngjcuxmrewy https://en.wikipedia.org/wiki/ADFGVX_cipher
keyabcdfghilmnopqrstuvwxz https://www.apprendre-en-ligne.net/crypto/bibliotheque/Plotz/Doc/ADFGVX.html
pgcenbqozrslaftmdviwkuyxh [1]洪焘宇,柳庆志,王博.在古典密码学范畴下对ADFGX加密法的改进[J].科技创新导报,2013(14):217-218+221.
amretqdnfliobuyckhwzpvsgx https://www.nku.edu/~christensen/1402%20ADFGVX.pdf
ABCDEFGHIKLMNOPQRSTUVWXYZ https://www.dcode.fr/adfgx-cipher
ABCDEFGHIJKLMNOPQRSTUWXYZ https://www.dcode.fr/adfgx-cipher
ABCDEFGHIJKLMNOPQRSTUVXYZ https://www.dcode.fr/adfgx-cipher
ABCDEFGHIJKLMNOPRSTUVWXYZ https://www.dcode.fr/adfgx-cipher
ABCDEFGHIJKLMNOPQRSTUVWXY https://www.dcode.fr/adfgx-cipher
移位密钥 / transposition key -
标准密钥
不移位 https://www.dcode.fr/adfgx-cipher
german http://practicalcryptography.com/ciphers/adfgx-cipher/
cargo https://en.wikipedia.org/wiki/ADFGVX_cipher
rhein [1]洪焘宇,柳庆志,王博.在古典密码学范畴下对ADFGX加密法的改进[J].科技创新导报,2013(14):217-218+221.
howareu https://wishingstarmoye.com/ctf/adfgx

ADFGVX 特征

总览 -
标准密文字符种类数量 6
标准密文字符种类 ADFGVX
标准密文分组
标准密文分组最小单位 2个字符
密文区分大小写字母
标准输入数量 3
标准输入 密码表/Keysquare, 移位密钥/transposition key, 密文/ciphertext|明文/message
标准明文字符种类支持数量 36
标准明文字符种类 a-z0-9
明文区分大小写字母
公开密码表 来源
ph0qg64mea1yl2nofdxkr3cvs5zw7bj9uti8 https://asecuritysite.com/encryption/ADFGVX
ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789 https://www.dcode.fr/adfgvx-cipher
ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890 https://www.dcode.fr/adfgvx-cipher
Z8HV7XEQLTGPCAOWS06K4MJI1Y2FNBURD593 https://cryptocompanion.netlify.com/adfgvx
na1c3h8tb2ome5wrpd4f6g7i9j0klqsuvxyz https://en.wikipedia.org/wiki/ADFGVX_cipher
dhxmu4p3j6aoibzv9w1n70qkfslyc8tr5e2g https://kifanga.com/what-is-adfgvx-cipher/
co8xf4mk3az9nwl0jd5siyhup1vb6req7t2g https://www.britannica.com/topic/ADFGVX-cipher
ai2o0d1bh6mstnwcq4lg7vyrf5e3xz9pjk8u https://www.nku.edu/~christensen/1402%20ADFGVX.pdf
公开移位密钥 来源
GERMAN https://asecuritysite.com/encryption/ADFGVX
cargo https://en.wikipedia.org/wiki/ADFGVX_cipher
CODE https://cryptocompanion.netlify.com/adfgvx
PRIVACY https://en.wikipedia.org/wiki/ADFGVX_cipher
howareu https://wishingstarmoye.com/ctf/adfgx
Cipher https://kifanga.com/what-is-adfgvx-cipher/
author https://www.britannica.com/topic/ADFGVX-cipher
Sinkov https://www.nku.edu/~christensen/1402%20ADFGVX.pdf
Kentucky https://www.nku.edu/~christensen/1402%20ADFGVX.pdf

标准加解密流程

标准加密实现 (以ADFGX为例)

本质是字符替换,然后进行移位,字符替换是很容易理解的,举个例子,消息为nintysecu,采用密码表phqgmeaynofdxkrcvszwbutil,密码表进行分布之后如下

\ A D F G X
A p h q g m
D e a y n o
F f d x k r
G c v s z w
X b u t i l

(类似的表被称为Polybius方格,也就是棋盘密码,用横纵坐标来代替具体内容)

替代的顺序为AA-> p AD->h DA->e诸如此类

其实我们可以想到, 如果仅仅是做这一步,如果需要做对应的加解密程序的话,并不需要真的考虑棋盘,考虑到密码替代覆盖范围,可以直接定义AA=p AD=h之类进行处理,棋盘的存在主要是用于移位时的理解

通过棋盘,可以将上面的消息转为DG XG DG XF DF GF DA GA XD,当然空格只是一种表现形式,为了将各个字母区分

此后还需要一串长度至少为2且建议至多不超过消息长度-1的字符串作为移位密钥,至于长度限制的原因,主要为了避免移位失败,移位的过程如下

先定义一个密钥为china,此时密钥长度为5,则将上方替换后的消息进行分割为长度为5的字符串组,得到DGXGD GXFDF GFDAG AXD,将分组按在消息中的先后顺序排列,得到

CHINA
DGXGD
GXFDF
GFDAG
AXD

将上面的细分下来,就是

C H I N A
D G X G D
G X F D F
G F D A G
A X D

china按字母顺序重新排列,得到achin

A C H I N
D D G X G
F G X F D
G G F D A
A X D

然后从上往下读,得到最终密文DFG DGGA GXFX XFDD GDA,当然空格不是必须的,仅仅是一种简单的表现形式。

标准解密实现 (以ADFGX为例)

假设我们拿到了密文DFGDGGAGXFXXFDDGDA,移位密钥china,密码表phqgmeaynofdxkrcvszwbutil

先计算密文长度为18,移位密钥长度为5,则可以推算出移位密钥中有三个字母下会排下4个字母,移位密钥前三位是chi,因此chi下会排4个字母。

将密钥china按照字母顺序排列,得到achin,然后开始排列18个字母,其中chi排4个,其他排3个,得到

A C H I N
D D G X G
F G X F D
G G F D A
A X D

然后排列回来

C H I N A
D G X G D
G X F D F
G F D A G
A X D

一行一行读取,两两分割,然后对照密码表取回正确消息nintysecu

思考 (以ADFGX为例)

在ADFGX的变换中,一共使用了两种变换手法,一种是棋盘密码,但实际上可以直接理解为单表替换密码,只是使用了二维坐标来表示,二来是转置密码,不过转置之前增加了移位密钥,变换了列排序,这也被称为列移位加密

替换密码的本质就是用一/多个字符替换为另一/多个字符,这是古典密码中经常出现的操作,比如凯撒、rot13、维吉尼亚等,本质上都是短单元(一个或几个字符)替换,只不过有些密码表是动态的,有些是写死的。

消息在经过棋盘密码替换之后,得到了以ADFGX五个字母为基础的密文,记为R,将R以移位密钥长度为单位分组并更换列顺序,然后使用转置密码进行处理。

以明文nintysecu密文DFGDGGAGXFXXFDDGDA为例,消息加密如动图所示,其中棋盘替换过程未给出。

可以料想,将ADFGX密码分解为两种存在先后顺序的单表替换和转置密码后,解密的方法呼之欲出了。

另外我们可以想到,所谓的转置密码,实际上只是栅栏密码的二维可视化表现形式,本质上是一样的。

首先要将其视为列移位加密,需要猜测移位密钥的长度和列顺序排列。

已知部分明文

由于已知解开转置密码之后就是一个单表替换密码,而单表替换密码其中一个特征就是一对一替换,正是转置密码和其移位变换打乱了这种一对一替换的顺序。因此如果 已经获取到部分明文 的话,可以根据明文密文的字符对应情况,尝试遍历移位密钥的长度和移位顺序,比如已知明文为thisisasecretmessage,那么此时如果尝试的密钥解出的消息为yfekeklkibuiyzikklgi就说明移位密钥极可能是正确的,而yfeekkiekbuekzikklgi就极可能是错误的,因为第三个字符应当和第五个字符一致,和第四个字符不同。此时解出的是转置密码部分。

转置密码解开之后剩下的就是单表替换问题了,同样的在 已知部分明文 的条件下,可以得到部分乃至全部的密码表,由此可以解开部分或全部的密文消息。这里的writeup就是这么做的(尽管这道题事实上给出了移位密钥)

但是如果 已知部分明文 的前置条件不成立呢?也许一部分人在日常用语中可能会有一些惯用语句,比如消息末尾写I look forward to hearing from you之类的,这是猜测 部分明文 的一些方法,但是如果依然无法获取到部分明文呢?

本身ADFGX/ADFGVX发明于二战时期,限于一些特殊情况可解密:在有两份或者多份相同明文开头的密文的情况下,可以尝试恢复换位;在有两份或多份相同明文结尾的密文的情况下,可以尝试破解密文代替部分的均匀分布的保护;而另外,在棋盘所有格子都被使用的情况下也可以破解[1],当然,这些的前提条件都是密文是通过同一个棋盘和移位密钥加密的。但是这些问题我还没有研究清楚,所以暂不细讲,等研究清楚了,再另起文章。

当没有移位密钥时

先尝试上方的公开移位密钥,实在找不到移位密钥的时候,可以考虑爆破,暴力分析,尤其是当消息本身是有意义的时候,可以结合字典分析出高概率的消息

对于CTF或者某些情况,应当考虑是否没有进行移位操作。

当没有密码表的时候

先尝试分析获取移位密钥,如果有明文的话将密文与明文对应,字母一一替换。

实例

CRY100 2nd PART - ebCTF 2013

>
We found the following encoded message to protect some 'cargo'.
>
VDFXXVFGAXAFVVDAFFXXFDXXXGXVVVDGAVGFFGFVGVXGFGFVFVGVGXGGXDFFAGXVAXFGFFDAVGFGGDVVAVVGDXGDGAAVGXDVFDDVDVFAVDFGFFDXDAGADAGFVDDGGXFVDVVFXGGVFAVDXXFXXVGVGGFXFXVVDGAGAVDXXAXAFFXGXVDAVFVXFGXFFXAVFGXVVVVVFVXFVXXGFVVVAFDDDGXGAADVXAGXXDAFGADXDXDFDXVGXVVGGGGVGGGXDVDDVFGVVVFFVAFVDGDFXDGXDVVDDAVVGAFDVXVGGVXGFDXDVXXXXXDAGGXADXGGGVDGDAVVXFVDFFXDGGFGDVDVDVFVGGXDFVGXDVAADADVVGDVXGXXDXAFDVAVVDDGVFXGVAXXGXVVDGFGFXXDFAGDFGFVFDAFVXGVVXAVGFFVVADAFVXVDVXVAXFGVGFFFAGAGVGDDDXAADVVXGGFFXVGXVXXFAGXGFDADDAFGFDAXGAFFDGXVXGAGVVDVXGVXXGVVVXFGGVVGAXX
>
We were able to partialy decode the header. Can you decode the rest:
>
Shipping order
>
from: bram bloemendaal (Phone: 0123456789)
to: joris verhoven

题目中给出了移位密钥为cargo,但是这不是必要的,可以通过工具分析。

先用CrypTool(v1)分析一下移位(暂时不清楚这里分析的原理是什么)

然后我们剩下的是进行单表替换操作,参考上面的已知明文攻击,使用标准alpha字母表替换(实际上任意棋盘都可以,但是默认的棋盘有一些带星号的)

得到

kzujjun06tr3t2t6abteab163a3nree1jz6n3qfliyhmpx7v6c6tuk53tz653n2unrb316we11vz3uv3akkzujj3rv6d6sz6j32s11d353tdvzun0uk68u2n6v23312t33v646nve4va36njz6n3nsab3tqfliyhmpx78unrt30etrkbteafqq8u16j6vev63khq8u164es1u216w3tll8u16ejj13kfiy8u1613386n3k346nrjetv62vz321e0b4f4q7

题目中已知密文的开头为

>
Shipping order
from: bram bloemendaal (Phone: 0123456789)
to: joris verhoven

正则简单处理一下,把[^a-zA-Z0-9]替换为空,全体转小写,得到

>
shippingorderfrombrambloemendaalphone0123456789tojorisverhoven

则明文消息为62字符,密文取前62字符,然后在bash中用tr处理一下
>
echo kzujjun06tr3t2t6abteab163a3nree1jz6n3qfliyhmpx7v6c6tuk53tz653n2unrb316we11vz3uv3akkzujj3rv6d6sz6j32s11d353tdvzun0uk68u2n6v23312t33v646nve4va36njz6n3nsab3tqfliyhmpx78unrt30etrkbteafqq8u16j6vev63khq8u164es1u216w3tll8u16ejj13kfiy8u1613386n3k346nrjetv62vz321e0b4f4q7 | tr 'kzujjun06tr3t2t6abteab163a3nree1jz6n3qfliyhmpx7v6c6tuk53tz653n' 'shippingorderfrombrambloemendaalphone0123456789tojorisverhoven'

得到
>
shippingorderfrombrambloemendaalphone0123456789tojorisverhovenfindbelowalltheitemsshippedtodoshopefslldeverdthingiso8ifnotfeelfreeto4onta4tmeonphonensmber01234567898indregardsbram1008ilopotatoes508ilo4asliflower228iloapples1348ilolee8onese4ondpartoftheflagb41409

可以看到消息末尾 onese4ondpartoftheflagb41409 ,可以想到是密文4没有对应明文在上面出现,但是可以猜到4对应c,由此得到flag:bc1c09

一些其他说明

并不是所有工具都完美实现了adfg(v)x的算法,也并不是所有CTF题目都正确地理解了该密码学。下面列出一些工具和CTF题目,部分存在问题(点名批评!)。

工具

https://wishingstarmoye.com/ctf/adfgx
https://www.cryptool.org/de/ct1-downloads
https://www.cryptool.org/en/cryptool2

-

https://github.com/guyoung/CaptfEncoder
影响:密码表中的j将被无视,如果输入了带有j的25个字符,将被提示长度不够

-

https://www.dcode.fr/adfgx-cipher
密文:FAXDFADDDGDGFFFAFAXAFAFX
密码表:BTALPDHOZKQFVSNGICUXMREWY
移位:CARGO
明文:attackatonce
影响:无法正确解密

CTF

某些CTF赛题可能不完全遵守解密流程,尽管给出的提示的确是ADFGX/ADFGVX,但实际上是一个有默认棋盘的棋盘密码。
http://www.shiyanbar.com/ctf/1955为例,给出的例子为FA XX DD AG FF XG FD XG DD DG GA XF FA,没有移位密钥,没有给出解密表,而解法则是使用公开密码表中的phqgmeaynofdxkrcvszwbutil进行单次替换,得到flagxidianctf

相关密码学

参考资料

源链接

Hacking more

...