2017.W19 - 橢圓曲線加密 ECC
> 學術介紹 輕鬆了解
## 前言 ##
橢圓曲線加密 (Elliptic Curve Cryptography, ECC)[0]
是基於橢圓曲線數學的一種公開金要加密演算法
相對於 RSA 可以用較短的金鑰來獲得相等的安全防護
## 內容 ##
橢圓曲線 (Elliptic Curve)[1] 是數學上一個代數曲線的分類
可以利用通式 : y^2 = x^3 + ax + b 來表示
原則上來說 所有 y 為二次且 x 為三次的多項式函數 都可透過伸縮與平移來獲得通式形式
橢圓曲線有若干特色與性質：
1. 沒有 cusp[2] 與 crunode[3]
2. 假設無窮遠點為 O，則 EC 跟直線必有三個根
相對於 RSA 是把質因數分解[5]當作是破解的困難點
ECC 則是把離散對數 (Discrete Logarithm) [6] 當作是破解的關鍵
給定一個質數 p 給定一個 數字 k 與 c
找到一個 m 滿足 c = m^k (mod p) 是困難的
把兩個概念整合起來 ECC 就是一個在橢圓曲線上的 Galois Field 的運算
其中的運算如下：
0. 無限遠的點為 0
1. P、Q 為 EC 上的一個點
2. P + 0 = P
3. P - P = 0
4. P + Q = -Z, 且 P, Q, Z 在同一個直線且同時為 EC 上的三個根
5. 2*p = P + P，同規則 4 且直線為切線
而 ECDLP (Elliptic Curve Discrete Logarithm Problem) 就是解決
給定一個橢圓曲線 C，並且任意給兩點 P、Q
找到一個 k 滿足 k * P = Q (on C)
## 驗證 ##
用一個 DLP 來當做例子：
假設有一個 GF(23) 也就是可用元素為 0 ~ 22，且所有運算都需要 module 23
計算 4 ^ 5 (mod 23) 是簡單的 用 Python 的語法則會是 pow(4, 5, 23)
計算方式為：4^5 = 4 * 4^4 其中我們可以快速鍵表格
4 = 4 (mod 23)
4^2 = 16 (mod 23)
4^4 = 3 (mod 23)
因此 pow(4, 5, 23) = 12
相反的... x^7 = 7 (mod 23) 要找出來 x 則是困難的 (一個有效的計算方式)
至於 ECDLP 有興趣的人 可以 Google 找相關的資料檢驗他的困難程度
[0]: https://zh.wikipedia.org/wiki/%E6%A4%AD%E5%9C%86%E6%9B%B2%E7%BA%BF%E5%AF%86%E7%A0%81%E5%AD%A6
[1]: https://zh.wikipedia.org/wiki/%E6%A4%AD%E5%9C%86%E6%9B%B2%E7%BA%BF
[2]: https://zh.wikipedia.org/wiki/%E5%B0%96%E9%BB%9E
[3]: https://en.wikipedia.org/wiki/Crunode
[4]: https://zh.wikipedia.org/wiki/%E6%9C%89%E9%99%90%E5%9F%9F
[5]: https://zh.wikipedia.org/wiki/%E6%95%B4%E6%95%B0%E5%88%86%E8%A7%A3
[6]: https://en.wikipedia.org/wiki/Discrete_logarithm