Cata1yst's blog

祇今尚有清流月，曾照高王万马过

0%

古典密码学之词频分析

发表于 更新于 分类于 ，
发现自己词频分析还不是很懂的样子(路过的好心人快来浇浇我)

词频分析适用情况

​ 1、词频分析适用于一些代换密码。代换密码就是那种用代换的方法加密的密码。代换密码可以简单理解为明文和密文之间存在有一张表，每一个字母通过表变换后结果是唯一的。而我们词频分析的词频在这种表格变换下是不会改变的，这就给我们破译密码提供了入口（信息论还是什么理论里好像提到对于一个好的密码，攻击者无法从密文中获得明文的信息，所以说，这个代换密码就是👎辣）

​ 2、词频分析需要获得较大量的密文。因为词频分析的基础是频率的计算，带有统计学的因素，只有样本足够多，分析的结果才会准确。

单表代换的词频分析

​ 单表代换的分析比较简单(大概),用到的就是词频分析的基本手段。著名的单表代换密码有凯撒密码和仿射密码。

​ 首先说说词频分析的依据，在英语文章中，不同字母出现的频率是不同的，比如 $ C $ 出现的频率要远高于 $ X $ (怎么有一种四六级的痛 ？) 。如前所述，如果加密的是单表代换，是不会改变其频率的，例如我们对 $ hello $ 做位移为 $ 1 $ 的位移加密得到 $ ifmmp $ ，可以看到 $ l $ ， $ m $ 出现了两次，而 $ l $ 和 $ m $ 恰好是一组对应关系。

​ 糟糕的是，在足够长的英语文章中，每个字母出现的频率是一个定值（大多数字母还是不一样的），而这种性质也被反映在了单表代换后的密文中。换句话说，密文中某个字母的频率其实反映了它对应的明文字母的频率，这就好像一个被加密为 $ a $ 的 $ z $ 在大喊“我是 $ z $ ！”，你我们就可以很轻易地还原出它。下面给出26个字母出现的频率(方便起见写成了字典)：

1
word_frequency={'a':0.082,'b':0.015,'c':0.028,'d':0.043,'e':0.127,'f':0.022,'g':0.020,'h':0.061,'i':0.070,'j':0.002,'k':0.008,'l':0.040,'m':0.024,'n':0.067,'o':0.075,'p':0.019,'q':0.001,'r':0.060,'s':0.063,'t':0.091,'u':0.028,'v':0.010,'w':0.023,'x':0.001,'y':0.020,'z':0.001}

​ 当然了，单纯分析频率有时候不太有效，毕竟统计学规律还得看你的样本大小还有误差的事你把握不住，不过这么操作下来其实已经得到了相当一部分对应关系了，剩下的可以通过枚举判断解析明文的语义来确定。

多表代换的词频分析

​ 多表代换就是很多个单表代换 多表代换可以理解为同一篇文章，不同的地方用了不同的单表代换，这个就比单纯的单表代换复杂了。比如著名的维吉尼亚密码。

​ 多表代换之于单表代换的一个问题是多表代换有时候不同的明文会得到相同的密文（反之亦然），比如 $ hellohello $ 用密钥 $ ab $ 做维吉尼亚加密会得到 $ helloifmmp $ 。这个时候如果逐字分析，字母的频率就改变了（如原文 $ l $ 出现了四次但密文不存在重复四次的字母）。这是因为加密用到了两张表，其中奇数位字母用 $ a $ （0）加密，偶数位用 $ b $ （1），从而造成了一些重复。不过我们发现，如果已知密钥长度（换句话说就是知道用了几张表和哪些地方用了同一张表），那么我们可以利用单表分析的办法逐个还原密钥，所以现在压力来到了如何确定密钥长度上。

​ 比较可靠的用于确定密钥长度的方法有两个。

​ 首先是目测法 $ Kasisi $ 测试法，其原理是在密文中找到几个重复的字符串（长度最好大于3），然后计算这些字符串的间距，然后多次选取几个不同的字符串操作，最后求出这些间距的最大公因子。它的原理是，一篇文章中肯定存在几个相同的单词（比如 $ the $ ），我们假设两个 $ the $ 之间的距离是 $ s_1 $ ，再假设密钥长度为 $ k $ ，如果两个 $ the $ 恰好被加密成同样的密文,则说明 $ s_1 $ 是 $ k $ 的倍数。我们在获得多个 $ s $ 后求出它们的公约数，就很有可能是 $ k $ 了。

​ $ Kasisi $ 测试法​有一个小问题，就是比较难用计算机语言形容，导致我们想要编程解决问题时有些困难，于是我们有了第二个方法——重合指数法。

​ 重合指数法基于的事实是，对于足够长的英语文章，从其中取出两个相同字母的概率是一个定值。这个很好理解，因为字母出现的频率确定的，而这个重合的概率只和频率有关（其实还和文章字数有关，但是密码分析里默认明文和密文一样长了）。我们假设每个字母出现的频数​（划重点，不是频率哦）用​ $ f_i $ 表示，文章总字母数记为 $ n $ ，则

$$
Ic=\sum_{i=0}^{25}{\frac{f_{i}(f_{i}-1)}{n(n-1)}}
$$
​ 于是，如果密钥长度不太长的时候，我们可以先假定密钥长度k，然后对密文进行分割（ $ c_1 $ … $ c_k $ ），此时 $ c_i $ 就是单表代换的结果，我们计算它的 $ Ic $ ，得到 $ k $ 个 $ Ic $ 后计算平均值或者分别比较，如果和标准值比较近，说明预测准确。在确定了 $ k $ 以后，再对每一个 $ c_i $ 进行词频分析就可以得到它对应的密钥，最后再把这些密钥连起来就是整个加密方案的密钥。

[AFCTF2018]一道有趣的题目

1
2
3
4
5
6
7
8
9
10
11
The 26 letters a, b, c, ..., y, z correspond to the integers 0, 1, 2, ..., 25
len(key_a) = m
len(key_k) = n
c[i] = (p[i] * key_a[i % m] + key_k[i % n]) % 26

p is plain text, only lowercase letters are refered to.
c is encrypted text

I have appended the flag at the end of plain text, the format of which is like 'flagis......'
Now you have the encrypted text, Good luck!

​ 这里还有一个c.txt文件就不展示了，是一篇加密文章。

​ 题目看着像仿射密码，但是仿射密码的$key_a$和$key_k$是固定的而本题两个参数分别由一个循环构成。这个就很像维吉尼亚密码和凯撒密码的关系，维吉尼亚密码其实就是凯撒密码中位移量变成了某个周期性变量。那么本题的解法就应该和维吉尼亚密码分析一样，首先根据重合指数分析密钥长度。

​ 不过有趣的地方在于，这题中的两个参数是独立的，也就是说，假设$key_a$,$key_k$的周期分别为$a,k$，那么我们就可以得到$a*k$种加密公式(前提是里面没有重复)。

​ 我们通过指数分析得到$k*a$的预计值后，可以按照一般的解仿射密码的办法求解线性同余方程组来确定每一个$(a,k)$组合；当然此题中a,k都只有26种情况（考虑到仿射密码要求$a$,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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
import math
from itertools import *
from string import ascii_lowercase
#引入每个字母对应的期望频率
letters=ascii_lowercase
standard=(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.01,0.023,0.001,0.020,0.001)
assert len(standard)==26
#读入文章
cipher=open('c.txt','r').read()
#用来记录密文中词频的函数，返回一个列表
def count_letter(cipher):
    result=[]
    for i in letters:
        result.append(cipher.count(i))
    return result
#计算重合指数的函数
def IC(cipher):
    result=count_letter(cipher)
    ic=0
    for i in range(len(result)):
        ic+=result[i]*(result[i]-1)/(len(cipher)*(len(cipher)-1))#这个就是计算公式
    return ic
#爆破密钥长度
def break_len(cipher):
    possible_len=[] #用于存放可能的密钥长度
    for i in range(1,50): #大致估计密钥长度，一般10~30就足够了
        Ic__=[] #存放在密钥长度i下 被分割出来的各个子密文的重合指数
        for j in range(i):
            Fragment=''.join(cipher[i*t+j] for t in range(len(cipher)//i)) #对密文进行分割
            Ic__.append(IC(Fragment)) #计算子密文的重合指数并合并入列表Ic__
        Ic=sum(Ic__)/len(Ic__) #计算各个子密文Ic的平均值，避免因为偶然性出错
        if abs(Ic-0.065)<0.006: #和标准值比较，这里误差设置了0.006
            possible_len.append(i) #计算值和标准值相近的可以认为是一个合理的密钥长度
    return possible_len
#输出可能的长度后需要人工观察一下，也可以编程计算公因子
print(break_len(cipher))
possible_len=6
#解密脚本，key表示加密方案的key_a ; iv表示加密方案的key_k
def decrypt(cipher,key,iv):
    m=''
    for c in cipher:
        x=(ascii_lowercase.index(c)-iv)*inverse(key,26)
        m+=ascii_lowercase[x%26]
    return m
# 这是一个比较简便的算法，在已知密钥长度（不是很长）的情况下，如果选择爆破密钥，那么我们需要对用预测密
# 钥解密的字母进行统计，再把计算值和标准值进行对比，这样脚本就会很繁琐。所有我们仍然采用一个重合指数的
# 方式，但是由于每一个计算值和标准值存在一定的误差，计算重合指数中用到的乘法会放大这个误差，导致最终结
# 果不能正确反映我们猜测的密钥的合理性，所以我们把其中fi/n这一项换成了对应字母的标准频率，然后再将结果
# 和0.0065比较，免去了每次都要比对26个字母的麻烦
def frequence(cipher):
    result=count_letter(cipher)
    M=0
    for i in range(26):
        M+=((result[i]-1)/(len(cipher)-1))*standard[i]
    return M
#爆破密钥,返回的列表中的元素是元组，分别代表加密方案的两个参数
def break_key(cipher,key_len): #这里的加密公式是 c=k1*m+k2 mod 26
    possible_key=[]
    for i in range(0,key_len):
        fragment=''.join(cipher[j] for j in range(i,len(cipher),key_len)) #按照之前算出来可能的长度分割密文
        for k1 in range(26): # k1的可能区间
            if math.gcd(k1,26)!=1: #根据仿射密码的原理知道k1和26要互素
                continue
            for k2 in range(26): #k2的可能区间
                fragment__=decrypt(fragment,k1,k2) #先用猜测的密钥解密密文。然后对“明文”进行词频分析，如果正常说明猜测合理
                M=frequence(fragment__)
                if abs(M-0.065)<0.01:
                    possible_key.append((k1,k2))
    return possible_key
#main
key_set=break_key(cipher,possible_len)
key=[i[0] for i in key_set]
iv=[i[1] for i in key_set]
def get_flag(cipher,key,iv):
    m = ''
    key=cycle(key)
    iv=cycle(iv)
    for c in cipher:
        x = (ascii_lowercase.index(c) - next(iv)) * inverse(next(key), 26)
        m += ascii_lowercase[x % 26]
    return m
print(get_flag(cipher,key,iv))

一些题外话

​ 虽然现在有很多在线解密网站可以直接爆破类似的词频分析密码，但是呢，我还是觉得懂一点原理总是有好处的。毕竟说真的，咱学个觅🐎要是最后全是用一些网站工具包做题的话，就好像在用网站和工具包做题一样。而且貌似有些题目网上不一定找得到解密网站（比如上面那题）。顺便附上一个维吉尼亚解密网站

家人们，反转辣 ！ ta写那么多废话就是为了来推荐这个网站 （逃