维吉尼亚多表替换加密术

所谓“替换加密术”就是用把普通信文中的文字符号替换成其他符号,其替换规则只有合法的通信者知道,以达到加密的目的。

西方国家大都使用拼音文字,文字符号较少,只有20来个字母和几个标点符号,所以很适合用替换法加密。替换法加密只是把单元转换,但密文中单元的位置没有改变。替换式密码亦有许多不同类型。如果每一个字母为一单元(或称元素)进行加密操作,就可以称之为“简易替换密码”或“单表加密”又称为单字母替换加密。如前述古罗马的凯撒密码,就是一种替换加密术。在凯撒密码中,对每一个字母都制定了一个唯一的替换符号——按字母表顺序排在它后n(一个固定的正整数))位的那个字母。这种加密方法被称为“单字母表替换加密”(monoalphabeticsubstitutioncipher),它很容易被前述的“频率分析法“破解。

于是,在1467年,多表替换密码由莱昂•巴蒂斯塔•阿尔伯蒂以圆碟的形式首次描述。字母群体为单元的加密则称为“多表加密”或“表格式加密”。单表加密只可在一个单元中使用同一种替换加密,而多表加密则可在一个单元使用不同的加密方式,明文单元映射到密文上可以有好几种可能性,反之亦然。

图1 维吉尼亚加密术所使用的字母表矩阵的一个例子

约翰尼斯•特里特米乌斯所著的《隐写术》中介绍了一种表格。1563年,乔瓦尼•巴蒂斯塔•德拉波尔塔在《书写中的隐蔽字符》描述了一个更复杂的混合字母版本。在一个多表替换密码中,会使用多个字母作为密码。为了加快加密或解密速度,所有的字母通常写在一张表格上,密码学上称作tableau。这种表格通常是26×26,因为这样才能放下全部26个英文字母。填充表格及选择下次使用的字母的方法,就是不同多字母替换密码之间的定义。多字母替换密码比单字母更难打破,因为其替换可能性多,密文要较长才可。用来加密和解密的维吉尼亚表格其中最著名的一种为吉奥万•巴蒂斯塔•贝拉索于1585年推出的维吉尼亚密码。它于1863年之前一直未被破解。法国人称它作“不能破译的密码”。(此密码曾被误以为由布莱斯•德•维吉尼亚所创,所以才叫作维吉尼亚密码。)维吉尼亚密码中,表格的第一行只需直接填上26个字母,然后以下每一行的字母都是向左偏移一格。(这叫作表格横移,数学上每一列同余26。)要用这种密码需要使用一个关键字来作为密钥。关键字每次用完就再次重复。假设关键字是“CAT”,明文的第一个字由“C”加密,第二个字由“A”加密,第三个则由“T”加密,然后再回到C加密,一直重复。然后按照右边的密码表加密,例如BALL用CAT作关键字时会加密至DAEN,可见即使是同一个“L”亦会加密至另一个字母。现实中,维吉尼亚密码的关键字非常长。

1863年,弗里德里希•卡西斯基少校发明了一种方法(在克里米亚战争前已由查尔斯•巴贝奇秘密并独立地发明),使得可以计算维吉尼亚密码中关键字的长度。这种方法需要较长的密文,因为其运作依靠找出常见的字(如THE))使用相同关键字(如ABC)的数量,因此,极短的密文难以用此办法找出。因此,即使在今天,如果在表格中使用混合表加密,或关键字是随机的,维吉尼亚密码理论上亦难以破解。但由于实际上很难用到这些方法,维吉尼亚密码的使用越来越少。其他著名的多字母替换加密包括:

格兰示菲特密码——与维吉尼亚密码相似,但由于整个密码只使用10个单元,因此关键字长度有限,很容易被破解。

博福特密码——这实际上就是维吉尼亚密码,除“tabula”改为向后偏移一格,数学上是等式为:密文=键-明文。博福特密码属于对等加密,即加密算法与解密算法相同。

自动密钥密码——它的密钥开头是一个关键词,之后则是明文的重复,以避免周期函数。

运动密钥密码,关键词从某些文章或名句中取出,因此可以非常长。

现代的流密码中可以看出,现代的多表替换加密都努力改进流密钥,使其尽可能的长及不可预知。