橢圓曲線公鑰密碼體制E

《橢圓曲線公鑰密碼體制E》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、橢圓曲線公鑰密碼體制(ECC)主講人：趙永哲e_mail:yongzhe@jlu.edu.cn電話：13180888761關(guān)于橢圓曲線橢圓曲線問題的研究有150多年的歷史1985年Washington大學(xué)的NealKoblitzIBM的VictorMiller把橢圓曲線應(yīng)用于密碼領(lǐng)域目前，橢圓曲線和RSA算法是使用最廣泛的公鑰加密算法實(shí)數(shù)域上的橢圓曲線橢圓曲線并非橢圓，之所以稱為橢圓曲線是因?yàn)樗那€方程與計(jì)算橢圓周長的方程類似。一般來講，橢圓曲線的曲線方程是以下形式的三次方程：y2+axy+by=x3+cx2+dx+e其中a，b，c

2、，d，e是滿足某些簡單條件的實(shí)數(shù)。典型橢圓曲線E:Y2=X3–5X+8-4-特點(diǎn):可以應(yīng)用幾何學(xué)使橢圓曲線上的點(diǎn)形成一個(gè)群.橢圓曲線的加法依據(jù)：如果在橢圓曲線上有三個(gè)點(diǎn)存在于一條直線上，則它們的和為無窮遠(yuǎn)點(diǎn)。其中無窮遠(yuǎn)點(diǎn)記為○點(diǎn)P和點(diǎn)-P相加垂直直線沒有第三個(gè)交點(diǎn)Q在無限遠(yuǎn)處增加點(diǎn)O點(diǎn)O位于位于每個(gè)垂線上OPQ=–P點(diǎn)P和點(diǎn)-P相加的和為無窮遠(yuǎn)點(diǎn)點(diǎn)P和點(diǎn)Q相加PQP+QR設(shè)連接點(diǎn)P和Q的直線，交橢圓曲線于點(diǎn)R,則點(diǎn)P和Q的和為點(diǎn)-R求點(diǎn)P的二倍P2*PR過P點(diǎn)作切線通過點(diǎn)P作曲線的切線，交曲線于另一點(diǎn)R,則2P=-R求點(diǎn)P的二倍的特例

3、P若點(diǎn)P的切線的斜率是0，則2P=O,3P=P,4P=O,5P=P……有限域上的橢圓曲線定義：對(duì)于曲線y2=x3+ax+b(modp)，a,b為小于p的整數(shù)當(dāng)4a3+27b2(modp)不為零時(shí)構(gòu)成有限域Fp上的橢圓曲線群。記為Ep(a,b)有限域上的橢圓曲線的點(diǎn)的構(gòu)造1.對(duì)于每一個(gè)x(0<=x

4、0)的點(diǎn)的構(gòu)造滿足條件的23個(gè)點(diǎn)是:(0,0)(1,5)(1,18)(9,5)(9,18)(11,10)(11,13)(13,5)(13,18)(15,3)(15,20)(16,8)(16,15)(17,10)(17,13)(18,10)(18,13)(19,1)(19,22)(20,4)(20,19)(21,6)(21,17)有限域上的兩個(gè)點(diǎn)的加法若P=(xP,yP)，Q=(xQ,yQ).若P和Q是不同的點(diǎn)且Q不是-P,P+Q=R按如下方法計(jì)算：λ=(yP-yQ)/(xP-xQ)modpxR=λ2-xP-xQmodpyR=-yP+λ

5、(xP-xR)modp例題仍以E23(1,1)為例，設(shè)P=(3,10)，Q=(9,7)，求P+Q所以P+Q=（17,20），仍為E23(1,1)中的點(diǎn)。求點(diǎn)P的2倍若P=(xP,yP)若yP不為02P=R按如下方法計(jì)算：λ=(3xP2+a)/(2yP)modpxR=λ2-2xPmodpyR=-yP+λ(xP-xR)modp例題仍以E23(1,1)為例，設(shè)P=(3,10)，求2P所以2P=(7,12)。練習(xí)1.Doestheellipticcurveequationy2=x3+10x+5defineagroupoverF17?2.Do

6、thepointsP(2,0)andQ(6,3)lieontheellipticcurvey2=x3+x+7overF17?3.WhatarethenegativesofthefollowingellipticcurvepointsoverF17?P(5,8)Q(3,0)R(0,6)4.Intheellipticcurvegroupdefinedbyy2=x3+x+7overF17,whatisP+QifP=(2,0)andQ=(1,3)?5.Intheellipticcurvegroupdefinedbyy2=x3+x+7o

7、verF17,whatis2PifP=(1,3)?上的橢圓曲線定義：對(duì)于曲線y2+xy=x3+ax2+bb不為0，a,b屬于的解的集合構(gòu)成上的橢圓曲線群。記為上的橢圓曲線舉例作為一個(gè)簡單的例子,考略,其上的不可約多項(xiàng)式為f(x)=x4+x+1.元素g=(0010)是生成元.g的冪為:g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12=(1111)g13=(110

8、1)g14=(1001)g15=(0001)上的橢圓曲線舉例對(duì)于橢圓曲線y2+xy=x3+g4x2+1.其中a=g4，b=g0=1.點(diǎn)(g5,g3)滿足橢圓曲線方程:y2+xy=x3+g4x2+1(g3)2+g5g3=(