椭圆曲线公钥密码体制(ecc)

《椭圆曲线公钥密码体制(ecc)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、椭圆曲线公钥密码体制(ECC)主讲人：赵永哲e_mail:yongzhe@jlu.edu.cn电话：13180888761关于椭圆曲线椭圆曲线问题的研究有150多年的历史1985年Washington大学的NealKoblitzIBM的VictorMiller把椭圆曲线应用于密码领域目前，椭圆曲线和RSA算法是使用最广泛的公钥加密算法实数域上的椭圆曲线椭圆曲线并非椭圆，之所以称为椭圆曲线是因为它的曲线方程与计算椭圆周长的方程类似。一般来讲，椭圆曲线的曲线方程是以下形式的三次方程：y2+axy+by=x3+cx2+dx+e其中a

2、，b，c，d，e是满足某些简单条件的实数。典型椭圆曲线E:Y2=X3–5X+8-4-特点:可以应用几何学使椭圆曲线上的点形成一个群.椭圆曲线的加法依据：如果在椭圆曲线上有三个点存在于一条直线上，则它们的和为无穷远点。其中无穷远点记为○点P和点-P相加垂直直线没有第三个交点Q在无限远处增加点O点O位于位于每个垂线上OPQ=–P点P和点-P相加的和为无穷远点点P和点Q相加PQP+QR设连接点P和Q的直线，交椭圆曲线于点R,则点P和Q的和为点-R求点P的二倍P2*PR过P点作切线通过点P作曲线的切线，交曲线于另一点R,则2P=-R求

3、点P的二倍的特例P若点P的切线的斜率是0，则2P=O,3P=P,4P=O,5P=P……有限域上的椭圆曲线定义：对于曲线y2=x3+ax+b(modp)，a,b为小于p的整数当4a3+27b2(modp)不为零时构成有限域Fp上的椭圆曲线群。记为Ep(a,b)有限域上的椭圆曲线的点的构造1.对于每一个x(0<=x

4、构造椭圆曲线E23(1,0)的点的构造满足条件的23个点是:(0,0)(1,5)(1,18)(9,5)(9,18)(11,10)(11,13)(13,5)(13,18)(15,3)(15,20)(16,8)(16,15)(17,10)(17,13)(18,10)(18,13)(19,1)(19,22)(20,4)(20,19)(21,6)(21,17)有限域上的两个点的加法若P=(xP,yP)，Q=(xQ,yQ).若P和Q是不同的点且Q不是-P,P+Q=R按如下方法计算：λ=(yP-yQ)/(xP-xQ)modpxR=λ2-x

5、P-xQmodpyR=-yP+λ(xP-xR)modp例题仍以E23(1,1)为例，设P=(3,10)，Q=(9,7)，求P+Q所以P+Q=（17,20），仍为E23(1,1)中的点。求点P的2倍若P=(xP,yP)若yP不为02P=R按如下方法计算：λ=(3xP2+a)/(2yP)modpxR=λ2-2xPmodpyR=-yP+λ(xP-xR)modp例题仍以E23(1,1)为例，设P=(3,10)，求2P所以2P=(7,12)。练习1.Doestheellipticcurveequationy2=x3+10x+5defin

6、eagroupoverF17?2.DothepointsP(2,0)andQ(6,3)lieontheellipticcurvey2=x3+x+7overF17?3.WhatarethenegativesofthefollowingellipticcurvepointsoverF17?P(5,8)Q(3,0)R(0,6)4.Intheellipticcurvegroupdefinedbyy2=x3+x+7overF17,whatisP+QifP=(2,0)andQ=(1,3)?5.Intheellipticcurve

7、groupdefinedbyy2=x3+x+7overF17,whatis2PifP=(1,3)?上的椭圆曲线定义：对于曲线y2+xy=x3+ax2+bb不为0，a,b属于的解的集合构成上的椭圆曲线群。记为上的椭圆曲线举例作为一个简单的例子,考略,其上的不可约多项式为f(x)=x4+x+1.元素g=(0010)是生成元.g的幂为:g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)

8、g11=(1110)g12=(1111)g13=(1101)g14=(1001)g15=(0001)上的椭圆曲线举例对于椭圆曲线y2+xy=x3+g4x2+1.其中a=g4，b=g0=1.点(g5,g3)满足椭圆曲线方程:y2+xy=x3+g4x2+1(g3)2+g5g3=(