核心概念#
本章從電視劇《暗算》出發，介紹密碼學從古代到現代的演進，核心觀點是：當今的密碼學是以數學為基礎的，而信息論的提出為現代密碼學奠定了理論基礎。
密碼學的自發時代#
- 密碼學的歷史可追溯到兩千多年前，凱撒大帝用字母替換表加密情報（如 A→B, B→E…），這種方法稱為「凱撒大帝」加密法
- 只要多截獲一些情報，統計字母頻率，就可以破解這種替換密碼
- 有經驗的編碼者會把常用詞對應成多個密碼，讓破譯者無法統計出規律（這裡已包含了樸素的概率論原理）
好的密碼必須做到：根據已知的明文和密文的對應，無法推斷出新的密文內容。從數學角度看，加密是一個函數 $F$ 的運算，解密是反函數的運算。好的加密函數不應該通過幾個自變量和函數值就能推出函數本身。
- 二戰中日本軍方的密碼設計存在嚴重缺陷，美軍因此截獲大量情報（如中途島海戰的 AF 密碼事件）
- 美國情報專家雅德利曾在重慶幫助中國政府破解日軍和間諜的通信密碼
信息論時代的密碼學#
- 二戰期間，香農（Shannon）和圖靈（Turing）分別在貝爾實驗室研究加密和解密
- 香農在研究過程中提出了信息論，這可以說是情報學的直接產物
- 根據信息論，密碼的最高境界是：無論敵方截獲多少密文，對我方的所知沒有任何增加（即信息量沒有增加）
- 具體要求：密文之間的分布均勻且統計獨立，提供的信息量最少
現代通用的公開密鑰加密法（如 RSA）基於信息論。Diffie 和 Hellman 在 1976 年發表開創性論文《密碼學的新方向》（New Directions in Cryptography），奠定了今天大多數互聯網安全協議的基礎。
RSA 算法原理#
以加密單詞 “Caesar” 為例：
- 找兩個很大的素數 $P$ 和 $Q$，計算 $N = P \times Q$，$M = (P-1) \times (Q-1)$
- 找一個和 $M$ 互素的整數 $E$（公開密鑰）
- 找一個整數 $D$，使得 $E \times D \mod M = 1$（私密密鑰）
- 加密：$X^E \mod N = Y$
- 解密：$Y^D \mod N = X$（利用費爾馬小定理）
公開密鑰的優點#
- 簡單：只是一些乘除和乘方運算
- 可靠：密文統計獨立且分布均勻，即使公開 $N$ 和 $E$，只有掌握私鑰 $D$ 的人才能解密
- 靈活：可以產生很多公開密鑰 $E$ 和私鑰 $D$ 的組合
破解難度#
- 世界上沒有永遠破不了的密碼，關鍵是能保持多長時間的有效期
- 破解公開密鑰的方法是對大數 $N$ 進行因數分解，目前這在計算上極其困難
- 一種加密方法只要保證 50 年內計算機破解不了，也就算是滿意了
本章小結#
利用信息論可以消除一個系統的不確定性，而利用已獲取的信息來消除情報系統的不確定性就是解密。密碼學的最高境界是無論敵方獲取多少密文，也無法消除己方情報系統的不確定性——密文之間相互無關，看起來像完全隨機的序列。