vigenere_cipher(维西尼亚)密码

Vigenere Cipher

凯撒密码
凯撒密码是一种简单的加密方法，即将文本中的每一个字符都位移相同的位置。

如选定位移3位：

原文：a b c
密文：d e f

由于出现了字母频度分析，凯撒密码变得很容易破解。
“如果我们知道一条加密信息所使用的语言，那么破译这条加密信息的方法就是找出同样的语言写的一篇其他文章，大约一页纸长，然后我们计算其中每个字母的出现频率。我们将 频率最高的字母标为1号，频率排第2的标为2号，第三标为3号，依次类推，直到数完样品文章中所有字母。然后我们观察需要破译的密文，同样分类出所有的字母，找出频率最高的字母，并全部用样本文章中最高频率的字母替换。第二高频的字母用样本中2号代替，第三则用3号替换，直到密文中所有字母均已被样本中的字母替换。” (0.0 厉害啊)

维吉尼亚密码分解后实则就是多个凯撒密码，只要知道密钥的长度，我们就可以将其分解。

如密文为：ABCDEFGHIJKLMN
如果我们知道密钥长度为3，就可将其分解为三组：

组1：A D G J N
组2：B E H K
组3：C F I M

分解后每组就是一个凯撒密码，即组内的位移量是一致的，对每一组即可用频度分析法来解密。
所以破解维吉尼亚密码的关键就是确定密钥的长度。
两种方法确定密钥的长度
一种是Kasiski测试法:确定两个相同字符串之间长度(至少为3)的公因数(目前用这个)
一种是重合指数法
定义公式：

pi(字母的出现频率--已知)

常用公式：xi为字母的频数，L为密文的长度

英语文本的重合指数为P(A)^2 + P(B)^2+……+P(Z)^2 = 0.065
利用重合指数推测密钥长度的原理在于，对于一个由凯撒密码加密的序列，由于所有字母的位移程度相同，所以密文的重合指数应等于原文语言的重合指数
假设使用维吉尼亚密码加密的密文串为y=y1y2...yn。将串y分割成m个长度相等的子串(m组)，分别为y1，y2，...，ym，这样就可以以列的形式写出密文，组成一个m×(n/m)矩阵。矩阵的每一行对应于子串yi,(每一行对应一组) 1≤i≤m

如果y1，y2，...，ym按如上方式构造，则m实际上就是密钥字的长度，每一组的CI值大约为0.065。

另外，如果m不是密钥字的长度，那么子串yi看起来更为随机，因为它们是通过不同密钥以移位加密方式获得的。对于一个随机串，其重合指数为0.038 (通过猜测密钥的长度,看是否接近0.065)

在知道了密钥长度n以后，就可将密文分解为n组，每一组都是一个凯撒密码，然后对每一组用字母频度分析进行解密，和在一起就能成功解密凯撒密码

首先对子密文段重各个字母的频率进行统计（记为fi, i∈a – z），查看字母频率分布统计概率表(记pi)，计算子密文段长度为n，使用公式

计算出M0，然后对子密文段移位25次，同样按照上述方法求出M1 — M25的值

根据重合指数的定义知：一个有意义的英文文本，M ≈0.065，所以找出M值接近0.065的移位数，就是秘钥中的对应字母

推荐网站 http://www.richkni.co.uk/php/crypta/vignere.php
解密很有用(0.0)

ps:
这篇文章虽然被分类到python中,但还没有用python实现 orz