百家號不支持代碼格式，文章裡的代碼排版都是亂的。
如果需要拷貝代碼，可以去同名微信公眾號。
上篇說到，維吉尼亞密碼不能通過暴力進行破解。
因為秘鑰的長度是不固定的，如果希望不被破解，只需要增加秘鑰的長度就可以了，當秘鑰長度是15位時，一臺每秒可以嘗試1000萬次的電腦也需要1000多萬年才能夠暴力破解維吉尼亞密碼。
同時，也不能像破解簡單替換加密那樣，通過計算字母出現的頻率，和字母的單詞模式來破解，因為經過維吉尼亞加密之後，字母頻率和單詞模式都變化了。
上一篇的最後，給了一首經過維吉尼亞加密之後的英文詩，這一篇，我們就來演示如何來破解這首詩。
SCRQUYMMSUOGHYMEOHEHHOGOXZKI
FYQCMINSSTGUWZCMGLAVR
BZKHEHJGZEMXINXUHVDXYOCQIMLWG
FYQCMIMSSNPYPDNMHEVZWUYR
CSQXOICNTAZWGFGOXBPQVRHZBWEFWGAPS
MSASLPHCISLFZJICSQILMOIRYO
HCIUYGRILXMAVCPBYMMMZJACYUDRNSSRMHO
HCIUYGRILTGWPIHWIKCYHCIQTBY
LIHAVRSJSVVMXINXUXCPRNLWIIRTGO
FYQCMICEWNAUDVZHNZHCIMPO
CSQXOICSPOMWWLBNSGPDZSJWSZBCDH
WIZZFZXBPMVVYLZGSQPROSVPTMIY
SCRQUYMOMGPGXEHLAVRNFFILCDVZEX
LBYTLPHZRXEVVXBPXPWNOCZWHEGZI
NSSVRMHSMQSQFDIHOWNFFZKDRATBOLYHWIH
NSSVRMHSMMMMZJACYUDRNSSRMHO
VJAGLBTXCXSNQODHVQUYZJSEFD
WIZZFZLYNOIWYPHCIMVM
CSQXOICYLFNQODHJRYXOILUGS
WIZZFZLYNOILYLFKIIAZZGLJ
VJAGLBTHYLHCWQTZGMNEOFI
NTZGLYVBJAMEVVXNZCHEHJDZSJWSCEPPRDIX
EVZEHDKZVGJTMMYYRDWVWCRMHRWIXBPKDRX
EVZEHDKZVCDPGSQTBBMHEVZACYR
破解維吉尼亞密碼的歷史故事
1854年，也就是在1553年貝拉索出版《吉奧萬·巴蒂斯塔·貝拉索先生的算術》之後整整300年，英國發明家,科學管理的先驅者查爾斯·巴貝奇宣布成功破解了維吉尼亞加密。但是他並沒有公布他的破解方法。
直到9年後的1863年，一位叫弗裡德裡希·卡西斯基的密碼學家獨立破解了維吉尼亞密碼，並發表了完整的破解方法，所以，後人習慣稱破解維吉尼亞密碼的方法為卡西斯基實驗。
但巴貝奇也不是在撒謊，後人在整理他生前筆記時，發現他的確早於卡西斯基就破解了維吉尼亞加密。關於巴貝奇，雖然在國內名氣並不大，但是在國外，甚至大多數人都認為他才是真正的計算機之父。巴貝奇的一生很有傳奇色彩，但就不在這裡展開了，有興趣的話可以百度百科。
下圖就是巴貝奇和他設計的計算機的前身「差分機」。
那麼巴貝奇或者說卡西斯基的破解方法是怎麼樣的呢？
其實現在看來，也就2招。
第一招：通過相同子串間隔確定秘鑰長度
還是上一篇的詩句為例，假設加密前明文如下
If you shed tears when you miss the sun you also miss the stars
我們選了一個新的秘鑰，加密之後得到的密文是
Jh bsv ukie vhesu zlfp bsv olwt vki twq cpw dptq pmtu wlf uwesu
看上去密文沒有什麼規律可循，但是仔細看，我們發現有2個子串是相同的。
Jh bsvukie vhesu zlfp bsv olwt vki twq cpw dptq pmtu wlf uwesu
這說明什麼呢？
一種可能，前後2個bsv對應的3個明文字母不同，每個字母對應的秘鑰也不同，機緣巧合之下，正好加密出了相同的密文。
比如說
abc 通過秘鑰 BRT 加密之後得到的密文是 bsv
xyz 通過秘鑰 EUW 加密之後得到的密文也是 bsv
另一種可能是，前後2個bsv對應的3個明文字母相同，每個字母對應的秘鑰也正好相同。
比如說，第一個是 abc 通過BRT加密所得，第二個也是 abc 通過BRT加密所得。
如果這樣的字符串只是偶爾出現，可能說明不了什麼問題。
但如果密文裡，出現了較多這樣重複的字符串，特別是字符串長度還比較長，那麼直觀猜測，這不太可能是不同的明文恰巧經過不同的秘鑰加密出相同的密文。
密碼學家們對此已經給出了嚴謹的證明，但我們不需要關心這個。只需要知道
如果密文裡出現長度大於3的相同子串，那麼它們很可能是由相同的明文經過相同的秘鑰加密得到的密文。
有了這個假設，就可以推測維吉尼亞秘鑰的長度了。
假設第一個 bsv對應的秘鑰是???
那麼第二個 bsv對應的秘鑰還是 ???
最直接的猜測是 ??? **** ***** **** 正好是完整的秘鑰，也即秘鑰長度為16。
Jh bsvukie vhesu zlfp bsv olwt vki twq cpw dptq pmtu wlf uwesu
??? **** ***** **** ??? **** ***** ****
不過仔細想一想，其實秘鑰的長度只要是16的因數就可以。
比如說秘鑰的長度是8，也能夠保證第2個bsv位置對應的秘鑰是相同的。
Jh bsvukie vhesu zlfp bsv olwt vki twq cpw dptq pmtu wlf uwesu
??? **** *???* **** ???
同理，秘鑰長度也可能是4,2,1。
所以，破解維吉尼亞密碼的第一招，就是在密文裡找相同的子字符串，並計算它們的間隔。
下面的程序，就是在密文裡找所有長度為6的子字符串，檢查密文裡有沒有相同的子字符串，並計算它們的間隔。
with open('data/poem.txt') as fr:
lines = fr.readlines()
poem=''
for line in lines:
poem += line
poemStr = ''.join(poem.split())
poemLen = len(poemStr)
subLen =6
result = {}
for i in range(poemLen-subLen):
subStr = poemStr[i:i+subLen]
if subStr in result:
continue
start = i+subLen
position = i
while start < poemLen - subLen:
compStr = poemStr[start:start+subLen]
if subStr == compStr:
if subStr in result:
result[subStr] = result[subStr]+','+str(start-position)
else:
result[subStr] = str(start-position)
position = start
start = start + subLen
else:
start += 1
print(result)
如上圖，執行程序，找到很多這樣的字符串。比如
'SCRQUY': '335' 說明'SCRQUY'出現了2次，2次中間隔了335個字符。
'FYQCMI': '50,175'，說明'FYQCMI'出現了3次，分別隔了50和175個字符。
觀察所有這些重複出現過的字符串的間隔，很容易發現，公因數是5。
所以，這次維吉尼亞秘鑰的長度是5。
第2招：通過字母頻率猜凱撒秘鑰
通過第1招，我們已經知道秘鑰的長度是5，但依然還不知道是哪5個字母。
當然，一種方式是暴力破解，因為知道長度後，只需要嘗試 26*26*26*26*26=11,881,376次，對計算機來說，也就一兩秒的事。
不過麻煩的是，計算機嘗試了所有的可能，還需要人去查看哪種可能是正常的英文單詞，對人來說，1000多萬實在過於龐大。
所以，我們希望有進一步的方法，可以縮小嘗試的範圍。而這個方法的思路其實在前面已經介紹過。
既然已經知道了秘鑰的長度是5。
那麼我們可以把密文分成5組，每組對應的秘鑰是相同的。
然後對每組都分別用26個英文字母進行凱撒解密，究竟哪個字母才是正確的秘鑰呢？可以用字母頻率做參考。
以如下第一組為例
SYOEHZQSWLZJXHOLQSPEYXTFPZWMPLCMOYXPMYSOYTHYTHJXXLTQEDZPXPLPWDZPLPPSYPLFDLPEPOESHQOZTHSHMYSOLXDYFZNPVXLDXGZNLAJLLTETVEZJWPEDJYWRPEDDTEY
用26個字母分別進行嘗試解密，並對解密出來的內容按字母出現的次數排序。
比如如上內容按字母A進行解密，解出來的內容中，按字母出現次數排序是
AWJPKIDEOZSHUBXQYGNRLC
而我們知道從統計上說，26個英文字母出現的頻率排序是
ETAOINRSHDCLMPUFGWYBVKXJQZ
怎麼衡量，用字母A的解密效果呢？
密碼學家給出的辦法是：計算前6個字母，後6個字母中重複字母的個數。
我們發現，用字母A進行解密之後，最前6個字母和最後6個字母中，只有2個字母是和統計學上的字母頻率順序吻合的。
AWJPKIDEOZSHUBXQ YGNRLC
ETAOIN RSHDCLMPUFGWYB VKXJQZ
依次用後續的字母進行解密.
message = 'SYOEHZQSWLZJXHOLQSPEYXTFPZWMPLCMOYXPMYSOYTHYTHJXXLTQEDZPXPLPWDZPLPPSYPLFDLPEPOESHQOZTHSHMYSOLXDYFZNPVXLDXGZNLAJLLTETVEZJWPEDJYWRPEDDTEY'
decrypt = ''
key = 'L'
numKey = ord(key) - 65
def calPro(message):
prob = 'ETAOINRSHDCLMPUFGWYBVKXJQZ'
dic = {}
for i in range(len(message)):
if message[i] in dic:
dic[message[i]] += 1
else:
dic[message[i]] = 1
dic = sorted(dic.items(),key=lambda item:item[1],reverse=True)
compStr = ''
for i in dic:
compStr += i[0]
cn = 0
for i in range(6):
if prob.index(compStr[i]) < 6:
cn += 1
if prob.index(compStr[len(compStr)-i-1])>19:
cn += 1
print(compStr,cn)
for j in range(len(message)):
decrypt += chr(65+(ord(message[j])-65-numKey)%26)
calPro(decrypt)
所有26個字母嘗試一遍，我們發現用字母L進行解密，吻合的字母是最多的。
因此，我們推測第一個秘鑰是字母L。
照葫蘆畫瓢，按同樣的方法破解後面的秘鑰。
最後得到最有可能的秘鑰是 LOVEU
破解成功
用LOVEU進行解密的結果如下。
正是鮑勃·迪倫的代表作《blowing in the wind》。
作為搖滾樂和民謠的一代宗師，2016年，鮑勃·迪倫獲得諾貝爾文學獎，稱為第一位獲得該獎項的非文學家。
破解維吉尼亞密碼簡單嗎?
雖然我們成功地破解了這首詩，但並不代表維吉尼亞密碼很容易破解。特別是第一步，破解秘鑰的長度。
如果明文裡有大量的重複，就像我們挑的這首詩，它其實是一首歌，所以自然會有大量的重複，所以出現重複字符串的概率就比較高，容易破解。
但是當明文很短，並且很少有大段內容重複時，要破解維吉尼亞加密還是比較困難的。
所以，李雷的父母並沒有再次成功破解密碼。
這次的問題出在Jim身上，在李雷的父母無計可施後，他們直接找到了Jim，威脅Jim，成功拿到了密碼。
那麼我們要思考的問題是，如果密碼都被人獲取了，加密還安全嗎？