|
|
頻率分析解密法教程
頻率分析解密法最先是由阿拉伯人發明,用于破解那些比較簡單的單字母替換密碼(單字母替換就是指明文中的
每一個字母都用另外一個的字母來替換,比如說將明文中所有的字母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 - - - - - - - - - - -
也就是說,如果我們截取到密文,只需要解到密鑰出現之后,剩下的就可以按順序寫下去而不用再去猜測了. |
|
