椭圆曲线实例

1、 基于椭圆曲线上的离散对数问题ECC2.实例： 椭圆曲线E23(1,0) 的点的构造即y2 = x3 + x在有限域F23上的点的构造(其中a=1,b=0)满足条件的23个点是: (0,0)(1,18) (9,18) (11,13) (13,18) (15,20) (16,15) (17,13) (18,13) (19,22) (20,19) (21,17) (0,0) (1,5) (9,5) (11,10) (13,5) (15,3)(16,8) (17,10)(18,10) (19,1) (20,4) (21,6) 椭圆曲E23线上共有24个点(包括无穷远点O)。除了(0,0)外，每一个x

2、都对应两个点，它们是互逆的，如p=(1,5)和-p=(1,-5)=(1.-5 mod 23)=(1,18),实际上(0,0)的逆是它本身。 基于椭圆曲线上的离散对数问题ECC2.实例:(多项式基于有限域GF(2m)上的椭圆曲线) : 考虑多项式 f(x) = x4 + x + 1定义的域GF(24). 元素g = (0010)是生成元.用多项式表示为 g=x , g的幂分别为: g0 = (0001) g1 = (0010) g2 = (0100) g3 = (1000) g4 = (0011) g5 = (0110) g6 = (1100) g7 = (1011) g8 = (0101) g

3、9 = (1010) g10 = (0111) g11 = (1110) g12 = (1111) g13 = (1101) g14 = (1001) g15 = (0001) g2 = x2 = (0100) ， g4 = x4 = x4 mod(x4 + x + 1) = x + 1=(0011) ，其余可类似求得。考虑椭圆曲线： y2 + xy = x3 + g4x2 + 1. 其中 a = g4 ,b = g0 =1. 点 (g5, g3) 满足椭圆曲线方程 : y2 + x y = x3 + g4x2 + 1 (g3)2 + g5g3 = (g5)3 + g4g10 + 1 g6 +

4、 g8 = g15 + g14 + 1 (1100) + (0101) = (0001) + (1001) + (0001) (1001) = (1001) 基于椭圆曲线上的离散对数问题ECC2.满足方程y2 + xy = x3 + g4x2 + 1. 其中 a = g4 ,b = g0 =1.的15个点是： (0, 1) (1, g6) (g3, g8) (g5, g3) (0, 1) (1, g13) (g3, g13) (g5, g11) (g6, g8) (g9, g10) (g10, g) (g12, 0) (g6, g14) (g9, g13) (g10, g8) (g12, g1

5、2) 上表表明了互逆点，除(0,1)的互逆点使其本身外，如p= (1, g6) ,它的互逆点:-p= (1,1+g6)=(1,(0001)+(1101)=(1,(1101) = (1, g13) 基于椭圆曲线上的离散对数问题ECC2.逆元：P = (x P, y P)的逆元： -P = (x P, - y P)加法：若 P = (x P , y P)，Q = (x Q , y Q). 若 P 和 Q 是不同的点且 Q 不是 -P, P + Q = R 按如下方法计算： = (y P y Q) / (x P x Q) mod p x R = 2 x P x Q mod p y R = -y P

6、+ (x P x R) mod p求2P ：若 P = (x P , y P) 若 y P 不为 0， 2P = R 按如下方法计算： = (3xP2 + a) / (2yP ) mod p x R = 2 - 2xP mod p y R = -y P + (x P x R) mod p GF(p) GF(p)上的两点运算上的两点运算( (用用代数方法代数方法表示表示) )： 基于椭圆曲线上的离散对数问题ECC2.例题：仍以E23(1,1)为例，设P=(3,10)，Q=(9,7)，求P+Q，2P2337103111mod239362113910917mod2311(317)1016420mod

7、23xy 所以P+Q=（17,20），仍为E23(1,1)中的点。1.22333 31516 mod 23210204633307 mod 236(37)103412 mod 23xy 2.所以2P=(7,12)。 基于椭圆曲线上的离散对数问题ECC2. GF(2m)GF(2m)上两点运算上两点运算( (用用代数方法代数方法表示表示): ): 逆元：P = (x P, y P)的逆元 ：-P = (x P, x P + y P)加法：若 P = (x P , y P)，Q = (x Q , y Q)。若 P 和 Q 是不同的点且 Q 不是 -P, P + Q = R 按如下方法计算： = (y

8、P +yQ) / (xP + xQ) xR = 2 + + xP + xQ + a yR = (xP + xR) + xR + yP 求2P ：若 P = (x P , y P) 若 y P 不为 0， 2P = R 按如下方法计算： = (xP 2 + yP )/ xP xR = 2+ + a yR = xP2 + ( + 1) xR 基于椭圆曲线上的离散对数问题ECC2.例题： 椭圆曲线T=(m=4,f(x)=x4+x+1,g=0010,a=g4,b=g0)点P=(g6,g8)，点Q=(g3,g13)，求点R=P+Q以及R=2P1. =(g8+ g13 )/(g6+ g3)=g X=g2+

9、g+g6+ g3 +g4=1 Y=g(g6+1)+1+ g8 =g13 所以 R=P+Q=(1,g13)2. =(g6 )2 +g8/g6=g3 X=(g3 )2 +g3+g4=g10 Y=g12+(g3+1)g10=g8所以 R=2P=(g10 ,g8) 基于椭圆曲线上的离散对数问题基于椭圆曲线上的离散对数问题ECCECC2. 给定椭圆曲线上的点 P 和点 Q , 寻找数 k 使得 k P = Q， 其中k称为Q基于P的离散对数。（当给定P和Q时计算K相对困难）椭圆曲线密码体制的依据就是利用定义在椭圆曲线点群上的离散对数问题的难解性。例如: 对于椭圆曲线F23：y2 = x3 + 9x + 17, 求点Q = (4,5) 基于点 P = (16,5)的离散对数k解： 计算k P, 直到Q为止 P =