10.1 密碼學 RSA 與橢圓曲線#

本章導言#

1976 年，Diffie 與 Hellman 發表《密碼學的新方向》，提出一個當時近乎科幻的想法：加密金鑰可以公開。1977 年，Rivest、Shamir、Adleman 據此做出 RSA。這門「公鑰密碼學」的地基不是工程，而是本書第 4–5 章的純數學：模運算、循環群、Euler–Fermat 定理。1990 年代之後，主戰場轉向橢圓曲線（ECC）：同樣的安全強度，金鑰更短、計算更省。本節展示 RSA 與橢圓曲線如何把「群論 + 數論」變成世界資訊基礎設施，並說明「難解性」如何成為一種可設計的資源。

歷史前因後果#

驅動關係：Diffie–Hellman 的思想實驗（兩個陌生人在公開頻道建立秘密）迫使人們尋找單向函數——正向易算、逆向極難的函數。這把古老數論問題（分解大數、離散對數）從「欣賞性的難題」變成「安全性的工程參數」。數學難題的「難」，第一次成為被標價出售的資源。

RSA 的構造#

設置：取兩個大質數 \(p, q\) ， \(N = pq\) ， \(\varphi(N) = (p-1)(q-1)\) （Euler 函數）。取 \(e\) 與 \(\varphi(N)\) 互質，由 Bézout（擴展歐幾里得）求 \(d\) 使 \(ed \equiv 1 \pmod{\varphi(N)}\) 。公鑰 \((N, e)\) ，私鑰 \(d\) 。

加密（明文 \(m \in \mathbb{Z}/N\) ）： \(c = m^e \bmod N\) 。解密： \(c^d = m^{ed} \equiv m \pmod N\) 。

定理 10.1.1（正確性）： \(m^{ed} \equiv m \pmod N\) 對一切 \(m\) 成立。

證明： \(ed = 1 + k\varphi(N)\) 。若 \(\gcd(m, N) = 1\) ，Euler 定理（5.2 節乘法群循環性的推論： \(|\mathbb{Z}_N^\times| = \varphi(N)\) ）給 \(m^{\varphi(N)} \equiv 1\) ，故 \(m^{ed} = m^{1+k\varphi(N)} \equiv m\) 。若 \(m\) 與 \(N\) 不互質（如 \(m \equiv 0 \pmod p\) ），在兩個質因子分別驗證（ \(m^{ed} \equiv 0 \equiv m \pmod p\) ；模 \(q\) 用 Euler），由中國剩餘定理合併。 \(\blacksquare\)

安全性依據：由 \((N, e)\) 求 \(d\) 需要知道 \(\varphi(N)\) ，而 \(\varphi(N) = (p-1)(q-1)\) 基本上等價於分解 \(N\) ——目前對經典計算機沒有多項式時間演算法。RSA 把「分解的難」轉化為「保密的可靠」。

DH 金鑰交換與離散對數#

RSA 的兄弟協議 Diffie–Hellman 更直接地用了 5.2 節：

• 公開：循環群 \(G\) （通常 \(\mathbb{F}_p^\times\) 或橢圓曲線群）與生成元 \(g\) 。
• Alice 取秘密 \(a\) ，公布 \(g^a\) ；Bob 取秘密 \(b\) ，公布 \(g^b\) 。
• 兩方各自計算 \((g^b)^a = (g^a)^b = g^{ab}\) ，作為共享密鑰。

竊聽者面對的是離散對數問題：由 \(g\) 與 \(g^a\) 求 \(a\) 。在精心選擇的群中（大質數體或橢圓曲線），這被認為計算上不可行。Galois 體（5.2）與循環群（2.3）在此不是練習題，而是全球加密流量的底層協議。

橢圓曲線：密碼學的新舞台#

定義 10.1.2：特徵 \(\ne 2, 3\) 的體 \(K\) 上，橢圓曲線是

加一個無窮遠點 \(O\) 。其上的點集合 \(E(K)\) 有幾何定義的群律：

• 過兩點 \(P, Q\) 的直線與曲線交於第三點 \(R\) ，定 \(P + Q = -R\) （ \(-R\) 是關於 \(x\) 軸的反射）；
• \(O\) 是單位元（過 \(P\) 的鉛垂線交曲線於 \(-P\) ）。

定理 10.1.3： \((E(K), +, O)\) 是交換群。

證明思想：交換律由「 \(P, Q\) 的弦與 \(Q, P\) 的弦相同」顯然；結合律最難，可用直線的 Cayley–Bacharach 性質（兩條三次曲線交於 9 點，過其中 8 點的任何三次曲線必過第 9 點）的幾何論證，或直接展開座標公式驗證； \(O\) 為單位、逆元為反射，皆直觀可驗。 \(\blacksquare\)

密碼學用法（ECDH）： \(K = \mathbb{F}_p\) （或 \(\mathbb{F}_{2^m}\) ，回顧 5.2 節有限體），群 \(E(\mathbb{F}_p)\) 有限。Diffie–Hellman 換到這個群：Alice 公布 \(aP\) （標量乘，即反覆加法），竊聽者面對橢圓曲線離散對數：由 \(P, aP\) 求 \(a\) 。

ECC 的工程優勢：目前最強的一般演算法（Pollard \(\rho\) ）對 \(n\) 階群需約 \(\sqrt n\) 步。RSA 的分解有亞指數演算法（數域篩），橢圓曲線只有指數型——所以 256 位元的 ECC 金鑰約等於 3072 位元 RSA 的安全度。手機、身分證、比特幣簽章，底層都是 \(E(\mathbb{F}_p)\) 上的標量乘法。

具體例題#

例題 10.1.1：(1) 用小參數演示 RSA： \(p = 3, q = 11\) ， \(e = 3\) ，加密 \(m = 4\) 並解密。(2) 演示橢圓曲線 \(y^2 = x^3 + 2x + 3 \pmod 5\) 上的點群運算。

解：

(1)： \(N = 33\) ， \(\varphi(33) = 2 \times 10 = 20\) 。 \(\gcd(3, 20) = 1\) ，求 \(d\) ： \(3d \equiv 1 \pmod{20} \Rightarrow d = 7\) （ \(21 \equiv 1\) ）。加密： \(c = 4^3 = 64 \equiv 31 \pmod{33}\) 。解密： \(31^7 \bmod 33\) 。逐步平方： \(31^2 = 961 \equiv 4\) ； \(31^4 \equiv 16\) ； \(31^7 = 31^4 \cdot 31^2 \cdot 31 \equiv 16 \cdot 4 \cdot 31 = 1984 = 60 \cdot 33 + 4 \equiv 4\) 。✓ 回到明文 \(4\) 。

(2)：曲線 \(E: y^2 = x^3 + 2x + 3\) 於 \(\mathbb{F}_5\) （ \(\Delta = -16(32+27) \ne 0\) ，橢圓）。逐點檢驗 \(x = 0,1,2,3,4\) ，計 \(y^2 = x^3 + 2x + 3 \pmod 5\) ：

平方剩餘（ \(\mathbb{F}_5\) 中 \(0^2=0, 1^2=4, 2^2=1, 3^2=4, 4^2=1\) ）：得點

階為質數 \(7\) ，故群循環（5.2 節定理的應用）。算一次加法： \(P = (1,1)\) ， \(Q = (1,4) = -P\) ，故 \(P + Q = O\) 。再算 \(2P\) ：斜率 \(s = \frac{3x_P^2 + a}{2y_P} = \frac{3+2}{2} = \frac{5}{2} = 0 \pmod 5\) ，故

\(2P = (3,4)\) 。驗證： \((3,4)\) 在曲線上（ \(4^2 = 16 \equiv 1\) ， \(3^3 + 6 + 3 = 36 \equiv 1\) ）。✓ 群的循環結構使標量乘成為「指數」，離散對數在此群上定義。 \(\blacksquare\)

量子威脅與後量子密碼#

Shor（1994）的量子演算法在理想量子電腦上多項式時間解決分解與（交換群的）離散對數——RSA、DH、ECC 同時淪陷。對策是後量子密碼學（NIST 2022–24 標準化）：基於格上的問題（LWE）、編碼理論（5.2 節 Reed–Solomon 的親戚）、與同源（isogeny，橢圓曲線之間的群同態）——注意同源問題不受 Shor 的交換群攻擊影響，因為同源圖不是交換群。密碼學的下一章，仍然由群論與代數幾何寫成。

安全性證明的結構：從「難」到「可靠」#

密碼學對「難」的要求比直覺嚴格，值得在本節說清楚，因為它與本書「障礙即定理」的主題（10.3）直接相關。

RSA 的安全性論證是一條歸約鏈：

• 「求 \(\varphi(N)\) \(\Rightarrow\) 可分解 \(N\) 」：因 \(\varphi(N) = (p-1)(q-1)\) 與 \(p + q = N - \varphi(N) + 1\) 聯立即得 \(p, q\) （二次方程求解）。
• 「可分解 \(N\) \(\Rightarrow\) 求 \(\varphi(N)\) 」顯然。
• 故兩問題計算等價——這是嚴格的數學等價（多項式時間歸約）。

但最後一環是信念而非定理：「分解 \(N\) 是難的」。我們沒有下界證明（沒有人能證明經典電腦上分解必須超多項式時間）——這與 5.3 節尺規判決的氣質完全相反：那裡的不可能性是被證明的，這裡的不可能性是被賭上的。密碼學是一門「把未證明的難題當地基」的工程學科，其可靠性靠的是數十年攻擊者社群的失敗紀錄。這種「以失敗紀錄代替證明」的認識論結構，是數學與工程交界處最有趣的現象之一；Shor 演算法（1994）則展示了賭注的脆弱：換一個計算模型，整座大廈的地基一夜改寫。

與其他領域的關聯#

• 往 5.2： \(\mathbb{F}_p\) 、 \(\mathbb{F}_{2^m}\) 、乘法群循環性、Euler 定理——RSA 與 DH 的數學母體。
• 往 2.3、3.1：循環群與 Lagrange（子群階整除群階）是安全性證明的骨架（ \(E(\mathbb{F}_p)\) 的階由 Hasse 定理約束）。
• 往 9.3：橢圓曲線的 \(\ell\) -進上同調與 Galois 表示是 Wiles 證明 Fermat 大定理的機器——密碼學使用的同一對象，在純數學的另一端支撐著數論最深的定理。
• 往 6.1：橢圓曲線上的 Galois 表示是「Galois 對應」的當代最前線應用。
• 往 8.3：複數橢圓曲線的端同構環是 ADE 名單的成員（ \(\mathbb{Z}\) 或 Gauss/Golden 整數的階）。

結語#

公鑰密碼學是本書主題的最佳註腳：不是為了解方程而發展的代數，最後決定了「方程不可解」的商業價值。Gauss 研究 \(\mathbb{Z}/p\) 時不會想到 RSA；Hasse 研究曲線點數時不會想到比特幣。數學的不可預測性與其基礎設施價值，是同一枚硬幣。下一節，我們轉向物理——對稱群在那裡不只是工具，而是自然定律的語法。