《Cypher》第四章 维吉尼亚密码的破译原理及代码实现

Github仓库链接：https://github.com/ZzySlhbcf/Cypher-Decoder

一、从凯撒密码说起

1.1 简单介绍凯撒密码

Caesar密码是最早的单表代换密码，也是一种简单的位移密码。其基本思想为：通过把字母在字母表上向左（或向右）按照一个固定的位数进行偏移来实现加密和解密。

明文序列：Cypher

密文序列：EARJGT（明文右移2位）

用数学公式进行描述（右移）：Dn(x)=(x+n) mod 26，其中x为字母在字母表中的序号（A=0，B=1...Z=25），n为偏移量。

1.2 频率分析法

Caesar密码为单表位移加密，就是简单的将字母表整体偏移。也就是说26个不同的明文字母在偏移后对应的密文字母也是不同的，可以轻松得到密文字母的频率与其对应的明文字母频率是相同的（不存在不同明文对应相同密文来改变频率）。

假设"E"对应的密文为"A"，如果在明文中"E"为12%，密文中的"A"也为12%。

字母频率是指各个字母在文本中出现的频率，常被应用于密码学，尤其是可破解古典密码的频率分析。根据统计，在英语材料中最常出现的字母是e，大约占12~13%，出现最少的字母是z，不到0.1%。

移位密码、仿射密码和单表代换密码都没有破坏统计规律，所以我们可以直接根据字母的频率分析进行破解。

如果在密文中，如果"T"出现的次数最多，那么它很大概率对应"E"。

1.3 频率分析法的弊端

频率分析法是基于统计的，也就说如果样本过小，概率将会不准确。这时我们可以通过文章的结构或者语法来分析，英文中出现频率最高的单词是：the, of, and, a, to, in……如果在密文中出现最多次的字母组合很可能就是其中的一个，另外我们还可以通过分析辅元音在单个单词中的组合与占比来分析密文结构。

如上的所有分析都是基于一个条件的：密文没有破坏明文的字母频率，但是如果密文破坏了字母频率，例如不同明文字母替换为相同的密文字母或相同明文字母替换为不同密文字母，那么对于密文本身的频率分析将变得没有意义，这也就是多表代换密码一开始难以破解的原因之一。

二、维吉尼亚密码

2.1 维吉尼亚密码的加密原理

Vigenere密码是一种简单的多表代换密码，即由多个偏移量不同的凯撒密码构成。这些偏移量组成了密钥，如密钥"ACBZ"对应的偏移量组就是(1,3,2,26)。

注意："1 3 2 26"是根据游戏中的对照表（如下图所示），现实中"ACBZ"对应的应该是"0 2 1 25"，即"A-Z"对应"0-25"。本文是游戏中的内容为依据来编写代码，如需更正可自行修改。

现在假设我们的密钥为"cypher"，即偏移量组为(3,25,16,8,5,18)，而我们现在需要加密"i like playing games"。

1. 将密文中的空格删去，根据密钥长度从前往后进行进行分组[(ilikep)，(laying)，(games)]。

2. 每一组中的明文字母根据密钥对应位置的偏移量向右进行偏移，如第一组中的第2个字母"L"，对应偏移量为25得到密文，即En=(12+25) mod 26=K。

3. 对每一组进行如上操作得到密文为[(LKYSJH)，(OZOQSB)，(JZCJK)]。

这样我们就得到了密文"L KYSJ HOZOQSB JZCJK"。解密与加密步骤相同，偏移与加密相反即可，如加密是向右偏移，解密则向左偏移。

假设明文为E，密文为D，密钥为K，明文序列下标为i，则

D(i)=[E(i) + K(i mod len(K))] mod 26

E(i)=[D(i) - K(i mod len(K))] mod 26

2.2 维吉尼亚密码破译原理

在上一小节的示例"i like playing games"中可以看到，其中两个"i"被分别加密成了"L、Y"两个密文，而"l、y"被同时加密为"O"。这也就是说维吉尼亚密码会改变字母频率，字母频率分析法就没有作用了，即我们无法通过分析明文和密文结构来解密。

我们可以从密钥寻找突破点。每一组明文段都用相同的密钥，不难发现如果正好有三个相同字母组被分割到了不同组内的相同位置，那么他们的密文就是相同的。例如[(athe)，(abcd)，(bthe)]，选取任意一个长度为4的密钥，明文中的"the"按照上一节的步骤都会被加密成同一个密文。

由此我们可以确定解密的三个步骤：

1. 确定密钥的长度

2. 确定密钥的内容

3. 根据密钥恢复明文

三、确定密钥的长度

3.1 Kasiski测试

按照如上思路，分别获取两个相同密文段的首字母的下标，按照例子就是1和9。我们只要找到首字母的下标之差（9-1=8）中大于相同密文段长度（3）的最大公因数GCD即可，8的最大公约数为4，正好可以与密钥长度4对应上。

这种方法虽然简单但是是有漏洞的，不同的密文段有可能对应相同的明文段（密钥长度过长）。而且，如果找不到足够多的重复字母组，那么Kasiski测试也等于无用。想要这种方法奏效，就需要密钥长度适中。

3.2 重合指数法（Coincidence Index）

在一个正常语义的英文文本中，和一个无意义乱序的英文文本中，字母出现次数的统计特征是有明显差异的，可以利用这种差异来帮助我们自动化的破解密码。回到1.2中的字母频率图，拿其中频率最高的"e"举例子，字母e在英文文本中出现的概率约为12.68%。易得我们在文本内任选两个字母都是"e"的概率为12.68%^2。类似的，对于任一概率为P(i)的字母 i，随机选取两个字母后都是 i 的概率为P(i)^2。在一串无规律的字母中，我们随意抽取两个字母，由于每个字母被抽到的概率相同，因此抽取的两个字母相同的概率为26*（1/26）^2=0.0385。

这里我们定义重合指数CI，即某个密文中随机无放回地抽取其中的两位，这两位的字母相同的概率。

其中c是归一化系数，用于对不同字母表进行归一化处理（英语为26），n下标a是字母“a”出现在文本中的次数，N是文本的长度。重合指数也可以用求和的形式来表示：

一个明文足够长的平移密码的重合指数接近0.0687，而一段完全随机的文本中，重合指数更接近0.038。由此可以判断密码为单表代换还是多表代换，维吉尼亚密码并不是简单的单表平移密码，它是由明文每个位置的字母按照对应的偏移得来的。也就说只要把密文拆解开，按照下标 i mod m（密钥长度） 分组重新组合为m个密文序列，这些序列CI的平均值应该是接近自然语言的重合指数的。

假设密钥长度只有2，明文的奇数位是同一偏移量，偶数位也为同一偏移量。

接下来我们只需要测试出哪个m可以使密文均值CI接近0.0687即可，这个很大概率为密钥长度，可以用3.1的Kasiski测试进行测试。

四、确定密钥内容

4.1 Chi测试

在得到密钥长度m后，将密文按照下标 i mod m重新组合为m个密文序列。每组对应的明文只有26中可能性（每组的偏移量相等）。暴力穷举的范围从26^L一下子降到了26^m，虽然下降了很多，但是这个数字依旧很大。字频统计也不能用——因为每组内的密文都是间隔 m−1 个字母取到的，这就意味者每组的样本量很小，用组内的字频会导致结果失真。

再将目光放回1.2中的字母频率图，对于每一组密文，都有26种位移可能，其中正确的偏移会使其IC指数接近0.065。但是有一个问题，由于样本数量小，IC一样不准确。IC指数定义中两次抓取都是再密文中进行的，我们略微做出改变，一次抓取再密文段中，另一次抓取正常英语文本中，这样就可以缓解密文段样本数量小的问题。

这样计算出来的称为“拟重合指数”，就是 SUM(P(i)Q(i)) ，其中P(i)就是密文的某一种位移后得到的字母的频率，Q(i))就是字母的在自然语言中一般概率，也就是上面的26字母频率表。这个“拟重合指数”越大，说明两段文本的字母的分布律越相像，也就代表密文段越像自然语言。

经过如此操作，我们将穷举次数再一次减少到了26*m次，以这种方法普通人花些时间也可以成功解密。

4.2 拟重合指数法的步骤

1. 统计每组密文中每个字母的频数 f(0) 、 f(1)…f(25) 。

2. 计算每组密文的长度L，计算26个字母在该组中的频率分布 p(0) 、 p(1)…p(25) 。

3. 对序列p(i)进行偏移，得到26种排序。当位偏移量为 k 的时候，原本的排序就会变为 p(26−k) 、 p(27−k)…p(25) 、p(0) 、 p(1)…p(25−k) ，可将这种排序设为26维向量组。

4. 将26×L的向量组与1×26的自然语言字母概率进行卷积 Correlation(Pk,Q)=SUM[p((k+1) MOD 26)q(i)]，其中最大的值所对应的为该组密文的偏移量。

五、小试牛刀

密文序列：

"LAFLUIWOYWPADUFHSNBVSWVNDZQDUFRBPLUYQPLWLPHZRLUEDUBSYMIPRDIJHTYQUCUZYLKFRSKHZBUHULUEKPQFOYLYSSAMWOCWHZOLGDTDDPPOFDDTGOPYUDGWOYOSDRYKVVDVLAULRZYGWPLJZYQKYPTWVLJIAFHHSWOMUVDDAPLMJLUEPVLRNPDWFXWMQAFHZSEQCFAGQDFLJFLHLDSWCLMQLFXUBULBDUBVPVWFQHWYUHRHJGSOCUZZXAGFVLILQVAFDARKPQLZCQAGULJBUCZAMPL"

首先重合指数法得到最大的IC值所对应的密钥长度m=3

根据密钥长度对密文进行分组。

对每组密文段求其拟重合指数，并将其最大的拟重合指数所对应的偏移量记为该组的偏移量。

对每组进行如上操作后得到密钥列表，最后根据密钥解密即可。

明文：

I think that I can help  you to pass an hour in an interesting and profitable manner," said Holmes, drawing his chair up to the table. "I am fairly familiar with all forms of secret writings, and am myself the author of a trifling monograph upon the subject, in which I analyze one hundred and sixty separate ciphers. But I confess that this is entirely new to me.

六、结语

如果密钥是完全随机、与明文的长度一致且只使用过一次，维吉尼亚密码理论上是不可破译的。然而，这种情况下密钥本身而非密文便成了关键，这被称为一次性密码本。

最后以下图最左边的小故事结束本篇文章。

BEALE（比尔密码）
1885年的弗吉尼亚州，旅店店主Robert Moriss出版了一个小册子，里面讲述了他的一位客人让他保管的一些重要文件，但是那位客人再也没有回来取走它们的故事。这些文件包含了1份注释和3份密文，据说包含了被掩埋的黄金藏匿处的方位。第二份密文是以《独立宣言》作为密钥，已被破译，而其他两份至今仍未被破译。