WhatsApp的新使用者授權合約成為了前陣子的全城熱話，也再次引起了大家對網絡安全的討論。我們經常看到「此對話已進行端對端加密」之類的訊息 — 可是，你有想過現代的加密過程到底是怎樣運作的嗎？我們又有多安全？

如果你有玩過密室逃脫遊戲的話，你應該碰到過一兩組密碼（cipher）— 就是那些看似無意義的亂碼，然而你必先解開箇中玄機才能逃脫。最著名的加密法大概是羅馬帝國時代的凱撒加密法（Caesar cipher），它把所有字母都按字母排列順序偏移某個數值的位置。可是，凱撒密碼也是最容易解開的密碼，因為我們可以對其進行頻率分析。在英文裡有著幾個最常出現的字母，譬如在這篇文章的英文原文裡，英文字母「e」到此為止已出現了81次，比其他字母都要多。解密者可以看看凱撒密碼裡哪個字母出現次數最多，那就不難猜到原文被順移了多少個字母。

從此，不同的加密法陸續誕生。與其只將每個英文字母按一定數值的位置偏移，人們開始將字母根據一個字，甚至一段文字進行不同的偏移，稱為維吉尼亞密碼（Vigenère cipher）。不斷複雜化的加密法，最終造就了著名的恩尼格瑪密碼機（Enigma），它的基本上是一系列相當聰明的字母偏移。儘管複雜如此，也眾所周知地被Alan Turing在英國政府的解密基地 — 布萊切利園（Bletchley Park）破解了。這件事發生之後，大家都意識到發展嶄新加密法的需要。

然後是RSA。它是現代加密的主要方法，以三位發明家Rivest、Shamir和Adleman的姓氏命名（註一）。RSA加密演算法和以上提到的加密法有著本質上的不同，凱撒加密法和恩尼格瑪密碼機使用對稱金鑰（symmetric keys），而RSA則是非對稱式加密（asymmetric cryptography）或公鑰加密（public key cryptography）的一員。在對稱式加密（symmetric cryptography）中，為訊息加密和解密用的金鑰是一樣的；但是RSA用上公鑰（public key）和私鑰（private key）兩把不同的金鑰 — 即是鎖上箱子用的鑰匙並不是解鎖的那把！加密和解密用上兩把不同鑰匙似乎難以用直覺理解，但RSA其實只依靠兩個基本概念：質數和模算數（modular arithmetic）。

質數是大於一而除了一和自己外，無法被其他自然數整除的數。它們本身就非常有趣，亦是我們曾經在第二十期討論過的課題之一。質數可以是任意大的：我們已知能寫出來的質數之中，最大的一個有多達24,862,048個數位。RSA加密演算法就是利用因數分解通常是極費時這一點，即使擁有強大電腦力量的人亦然，因此要把加密內容破解往往需要花上不合理的電腦力量，令人敬而遠之（註二）。

另一個重要的概念是模算數。那基本上和從時鐘看時間差不多，在24小時制裡，我們會以「時間模24（time modulo 24）」來描述小時 — 23:00後的三個小時是02:00，而不是26:00（註三）。模算數的原理基本上就是除數：要得出n mod a，基本上就要把n除以a約干次，直至商數比a小，得出的餘數就是我們要找的值。

理解了這兩個概念後，要明白RSA加密演算法其實不太難，在此我們會逐步解釋 [1]。

我們首先選兩個質數作示範，例如p = 11、q = 13。把它們相乘，得出公鑰n = 143。（在現實世界中這些質數都極為龐大，現在建議的是2048位元（註四）。可是為了編輯的身心健康著想，我們這次選了比較小的數值！）我們也要選一個與10（即p – 1）和12（即q – 1）沒有共同因數（互質）的數字e，這次我們選e = 7。每個人選的n都不同，而e和n就是剛才提到的公鑰，它們被發表在一個公開的目錄中，當傳送訊息給別人的時候，電腦可以使用目錄中的公鑰。

假設Cliff想給我傳一個非常簡單的訊息，越簡單越好 — 「Hi」。一如所料，如果你要電腦工作，就要先把英文字母轉成數字。很感恩，我們已經有一套這樣的系統 — 美國資訊交換標準代碼（American standard code for information interchange/ASCII），它可以將英文字母變成7位元的數字。在ASCII中「H」的代碼是72，而「i」的代碼是105。

要把字母「H」加密，Cliff要找出我的公鑰。他從目錄得知n = 143、e = 7。加密後的文字由公式c = T^e (mod n) 得出，我們的第一個字母是T₁ = 72，經加密後會變成c₁ = 72^7 (mod 143) — 這看起來很棘手，絕不是人手可以計算的，但我們可以借助電腦的力量 — Google一下便可以得出c₁ = 19 (mod 143)，所以我們第一個要傳送的是19。我們重複上述的步驟一次來加密「i」：c₂ = 105^7 (mod 143)，因此第二個數字是c₂ = 118 (mod 143)。訊息「Hi」也就變成了「19 118」。

對外人來說，解開加密訊息是不可能的，因為你不能從已取模的數字還原本來的數字；可是，我們比外人知道多兩項資訊，就是p和q的數值。沒有了它們，你就要對n 進行因數分解，而現實上n的數值很大，分解往往極之費時。解密的關鍵如下，我們先取p – 1 和q – 1的最小公倍數lcm (10, 12) = 60，解密的金鑰d能從方程式1 = (e x d) mod (lcm (p – 1, q – 1)) 得出。對我們而言，1 = (7 x d) mod 60，所以d = 43 — 這就是我們還原訊息的神奇密碼了。最後經過解密的訊息m可以由方程式m = c^d (mod n) 得出。我們收到了兩個字母，所以要把它們分開解密：第一個字母是19^43 (mod 143)，等於72 (mod 143)，亦即是字母「H」；同樣地，字母「i」來自118^43 (mod 143) = 105 (mod 143)。這些計算看似涉及天文數字，但對電腦來說其實輕而易舉。此外，有了d，你以後可以還原Cliff 給你的每一條訊息（註五）。

RSA加密法之所以會成功，是因為數論中的費馬小定理（Fermat’s Little Theorem）— 就是那個費馬，可是這並不是把數學家弄得焦頭爛額的費馬最後定理（Fermat’s Last Theorem）。費馬小定理乍看起來非常簡單：若p是質數，a^p ≡ a (mod p) （註六）。這可是RSA加密法的關鍵，因為RSA常常需要取p次方的計算。費馬小定理的證明需要花點筆墨才能解釋，但在維基百科也能輕易找到，這裡我們就不介紹了。

現在RSA加密系統是用於加密少量訊息的預設選擇，譬如用於加密對稱金鑰加密中的金鑰（註七）。現時已知最大被成功因數分解的n有250個數位（829位元），電腦用了2700核心年（註八）在2019年將其分解 [2]。相比之下，用於加密的長度一般為2048位元，因此我們暫時還是安全的。然而，從歷史上看，所有加密法都總有被人破解的一天，那時我們就要創造另外一種新的加密法了。

1 其實第一個發明RSA的人是英國數學家Clifford Cocks，他在1973年已經研究出RSA，比Rivest、Shamir和Adleman在1977年的發明還要早四年。可是，Cocks當時在英國情報部門工作，研究屬於機密，因此要到20年後的1997年才對外公布，所以這演算法就以Rivest、Shamir和Adleman命名了。

2 隨著量子電腦的發展，這可能會改變。可是現在的量子電腦還沒有成熟到可以解開RSA加密的地步。如果你對這方面有興趣的話，可以搜尋一下「秀爾演算法（Shor’s Algorithm）」。

3 稍微不同的地方是，我們會說午夜十二時為零時或十二時，但是數學模算數的世界裡，我們會說12 ≡ 0 (mod 12)（即是零時，並非十二時）。

4 位元的英文「bit」是「binary digit（二進制數位）」的縮寫，因此7位元的數值範圍是從1到2⁷ – 1 = 127，而2048位元的數值則是從1到2²⁰⁴⁸ – 1，那大概有617個數位左右。

5 這條方程永遠有唯一解d，是因為我們一開始就設定e與10和12互質。

6 這條方程是用模算數計算的，並非我們熟悉的代數式。要留意左右兩邊均需取模，即是a^p (mod p) ≡ a (mod p)。

7 RSA是通訊協定TLS（Transport Layer Security；傳輸層安全性協定）的重要部分，TLS很多時被用於網上交易和通訊。

8 核心年（core year）代表用一個中央處理器（CPU）核心持續運行一年（365天）。研究的作者使用Intel Xeon Gold 6130 CPUs作為參考 [2]。

參考資料：

[1] Singh, S. (2003). The Code Book: The Secrets Behind Codebreaking. New York, NY: Delacorte Press.

[2] Zimmermann, P. (2020, February 28). Factorization of RSA-250. Retrieved from https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2020-February/001166.html