“不可破譯”的維吉尼亞密碼

• 前言
• 古典密碼分類
• 維吉尼亞為什么這么難破
• 選擇破解的密文
• 破解過程
• • 確定密鑰長度
  • 確定相對位移
  • 窮舉搜索密鑰

前言

這是本次專欄的第一部分——破解維吉尼亞密碼，先來介紹一下維吉尼亞密碼的歷史。

1553年，意大利密碼學(xué)家吉奧萬·巴蒂斯塔·貝拉索出版了他的密碼學(xué)著作《吉奧萬·巴蒂斯塔·貝拉索先生的密碼》（La cifra del. Sig. Giovan Battista Bellaso），里面詳細(xì)記錄了這種新的加密方式。

1586年，由法國密碼學(xué)家布萊斯·德·維吉尼亞對這種加密方式進行了一定程度上的優(yōu)化，所以后世誤認(rèn)為這種新的加密方式是維吉尼亞首先發(fā)明，是不是很像阿拉伯?dāng)?shù)字（doge）。

正如標(biāo)題所言維吉尼亞密碼一度認(rèn)為是不可破譯的。因為1917年，在著名的《科學(xué)美國人》雜志上，依然表達了這個觀點。

那么我們今天就來破破看看！！！

符號表示
P：明文空間，所有可能的明文組成的有限集
C：密文空間，所有可能的密文組成的有限集
K：密鑰空間，所有可能的密鑰組成的有限集

Enc：加密算法
Dec：解密算法

古典密碼分類

古典密碼名稱描述

凱撒密碼	對于26個字母，密鑰為3，明文字母向后移動3位
移位變換	對于26個字母，假設(shè)密鑰為k，則明文字母向后移動k位，即c=m+kmod26
仿射變換	有兩個密鑰a，b，c=am+bmod16，其中為了保證a可逆，所以gcd（a，26）=1
維吉尼亞密碼	多個凱撒密碼，假設(shè)密鑰為k1，k2…第一個用k1加密，第二個用k2加密如此循環(huán)

可以看出來不管是凱撒密碼，移位密碼，還是放射密碼都是單表代換，明密文一一對應(yīng)，而維吉尼亞密碼則是多表代換的典型例子。

維吉尼亞為什么這么難破

1.相比單表代換，維吉尼亞密碼加密過程由一個26×26的表格組成，橫坐標(biāo)為明文，縱坐標(biāo)為密鑰。

2.破壞了統(tǒng)計規(guī)律，我們知道單表代換是不會破壞統(tǒng)計規(guī)律的，假如一篇密文里k出現(xiàn)的概率最高，那么k對應(yīng)的明文可能是e、t等，因為在樣本數(shù)量足夠大時字母出現(xiàn)的概率具有規(guī)律性，e，t，a，o等出現(xiàn)概率最高，j，x，q，z出現(xiàn)概率最低。但是維吉尼亞密碼作為多表代換，同一個明文可能對應(yīng)不同的密文，無法利用統(tǒng)計規(guī)律攻擊。

3.確定密鑰長度困難，破解密鑰長度是破解密鑰乃至明文的關(guān)鍵，這也是多表代換密碼破譯比起單表代換困難的主要原因。

選擇破解的密文

krkpewxvftksopztecxvbuhfvycgxouflihoffptrcwffwhkcevxhiuzfposdvccyctpmjtbfymllctiwxtacsmjmoncwdnawjrwtjgjsuystvbxgvcmgczbqecllttfkjlacpfttjgeegtbvkfpmhjzqaxhvvpgxoeychrcwumchhyigixhqdciawunmjerefkekcozqttznfdjlopuyqhjgrjawcpfrgxhwiljgrgiycrqkiajfgvrlrxgkkghdbqnliaovzrltgafslacjvjexrwjrdzsvruprttfkwxfgrlstznnmjerdvjdlhkwwdngjfsawgjfunhitjcaykgrptzicibtwrcpycwbkxfibrqemivotvwdnotvldmvgicshbqkztmfqlzaxrqekntqefscmbqkfxguyzjaaorgccmcovrwxbckgdgonrqhxadcclbznjfdpzgegtgqawygxkgcjiasofqiecxvbdyageztjikvrxymqlapghcbcrtfgfdnhitjcaytqiknlsnwgrtbpfrlkwvvycraqicqnhpfrwbbizliasyfpawqqljslhqgktmccumgxmqlsemcvycsxovy

破解過程

1.確定密鑰長度——重合指數(shù)法
2.確定密鑰相對位移——重合互指數(shù)法
3.窮搜密鑰字——窮搜法
PS：變成語言python

確定密鑰長度

方法一：Kasiski 測試法
原理：兩個相同的明文段將被加密成相同的密文段，它們的位置間距假設(shè)為 σ，則σ≡0 （mod m）。因此搜索長度至少為 3 的相同密文段，記下其離起始點的密文段的距離為σ1，σ2，σ3…………，那么可以猜測 m 。

這是一個很考驗眼神的方法，從所示密文最后部分來看vy顯然重復(fù)出現(xiàn)了，兩個vy間的距離為6，后面可以驗證果然是6（攤手）。

方法二：重合指數(shù)法
原理：自然語言（以英語為例）的重合指數(shù)約為 0.065，而且單標(biāo)代換不會改變該值。

重合指數(shù)的計算：設(shè) X=x1 x2 x3…………xn 是一條 n 個字母的串，x 的重合指數(shù)記為Ic（x），定義為 x 中兩個隨機元素相同的概率。計算公式如下：$I_c(x)=\frac{{\sum }_{i=0}^N{f}_i(f_i?1)}{n(n?1)}$

在單表代換中，不會改變該值，也就是用相同密鑰字加密應(yīng)服從相同的重合指數(shù)。如果我們從 1 開始猜測密鑰字長度，根據(jù)密鑰字長度將所有用相同密鑰字加密的密文分組，按組計算重合指數(shù)，最接近 0.065 時密鑰長度即為我們所需的密鑰長度。

結(jié)論：密鑰長度為6時重合指數(shù)最接近0.065

確定相對位移

原理：密鑰字的相對位移實際上就是確定密鑰之間的相互關(guān)系重合互指數(shù)：設(shè) x=x1 x2 x3 x4…………xn 和 y=y1 y2 y3 ……yn是長度為 n 和 n的串，其重合互指數(shù)為從 x 和 y 中分別隨機選出一個元素且兩個元素相同的概率。

方法：計算重合互指數(shù)$M{I}_c(x,y)=\frac{{\sum }_{i=0}^{N}f{1}_i(f{2}_i)}{n1n2}$

考慮不同的密鑰字加密后密文串的重合互指數(shù)，設(shè)密鑰字為k=k1 k2 k3 ……kdC i 中的一個字母與 Cj 中的一個字母都是 a 的概率為 p0-kip0-kj其中 p0-ki 為密文 a 所對應(yīng)的明文字母出現(xiàn)的概率，同理計算 b，c，d……z.

MIc 取決于相對位移 ki-kj，因此可以利用此特點計算密鑰字 C1，C2，C3，C4，C5，C6 的相對位移猜測不同的密鑰字的相對位移 s（0~25）.如果 s 猜對了，則 MIc 應(yīng)該接近 0.065，這意味著找到了不同密鑰字加密的相同的明文字母，也就是找到了密鑰字之家安的相對位移。用 m 表示明文字母，c，C分別表示 Ci ，Cj 中 m 對應(yīng)的密文字母，那么有：m≡c-kj （mod26）m≡C-kj（mod 26)因此密鑰之間的相對位移體現(xiàn)在密文的相對位移上。


可以得到位移關(guān)系：
K1-k2=11
K1-k3=4
K1-k4=13
K1-k5=9
K1-k6=14

窮舉搜索密鑰

原理：我們通過第二步已經(jīng)知道了后五位密鑰字與第一位密鑰字的相對位移，因此我們從 a 開始窮搜第一位密鑰字，得出明文后觀察明文是否符合自然語言，符合則猜測正確。

可以得到，當(dāng)密鑰為crypto時明文：
I am a live here my beloved for the reason to adore you oh how anxious i have been for you and how sorry i am about all you must have suffered in having no news from us may heaven grant that this letter reaches you do not write to me this would compromise all of us and above all do not return under any circumstance sit is known that it was you who helped us to get away from here and all would be lostif you should show yourself we are guarded day and night i do not care you are no there do not be troubled on my account nothing will happen to me the national assemble will show leniency f are well the most loved of men be quiet if you can take care of yourself for myself i cannot write anymore but nothing in the world could stop me to adore

總結(jié)

以上是生活随笔為你收集整理的破解维吉尼亚密码的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。