這篇文章我本來是想寫了放到極客時間上 我寫的專欄 裡面的，但是專欄的內容是需要仔細斟酌的。這篇文章我認為還是偏難，不適合整個專欄的內容和難度的定位，因此我把它稍微加工了一下，放到我這個博客上。
在專欄中的第 36 講的選修課堂（該講預計在 12 月初發布）中，我介紹了 Diffie–Hellman 密鑰交換這一算法，它可以說是質數在加密技術中的一個應用，並且是通過其中的 “模冪運算” 來實現的。今天，我來介紹質數的另一個應用，RSA 背後的算法。我在互聯網上搜索了一下，我發現基本沒有能把它背後的實現原理用淺顯的中文敘述講清楚的，但我還是想試一試，看看能不能儘可能避開那些難懂的術語，用盡量形象和易於理解的方式，把 RSA 背後的原理講清楚。
在專欄的 第 02 講 ，我們講了非對稱性加密，比如通過公鑰加密的數據，能且只能通過私鑰來解密，可是這是怎樣實現的呢？這就要講 RSA 加密技術的原理了。現在，假定我們要通過 RSA 來進行安全的通信，於是你要使用我發佈的公鑰來對數據加密，加密以後發給我，我拿到加密數據以後使用對應的私鑰解密，而攻擊者截獲了這個加密數據並嘗試破解。
模冪等式
我們在介紹 Diffie–Hellman 密鑰交換的時候講到了這個模冪等式：
gᵃ mod p = A
從難度上看它具有如下三個特性：
- 特性 ①：已知 g、a 和 p，求 A 容易；
- 特性 ②：已知 g、p 和 A，求 a 困難；
- 特性 ③：已知 a、p 和 A，求 g 也困難。
再看看上面我們介紹的模冪公式關於離散對數求解的三種難易程度不同的情況吧， 我們在 Diffie–Hellman 密鑰交換中應用了特性 ① 和特性 ②，而在 RSA 中，我們還要應用特性 ① 和特性 ③ 。
觀察特性 ①，我們可以利用它來設計 RSA 加密，即讓 g 代表需要被加密的實際值，而 a、p 可以公開。於是你就求出它的 a 次冪，並取 p 模，得到了 “密文” A，把它發給我。這個過程中，如果 A 被截獲，那麼根據特性 ③，已知 A、p 和 a，攻擊者是很難求解出 g 來的。我們已經說過了，這符合 “ 正向計算簡單，逆向求解困難 ” 這一特性，這一點很適合用來加密。
但是和前面的 Diffie–Hellman 密鑰交換不同的是，我們並不是要讓所有人都求解這個 g 困難，因為密文是發給我的，我得很容易求解這個 g 才行啊，要不然就像是用一把沒人擁有鑰匙的鎖來加密，這把鎖就失去意義了。
我們再來觀察一下這個模冪等式：
gᵃ mod p = A
藉由 Diffie–Hellman 密鑰交換帶來的靈感，如果我們構造這樣一個和上式形式一致，但變量具有一定對稱性的等式：
Aᵈ mod p = g
這其實是什麼？這不就是將加密的數據 A，經過模冪運算以後，得到了原始的未加密數據 g 了嗎？也就是說， 既然 a 是公鑰，那麼這裡的 d 就是所謂的 “私鑰” 啊 。
好，我們把後面這個公式的 A 通過前面那個公式來帶入，得到：(gᵃ mod p)ᵈ mod p = g，根據我們前面介紹模冪運算時提到的聯等公式，它就可以化簡為：
gᵃᵈ mod p = g
因此這個式子，就表示出了公鑰、私鑰，以及被加密數之間的關係。
接下去，我們來思考怎樣生成這個私鑰 d。
歐拉函數
為了繼續進行後面的分析，我們需要一點知識儲備，首先是歐拉函數。 歐拉函數 φ(x) 表示，有多少不大於 x 的正整數中，與 x 互質的數目 （即公因數只有 1）。
舉例來說，要計算 φ(4)，你看不大於 4 的正整數包括 1、2、3、4，其中：
- 1 和 4 互質；
- 2 不和 4 互質，因為它們有公因數 2；
- 3 和 4 互質；
- 4 不和 4 互質，因為它們有公因數 4。
所以 φ(4) = 2。
歐拉函數 φ(x) 一般很難計算，但是如果 x 是質數，情況就不同了，因為質數和任何比它小的正整數互質，比如 φ(5) = 4，這四個數分別是 1、2、3、4，因此，在 x 是質數的情況下：
φ(x) = x – 1
同時，如果 x 是一個可以因式分解的合數，比如 x = m*n，歐拉函數還具備這樣的特性：
φ(m*n) = φ(m) * φ(n) = (m-1) * (n-1)
這個公式我們後面還會用到。
歐拉定理
有了歐拉函數的知識，我們進一步瞭解歐拉定理。 歐拉定理 指的是，對於正整數且互質的 g 和 x，有如下性質：
gᵠ⁽ᴾ⁾ ≡ 1 (mod p)
其中的三橫線不是表示 “恆等”，而是表示 “同餘”，上面的意思是，g 的 φ(p) 次冪，除以 p 所得的餘數，和 1 除以 p 所得的餘數，二者相同。
舉例來說，當 g=3，p=5，根據前面學的歐拉函數有 φ(5)=4，那麼 gᵠ⁽ᴾ⁾=81，81 除以 5 餘 1；1 除以 5 也餘 1，同餘關係成立。
密鑰生成
由於 1ᵏ ≡ 1 (mod p)，我們可以給指數上的歐拉函數賦予正整數係數 k，gᵏᵠ⁽ᴾ⁾ ≡ 1 (mod p)，我們再給兩邊乘以 g，得到 gᵏᵠ⁽ᴾ⁾⁺¹ ≡ g (mod p)。當 g 小於 p 的時候，g 除以 p 的餘數就是 g，因此這個同餘式可以寫成：
gᵏᵠ⁽ᴾ⁾⁺¹ mod p = g
再聯想前面的：
gᵃᵈ mod p = g
你看，這兩個式子的形式是一樣的，這就意味著，kφ(p)+1 = ad。因此，這個私鑰就是：
d = (kφ(p)+1)/a
這意味著什麼？這意味著如果能夠求得 φ(p) 的值，那麼這個私鑰就求解出來了。但是，怎樣求解 φ(p) 呢？這裡，我希望：
- 密鑰是我生成的，因此我求解這個 φ(p) 要非常容易，這樣我就可以很容易計算出密鑰來；
- p 是公開的，攻擊者僅僅知道 p，求解 φ(p) 要非常困難才行，那樣才能保證加密的安全性。
你看，這是不是又一個需要 “ 正向計算簡單，逆向求解困難 ” 特性的問題？
回想一下前面我們學習歐拉函數的時候，我講到了，如果 m、n 是質數，那麼歐拉函數可以這樣求得：
φ(m*n) = φ(m) * φ(n) = (m-1) * (n-1)
這正是我需要的！
你想，如果我選取兩個非常非常大的質數 m 和 n，選擇 p 的時候，就讓它等於 m 和 n 的乘積，那麼 φ(p) = φ(m*n) = (m-1) * (n-1)，這個正向計算是很簡單的，也就是說，因為我知道 m、n，密鑰的生成是很容易的一件事情。
可是，攻擊者拿不到 m、n，就只能硬生生地嘗試去給 p 因式分解才能得到 m、n，而對於一個超大質數的因式分解，這個過程是極其困難的。縱觀整個 RSA 的原理，其中涉及到了兩個和質數相關的 “正向計算簡單，逆向求解困難” 的特性：
- 一個是前面介紹的模冪等式逆向求底數；
- 另一個就是這裡介紹的超大質數的因式分解。
這也就是 RSA 安全性的基本原理。
當然，隨著科技發展，計算能力越來越強，特別是量子計算的興起，我們對超大質數的位數要求也越來越高，512 bit 的 RSA 已經被破解，而 1024 bit 也已經搖搖欲墜，現階段 2048 bit 長度還是安全的，可是未來，誰又知道呢？
閱讀更多 sandag 的文章
