密碼學(xué)原理-篇1:重合指數(shù)

古典密碼學(xué)之所以被稱為古典,是因?yàn)閰^(qū)別于現(xiàn)代密碼學(xué)提澎,這些密碼理論雖然很有價(jià)值姚垃,但是現(xiàn)在很少使用。因此盼忌,學(xué)習(xí)古典密碼學(xué),主要是學(xué)習(xí)前人設(shè)計(jì)密碼的思路,和他們成功或失敗的歷史首懈。


多表替換密碼(Poly-alphabetic Shift Cipher,Vigenère Cipher)

為了較好地為信息加密华畏,古人發(fā)明了加密算法:維吉尼亞密碼(Vigenère Cipher)。其特點(diǎn)就是選用某一段字符串作為其密鑰跨嘉,并將密鑰重復(fù)若干次直到長度與明文相同川慌。

例如,用密鑰“THINK”加密明文"ATTACKATONCE"祠乃,就要將密鑰重復(fù)并得到密鑰排列"THINKTHINKTH"梦重。密鑰排列得到的一串字符,每個(gè)字符都代表將該位置的明文字母向后移動(dòng)某位亮瓷,從而得到密文琴拧。對(duì)于上述的"THINKTHINKTH"而言,用所需移位的數(shù)字表示就是“19,7,8,13,10,19,7,8,13,10,19,7”嘱支。

明文第一位(A)對(duì)應(yīng)密鑰排列的第一位(T)蚓胸,而T在字母表中排第19位(A是第0位)挣饥,就將明文的第一位字母(A)向字母表排序的后面移動(dòng)19位,由于A在字母表中排第0位沛膳,移動(dòng)完是第19位T扔枫,因此得到密文第一位字母(T);

明文的第二位(T)對(duì)應(yīng)密鑰排列的第二位(H)于置,而H在字母表中排第7位茧吊,就將明文的第二位字母(T)向字母表排序的后面移動(dòng)7位,由于T是第19位八毯,19向后7位是第26位搓侄,而字母表中最后一位字母Z是第25位,因此得到新的循環(huán)中的字母表第0位话速,于是得到密文的第二位字母(A)讶踪;

第三位同理能夠得到字母表中第27位,也就是B泊交。以此類推乳讥,最終將會(huì)得到密文"TABNMDHBBXVL"。

相較于邏輯推演生成密碼廓俭,維吉尼亞密碼還可以使用表格法生成密碼云石。

如下圖,對(duì)于明文的第三個(gè)字母T研乒,對(duì)應(yīng)密鑰的第三個(gè)字母I汹忠,于是使用表格中I行字母表進(jìn)行加密,得到密文第三個(gè)字母B雹熬。類似地宽菜,明文第六個(gè)字母為K,對(duì)應(yīng)密鑰的第六個(gè)字母T竿报,在表格中使用對(duì)應(yīng)的T行進(jìn)行加密铅乡,得到密文第二個(gè)字母D。以此類推烈菌,可以得到密文“TABNMDHBBXVL”阵幸。

加密表,圖片來自百度百科

可以看出芽世,使用表格法無論是加密還是解密侨嘀,都有著更低的學(xué)習(xí)成本以及更高的效率。這種密碼的高易用性和不錯(cuò)的強(qiáng)度讓它聲名顯赫捂襟。

維吉尼亞密碼以其簡單易用而著稱咬腕,同時(shí)初學(xué)者通常難以破解,因而又被稱為“不可破譯的密碼”(法語:le chiffre indéchiffrable)葬荷。這也讓很多人使用維吉尼亞密碼來加密的目的就是為了將其破解涨共。維吉尼亞密碼足夠地易于使用使其能夠作為戰(zhàn)地密碼纽帖。例如,美國南北戰(zhàn)爭(zhēng)期間举反,南軍就使用黃銅密碼盤生成維吉尼亞密碼懊直。北軍則經(jīng)常能夠破譯南軍的密碼。戰(zhàn)爭(zhēng)自始至終火鼻,南軍主要使用三個(gè)密鑰室囊,分別為“Manchester Bluff(曼徹斯特的虛張聲勢(shì))”、“Complete Victory(完全的勝利)”以及戰(zhàn)爭(zhēng)后期的“Come Retribution(報(bào)應(yīng)來臨)”魁索。

對(duì)包括維吉尼亞密碼在內(nèi)的所有多表密碼的破譯融撞,都是以字母的出現(xiàn)頻率為基礎(chǔ)的,但直接的頻率分析卻并不適用粗蔚。例如尝偎,如果’P‘是密文中出現(xiàn)次數(shù)最多的字母,則’P‘所代表的明文很有可能是’E‘(在明文為英文的前提下)鹏控,其原因在本文的第二章已經(jīng)論述致扯。由于在維吉尼亞密碼中,同一個(gè)明文字母可以被加密成不同的密文当辐,因而簡單的頻率分析在這里并沒有用抖僵。


然而,維吉尼亞密碼也有著很明顯的漏洞缘揪。如果我們知道了密鑰的長度裆针,那密文就可以被看作是交織在一起的愷撒密碼,而其中每一個(gè)都可以單獨(dú)破解寺晌。例如,上個(gè)例子中以”THINKTHINKTH“作為密鑰排列澡刹,這種情況下明文的第一位和第六位都將以密鑰字母’T‘加密呻征,它們的偏移量就是相同的。倘若明文足夠長罢浇,就可以選取所有模5同余的位上得到字母來組成一組愷撒密碼陆赋。

因此,對(duì)于一個(gè)明文足夠長嚷闭、密鑰長度為t的維吉尼亞密碼攒岛,至多需要將其按照模t同余的原則分解為t組平移密碼即可破譯。于是胞锰,破譯過程的核心便落在了如何取得t值上灾锯。

五、卡西斯基試驗(yàn)(Kasiski’s Method)嗅榕、弗里德曼試驗(yàn)和重合指數(shù)(Index of Coincidence)

為了求出密鑰長度t顺饮,可以利用卡西斯基實(shí)驗(yàn)和重合指數(shù)吵聪。卡西斯基實(shí)驗(yàn)的內(nèi)容很容易理解兼雄,不多做贅述吟逝。這里引用百度百科中的例子。

卡西斯基試驗(yàn)是基于類似the這樣的常用單詞有可能被同樣的密鑰字母進(jìn)行加密赦肋,從而在密文中重復(fù)出現(xiàn)块攒。例如,明文中不同的CRYPTO可能被密鑰ABCDEF加密成不同的密文:

????????密鑰:ABCDEF AB CDEFA BCD EFABCDEFABCD

????????明文:CRYPTO IS SHORT FOR CRYPTOGRAPHY

????????密文:CSASXT IT UKSWT GQU GWYQVRKWAQJB

此時(shí)明文中重復(fù)的元素在密文中并不重復(fù)佃乘。然而囱井,如果密鑰相同的話,結(jié)果可能便為(使用密鑰ABCD):

????????密鑰:ABCDAB CD ABCDA BCD ABCDABCDABCD

????????明文:CRYPTO IS SHORT FOR CRYPTOGRAPHY

????????密文:CSASTP KV SIQUT GQU CSASTPIUAQJB

此時(shí)卡西斯基試驗(yàn)就能產(chǎn)生效果恕稠。對(duì)于更長的段落此方法更為有效琅绅,因?yàn)橥ǔC芪闹兄貜?fù)的片段會(huì)更多。如通過下面的密文就能破譯出密鑰的長度:

????????密文:DYDUXRMHTVDVNQDQNWDYDUXRMHARTJGWNQD

其中鹅巍,兩個(gè)DYDUXRMH的出現(xiàn)相隔了18個(gè)字母千扶。因此,可以假定密鑰的長度是18的約數(shù)骆捧,即長度為18澎羞、9、6敛苇、3或2妆绞。而兩個(gè)NQD則相距20個(gè)字母,意味著密鑰長度應(yīng)為20枫攀、10括饶、5、4或2来涨。取兩者的交集图焰,則可以基本確定密鑰長度為2。??

除了卡西斯基實(shí)驗(yàn)蹦掐,我們也可以使用別的參數(shù)來描述猜測(cè)的t值是否準(zhǔn)確技羔。當(dāng)計(jì)算某個(gè)密文的重合指數(shù)(又名:重合概率Index of Coincidence)時(shí)卧抗,即相當(dāng)于求在某個(gè)密文中隨機(jī)無放回地抽取其中的兩位藤滥,這兩位的字母相同的概率。

對(duì)于一個(gè)由任意字母表所構(gòu)成的密文字母串而言社裆,其重合指數(shù)可以表示下圖:


圖片源自維基百科

其中c是歸一化系數(shù)拙绊,用于對(duì)不同字母表進(jìn)行歸一化處理(英語為26),n?下標(biāo)a是字母“a”出現(xiàn)在文本中的次數(shù),N是文本的長度时呀。重合指數(shù)也可以用求和的形式來表示:


圖片源自維基百科

我們已經(jīng)知道张漂,維吉尼亞密碼可以被分解為若干組平移密碼來破譯,而一個(gè)明文足夠長的平移密碼的重合指數(shù)接近0.0687谨娜。換言之航攒,如果我們選取某個(gè)t值,使得分組后的密文的重合指數(shù)接近0.065趴梢,則說明選取的t值與密鑰的長度是一致的漠畜。?

在一串無規(guī)律的字母中,我們隨意抽取兩個(gè)字母坞靶,由于每個(gè)字母被抽到的概率相同憔狞,因此抽取的兩個(gè)字母相同的概率為26*(1/26)^2=0.0385。如果是從一篇文章或者一句完整的話中抽取彰阴,此時(shí)的概率為P(a)^2+P(b)^2+….+p(z)^2=0.067瘾敢。這種特性是破譯密碼的一大關(guān)鍵,正常的單表替換尿这,其重合指數(shù)更接近于0.067簇抵,而像維吉尼亞密碼這類周期性多表替換,其重合指數(shù)更接近于0.0385射众。

這里引用維基百科中的例子進(jìn)一步闡述碟摆,為簡化描述,下文中“重合指數(shù)”全部指明文為英文時(shí)的情況:


作為使用IC的實(shí)際例子叨橱,假設(shè)我們截獲了以下密文消息:

QPWKA LVRXC QZIKG RBPFA EOMFL JMSDZ VDHXC XJYEB IMTRQ WNMEA IZRVK CVKVL XNEIC FZPZC ZZHKM LVZVZ IZRRQ WDKEC HOSNY XXLSP MYKVQ XJTDC IOMEE XDQVS RXLRL KZHOV

(分為五個(gè)字符只是一個(gè)電報(bào)慣例典蜕,與實(shí)際字長無關(guān)。)我們懷疑這是一個(gè)使用Vigenère密碼加密的英文密文罗洗,其中包含普通的A-Z分量和一個(gè)短的重復(fù)關(guān)鍵字愉舔,我們可以考慮密文“堆疊”成若干列,例如7列:

Q????P????W????K????A????L????V

R????X????C????Q????Z????I????K

G????R????B????P????F????A????E

O????M????F????L????J????M????S

D????Z????V????D????H????X????C

X????J????Y? ? ?E? ? B? ? ?I? ? ?M

T????R????Q? ?W????N????...????...

如果密鑰大小恰好與假定的列數(shù)相同伙菜,那么單個(gè)列中的所有字母都將使用相同的密鑰字母加密轩缤,實(shí)際上是一個(gè)簡單的愷撒密碼,應(yīng)用于隨機(jī)選擇的英文明文字符仇让。與它們相應(yīng)的密文字母組,盡管每個(gè)字母已被置換(移位對(duì)應(yīng)于密鑰字母的量躺翻,參考本文第四節(jié))丧叽,也應(yīng)具有類似于英語的頻率分布的粗糙度。

因此公你,如果我們計(jì)算每列重合指數(shù)IC踊淳,它應(yīng)該在0.067左右;另一方面,如果我們猜錯(cuò)了密鑰大杏爻ⅰ(也就是選錯(cuò)了列數(shù))脱茉,則其重合指數(shù)IC應(yīng)該在0.0385左右。因此垄开,我們分別計(jì)算當(dāng)密鑰大小從1到10時(shí)的 IC:

t取5或10的時(shí)候IC最接近0.067

從上圖可以看出琴许,密鑰長度t很可能是5.如果實(shí)際長度是5,那么當(dāng)長度取10的時(shí)候也會(huì)有較高的IC溉躲,原因是此時(shí)它的每列也對(duì)應(yīng)一個(gè)簡單的愷撒加密榜田。

在求得密鑰長度之后,通過窮舉密鑰字母的每一種可能取值(A到Z總共26種)锻梳,并且針對(duì)每一行求其在某一取值下重合指數(shù)箭券,重合指數(shù)最高的情況下該行最有可能為明文原文,此時(shí)的窮舉結(jié)果即為密鑰字母疑枯。以下是經(jīng)過解密后得到的明文:

MUSTC HANGE MEETI NGLOC ATION FROMB RIDGE TOUND ERPAS SSINC EENEM YAGEN TSARE BELIE VEDTO HAVEB EENAS SIGNE DTOWA TCHBR IDGES TOPME ETING TIMEU NCHAN GEDXX

從中可以讀出明文想要發(fā)送的信息為:

是否必須將會(huì)議地點(diǎn)從橋改到地下通道辩块,因?yàn)閾?jù)信敵方特工已被派去觀看橋頭會(huì)議.時(shí)間不變XX

在明顯的位置恢復(fù)了單詞劃分【S溃“?XX”顯然是“空”字符废亭,用于填充最后一組進(jìn)行傳輸。

整個(gè)過程可以很容易地打包成自動(dòng)算法來破解這些密碼屁魏。由于正常的統(tǒng)計(jì)波動(dòng)滔以,這種算法偶爾會(huì)做出錯(cuò)誤的選擇,特別是在分析短密文時(shí)氓拼。


以上內(nèi)容僅代表本人大學(xué)學(xué)習(xí)思考內(nèi)容你画,如有侵權(quán)及時(shí)刪除,歡迎討論和指教桃漾!

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末坏匪,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子撬统,更是在濱河造成了極大的恐慌适滓,老刑警劉巖,帶你破解...
    沈念sama閱讀 216,591評(píng)論 6 501
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件恋追,死亡現(xiàn)場(chǎng)離奇詭異凭迹,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)苦囱,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,448評(píng)論 3 392
  • 文/潘曉璐 我一進(jìn)店門嗅绸,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人撕彤,你說我怎么就攤上這事鱼鸠。” “怎么了?”我有些...
    開封第一講書人閱讀 162,823評(píng)論 0 353
  • 文/不壞的土叔 我叫張陵蚀狰,是天一觀的道長愉昆。 經(jīng)常有香客問我,道長麻蹋,這世上最難降的妖魔是什么跛溉? 我笑而不...
    開封第一講書人閱讀 58,204評(píng)論 1 292
  • 正文 為了忘掉前任,我火速辦了婚禮哥蔚,結(jié)果婚禮上倒谷,老公的妹妹穿的比我還像新娘。我一直安慰自己糙箍,他們只是感情好渤愁,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,228評(píng)論 6 388
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著深夯,像睡著了一般抖格。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上咕晋,一...
    開封第一講書人閱讀 51,190評(píng)論 1 299
  • 那天雹拄,我揣著相機(jī)與錄音,去河邊找鬼掌呜。 笑死滓玖,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的质蕉。 我是一名探鬼主播势篡,決...
    沈念sama閱讀 40,078評(píng)論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼模暗!你這毒婦竟也來了禁悠?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 38,923評(píng)論 0 274
  • 序言:老撾萬榮一對(duì)情侶失蹤兑宇,失蹤者是張志新(化名)和其女友劉穎碍侦,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體隶糕,經(jīng)...
    沈念sama閱讀 45,334評(píng)論 1 310
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡瓷产,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,550評(píng)論 2 333
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了枚驻。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片濒旦。...
    茶點(diǎn)故事閱讀 39,727評(píng)論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖测秸,靈堂內(nèi)的尸體忽然破棺而出疤估,到底是詐尸還是另有隱情,我是刑警寧澤霎冯,帶...
    沈念sama閱讀 35,428評(píng)論 5 343
  • 正文 年R本政府宣布铃拇,位于F島的核電站,受9級(jí)特大地震影響沈撞,放射性物質(zhì)發(fā)生泄漏慷荔。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,022評(píng)論 3 326
  • 文/蒙蒙 一缠俺、第九天 我趴在偏房一處隱蔽的房頂上張望显晶。 院中可真熱鬧,春花似錦壹士、人聲如沸磷雇。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,672評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽唯笙。三九已至,卻和暖如春盒使,著一層夾襖步出監(jiān)牢的瞬間崩掘,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 32,826評(píng)論 1 269
  • 我被黑心中介騙來泰國打工少办, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留苞慢,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 47,734評(píng)論 2 368
  • 正文 我出身青樓英妓,卻偏偏與公主長得像挽放,于是被迫代替她去往敵國和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子鞋拟,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,619評(píng)論 2 354

推薦閱讀更多精彩內(nèi)容