有限域椭圆曲线
有限域椭圆曲线
椭圆曲线是连续的,并不适合用于加密;所以,我们必须把椭圆曲线变成离散的点,我们要把椭圆曲线定义在有限域上。
我们给出一个有限域Fp
-
Fp中有p(p为质数)个元素0,1,2,…, p-2,p-1
-
Fp的加法是a+b≡c(mod p)
-
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]
y2=x3+ax+b(modp)
选择两个满足下列约束条件的小于p的非负整数a、b
4a3+27b2≠0(modp)
Fp上的椭圆曲线同样有加法
-
1.无穷远点 O∞是零元,有O∞+ O∞= O∞,O∞+P=P
-
2.P(x,y)的负元是 (x,-y mod p)= (x,p-y) ,有P+(-P)= O∞
-
3.P(x1,y1),Q(x2,y2)的和R(x3,y3) 有如下关系:
x3≡k2-x1-x2(mod p)
y3≡k(x1-x3)-y1(mod p)
若P=Q 则 k=(3x2+a)/2y1mod p
若P≠Q,则k=(y2-y1)/(x2-x1) mod p
例题椭圆曲线已知E23(1,1)上两点P(3,10),Q(9,7),求(1)-P,(2)P+Q,(3) 2P
(1)−P=(3,−10mod23)=(3,13)(2)k=7−109−3=−2−1mod232⋅2−1=1mod23⇒2−1=12k=−12mod23=11P+Q=(112−3−9mod23,11×(3−(−6))mod23)=(17,20)(3)k=3×32+12×10mod23=7⋅5−1mod235⋅5−1=1mod23⇒5−1=14k=7⋅14mod23=62P=(62−3−3mod23,6×(3−7)−10mod23)=(7,12)
补充:
-2^(-1) mod 23 进行两部分计算
(1) 先算 2^(-1) 对应的数A, 在这里2^(-1)不是2的-1次方,而是2的逆元
(2) 再算-A mod 23
(1) 计算第一步
根据有限域除法规则 2 * 2^(-1) = 1 mod 23
即 2A = 1 mod 23 ==> 2A = 23 + 1 == > A = 12
(2) 计算第二步
-A mod 23 ==> -12 mod 23 即 23 -12 = 11
所以有
-2^(-1) mod 23 = 11
有限域椭圆曲线点的阶
如果椭圆曲线上一点P,存在最小的正整数n使得数乘nP=O∞ ,则将n称为P的阶
若n不存在,则P是无限阶的
计算可得27P=-P=(3,13)
所以28P=O ∞ P的阶为28
这些点做成了一个循环阿贝尔群,其中生成元为P,阶数为29。显然点的分布与顺序都是杂乱无章