Understanding Elliptic Curve Cryptography（橢圓曲線加密學）

要理解 ECC, 首先要了解 Elliptic Curve 的特性和定義。

以下內容會以最簡單的方式表達。

1. Elliptic Curve 的定義：

• y^2 = x^3 + ax + b
• 當中 4a^3 + 27b^2 != 0 （有 cusp 或者 self-intersection 交點的曲線都不算 Elliptic Curve）

符合 EC 的例子（a = -7 , b = 10）：

---

2. Elliptic Curve 的特性：

• 用圖片表示的話，你會發現所有 EC 都會有 P+Q+R=0 的特性
• （注意：這裏用的 P/Q/R 並非普通座標計算，而是有特定的公式）

用圖片表達，你會發現以下的現象：

為了方便日後討論，我們重新定義 EC 的加法「＋」和乘法「・」的意思：

加法 (Algebraic Addition)： 

• 假設 P != Q，斜率 m = ( y_p - y_q ) / ( x_p - x_q )
• 如果 P = Q，斜率 m = 3x_p^2 + a / 2y_p （如果用上一條式，除 0 計不到啊）
• R = ( x_r , y_r  ) , x_r = m^2 - x_p - x_q , y_r = y+p + m(x_r - x_p)

乘法 (Scalar Multiplication)：

• 這個簡單得多，n・P 不就是 P + P + ... + P 共 n 次嗎？
• 所以計法就是不斷用上面的加法，一直加到 n 次
• （但如果真的加 n 次，計算時間就會太繁複，所以有人想到用 double and add 的方法加速，在此不述）

---

3. 加了餘數 (modulo) 的 EC 公式

加了餘數的公式將會變成：

• y^2 = (x^3 + ax + b) mod p
• 當中 (4a^3 + 27b^2) != 0 mod p 
• 假設 P != Q，斜率 m = ( y_p - y_q )*( x_p - x_q )^-1 mod p
• 如果 P = Q，斜率 m = (3x_p^2 + a)*(2y_p)^-1 mod p 
• R = ( x_r , y_r  ) , x_r = (m^2 - x_p - x_q) mod p , y_r = [ y+p + m(x_r - x_p) ] mod p

可見即使加了 mod，P+Q+R = 0 的特性仍然生效，而且公式也很像樣（數學證明在此不述）。

以下圖表則是 mod 版本的 EC：

---

4. 找出重複規律

Mod 版的 EC 在不斷進行 P 點相加後，會出現重複規律。

例如 y^2 = (x^3 -x + 3) mod 37，如果從 P=(2,3) 開始，每加 7 次就會出現 R = (0,0) 

我們要找出其最小規律 (subgroup order n) ，任由選一個規律倍數 (order N)，

並且只用這個規律中的餘因子 (cofactor h = N/n) 來進行加密。

例子：y^2 = (x^3 -x + 3) mod 37, n = 7, N = 7, 14, 21, 28, 42, 49 ...

最後，G = h・P 將會用作加密用途。

h 會成為私密鑰匙。對方如果想找出 h，唯一方法就只有不斷加 P。
同時，因為每次加 P 都要用 double and add，相比傳統 RSA，破解時間會較長。

---

5. 用作非對稱加密 (Asymmetric Encryption)

公鑰 (Public Key): a, b, p, G, P 

私鑰 (Private Key): h

加密 M ：C = {kP, M + kG} （k 只有發送者知道）

解密 C：M + kG - hkP = M + khP - hkP = M

---

6. 用作交換共同金鑰 (EC Diffie-Hellman Key Exchange)

假設 Alice 和 Bob 均使用同一點 G:

Alice 公鑰 (Public Key): Ha = da・G 

Alice 私鑰 (Private Key): da

Bob 公鑰 (Public Key): Hb = db・G

Bob 私鑰 (Private Key): db

Alice 計算出 S = da・(Hb) = da・db・G

Bob 計算出 S = db・(Ha) = db・da・G

所以，他們就能有同一條金鑰 S 用作對稱加密。

---

7 . 用作簽署 (ECDSA)

由於只是 DSA 協議的變種，在此不再詳述。

---

參考資料：

https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/

http://course.ece.cmu.edu/~ece733/lectures/21-intro-ecc.pdf

http://amitmason.blogspot.com/2016/08/elliptic-curve-cryptography_37.html
https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/

CX4024 Lecture 4 - 2018, Anwitaman Datta, Nanyang Technological University