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 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 123.193.122.171 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/NetSecurity/M.1494334702.A.07A.html