橢圓曲線（elliptic curve）是平面上的一條曲線——一群具有 x 與 y 座標的點。曲線的方程式定義了所有屬於該曲線的點。

例如 y = 3 是縱座標為 3 的水平線，y = ax + b 形式的曲線是直線，x² + y² = 1 是以原點為中心、半徑為 1 的圓。無論哪種曲線，曲線上的點就是所有滿足該曲線方程式的 (x, y) 對。

密碼學所用的形式#

密碼學所用的橢圓曲線，方程式通常是 Weierstrass 形式：

y² = x³ + ax + b

其中常數 a 與 b 定義了曲線的形狀。

本章聚焦於最簡單、最常見的橢圓曲線型態，但也有其他形式的橢圓曲線。

例如 Edwards 曲線的方程式形式是 x² + y² = 1 + dx²y²，它們有時被用於密碼學（例如 Ed25519 方案）。

曲線上的點#

以 y² = x³ − 4x 為例：

• x = 0：y² = 0³ − 4×0 = 0，因此 y = 0 是解，點 (0, 0) 屬於曲線。
• x = 2：y² = 8 − 8 = 0，因此 y = 0，點 (2, 0) 屬於曲線。
• x = 1：y² = 1 − 4 = −3。沒有解（沒有實數平方後等於 −3），因此曲線在 x 軸這個位置上沒有點。
• x = −1：y² = −1 + 4 = 3，有兩個解 y = √3 與 y = −√3。

平方一個數永遠得到正數，所以對任何實數 y 都有 y² = (−y)²。因此所有 y² = x³ + ax + b 形式的橢圓曲線，對 x 軸都是對稱的。

（y² = −3 在複數中有解，但橢圓曲線密碼學只處理自然數——更精確地說，是質數之模下的整數。）

整數上的橢圓曲線#

這裡有個轉折：橢圓曲線密碼學所用的曲線，實際上看起來不像一條曲線，而像一團點雲。

差別在於點所在的數集不同：

• 在實數上，曲線是連續的——它包含 x = 2.0、x = 2.1、x = 2.00002 等所有點。
• 在整數上，只顯示滿足方程式的整數，排除了小數。

例如同樣的 y² = x³ − 4x，若取模 191 的整數（0, 1, 2, …, 190，記為 Z191），所有點的 x、y 座標都是模 191 的整數：

• x = 2：y² = 0，y = 0 是有效解，點 (2, 0) 屬於曲線。
• x = 3：y² = 27 − 12 = 15。這在 Z191 中有兩個解——46 與 145，因為 46² mod 191 = 15 且 145² mod 191 = 15。因此點 (3, 46) 與 (3, 145) 都屬於曲線。

這裡用的是 Z191 = {0, 1, 2, ..., 190}，包含零——這與我們在 RSA 與 Diffie–Hellman 脈絡下討論的 Zp*（帶星號）不同。

原因是：我們同時要做乘法與加法，因此需要確保數集包含加法的單位元（也就是 0，使 x + 0 = x）。而且每個數 x 都有加法反元素 −x 使 x + (−x) = 0（例如 Z191 中 100 的反元素是 91，因為 100 + 91 mod 191 = 0）。

這種「加法與乘法都可行、每個元素都有加法反元素、且除零之外每個元素都有乘法反元素」的數集，稱為體（field）。當一個體有有限個元素時（如 Z191，以及所有用於橢圓曲線密碼學的體），就稱為有限體（finite field）。

點的加法#

橢圓曲線上的點可以相加，規則稱為加法律（addition law）。

一般情況：兩個相異點#

要把曲線上兩點 P 與 Q 相加得到 R = P + Q，最簡單的理解方式是幾何規則：

幾何規則不會直接給你 R 的座標。用 P 的座標 (xP, yP) 與 Q 的座標 (xQ, yQ) 計算 R 的座標 (xR, yR)：

xR = m² − xP − xQ
yR = m(xP − xR) − yP

其中 m = (yQ − yP) / (xQ − xP)  是連接 P 與 Q 之直線的斜率

遺憾的是，這些公式與畫線的技巧不總是管用：

• 若 P = Q，你無法在兩點之間畫線（只有一個點）。
• 若 Q = −P，那條線不會再次與曲線相交，因此沒有點可以鏡射。

特例一：點與其負元相加#

點 P = (xP, yP) 的負元是 −P = (xP, −yP)——繞 x 軸鏡射的點。對任何 P：

P + (−P) = O

無窮遠點是屬於任何橢圓曲線的虛擬點；它之於橢圓曲線，就如同零之於整數。

特例二：倍點#

當 P = Q 時，把 P 與 Q 相加等同於計算 P + P（也記為 2P），這個加法操作稱為倍點（doubling）。

由於無法在 P 與它自己之間畫線，改為畫出曲線在 P 處的切線，2P 就是這條切線與曲線相交之點的負元。

座標公式基本相同，但 m 的值不同：

xR = m² − xP − xQ
yR = m(xP − xR) − yP

其中 m = (3·xP² + a) / (2·yP)   a 是曲線參數

點的乘法#

要把橢圓曲線上的點乘以某個整數 k，我們把 P 與自己相加 k − 1 次來決定點 kP：

2P = P + P
3P = P + P + P
...

但要有效率地計算 kP，「套用加法律 k − 1 次」這種天真做法遠非最佳。

若 k 很大（例如橢圓曲線密碼方案中 2^256 這個量級），計算 k − 1 次加法根本不可行。

例如要算 8P，不必用天真方法做 7 次加法，只要 3 次：

P₂ = P + P
P₄ = P₂ + P₂
8P = P₄ + P₄

橢圓曲線群#

由於點可以相加，橢圓曲線上的點集構成一個群：

• 封閉性：若 P 與 Q 屬於某曲線，則 P + Q 也屬於該曲線。
• 結合律：對任意 P, Q, R 都有 (P + Q) + R = P + (Q + R)。
• 單位元：無窮遠點 O，使 P + O = P。
• 反元素：每個點 P = (xP, yP) 都有反元素 −P = (xP, −yP)，使 P + (−P) = O。

實務上，多數基於橢圓曲線的密碼系統，其 x 與 y 座標都是某質數 p 之模下的數（也就是有限體 Zp 中的數）。

曲線的階#

就像 RSA 的安全性取決於所用數字的大小，橢圓曲線密碼系統的安全性取決於曲線上點的數量。

那要如何知道橢圓曲線上點的數量（它的基數，cardinality）？這取決於曲線與 p 的值。

一個經驗法則是：曲線上大約有 p 個點。

但你可以用 Schoof 演算法算出精確的點數——它計算有限體上橢圓曲線的點數，SageMath 已內建：

sage: Z = Zmod(191)
sage: E = EllipticCurve(Z, (-4,0))
sage: E.cardinality()
192

上例先把變數 Z 定義為模 191 的整數集，再把 E 定義為 Z 上係數為 −4 與 0 的橢圓曲線，最後算出曲線上的點數——也稱為它的基數、群階（group order）或就叫階。

這個計數包含了無窮遠點 O。