内容发布更新时间 : 2024/5/7 7:08:40星期一 下面是文章的全部内容请认真阅读。

背景了解

替代是古典密码中用到的最基本的处理技巧之一 。

替代密码是指先建立一个替换表，加密时将需要加密的明文依次通过查表，替换为相应的字符，明文字符被逐个替换后，生成无任何意义的字符串，即密文，替代密码的密钥就是其替换表 。

根据密码算法加解密时使用替换表多少的不同，替代密码又可分为单表替代密码和多表替代密码。

单表替代密码的密码算法加解密时使用一个固定的替换表。单表替代密码又可分为一般单表替代密码、移位密码、仿射密码、密钥短语密码。

多表替代密码的密码算法加解密时使用多个替换表。 多表替代密码有弗吉尼亚密码、希尔(Hill)密码、一次一密钥密码、Playfair密码。 多表替代密码

单表替代密码表现出明文中单字母出现的频率分布与密文中相同， 多表替代密码使用从明文字母到密文字母的多个映射来隐藏单字母出现 的频率分布，每个映射是简单替代密码中的一对一映射多表替代密码将 明文字母划分为长度相同的消息单元，称为明文分组，对明文成组地进 行替代，同一个字母有不同的密文，改变了单表替代密码中密文的唯一 性，使密码分析更加困难。

多表替代密码的特点是使用了两个或两个以上的替代表。著名的维吉尼亚密码和Hill密码等均是多表替代密码。

⒈维吉尼亚密码

维吉尼亚密码是最古老而且最著名的多表替代密码体制之一，与位移密码体制相似，但维吉尼亚密码的密钥是动态周期变化的。

该密码体制有一个参数n。在加解密时，同样把英文字母映射为0－25的数字再进行运算，并按n个字母一组进行变换。明文空间、密文空间及密钥空间都是长度为n的英文字母串的集合，因此可表示

加密变换定义如下：

设密钥 k=(k1,k2,?,kn), 明文m=(m1,m2,?,mn), 加密变换为： Ek(m)=(c1,c2,?,cn),

其中ci(mi + ki)(mod26)，i =1,2,?,n 对密文 c=(c1,c2,?,cn), 解密变换为：

Dk(c)=(m1,m2,?,mn), 其中 mi=(ci －ki)(mod26)，i =1,2,?,n ⒉希尔（Hill）密码

Hill密码算法的基本思想是将n个明文字母通过线性变换，将它们转换为n个密文字母。解密只需做一次逆变换即可。

⒊一次一密密码（One Time Pad）

若替代码的密钥是一个随机且不重复的字符序列，这种密码则称为一次一密密码，因为它的密钥只使用一次。该密码体制是美国电话电报公司的Joseph Mauborgne在1917年为

电报通信设计的一种密码，所以又称为Vernam密码。Vernam密码在对明文加密，前首先将明文编码为（0，1）序列，然后再进行加密变换。

设m=(m1 m2 m3 ? mi ?)为明文,k=(k1 k2 k3 ? ki ?)为密钥,其中mi,ki ∈(0,1), i≥1, 则加密变换为： c=(c1 c2 c3 ? ci ?) ,其中ci = mi Å ki , i≥1,

这里为模2加法（或异或运算） 解密变换为：

m=(m1 m2 m3 ? mi ?) ,其中mi = ci Å ki , i≥1,

在应用Vernam密码时，如果对不同的明文使用不同的随机密钥，这时Vernam密码为一次一密密码。由于每一密钥序列都是等概率随机产生的，敌手没有任何信息用来对密文进行密码分析。香农（Claude Shannon）从信息论的角度证明了这种密码体制在理论上是不可破译的。但如果重复使用同一个密钥加密不同的明文，则这时的Vernam密码就较为容易破译。

若敌手获得了一个密文c=(c1 c2 c3 ? ci ?) 和对应明文

m=(m1 m2 m3 ? mi ?) 时，就很容易得出密钥 k=(k1 k2 k3 ? ki ?) ，其中ki = ciÅ mi，i≥1。 故若重复使用密钥，该密码体制就很不安全。

实际上Vernam密码属于序列密码，加密解密方法都使用模2加，这使软 硬件实现都非常简单。但是，这种密码体制虽然理论上是不可破译的，然而 在实际应用中，真正的一次一密系统却受到很大的限制，其主要原因在于该 密码体制要求：

① 密钥是真正的随机序列； ② 密钥长度大于等于明文长度； ③ 每个密钥只用一次（一次一密）。

这样，分发和存储这样的随机密钥序列，并确保密钥的安全都是很因难 的；另外，如何生成真正的随机序列也是一个现实问题。因此，人们转而寻 求实际上不对攻破的密码系统。 ⒋Playfair密码

Playfair密码是一种著名的双字母单表替代密码，实际上Playfair密码属于一种多字母替代密码，它将明文中的双字母作为一个单元对待，并将这些单元转换为密文字母组合。替代时基于一个5×5的字母矩阵。字母矩阵构造方法同密钥短语密码类似，即选用一个英文短语或单词串作为密钥，去掉其中重复的字母得到一个无重复字母的字符串，然后再将字母表中剩下的字母依次从左到右、从上往下填入矩阵中，字母I，j占同一个位置。

题目：如何破解多表替代密码？（提示-先确定周期）

单表中的凯撒密码，字母的替换是整体移位，一般破解单表替换的密文，主要以字母出现的频率做频率分析和字母出现的顺序做模式检查，找出映射关系，破译简单的替换式密码。

对于多表的从凯撒密码拓展出来的维吉尼亚密码为例，根据老师的提示我们可以先通过任意比密钥长很多的加密信息找出对同一个单词或事件的加密后第一重复出现相同加密后的间隔，也就是确定明文中同样的字母序列使用密钥中同样的字母加密的周期，当然也有很小的可能是不同的明文字母序列通过密钥的不同部分加密后形成的相同密文，但是我们可以通过大量的数据或者限制范围很大程度的排除这种情况。

多表代换密码体制的分析方法主要分为三步：第一步确定秘钥长度，常用的方法有卡西斯基（Kasiski）测试法和重合指数法（Index of Coincidence）;第二步就是确定秘钥，常用的方法是拟重合指数测试法；第三步是根据第二步确定的密钥恢复出明文。

总之，第一步就是找出密文中重复出现一次以上字母，第二步就是通过这些重复出现的密文确定密钥的长度，第三步再进行频率分析，频率分析主要要注意特征比较显著的字母段，还要结合实际的情况分析明文中可能出现的高频字符串，当然还有英文语法中的单词，为了直观的感受也需要作出图表方便对比差异和规律性的波动。

Kasiski测试法：若用给定的m个密钥表周期地对明文字母加密，则当明文中有两个相同字母组在明文序列中间隔的字母数为m的倍数时，这两个明文字母组对应的密文字母组必相同。但反过来，若密文中出现两个相同的字母组，它们所对应的明文字母组未必相同，但相同的可能性很大。如果我们将密文中相同的字母组找出来，并对其相同字母数综合研究，找出它们的相同字母数的最大公因子，就有可能提取出有关密钥字的长度m的信息。

具体方法：搜索长度至少为3的相同密文段，记录这些相同密文端到起始点之间的距离（d1,d2,d3……），找出（d1,d2,d3……）的所有公因子，同样为了确保秘钥长度的准确性，我们在搜索另一至少长为3的相同密文段，重复上操作，最后找出他们共同的公因子，若公因子不唯一，则在采用下边的重合因子测试法确定密钥长度。

重合指数法（index of coincidence，又称一致检索法）是Wolfe Friendman于1920年提出的方法。首先利用Kasiski测试法猜测出密钥的长度，然后利用重合指数法进行验证我们的猜测对不对。

根据基本测试和计算，26个字母构成的一段有意义文字中，任取两个元素刚好相同的概率约为0.065，所以如果一段明文是用同一个字母做密钥加密的话，这个概率是不变的。

首先根据Kasiski测试法得到了一个猜测出来的密钥长度m=5。我们可以直奔主题验证m=5时的概率，但是也可以谨慎地从m=1开始验起。

验证m=1的情况方法如下：

首先将密文（按顺序）排成一列，两两选取字母（取遍所有可能情况），计算其相同的概率。当然像图中所述例子，用手算显然不是我们想要的，我们如果自己想算的话可以利用计算机程序。我们用“字母相同的次数”除以“总抽取次数”即可得这一概率。最后计算出来的结果是0.045，很显然它更接近0.038，而不是0.065。