在古典密码学范畴下对ADFGX加密法的改进

　　摘要：密码学作为保护关键信息的手段，最早被应用在军事以及外交领域。随着人们日常生活的需求以及科技的发展等因素，密码学的应用已经逐渐进入了人们的生活中。密码学的发展历程可以分为古典密码学以及现代密码学两个阶段。1949年，n发表了题为《Communicationtheoryofsecrecysystems》的著名论文，首次将信息论引入密码系统，建立了密码学的数学模型，将密码学领到了科学的轨道上。使得密码学的发展进入了现代密码学的阶段。在此之前的密码学都称为古典密码学。一切现有的现代密码学的加密方法，几乎都是由古典密码学加密方法的组合而来的。所以研究古典密码学，能对现代密码学的加密、解密以及破解有很高的帮助。在这里，我们对古典密码学中的经典之作“ADFGX加密法”进行进一步的改善，来管窥一下古典密码学的奥妙所在。

　　关键词：密码学古典密码学ADFGX加密法Polybius方阵

　　中图分类号：B81文献标识码：A文章编号：1674-098X（2013）05（b）-0217-03

　　1古典密码

　　古典密码，即密码术，它的历史极为久远。在计算机出现前，密码学，即古典密码学是基于字符的密码体制组成的。不同的密码算法是字符之间互相代换或者是互相之间换位，较好的密码体制是这二种方法的多次运算。

　　古典密码中流传下来的这些密码比较简单，但它们的破译是一切现代密码破译的基础。古典密码的破译采用归纳法与演绎法。步骤是：分析、假设、推测、最后证实或否定，该文将介绍几种典型的古典密码。

　　2ADFGX加密法

　　ADFGX加密的过程如下。将字母表中的字母放入一个5×5的矩阵（Polybius方阵），i和j作为同一个字母（由于Polybius时代的希腊字母为25个，所以最初的Polybius方阵使用25个字母刚好。此处ADFGX加密法是由德国人是用的，所以在德文中是讲i和j看做一个字母。行和列用字母A、D、F、G、X标记。例如，矩阵可以是：

　　每个明文字母都用它所在的行和列的标记替代。例如s变成了FA，z变成了DG。假设明文是

　　KaiserWilhelm

　　这一初始步骤（分解）的结果就是：

　　XAFFGGFAAGDXGXGGFDXXAGFDGA

　　目前位置可以看到，这是一个明显的替换密码。下一步极大地增加了复杂度。选择一个关键字（移位密钥，KEY），如Rhein。用这个字标记矩阵的列，把第一步的结果组成如下矩阵：

　　现在对列进行调整，使标记按照字母序排列；最后，按照列的次序来读字母（标记忽略），得到密文：

　　AGDFAFXFGFAX

　　XDGGGXGXGDGAA

　　只要知道了关键字，解密不难。关键字和密文的长度决定了矩阵每一列的长度。字母放入列中，调整次序和关键字匹配，再利用初始矩阵就可以恢复明文了。

　　初始矩阵和关键字要常变动，增加了分析的难度，因为对每一种组合只有有限数量的密文。但是，这个密码系统最终还是成功地被法国的密码专家GeorgesPainvin和BureauduChiffre破解了，并且破译了相当数量的消息。

　　3ADFGX加密法的改进

　　ClaudeShannon在其现代密码学的奠基性论文《Communicationtheoryofsecrecysystems（保密系统的通信原理）》中，给出一个好的密码系统抵抗统计分析所需的两条性质：扩散（diffusion）和混淆（confusion）。

　　扩散的意思是，如果明文的一个字符改变了，相应密文的几个字符也应该改变；同样，如果密文的一个字符改变了，相应明文的几个字符也应该改变。可以看到，Hill密码具有这一性质。这就意味着，明文中字母、双连字和三连字等的统计频率，扩散到明文中的多个字符中去了，这样进行一次有意义的统计攻击就需要更多的密文。

　　混淆的意思是，密钥不是和密文简单的相关。特别地，密文中的每一个字符应该依赖于密码的多个部分。例如，假设有一个n×n矩阵的Hill密码，已知n个足以解出加密矩阵的密明文对。如果改变密文的一个字符，矩阵的一列将会完全改变。当然，整个密钥都改变了更好。当这种情况出现时，分析者可能需要同时解决所有的密钥，而不是一段一段地逐个进行。

　　所以要对ADFGX加密法进行改进，可考虑的就是尽量多的扩散与混淆。故现在对ADFGX密码在古典密码学范畴下进行改进。总的来说，对于ADFGX密码，可以从以下三个方面进行改进。

　　（1）初始矩阵的生成。

　　（2）初始加密后密文的再次加密。

　　（3）横放纵取阶段的再次加密。

　　现在，我们开始就这三个方面开始陈述。

　　4ADFGX加密法的改进·初始矩阵的生成

　　由于ADFGX加密法，在最初使用时，是在开始使用前，制定好所有的初始矩阵并记录到密码本上，并规定好在什么时间段内使用哪个矩阵。所以只要保证记录矩阵的密码本的安全性，就能保证初始矩阵的安全性。

　　显然，这种方法在现在看来是非常不可靠的。在这里，我们可以用其他方法来生成初始矩阵。方法如下：

　　在现在的技术下，密文的发送与接收可以认为都是瞬间完成的。故，我们认定发送者与接收者是即时进行密文的传送。所以，我们记录下密文发送的月份α（α=1，2，…，12）与日期β（β=1，2，…，31），并构建仿射函数y=αxij2+β（mod36）。其中xij是来自矩阵

　　的第i行j列的元素，在此矩阵中，0～25表示英文字母a～z，26～36表示数字0～9。

　　即：

　　在本例中，我们选择2月20日，即α=2，β=20。我们按照行序开始运算，即从i=1开始，依次取j=1，2，…，6时的xij的取值。

　　下面将结果转成新的矩阵，具体步骤如下：

　　（1）x与y的值保持对应关系，按照x取值的升幂顺序开始进行操作。即，从初始矩阵中的x11=0位置处开始操作，此时，y=20。依次向下进行，将x的取值插到空白的y的取值所对应的地方。

　　（2）若x所对应的插入点已经填入过数字，那么，记录该点的行、列序。先按照同一列从上向下的顺序将x的值放入最开始的空白处；若列满，则按照同一行从左到右排列将x的取值放入最开始的空白处；若行也满，则移至下一行继续进行同一行从左到右排列将x的取值放入最开始的空白处；若新的行也满，则继续进行上一步，直至将该x的取值填到空白处。特别的，若已经进行到新矩阵的x66的位置处，则从x11的位置重新开始行的操作。在最终得到的新的矩阵中，仍然是0～25表示英文字母a～z，26～36表示数字0～9。

　　这就是本例中最终的初始矩阵。同时仍然用ADFGVX进行标记，则有：

　　5ADFGX加密法的改进·初始加密后密文的再次加密

　　假设，明文为：

　　God’’srightwiththeworld！

　　去掉标点与空格，为

　　godsinhisheavenallsrightwiththeworld

　　则，由示例中的初始矩阵可得（如表1）。

　　此时，用Vigenere加密法继续进行加密处理。我们将上一步得到的密文序列称为分解加密结果。示例中的分解加密结果为72个字符，由加密者自主选择一个关键字（KEY），我们在这称之为KEY-1。先确定密钥的长度，如6；再选择一个元素个数为6的向量，其中的元素是0～35的整数（避免重复），一般来说都可以对应一个英文单词，这可以是一个便于记忆的单词。在本例中，我们选取Wright作为KEY-1，此时，wright相应原始矩阵的向量为K1=（22，17，8，6，7，19）。

　　用这个密钥加密消息。首先，取第一个字母，移动22个位置，记下新位置在初始矩阵中对应的元素。然后，取第二个字母，移动17个位置，记下新位置在初始矩阵中对应的元素。以此类推继续下去。一旦到达密钥的末尾，我们就返回到密钥的第1个字母。在此过程中，始终进行（mod36）处理。则，得到第一阶密文如下：ZWNGHY2UI14TZCI1NWZCN1NYWUN14T2WLGKT2UOGHEZWL1NZ1UI1NZZCOMKE1CNJMT2RLGHY

　　ADFGX加密法的改进·横放纵取阶段的再次加密

　　再选取一个关键字（KEY），我们称之为KEY-2。这个关键字是加密者根据一阶密文的长度，也即明文长度的两倍选取，以其可以凑成的矩阵的行或列的个数两者中最大者为最小取值来确定。例如，在本例中，一阶密文可以凑成一个9×8阶矩阵，于是我们可以选择一个元素个数为9的向量，其中的元素是0～35的整数（避免重复），一般来说都可以对应一个英文单词，这可以是一个便于记忆的单词。具体的，我们可以选择masterily作为KEY-2，其对应的向量为K2=（12，0，18，19，4，17，8，11，24）。

　　先构造一个9×9的空白方阵，里面共有81个元素。而我们在示例中得到的一阶密文为72位，这其中少了9个元素。

　　特此，我们要在开始构造的9×9的空白方阵中构造9个“挡板”（或称“漏格”）来弥补这9个元素的位置。构造方法，为最开始构造初始矩阵的方法，只不过在此处由6×6变成了9×9，而且只要得出位置即可。

　　故，整理后得到挡板位置为（13，19，20，20，31，38，52，65，67）

　　现在，横向将所得到的一阶密文填入到该矩阵中，遇到“挡板”则越过。同时，用刚才的KEY-2标记这个矩阵；然后，对列进行调整，使标记按照对应的0～35的顺序排列；最后，按照列的次序来提取字母（忽略标记与“挡板”），得到最终密文：

　　W1WLH1MMGZKW1RYCN421Z1G2I1TUZCHZINYW

　　GZOJHZC1TLNEL4UEUTNTWNGZIK2U1N2ONCNY

　　考虑到当输入内容过多，如若明文内容在648位（虽然一般的机密信息传输不会涉及如此多的信息，但是也不能排除此类情况的发生），则第一阶密文将达到1296位，即362，此时若KEY-2还是限制为36个不重复的组合，无法进行插入“挡板”的横放纵取阶段。所以此时要放弃KEY-2不能重复的限制。

　　具体操作为：当有两个及以上字母（或数字）重复时，对于第一个出现的首个重复的字母（或数字），将位于该字母（或数字）序列以后的字母（或数字）统一做+1处理。这样重复的字母（或数字）就比第一个出现的首个重复的字母（或数字）要“大”一个位数，故不再重复，且后面重复的字母就会位于第一个出现的首个重复的字母后面，即这些重复的字母（或数字）的出现的相对顺序不会改变，且后面的字母（或数字）的相对顺序也不会改变。在进行横放纵取阶段时也保留这些进行+1处理的字母（或数字），这样KEY-2有重复的结果与KEY-2无重复的结果不会有逻辑上的不一致。

　　在进行传输时，只需发出KEY-1、KEY-2与密文即可。其中，可将KEY-1、KEY-2结合到一起。例如，此例中，便可将KEY-1、KEY-2结合为Wright’smasterily来进行发送。解密时，进行逆过程操作即可。

　　作者：洪焘宇等