看,這就是加密學!(1)——古老的加密學

話說咱們翻牆黨多多少少都聽說過加密學,啊,至少也聽過各種加密算法,什麼AES啊,RSA啊,對稱加密算法啊,非對稱加密算法啊,會話金鑰啊,公鑰啊,私鑰啊諸如此類的加密學名詞。

不過,聽說歸聽說,這些名詞究竟是個什麼意思,加密學究竟是一門怎樣的學科,恐怕就沒多少人清楚了。

那麼,就讓本幽靈在前面開路,和諸位一起看看加密學的世界吧!

說起加密學,這可是個老傢伙啊。加密學的英文是cryptography,這詞起源於兩個希臘文詞彙:kryptós(對應的英文為hidden,secret)和
graphein(對應的英文為writing),剛好展現了加密學的本質:秘密書寫。廣義的密碼學負責信息的保密認證和防篡改,包括加密算法和散列算法,狹義的密碼學只有加密算法。

A想要傳遞信息給B,但又不想讓路上的C知道,所以就把本來人人都能讀懂的信息通過一定的規則轉換成沒人能讀懂的信息,B收到之後再通過對應的規則轉換回能讀懂的信息。
其中,“人人都能讀懂的信息”被稱作明文(plaintext),“沒人能讀懂的信息”被稱作密文(ciphertext),這兩個詞彙會在我以後的科普中被廣泛使用,諸位不要忘了它們的含義哦:)

最早的加密算法出現在古希臘,是一種重組(transposition)算法。舉個例子:明文為hello world,密文為elolh drwlo,這就是最典型的重組算法。

除了重組算法,還有替代(substitution)算法,最有名的替代算法是凱撒密碼:明文為attack tonight,加密算法是將每個字母替換為字母表中三位後的字母(例如a替換為d),密文就是dwwdfn wrqljkw。

很顯然凱撒密碼非常容易被破解,於是後來有人設計了使用數次重組和替代的算法,例如二戰時的英格瑪密碼機。很長一段時間之內,密碼學家們都是在研究字母表:)

這些基於字母表的算法,統稱為古典加密算法。加密學在很長一段時間之內,都是軍方的寵物,似乎與普通人無關。

後來,計算機誕生了,人們開始用0和1傳遞信息。此時,基於複雜數學方法的現代加密算法誕生了:密碼學家們不再拿著字母表,而是開始研究數學(尤其是離散數學),研究如何將這些0和1轉換成沒人能看懂也沒人能破譯的內容,同時又可以變回明文(這個特性叫做可逆性,加密算法必須具有可逆性;相對的,散列算法要求不可逆)。

最開始誕生的是對稱加密算法(symmetric-key algorithm):隨機生成一個密鑰K,然後將這個密鑰和明文一起輸入到算法中,產生密文,接收方再用同一個密鑰K解密得到明文(或者也可以是不同的密鑰K1和K2,但是兩者可以相互派生,也就是說知道其中一個就可以輕易得知另一個)。

對稱加密算法的代表有DES(Data Encryption Standard,數據加密標準),3DES(DES的改進版本),AES(Advanced Encryption Standard,高級加密標準),RC4(Rivest Cipher 4)等。其中DES已經因為安全性過弱而被棄用,現在AES被廣泛使用,迄今為止AES依舊非常安全,被認為實際上無法破解。

這其中DES和AES都是塊密碼(Block Cipher),數據以塊的形式輸入(一塊512bits的數據,加密,一塊512bits的數據,加密……);而RC4則是流密碼(Stream Cipher),數據以bit流或字節流的形式輸入(數據流,加密……)。對稱加密算法非常非常非常(!)複雜,這裡我就不展開了,在以後的系列裡介紹相對簡單的吧。

哈,這裡有個詞很奇怪:實際上無法破解?事實上,除了屬於古典加密算法的“一次性填充(one-time pad)”之外,其他所有加密算法(不管是古典還是現代,不管是對稱還是非對稱)都是理論上可破解的:brute-force attack,一個個嘗試密鑰的破解(聽起來很像所謂的暴力破解,不過還是有所不同:比起暴力破解,brute-force attack更有技術含量,會採用一些技巧進行輔助破解)。只要攻擊者有足夠的時間和資源,理論上來說沒有加密算法可以擋住brute-force attack。

我們仔細看一下吧:一次性填充是採用完全隨機的一次性密碼本的,這導致攻擊者完全無從下手,但是其他所有算法都做不到這一點,包括現代加密算法,解密密鑰是通過計算機生成的偽隨機數而不是隨機數,也就是說如果偽隨機數生成函數有問題,生成的偽隨機數不夠隨機或者位數過少,那麼攻擊者很容易嘗試出解密密鑰;即便算法足夠強悍,在理想情況(不考慮時間和計算成本)下還是可以嘗試出解密密鑰。

那麼,有人大概會想:你說的破解前提建立在攻擊者知道加密算法這一點之上,不是嗎?那麼我們只要把保密工作做好,不讓第三方知道我們使用的算法不就可以了?

很不幸,你想得太美了!除了前面提到的brute-force attack,還有一種更常見的密碼破解方式:密碼學分析(cryptanalysis),通過分析密文或者比對密文和已知明文等手段找出加密算法的漏洞,從而將密碼破解。如果一個加密算法有嚴重缺陷,那麼即便再怎麼保密,攻擊者還是能很輕易的找出這個算法的漏洞並將其破解
(密碼學中破解的定義是:找到一種比暴力破解更有效率的獲得解密密鑰的方法)。

密碼學實踐也說明了這一點:很多自創的加密算法雖說對第三方保密,但是在密碼學分析面前不堪一擊;而像AES這種從一開始就公開了所有細節的算法,反倒是一直極為堅挺,直到現在,密碼分析師們無從下手。越公開的算法,經受了越多密碼分析師的檢驗,抗擊密碼學分析的能力也越強。

密碼學原理一:公開算法的安全性好過保密算法。

關於密碼分析和brute-force attack,還有相當多的內容可以聊,不過考慮到快要失控的篇幅,就此打住吧。

雖然現代加密算法理論上可破解,但如果說你破解一段密文需要10年時間,花上個幾百億美金,你說你會去破解嗎?就算破解出來,也早就黃花菜都涼了啊。
這就是實際上不可破解的真正含義!

前面說了對稱加密算法,那麼自然還有非對稱加密算法(asymmetric-key algorithm):加密密鑰和解密密鑰不是同一個,更重要的是無法相互派生,知道其中一個也找不出另外一個。非對稱加密算法的加密密鑰又被稱作公鑰,可以隨便公開;而解密密鑰被稱作私鑰,由解密者秘密持有。所以很多時候非對稱加密算法又被叫做公鑰加密算法(public-key algorithm)。

最著名的非對稱加密算法非RSA莫屬,這名字是三個密碼學大牛的姓名開頭第一個字母的組合:R,Ronald Rivest;S,Adi Shamir;A,Leonard Adleman。RSA算法誕生於1978年,迄今為止仍然被廣泛使用。不過RSA算法並不是第一個非對稱加密算法,這當中還有一段很有趣的故事,下次具體聊RSA的時候仔細聊聊吧。

諸位應該很好奇非對稱加密算法具體是怎樣的吧?請期待下一篇!
(其實本來我不想嘮叨這麼多的,但是一不小心就寫了這麼多,諸位請耐心消化吧)

科普文鏈接集合:https://plus.google.com/109790703964908675921/posts/TpdEExwyrVj

發表迴響

你的電子郵件位址並不會被公開。 必要欄位標記為 *