2012年1月17日 星期二

密碼學的第二課:換位加密法和替代加密法

大家好,
關於換位加密法和替代加密法,大家好像有些搞不清楚,再說明一下。

換位加密法是明文中出現的字母,在密文中也會出現,只是順序被打散(明文沒出現的字母,密文也不會出現)。
譬如將The tree is green分成三列書寫(去掉空格),再以橫式抄錄回來(左-->右,上-->下)
就會變成 Ttegehrirneese

Ttege
hrirn
eese

(動畫: http://www.nsa.gov/kids/ciphers/cipherKey.swf)

替代加密法則是將原有明文中的所有字母都以其他字母取代了。
譬如由A至Z的字母順序中的位置往後移k個位置所得的新字母取代,其中k是一個介於0與25間的整數。
當k=5時,A變成F,B變成G,C變成H...
那麼The tree is green就會變成ocz omzz dn bmzzi

那假如a~z以0~25表示,舊字母的位置為x,字母的新位置y=25-x
將字母反序排列,A變成Z,B變成Y,C變成X...
那麼The tree is green會變成gsv givv rh tivvm

(動畫: http://www.nsa.gov/kids/ciphers/cipherCaesar.swf)

這樣就可以達到將訊息隱藏的效果了。

有沒有注意到一個特性,這樣的方法,某些字母會出現的特別多次,
尤其當加密的文章很長時,這樣的特性就會更明顯。
這也就給了解密者一些資訊,就造成了這種方法的不安全。

根據英文字的特性,
字母e是用的最多的,
其次是a i o u t s r y
然後是m n b o p d g h j k l
最後q w z x v

所以在解密的時候,把密文中最常出現的字母先代換為e,其次代換為a
或是最常見的雙字母組代換為th和三字母組代換為the...
再根據前後文,大致上就可以得到原來的訊息囉(也就是明文)

(想看看專家用這種方法的解密過程,可以閱讀 http://goo.gl/Dysz0)

(字母頻率表,http://goo.gl/Rl4ZS)
A 8.19 B 1.47 C 3.83 D 3.91 E 12.25
F 2.26 G 1.71 H 4.57 I 7.10 J 0.14
K 0.41 L 3.77 M 3.34 N 7.06 O 7.26
P 2.89 Q 0.09 R 6.85 S 6.36 T 9.41
U 2.58 V 1.09 W 1.59 X 0.21 Y 1.58 Z 0.08

著名的小說《福爾摩斯偵探集》中,有一章《跳舞的小人》也有類似的情節。

值得一提的是,中文也有類似的統計頻率唷~
例如最常見的中文字是"的",其次大概是"一"或"是" (根據文章屬性的不同)
可以參見 http://crypt.math.fju.edu.tw/09/Freq.html

利用頻率分析,有時候也可以解答別人的問題呢!

密碼學的第一課:古典密碼學簡介

各位同學大家好,今天要上密碼學的第一課:
大家要瞭解密碼學(Cryptography)這個字的由來、
古典密碼學的換位式加密法(Transposition cipher)與取代式加密法(substitution cipher),
以及密碼學最興盛的第一次世界大戰與第二次世界大戰時期
(帥氣的ENIGMA)

請同學翻開課本,http://goo.gl/SEDpZ
閱讀下面章節

1 術語
2 密碼學與密碼分析的歷史
2.1 經典密碼學
2.2 中世紀至第二次世界大戰
2.2.1 蘇格蘭的瑪麗女王
2.2.2 第一次世界大戰
2.2.3 第二次世界大戰

值得一提的是,密碼學的逐步發展,而產生了許多不同的分支。譬如資訊隱藏(steganography or information hiding)。

傳統的資料隱藏,是將欲隱藏的資料附於一般資料後,使得人眼只看得到一般的資料(如一般風景圖片),而看不到欲保密的資料。

雖然作用一樣為資料的保密,但在學術上已分屬於不同的研
究領域,而媒體往往均以密碼作為通稱。
譬如以下的影片,應屬於資訊隱藏的領域。
http://www.youtube.com/watch?v=ZqjYqhKB5hw

密碼學中通常加密與解密的雙方會擁有共同的解密資訊(稱
為金鑰);藉由金鑰可以將密碼還原而得到原先的訊息。
譬如著名小說"達文西密碼"中,索尼耶赫館長就曾使用密
文留下訊息給孫女蘇菲。
13-3-2-21-1-1-8-5
O,Draconiand evil! (啊,嚴酷的魔王!)
Oh,Lame Saint! (噢,瘸腿的聖徒!)

很顯然,這就是一組設定較弱的密碼,因此很容易被瞭解,其加密模式為換位式加密,透過斐波那契數列(Fibonacci number)即可得到訊息為

Leonardo da Vinci! (列昂納多‧達‧文西!)
The Mona Lisa! (蒙娜麗莎!)

此外,書中所提到的藏密筒(cryptex),其實就是ENIGMA的一種變形。可見古典密碼學其實仍有很多的用途,甚至可以說是近代密碼學的根基。
關於藏密筒的相關說明,可以閱讀http://goo.gl/xPz7R