學號：16030140019
姓名:?? 莫益彰
【嵌牛導讀】：凱撒密碼是一種簡單的加密方法，即將文本中的每一個字符都位移相同的位置。如選定位移3位：
原文：a b c
密文：d e f
由于出現(xiàn)了字母頻度分析，凱撒密碼變得很容易破解，因此人們在單一愷撒密碼的基礎上擴展出多表密碼，稱為“維吉尼亞”密碼。
【嵌牛鼻子】密碼學，計算機安全。
【嵌牛提問】維吉尼亞怎么破解，8位維吉尼亞是否可破？維吉尼亞算法的時間復雜度？
【嵌牛正文】
維吉尼亞密碼的加密
維吉尼亞密碼由凱撒密碼擴展而來，引入了密鑰的概念。即根據(jù)密鑰來決定用哪一行的密表來進行替換，以此來對抗字頻統(tǒng)計。假如以上面第一行代表明文字母，左面第一列代表密鑰字母，對如下明文加密:
TO BE OR NOT TO BE THAT IS THE QUESTION
當選定RELATIONS作為密鑰時，加密過程是：明文一個字母為T，第一個密鑰字母為R，因此可以找到在R行中代替T的為K，依此類推，得出對應關系如下：
密鑰:RE LA ?TI ?ONS ?RE LA TION ? SR ELA TIONSREL
明文:TO BE OR NOT TO BE THAT ?IS ?THE QUESTION
密文:KS ME HZ ?BBL ?KS ME MPOG AJ XSE JCSFLZSY
圖解加密過程:
????????在維吉尼亞（Vigenère）的密碼中，發(fā)件人和收件人必須使用同一個關鍵詞（或者同一文字章節(jié)），這個關鍵詞或文字章節(jié)中的字母告訴他們怎么樣才能前后改變字母的位置來獲得該段信息中的每個字母的正確對應位置。
維吉尼亞密碼的破解
維吉尼亞密碼分解后實則就是多個凱撒密碼，只要知道密鑰的長度，我們就可以將其分解。
如密文為：ABCDEFGHIJKLMN
如果我們知道密鑰長度為3，就可將其分解為三組：
組1：A D G J N
組2：B E H K
組3：C F I M
分解后每組就是一個凱撒密碼，即組內的位移量是一致的，對每一組即可用頻度分析法來解密。
所以破解維吉尼亞密碼的關鍵就是確定密鑰的長度。
確定密鑰長度
確定密鑰長度主要有兩種方法，Kasiski 測試法相對簡單很多，但Friedman 測試法的效果明顯優(yōu)于Kasiski 測試法。
Kasiski 測試法
在英文中，一些常見的單詞如the有幾率被密鑰的相同部分加密，即原文中的the可能在密文中呈現(xiàn)為相同的三個字母。
在這種情況下，相同片段的間距就是密文長度的倍數(shù)。
所以我們可以通過在密文中找到相同的片段，計算出這些相同片段之間的間距，而密鑰長度理論上就是這些間距的公約數(shù)。
然后我們需要知道重合指數(shù)（IC, index of coincidence）的概念。
重合指數(shù)表示兩個隨機選出的字母是相同的的概率，即隨機選出兩個A的概率+隨機選出兩個B的概率+隨機選出兩個C的概率+……+隨機選出兩個Z的概率。
對英語而言，根據(jù)上述的頻率表，我們可以計算出英語文本的重合指數(shù)為
P(A)^2 + P(B)^2+……+P(Z)^2 = 0.65
利用重合指數(shù)推測密鑰長度的原理在于，對于一個由凱撒密碼加密的序列，由于所有字母的位移程度相同，所以密文的重合指數(shù)應等于原文語言的重合指數(shù)。
據(jù)此，我們可以逐一計算不同密鑰長度下的重合指數(shù)，當重合指數(shù)接近期望的0.65時，我們就可以推測這是我們所要找的密鑰長度。
舉例來說，對密文ABCDEABCDEABCDEABC
首先測試密鑰長度=1，對密文ABCDEABCDEABCDEABC統(tǒng)計每個字符出現(xiàn)的次數(shù)：
A: 4 B: 4 C: 4 D:3 E:3
那么對于該序列的重合指數(shù)就為：(4/18)^2 +?(4/18)^2 +?(4/18)^2 +(3/18)^2?+(3/18)^2 != 0.65
然后測試密鑰長度=2，將密文ABCDEABCDEABCDEABC分解為兩組：
組1：A C E B D A C E B
組2：B D A C E B D A C
我們知道如果密鑰長度真的是2，那么組1，組2都是一個凱撒密碼。對組1組2分別計算重合指數(shù)。
如果組1的重合指數(shù)接近0.65，組2的重合指數(shù)也接近0.65，那么基本可以斷定密鑰長度為2。
在知道了密鑰長度n以后，就可將密文分解為n組，每一組都是一個凱撒密碼，然后對每一組用字母頻度分析進行解密，和在一起就能成功解密凱撒密碼。
上文已經說到，自然語言的字母頻度是一定的。字母頻度分析就是將密文的字母頻度和自然語言的自然頻度排序對比，從而找出可能的原文。
