密碼學基礎：前世今生

Cryptography（中文：密碼學）一詞源於希臘語 κρυπτός（隱藏，秘密）和 γράφειν（書寫）。如今信息安全變得越來越重要，保護信息安全的措施也愈加豐富，而密碼學（Cryptography）在其中的作用不可忽視。筆者在「初級隱私保護工具推介」中提到的「GPG」就是密碼學發展的產物。

密碼學的發展有很長的歷史，經典密碼學（Classic Cryptography）與現代密碼學有很大的區別。經典密碼學如「Wikipedia（密碼學）」所說，通常依賴於設計者和敵手的創造力與技巧，作為一種實用性藝術存在，並沒有對於密碼學原件的清晰定義。而現代密碼學得益於計算機技術的發展，與計算機科學、數學等學科更加息息相關。所以說學好密碼學首先要有一定的數學認知，其中比較重要的學科是「Number theory」（中文：數論），筆者會盡力在以後撰寫一篇關於「Number theory」的文章。

這裡插一句題外話～數學的奧妙就是如此，看似和現實生活關聯不大，卻能潤物細無聲地推動科學和現實生活的發展。「Number theory」的是一個相對古老的學科，但人們在很長的一段時間中都無法將其在現實中應用。然而隨着計算機技術的誕生，人們發現很多計算機領域的問題都可以從「Number theory」中尋求答案。

言歸正傳，讓我們開始瞭解密碼學吧！

目錄

歷史

密碼學早在古代就被應用於戰爭之中。古中國周朝兵書《六韜．龍韜》就有記載：

太公曰：「主與將，有陰符，凡八等。有大勝克敵之符，長一尺。破軍擒將之符，長九寸。降城得邑之符，長八寸。卻敵報遠之符，長七寸。警眾堅守之符，長六寸。請糧益兵之符，長五寸。敗軍亡將之符，長四寸。失利亡士之符，長三寸。諸奉使行符，稽留，若符事聞，泄告者，皆誅之。八符者，主將祕聞，所以陰通言語，不泄中外相知之術。敵雖聖智，莫之能識。」武王問太公曰：「…符不能明；相去遼遠，言語不通。為之奈何？」太公曰：「諸有陰事大慮，當用書，不用符。主以書遺將，將以書問主。書皆一合而再離，三發而一知。再離者，分書為三部。三發而一知者，言三人，人操一分，相參而不相知情也。此謂陰書。敵雖聖智，莫之能識。」

簡單來說，「陰符」就是使用不同長度的「符」來表達不同的含義，而「陰書」則是將信息分成三份，只有三份合一才能解讀信息。除了這段文獻筆者也找到了古代中國和密碼學相關的其他的一些文獻，但是在網路上中文資料對於中國古代密碼學的總結並不是很多。而且鑑於密碼學本身就是一個相對現代（且偏西方知識體系）的概念，對於一件事物算不算是密碼學的界定也相對模糊，所以筆者無法再做更加詳盡的介紹。可以知道的是，中國古代是有一些零零散散的密碼學應用。

除了中國，古埃及和古希臘人也有着一定的密碼學應用，這些歷史可以參考「Wikipedia(Cryptography)」。以下是非常廣爲人知的經典加密方法「Shift cipher」（又名：Caesar cipher，據說凱撒大帝在戰場上就應用了這個方法）。其加密過程就是將字母表進行位移，使得每一個原有的字母都有其唯一對應的經過位移的字母，例如我們將所有字母向左位移 1： 

Plain:  ABCDEFGHIJKLMNOPQRSTUVWXYZ
Cipher: BCDEFGHIJKLMNOPQRSTUVWXYZA

當我們想要加密（encipher）文字的時候，只需要應用上面的表格即可，例如： 

Plain text:   HELLO WORLD
Cipher text:  IFMMP XPSME

解密（decipher）的時候只需要反向操作即可。

不過這些加密方法雖然看似種類繁多，卻又大同小異。而且這些加密方法有一個很大的缺點，那就是使用加密方式進行交流的雙方需要提前通過物理接觸達成一個「共識」（例如上面例子中的「向左位移 1」），所以任何一個掌握「共識」的人都可以對密文進行破解。

隨着時間的推移人們發明出來的加密方法愈發複雜和難以破解，但這些方法的本質卻沒有任何進步，都存在着上述的問題。即使是二戰有名的「Enigma」也跳脫不出這個限制。當然人們對密碼學的理解並非停滯不前，生活在 19 世紀的「Auguste Kerckhoffs」就提出過「Kerckhoffs's principle」：一個人盡皆知的系統，只要保有密鑰，那它依然應該是安全的。尤其是隨着計算機技術的發展，經典密碼學的加密方法變得極易破解，人們很需要一套更加現代的密碼學體系。

現代密碼學

如今的密碼學（Cryptography）是一門綜合性非常強的學科，但是信息保密依然是最為重要的一環。因此這一部分筆者將着重地介紹，比較著名的加密算法（Encryption algorithm）及其原理。

⚠注意：

Diffie–Hellman key exchange

時間是 1976 年，Diffie 和 Hellman 兩個人發表了一項重要的研究，這是第一個在公共信道（public channel）中安全交換密鑰（cyptographic key）的方法，被後人成為「Diffie–Hellman key exchange」。但因為受到 NSA 的阻力，直到 1977 年這個方法才得以在「The International Symposium on Information Theory」上公開宣講，具體的歷史故事可以看這裡。不過，1997 年英國 GCHQ 公開的機密信息顯示，其研究人員在 1969 年便實現了「public-key cryptography」。另外，在 2002 年 Hellman 將這個安全協議的名稱加上「Ralph Merkle」的名字，更改為「Diffie–Hellman–Merkle key exchange」，因為是 Merkle 最先提出了「public key distribution system」的概念。

步驟

下面我們來看一下「Diffie–Hellman」的操作步驟：

  1. Alice and Bob agree on a large prime \(p\) and a primitive root \(g\) (i.e. \((\mathbb{Z}/p)^{\times} = \langle g \rangle \)) (⚠ Now: Everyone knows \(p\), \(g\))

  2. Alice chooses a secret \(x\), then sends \(X \equiv g^{x} \bmod p\) to Bob

  3. Bob chooses a secret \(y\), then sends \(Y \equiv g^{y} \bmod p\) to Alice (⚠ Now: Everyone knows \(p\), \(g\), \(X\), \(Y\))

  4. Alice computes \(k \equiv Y^{x} \bmod p\)

  5. Bob computes \(k \equiv X^{y} \bmod p\)

  6. Finally, Alice and Boc share a secret \(k\)

原理

其原理非常的簡單，如下：

\(k \equiv Y^{x} \equiv (g^{y})^{x} \equiv g^{yx} \equiv (g^{x})^{y} \equiv X^{y} \bmod p\)

其難度是基於人們目前沒有找到高效的解決「discrete logarithm problem」的辦法。

破解

如上面所述，「Diffie–Hellman」的安全性是基於「discrete logarithm problem」的難度。如果未來有人找到了這個問題更好的解決辦法，那這一類系統的破解難度就會大幅度降低。

這裡筆者會介紹兩種目前用來破解「Diffie–Hellman key exchange」的方法：

Baby-step giant-step

用「Baby-step giant-step」方法直接暴力破解是相對直接的方法，首先我們先簡單介紹「Baby-step giant-step」的原理：

⚠ For a given cyclic group \(G\) of order \(p-1\), a generator \(g\) of the group and a group element \(a\). We want to find an integer \(l\) such that: \(g^l=a \bmod p\).

  1. Set \(m = \lceil\sqrt{p-1}\rceil\), then \(p - 1 \leqslant m^2\)
  2. Let \(l = im + j\), where \(i, j < m\)
  3. (Baby-Step) Compute and record \(g^0, g^1, g^2, \dots ,g^{m-1} \bmod p\)
  4. We have \(g^l \equiv a \bmod p \Rightarrow g^{im+j} \equiv a \bmod p \Rightarrow g^j \equiv ag^{-im} \bmod p\)
  5. Compute \(g^{-m} \bmod p\)
  6. (Giant-Step) Start Computing \(a(g^{-m})^i\) for \(i=0,1,2,3\dots\)
  7. Then we can find a match in "Giant-Step" corresponding to one of the "Baby-Step". Thus, we can compute the result.

在了解「Baby-step giant-step」的原理後，我們就可以很直接的破解「Diffie–Hellman」了。我們已知在「Diffie–Hellman」中 \(p\), \(g\), \(X\), \(Y\) 都是已知的，所以我們要做的就是用「Baby-step giant-step」解決「\(X=g^{x} \bmod p\) 中的 \(x\)」和「\(Y=g^{y} \bmod p\) 中的 \(y\)」這兩個問題。然後通過 \( g^{xy} \)就可以求出密鑰了。

Man-in-the-middle attack (MITM)

在公共網路環境中如果不加以身份驗證，我們就可以很容易的通過「Man-in-the-middle attack (MITM)」竊聽 Alice 和 Bob 的內容。

RSA

「Diffie–Hellman」的公布使人們打開了研究「Cryptography」的新思路。於是在一年後，也就是 1977 年「Rivest」，「Shamir」，「Adleman」三人發表了「RSA」加密算法（也就是三人姓氏的首字母），這也是現如今被使用最廣泛的加密算法之一。另外神奇的是，1997 年英國 GCHQ 公開機密信息顯示其研究人員在 1973 年就已經研究出了類似的算法。

步驟

下面我們來看一下「RSA」的操作步驟：

  1. choose two large primes \(p \neq q\)

  2. compute \(n = pq\) and \(\varphi(n)=(p-1)(q-1)\)

  3. choose \(e\) with \(\gcd(e,\varphi(n))=1\)

  4. choose \(d\) so that \(de \equiv 1 ; (\bmod \varphi(n))\)

  5. Now, the public key is \((e,n)\)

  6. To encode message \(M\) (less than \(n\)), compute \(M^{e} (\bmod n)\)

  7. to decode, compute \((M^{e})^{d} \equiv M (\bmod n)\)

原理

其原理便是步驟中的最後一步：

\((M^{e})^{d} \equiv M (\bmod n)\)

其破解難度是基於在實踐中沒有高效的解決「integer factorization problem」的方法。

破解

如上面所述，「RSA」的難度在於「integer factorization problem」的困難，所以當我們在討論如何破解「RSA」的時候我們主要是研究如何分解一個整數。而這就是一個很大的話題了，所以筆者會在以後進行補充 （未完待續～）

總結

「Cryptography」的研究是一個艱難的過程。信息安全很多時候與國家利益息息相關，使得其經常成為追求人權及自由的人們和政府鬥爭的焦點。其中，「Diffie–Hellman–Merkle key exchange」這種在發表時受阻已是政府相對平和的做法，在很多國家公開發表和傳播特定的「Cryptography」相關知識很可能會被訴訟，甚至惹上牢獄之災。例如筆者在多篇文章中介紹過的 PGP，被其發明者 Phil Zimmermann 在網路上發表之後便因 PGP 傳出國門而遭到了政府的犯罪調查，美國當時的「Export controls」認定 PGP 的源代碼屬於軍需品所以不能出口。好在 Phil Zimmermann 機智的將 PGP 的源代碼出版成了一本書，從而通過「First Amendment」中的言論自由（書籍出版自由）的部分保護了自己的權益。雖然如今歐美的法律對於信息安全等領域的限制已經越來越少，但很多法律依舊暗藏殺機。

信息安全的應用本身就是亦正亦邪的。例如普通人可以用「Cryptography」來保護自己的隱私，但是壞人可以用來傳播恐怖指令而不被發現。然而我們應該為這樣的不安而放棄自由嗎？每個人都有自己的理解，筆者認為，我們應該捍衛自由。因為這是我們人權中的一部分，就像法國的《人權宣言》所闡述的：

La liberté consiste à pouvoir faire tout ce qui ne nuit pas à autrui
—— Déclaration des Droits de l'Homme et du Citoyen de 1789

自由就是有權從事一切無害於他人的行為，而我們也應該捍衛所有人能夠從事一切無害於他人的行為的權力。

言歸正傳，「Cryptography」是一門很豐富的學科。本篇文章只是冰山一角，更多的是希望諸位對「Cryptography」有一個整體的概念並且受到一些啟發。如今看來大部分的加密方法都無法做到一勞永逸，隨着科學技術的發展破解的方法只會更多，速度也會更快。例如隨着量子計算機「Quantum computing」的發展，「Diffie–Hellman」、「RSA」和「elliptic curve」這樣常見加密方法的安全程度都會大打折扣。「Cryptography」就像是矛與盾的博弈，這也它如此充滿魅力的原因。

最後筆者想說，本文有很多筆者自己理解的東西，如果有任何錯誤還望諸位不吝賜教(,,・ω・,,)