维吉利亚密码密钥长度怎么确定
维吉利亚密码密钥长度怎么确定
定义
维吉尼亚密码（又译维热纳尔密码）是使用一系列凯撒密码组成密码字母表的加密算法，属于多表密码的一种简单形式。
描述
在一个凯撒密码中，字母表中的每一字母都会作一定的偏移，例如偏移量为3时，A就转换为了D、B转换为了E……而维吉尼亚密码则是由一些偏移量不同的恺撒密码组成。
为了生成密码，需要使用表格法。这一表格（如图1所示）包括了26行字母表，每一行都由前一行向左偏移一位得到。具体使用哪一行字母表进行编译是基于密钥进行的，在过程中会不断地变换。
图1.表格
图1.表格
例如，假设明文为：
ATTACKATDAWN
选择某一关键词并重复而得到密钥，如关键词为LEMON时，密钥为：
LEMONLEMONLE
对于明文的第一个字母A，对应密钥的第一个字母L，于是使用表格中L行字母表进行加密，得到密文第一个字母L。类似地，明文第二个字母为T，在表格中使用对应的E行进行加密，得到密文第二个字母X。以此类推，可以得到：
明文：ATTACKATDAWN密钥：LEMONLEMONLE密文：LXFOPVEFRNHR
解密的过程则与加密相反。例如：根据密钥第一个字母L所对应的L行字母表，发现密文第一个字母L位于A列，因而明文第一个字母为A。密钥第二个字母E对应E行字母表，而密文第二个字母X位于此行T列，因而明文第二个字母为T。以此类推便可得到明文。
长度确定
确定密钥长度主要有两种方法，Kasiski 测试法相对简单很多，但Friedman 测试法的效果明显优于Kasiski 测试法。
Kasiski 测试法
在英文中，一些常见的单词如the有几率被密钥的相同部分加密，即原文中的the可能在密文中呈现为相同的三个字母。在这种情况下，相同片段的间距就是密文长度的倍数。所以我们可以通过在密文中找到相同的片段，计算出这些相同片段之间的间距，而密钥长度理论上就是这些间距的公约数。
具体方法：搜索长度至少为3的相同密文段，记录这些相同密文端到起始点之间的距离（d1,d2,d3……），找出（d1,d2,d3……）的所有公因子，同样为了确保秘钥长度的准确性，我们在搜索另一至少长为3的相同密文段，重复上操作，最后找出他们共同的公因子，若公因子不唯一，则在采用下边的重合因子测试法确定密钥长度。
Friedman 测试法
首先我们要知道，对于一种特定的自然语言，如果文本足够长，那么各个字母出现的概率是相对稳定的。
以下是维基百科给出的英语的字母频率表：
| 字母 | 英语中出现的频率 |
|---|---|
| a | 8.167% |
| b | 1.492% |
| c | 2.782% |
| d | 4.253% |
| e | 12.702% |
| f | 2.228% |
| g | 2.015% |
| h | 6.094% |
| i | 6.966% |
| j | 0.153% |
| k | 0.772% |
| l | 4.025% |
| m | 2.406% |
| n | 6.749% |
| o | 7.507% |
| p | 1.929% |
| q | 0.095% |
| r | 5.987% |
| s | 6.327% |
| t | 9.056% |
| u | 2.758% |
| v | 0.978% |
| w | 2.360% |
| x | 0.150% |
| y | 1.974% |
| z | 0.074% |
然后我们需要知道重合指数（IC, index of coincidence）的概念。
重合指数表示两个随机选出的字母是相同的的概率，即随机选出两个A的概率+随机选出两个B的概率+随机选出两个C的概率+……+随机选出两个Z的概率。
对英语而言，根据上述的频率表，我们可以计算出英语文本的重合指数为
P(A)^2 + P(B)^2+……+P(Z)^2 = 0.65
利用重合指数推测密钥长度的原理在于，对于一个由凯撒密码加密的序列，由于所有字母的位移程度相同，所以密文的重合指数应等于原文语言的重合指数。
据此，我们可以逐一计算不同密钥长度下的重合指数，当重合指数接近期望的0.65时，我们就可以推测这是我们所要找的密钥长度。
举例来说，对密文ABCDEABCDEABCDEABC
首先测试密钥长度=1，对密文ABCDEABCDEABCDEABC统计每个字符出现的次数：
A: 4 B: 4 C: 4 D:3 E:3
那么对于该序列的重合指数就为：(4/18)^2 + (4/18)^2 + (4/18)^2 +(3/18)^2 +(3/18)^2 != 0.65
然后测试密钥长度=2，将密文ABCDEABCDEABCDEABC分解为两组：
组1：A C E B D A C E B
组2：B D A C E B D A C
我们知道如果密钥长度真的是2，那么组1，组2都是一个凯撒密码。对组1组2分别计算重合指数。
如果组1的重合指数接近0.65，组2的重合指数也接近0.65，那么基本可以断定密钥长度为2。
字母频度分析
在知道了密钥长度n以后，就可将密文分解为n组，每一组都是一个凯撒密码，然后对每一组用字母频度分析进行解密，和在一起就能成功解密凯撒密码。
上文已经说到，自然语言的字母频度是一定的。字母频度分析就是将密文的字母频度和自然语言的自然频度排序对比，从而找出可能的原文。
理论上文本长度越长，字母频度分析的效果更好。
本文使用 CC BY-NC-SA 3.0 中国大陆 协议许可
具体请参见 知识共享协议
本文链接：https://zyhang8.github.io/2019/10/13/cipher-exp1/