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²+a6

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

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

约掉 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)定义在某个域上,可以是有理数域、实数域、复数域,还可以是有限域GFpr),椭圆曲线密码体制中用到的椭圆曲线都是定义在有限域上的。

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

mP=P+P+…+P=Q

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

1.1域和椭圆曲线

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

素域Fp:

1q是奇素数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 = x2P2 <> −P1

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

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

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

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

举个简单的例子

素域Fp:以素域Fp为计算例子,取素数p=19.

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

2)     F19中加法的示例:10;14 ∈F1910+14=2424mod19=5,则10+14=5

3)     F19中乘法的示例:7;8 ∈F197×8=5656mod19=18,则7·8=18

4)     13F19的一个生成元,则F19中元素可由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

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

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

F19上椭圆曲线方程:y2 = x3+x+1,其中a = 1b = 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为正整数,Pk倍点为Q,即

Q = [k]P = P+P+· · ·+P   kp点)

安全性分析:

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

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

1)     Pohlig-Hellman方法:设ln的最大素因子,则算法复杂度为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)。例 ...