要理解 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，破解時間會較長。
同時，因為每次加 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 協議的變種，在此不再詳述。
---
參考資料：
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/
https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/
CX4024 Lecture 4 - 2018, Anwitaman Datta, Nanyang Technological University
