橢圓曲線加密的數學基礎與方法
本文透過建構數學相關基礎建立橢圓曲線加密的觀念。從羣的定義開始建立橢圓加密系統，而後建立橢圓曲線的離散對數問題(Discrete Logarithm Problem with Elliptic Curves, ECDLP). 最後介紹橢圓曲線的數位簽章演算法(Elliptic Curve Digital Signature Algorithm, ECDSA)
背景知識：
本文所介紹的內容假設讀者已經了解何謂 RSA 加密演算法以及數位簽章演算法(Digital Signature Algorithm, DSA)
動機：
在古典密碼學中，RSA密碼學已被廣泛地使用。為了增加RSA的安全性，我們不斷地增加密鑰的長度。然而，解密的時間也隨著密鑰長度的增長而愈來愈久。
同為古典密碼學的橢圓曲線密碼學(Elliptic curve cryptography, ECC)，在密鑰長度相等的前提下，其安全性較 RSA 高出許多。換言之，若要同時提高安全性並維持解密時間不變，使用橢圓加密便可解決這個問題。
內文：
為了保持文章整體的故事性，希望讀者不會有「為什麼突然講這個觀念」的感覺。數學內容會隨著故事的動機而引入，亦即數學結構會沒那麼有系統。
一、橢圓曲線 (Elliptic curve)
認識橢圓曲線加密前，我們先定義橢圓曲線：
（一）實數域上的橢圓曲線(Elliptic curve over the real numbers)
定義：（實數域上的橢圓曲線）(Elliptic curve over the cyclic group)
給定兩實數 a 和 b. 我們定義實數域上的橢圓曲線是平面上滿足 y²=x³+ax+b 的實數點集合。
我們希望透過這些點建立橢圓曲線的加密基礎，但是橢圓曲線是個連續函數，該集合的座標點有無限多個，我們希望能夠和 RSA 一樣使用有限個數的加密建立橢圓加密系統。
問題：
為何古典密碼學沒有考慮使用連續函數加密？（或者其實有，但這邊沒有找到相關資料）要將連續函數上的無限多的點，簡化成有限個點，我們引進了「同餘」的觀念。想像一個例子：正整數有無限多個，如果把所有正整數分成三類，分別是：
- 整除 3
- 除以 3 餘 1
- 除以 3 餘 2
如此一來就把無限多個東西分成了有限多組，每個正整數都是其中一組的組員。有了同餘的觀念，我們接著要建立的是 循環羣(Cyclic group) 上的橢圓曲線。
（二）循環羣上的橢圓曲線(Elliptic curve over an cyclic group) — 集合
什麼是循環羣？在了解循環羣之前，我們先介紹什麼是羣。
定義：（羣）
我們以 (G, · ) 代表一個羣，其中 G 是一個集合，而 · 是一個運算符號滿足以下四個條件：（運算符號可以是 +, -, *, / 等等自己定義的運算符號）
1. 封閉性：∀ a, b∈G, a · b ∈G
2. 結合律：∀ a, b, c∈G, (a · b) · c = a · (b · c)
3. 單位元：∀ a∈G, ∃ e∈G such that a · e= e· a = a
4. 反元素：∀ a∈G, ∃ b∈G such that a · b = b · a = 1
上面關於 除以 3 餘 1, 餘 2 和整除 的例子就是一個羣，其中
G = { 除以 3 餘 1, 除以 3 餘 2, 整除 3 } （這三個元素所形成的集合）
而 · 是個加法運算。
有了羣的概念，我們就可以來認識循環羣。
定義：（循環羣）
若一個羣 (G, · ) 中的所有元素可以用 G 的其中一個元素 透過 · 運算生成，則我們稱 (G, · ) 是一個循環羣。
剛剛才提到的 G = { 除以 3 餘 1, 除以 3 餘 2, 整除 3 } 其實就是一個循環羣。因為每一個元素都可以由 除以 3 餘 1 這個元素透過 + 進行生成。我們將這個羣記做 Z_3，若將除數改成 p ，則生成的羣記做 Z_p.
除以 3 餘 1 的數 = 除以 3 餘 1 的數
除以 3 餘 1 的數 + 除以 3 餘 1 的數 = 除以 3 餘 2 的數
除以 3 餘 1 的數 + 除以 3 餘 1 的數 + 除以 3 餘 1 的數 = 整除 3 的數
建立了循環羣的觀念，我們正式定義循環羣上的橢圓曲線：
定義：（循環羣上的橢圓曲線）(Elliptic curve over an cyclic group)
給定一個質數 p 以及兩整數 a, b∈Z_p. 我們定義循環羣上的橢圓曲線是平面上滿足 y² ≡ x³+ax+b (mod p) 的整數點 (x, y) 及一個無窮遠點所形成的集合。其中 4·a³ + 27·b² ≠ 0 (mod p) 而無窮遠點為這個循環羣的單位元
問題：p 是質數的必要性？有了以上的觀念，我們取得了有限個數的集合（也就是循環羣的 G ）作為橢圓加密算法的基礎。回顧羣的定義，我們還欠缺循環羣的運算規則，也就是 (G, · ) 的 ·
（三）循環羣上的橢圓曲線(Elliptic curve over an cyclic group) — 運算規則
我們知道循環羣上的橢圓曲線中，每個元素都是平面座標上的格子點 (x, y) 其中 x, y 都是整數。為了讓運算看起來沒有規律，以增加被有心人破密的複雜度，我們給出了以下的運算規則定義：
定義：（循環羣上的橢圓曲線運算規則-圖形版）
我們以符號+取代原先要定義的 · 並參考下圖。
給定 P, Q 兩個在橢圓曲線上的整數點，則循環羣上的橢圓曲線運算規則為：
P+Q=R，其中 R 點就是將 P, Q 兩點連線後與橢圓曲線的交點對稱於 X 軸。
若 Q = P, 則 R 點就是做 P 點切線交於橢圓曲線再將其交點對稱於 X 軸。
定義：（循環羣上的橢圓曲線運算規則-座標）
若 P(x_1, y_1), Q(x_2, y_2) 為橢圓曲線上滿足 y²=x³+ax+b (mod p) 的整數點則 R(x_3, y_3)=P+Q 的座標為：
x_3 = s²-x_1-x_2 (mod p)
y_3 = s(x_1-x_3)-y_1 (mod p)
其中，若 P=Q 則 s=frac{3x_1²+a}{2y_1} (mod p)
若 P≠Q 則 s=frac{y_2-y_1}{x_2-x_1} (mod p)
關於以上公式的推導，我們將 P, Q 兩點座標連線的方程式帶入橢圓曲線。會得到 x² 項係數為 PQ 兩點斜率的平方。根據根與係數，三根和
x_1+x_2+x_3 = -(frac{y_2-y_1}{x_2-x_1})
最後再由對稱前的點在斜直線上
s = frac{-y_3-y_1}{x_3-x_1}
得到 y_3 的值
當 P=Q 時，我們計算切線方程式的斜率為
(d/dx) sqrt(x³+ax+b) | x = x_1
=> m = (3x_1²+a) / 2 sqrt(x³+ax+b) = (3x_1²+a) / 2 y_1
有了完整的循環羣系統，我們可以從中獲得這個系統的幾個性質：
- P + O = P, 其中 O 代表無窮遠點。根據運算規則，幾何上可以想像一條過 P 點且與 Y 軸平行的鉛直線，交於 X 軸的對稱點後再對稱回原本的 P 點
- P + (-P) = O, 若 P 的座標為 (x_1, y_1), 則 -P 的座標為 (x_1, p-y_1)
問題：給定一個循環羣，我們可以定義出一套橢圓加密的規則。但不只是循環羣可以建構一套橢圓加密規則，兩循環羣的乘積(Product of two cyclic group)亦可。這邊牽涉到兩個羣乘積的定義，不會在此說明，讀者若有興趣可以研究相關的證明。二、橢圓曲線的離散對數問題 (Discrete Logarithm Problem with Elliptic Curves, ECDLP)
和 RSA 一樣，透過離散對數問題建立一組公鑰和私鑰。
定義：（橢圓曲線的離散對數問題）
給定一個橢圓曲線 E 以及一個循環羣 (G, · ) 並以 P 代表其中一個可以透過運算元生成整個羣的元素；以 T 代表羣的任意一個元素。橢圓曲線的離散對數問題是指：
給定 P 和 T, 求最小的 d 使得 P 加了 d 次之後等於 T。
即 P + P + … + P = T
在加密系統中，T 就是公鑰，而 d 就是私鑰。由於無法顯著地看出運算規則，要透過上述運算破解私鑰 d 是相當困難地。
三、橢圓曲線的數位簽章演算法 (Elliptic Curve Digital Signature Algorithm, ECDSA)
數位簽章的流程不外乎三步驟：產生金鑰、簽章、驗簽
給定一串訊息 x，以及一個 hash function h(·)
我們透過以下步驟進行簽章演算法的流程：
（一）產生金鑰：
- 選定 a 和 b 分別為橢圓曲線的係數，而 p 為同餘數。再選定一個循環羣 (G, · ) 並以 P 代表其中一個可以透過運算元生成整個羣的元素。其中這個循環羣的元素個數為 q
- 選擇任意一個符合 0 < d < q 的整數 d
- 計算 T = P + P +…+ P 共加 d 次
則我們可以得到：
公鑰：(p, a, b, q, P, T)
私鑰：(d)
（二）簽章：
- 隨機選定一個暫時的整數 e, 符合 0 < e < q.
- 計算 R = P + P +… + P 共加 e 次
- 取 r =( R 的 X 座標 )
- 計算 s ≡ (h(x) + d · r) · e^{-1} (mod q)
其中 e 的倒數可以透過輾轉相除法求得。
（三）驗章：
- 利用輾轉相除法計算 w ≡ s^{-1} (mod q)
- 計算 u ≡ w · h(x) (mod q)
- 計算 v ≡ w · r (mod q)
- 計算 A = u · P + v · T，也就是 P 加了 u 次後再加上 T 加了 v 次
- 若 A 的 X 座標 ≡ r (mod q) 則該簽章為合法的簽章，若不為 r 則該簽章不合法。
第一階段在產生公私鑰的時候已經將公鑰 (p, a, b, q, P, T) 送出
第二階段的簽章發送的是一段文字 x 以及簽名 (r, s)
第三階段僅是驗證 (r, s) 確認訊息 x 是否是由一開始發送公鑰的人所傳遞
以上是橢圓加密簽章的原理。
後記：本文盡可能避免提及「體 (Field)」相關的術語，這也是為什麼常常看到P+P+...+P，因為我們定義的羣中沒有乘法的運算機制(雖然最後還是用了QQ)，但我們暫時可以用乘法去理解它。引入了體的觀念後，這個乘法的概念也是正確的。事實上每個循環羣Z_p（p 是質數）都是一個有限體(Galois field)，讀者有興趣可自行研究。希望能透過這篇文章，讓沒有相關背景知識的讀者能對簽章的原理有初步的了解。
也勉勵若沒有相關背景的讀者若能理解其中的內容，不妨可以看看有限體的定義。文章中間留下許多問題討論，歡迎讀者們提供想法。
也歡迎大家為這篇文提供批評和建議，讓這篇文能夠愈來愈好。