椭圆曲线、双线性对与群签名.pptx

《椭圆曲线、双线性对与群签名.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第9章密码学新技术主讲人：叶世贝、倪凯敏、高闯2021/7/3119.1椭圆曲线★椭圆曲线并非椭圆，之所以称为椭圆曲线是因为它的曲线方程与计算椭圆周长的方程类似。在数学上，椭圆曲线的曲线方程是以下形式的三次方程：y2=x3+ax+b因为＝(a/3)3+(b/2)2=(4a3+27b2)/108是方程x3+ax+b＝0的判别式，当4a3+27b2＝0时方程有重根，设为x0，则点Q0＝(x0,0)是椭圆曲线的重根即x3+ax+b＝(x-x0)3，重根使一阶导数3x2＋a在该Q0点为0令F(x,y)=y2－x3－ax－b，则F/x

2、Q0=F/y

3、Q0

4、=0所以dy/dx=－(F/x)/(F/y)＝(3x2＋a)/2y在Q0点无定义，即曲线y2≡x3+ax+b在Q0点的切线无定义，因此点Q0的倍点运算无定义所以要求判别式=4a3+27b202021/7/3129.1椭圆曲线★实数域上的椭圆曲线对于固定的a和b，满足形如方程y2=x3+ax+b的所有点（x，y）集合，外加一个无穷远点O，其中，a、b是实数,x和y在实数域上取值。★有限域GF(p)上的椭圆曲线对于固定的a和b，满足形如方程y2≡x3+ax+b(modp)(a,b,x,yGF(p),4a3+27b2(modp)≠0)的所有点（x

5、，y）集合，外加一个零点或无穷远点O，其中，a、b、x和y均在有限域GF(p)上取值，即在{0,1,2,…p-1}上取值。P是素数。2021/7/3139.1椭圆曲线2021/7/314★一般来说，Ep(a,b)由以下方式产生：①对每一个x(0x

6、集合，外加一个零点或无穷远点O，其中，a、b、x，yGF(2^m)GF(2^m)上的点是m位比特串。9.1.1椭圆曲线的加法运算法则2021/7/315★Ep(a,b)上的加法定义如下：设P，QEp(a,b)，则①P+O=P；②若P=(x,y)，那么(x,y)+(x,-y)=O，即(x,-y)是P的加法逆元，记为-P。显然任一点P和其逆元-P都是Ep(a,b)中的点，如P=(1,11)和-P=(1,-11)=(1,12)E23(1,4)③设P=(x1,y1)，Q=(x2,y2)，P≠-Q，则P+Q=(x3,y3)由以下确定：x3≡λ2－x1－x2(

7、modp)y3≡λ(x1－x3)－y1(modp)其中λ＝切线，倍乘9.1.1椭圆曲线的加法运算法则2021/7/316★两相异点相加：P,Q为椭圆曲线上相异两点，有P+Q=R，点R是经过P、Q两点的直线与曲线相交点的唯一负点（逆元）。★倍乘运算：P的倍点2P是经过点P的切线与椭圆曲线相交点的负点（逆元）。若存在最小正整数n使nP=0成立，则点P的阶(周期)为n。★倍乘运算仍定义为重复加法，如4P=P+P+P+P★Ep(a,b)是一个Abel群对一般的Ep(a,b)，其上的加法运算是封闭的，满足交换律、结合律，其上的加法逆元运算也是封闭的，有单位元O，所

8、以Ep(a,b)是一个Abel群。9.1.2椭圆曲线的应用2021/7/317★椭圆曲线群中的离散对数问题是指已知群中的P和Q，求解方程：kP=Q中k值的问题。由k和P易求Q，但由P、Q求k则是困难的，这就是椭圆曲线上的离散对数问题，可应用于公钥密码体制。★例：对基于GF(23)的椭圆群y2＝x3+9x+17(mod23)，求Q=(4，5)对于P=(16，5)的离散对数。P＝(16，5)，2P=(20，20)，3P＝(14，14),4P=(19，20)，5P＝(13，10)，6P＝(7，3)，7P＝(8，7)，8P＝(12，17)，9P＝(4，5)因此k

9、关于Q的离散对数是9，点P称为基点。明文到椭圆曲线上的嵌入2021/7/318★使用椭圆曲线构造密码体制前，需将明文嵌入到椭圆曲线上，作为椭圆曲线上的点。设明文消息为m，令k为一个大整数，满足(m+1)k

10、椭圆曲线上的密码★利用椭圆曲线实现ElGamal密码体制首先选取一条椭圆曲线，