维吉尼亚的破解

crypto

字数统计: 1.6k阅读时长: 6 min

 2016/04/04   Share

首先要说一句，这是我第一次用python coding，所以很多地方都不太懂，吐槽自己竟然用sum当变量名，之后有用sum()函数，然后报了错还不知道为什么。不知道用ascii码要做chr()转化，等等，还比如在重合指数函数和拟重合函数中可以提炼出一个共同的函数，但是我写完重合指数才发现，越改越乱所以就算了吧。但是我终于还是写完了，应该比C语言的代码少个几百行吧，我是不会说这篇文章，我从开始看原理到敲代码写了一天多。

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

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

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

重合因子测试法：利用随机文本和英文文本的统计概率差别来分析秘钥长度。设一门语言由n个字母构成，每个字母发生的概率为pi，1≤i≤n，则重合指数是指其中两个随机元素相同的概率，记为：

实际使用CI的估计值CI’: L:密文长度；xi：密文符号i发生的数目

下面就让我们拿个例子说一下吧。

这是一个使用维吉尼亚进行加密的密文段，从中选取一些一眼看到的重复字段，并计算相隔的距离。

import string
def findstr(str1,str2):
    a = 0
    r = []
    while a < len(str1):
        a = word.find(str2, a)
        if a == -1:
            break
        r.append(a)
        a = a + 1
    x = 0
    while x + 1 <len(r):
        print(r[x + 1] - r[x])
        x = x + 1
word = "密文段落"
findstr(word,'sxc')

通过计算，结果如下：

观察发现，大部分都有公因子7，基本可以推断密钥的长度为7.（如果公因子还有其他的，可通过重合因子测试法进一步确定密钥长度）

当然还可以通过重合指数法推断密钥长度：

#重合指数算法，str为文本，n为假设的秘钥长度，可以分别1-n密钥长度下的ic值，找到峰值ic对应的n的大小
def count_IOC(str,n):
    x = 0
    r = []
    ic_all = []
    while x < n:
        sum_all = 0
        c = str[x::n]
        len_str = len(c)
        for y in range(0,26):
            r.append(c.count(chr(97+y) ,0,len_str))
        for p in range(0,26):
            sum_all = sum_all + r[p] * (r[p] - 1)
        ic = float(sum_all)/(len_str * (len_str - 1))
        print(ic)
        ic_all.append(ic)
        x = x + 1
    return sum(ic_all)/ n
#假设猜测秘钥长度在10以下
for x in range(0,10):
    count_IOC(word, x)

结果如下，峰值为n = 7时，佐证了用kasiski测试法算出的秘钥等于7.

知道了密钥，下一步就是利用拟重合指数测试法了。

首先按照已知秘钥的长度，将密文7个一行7各一行进行分组，把每列作为一组进行分组，

#对密文进行分组（密文文本，第i组，秘钥长度）
def divstr(str, i, n):
    c = str[i::n]
    return c

拟重合指数测试法：首先子密文段重各个字母的频率进行统计（记为fi, i∈a – z），查看字母频率分布统计概率(记pi)，计算子密文段长度为n，

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

根据重合指数的定义知：一个有意义的英文文本，M ≈0.065，所以利用这个规律，就可以确定秘钥中的每一个字母。

#所有成员自增
def member_plus(r):
    m = []
    for i in r:
        if i == 'z':
            i = chr(96)
        m.append(chr(ord(i)+1))
    return ('').join(m) 
这里有必要说一下return('').join(p)，p是一个list，而我们需要的是个字符串，如果返回list，下边就会报错，因为python中有list.count(ord)和str.count(sub,,)函数。

#拟重合指数
def count_NIOC(i, c):
    p = [0.08167, 0.01492, 0.02782, 0.04253, 0.12702, 0.02228, 0.02015, 0.06094, 0.06966, 0.00153, 0.00772, 0.04025,
         0.02406, 0.06749, 0.07507, 0.01929, 0.00095, 0.05987, 0.06327, 0.09056, 0.02758, 0.00978, 0.02360, 0.00150,
         0.01974, 0.00074]
    len_str = len(c)
    r = []
    sum_m = 0
    for y in range(0, 26):
        r.append(c.count(chr(97 + y), 0, len_str))#统计字串中a-z的数量
    for x in range(0, 26):
        f = (r[x] * p[x]) / len_str 
        sum_m = sum_m + f
    print(i,sum_m)

#改变第二个参数：第几组子密文段，第三个参数：秘钥长度，分别计算秘钥中的各个字母
str0 = divstr(word,2,7)
for x in range(0,26):
    count_NIOC(x, str0)
    str0 = member_plus(str0)#每计算一次Mx，子密文段自加

以代码中的第3组为例对上文例题计算结果如下图：

可以看到x = 16时，M最接近0.065，所以x = 16 对应的字母q就是第三组密文的秘钥。

终于写完了，激动地快要哭了。很多地方纠结了很久，这个例题是网上下载的ppt里边的，也没有具体的答案，只能讲个大概的过程，书上对维吉尼亚的破解讲的也十分模糊，我只能尽力理解到这里了。

Next Post

hello world

CATALOG

