中海學堂:「表裡表氣」的維吉尼亞密碼
「表裡表氣」的維吉尼亞密碼(Vigenère cipher)
之前,中海給大家講過非常有趣的「凱撒密碼」。
當然,「凱撒密碼」是很簡單的的替換密碼,太容易被破解。
所以,人們在單一凱撒密碼的基礎上擴展出多表密碼,
稱為「維吉尼亞密碼」。
那麼,這一期的主題就是「維吉尼亞密碼」。
公元16世紀晚期,想要獲得更高的保密度的人獲得了一種設計更加精細的密碼錶。
法國外交家布萊斯·德·維吉尼亞(Blaise de Vigenère)發明了一種方法來對同一條信息中的不同字母用不同的密碼進行加密。
這樣,同樣的E在一個位置可能被M所取代,而在另一個位置的E則有可能以K的面目出現。
這樣,就可以防止任何人利用頻率分析法解密該條信息。
事實上,
該方法最早記錄在吉奧萬·巴蒂斯塔·貝拉索(Giovan Battista Bellaso)於1553年所著的書
《吉奧萬·巴蒂斯塔·貝拉索先生的密碼》(義大利語:La cifra del. Sig. Giovan Battista Bellaso)中。
吉奧萬·巴蒂斯塔·貝拉索,是義大利密碼學家。
中海找了很久,也沒有找到這位仁兄的畫像,
於是暫用一副義大利的美景圖,權當放鬆一下啊。
他的主要著作就是1553年出版的
《吉奧萬·巴蒂斯塔·貝拉索先生的密碼》(La cifra del. Sig. Giovan Battista Bellaso)。
在此書中,他提出了一種多表密碼,在當時十分先進,
但後來被誤認為是布萊斯·德·維吉尼亞所發明,
因而現在被稱為維吉尼亞密碼。
中海要在這裡提示大家,這一課略有枯燥,要集中注意力啊。
來,跟我一起說,
好好學習!天天向上!
下面繼續上課。
維吉尼亞密碼的組成元素包括:
明文、密鑰、密表
它將26個凱撒密表合成一個,
見下表:
其實這個表一出來,
估計許多聰明的小夥伴已經知道怎樣加密和解密啦。
是的,維吉尼亞密碼最核心的就是
表!表!表!
所以,中海給它起名「表裡表氣」的維吉尼亞密碼,
哈哈哈。。。
如何加密?
維吉尼亞密碼引入了「密鑰」的概念,
即根據密鑰來決定用哪一行的密表來進行替換,
以此來對抗字頻統計。
舉例如下,
假如以上面第一行代表明文字母,
左面第一列代表密鑰字母,
對如下明文加密:
TO BE OR NOT TO BE THAT IS THE QUESTION
當選定RELATIONS作為密鑰時,
加密過程是:
明文一個字母為T,第一個密鑰字母為R,
因此可以找到在R行中代替T的為K,依此類推,得出對應關係如下:
明文:TOBEO RNOTT OBETH ATIST HEQUE STION
密鑰:RELAT IONSR ELATI ONSRE LATIO NSREL
密文:KSMEH ZBBLK SMEMP OGAJX SEJCS FLZSY
再來一個,
明文:THE BUTCHER THE BAKER AND THE CANDLESTICK MAKER。
(屠夫、麵包師和蠟燭匠)。
密鑰:BIG BIGBIGB IGB IGBIG BIG BIG BIGBIGBIGBI GBIGB
密文:UPK CCZDPKS BNF JGLMX BVJ UPK DITETKTBODS SBSKS
收件人知道「BIG」是密鑰,就能很容易地通過相應的位置改變字母位置,從而譯出經過加密的文字。
再試一下,
用關鍵詞(密鑰)FOREST來加密Better to do well than to say well.
明 文b e t t e r t o d o w e l l t h a n t o s a y w e l l
關鍵詞F O R E S T F O R E S T F O R E S T F O R E S T F O R
密 文G S K X W K Y C U S O X Q Z K L S G Y C J E Q P J Z C
如何解密?
很多年以來,維吉尼亞(Vigenère)密碼都被認為是不可破解的,
但查爾斯·巴貝奇(Charles Babbage),一個獨立的英國富人在19世紀50年代向人們展示了事實並非如此。
順便提一句,這個人也因為其在計算機科學領域方面所進行的先鋒性工作而被世人所熟悉。
這位巴貝奇可不是一般人,他是科學管理的先驅者,第一台可編程的機械計算機的設計者。
巴貝奇(Babbage)通過尋找重複的字母段破解了這個密碼系統。
當然,維吉尼亞密碼的優勢在於這種密碼被假定為它將不同位置的字母進行不同的加密。
比如同一段文字中的「THE」 可能在前面表現為「UPK」,
但在後面則被表現為「BNF」。
同樣,象「AKER」這樣的字母也會被進行不同的加密。
但是,第一個和第三個「THE」都會被編碼為「UPK」。
第一個「THE」中的「T」會用「B」來進行編碼,
而第三個「THE」中的「T」也同樣是用「B」來編碼。
發生這種情況是因為第三個「THE」是排在第一個「THE」後面第21個字母,
而3字密鑰BIG會在重複7次之後又回到了最開始。
在任何比密鑰要長得多的加密信息中,
都會不可避免地出現類似這樣的重複。
而一個解密者應該如何才能揭示加密文件的真正面目呢?
比如,如果加密文字「UPK」出現了兩次,
第一個"U"到下一個"U"會數21個字母,
那麼他就可以推斷出密鑰的長度是21的整除數。
或者換種說法,他可以推斷出21是密鑰的倍數。
(約數或稱除數是一個數字被除之後不會有餘數。比如21的除數就是1、3、7和21。)
如果獲得了足夠多類似的線索,解密者就可以知道密鑰的確切長度。
一旦他知道了密鑰長度,他就可以對加密信息進行日常頻率分析。
注意,數學在解密工作中總是放在首位的:
解密者首先會計算出密鑰的長度,
這步工作甚至是在他要考慮密鑰的具體內容是什麼之前所要做的。
巴貝奇的獨具創意的技巧開創了一片密碼術的新天地,
並且將數學工具引入到了以前被認為專屬於文字學的領域之中。
即使一種編密碼系統沒有明確地使用數學,
但其中隱藏的格式卻通常需要以數學的方式進行整理。
需要注意的一些解密技巧
1.A-E段,U-Z段以及O-T段的特徵比較顯著,可先從這些方面著手;
2.如果一些字元串出現的頻率較多,不妨猜猜,特別要注意THE,-ING等的出現;
3.要留意那些圖表中沒有出現的字母,很多時候也會是突破點,如X與Z的空缺;
4.圖表最好還是做一下,畢竟比較直觀,好看。
是的,維吉尼亞密碼就是這麼簡單。
歷史上以維吉尼亞密表為基礎又演變出很多種加密方法,
其基本元素無非是密表與密鑰,
並一直沿用到二戰以後的初級電子密碼機上。
我們可以主動去了解這些密表,說不定什麼時候就能用得上呢。
「表裡表氣」的維吉尼亞密碼,
看得中海已經有點眼花了。
放鬆放鬆吧。。。
中海希望對密碼有興趣的小夥伴們,可以跟中海的密碼專家們一起探討學習啊!
本文部分內容來源於百度詞條
※「2018 TOKENSKY區塊鏈大會」之《DCO:基於Token的分散式協作組織》
TAG:中海聞達 |