【科普】从单表代换到字频分析

从单表代换到字频分析——简单密码的常用分析手段 

一 为什么要写这篇专栏 

最近和几位dalao们一起解开了Steam上的解谜游戏《Alchemia》。谜题的主体是查资料、猜谜语、解密码。

由于《Alchemia》的设定是在1688年,所以其中的密码(从现在看来)是比较弱的,有时直接分析甚至比按书上的方法解密还要来的快。

扉页上写有MDCLXXXVIII

这篇专栏旨在进行一些和单表代换密码与常用分析手段的科普与推荐。

二 常见分析方法理论 

0 什么叫单表代换密码

“单表代替(Monoalphabetic Substitution Cipher)是密码学中最基础的一种加密方式。在加密时用一张自制字母表上的字母来代替明文上的字母来达到加密。” 

常见的凯撒密码(Caesar Cipher)就属于单表代换密码里面的移位密码。ROT13可以算是一种特殊的凯撒密码。埃特巴什(Atbash)密码还有各种用符号代替指定字母的密码也属于单表代换密码。

另外注意,维吉尼亚密码(Vigenère Cipher)是常见的表代换密码。

1 密码缺陷及对应的破解方法

(1)保留频率

众所周知,英文中频率最高的字母是E。

如果密文中某一字母对出现频率特别高,则它对应的明文很有可能也是E(或者次频繁凡的T之类)。

破解方法:

英文中最常见的12个字母依次是ETAOIN SHRDLU,记住它。

截自《Alchemia》前作《Cypher》

密文长度越大,字频统计结果就会越接近这个顺序——所以密文长度极长的单表代换密码实际上是很弱的。

反之,密文长度比较短的话,字频统计的参考价值也会低一些。

(2)短词语、重复词

如果密文带有空格,就暴露了更多弱点。我们知道单字词只有I和A,所以如果密文里有单字就一定是A/I两者之一。

类似地,如果密文里有2/3/4字词多次出现,则有可能是TO/OF、THE/AND、THIS/WITH之类。

参考网页

https://en.wikipedia.org/wiki/Most_common_words_in_English

https://www.rypeapp.com/most-common-english-words/

频率最高的100个英文单词(部分)

破解方法:

用这种思路,可以推出A/E/H/I/O/T之类的字母对应的密文。

(3)长词语

密文中有很长(比如说SFJBCLJNTNANKM)的单词时,其内部的规律可能对于这个词几乎是唯一的。

方法:

这时用一些Word Pattern Finder就很容易找到对应的明文。

参考网页

https://design215.com/toolbox/wordpattern.php

唯一解RESPONSIBILITY

(4)双写字母,etc. 

这里与其说是缺陷不如说是分析技巧,一些积累下来的常识。

例1:一个四字词中间出现双写字母(即形如ABBC的词),“B”的明文几乎一定(>95%)是字母E或字母O;

例2:当双写字母出现在单词结尾时,几乎一定是SS或者LL(极少数情况下会是FF或者ZZ)。

还有一些其他的积累而成的小技巧,这里不一一列举。

2 破解时可以使用的工具

(1)英语能力

已知一个词的一部分(如_A_TIALL_)推出完整词语的能力和已知上下文,猜到中间词语的能力直接和解谜者的英语水平相关。

(2)Hangman Solver

Hangman是一种猜字游戏,我们从词的部分推理出整个词的过程也是某种意义上的Hangman,所以网络上关于Hangman的工具当然适用

如果查到符合条件的词特别多,可能目前还没法推断出这个词。

如果查询的词不存在,就表明目前的结果可能有错误,反思一下之前的假设是否正确。

参考网页

https://www.wordgamehelper.com/hangman-solver

http://www.hangman-solver.com/

立刻发现答案是PARTIALLY

(3)加密解密、编码解码工具网站

参考网页

https://cryptii.com/

体验感真的很好

Caesar Cipher选项可以遍历凯撒密码的所有移位;Alphabetical Substitution里面可以自定义单表代换密码,其默认设定是Atbash Cipher。

(除此以外,该网站还支持Base64、维吉尼亚密码(Vigenère Cipher)、波利比奥斯棋盘密码(Polybius Square Cipher)、ASCII、甚至是恩尼格玛(Enigma)等等)

参考网页

https://www.dcode.fr/en

也是很不错的工具网站

一个类似的网页。

(4)Word Pattern Finder

看起来很万能

具体详见上文。

三 实战分析——破解密码时对上述方法的应用

(剧透警告——下文含有游戏《Alchemia》的部分密码明文。)

(下文中只提取了破解《Alchemia》时用到的密码分析(Cryptanalysis)方法,所以看上去有时会有些不连贯。按破解时间排序。)

1 联想与Hangman Solver——第四段密文(部分)

两位数字...

用正常方法(文字线索)解了一半后,明文目前是这样的

还有不少空缺

这时候明文THE,SEARCHING比较容易猜到;对于那些没有什么把握的则可以用Hangman Solver查询一下:

查询一下就能找到明文词语KNOWLEDGE

KNOWLEDGE,DOUBTLESS都是这样查到的。


完成解密

最后的明文。

2 位移遍历——第五段密文

一瞬间有点无从下手?

简单观察,密文分8节,前7节都有7个字;每节之前有不同的星座符号,推测每节的加密(解密)方式略有区别。

“第五月的那人知道解密方法 / 关键是把连接数和单词相加”

观察文字提示中的“Connections plus word”,一个数+一个词,可能是移位密码?用第一节PDACNAW试一下... 

因为题干说“plus”所以选项用的是加密(Encode)

Shift=4,结果THEGREA,很有希望

第二段ITGVXUI

Shift=11,结果TERGIFT

“THE GREATER GIFT... ”,看来是对的

同理,枚举移位,最后的明文是“THE GREATER GIFT FRO[sic] GOD HAS SECRETED MANY WONDERS IN THE WORLD”,移位依次是4, 11, 7, 7, 7, 10, 17, 7. 

3 密文规律查询——第三段密文

第二个词好长啊...

暂且不确定是不是单表代换,字频分析也没法带来很大的突破。密文里有个13字词GENAFZHGNGVBA,试着用Word Pattern Finder查一下(思路:如果是单表代换,应该可以查到几乎唯一解;如果查不到,那就应该不是单表代换)

这是一个很大的进展!

GENAFZHGNGVBA=TRANSMUTATION

这时列一下明文—密文对照:

明文 A    I    M N O    R S T U

密文 N   V    Z A B     E F G H

是不是很连贯?容易发现,这是一个位移为13的凯撒密码(即ROT13)。

既然知道加密方式了,自然很容易推出明文:“WHILE TRANSMUTATION TO GOLD MAY HAVE ELUDED MANY GREAT”. 

4 常见词猜测与字频分析——《Cypher》3-2

很遗憾,《Alchemia》里面已经没有合适的例子了。

为了展示这种解题方法/思路,我们借用一下《Alchemia》的前作《Cypher》里面的一道题。

第三章《单表代换》第2题

我们的目标是解出OVWGJVZGJP的明文。

嗯... 首先因为有单字词C,所以密文C=I/A.

出题人很友好地给了每个字母出现的次数;X有29次,Z有24次,它们的明文可能是E和T.

再看到出现4次的三字词ZMX,ZMX=THE.

最后一行的两字词ZG=T_明显是TO,G=O.

最后一行UCZM=_ I/A T H,比较常见的合题的词是WITH. (如果怀疑的话,先假设正确,然后第二行UMCDM=WHI_H=WHICH,说明没有问题,顺便还得到了D=C)

有了U=W我们看倒数第二行UXJX=WE_E=WERE,J=R. 

哦对,第三行两字词VZ=_T=AT(C=I所以不能是IT),V=A. 

已经解了多少了?

OVWGJVZGJP=_A_ORATOR_,

很明显了吧——答案是LABORATORY. 

不明显的话就再多解几个单词

四  总结

单表代换密码几乎算是最基本的密码了(Simple Substitution),这里提到的操作也是相当基础的。对其进行合理且熟练的运用,可以适当的提高解题效率。

最后,《Alchemia》和《Cypher》都是很棒的解谜游戏,其中《Alchemia》偏硬核一点。如果你热爱解谜,我强烈推荐这两款游戏。

本文为我原创

-- --
  • 投诉或建议
评论