现代密码学_第10讲ECC

《现代密码学_第10讲ECC》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、椭圆曲线(ECC)密码体制EllipticCurveCryptography2021/7/291椭圆曲线椭圆曲线的曲线方程是以下形式的三次方程y2+axy+by=x3+cx2+dx+ea,b,c,d,e是满足某些简单条件的实数。定义中包含一个称为无穷远点的元素，记为O.2021/7/292有限域上的椭圆曲线曲线方程中的所有系数都是某一有限域GF(p)中的元素(p为一大素数)，最为常用的曲线方程为y2=x3+ax+bmod(p)(a,b∈GF(p),4a3+27b2≠0modp)例：p=23,a=b=1,4a3+27b2=8≠0(mod23),方程y2=x3+x+1mod(p)记为Ep(a,

2、b):表示ECC上点集{(x,y)

3、0≤x

4、x,-y)P+(-P)=O当4a3+27b2≠0modpEp(a,b)构成加法交换群否则导致加法运算无意义2021/7/295Ep(a,b)上加法O为加法单位元P+O=PP(x,y)加法逆元-P(x,-y+p)P＝(x1,y1),Q=(x2,y2),P≠-Q,P+Q=(x3,y3)x3=l2-x1-x2（modp）y3=l(x1-x3)-y1(modp)例：E23(1,1)P=(3,10),Q(=9,7)2021/7/296ECC上的密码应用Diffie-Hellman密钥交换Elgamal密码体制安全基础ECC上的离散对数问题是困难问题在ECC构成的交换群Ep(a,b)上考虑方程Q＝kP

5、，P,Q∈Ep(a,b),k

6、G

7、大素数)Ep(a,b)和G公开PA=nAGPB=nBGnAPBnBPA共享的秘钥K2021/7/298Elgamal密码体制密钥产生选择一个素数p，g(g

8、

9、C2。

10、解密M=C2/C1x=Myk/gkx=Mgxk/gkxmodpECC实现Elgamal密码体制密钥产生选取椭圆曲线Ep(a,b),生成元G,nA。私钥:nA公钥:Ep(a,b),G,PA(PA=nAG)加密选随机正整数k，将明文消息通过编码嵌入曲线上得到点pm???C1=kGC2=Pm+kPA密文Cm=(C1,C2)解密Pm=C2-nAC1p，g,x,y指数关系Ep(a,b),G,nA,PA倍乘关系2021/7/299明文嵌入(整数m→点Pm)选取K(大整数k，且满足(m+1)k

11、bmod(p)有平方根y,则Pm=（x,y）;否则j=j+1,返回2如果j=k;则嵌入失败。失败概率1/2k解密点Pm（x,y）→整数m=[x/k]y2=x3+2x+7mod(179)m=5选K=10(满足(5+1)10<179)令x=5*10+j(j=0,1..9)当x=51,x3+2x+7mod(179)=121则Pm=（51,11）解密m=[51/10]=52021/7/2910例子椭圆曲线设用户A的私钥为7，则公钥为：1)设用户B的消息m编码后为　　　，且选取了随机数2)用户B计算：　　　　　，3）B向A发送消息：4)用户A计算：5)用户A计算：2021/7/2911ECC算法实现

12、pointadd(pointp1,pointp2,longa,longb,longn){//一些定义……if(x1==x2&&y1==-y2){p3.x=inf;p3.y=inf;returnp3;}if(p1.x==inf&&p1.y==inf)returnp2;if(p2.x==inf&&p2.y==inf)returnp1;if(x2!=x1)m=((y2-y1)*invmod(x2-x1,n))%n;elsem=