|
|
频率分析解密法教程
频率分析解密法最先是由阿拉伯人发明,用于破解那些比较简单的单字母替换密码(单字母替换就是指明文中的
每一个字母都用另外一个的字母来替换,比如说将明文中所有的字母A都换成字母B),就福尔摩斯里面的跳舞的小
人就是一种变相的单字母替换密码.随着频率分析法在军事上的广泛应用,单字母替换密码术逐渐被淘汰,取而代
之的是多字母替换密码(多字母替换就是指明文中的每一个字母都用另外两个或以上的字母来替换).比较典型而
且存活了比较久的多字母替换密码术有维热纳尔密码(Vigenere cipher),这种密码术在TT所发的密码知识的帖
子里面就有,是一种过了很久才被破解的比较牛的密码(具体时间忘记了,好像是差不多2个世纪),有兴趣的朋友
可以去看看,还有就是国家财宝2里面的培菲密码(playfair cipher)也属于多字母替换密码的一种,如果大家有
兴趣的话我可以写一下关于这种密码的使用方法.
虽然频率分析解密法无法直接用来破解多字母替换密码,但是在破解的过程中,还是扮演着非常重要的角色,可以
说,要破解密码首先一定要会应用频率分析法,当然那种单纯的移位密码除外,如栅栏密码("rail fence" transposition)...
接下来这几个步骤就是在利用频率分析解密法解密的过程中,可能需要用到的分析方法.
1. 英文字母在文章里所出现的平均频率(单位: %)
a: 8.2 n: 6.7
b: 1.5 o: 7.5
c: 2.8 p: 1.9
d: 4.3 q: 0.1
e: 12.7 r: 6.0
f: 2.2 s: 6.3
g: 2.0 t: 9.1
h: 6.1 u: 2.8
i: 7.0 v: 1.0
j: 0.2 w: 2.4
k: 0.8 x: 0.2
l: 4.0 y: 2.0
m: 2.4 z: 0.1
这些数据是根据一些报纸跟小说的某些文章段落统计得来的,用来统计的段落样本总共有100362个字母,但这并
不能总结说任何文章的字母出现频率都是这样,只能当作一个平均数据作为参考. (曾经就有一位法国老兄写了
一本200页的法文小说La Disparition,里面没用到过字母e,有人翻译成英文之后,照样还是没有用到e)
2. 英文里由单字母组成的单词只有2个, a和i, 当密文里的词与词之间有空格分开的时候, 用这个方法可以很
容易判断出a和i的密文对应字母是什么.
3. 英文中的元音a,e,i,o,u可以跟大部份的其它字母组合成单词,而辅音字母则只能和其它的小部分字母组成单
词. 当你无法确定一个密文所对应的明文是元音字母还是辅音字母,可以使用这个方法,特别是在判断e跟t这两
个字母时特别有用,因为e跟t的出现频率差不多,而且又往往是你破解密码时需要最先破解的两个单词
4. 英文中最常出现的一些单词:
英文中最经常出现的3字母的单词是the, and
英文中最经常出现的2字母的单词是of, to, in, it, is, be, as, at, so, we, he, by, or, on, do, if, me, my, up, an, go, no, us, am
英文中最经常出现的重复字母是ss, ee, tt, ff, ll, mm, oo
5. 每个英文单词里面都至少含有一个元音字母,依照这个条件其实基本上就可以确定出所有元音字母所对应的
密文了.
6. 字母q有一个很独特的性质,就是一个单词里面,紧接着字母q后面如果有别的字母,那么那个字母一定是u.这
个规律不能应用于那些缩写的短语(QC, QA...)
7. 猜测加尝试. 对于单字母替换的加密方法,使用前面6个步骤去判断,基本上已经可以判断出大部份的字母所
对应的明文,接下来的那些只要靠猜测跟尝试就可以破解出来了
接下来这个密码是取自于<the code book>里面的一个例子,大家有兴趣的话可以先试试,下面有解法.
PCQ VMJYPD LBYK LYSO KBXBJXWXV BXV ZCJPO EYPD KBXBJYUXJ LBJOO KCPK. CP LBO LBCMKXPV XPV IYJKL
PYDBL, QBOP KBO BXV OPVOV LBO LXRO CI SX'XJMI, KBO JCKO XPV EYKKOV LBO DJCMPV ZOICJO BYS, KXUYPD:
"DJOXL EYPD, ICJ X LBCMKXPV XPV CPO PYDBLK Y BXNO ZOOP JOACMPLYPD LC UCM LBO IXZROK CI FXKL XDOK
XPV LBO RODOPVK CI XPAYOPL EYPDK. SXU Y SXEO KC ZCRV XK LC AJXNO X IXNCMJ CI UCMJ SXGOKLU?"
OFYRCDMO, LXROK IJCS LBO LBCMKXPV XPV CPO PYDBLK
解法与分析: (下面密文以大写字母表示,明文以小写字母表示)
首先列出各个字母在文章里出现的次数跟频率:
A: 3 0.9% N: 3 0.9%
B: 25 7.4% O: 38 11.2%
C: 27 8.0% P: 31 9.2%
D: 14 4.1% Q: 2 0.6%
E: 5 1.5% R: 6 1.8%
F: 2 0.6% S: 7 2.1%
G: 1 0.3% T: 0 0.0%
H: 0 0.0% U: 6 1.8%
I: 11 3.3% V: 18 5.3%
J: 18 5.3% W: 1 0.3%
K: 26 7.7% X: 34 10.1%
L: 25 7.4% Y: 19 5.6%
M: 11 3.3% Z: 5 1.5%
然后先找出密文里出现次数比较多的几个字母,这里依次是O, X跟P. 我们可以依照上面步骤1里面的字母出现频
率,来确定OXP这3个密文字母可能代表eta这3个明文字母,不过这时候不能马上就确定说O=e, X=t, P=a,因为并
不是所有的文章的字母出现频率都一定遵循着那个顺序,但我们可以先假设:
O = e, t 或者 a X = e, t 或者 a P = e, t 或者 a
这时候我们可以依照步骤2来确定出明文字母a所对应的密文字母是什么.因为文章中以单字母形式出现的单词有
X跟Y,由于X出现的频率要大于Y很多,所以我可以比较有把握的确定:
X = a Y = i
接下来我们可以依照步骤3来确定O跟P到底哪个对应e哪个对应t, 其实就只要确定O跟P哪个是元音哪个是辅音就
可以了.根据密文我们可以列出下面这个表,来表示O跟P分别在26个字母的前面或者后面所出现的频率:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
O 1 9 0 3 1 1 1 0 1 4 6 0 1 2 2 8 0 4 1 0 0 3 0 1 1 2
P 1 0 5 6 0 0 0 0 0 1 1 2 2 0 8 0 0 0 0 0 0 11 0 9 9 0
从上面的表中不难看出, O在不多数字母的前面跟后面都出现过,而P只在少部分的字母旁边出现,所以我们可以
确定O代表元音字母, P代表辅音字母,而且OO的重复字母组合在密文中出现了2次,根据步骤3跟4的双重保险,可
以比较有把握地确定:
O = e
(那么剩下的P究竟是不是代表t呢,这个等后面再分析)
既然我们已经确定出O所对应的明文就是e, 那么我们也可以用e的出现规律来确定出h所对应的密文.因为在英文
中,字母h经常是出现在字母e的前面,而很少在后面(如单词: the, then, they, them, there等等, h都是出现
在e的前面, 而且这些单词在普通的文章里出现的频率都比较高).所以根据密文我们可以再列出一个表:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
在O后面 1 0 0 1 0 1 0 0 1 0 4 0 0 0 2 5 0 0 0 0 0 2 0 1 0 0
在O前面 0 9 0 2 1 0 1 0 0 4 2 0 1 2 2 3 0 4 1 0 0 1 0 0 1 2
从表中可以看出字母B在O的前面出现了9次但在后面出现了0次, 所以我们可以比较肯定的就是:
B = h
接着我们先把已经确定的密文XYOB所对应的明文代入文章里面(注:大写字母是密文,小写字母是明文):
PCQ VMJiPD LhiK LiSe KhahJaWaV haV ZCJPe EiPD KhahJiUaJ LhJee KCPK. CP Lhe LhCMKaPV aPV IiJKL
PiDhL, QheP Khe haV ePVeV Lhe LaRe CI Sa'aJMI, Khe JCKe aPV EiKKeV Lhe DJCMPV ZeICJe hiS, KaUiPD:
"DJeaL EiPD, ICJ a LhCMKaPV aPV CPe PiDhLK i haNe ZeeP JeACMPLiPD LC UCM Lhe IaZReK CI FaKL aDeK
aPV Lhe ReDePVK CI aPAiePL EiPDK. SaU i SaEe KC ZCRV aK LC AJaNe a IaNCMJ CI UCMJ SaGeKLU?"
eFiRCDMe, LaReK IJCS Lhe LhCMKaPV aPV CPe PiDhLK
根据步骤4里面所说的"英文中最经常出现的3字母的单词是the, and", 再看看文章,可以发现Lhe出现了6次,而
aPV出现了5次,所以可以确定:
L = t P = n V = d
(这就是为什么刚才我在分析P的时候没有直接代入t, 因为我是在知道答案的情况下解这道密码的,呵呵,如果事
先不知道答案,我想我也会直接让P = t, 当然结论就是会得出一个错误的结果,所以就要重新再分析过了,解密
的过程中很容易就会出现这种错误的猜测,所以是一个很考耐心的过程)
在知道了LPV之后,我们再代入文章中:
nCQ dMJinD thiK tiSe KhahJaWad had ZCJne EinD KhahJiUaJ thJee KCnK. Cn the thCMKand and IiJKt
niDht, Qhen Khe had ended the taRe CI Sa'aJMI, Khe JCKe and EiKKed the DJCMnd ZeICJe hiS, KaUinD:
"DJeat EinD, ICJ a thCMKand and Cne niDhtK i haNe Zeen JeACMntinD tC UCM the IaZReK CI FaKt aDeK
and the ReDendK CI anAient EinDK. SaU i SaEe KC ZCRd aK tC AJaNe a IaNCMJ CI UCMJ SaGeKtU?"
eFiRCDMe, taReK IJCS the thCMKand and Cne niDhtK
解出了这么多,接下来的就不会很难了.
文中出现了Cn,根据步骤5,C必需是元音,所以可以确定C = o.
再来就是Khe, 从这里可以知道K代表的是t或者s, 但是我们已经确定出t了, 所以K = s.
再把C跟K代入最后一个句子,出现了taRes IJoS the thoMsand and one niDhts, 这里不难看出最后一句其实就
是tales from the thousand and one nights.
所以:
M=u I=f J=r D=g R=l S=m
所以我们可以得出密文跟明文的对照表如下:
明文: a b c d e f g h i j k l m n o p q r s t u v w x y z
密文: X - - V O I D B Y - - R S P C - - J K L M - - - - -
代入文章里:
noQ during this time shahraWad had Zorne Eing shahriUar three sons. on the thousand and first
night, Qhen she had ended the tale of ma'aruf, she rose and Eissed the ground Zefore him, saUing:
"great Eing, for a thousand and one nights i haNe Zeen reAounting to Uou the faZles of Fast ages
and the legends of anAient Eings. maU i maEe so Zoid as to AraNe a faNour of Uour maGestU?"
eFilogue, tales from the thousand and one nights
文章的大概意思已经出来了,最后就是再根据步骤7判断出剩下的密文所对应的明文了,像noQ代表now, Eing代表
king, Uour maGestU代表your majesty. 这里就不再一个一个说了
最终的结果是:
now during this time shahrazad had borne king shahriyar three sons. on the thousand and first
night, when she had ended the tale of ma'aruf, she rose and kissed the ground before him, saying:
"great king, for a thousand and one nights i have been recounting to you the fables of past ages
and the legends of ancient kings. may i make so boid as to crave a favour of your majesty?"
epilogue, tales from the thousand and one nights
明文: a b c d e f g h i j k l m n o p q r s t u v w x y z
密文: X Z A V O I D B Y G E R S P C F H J K L M N Q T U W
在最后我们可以发现密文的中含有AVOIDBYGERSPC, 在C之后就是按字母表的前后顺序排列下去FHJKLMN... 其实
这篇文章有一个密钥,那就是A VOID BY GEORGES PEREC.
我们之所以要加密我们的文章是因为我们不想信息在通信过程中被截取,导致秘密外泄,所以我们使用密码.但是
我们通信的初衷是要信息接收者知道我们要给他的信息是什么,如果信息没有被截取,安全地到达原定接收者手
里,但是他拿到加密的信息之后,却不知道是什么意思,那就没有意义了.
所以通信的双方必需有一个协议,那就是要知道什么密文对应什么明文,但是如果这种对应关系是没有规律的,那
通信的双方就必需花时间去背诵这个明文跟密文的对应表,而且一旦信息被截取,密码被破解,那么下次通信的双
方就又要重新制定一个新的密文明文对应表,然后又要花时间去背诵.所以通常情况下,通信的双方没有去制定整
个密文明文对应表,而是制定一个密钥,就好像本文中的A VOID BY GEORGES PEREC, 这样的话双方就不需要去记
住整个对应表,只要记住这个有意思的密钥,效率提高了许多.在解密的时候,只要先把密钥在规定的位置写下去(
本文是在第3个位置),然后把重复的字母去掉,后面剩下的就按照
字母表的顺序一个一个写下去就好.
明文: a b c d e f g h i j k l m n o p q r s t u v w x y z
密文: - - A V O I D B Y G E R S P C - - - - - - - - - - -
也就是说,如果我们截取到密文,只需要解到密钥出现之后,剩下的就可以按顺序写下去而不用再去猜测了. |
登录帐号可查看完整回帖内容
|
