信息安全專題講座07課件

Q=∠BAP→/2AP→L2可設(shè)想L1上有一點(diǎn)P∞，它為L2和L1的交點(diǎn)，稱之為無窮遠(yuǎn)點(diǎn)。直線L1上的無窮遠(yuǎn)點(diǎn)只能有一個(gè)。（因?yàn)檫^A點(diǎn)只能有一條平行于L1的直線L2，而兩直線的交點(diǎn)只能有一個(gè)。）結(jié)論：1*.平面上一組相互平行的直線，有公共的無窮遠(yuǎn)點(diǎn)。（為與無窮遠(yuǎn)點(diǎn)相區(qū)別，把原來平面上的點(diǎn)叫做平常點(diǎn)）2*.平面上任何相交的兩直線L1,L2有不同的無窮遠(yuǎn)點(diǎn)。原因：若否，則L1和L2有公共的無窮遠(yuǎn)點(diǎn)P∞，則過兩相異點(diǎn)A和P∞有相異兩直線，與公理相矛盾。Q=∠BAP→/2AP→13*.全體無窮遠(yuǎn)點(diǎn)構(gòu)成一條無窮遠(yuǎn)直線。注：歐式平面添加上無窮遠(yuǎn)點(diǎn)和無窮遠(yuǎn)直線，自然構(gòu)成射影平面。(2)齊次坐標(biāo)解析幾何中引入坐標(biāo)系，用代數(shù)的方法研究歐氏空間。這樣的坐標(biāo)法也可推廣至攝影平面上，建立平面攝影坐標(biāo)系。

平面上兩相異直線L1,L2，其方程分別為：

L1:a1x+b1y+c1=0 L2:a2x+b2y+c2=0AL1L2P∞3*.全體無窮遠(yuǎn)點(diǎn)構(gòu)成一條無窮遠(yuǎn)直線。AL1L2P∞2其中a1,b1不同時(shí)為0；a2,b2也不同時(shí)為0。設(shè)

D=a1b1Dx=b1c1Dy=c1a1a2b2b2c2c2a2若D≠0，則兩直線L1,L2相交于一平常點(diǎn)P(x,y)，其坐標(biāo)為x=Dx/D，y=Dy/D.這組解可表為：x/Dx=y/Dy=1/D(約定：分母Dx，Dy有為0時(shí)，對(duì)應(yīng)的分子也要為0）上述表示可抽象為（Dx，Dy，D).若D=0，則L1∥L2，此時(shí)L1和L2交于一個(gè)無窮遠(yuǎn)點(diǎn)P∞。這個(gè)點(diǎn)P∞可用過原點(diǎn)O且平行于L2的一條直線L來指出他的方向，而這條直線L的方程就是：a2x+b2y=0.其中a1,b1不同時(shí)為0；a2,b2也不同時(shí)為0。3為把平常點(diǎn)和無窮遠(yuǎn)點(diǎn)的坐標(biāo)統(tǒng)一起來，把點(diǎn)的坐標(biāo)用（X，Y，Z)表示，X，Y，Z不能同時(shí)為0，且對(duì)平常點(diǎn)（x，y)來說，有Z≠0，x=X/Z，y=Y/Z，于是有：

i.e.

X/Dx=Y/Dy=Z/D，有更好的坐標(biāo)抽象，X,Y,Z),這樣對(duì)于無窮遠(yuǎn)點(diǎn)則有Z=0，也成立。注：a).若實(shí)數(shù)p≠0，則(pX,pY,pZ)與（X,Y,Z)表示同一個(gè)點(diǎn)。實(shí)質(zhì)上用（X:Y:Z)表示。3個(gè)分量中，只有兩個(gè)是獨(dú)立的，具有這種特征的坐標(biāo)就叫齊次坐標(biāo)。i.e.為把平常點(diǎn)和無窮遠(yuǎn)點(diǎn)的坐標(biāo)統(tǒng)一起來，把點(diǎn)的坐標(biāo)用i.e.4b).設(shè)有歐氏直線L，它在平面直角坐標(biāo)系Oxy上的方程為：

ax+by+c=0則L上任一平常點(diǎn)(x,y)的齊次坐標(biāo)為(X,Y,Z)，Z≠0，代入得：

aX+bY+cZ=0給L添加的無窮遠(yuǎn)點(diǎn)的坐標(biāo)(X,Y,Z)應(yīng)滿足aX+bY=0，Z=0;平面上無窮遠(yuǎn)直線方程自然為：Z=0

!!(3)任意域上的橢圓曲線K為域，K上的攝影平面P2(K)是一些等價(jià)類的集合{(X:Y:Z)}。考慮下面的Weierstrass方程(次數(shù)為3的齊次方程)：

Y2Z+a1XYZ+a3YZ2=X3+a2X2z+a4XZ2+a6Z3

(其中系數(shù)ai∈K，或ai∈K為K的代數(shù)閉域）b).設(shè)有歐氏直線L，它在平面直角坐標(biāo)系Oxy上的方程為：5Weierstrass方程被稱為光滑的或非奇異的是指對(duì)所有適合以下方程的射影點(diǎn)P=(X:Y:Z)∈P2(K)來說，F(xiàn)(X,Y,Z)=Y2Z+a1XYZ+a3YZ2-X3-a2X2Z-a4XZ2-a6Z3=0在P點(diǎn)的三個(gè)偏導(dǎo)數(shù)之中至少有一個(gè)不為0若否稱這個(gè)方程為奇異的。橢圓曲線E的定義：橢圓曲線E是一個(gè)光滑的Weierstrass方程在P2(K)中的全部解集合。Y2Z+a1XYZ+a3YZ2=X3+a2X2Z+a4XZ2+a6Z3注：a)在橢圓曲線E上恰有一個(gè)點(diǎn)，稱之為無窮遠(yuǎn)點(diǎn)。即(0:1:0)用θ表示。Weierstrass方程被稱為光滑的或非奇異的是指對(duì)所有適6b)可用非齊次坐標(biāo)的形式來表示橢圓曲線的Weierstrass方程:設(shè)x=X/Z，y=Y/Z，于是原方程轉(zhuǎn)化為：

y2+a1xy+a3y=x3+a2x2+a4x+a6(1)此時(shí)，橢圓曲線E就是方程（1)在射影平面P2(K)上的全部平常點(diǎn)解，外加一個(gè)無窮遠(yuǎn)點(diǎn)θ組成的集合。c)若a1,a2,a2,a4,a6∈K，此時(shí)橢圓曲線E被稱為定義在K上，用E/K表示。如果E能被限定在K上，那么E的K——有理點(diǎn)集合表示為E(K)，它為E中的全體有理坐標(biāo)點(diǎn)的集合外加無窮遠(yuǎn)點(diǎn)θ.(4)實(shí)域R上的橢圓曲線設(shè)K=R，此時(shí)的橢圓曲線可表為平面上的通常曲線上的點(diǎn)，外加無窮遠(yuǎn)點(diǎn)θ。b)可用非齊次坐標(biāo)的形式來表示橢圓曲線的Weier7實(shí)域R上橢圓曲線的點(diǎn)的加法運(yùn)算法則：設(shè)L∈P2(R)為一條直線。因?yàn)镋的方程是三次的，所以L可與E在P2(R)恰有三個(gè)交點(diǎn)，記為P,Q,R（注意：如果L與E相切，那么P,Q,R可以不是相異的）。按下述方式定義E上運(yùn)算：設(shè)P,Q∈E，L為聯(lián)接P,Q的直線（若P=Q，則L取過P點(diǎn)的切線）；設(shè)R為L與E的另一個(gè)交點(diǎn)；再取連接R與無窮遠(yuǎn)點(diǎn)的直線L′。則L′與E的另一個(gè)交點(diǎn)定義為PQ。信息安全專題講座07課件8PQP=QLLL′L′(PQ)

R=θθθTT=θ(P=Q=R)PQPQRRTPQP=QLLL′L′(PQ)R=θθθTT=θP9上頁的實(shí)際圖像為橢圓曲線y2=x3-x的一般化。來自對(duì)具體曲線的抽象。對(duì)運(yùn)算更具體一些：設(shè)P=(x1,y1)，Q=(x2,y2)，PQ=(x3,y3),由PQ的定義，設(shè)y=αx+β為通過P,Q兩點(diǎn)直線L的方程，可算出：

α=(y2-y1)/(x2-x1),β=y1-αx1

易見，直線L上的一個(gè)點(diǎn)（x,αx+β)是在橢圓曲線E上，當(dāng)且僅當(dāng)(αx+β)2=x3–x。

PQ=(x1,y1)(x2,y2)=(x3,y3)=(x3,-(αx3+β))其中，x3=α2-x1-x2=((y2-y1)/(x2-x1))2-x1-x2；

y3=-y1+((y2-y1)/(x2-x1))(x1-x3)當(dāng)P=Q時(shí)：

PQ=（x3，y3）算得：x3=((3x12-1)/2y1)2-2x1;y3=-y1+((3x12-1)/2y1)(x1-x3)

上頁的實(shí)際圖像為橢圓曲線y2=x3-x的一般化。10注：a)如果直線L與E相交與三點(diǎn)P,Q,R(不一定相異），那么(PQ)R=θ(從圖中可見）。b)任給P∈E,Pθ=P(此時(shí)設(shè)Q=θ，易見L=L′)c)任給P,Q∈E有：PQ=QPd)設(shè)P∈E，那么可以找到-P∈E使P-P=θe)任給P,Q,R∈E，有(PQ)R=P(QR)綜上所述，知E對(duì)運(yùn)算形成一個(gè)Abel群。f)上述規(guī)則可開拓到任意域上，特別是有限域上。假定橢圓曲線是定義在有限域Fq上（q=pm)，那么

E(Fq)={(x,y)∈Fq×Fq|y2+a1xy+a3y=x3+a2x2+a4x+a6}∪{θ}它對(duì)“”形成一個(gè)群，為Abel群。注：112有限域上橢圓曲線的運(yùn)算令Fq表示q個(gè)元素的有限域，用E(Fq)表示定義在Fq上的一個(gè)橢圓曲線E。定理1.(Hass定理)

E(Fq)的點(diǎn)數(shù)用#E(Fq)表示，則

|#E(Fq)-q-1|≤2q1/2(1)Fp（素域，p為素?cái)?shù)）上橢圓曲線

令p>3，a,b∈Fp，滿足4a3+27b2≠0，由參數(shù)a和b定義的Fp上的一個(gè)橢圓曲線方程為：y2=x3+ax+b(2)它的所有解(x,y)，(xFp，yFp)，連同一個(gè)稱為“無窮遠(yuǎn)點(diǎn)”（記為θ）的元素組成的集合記為E(Fp)，由Hass定理2有限域上橢圓曲線的運(yùn)算令Fq表示q12知：p+1-2p1/2≤#E(Fp)≤p+1+2p1/2集合E(Fp)對(duì)應(yīng)下面的加法規(guī)則，且對(duì)加法形成一個(gè)Abel群：(i)θθ=θ（單位元素）(ii)

(x,y)θ=(x,y),任給(x,y)∈E(Fp)(iii)

(x,y)(x,-y)=θ，任給(x,y)∈E(Fp),即點(diǎn)(x,y)的逆元為(x,-y).(iv)令(x1,y1),(x2,y2)為E(Fp)中非互逆元，則(x1,y1)(x2,y2)=(x3,y3),其中

x3=α2-2x1，y3=α(x1-x3)-y1且α=(y2-y1)/(x2-x1)（3）(v)（倍點(diǎn)運(yùn)算規(guī)則）設(shè)(x1,y1)∈E(Fp),y1≠0，則2(x1,y1)=(x3,y3)，其中知：p+1-2p1/2≤#E(Fp)≤p+1+2p1/213

x3=α2-2x1,y3=α(x1-x3)-y1這里α=(3x12+a)/(2y1)(4)注：若#E(Fp)=p+1，曲線E(Fp)稱為超奇異的，否則稱為

非超奇異的。例子：F23上的一個(gè)橢圓曲線令y2=x3+x+1是F23上的一個(gè)方程(a=b=1)，則該橢圓曲線方程在F23上的解為(y2=x3+x+1的點(diǎn))：(0,1)，(0,22)，(1,7)，(1,16)，(3,10)，(3,13)，(4,0)，(5,4)，(5,19)，(6,4)，(6,19)，(7,11)，(7,12)，(9,7)，(9,16)，(11,3)，(11,20)，(12,4)，(12,19)，(13,7)，(13,16)，(17,3)，(17,20)，(18,3)，(18,20)，(19,5)，(19,18)；θ。群E(F23)有28個(gè)點(diǎn)（包括無窮遠(yuǎn)點(diǎn)θ）。x3=α2-2x1,y3=α(x1-14(2)F2m上的橢圓曲線

F2m上由參數(shù)a,b∈F2m，b≠0定義的一個(gè)非超奇異橢圓曲線E(F2m)是方程y2+xy=x3+ax2+b(5)的解集合(x,y)，其中x,y∈F2m，連同θ。E(F2m)的加法規(guī)則如下：(i)θ+θ=θ(ii)任給(x,y)∈E(F2m)，則(x,y)θ=(x,y)(iii)任給(x,y)∈E(F2m)，則(x,y)+(x,x+y)=θ，即點(diǎn)(x,y)的逆為(x,x+y).(iv)兩個(gè)相異且不互逆的點(diǎn)的加法規(guī)則：令(x1,y1),(x2,y2)∈E(F2m)且有x1≠x2則(2)F2m上的橢圓曲線F2m上由參數(shù)a,b∈15(x1,y1)(x2,y2)=(x3,y3)，其中

x3=α2+α+x1+x2+a；y3=α(x1+x3)+x3+y1.其中α=(y2+y1)/(x2+x1)(v)倍點(diǎn)規(guī)則令(x1,y1)∈E(F2m)，其中x1≠0。則

2(x1,y1)=(x3,y3)，其中

x3=α2+α+a,y3=x12+(α+1)x3,這里α=(x1+y1/x1)易見，群E(F2m)為Abel群。例：F24上的一個(gè)橢圓曲線f(x)=x4+x+1為F2上的一個(gè)不可約多項(xiàng)式，易見

(x1,y1)(x2,y2)=(x3,y316F24=F2[x]/(f(x))={(k0,k1,k2,k3)|(k0,k1,k2,k3)=k0+k1α+k2α2+k3α3，α為f(x)的零點(diǎn)，ki∈F2}假定F24上的非超奇異橢圓曲線有下述方程定義：y2+xy=x3+α4x2+1，注意f(α)=0。方程應(yīng)表為：(1000)y2+(1000)xy=(1000)x3+(1100)x2+(1000)F24=F2[x]/(f(x))=173橢圓曲線密碼體制1985年，N.Koblitz和V.Miller分別獨(dú)立提出了橢圓曲線密碼體制(ECC)，其依據(jù)就是定義在橢圓曲線點(diǎn)群上的離散對(duì)數(shù)問題的難解性。（1）知E(Fq)對(duì)點(diǎn)的“”運(yùn)算形成一個(gè)Abel群設(shè)p∈E(Fq)，若p的周期很大，即使

pp……p=θ(共有t個(gè)p相加）成立的最小正整數(shù)t，希望t很大。(t=p的周期，表示為∏(p)=t)。并且對(duì)Q∈E(Fq)，定有某個(gè)正整數(shù)m使

Q=m·p=p……p(共有t個(gè)p相加)3橢圓曲線密碼體制1985年，18定義

m=㏒pQ(m為以p為底Q的對(duì)數(shù)）。橢圓曲線上的點(diǎn)形成的群E(Fq)，相關(guān)它的離散對(duì)數(shù)問題是難處理的。（2）建立橢圓曲線密碼體制

選取基域Fq，F(xiàn)q的橢圓曲線具體給定為確定的形式。在E(Fq)中選一個(gè)周期很大的點(diǎn)，如選了一個(gè)點(diǎn)P=(xp,yp)，它的周期為一個(gè)大的素?cái)?shù)n，記∏(P)=n(素?cái)?shù))。注意：在這個(gè)密碼體制中，具體的曲線及點(diǎn)P和它的n都是公開信息。密碼體制的形式采用EIGamal體制，是完全類比過來。定義19a)密鑰的生成

Bob(使用者）執(zhí)行了下列計(jì)算：i)在區(qū)間[1,n-1]中隨機(jī)選取一個(gè)整數(shù)d。ii)計(jì)算點(diǎn)Q:=dP(d個(gè)P相）iii)Bob公開自己的公開密鑰——(E(Fq),p,n,Q)iv)Bob的私鑰為整數(shù)d！Alice要發(fā)送消息m給Bob，Alice執(zhí)行：i)查找Bob的公鑰(E(Fq),p,n,Q),ii)將m表示成一個(gè)域元素m∈Fq,iii)在區(qū)間[1，n-1]內(nèi)選取一個(gè)隨機(jī)數(shù)k,iv)依據(jù)Bob的公鑰計(jì)算點(diǎn)(x1,y1):=kP(k個(gè)P相）v)計(jì)算點(diǎn)(x2,y2):=kQ,如果x2=0,則回到第iii)步.a)密鑰的生成

Bob(使用者）執(zhí)行了下列計(jì)算：20精品課件！精品課件！21精品課件！精品課件！22ⅵ)計(jì)算C:=m·x2

ⅶ)傳送加密數(shù)據(jù)(x1,y1,C)給Bobb)Bob的解密過程Bob收到Alice的密文(x1,y1,C)后，執(zhí)行i)使用私鑰d，計(jì)算點(diǎn)(x2，y2):=d(x1,y1)，再計(jì)算Fq中x2-1=?Ii)通過計(jì)算m:=C·x2-1，恢復(fù)出明文數(shù)據(jù)m。ⅵ)計(jì)算C:=m·x223Q=∠BAP→/2AP→L2可設(shè)想L1上有一點(diǎn)P∞，它為L2和L1的交點(diǎn)，稱之為無窮遠(yuǎn)點(diǎn)。直線L1上的無窮遠(yuǎn)點(diǎn)只能有一個(gè)。（因?yàn)檫^A點(diǎn)只能有一條平行于L1的直線L2，而兩直線的交點(diǎn)只能有一個(gè)。）結(jié)論：1*.平面上一組相互平行的直線，有公共的無窮遠(yuǎn)點(diǎn)。（為與無窮遠(yuǎn)點(diǎn)相區(qū)別，把原來平面上的點(diǎn)叫做平常點(diǎn)）2*.平面上任何相交的兩直線L1,L2有不同的無窮遠(yuǎn)點(diǎn)。原因：若否，則L1和L2有公共的無窮遠(yuǎn)點(diǎn)P∞，則過兩相異點(diǎn)A和P∞有相異兩直線，與公理相矛盾。Q=∠BAP→/2AP→243*.全體無窮遠(yuǎn)點(diǎn)構(gòu)成一條無窮遠(yuǎn)直線。注：歐式平面添加上無窮遠(yuǎn)點(diǎn)和無窮遠(yuǎn)直線，自然構(gòu)成射影平面。(2)齊次坐標(biāo)解析幾何中引入坐標(biāo)系，用代數(shù)的方法研究歐氏空間。這樣的坐標(biāo)法也可推廣至攝影平面上，建立平面攝影坐標(biāo)系。

平面上兩相異直線L1,L2，其方程分別為：

L1:a1x+b1y+c1=0 L2:a2x+b2y+c2=0AL1L2P∞3*.全體無窮遠(yuǎn)點(diǎn)構(gòu)成一條無窮遠(yuǎn)直線。AL1L2P∞25其中a1,b1不同時(shí)為0；a2,b2也不同時(shí)為0。設(shè)

D=a1b1Dx=b1c1Dy=c1a1a2b2b2c2c2a2若D≠0，則兩直線L1,L2相交于一平常點(diǎn)P(x,y)，其坐標(biāo)為x=Dx/D，y=Dy/D.這組解可表為：x/Dx=y/Dy=1/D(約定：分母Dx，Dy有為0時(shí)，對(duì)應(yīng)的分子也要為0）上述表示可抽象為（Dx，Dy，D).若D=0，則L1∥L2，此時(shí)L1和L2交于一個(gè)無窮遠(yuǎn)點(diǎn)P∞。這個(gè)點(diǎn)P∞可用過原點(diǎn)O且平行于L2的一條直線L來指出他的方向，而這條直線L的方程就是：a2x+b2y=0.其中a1,b1不同時(shí)為0；a2,b2也不同時(shí)為0。26為把平常點(diǎn)和無窮遠(yuǎn)點(diǎn)的坐標(biāo)統(tǒng)一起來，把點(diǎn)的坐標(biāo)用（X，Y，Z)表示，X，Y，Z不能同時(shí)為0，且對(duì)平常點(diǎn)（x，y)來說，有Z≠0，x=X/Z，y=Y/Z，于是有：

i.e.

X/Dx=Y/Dy=Z/D，有更好的坐標(biāo)抽象，X,Y,Z),這樣對(duì)于無窮遠(yuǎn)點(diǎn)則有Z=0，也成立。注：a).若實(shí)數(shù)p≠0，則(pX,pY,pZ)與（X,Y,Z)表示同一個(gè)點(diǎn)。實(shí)質(zhì)上用（X:Y:Z)表示。3個(gè)分量中，只有兩個(gè)是獨(dú)立的，具有這種特征的坐標(biāo)就叫齊次坐標(biāo)。i.e.為把平常點(diǎn)和無窮遠(yuǎn)點(diǎn)的坐標(biāo)統(tǒng)一起來，把點(diǎn)的坐標(biāo)用i.e.27b).設(shè)有歐氏直線L，它在平面直角坐標(biāo)系Oxy上的方程為：

ax+by+c=0則L上任一平常點(diǎn)(x,y)的齊次坐標(biāo)為(X,Y,Z)，Z≠0，代入得：

aX+bY+cZ=0給L添加的無窮遠(yuǎn)點(diǎn)的坐標(biāo)(X,Y,Z)應(yīng)滿足aX+bY=0，Z=0;平面上無窮遠(yuǎn)直線方程自然為：Z=0

!!(3)任意域上的橢圓曲線K為域，K上的攝影平面P2(K)是一些等價(jià)類的集合{(X:Y:Z)}?？紤]下面的Weierstrass方程(次數(shù)為3的齊次方程)：

Y2Z+a1XYZ+a3YZ2=X3+a2X2z+a4XZ2+a6Z3

(其中系數(shù)ai∈K，或ai∈K為K的代數(shù)閉域）b).設(shè)有歐氏直線L，它在平面直角坐標(biāo)系Oxy上的方程為：28Weierstrass方程被稱為光滑的或非奇異的是指對(duì)所有適合以下方程的射影點(diǎn)P=(X:Y:Z)∈P2(K)來說，F(xiàn)(X,Y,Z)=Y2Z+a1XYZ+a3YZ2-X3-a2X2Z-a4XZ2-a6Z3=0在P點(diǎn)的三個(gè)偏導(dǎo)數(shù)之中至少有一個(gè)不為0若否稱這個(gè)方程為奇異的。橢圓曲線E的定義：橢圓曲線E是一個(gè)光滑的Weierstrass方程在P2(K)中的全部解集合。Y2Z+a1XYZ+a3YZ2=X3+a2X2Z+a4XZ2+a6Z3注：a)在橢圓曲線E上恰有一個(gè)點(diǎn)，稱之為無窮遠(yuǎn)點(diǎn)。即(0:1:0)用θ表示。Weierstrass方程被稱為光滑的或非奇異的是指對(duì)所有適29b)可用非齊次坐標(biāo)的形式來表示橢圓曲線的Weierstrass方程:設(shè)x=X/Z，y=Y/Z，于是原方程轉(zhuǎn)化為：

y2+a1xy+a3y=x3+a2x2+a4x+a6(1)此時(shí)，橢圓曲線E就是方程（1)在射影平面P2(K)上的全部平常點(diǎn)解，外加一個(gè)無窮遠(yuǎn)點(diǎn)θ組成的集合。c)若a1,a2,a2,a4,a6∈K，此時(shí)橢圓曲線E被稱為定義在K上，用E/K表示。如果E能被限定在K上，那么E的K——有理點(diǎn)集合表示為E(K)，它為E中的全體有理坐標(biāo)點(diǎn)的集合外加無窮遠(yuǎn)點(diǎn)θ.(4)實(shí)域R上的橢圓曲線設(shè)K=R，此時(shí)的橢圓曲線可表為平面上的通常曲線上的點(diǎn)，外加無窮遠(yuǎn)點(diǎn)θ。b)可用非齊次坐標(biāo)的形式來表示橢圓曲線的Weier30實(shí)域R上橢圓曲線的點(diǎn)的加法運(yùn)算法則：設(shè)L∈P2(R)為一條直線。因?yàn)镋的方程是三次的，所以L可與E在P2(R)恰有三個(gè)交點(diǎn)，記為P,Q,R（注意：如果L與E相切，那么P,Q,R可以不是相異的）。按下述方式定義E上運(yùn)算：設(shè)P,Q∈E，L為聯(lián)接P,Q的直線（若P=Q，則L取過P點(diǎn)的切線）；設(shè)R為L與E的另一個(gè)交點(diǎn)；再取連接R與無窮遠(yuǎn)點(diǎn)的直線L′。則L′與E的另一個(gè)交點(diǎn)定義為PQ。信息安全專題講座07課件31PQP=QLLL′L′(PQ)

R=θθθTT=θ(P=Q=R)PQPQRRTPQP=QLLL′L′(PQ)R=θθθTT=θP32上頁的實(shí)際圖像為橢圓曲線y2=x3-x的一般化。來自對(duì)具體曲線的抽象。對(duì)運(yùn)算更具體一些：設(shè)P=(x1,y1)，Q=(x2,y2)，PQ=(x3,y3),由PQ的定義，設(shè)y=αx+β為通過P,Q兩點(diǎn)直線L的方程，可算出：

α=(y2-y1)/(x2-x1),β=y1-αx1

易見，直線L上的一個(gè)點(diǎn)（x,αx+β)是在橢圓曲線E上，當(dāng)且僅當(dāng)(αx+β)2=x3–x。

PQ=(x1,y1)(x2,y2)=(x3,y3)=(x3,-(αx3+β))其中，x3=α2-x1-x2=((y2-y1)/(x2-x1))2-x1-x2；

y3=-y1+((y2-y1)/(x2-x1))(x1-x3)當(dāng)P=Q時(shí)：

PQ=（x3，y3）算得：x3=((3x12-1)/2y1)2-2x1;y3=-y1+((3x12-1)/2y1)(x1-x3)

上頁的實(shí)際圖像為橢圓曲線y2=x3-x的一般化。33注：a)如果直線L與E相交與三點(diǎn)P,Q,R(不一定相異），那么(PQ)R=θ(從圖中可見）。b)任給P∈E,Pθ=P(此時(shí)設(shè)Q=θ，易見L=L′)c)任給P,Q∈E有：PQ=QPd)設(shè)P∈E，那么可以找到-P∈E使P-P=θe)任給P,Q,R∈E，有(PQ)R=P(QR)綜上所述，知E對(duì)運(yùn)算形成一個(gè)Abel群。f)上述規(guī)則可開拓到任意域上，特別是有限域上。假定橢圓曲線是定義在有限域Fq上（q=pm)，那么

E(Fq)={(x,y)∈Fq×Fq|y2+a1xy+a3y=x3+a2x2+a4x+a6}∪{θ}它對(duì)“”形成一個(gè)群，為Abel群。注：342有限域上橢圓曲線的運(yùn)算令Fq表示q個(gè)元素的有限域，用E(Fq)表示定義在Fq上的一個(gè)橢圓曲線E。定理1.(Hass定理)

E(Fq)的點(diǎn)數(shù)用#E(Fq)表示，則

|#E(Fq)-q-1|≤2q1/2(1)Fp（素域，p為素?cái)?shù)）上橢圓曲線

令p>3，a,b∈Fp，滿足4a3+27b2≠0，由參數(shù)a和b定義的Fp上的一個(gè)橢圓曲線方程為：y2=x3+ax+b(2)它的所有解(x,y)，(xFp，yFp)，連同一個(gè)稱為“無窮遠(yuǎn)點(diǎn)”（記為θ）的元素組成的集合記為E(Fp)，由Hass定理2有限域上橢圓曲線的運(yùn)算令Fq表示q35知：p+1-2p1/2≤#E(Fp)≤p+1+2p1/2集合E(Fp)對(duì)應(yīng)下面的加法規(guī)則，且對(duì)加法形成一個(gè)Abel群：(i)θθ=θ（單位元素）(ii)

(x,y)θ=(x,y),任給(x,y)∈E(Fp)(iii)

(x,y)(x,-y)=θ，任給(x,y)∈E(Fp),即點(diǎn)(x,y)的逆元為(x,-y).(iv)令(x1,y1),(x2,y2)為E(Fp)中非互逆元，則(x1,y1)(x2,y2)=(x3,y3),其中

x3=α2-2x1，y3=α(x1-x3)-y1且α=(y2-y1)/(x2-x1)（3）(v)（倍點(diǎn)運(yùn)算規(guī)則）設(shè)(x1,y1)∈E(Fp),y1≠0，則2(x1,y1)=(x3,y3)，其中知：p+1-2p1/2≤#E(Fp)≤p+1+2p1/236

x3=α2-2x1,y3=α(x1-x3)-y1這里α=(3x12+a)/(2y1)(4)注：若#E(Fp)=p+1，曲線E(Fp)稱為超奇異的，否則稱為

非超奇異的。例子：F23上的一個(gè)橢圓曲線令y2=x3+x+1是F23上的一個(gè)方程(a=b=1)，則該橢圓曲線方程在F23上的解為(y2=x3+x+1的點(diǎn))：(0,1)，(0,22)，(1,7)，(1,16)，(3,10)，(3,13)，(4,0)，(5,4)，(5,19)，(6,4)，(6,19)，(7,11)，(7,12)，(9,7)，(9,16)，(11,3)，(11,20)，(12,4)，(12,19)，(13,7)，(13,16)，(17,3)，(17,20)，(18,3)，(18,20)，(19,5)，(19,18)；θ。群E(F23)有28個(gè)點(diǎn)（包括無窮遠(yuǎn)點(diǎn)θ）。x3=α2-2x1,y3=α(x1-37(2)F2m上的橢圓曲線

F2m上由參數(shù)a,b∈F2m，b≠0定義的一個(gè)非超奇異橢圓曲線E(F2m)是方程y2+xy=x3+ax2+b(5)的解集合(x,y)，其中x,y∈F2m，連同θ。E(F2m)的加法規(guī)則如下：(i)θ+θ=θ(ii)任給(x,y)∈E(F2m)，則(x,y)θ=(x,y)(iii)任給(x,y)∈E(F2m)，則(x,y)+(x,x+y)=θ，即點(diǎn)(x,y)的逆為(x,x+y).(iv)兩個(gè)相異且不互逆的點(diǎn)的加法規(guī)則：令(x1,y1),(x2,y2)∈E(F2m)且有x1≠x2則(2)F2m上的橢圓曲線F2m上由參數(shù)a,b∈38(x1,y1)(x2,y2)=(x3,y3)，其中

x3=α2+α+x1+x2+a；y3=α(x1+x3)+x3+y1.其中α=(y2+y1)/(x2+x1)(v)倍點(diǎn)規(guī)則令(x1,y1)∈E(F2m)，其中x1≠0。則

2(x1,y1)=(x3,y3)，其中

x3=α2+α+a,y3=x12+(α+1)x3,這里α=(x1+y1/x1)易見，群E(F2m)為Abel群。例：F24上的一個(gè)橢圓曲線f(x)=x4+x+1為F2上的一個(gè)不可約多項(xiàng)式，