ECC 椭圆加密算法数学基础

椭圆加密算法 ECC（Elliptic Curve Crypto）是一种公钥加密体制，最初由 Koblitz 和 Miller 两人于 1985 年提出，其数学基础是利用椭圆曲线上的有理点构成 Abel 加法群上椭圆离散对数的计算困难性。

公钥密码体制根据其所依据的难题一般分为三类：大整数分解问题类、离散对数问题类、椭圆曲线类。有时也把椭圆曲线类归为离散对数类。

 

1. 为什么使用 ECC

RSA 解决分解整数问题，需要亚指数时间复杂度的算法，而目前已知计算椭圆曲线离散对数问题(Elliptic Curve Discrete Logarithm Problem，缩写为ECDLP)的最好方法都需要全指数时间复杂度。

这意味着在椭圆曲线系统中，我们只需要使用相对于 RSA 短得多的密钥就可以达到与其相同的安全强度。

例如，160bit 的椭圆曲线密钥提供的安全强度与 1024bit RSA 密钥相当，210bit 的椭圆曲线密钥提供的安全强度与 2048bit RSA 密钥相当。

使用短的密钥的好处在于加解密速度快、节省能源、节省带宽、存储空间。

比特币和中国的二代身份证都使用了256 比特的椭圆曲线密码算法。

目前在数字签名领域RSA算法使用较为广泛，随着计算机网络的迅速发展，ECC算法也已经有了一定程度的应用。

ECC算法由于其抗攻击性强、占用存储空间小和加密速度快等优势开始受到人们越来越多的重视，其应用前景也将会更加广阔。

 

2. 椭圆曲线

我们在高中就学过标准圆的方程：

x² + y² = r² 。

而标准椭圆曲线的方程：

x²/a² +  y²/b² = 1  (a>b，焦点在 x 轴，a<b，焦点在 y 轴)。

本文提到的椭圆曲线，跟这个高中时代的椭圆曲线方程基本无关。ECC 椭圆曲线方程是一个二元三次方程，它的图形就不是一个椭圆，椭圆曲线的椭圆一词来源于椭圆周长积分公式。

一条椭圆曲线是在射影平面上满足威尔斯特拉斯方程（Weierstrass）所有点的集合，Weierstrass）方程是一个齐次方程：

Y²Z+a1​XYZ+a3​YZ²=X³+a​2X²Z+a4​XZ²+a6Z³

对普通平面上点 (x,y)，令 x=X/Z，y=Y/Z，Z≠0，得到如下方程：

y²Z³+a1​xyZ³+a3​yZ³=x³Z³+a​2x²Z³+a4​xZ³+a6Z³

约掉 Z³，可以得到：

y²+a1​xy+a3​y=x³+a​2x²+a4​x+a6

令 a1=0 ，a3= 0，a​2=0，a4=a，a6=b，那么简化后的 Weierstrass 方程：

E: y²=x³+ax+b

其中：

  • Δ = − 16 ( 4a3+ 27b ) ≠ 0，用来保证曲线是光滑的，即曲线的所有点都没有两个或者两个以上的不同的切线。
  • a，b∈K，K 为 E 的基础域。
  • 点 O∞ 是曲线的唯一的无穷远点。

 

3. 椭圆曲线示例

 

4. 椭圆曲线阿贝尔群

我们已经看到了椭圆曲线的图象，但点与点之间好象没有什么联系。我们能不能建立一个类似于在实数轴上加法的运算法则呢？这就需要定义椭圆曲线的加法群，用到近世代数中的阿贝尔群。

在数学中，群是一种代数结构，由一个集合和一个二元运算组成。

已知集合和运算(G,*)，如果满足以下要求，那么这个集合和运算(G,*)就构成群：

  • 封闭性： ∀a,b∈G，ab ∈ G
  • 结合律： ∀a,b,c∈G ，有 (ab)c = a (bc)
  • 单位元： ョe∈G， ∀a ∈G，有ea = ae = a
  • 逆元： ∀a ∈G ，ョb∈G 使得 ab = ba = e

如果一个群满足交换律，那么这个群就称为可交换群，又叫做阿贝尔群（Abelian Group）或者加群：

  • 交换性: ∀a,b∈G，ab = ba

椭圆曲线可以定义阿贝尔群。

任意取椭圆曲线上两点P、Q（若P、Q两点重合，则作 P 点的切线），作直线交于椭圆曲线的另一点 R’，过 R’ 做 y 轴的平行线交于 R，定义 P+Q=R。

这样，加法的和也在椭圆曲线上，并同样具备加法的交换律、结合律。

 

若有 k 个相同的点 P 相加，记作 kP 。

例如：P+P=2P。

例如：P+P+P=2P+P=3P。

5. 有限域椭圆曲线

椭圆曲线是连续的，并不适合用于加密。所以，我们必须把椭圆曲线变成离散的点，我们要把椭圆曲线定义在有限域上。

我们给出一个有限域 Fp。

  • Fp 中有 p 个元素 0，1，2，…，p-2，p-1，其中 p为质数
  • Fp 加法是 a + b ≡ c (mod p) a+b
  • Fp 乘法是 a × b ≡ c (mod p)
  • Fp 除法是 a ÷ b ≡ c (mod p) ，即 a × b-1≡ c (mod p)， b-1 也是一个 0 到 p − 1 之间的整数，但满足 b × b-1≡ 1(mod p) 。
  • Fp的单位元是1，零元是 0
  • Fp域内运算满足交换律、结合律、分配律
  • 椭圆曲线Ep(a,b)，p为质数，x,y∈[0,p-1]

    y²=x³+ax+b (mod p)选择两个满足下列约束条件的小于p的非负整数a、b :

 

所确定的平面曲线。其中系数ai(I=1,2,…,6)定义在某个域上，可以是有理数域、实数域、复数域，还可以是有限域GF（pr），椭圆曲线密码体制中用到的椭圆曲线都是定义在有限域上的。

椭圆曲线上所有的点外加一个叫做无穷远点的特殊点构成的集合，连同一个定义的加法运算构成一个Abel群。在等式

mP=P+P+…+P=Q

中，已知m和点P求点Q比较容易，反之已知点Q和点P求m却是相当困难的，这个问题称为椭圆曲线上点群的离散对数问题。椭圆曲线密码体制正是利用这个困难问题设计而来。

 

1.1域和椭圆曲线

概述：给出有限域Fq的描述及其元素的表示，q是一个奇素数或者是2的方幂。当q是奇素数p时，要求p > 2^191；当q是2的方幂2^m时，要求m > 192且为素数。

素域Fp:

1）当q是奇素数p时，素域Fp中的元素用整数0;1;2; · · · ; p−1表示。

a) 加法单位元是整数0；

b) 乘法单位元是整数1；

c) 域元素的加法是整数的模p加法，即若a;b ∈ Fp，则a+b = (a+b) mod p；

d) 域元素的乘法是整数的模p乘法，即若a;b ∈ Fp，则a · b = (a · b) mod p。

2）定义在Fp(p是大于3的素数)上的椭圆曲线方程为：

y2=x3+ax+b， a;b ∈ Fp，且(4a3+27b2) mod p ≠ 0。

椭圆曲线E(Fp)定义为：

E(Fq) = {(x;y)|x;y ∈ Fp，且满足方程(1)}∪{O}，其中O是无穷远点。

椭圆曲线E(Fp)上的点的数目用#E(Fq)表示，称为椭圆曲线E(Fp)的阶。

 如果椭圆曲线上一点P，存在最小的正整数n，使得数乘nP=0∞，则将n称为P的阶，若n不存在，我们说P是无限阶的。

事实上，在有限域上定义的椭圆曲线上所有的点的阶n都是存在的（证明，请参考近世代数方面的书）

3）仿射坐标表示：

E(Fp)上的点按照下面的加法运算规则，构成一个阿贝尔群：

a) O+O = O；

b) ∀P = (x;y) ∈ E(Fp)\{O}，P+O = O+P = P；

c) ∀P = (x;y) ∈ E(Fp)\{O}，P的逆元素−P = (x;−y)，P+(−P) = O；

d)点P1 = (x1;y1) ∈ E(Fp)\{O}，P2 = (x2;y2) ∈ E(Fp)\{O}，P3 = (x3;y3) = P1+P2 = O，则

x3 = λ2−x1−x2 ;

y3 = λ(x1−x3)−y1;

其中

λ = (y2−y1)/(x2−x1);           若x1 <> x2;

λ = (3x12+a)/(2y1);             若x1 = x2且P2 <> −P1。

二元扩域F2m:当q是2的方幂2m时，二元扩域F2m可以看成F2上的m维向量空间，其元素可用长度为m的比特串表示。

定义在F2m上的椭圆曲线方程为：

y2+xy = x3+ax2+b， a;b ∈ F2m，且b = 0。

接下来主要是介绍素域Fp上的算法运用，二无扩域F2m后面不再介绍，有兴趣的同学可以自己找些资料。

举个简单的例子

素域Fp：以素域Fp为计算例子，取素数p=19.

1)     素域F19，F19 = {0;1;2; ·· · ;18}

2)     F19中加法的示例：10;14 ∈F19，10+14=24，24mod19=5，则10+14=5。

3)     F19中乘法的示例：7;8 ∈F19，7×8=56，56mod19=18，则7·8=18。

4)     13是F∗19的一个生成元，则F∗19中元素可由13的方幂表示出来：

130= 1;131= 13;132= 17;133= 12;134= 4;135=14;136= 11;137=10;138=16;

139= 18,1310= 6;1311= 2;1312= 7;1313= 15;1314= 5;1315= 8;1316= 9;

1317= 3;1318= 1。

注：记F∗p是由Fp中所有非零元构成的乘法群，由于F∗p是循环群，所以在Fp中至少存在一个元素g，使得Fp中任一非零元都可以由g的一个方幂表示，称g为F∗p的生成元(或本原元)，即F∗p ={gi|0≤i≤ p−2}。设a = gi∈ F∗p，其中0 ≤ i ≤ p−2，则a的乘法逆元为：a−1= gp−1−i。

E(Fp)阶与仿射坐标表示：

F19上椭圆曲线方程：y2 = x3+x+1，其中a = 1，b = 1。则F19上曲线的点为：

(0,1), (0,18), (2,7), (2,12), (5,6), (5,13), (7,3), (7,16), (9,6), (9,13), (10,2), (10,17), (13,8), (13,11), (14,2),(14,17), (15,3), (15,16), (16,3), (16,16),

则E(F19)有21个点(包括无穷远点0)。

a) 取P1 = (10;2)，P2 = (9;6)，计算P3 = P1 +P2：

λ= (y2 −y1)/(x2 −x1)= (6−2)/(9−10)= 4/−1= −4 ≡ 15 (mod19);

x3 = λ2−x1−x2 =152-10-9 = 225−10−9 ≡ 16−10−9 = −3 ≡ 16 (mod19);

y3 = λ(x1−x3)−y1= 15×(10−16)−2 = 15×(−6)−2 ≡ 3 (mod19)，

所以P3 = (16;3)。

b)取P1 = (10;2)，计算[2]P1：

λ= (3x12+a)/(2y1) = (3×102+1)/2×2= 4= 4 (mod19);

x3 =λ2−x1−x2 =42−10−10 = −4 ≡ 15 (mod19)，

y3=λ(x1−x3)−y1= 4×(10−15)−2 = −22 ≡ 16 (mod19)，

所以[2]P1 = (15;16)。

 

椭圆曲线多倍点运算：

设P是椭圆曲线E上阶为N的点，k为正整数，P的k倍点为Q，即

Q = [k]P = P+P+· · ·+P   （k个p点）

安全性分析：

安全主要是依靠椭圆曲线离散对数求解方法问题(ECDLP)。

已知椭圆曲线E(Fq)，阶为n的点P ∈ E(Fq)及Q ∈ ⟨P⟩，椭圆曲线离散对数问题是指确定整数k ∈[0;n−1]，使得Q = [k]P成立。

1)     Pohlig-Hellman方法：设l是n的最大素因子，则算法复杂度为O(l1=2)；

2)     BSGS方法：时间复杂度与空间复杂度均为(πn=2)1=2；

3)     Pollard方法：算法复杂度为(πn=2)1=2；

4)     并行Pollard方法：设r为并行处理器个数，算法复杂度降至(πn=2)1=2=r；

5)     MOV-方法：把超奇异椭圆曲线及具有相似性质的曲线的ECDLP降到Fq的小扩域上的离散对数问题（亚指数级计算复杂度算法）；

6)     异常曲线离散对数求解方法：对异常曲线(#E(Fp) = p的曲线)的有效攻击方法(多项式级计算复杂度算法)；

7)       GHS-方法：利用Weil下降技术求解扩张次数为合数的二元扩域上椭圆曲线离散对数问题，将ECDLP转化为超椭圆曲线离散对数问题，而求解高亏格的超椭圆曲线离散对数存在亚指数级计算复杂度算法。

对于一般曲线的离散对数问题，目前的求解方法都为指数级计算复杂度，未发现有效的亚指数级计算复杂度的一般攻击方法；而对于某些特殊曲线的离散对数问题，存在多项式级计算复杂度或者亚指数级计算复杂度算法。

选择曲线时，应避免使用易受上述方法攻击的密码学意义上的弱椭圆曲线。

 

ECC技术要求

通常将Fp上的一条椭圆曲线描述为T=(p,a,b,G,n,h) p、a、b确定一条椭圆曲线（p为质数，(mod p)运算）G为基点，n为点G的阶，h是椭圆曲线上所有点的个数m与n相除的商的整数部分

参量选择要求：

  • p 越大安全性越好，但会导致计算速度变慢；
  • 200bit左右可满足一般安全要求；
  • n 应为质数 h≤4；p≠n×h ；pt≠1 (mod n) (1≤t＜20)；
  • 4a3+27b2 ≠ 0 (mod p)


ECC的应用（比特币）

比特币系统选用的 secp256k1 中，参数为:

  • p = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F = 2256 − 232− 29 − 28− 27 − 26 − 24− 1
  • a = 0， b = 7
  • G=(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)
  • n = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
  • h = 01

椭圆曲线方程为：y2 = x3+7。

有限域上的逆元计算求解逆元，即逆元素，是指一个可以取消另一给定元素运算的元素，在数学里，逆元素广义化了加法中的加法逆元和乘法中的倒数。在正整数有限域 Fp (p是素数)上，a 的乘法逆元 b 满足：ab ≡ 1(mod p)。例 ...