【浅谈系列】对单表替换密码的攻击

4 minute read

Published:

quipqiup 用习惯了,让你自己手写一个单表替换密码的攻击,你还会写吗?

以前打 CTF 总习惯用 quipqiup,这次应用密码学作业要么手动分析要么交代码,没法用 quipqiup,于是查了一些资料,尝试写了代码。

0. 参考资料

1. 总述

古典密码本质就是若干次替换或是置换。单表替换密码,则是最简单的一种,定义不必赘述。

对于单表替换密码,有若干种分析方法,而本文试图对现存的若干种主流分析方法进行一个简单总结。

2. 字频分析

字频分析是对于单表替换密码最经典的分析方法。因为单表替换密码只用了一张表,因此字母的简单替换并不改变其语言上的统计特性。因此,我们可以断言,当被加密的英文文本足够长时,那么各个字母出现频率应该与一般英文文本中出现频率高度一致。

Wikipedia 我们可以获取一般英语文本中英文字母频率:

default_letter_frequency = {
    'a': 0.08167, 'b': 0.01492, 'c': 0.02782, 'd': 0.04253,
    'e': 0.12702, 'f': 0.02228, 'g': 0.02015, 'h': 0.06094,
    'i': 0.06966, 'j': 0.00153, 'k': 0.00772, 'l': 0.04025,
    'm': 0.02406, 'n': 0.06749, 'o': 0.07507, 'p': 0.01929,
    'q': 0.00095, 'r': 0.05987, 's': 0.06327, 't': 0.09056,
    'u': 0.02758, 'v': 0.00978, 'w': 0.02361, 'x': 0.00150,
    'y': 0.01974, 'z': 0.00074
    }

因此,我们可以找到密文中最高频的字母,将其视为 $e$,其次是 $t$,以此类推。

更进一步,我们可以使用两个连续字母的频率,甚至三个、四个。

但如果所给的密文不算很短也不算很长,那怎么办呢?

由于不短,如果手动分析计算,比较花费时间精力;由于不长,语言上的统计特性可能并不恰好是英文文本的标准的那个字母频率,可能某几个对应关系无法准确确定。因此,如果我们依然使用字频分析,并手动来做的话,会花费大量时间精力。

阅读相关 参考资料,我学习并了解了一些其他方法。阐述如下。

3. Hill ClimbingSimulated Annealing

Hill Climbing 思想很好理解。简单来说它和我们在机器学习或是最优化里常用的梯度下降是一个意思,就是如何从一个点出发,找到该点附近的局部最高点或最低点。它还有其他叫法,在 Decrypting classical cipher text using Markov chain Monte Carlo 与参考了这篇文献的 Solving substitution ciphers with markov chains in Python - Warsquid’s Blog 中,它被称为 Markov chain Monte Carlo。尽管叫法不同,但方法几乎一样。

Hill Climbing 算法的本质其实还是字频分析。它的主要思想我会在下面细说。

首先我们给出 n-gram 的定义。

n-gram,也就是 n 元组,它是指对于某种语言的文本,从文本中取 $n$ 个连续字母。它本身可以很好的体现某种语言的统计特性,比如在足够长的英文文本中,一元组出现最多的必然是 $e$,三元组出现最多的必然是 $the$。针对这道题目,我选择使用四元组,因为恰好可以从我列出的参考资料中,找到一个使用《战争与和平》处理好的四元组文本文件,quadgrams.txt,我们可以直接拿来用。而且毋庸置疑的是,从携带更多英文文本统计上的信息来看,四元组优于三元组,三元组优于二元组,二元组优于单个字母频率。

那么,对于一段文本,我们将它所有的四元组提取出来,根据英文文本中每个四元组应该出现的频率,用对数先对其频率处理后再相加。英文文本中一般不存在的四元组,我们将其设置为非常接近于 $0$ 的数,对数后得到一个非常非常大的负数。于是,所有的分数都是负数,分数越小,也就是负数越大,说明这段文本越趋近于随机字符串;分数越大,则越接近英文文本。综上我们可知,最终得到的结果,一定是分数最大的那个字符串。

然后我给出 Hill Climbing 算法的主要思想。

攻击者随机生成一个密钥,使用这个密钥尝试解密,对解密后的信息计算 n-gram score。然后,将其某两个字母互换,再计算 n-gram score。如果得到的分数变大,那说明这个新的字符串更有可能是明文,用它替换掉原来的字符串。不断进行下去,我们必然可以得到一个局部最优解,它的分数局部最大。

但问题来了,局部最优解不一定是全局最优解。于是,这就要用到模拟退火的思想。模拟退火的思想简单来说就是跳出局部最优,重新从某个点出发,或许能找到比先前的局部最优更好的解。

对于单表替换密码的密钥来说,如果我们得到一个局部最优解了,那我们应该重新开始,生成一个新的随机密钥,使得解密后的信息与局部最优解相比大幅度打乱,再寻找这个新的信息的局部最优解。如果我们多次寻找新的局部最优解,依然不能取代目前这个局部最优解,那我们可以认为,目前的这个局部最优解就是全局最优解。

但如果对于多峰函数,峰值过多的情况,模拟退火是否还好用呢?我暂时还没怎么思考过这个问题如何解决。在 模拟退火 - OI Wiki 里也提到了这个问题,但并没详细说怎么解决。

4. 遗传算法 Genetic Algorithms

遗传算法简单来说就是模拟遗传学上的生物进化论,从初始的一个种群开始,拥有携带基因的染色体的个体,每次迭代时染色体交叉、变异,然后根据适应度进行自然选择,如此不断迭代,达到最优解。细节可以自行搜索相关资料。

而用在分析单表替换密码里,它的思想其实和 Hill Climbing 类似,本质上还是字频分析。比如遗传算法的适应度,我们选择 n-gram score 作为适应度,来评判哪些基因要被淘汰,哪些要被保留。

细节不赘述,一个实现可以参考 Solving substitution ciphers with genetic algorithms - Warsquid’s Blog

但我个人认为,此处遗传算法不如带有模拟退火思想的 Hill Climbing 好用。

5. quipqiup 与其论文

CTF 的或多或少都用过 quipqiup 吧。作者好多年前在一个网站上公开过源码,不过那个网站已经无了。

作者论文倒是还可以查到,他说他用的是 dictionary attack,细节详见论文:Robust Dictionary Attack of Short Simple Substitution Ciphers

6. 代码实现

由于最近时间有限,此处我仅仅对 Hill Climbing 进行了简单实现,遗传算法的实现可以参考我列出的那个博客,字典攻击可以参考作者论文自行实现。

此处拿应用密码学第一次作业里的一道题做例子。

运行环境:

SageMath 9.2, Python 3.7.7

代码如下:

# Applied Cryptography Assignment (1)
# Task 1
# break a simple substitution cipher
# 2021.09.15, written by LiMinzhang
# in this code, I just use lowercase

from pycipher import SimpleSubstitution
from math import log10
import random
import string


# calculate default ngram using prepared text
class ngram(object):
    def __init__(self, datafile):
        self.default_ngrams = {}
        for line in open(datafile):
            key, count = line.split()
            self.default_ngrams[key] = int(count)
        self.key_length = len(key)
        self.key_sum = sum(self.default_ngrams.values())
        for key in self.default_ngrams.keys():
            self.default_ngrams[key] = log10(float(self.default_ngrams[key])/self.key_sum)
        self.floor = log10(0.0001/self.key_sum)    
        
        
    def calculate_score(self, text):
        score = 0
        for i in range(len(text)-self.key_length+1):
            if text[i:i+self.key_length] in self.default_ngrams:
                score += self.default_ngrams[text[i:i+self.key_length]]
            else:
                score += self.floor
        return score


# hill climbing and simulated annealing
def hill_climbing(cipher):
    text_ngram = ngram("quadgrams.txt")
    cipher = cipher.lower()
    testkey = list(string.ascii_lowercase)
    finalscore = float("-inf")
    finalkey = ""

    times = 0
    cnt = 0
    cnt_end = 100
    upper = 10
    record = {}

    while True:
        if cnt > cnt_end:
            return None
        cnt += 1
        if times in record:
            record[times] += 1
        else:
            record[times] = 1
        if record[times] > upper:
            return (finalscore, finalkey, SimpleSubstitution(finalkey).decipher(cipher))
        random.shuffle(testkey)
        testplain = SimpleSubstitution(testkey).decipher(cipher)
        testscore = text_ngram.calculate_score(testplain)
        count_end = 1000
        count = 0
        while count < count_end:
            a, b = random.randint(0, 25), random.randint(0, 25)
            tmpkey = testkey[:]
            tmpkey[a], tmpkey[b] = tmpkey[b], tmpkey[a]
            tmpplain = SimpleSubstitution(tmpkey).decipher(cipher)
            tmpscore = text_ngram.calculate_score(tmpplain)
            if tmpscore > testscore:
                testscore = tmpscore
                testkey = tmpkey[:]
                count = 0
            count += 1
        if testscore > finalscore:
            finalscore, finalkey = testscore, testkey[:]
            times += 1
        print ("Test {} finished.".format(cnt))


cipher = "EMGLOSUDCGDNCUSWYSFHNSFCYKDPUMLWGYICOXYSIPJCKQPKUGKMGOLICGINCGACKSNISACYKZSCKXECJCKSHYSXCGOIDPKZCNKSHICGIWYGKKGKGOLDSILKGOIUSIGLEDSPWZUGFZCCNDGYYSFUSZCNXEOJNCGYEOWEUPXEZGACGNFGLKNSACIGOIYCKXCJUCIUZCFZCCNDGYYSFEUEKUZCSOCFZCCNC"
result = hill_climbing(cipher)
if result:
    print ("------------------------")
    print ("Best score: {}".format(result[0]))
    print ("Best key found: {}".format(result[1]))
    print ("Plaintext is: {}".format(result[2]))
else:
    print ("ERROR")

题目信息如下:

EMGLOSUDCGDNCUSWYSFHNSFCYKDPUMLWGYICOXYSIPJCKQPKUGKMGOLICGINCGACKSNISACYKZSCKXECJCKSHYSXCGOIDPKZCNKSHICGIWYGKKGKGOLDSILKGOIUSIGLEDSPWZUGFZCCNDGYYSFUSZCNXEOJNCGYEOWEUPXEZGACGNFGLKNSACIGOIYCKXCJUCIUZCFZCCNDGYYSFEUEKUZCSOCFZCCNC

运行结果如下:

Test 1 finished.
Test 2 finished.
Test 3 finished.
Test 4 finished.
Test 5 finished.
Test 6 finished.
Test 7 finished.
Test 8 finished.
Test 9 finished.
Test 10 finished.
Test 11 finished.
Test 12 finished.
Test 13 finished.
Test 14 finished.
Test 15 finished.
------------------------
Best score: -972.1824432505555
Best key found: ['g', 'd', 'j', 'i', 'c', 'h', 'w', 'z', 'e', 'q', 'b', 'n', 'm', 'o', 's', 'x', 'v', 'y', 'k', 'u', 'p', 'a', 'f', 'r', 'l', 't']
Plaintext is: IMAYNOTBEABLETOGROWFLOWERSBUTMYGARDENPRODUCESJUSTASMANYDEADLEAVESOLDOVERSHOESPIECESOFROPEANDBUSHELSOFDEADGRASSASANYBODYSANDTODAYIBOUGHTAWHEELBARROWTOHELPINCLEARINGITUPIHAVEALWAYSLOVEDANDRESPECTEDTHEWHEELBARROWITISTHEONEWHEELE

对结果合理添加空格,得到明文如下:

i may not be able to grow flowers but my garden produces just as many dead leave sold over shoes pieces of rope and bushels of dead grass as anybodys and to day i bought a wheelbarrow to help in clearing it up i have always loved and respected the wheelbarrow it is the one wheele

Google 搜索了一下,发现来自于《塞缪尔·马奇班克斯论文集》,英文是 The Papers of Samuel Marchbanks,但这个人名并不真实存在,而是一个小说家作品里虚构的人物。

7. 其他

在论文 Decrypting classical cipher text using Markov chain Monte Carlo 中,作者使用 Markov Chain Monte Carlo 方法,除了对单表替换密码进行分析,还对古典密码中的置换密码进行了分析。细节详见该论文及相关研究。


声明:本文采用 CC BY-NC-SA 4.0 授权。

This work is licensed under a CC BY-NC-SA 4.0.