RSA 的實作 • 嚴謹密碼學：現代加密實務入門

作者由衷希望你永遠不必從頭實作 RSA。
如果有人要求你這麼做，能跑多快就跑多快，並且質疑那個人的理智。
密碼學家與工程師花了數十年才發展出快速、足夠安全、但願沒有致命 bug 的 RSA 實作，你真的不會想重新發明 RSA。即使有所有文件可用，完成這項艱鉅任務也得花上好幾個月。

使用函式庫#

實作 RSA 時，你通常會使用提供必要函式的函式庫或 API。例如 Go 語言的 crypto 套件：

func EncryptOAEP(hash hash.Hash, random io.Reader, pub *PublicKey, msg []byte,
label []byte) (out []byte, err error)

EncryptOAEP() 接收一個雜湊函式、一個 PRNG、一把公鑰、一則訊息與一個 label（OAEP 的選用參數），回傳簽章與錯誤碼。它會呼叫 encrypt() 對填充後的資料計算 RSA 函式：

func encrypt(c *big.Int, pub *PublicKey, m *big.Int) *big.Int {
    e := big.NewInt(int64(pub.E))
    c.Exp(m, e, pub.N)
    return c
}

主要操作就是 c.Exp(m, e, pub.N)——把訊息 m 提升到 e 次方再對 pub.N 取模。

若你選擇自己實作 RSA 而非使用現成的函式庫函式，務必依賴既有的大數函式庫——一組讓你能定義並計算數千位元大數之算術運算的函式與型別。
例如 C 的 GMP（GNU Multiple Precision）算術函式庫，或 Go 的 big 套件。相信作者，你不會想自己實作大數算術的。

即使你只是用函式庫函式來實作 RSA，也務必理解內部是怎麼運作的，才能評估風險。

快速指數運算：平方與相乘#

把 x 提升到 e 次方（計算 x^e mod n）的操作稱為指數運算（exponentiation）。處理大數時，這個操作若天真實作會極慢。

天真做法需要 e − 1 次乘法：

expModNaive(x, e, n) {
    y = x
    for i = 1 to e – 1 {
        y = y * x mod n
    }
    return y
}

這個演算法簡單但極度沒有效率。
要指數級地加快，方法是用平方而非乘法推進指數，直到達到正確的值。這族方法稱為平方與相乘（square-and-multiply），也叫平方指數運算或二進位指數運算。

一個例子#

假設要計算 3^65537 mod 36567232109354321（65537 是多數 RSA 實作所用的公開指數）。

我們可以把 3 乘自己 65536 次，也可以理解到 65537 = 2^16 + 1，改用一連串平方運算：

初始化 y = 3，然後：
1. y = y² mod n   → y = 3²    mod n
2. y = y² mod n   → y = 3⁴    mod n
3. y = y² mod n   → y = 3⁸    mod n
4. y = y² mod n   → y = 3¹⁶   mod n
5. y = y² mod n   → y = 3³²   mod n
...
執行 16 次平方後，y = 3^65536

最後回傳 3 × y mod n = 3^65537 mod n = 26652909283612267。

換句話說，我們只用 17 次乘法就算出結果，而天真做法要 65536 次。

一般演算法#

平方與相乘法的做法是：由左至右逐位元掃描指數的位元，為每個指數位元計算平方（讓指數值加倍），並在遇到值為 1 的位元時乘上原始的數。

上例中指數 65537 的二進位是 10000000000000001，我們為每個新位元平方 y，只在最前與最後兩個位元乘上原始的 3。

expMod(x, e, n) {
    y = x
    for i = m – 1 to 0 {
        y = y * y mod n
        if eᵢ == 1 then
             y = y * x mod n
    }
    return y
}

真實系統常實作這個最簡單方法的變體。其中之一是滑動視窗法（sliding window method）——它考慮一整塊位元而非個別位元來執行給定的乘法操作。例如 Go 語言的 expNN() 函式（https://golang.org/src/math/big/nat.go ^↗）。

安全隱憂：時序攻擊#

這些加速技巧往往增加了對某些攻擊的脆弱性。
弱點在於：指數運算高度依賴指數的值。上述演算法中的 if 會依指數位元是 0 還是 1 走不同分支——若位元是 1，該次 for 迴圈迭代就比位元是 0 時更慢。
監控 RSA 操作執行時間的攻擊者，能利用這個時間差還原私有指數——這稱為時序攻擊（timing attack）。
針對硬體的攻擊則能藉由監控裝置的功率消耗、觀察哪些迭代執行了額外的乘法，來分辨 1 位元與 0 位元，從而揭露私有指數中哪些位元是 1。

小指數加快公鑰運算#

由於 RSA 計算本質上就是指數運算，其效能取決於所用指數的值。指數越小，需要的乘法越少，指數運算就快得多。

公開指數 e#

公開指數 e 原則上可以是 3 到 φ(n) − 1 之間的任何值，只要 e 與 φ(n) 互質。

但實務上你只會看到小的 e 值，而且多數時候 e = 65537——這是出於加密與簽章驗證速度的考量。
例如 Microsoft Windows CryptoAPI 只支援放得進 32 位元整數的公開指數。e 越大，計算 x^e mod n 就越慢。

私有指數 d#

與公開指數不同，私有指數 d 大約與 n 一樣大，這使得解密遠慢於加密、簽章遠慢於驗證。
因為 d 是秘密的，它必須不可預測，因此不能被限制成小值。例如若 e 固定為 65537，對應的 d 通常會與模數 n 同一數量級——若 n 是 2048 位元，d 就接近 2^2048。

運算	乘法次數
提升到 65537 次方	17
提升到某個 2048 位元數的次方	約 3000

實測#

用 OpenSSL 工具包測量實際速度（在配備 2.7 GHz Intel Core i5-5257U 的 MacBook 上）：

$ openssl speed rsa512 rsa1024 rsa2048 rsa4096
--snip--
                  sign    verify    sign/s verify/s
rsa 512 bits  0.000059s 0.000005s 16838.0 193781.5
rsa 1024 bits 0.000174s 0.000012s   5741.4 84714.2
rsa 2048 bits 0.000736s 0.000034s   1358.7 29831.8
rsa 4096 bits 0.007628s 0.000133s    131.1   7527.9

驗證相對於簽章的速度比：

模數大小	驗證／簽章速度比
512 位元	約 11.51
1024 位元	約 14.75
2048 位元	約 21.96
4096 位元	約 57.42

差距隨模數大小而擴大，因為 e 運算的乘法次數相對於模數大小保持不變（例如 e = 65537 時是 17 次），而私鑰運算所需的乘法會隨模數增大而增加，因為 d 會跟著變大。

為什麼是 65537 而不是 3#

若用 OAEP、PSS 或 FDH 這類安全方案實作 RSA，用 3 當指數其實沒問題，而且更快。
但密碼學家避免這麼做，因為 e = 3 時較不安全的方案會讓某些數學攻擊成為可能。
65537 大到足以避開這類低指數攻擊，而且它只有一個位元為 1（低漢明權重），減少了計算時間。

65537 對數學家還有特別意義：它是第四個費馬數——形如 2^(2^n) + 1 的數，因為它等於 2^16 + 1 而 16 = 2^4。不過這對密碼工程師來說大致只是個趣聞。

中國剩餘定理（CRT）#

加速解密與簽章產生（也就是計算 y^d mod n）最常見的技巧是中國剩餘定理（CRT，Chinese remainder theorem）。它讓 RSA 快約四倍。

CRT 讓解密更快的方式是：計算兩次分別對 p 與對 q 取模的指數運算，而非單純對 n 取模。
因為 p 與 q 遠小於 n，做兩次「小」的指數運算比做一次「大」的更快。

一般形式#

CRT 不專屬於 RSA。它是一個通用的算術結果：若 n = n₁n₂n₃... 且各 nᵢ 兩兩互質（GCD(nᵢ, nⱼ) = 1），則 x mod n 可以從 x mod n₁、x mod n₂、x mod n₃…算出來。

延伸：CRT 的一般計算範例

設 n = 1155 = 3 × 5 × 7 × 11。我們想找出滿足下列條件的數 x：

x mod 3  = 2
x mod 5  = 1
x mod 7  = 6
x mod 11 = 8

用 CRT，我們計算總和 P(n₁) + P(n₂) + ...，其中：

P(nᵢ) = [ (x mod nᵢ) × (n/nᵢ) × ((1/(n/nᵢ)) mod nᵢ) ] mod n

注意第二項 n/nᵢ 就是「除了這個 nᵢ 之外所有因數的乘積」。

套用到本例：

[ 2 × 385 × ((1/385) mod 3) + 1 × 231 × ((1/231) mod 5)
+ 6 × 165 × ((1/165) mod 7) + 8 × 105 × ((1/105) mod 11) ] mod n

化簡為 [770 + 231 + 1980 + 1680] mod n = 41——確實 41 就是本例挑的那個數，結果正確。

套用到 RSA#

把 CRT 套用到 RSA 比上述範例簡單，因為每個 n 只有兩個因數（p 與 q）。

給定要解密的密文 y，你不計算 y^d mod n，而是用 CRT 計算：

xp = y^s mod p    其中 s = d mod (p − 1)
xq = y^t mod q    其中 t = d mod (q − 1)

再合併這兩個式子：

x = [ xp × q × ((1/q) mod p) + xq × p × ((1/p) mod q) ] mod n

這比平方與相乘更快，因為乘法密集的運算是在模 p 與模 q 下進行的——這兩個數比 n 小一半。

在最後的運算中，q × ((1/q) mod p) 與 p × ((1/p) mod q) 這兩個數可以事先算好，這意味著只需計算兩次乘法與一次模 n 加法就能求出 x。

遺憾的是，這些技巧附帶了一個安全但書——見「常見錯誤」中的 Bellcore 攻擊。