7.橢圓曲線密碼學-中國安全網(wǎng)-安全您的網(wǎng)絡安全

1、第七章 橢圓曲線密碼學,1 有關(guān)的基本概念 (1) 無窮遠元素（無窮遠點，無窮遠直線） 平面上任意兩相異直線的位置關(guān)系有相交和平行兩種。引入無窮遠點，是兩種不同關(guān)系統(tǒng)一。 AB⊥L1， L2∥L1，直線AP由AB起繞A點依逆時針方向轉(zhuǎn)動，P為AP與L1的交點。,,,,,,L2,L1,P∞,B,A,P,Q,,Q=∠BAP→? /2 AP → L2可設想L1上有一點P

2、∞，它為L2和L1的交點，稱之為無窮遠點。直線L1上的無窮遠點只能有一個。（因為過A點只能有一條平行于L1的直線L2，而兩直線的交點只能有一個。）結(jié)論：1*. 平面上一組相互平行的直線，有公共的無窮遠點。（為與無窮遠點相區(qū)別，把原來平面上的點叫做平常點）2* .平面上任何相交的兩直線L1,L2有不同的無窮遠點。原因：若否，則L1和L2有公共的無窮遠點P∞，則過兩相異點A和P ∞有相異兩直線，與公理相矛盾。,,3*. 全體無

3、窮遠點構(gòu)成一條無窮遠直線。注：歐式平面添加上無窮遠點和無窮遠直線，自然構(gòu)成射影平面。(2) 齊次坐標 解析幾何中引入坐標系，用代數(shù)的方法研究歐氏空間。這樣的坐標法也可推廣至攝影平面上，建立平面攝影坐標系。 平面上兩相異直線L1,L2，其方程分別為： L1: a1x+b1y+c1=0 L2: a2x+b2y+c2=0,,,A,L1,L2,,P∞,其中a1,b1

4、不同時為0；a2,b2也不同時為0。設 D= a1 b1 Dx= b1 c1 Dy= c1 a1 a2 b2 b2 c2 c2 a2若D≠0，則兩直線L1,L2相交于一平常點P(x,y)，其坐標為x=Dx/D，y=Dy/D.這組解可表為：x/Dx=y/Dy=1/D(約定：分母D

5、x，Dy有為0時，對應的分子也要為0）上述表示可抽象為（Dx，Dy，D).若 D=0，則L1∥L2，此時L1和L2交于一個無窮遠點P∞。這個點P∞可用過原點O且平行于L2的一條直線L來指出他的方向，而這條直線L的方程就是：a2x+b2y=0.,,,,,,,為把平常點和無窮遠點的坐標統(tǒng)一起來，把點的坐標用（X，Y，Z)表示，X，Y，Z不能同時為0，且對平常點（x，y)來說，有Z≠0，x=X/Z，y=Y/Z，于是有：

6、 i.e. X / Dx = Y / Dy = Z / D，有更好的坐標抽象，X,Y,Z),這樣對于無窮遠點則有Z=0，也成立。注：a).若實數(shù)p≠0，則(pX,pY,pZ)與（X,Y,Z)表示同一個點。實質(zhì)上用（X:Y:Z)表示。3個分量中，只有兩個是獨立的，具有這種特征的坐標就叫齊次

7、坐標。,i.e.,b).設有歐氏直線L，它在平面直角坐標系Oxy上的方程為： ax+by+c=0 則L上任一平常點(x,y)的齊次坐標為(X,Y,Z)，Z≠0，代入得： aX+bY+cZ=0 給L添加的無窮遠點的坐標(X,Y,Z)應滿足aX+bY=0，Z=0;平面上無窮遠直線方程自然為：Z=0 !! (3)任意域上的橢圓曲線K為域，K上的攝

8、影平面P2(K)是一些等價類的集合{(X:Y:Z)}。考慮下面的Weierstrass方程(次數(shù)為3的齊次方程)： Y2Z+a1XYZ+a3YZ2=X3+a2X2z+a4XZ2+a6Z3 (其中系數(shù)ai∈K，或ai∈K為K的代數(shù)閉域）,Weierstrass方程被稱為光滑的或非奇異的是指對所有適合以下方程的射影點P=(X:Y:Z) ∈ P2(K)來說， F(X,Y,Z)=Y2Z+a1XYZ+a

9、3YZ2-X3-a2X2Z-a4XZ2-a6Z3=0在P點的三個偏導數(shù) 之中至少有一個不為 0若否稱這個方程為奇異的。橢圓曲線E的定義： 橢圓曲線E是一個光滑的Weierstrass方程在P2(K)中的全部解集合。 Y2Z+a1XYZ+a3YZ2=X3+a2X2Z+a4XZ2+a6Z3注：a) 在橢圓曲線E上恰有一個點，稱之為無窮遠點

10、。即(0:1:0)用θ表示。,b) 可用非齊次坐標的形式來表示橢圓曲線的Weierstrass方程: 設 x=X/Z，y=Y/Z，于是原方程轉(zhuǎn)化為： y2+a1xy+a3y=x3+a2x2+a4x+a6 (1) 此時，橢圓曲線E就是方程（1)在射影平面P2(K)上的全部平常點解，外加一個無窮遠點θ組成的集合。c

11、) 若a1,a2,a2,a4,a6∈K，此時橢圓曲線E被稱為定義在K上，用E/K表示。如果E能被限定在K上，那么E的K——有理點集合表示為E(K)，它為E中的全體有理坐標點的集合外加無窮遠點θ.(4)實域R上的橢圓曲線 設K=R，此時的橢圓曲線可表為平面上的通常曲線上的點，外加無窮遠點θ。,,實域R上橢圓曲線的點的加法運算法則： 設L ∈ P2(R)為一條直線。因為E的方程是三次的，所

12、以L可與E在P2(R)恰有三個交點，記為P,Q,R（注意：如果L與E相切，那么P,Q,R可以不是相異的）。按下述方式定義E上運算?： 設P,Q ∈ E，L為聯(lián)接P,Q的直線（若P=Q，則L取過P點的切線）；設R為L與E的另一個交點；再取連接R與無窮遠點的直線L′。則L′與E的另一個交點定義為P ? Q。,,,,,,,,,,P,Q,P=Q,L,L,L′,L′,(P?Q) ?R=θ,θ,θ,T?T= θ(P=Q=

13、R),P?Q,P?Q,,,R,,R,T,,上頁的實際圖像為橢圓曲線y2=x3 - x的一般化。來自對具體曲線的抽象。對運算更具體一些： 設 P=(x1,y1)，Q=(x2,y2)，P?Q=(x3,y3), 由P?Q的定義，設y=αx+β為通過P,Q兩點直線L的方程，可算出： α=( y2-y1 )/(x2-x1), β=y1-αx1 易見，直線L

14、上的一個點（x, αx+β)是在橢圓曲線E上， 當且僅當(αx+β)2= x3 – x 。 P?Q=(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) 當P=Q時： P?Q=（x

15、3，y3）算得： x3=((3x12-1)/2y1)2-2x1; y3= -y1+((3x12-1)/2y1)(x1-x3),注：a) 如果直線L與E相交與三點P,Q,R(不一定相異），那么 (P?Q)?R=θ(從圖中可見）。b) 任給P∈E, P ? θ =P (此時設Q= θ ，易見L=L′)c) 任給P,Q∈E有： P ? Q =Q ? Pd) 設P∈E，那么可以找到 - P∈E使P ? -P= θ

16、e) 任給P,Q,R∈E，有(P ? Q) ? R= P ?(Q ? R) 綜上所述，知E對? 運算形成一個Abel群。f) 上述規(guī)則可開拓到任意域上，特別是有限域上。假定 橢圓曲線是定義在有限域Fq上（q=pm)，那么 E(Fq)={(x,y)∈Fq×Fq | y2+a1xy+a3y=x3+a2x2+a4x+a6} ∪{θ}它對“? ”形成一個群，為Abel群。,2 有限域上橢圓曲線的

17、?運算,令Fq表示q個元素的有限域，用E(Fq)表示定義在Fq上的一個橢圓曲線E。定理1.(Hass定理) E(Fq)的點數(shù)用#E(Fq)表示，則 | #E(Fq)-q-1|≤2q1/2(1) Fp（素域，p為素數(shù)）上橢圓曲線 令p>3，a,b∈Fp，滿足4a3+27b2≠0，由參數(shù)a和b定義的Fp上的一個橢圓曲線方程為： y2=x3+ax+b

18、 (2)它的所有解(x,y)，(x?Fp，y?Fp)，連同一個稱為“無窮遠點”（記為θ）的元素組成的集合記為E(Fp)，由Hass定理,知：p+1-2p1/2≤#E(Fp) ≤ p+1+2p1/2 集合E(Fp)對應下面的加法規(guī)則，且對加法?形成一個Abel群：(i) θ ? θ=θ （單位元素）(ii) (x,y) ? θ=(x,y), 任給(x,

19、y) ∈E(Fp)(iii) (x,y) ?(x,-y)=θ，任給(x,y) ∈E(Fp),即點(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)/(x

20、2-x1) （3）(v)（倍點運算規(guī)則） 設(x1,y1) ∈E(Fp),y1≠0，則2(x1,y1)=(x3,y3)，其中,x3= α2-2x1, y3=α(x1-x3)-y1 這里α=(3x12+a)/(2y1) (

21、4)注：若#E(Fp)=p+1，曲線E(Fp)稱為超奇異的，否則稱為 非超奇異的。例子：F23上的一個橢圓曲線 令y2=x3+x+1是F23上的一個方程(a=b=1)，則該橢圓曲線方程在F23上的解為(y2=x3+x+1的點)： (0,1)，(0,22)，(1,7)，(1,16)，(3,10)，(3,13)，(4,0)，(5,4)，(5,19)，(6,4)，(6,19)，(7,1

22、1)，(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個點（包括無窮遠點θ ）。,(2) F2m上的橢圓曲線,F2m上由參數(shù)a,b∈F2m，b≠0定義的一個非超奇異橢圓曲線E(F2m)是方程 y2+xy=x3+ax2+

23、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)= θ， 即點(x,y)的逆為(x,x+y).(iv

24、) 兩個相異且不互逆的點的加法規(guī)則： 令(x1,y1),(x2,y2) ∈E(F2m)且有x1≠x2則,(x1,y1)?(x2,y2)=(x3,y3)，其中 x3=α2+α+x1+x2+a； y3=α(x1+x3)+x3+y1.其中 α= (y2+y1)/(x2+x1)(v) 倍點規(guī)則令(x1,y1) ∈E(F2m)，其中x1≠0。則 2(x1,y1)=(x3,y3)

25、，其中 x3= α 2+ α +a, y3=x12+(α +1)x3, 這里α =(x1+y1/x1)易見，群E(F2m)為Abel群。例：F24上的一個橢圓曲線f(x)=x4+x+1為F2上的一個不可約多項式，易見,F24=F2[x] / (f(x)) = {(k0,k1,k2,k3) | (k0,k1,k2,k3)=k0+k1α+k2α2+k3α3， α為f(x)的零點，ki∈F2}假定F24上的非超

26、奇異橢圓曲線有下述方程定義： y2+xy=x3+α4x2+1，注意f(α)=0。 方程應表為： (1000)y2 + (1000)xy = (1000)x3 + (1100)x2 +(1000),3 橢圓曲線密碼體制,1985年，N. Koblitz和V. Miller分別獨立提出了橢圓曲線密碼體制(ECC)，其依據(jù)就是定義在橢圓曲線點群上的離散對數(shù)問題的難解性。（1）知E(Fq)對點的“?”運算形成一個

27、Abel群設p∈E(Fq)，若p的周期很大，即使 p? p ?…… ? p= θ (共有 t個p相加） 成立的最小正整數(shù) t，希望 t 很大。 (t = p的周期，表示為∏(p)=t)。 并且對Q∈E(Fq)，定有某個正整數(shù)m使 Q=m·p=p ? …… ? p (共有t個p相加),定義 m=㏒pQ

28、 (m為以p為底Q的對數(shù)）。 橢圓曲線上的點形成的群E(Fq)，相關(guān)它的離散對數(shù)問題是難處理的。（2） 建立橢圓曲線密碼體制 選取基域Fq，F(xiàn)q的橢圓曲線具體給定為確定的形式。在E(Fq)中選一個周期很大的點，如選了一個點P=(xp,yp)，它的周期為一個大的素數(shù)n，記∏ (P)=n(素數(shù))。注意：在這個密碼體制中，具體的曲線及點P和它的n都是公開信息。密碼體制的形式采用E

29、IGamal體制，是完全類比過來。,,a)密鑰的生成Bob(使用者）執(zhí)行了下列計算： i) 在區(qū)間[1,n-1]中隨機選取一個整數(shù)d。 ii) 計算點Q:=dP (d個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表示

30、成一個域元素m∈Fq, iii) 在區(qū)間[1，n-1]內(nèi)選取一個隨機數(shù)k, iv) 依據(jù)Bob的公鑰計算點 (x1,y1):=kP(k個P相? ） v) 計算點(x2,y2):=kQ,如果x2=0,則回到第iii)步.,ⅵ) 計算C:=m·x2 ⅶ) 傳送加密數(shù)據(jù)(x1,y1,C)給Bobb) Bob的解密過程Bob收到Alice的密文(x1,y1,C)后，執(zhí)行 i) 使用私鑰d，計算點(x2，