椭圆曲线加密算法原理解析ECC

jiezi

6 年前

随着计算机性能的提升，市面上的加密技术越来越不安全，1024 位的 RSA 私钥加密已经可以破解，目前有效的手段只是将 1024 位换成 2048 位，但随着技术的进步，RSA 算法的破解难度会越来越低，因此需要用更安全的加密算法来代替，下面我们来介绍更为安全的 ECC 公钥加密算法
什么是 ECC
ECC 是 Elliptic Curve Cryptography（椭圆曲线密码学）的缩写，是一种基于椭圆曲线数学的公开密钥加密算法，其本质是利用离散对数问题实现加密。
ECC 的主要优势，是在使用更小的密钥的同时，提供更快的性能和更高等级的安全。
什么是椭圆曲线
Wolfram MathWorld（线上数学百科全书，http://mathworld.wolfram.com）给出了非常精准的定义：
一条椭圆曲线就是一组被 y^2 = x^3 + ax + b 定义的且满足 4a^3 + 27b^2 ≠ 0 的点集。
4a^3 + 27b^2 ≠ 0 这个限定条件是为了保证曲线不包含奇点（在数学中是指曲线上任意一点都存在切线）。
椭圆曲线示例图：

                   不同的椭圆曲线对应不同的形状（b=1，a 从 2 到 -3)

      左（带锐点）：y^2 = x^3
     右（曲线自交）：y^2 = x^3 -3x + 2
      都不是有效的椭圆曲线

阿贝尔群的概念是抽象代数的基本概念之一，是一种代数结构，由一个集合以及一个二元运算所组成。
如果一个集合或者运算是群的话，就必须满足以下条件（+ 表示二元运算）：
1、封闭性（closure），如果 a 和 b 被包含于群，那么 a + b 也一定是群的元素；
2、结合律(associativity)；
3、存在一个单位元（identity element）0，0 与任意元素运算不改变其值的元素，即 a+0 = 0+a = a；
4、每个元素都存在一个逆元(inverse)；
5、交换律(commutativity)，即 a+b = b+a；

我们可以在椭圆曲线上定义一个群：
1、群中的元素就是椭圆曲线上的点；
2、单位元就是无穷处的点 0；
3、相反数 P，是关于 X 轴对称的另一边的点；
4、二元运算规则定义如下：取一条直线上的三点（这条直线和椭圆曲线相交的三点），P, Q, R（皆非零），他们的总和等于 0，
P+Q+R=0。

如果 P, Q, R 在一条直线上的话，他们满足:

                P+(Q+R)=Q+(P+R)=R+(P+Q)=⋯=0。

当 P，Q 点为同一点时,P=Q，满足：

这样，我们可以直观的证明：+ 运算符是符合交换律和结合律的，这是一个阿贝尔群。
因为阿贝尔群满足交换律和结合律，所以点 P 和点 - R 的二元运算结果必会在曲线上，即 P +P+ P 的结果必会在曲线上的另一点 Q，
以此类推，可以得出得出：

          Q=kP(k 个相同的点 P 进行二元运算（数乘）, 记做 kP)

前文中有提到离散对数问题，我们熟悉的 RSA 算法，是基于大数的质因数分解，即对两个质数相乘容易，而将其合数分解很难的这个特点进行加密。
而 ECC 算法是在有限域 Fp 定义公式：Q=kP，已知大数 k 和点 P 的情况下，很容易求点 Q，但是已知的点 P、点 Q，却很难求得 k，这就是经典的离散对数问题，ECC 算法正是利用该特点进行加密，点 Q 为公钥，大数 k 为私钥，点 P 为基点，和 RSA 最大的实际区别，主要是密钥长度

描述一条 Fp 上的椭圆曲线，常用到六个参量：T=(p,a,b,n,x,y)。
（p、a、b）用来确定一条椭圆曲线，p 为素数域内点的个数，a 和 b 是其内的两个大数；
x,y 为 G 基点的坐标，也是两个大数；
n 为点 G 基点的阶；
以上六个量就可以描述一条椭圆曲线，有时候我们还会用到 h(椭圆曲线上所有点的个数 p 与 n 相除的整数部分)。
现在我们描述一个利用椭圆曲线进行加密通信的过程：
1、选定一条椭圆曲线 Ep(a,b) 并取椭圆曲线上一点，作为基点 P。
2、选择一个大数 k 作为私钥，并生成公钥 Q=kP。
3、将 Ep(a,b) 和点 Q、P 传给用户。
4、用户接到信息后，将待传输的明文编码到 Ep(a,b)上的一点 M，并产生一个随机整数 r。
5、公钥加密（密文 C 是一个点对）：
C={rP, M+rQ}
6、私钥解密（M + rQ – k(rP)，解密结果就是点 M），公式如下：

        M + rQ - k(rP) = M + r(kP) - k(rP) = M

7、对点 M 进行解码就可以得到明文
假设在加密过程中，有一个第三者 H，H 只能知道椭圆曲线 Ep(a,b)、公钥 Q、基点 P、密文点 C，而通过公钥 Q、基点 P 求私钥 k 或者通过密文点 C、基点 P 求随机数 r 都是非常困难的，因此得以保证数据传输的安全。

因为在安全性、加解密性能、网络消耗方面有较大优势，ECC 加密算法大有取代 RSA 成为下一代主流加密算法的趋势。如今 ECC 应用范围很广，在 TLS、区块链（比特币、以太坊等等）、SM2 国密算法、证书、银行政府机构等许多方面都有大量应用。

椭圆曲线加密算法原理解析ECC

前言

关于阿贝尔群(abelian group)

椭圆曲线中的阿贝尔群

离散对数问题

椭圆曲线加密算法原理

ECC 应用