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

RSA（Rivest–Shamir–Adleman）密碼系統在 1977 年作為第一個公鑰加密方案出現時，徹底革新了密碼學。

古典的對稱金鑰加密方案用同一把秘密金鑰加解密訊息，而公鑰加密（也稱非對稱加密）用兩把金鑰：

公鑰：任何想加密訊息給你的人都能使用。
私鑰：解密以公鑰加密之訊息所必需。

這個魔法正是 RSA 成為真正突破的原因。四十年後，它仍是公鑰加密的典範、網際網路安全的主力。

RSA 出現的前一年，Diffie 與 Hellman 已引入公鑰密碼學的概念，但他們的方案無法執行公鑰簽章。

RSA 是一個算術把戲#

RSA 的運作方式是建立一個稱為陷門置換（trapdoor permutation）的數學物件——一個把數 x 變換成同範圍內數 y 的函式，使得：

用公鑰從 x 算出 y 很容易。
從 y 算出 x 實際上不可能，除非你知道私鑰——也就是那個陷門。

（把 x 想成明文、y 想成密文。）

除了加密之外，RSA 也用來建構數位簽章：私鑰的擁有者是唯一能簽署訊息的人，而公鑰讓任何人都能驗證簽章的有效性。

本章脈絡#

RSA 背後的數學——乘法群 Zn* 與歐拉函數 φ(n)。
RSA 陷門置換——公開指數 e 與秘密指數 d。
金鑰產生與安全性——n 的大小、p 與 q 的選擇。
用 RSA 加密——教科書 RSA 的可鍛造性，以及 OAEP。
用 RSA 簽章——盲化攻擊、PSS 與 FDH。
RSA 的實作——平方與相乘、小指數、中國剩餘定理。

常見錯誤#

比 RSA 方案本身更美的，是那一系列的攻擊——它們之所以奏效，或是因為實作洩漏（或能被誘使洩漏）內部資訊，或是因為 RSA 被不安全地使用。

對 RSA-CRT 的 Bellcore 攻擊#

Bellcore 攻擊是 RSA 歷史上最重要的攻擊之一。1996 年首次被發現時，它之所以突出，是因為它利用了 RSA 對故障注入（fault injection）的脆弱性——那種強迫演算法的某部分行為異常、因而產生錯誤結果的攻擊。

例如硬體電路或嵌入式系統可以藉由突然改變供電電壓、或朝晶片上審慎選定的位置發射雷射脈衝來暫時擾動。
攻擊者接著觀察這些故障對最終結果的影響來加以利用——例如比較正確結果與錯誤結果，就能提供關於演算法內部值（包括秘密值）的資訊。

Bellcore 攻擊適用於使用中國剩餘定理且為確定性的 RSA 簽章方案。
也就是說：它對 FDH 有效，對機率性的 PSS 無效。

攻擊原理：回想使用 CRT 時，x^d mod n 是這樣算出來的（其中 xp = y^s mod p、xq = y^t mod q）：

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

現在假設攻擊者在 xq 的計算中誘發了一個故障，讓你得到某個錯誤的值 xq′，最終結果變成 x′。攻擊者接著把錯誤簽章 x′ 從正確簽章 x 中減去：

x − x′ = (xq − xq′) × p × ((1/p) mod q) mod n

GCD(x − x′, n) = p
我們接著能算出 q = n/p 與 d——RSA 簽章完全被攻破。

這個攻擊有一個變體，在你不知道正確簽章、只知道被簽訊息時仍然有效。另外也有一個針對模數值（而非 CRT 值計算）的類似故障攻擊。

共用私有指數或模數#

為什麼你的公鑰不該與別人有相同的模數 n？

不同私鑰顯然該有不同的私有指數 d，即使金鑰使用不同的模數。否則你可以試自己的 d 去解密給其他實體的加密訊息，直到撞上一個共用相同 d 的。
不同的金鑰對也該有不同的 n 值，即使它們有不同的 d——因為 p 與 q 通常是私鑰的一部分。因此若我們共用相同的 n（也就是相同的 p 與 q），我就能用 p、q 從你的公鑰 e 算出你的私鑰。

那如果只共用 n 呢？ 假設我的私鑰是 (n, d₁)，你的私鑰是 (n, d₂)、公鑰是 (n, e₂)。我知道 n 但不知道 p 與 q，所以無法直接從 e₂ 算出 d₂。

那要如何只從一個私有指數 d 算出 p 與 q？解法有點技術性，但很優雅。

延伸：從 d 反推 p 與 q 的推導

記得 d 與 e 滿足 ed = kφ(n) + 1，其中 φ(n) 是秘密的、且能直接給我們 p 與 q。我們不知道 k 或 φ(n)，但我們能算出 kφ(n) = ed − 1。

第一個觀察：依歐拉定理，對任何與 n 互質的數 a 都有 a^φ(n) = 1 mod n。因此在模 n 下：

a^(kφ(n)) = (a^φ(n))^k = 1^k = 1

第二個觀察：因為 kφ(n) 是偶數，我們可以把它寫成 2^s · t。也就是說，我們能把 a^(kφ(n)) = 1 mod n 寫成 x² = 1 mod n 的形式，其中 x 可以從 kφ(n) 輕易算出。這樣的 x 稱為單位根（root of unity）。

關鍵觀察：x² = 1 mod n 等價於說 x² − 1 = (x − 1)(x + 1) 整除 n。換句話說，x − 1 或 x + 1 必定與 n 有共同因數，這就能給我們 n 的因式分解。

Python 實作（為求簡潔用小的 64 位元數）：

from math import gcd

n = 36567232109354321
e = 13771927877214701
d = 15417970063428857

kphi = d*e - 1
t = kphi

while t % 2 == 0:
    t = divmod(t, 2)[0]

a = 2
while a < 100:
    k = t
    while k < kphi:
        x = pow(a, k, n)
        if x != 1 and x != (n - 1) and pow(x, 2, n) == 1:
            p = gcd(x - 1, n)
            break
        k = k*2
    a = a + 2

q = n//p
assert (p*q) == n
print('p = ', p)
print('q = ', q)

這支程式從 e 與 d 判定 kφ(n)，找出滿足 kφ(n) = 2^s · t 的 t；接著以 t 為起點尋找滿足 (a^k)² = 1 mod n 的 a 與 k；條件滿足時就找到了解，然後判定因數 p 並驗證 pq 等於 n。

輸出：

p = 2046223079
q = 17870599

程式正確回傳了兩個因數。