最新椭圆曲线、双线性对与群签名幻灯片.ppt

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

1、椭圆曲线、双线性对与群签名9.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/

3、y

4、Q0=0所以dy/dx=－(F/x)/(F/y)＝(3x2＋a)/2y在Q0点无定义，即曲线y2≡x3+ax+b在Q0点的切线无定义，因此点Q0的倍点运算无定义所以要求判别式=4a3+27b202021/9/2029.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

5、GF(p),4a3+27b2(modp)≠0)的所有点（x，y）集合，外加一个零点或无穷远点O，其中，a、b、x和y均在有限域GF(p)上取值，即在{0,1,2,…p-1}上取值。P是素数。2021/9/2039.1.2椭圆曲线的应用★椭圆曲线群中的离散对数问题是指已知群中的P和Q，求解方程：kP=Q中k值的问题。由k和P易求Q，但由P、Q求k则是困难的，这就是椭圆曲线上的离散对数问题，可应用于公钥密码体制。★例：对基于GF(23)的椭圆群y2＝x3+9x+17(mod23)，求Q=(4，5)对于P=(

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

7、)是平方剩余，即得到椭圆曲线上的点(x,)。因为在0到p的整数中，有一半是模p的平方剩余，一半是模p的非平方剩余。所以k次找到x，使得x3+ax+b(modp)是平方根的概率不小于1－1/2k。反之，从椭圆曲线上点(x,y)得到明文消息m，只须求m＝x/k2021/9/208椭圆曲线上的密码★利用椭圆曲线实现ElGamal密码体制首先选取一条椭圆曲线，并得Ep(a,b)，将明文消息m通过编码嵌入到曲线上点Pm，再对点Pm做加密变换。取Ep(a,b)的一个生成元G，G的阶为素数n，Ep(a,b)、G和n

8、作为公开参数。用户A在[1,n-1]上选随机整数kA作为私钥，并以PA=kAG作为公钥任一用户B若想向A发送消息Pm，可在[1,n-1]选取一随机正整数k，产生以下点对作为密文：Cm={kG，Pm+kPA}A解密时，以密文点对中的第二个点减去用自己的秘密钥与第一个点倍乘，即(Pm+kPA)－kAkG=Pm+k(kAG)－kAkG=Pm攻击者若想由Cm得到Pm，就必须知道k。而要得到k，只有通过椭圆曲线上的两个已知点G和kG，这意味着必须求椭圆曲线上的离散对数，因此不可行。2021/9/209椭圆曲线上的密

9、码★利用椭圆曲线实现Diffie-Hellman密钥交换第1步：选取一个基域GF(p)和两个参数a、b，则得椭圆曲线上的点及无穷远点构成Abel群Ep(a,b)。第2步:取Ep(a,b)的一个生成元G＝(x1,y1)，G的阶是素数n。Ep(a,b),G,n作为公开参数。第3步:用户A和B之间的密钥交换如下进行：①A随机选整数kA

10、PB=kA(kBG)=kB(kAG)=kBPA攻击者若想获取K，则必须由PA和G求出kA，或由PB和G求出kB，即需要求椭圆曲线上的离散对数，因此是不可行的。如果将这一密钥用作传统密码中的会话密钥，可简单地取点坐标中的一个，如取x坐标，或取x坐标的某一简单函数。2021/9/2010椭圆曲线密码体制的优点★与基于有限域上离散对数问题的公钥体制相比，椭圆曲线密码体制有如下优点:(1)安全性高攻击有限域上的离散对数问题可以用指数积