Monday, September 23, 2019

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 = hP 將會用作加密用途。
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 協議的變種,在此不再詳述。

---
參考資料:

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

No comments:

Post a Comment