友情提示:本文共有 4440 个字,阅读大概需要 9 分钟。
用一首著名的英文诗,手把手演示如何破解简单替换加密。
百家号不支持代码格式,文章里的代码排版都是乱的。
如果需要拷贝代码,可以去同名微信公众号。
上篇说到,李雷用凯撒加密,仿射加密给Kate写信,都被父母轻松破解了。
李雷只好放大招,使用了简单替换加密。
因为简单替换加密有403291461126605635584000000个不重复的秘钥!即使电脑一秒钟可以尝试1000万次,暴力破解也需要120万年。
在信里,李雷抄了一首著名的英文诗,加密之后如下。
有兴趣的话,可以先不看后面的内容,试着去破解它。
Tgm fiztgmqt usqtycam sc tgm klzru
Sq clt vmtkmmc rsfm ycu umytg
Vit kgmc S qtycu sc fzlct lf xli
Xmt xli ulc"t wclk tgyt S rlom xli.
Tgm fiztgmqt usqtycam sc tgm klzru
Sq clt kgmc S qtycu sc fzlct lf xli
Xmt xli ayc"t qmm nx rlom
Vit kgmc iculivtrx wclkscp tgm rlom fzln vltg
Xmt aycclt vm tlpmtgmz.
Tgm fiztgmqt usqtycam sc tgm klzru
Sq clt vmscp yeyzt kgsrm vmscp sc rlom
Vit kgmc S eryscrx aycclt zmqsqt tgm xmyzcscp
Xmt ezmtmcuscp xli gyom cmomz vmmc sc nx gmyzt.
Tgm fiztgmqt usqtycam sc tgm klzru
Sq clt qtzipprscp ypyscqt tgm tsumq
Vit iqscp lcm"q scusffmzmct gmyzt
Tl usp yc icazlqqyvrm zsomz
Flz tgm lcm kgl rlomq xli
Python实现简单替换加密?
简单替换加密的原理很简单。
就是给26个英文字母都挑选一个替换的字母。
字母A,可以从A~Z,26个字母里任意挑一个,有26种可能。
假设挑选了字母 X 来替换 A。
字母B,不能再挑选X,只能从剩下的25个字母里挑选,所以有25种可能。
……
以此类推,一共有
26*25*24*……*1 = 403291461126605635584000000种可能。
假设我们这次挑选的字母替换关系如下
我们用它来加密爱尔兰著名诗人叶芝的诗《当你老了》中的第一句
When you are old and grey and full of sleep
message = "When you are old and grey and full of sleep"
source = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
key = "XRMAFGZBWDCEHOIVLKTJNYSQPU"
entry = ""
for i in range(len(message)):
if message[i].isalpha():
if message[i].islower():
entry += key[source.find(message[i].upper())].lower()
else:
entry += key[source.find(message[i])]
else:
entry += message[i]
print(entry)
上面的程序,就是逐一遍历这句诗的每一个字母。
通过find函数找到字母在正常字母表source里的位置,
然后把它替换成密文字母表key里位置相同的字母。
可见,简单替换加密的实现很简单。
但是破解缺需要一些技巧。
第一招:字母频率
在例子中,诗句的原文
When you are old and grey and full of sleep
出现得最多的字母是 e,一共出现了6次,其次是字母 l,出现了4次。
而加密之后的密文
Sbfo pin xkf iea xoa zkfp xoa gnee ig teffv
出现的最多的字母是f,也出现了6次。
道理很简单,因为原文中所有的e都替换成了f。
所以,我们有了一个大胆的猜想,如果英文里,每个字母出现的频率是固定的。
比如说在所有的英文里,字母e是出现频率最高的,那么是不是只要找出密文里出现次数最多的那个字母,它对应的明文一定就是字母e呢?
这就是破解简单替换加密的第一招。
如下图,密码学家通过对海量的英文文章进行统计,发现26个英文字母出现的频率顺序如下。
ETAONRISHDLFCMUGYPWBVKJXQZ
不过,字母频率只能用来做参考。
比如上的密文
Sbfo pin xkf iea xoa zkfp xoa gnee ig teffv
f出现了6次,频率最高,对应 e,是正确的。
但是密文里出现次数第2多的是 e,如果按照字母频率的顺序,它应该对应字母 t,但实际上,它对应的明文是 l 。
很显然,文章越长,字母频率越准确,文章越短,不确定性就越大。
当然,也有例外。
比如在法文里,出现得最多的字母也是e,但是法国著名作家George Perec就写了一本小说《La Disparition》(消失),里面一个字母e都没有。
试着用第一招来破解
不妨试一试用字母频率来进行破解。
先把密文保存成文件 mail.txt
接下来就是统计密文里每个字母出现的频率
count = {}
with open("data/mail.txt") as fr:
lines = fr.readlines()
for line in lines:
for i in range(len(line)):
if line[i].isalpha():
if line[i].upper() in count:
count[line[i].upper()] += 1
else:
count[line[i].upper()] = 1
count = sorted(count.items(),key=lambda item:item[1],reverse=True)
result = ""
for i in count:
result += i[0]
print(result)
执行程序,得到密文里字母的频率排序是
MTCLSGZQYIURXFKVPAONEW
可以试着把密文里的每个字母按频率进行替换。
ETAONRISHDLFCMUGYPWBVKJXQZ
也就是说密文里的字母 M替换成 字母 E,密文里的字母 T 替换成字母 T ……
但是,最后破解出来的结果如下,显然不正确。
第二招:单词模式
先来看例诗中的一个单词 sleep
如果我们用下面的方法来表示这个单词
第一个出现的字母 s,记为 0
第2个字母 l,和第一个字母不同,记为 1
第3个字母e,和前2个字母不同,记为 2
第4个字母 e,和第3个字母相同,所以还是记为 2
第5个字母 p,和前面的字母都不同,记为 3
所以,sleep 记为 01223
在我们的例子里,sleep经过加密之后,密文是 teffv
如果用同样的方法,teffv 也记为 01223。
我们称这种方法为单词模式
很显然,经过简单替换加密之后,单词模式并不会发生改变。
如果我们知道每个英文单词的单词模式,那么,是不是就可以通过单词模式进行破解呢?
这就是破解简单替换加密的第二招:单词模式。
当然,首先你得有所有的英文单词。
网上并没有现成的单词库,不过好在我们可以通过爬虫去爬取(爬虫的知识后面再介绍),如下,已经爬取好了16335个单词,并保存成了 dic.txt文件。
其次,还得把每个单词转成单词模式。
程序如下,其中 函数 calculate就是专门用来将单词转换成单词模式的。
def calculate(message):
dicTmp = {}
k = 0
result = ""
for i in range(len(message)):
if message[i] not in dicTmp:
dicTmp[message[i]] = k
k += 1
result += str(dicTmp[message[i]])
else:
result += str(dicTmp[message[i]])
return result
dic = {}
with open("data/dic.txt") as fr:
lines = fr.readlines()
for line in lines:
word = line.strip()
rs = calculate(word)
if rs in dic :
dic[rs] = dic[rs]+","+word
else:
dic[rs] = word
print(dic)
转换之后的效果如下。
我们看到,单词模式 0 ,只有单词 a 和单词 i 。想一想,一个字母就是一个单词的是不是就只有这2个字母。
再比如,单词模式是 0102342的只有一个单词 abandon
当然,我们也看到,有的单词模式有很多个单词,比如 01023
试着用第二招来破解
接下来,我们把密文文件 mail.txt 里的每一个单词转换成单词模式。
然后从单词库里去找相同单词模式的单词。
当然,我们先找那些一个单词模式只有少量单词的,比如先限制小于10个单词。
with open("data/mail.txt") as fr:
lines = fr.readlines()
for line in lines:
line = line.replace(",","").replace(".","").replace(";","").strip()
words = line.split(" ")
for i in range(len(words)):
re = calculate(words[i])
if re in dic and 0<= dic[re].count(",")<10:
print(re,words[i],dic[re])
执行程序,我们发现,有2个密文单词,找到了唯一匹配的明文单词。
分别是
ezmtmcuscp ,单词模式 0123245647,匹配的明文单词只有quarantine
scusffmzmct,单词模式01203345416 ,匹配的明文单词只有indifferent
根据这2个单词,就可以开始破解了。
先制作这样一个表格
根据第一个单词 ezmtmcuscp对应quarantine,可以填上
再根据第二个单词scusffmzmct,对应indifferent,可以继续补充
但是,发现这2个单词破解出来的字母映射关系不一致。应该怎么处理呢?
这时,第一招字母频率就可以发挥作用了。
密文中,字母出现次数排序是MTCLSGZQYIURXFKVPAONEW
而英文中字母出现次数排序是 ETAONRISHDLFCMUGYPWBVKJXQZ
从频率上分析,m对应的明文字母应该是e,t对应的应该是t,显然第二个单词更可信。所以,我们只保留第二个单词的字母映射。
接下来,继续看第三个密文单词tlpmtgmz 它的单词模式是01230435,可能的单词有三个sadistic,sidestep,together。
但是根据第二个单词已经整理出来的映射关系,t-->t,只有单词together满足要求。同时根据 tlpmtgmz --> together,又可以多得到 l --> o,p --> g,g--> h
以此类推,可以破解出
有了这么多字母的映射关系,其实可以试着去破解整首诗了。
密文的第一句是
Tgm fiztgmqt usqtycam sc tgm klzru
用已知的字母映射破解得到
The furthest distance in the wor?d
虽然,密文里字母r对应什么字母还不知道,但根据整个句子的意思,很容易就能猜到,完整的句子应该是
The furthest distance in the world
这首诗就是著名的《世界上最遥远的距离》。
关于这首诗的作者,一说出自张小娴的小说《荷包里的单人床》,另一说出自印度著名诗人泰戈尔诗集《飞鸟集》。
黔驴技穷的李雷
连理论上无法破解的简单替换加密都被破解了,你还能为李雷想到什么更安全的加密方式吗?
本文如果对你有帮助,请点赞收藏《27.Python密码学入门六:手把手破解一首简单替换加密后的英文诗》,同时在此感谢原作者。