细说经典密码学 ADFGX/ADFGVX（一）

前言

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

...