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