資源描述:
《現(xiàn)代密碼學(xué)_第10講ECC》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、橢圓曲線(ECC)密碼體制EllipticCurveCryptography2021/7/291橢圓曲線橢圓曲線的曲線方程是以下形式的三次方程y2+axy+by=x3+cx2+dx+ea,b,c,d,e是滿足某些簡單條件的實數(shù)。定義中包含一個稱為無窮遠點的元素,記為O.2021/7/292有限域上的橢圓曲線曲線方程中的所有系數(shù)都是某一有限域GF(p)中的元素(p為一大素數(shù)),最為常用的曲線方程為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當(dāng)4a3+27b2≠0modpEp(a,b)構(gòu)成加法交換群否則導(dǎo)致加法運算無意義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上的密碼應(yīng)用Diffie-Hellman密鑰交換Elgamal密碼體制安全基礎(chǔ)ECC上的離散對數(shù)問題是困難問題在ECC構(gòu)成的交換群Ep(a,b)上考慮方程Q=kP
5、,P,Q∈Ep(a,b),k
6、G
7、大素數(shù))Ep(a,b)和G公開PA=nAGPB=nBGnAPBnBPA共享的秘鑰K2021/7/298Elgamal密碼體制密鑰產(chǎn)生選擇一個素數(shù)p,g(g
8、
9、C2。
10、解密M=C2/C1x=Myk/gkx=Mgxk/gkxmodpECC實現(xiàn)Elgamal密碼體制密鑰產(chǎn)生選取橢圓曲線Ep(a,b),生成元G,nA。私鑰:nA公鑰:Ep(a,b),G,PA(PA=nAG)加密選隨機正整數(shù)k,將明文消息通過編碼嵌入曲線上得到點pm???C1=kGC2=Pm+kPA密文Cm=(C1,C2)解密Pm=C2-nAC1p,g,x,y指數(shù)關(guān)系Ep(a,b),G,nA,PA倍乘關(guān)系2021/7/299明文嵌入(整數(shù)m→點Pm)選取K(大整數(shù)k,且滿足(m+1)k
11、bmod(p)有平方根y,則Pm=(x,y);否則j=j+1,返回2如果j=k;則嵌入失敗。失敗概率1/2k解密點Pm(x,y)→整數(shù)m=[x/k]y2=x3+2x+7mod(179)m=5選K=10(滿足(5+1)10<179)令x=5*10+j(j=0,1..9)當(dāng)x=51,x3+2x+7mod(179)=121則Pm=(51,11)解密m=[51/10]=52021/7/2910例子橢圓曲線設(shè)用戶A的私鑰為7,則公鑰為:1)設(shè)用戶B的消息m編碼后為 ,且選取了隨機數(shù)2)用戶B計算: ,3)B向A發(fā)送消息:4)用戶A計算:5)用戶A計算:2021/7/2911ECC算法實現(xiàn)
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=