River5tone

Vigenere破解

Programming Cryptography
字数统计: 2.7k阅读时长: 11 min
2018/10/10 Share

Vigenere破解

「密码系统应该就算被所有人知道系统的运作步骤，仍然是安全的」——奥古斯特·柯克霍夫

「敌人知道系统」——劳德·艾尔伍德·香农

​

写在前面：

这是一次有趣的维吉尼亚密码算法破解，也帮助我这一个python小白多少学习了python这个有趣的语言。

（全程）参考：

[1] https://blog.csdn.net/Ni9htMar3/article/details/53371817

[2] https://www.jianshu.com/p/3d2c73464a51

[3] https://blog.csdn.net/sarahduo/article/details/51236000

[4] 百度百科https://baike.baidu.com/item/%E7%BB%B4%E5%90%89%E5%B0%BC%E4%BA%9A%E5%AF%86%E7%A0%81/4905472?fr=aladdin#4_3

​

多表替换密码（Poly-alphabetic Shift Cipher,Vigenère Cipher)

用数字0-25代替字母A-Z，维吉尼亚密码的加密文法可以写成同余的形式：

img

​

pre：预备知识

​

1.卡西斯基试验

卡西斯基试验是基于类似the这样的常用单词有可能被同样的密钥字母进行加密，从而在密文中重复出现。

对于长段落此方法更为有效，因为通常密文中重复的片段会更多。

2.重合指数（弗里德曼试验）

重合指数（index of coincidence）用来来描述密文字母频率的不匀性，从而破译密码。

当计算某个密文的重合指数时，即相当于求在某个密文中随机无放回地抽取其中的两位，这两位的字母相同的概率。

对于一个由任意字母表所构成的密文字母串而言，其重合指数可以表示下图：

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

在一串无规律的字母中，我们随意抽取两个字母，由于每个字母被抽到的概率相同，因此抽取的两个字母相同的概率为26*（1/26）^2=0.0385。如果是从一篇文章或者一句完整的话中抽取，此时的概率为P(a)^2+P(b)^2+….+p(z)^2=0.067。这种特性是破译密码的一大关键，正常的单表替换，其重合指数更接近于0.067，而像维吉尼亚密码这类周期性多表替换，其重合指数更接近于0.0385。

​

3.频率分析

一旦能够确定密钥的长度，密文就能重新写成多列，列数与密钥长度对应。这样每一列其实就是一个凯撒，而此密码的密钥（偏移量）则对应于维吉尼亚密码密钥的相应字母。与破译凯撒密码类似的方法，就能将密文破译。

柯克霍夫方法，将每一列的字母频率与转换后的明文频率相对应而得出每一列的密钥字母。一旦密钥中每一个字母都能确定，就能很简单地破译密文，从而得到明文。

如果维吉尼亚字母表表格本身是杂乱而非按通常字母表顺序的话，那柯克霍夫方法就会无效，但卡西斯基试验和重复指数对于决定密钥长度仍旧是有效的。

​

破译（附代码）：

​

1.主程序部分
1
2
3
4
5
6
7
8
9
10
11
12
13
from Kasiski import kasiski
from KeyCrack import keycrack
from Decipher import decipher


def main():
    kasiski()
    keycrack()
    decipher()


if __name__ == '__main__':
    main()

​

关于程序入口：

对于很多编程语言来说，程序都必须要有一个入口，C，C++都需要有一个main函数作为程序的入口，也就是程序的运行会从main函数开始。而Python则不同，它属于脚本语言，不像编译型语言那样先将程序编译成二进制再运行，而是动态的逐行解释运行。也就是从脚本第一行开始运行，没有统一的入口。

一个Python源码文件（.py）除了可以被直接运行外，还可以作为模块（也就是库），被其他.py文件导入。不管是直接运行还是被导入，.py文件的最顶层代码都会被运行（Python用缩进来区分代码层次），而当一个.py文件作为模块被导入时，我们可能不希望一部分代码被运行。

if __name__ == '__main__'的意思是：当.py文件被直接运行时，if __name__ == '__main__'之下的代码块将被运行；当.py文件以模块形式被导入时，if __name__ == '__main__'之下的代码块不被运行。

运行Python程序的两种方式

  • python xxx.py，直接运行xxx.py文件

  • python -m xxx.py，把xxx.py当做模块运行

小注：

  1. 函数名需要小写

  2. 定义函数前面期望有两个空行

2.卡西斯基&重合指数攻击（kasiski）

遍历可能的密钥长度klen，将原文（无空白字符）分成klen列，即每行klen个字符。如果密钥大小恰好与假定的列数相同，那么单个列中的所有字母都将使用相同的密钥字母加密，即简单凯撒。尽管每个字母已被置换，也应具有类似于英语的频率分布的粗糙度（重合指数与字母本身是什么是否常用无关）。

因此，如果计算每列重合指数IC，它应该在0.067左右；反之，如果我们猜错了密钥大小（也就是选错了列数），则其重合指数IC应该在0.0385左右（计算公式在预备知识中给出）。我们可以列出密钥长度为1~10的重合指数，选择可能的进行接下来的分析。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# -*- coding: utf-8 -*-
import string


def kasiski():
    f = open("E:/now/Vigenere/vencode.txt")
    sec_msg = "".join(f.readlines())
    print("可能的密钥长度最大为：")
    for klen in range(0,10):
        r = 0
        for i in range(0,klen):
            s = sec_msg[i::klen]
            len_str = len(s)
            sum_a = 0
            for y in range(0,26):
                x = s.count(chr(97+y), 0, len_str)
                sum_a += x*(x-1)
            klv = float(sum_a)/(len_str*(len_str-1))#重合指数
            r += klv
        if klen:#非零
            r = float(r)/klen#求各列重合指数平均值
            if abs(r-0.0385) > abs(r-0.067):
                print(klen),
                print( '---------->'),
                print(klv)

小注：

  1. 引用文件名地址中不能有空格，应避免中文字符。

  2. join()函数

    语法：sep.join(seq)

    参数说明：
    sep：分隔符，可以为空。
    seq：要连接的元素序列、字符串、元组、字典。
    上面的语法即：以sep作为分隔符，将seq所有的元素合并成一个新的字符串。

    返回值：返回一个以分隔符sep连接各个元素后生成的字符串。

  3. range(n)遍历0~n-1

  4. 切片

    语法：[start : end : step]

    sec_msg[i::klen]表示每klen个字符取第i个。

  5. s.count(ch, start, end)，s.append(str)，f.readlines()。

3.拟重合指数破解密钥（keycrack）

已知密钥长度n时，可将密文分解成n组，每一组都是一个凯撒密码，然后对每一组用字母分析进行解密，最终和在一起即为正确密钥。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def keycrack():
    f = open("E:/now/Vigenere/vencode.txt")#获取密文
    
    #去除非字母字符
    sec_msg_temp = "".join(f.readlines())
    f.close()
    sec_msg = ""
    lenth = int(raw_input("请输入可能的密钥长度\n"))#输入上回得到的最可能的密钥长度
    for each in sec_msg_temp:
        if each in string.letters:#排除非字母符号
            sec_msg += each

    word = ["" for i in range(lenth)]#设置数组存放分组密文#分成lenth组
    for i in xrange(len(sec_msg)):
        word[i % lenth] += sec_msg[i]#按key长分组
    boom(sec_msg, lenth, word)#爆破

小注：

  1. raw_input

    Python 版本 2.x 中，raw_input() 会从标准输入（sys.stdin）读取一个输入并返回一个字符串，且尾部的换行符从末尾移除。

    python3里面已经把raw_input()给去掉了。在 Python 3 内，将 raw_input() 重命名为 input()，这样一来，无须导入也能从标准输入获得数据了。

  2. string.letters

  3. 字母 英语中出现的频率
    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%

  4. word = ["" for i in range(lenth)]字符串数组初始化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# -*- coding: utf-8 -*-
import string

Alphabet_boom = [0.082, 0.015, 0.028, 0.043, 0.127, 0.022, 0.020,
                 0.061, 0.070, 0.002, 0.008, 0.040, 0.024, 0.067,
                 0.075, 0.019, 0.001, 0.060, 0.063, 0.091,
                 0.028, 0.010, 0.023, 0.001, 0.020, 0.001]#字母频率


def boom(sec_msg, lenth, word):
    Mg = [[0.0 for i in range(26)] for j in xrange(lenth)]
    for group in range(lenth):#遍历key分组lenth
        f = [0.0 for i in xrange(26)]#统计频数
        for i in xrange(len(word[group])):
            f[ord(word[group][i])-ord("a")] += 1
        for key in xrange(26):#遍历分组内key26
            for each in xrange(26):  
                #遍历word内第lenth个分组字符串，计算 Mg[lenth][key26]=累加fp/n'#移位过程
                Mg[group][key] += f[(each+key)%26]*Alphabet_boom[each]/len(word[group])
    key = ""
    for i in xrange(lenth):
        max_ = max(Mg[i])#得到最大频数字母
        if max_ < 0.05:#若小于0.05，则表示错误
            print "none!"
            key += " "
            continue

        temp = []
        for j in xrange(26):
            if Mg[i][j] == max_:
                temp.append(chr(j+ord("a")))#将数字转换成相应字母
                print chr(j+ord("a")),
                print '---------->',
                print Mg[i][j]
        if len(temp) != 1:#多种可能情况
            key += '('+''.join(temp)+')'
        else:
            key += temp[0]
    print "key>>", key
    f=open("E:/now/Vigenere/key.txt", 'w') #将密钥写入文本
    f.write(key)
    f.close()

小注：

  1. Mg = [[0.0 for i in range(26)] for j in xrange(lenth)]二维数组初始化。

  2. chr将数字转换成字符；

    ord将字符转换成数字。

  3. xrange和range用法完全相同；

    所不同的是：

    range生成的是一个list对象；

    xrange生成的是一个生成器。

    要生成很大的数字序列的时候，用xrange会比range性能优很多，因为不需要一上来就开辟一块很大的内存空间。

4.解密密文文本

加密逆过程，Pi = Ci - Ki （mod 26）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# -*- coding: utf-8 -*-


def decipher():
    f = open("E:/now/Vigenere/key.txt")#打开密钥
    key = "".join(f.readlines())
    f = open("E:/now/Vigenere/vencode.txt")#打开密文
    text = "".join(f.readlines())
    str = 'abcdefghijklmnopqrstuvwxyz'
    keylen = len(key)
    tlen = len(text)
    plaintext = ''

    for i in range(tlen):#进行移位解密
        j = i % keylen
        k = str.index(key[j])
        m = str.index(text[i])
        if m < k:
            m += 26
        plaintext += str[m-k]#解密即加密逆过程，即-

    print(plaintext)
    f = open("E:/now/Vigenere/plaintext.txt", 'w') #将明文写入文件
    f.write(plaintext)
    f.close()

​

段段的例题：

​

密文：

fskhrdjpwledqptuugufutkqistuhrtngwlitkzsneguahbvwleogwaosmvirwkfisdjhgkjpjqoegpinuguidqcvwwptgwfptfvadmdfimkwcoshusmujhaamnvxrfgwnovtqelfodmltprspjpjmspmlrtighcetqixhfndaasgfinuwvhitvumcueryrufhgitkrriorhrntaoz

key：abcde

明文：
friendinthecomputerbusinesssentmethisiwonderwhatthenetworkservicescheckingmodementeredpasswordsforcrackabilityorfromthewallstreetjournalemailsnoopingisokintheeyesofthelawarecentusdistrictcourtdecisioninpennsylv

加空格：

friend in the computer business sent me this

i wonder what the network services checking modem entered passwords for crack ability or from the wall street journal email snooping is ok in the eye soft he law are cent us district court decision in pen nsylv

​

END.THX.

原文作者：OtterV

原文链接：https://otterv.github.io/2018/10/10/20181010Vigenere/

发表日期：October 10th 2018, 9:20:13 pm

更新日期：October 4th 2019, 7:18:15 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. Vigenere破解
    1. 1.1. 写在前面：
    2. 1.2. 多表替换密码（Poly-alphabetic Shift Cipher,Vigenère Cipher)
    3. 1.3. pre：预备知识
      1. 1.3.1. 1.卡西斯基试验
      2. 1.3.2. 2.重合指数（弗里德曼试验）
      3. 1.3.3. 3.频率分析
    4. 1.4. 破译（附代码）：
      1. 1.4.1. 1.主程序部分
        1. 1.4.1.1. 关于程序入口：
        2. 1.4.1.2. 运行Python程序的两种方式
      2. 1.4.2. 2.卡西斯基&重合指数攻击（kasiski）
      3. 1.4.3. 3.拟重合指数破解密钥（keycrack）
      4. 1.4.4. 4.解密密文文本
    5. 1.5. 段段的例题：
Total : 21
9101
2020
2019
2018
Blog EAT Binary Security for Reverse computer Programming Cryptography Reading Movie Pwn C ACM