第10章椭圆曲线密码学Word文件下载.docx
《第10章椭圆曲线密码学Word文件下载.docx》由会员分享,可在线阅读,更多相关《第10章椭圆曲线密码学Word文件下载.docx(8页珍藏版)》请在冰点文库上搜索。
1.椭圆曲线
椭圆曲线并非椭圆,之所以称为椭圆曲线是因为它的曲线方程与计算椭圆周长的方程类似,一般来计,椭圆曲线的曲线方程是以下形式的三次方程:
y2+axy+by=x3+cx2+dx+e
(1)
其中a,b,c,d,e是满足某些简单条件的实数。
其中包括称为无穷远点的元素。
密码中普遍采用的是有限域上的椭圆曲线,有限域上的椭圆曲线是指曲线方程定义式
(1)中,所有系数都是某一有限域GF(p)中的元素(其中p为一大素数)。
其中最为常用的是由方程
y2≡x3+ax+b(modp)
定义的曲线。
(a,b∈GF(p),4a2+27b3≠0modp)
椭圆曲线上的加法运算定义如下:
(1)设L是通过P和Q的直线。
L交E于P和Q,容易看出,L还交E于第三点,记作R’。
对x轴反射R’,得到一点R,定义P+Q=R。
见图1和图2.
图2中的P点和Q点重合。
(2)o为加法单位元(无穷远点),即对椭圆曲线上任一点P,有P+o=o+P=P.
(3)P=(x,y)是椭圆曲线上的一点,它的加法逆元定义为
-P=(x,-y)
P+(-P)=o
下面给出一个计算R的代数公式。
椭圆曲线E上的两点P=(x1,y1)和Q=(x2,y2)可以按照下面的规则相加:
(1)如果x2=x1,y2=-y1,则P+Q=o;
否则P+Q=(x3,y3),其中
x3≡λ2-x1-x2(modp)
y3≡λ(x1-x3)-y1(modp)
其中λ是直线L的斜率,
λ≡(y2-y1)(x2-x1)-1modp当P≠Q时
λ≡(3x12+a)(2y1)-1modp当P=Q时
举例:
设E是Z11上的椭圆曲线y2≡x3+x+6。
请确定E上的点。
解:
从y2≡x3+x+6看出,a=1,b=6,则
4a3+27b2≡8≠0mod11所以该椭圆曲线可用于密码体制。
(1)当x=0时
y2≡6mod11
(2)
现在求解方程
(2),首先根据legendre符号来判断方程
(2)有没有解:
而
可见
方程
(2)无解。
(2)当x=1时,方程变为
y2≡8mod11(3)
现判断方程(3)有没有解。
所以方程(3)也无解。
(3)当x=2时,方程变为
y2≡5mod11(4)
方程(4)有解,其解为
y≡±
5(11+1)/4≡±
53≡±
4(mod11)
即有两个点(2,4),(2,-4)
(4)当x=3时,y2≡3mod11(5)
因为
所以方程(5)有解,其解为:
3(11+1)/4≡±
33≡±
5(mod11)
即有两个点(3,5),(3,-5)
同理可以算出:
当x=4,5,6,7,8,9,10时各方程解。
结果如下表所示:
x
X3+x+6mod11
是否为二次剩余
y
6
否
1
8
2
5
是
4,7
3
5,6
4
2,9
7
9
3,8
10
可见E有13点(包括无穷远点o).
假设取p=(2,7),计算2P:
2P=P+P
λ≡(3x12+a)(2y1)-1modp≡(3╳22+1)(2╳7)-1mod11
≡2╳3-1mod11≡8mod11
x3≡λ2-x1-x2(modp)≡82-2-2≡5mod11
y3≡λ(x1-x3)-y1(modp)≡8(2-5)-7≡2mod11
所以2P=(5,2)
下面计算3P
3P=2P+P=(5,2)+(2,7)
λ≡(y2-y1)(x2-x1)-1modp≡(7-2)(2-5)-1modp
≡5╳(-3)-1modp≡5╳8-1≡2mod11
x3≡λ2-x1-x2(modp)≡22-5-2≡8mod11
y3≡λ(x1-x3)-y1(modp)≡2(5-8)-2≡3mod11
可见3P=(8,3)
如此继续下去,其余的乘积计算结果如下:
P=(2,7)2P=(5,2)3P=(8,3)
4P=(10,2)5P=(3,6)6P=(7,9)
7P=(7,2)8P=(3,5)9P=(10,9)
10P=(8,8)11P=(5,9)12P=(2,4)
2.椭圆曲线上的密码体制
(1)ElGamal密码体制
设p是一个素数,g是Zp*的一个生成元(也叫原根)。
明文空间P=Zp*,密文空间C=Zp*╳Zp*,选定0<
a<
p,计算
b≡gamodp。
私钥:
a公钥:
b
加密算法:
设明文为m,0≤m<
p,随机地选择一个正整数k,0≤k<
p,计算:
y1≡gkmodp,y2≡mbkmodp
密文c=(y1,y2)
解密算法:
m≡y2y1-amodp
(2)基于椭圆曲线的ElGamal密码体制
首先选取一条满足4a3+27b2≠0modp的椭圆曲线Ep(a,b),将明文消息通过编码嵌入到曲线上得点Pm,再对点Pm做加密变换。
取Ep(a,b)上的一个点,Ep(a,b)和G作为公开参数
用户选nA作为秘密钥,并以PA=nAG作为公开密钥。
任一用:
1)加密:
用户B若想向A发送消息Pm,可选取一随机正整数k,产生以下密文对:
Cm={kG,Pm+kPA}={C1,C2}
2)解密:
C2-nAC1=Pm+kPA-nAkG=Pm+knAG-nAkG=Pm
利用上例的椭圆曲线y2≡x3+x+6。
取G=(2,7),私钥nA=7,则公钥为PA=nAG=7(2,7)=(7,2)
若明文Pm=(10,9),取随机数k=3,
加密:
C1=kG=3(2,7)=(8,3)
C2=Pm+kPA=(10,9)+3(7,2)=(10,2)
解密:
Pm=C2-nAC1=(10,2)-7(8,3)=(10,2)-(3,5)
=(10,2)+(3,6)=(10,9)
3.椭圆曲线密码算法的优点
ECC与RSA比较,有很多技术优点:
(1)安全性能更高
安全性能占绝对优势,ECC在计算复杂度上目前是完全指数级的,而RSA是亚指数级。
(2)计算量小和处理速度快。
(3)存储空间小。
160bit的ECC与1024bit的RSA具有相同的安全强度
210bit的ECC与2048bit的RSA具有相同的安全强度。
意味着它所占的存储空间要小得多。
这对于加密算法在资源受限环境上(如智能卡等)的应用具有特别重要的意义。
(4)带宽要求低。
习题:
求出椭圆曲线E:
y2≡x3-2mod7上的点,并:
(1)在E上找到(3,2)+(6,5)的和。
(2)在E上找到(3,2)+(3,2)的和。