第九章橢圓曲線

第九章橢圓曲線第1頁，共23頁，2023年，2月20日，星期三9.0簡介1985年N.Koblitz及V.S.Miller分別提出用于加密、數(shù)字簽名、密鑰交換、大數(shù)分解、之樹判斷等相同安全強度下，密鑰比其他公鑰系統(tǒng)（如RSA）小，且快第2頁，共23頁，2023年，2月20日，星期三9.1射影幾何——無窮遠點射影幾何與透視學(xué)十七世紀真正成為幾何學(xué)的重要分支非歐幾何：歐幾里得第五公設(shè)開普勒引入無窮遠點把直線的平行與相交統(tǒng)一經(jīng)過同一無窮遠點的所有直線平行一條直線的無窮遠點只有一個，相交直線的無窮遠點不同平面上全體無窮遠點構(gòu)成一條無窮遠直線。平面上全體無窮遠點與全體平常點構(gòu)成射影平面。第3頁，共23頁，2023年，2月20日，星期三9.1射影幾何——無窮遠點十七世紀真正成為幾何學(xué)的重要分支中心射影和平行射影兩者就可以統(tǒng)一了凡是利用中心投影或者平行投影把一個圖形映成另一個圖形的映射，就叫做射影變換。概括的說，射影幾何學(xué)是幾何學(xué)的一個重要分支學(xué)科，它是專門研究圖形的位置關(guān)系的，也是專門用來討論在把點投影到直線或者平面上的時候，圖形的不變性質(zhì)的科學(xué)。第4頁，共23頁，2023年，2月20日，星期三9.1射影幾何——齊次坐標射影平面坐標系笛卡兒平面直角坐標系的擴展問題：如何表示無窮遠點？引入?yún)?shù)，區(qū)分無窮遠點和平常點第5頁，共23頁，2023年，2月20日，星期三9.1射影幾何——齊次坐標歐氏坐標表示一個點P=(x,y)T表示一條直線l:ax+by+c=0l=(a,b,c)T引入taxz+byz+cz=0齊次坐標：P=(xz,yz,z)T

；l=(a,b,c)T注意：P=sPl=sl第6頁，共23頁，2023年，2月20日，星期三9.1射影幾何——齊次坐標齊次坐標表示無窮遠點

平行直線方程：aX+bY+c1Z=0；aX+bY+c2Z=0有c2Z=c1Z=-（aX+bY），∵c1≠c2∴Z=0

所以無窮遠點：

（X：Y：0）

第7頁，共23頁，2023年，2月20日，星期三9.2橢圓曲線定義射影平面坐標系下建立一條橢圓曲線是在射影平面上滿足方程的所有點的集合，且曲線上的每個點都是非奇異（或光滑）的。第8頁，共23頁，2023年，2月20日，星期三9.2橢圓曲線定義注意：橢圓曲線的形狀，并不是橢圓的第9頁，共23頁，2023年，2月20日，星期三9.2橢圓曲線定義注意：所謂“非奇異”或“光滑”的，在數(shù)學(xué)中是指曲線上任意一點的偏導(dǎo)數(shù)Fx(x,y,z)，F(xiàn)y(x,y,z)，F(xiàn)z(x,y,z)不能同時為0可以這樣理解這個詞，即滿足方程的任意一點都存在切線。右邊不是橢圓曲線第10頁，共23頁，2023年，2月20日，星期三9.2橢圓曲線定義注意：橢圓曲線并不一定關(guān)于x軸對稱第11頁，共23頁，2023年，2月20日，星期三9.2橢圓曲線定義注意橢圓曲線上有無窮遠點O∞可以把橢圓曲線放到普通平面直角坐標系這條光滑曲線加上一個無窮遠點O∞，組成了橢圓曲線威爾斯特拉斯（weierstrass）方程第12頁，共23頁，2023年，2月20日，星期三9.3橢圓曲線的加法原理運算法則：任意取橢圓曲線E上兩點P、Q（若P、Q兩點重合，則做P點的切線）做直線交于橢圓曲線的另一點R’，過R’做y軸的平行線交于R。我們規(guī)定P+Q=R第13頁，共23頁，2023年，2月20日，星期三9.3橢圓曲線的加法原理（E,+）構(gòu)成交換群封閉單位元：P+e=Pe=O∞，即零元逆元：P+(-P)=e交換律：P+Q=Q+P結(jié)合律：P+Q+T=P+(Q+T)如果橢圓曲線上的三個點A、B、C，處于同一條直線上，那么他們的和等于零元，即A+B+C=O∞第14頁，共23頁，2023年，2月20日，星期三9.3橢圓曲線的加法原理定理9-1P(x1,y1)，Q(x2,y2)，R=P+Q的坐標？（1）先求點-R(x3,y3)因為P,Q,-R三點共線，故設(shè)共線方程為y=kx+b,其中若P≠Q(mào)(P,Q兩點不重合)則直線斜率k=(y1-y2)/(x1-x2)若P=Q(P,Q兩點重合)則直線為橢圓曲線的切線，k=(3x2+2a2x+a4-a1y)/(2y+a1x+a3)

因為：(kx+b)2+a1x(kx+b)+a3(kx+b)=x3+a2x2+a4x+a6

當三次項系數(shù)為1時；-x1x2x3

等于常數(shù)項系數(shù)，x1x2+x2x3+x3x1等于一次項系數(shù)，-(x1+x2+x3)等于二次項系數(shù)。所以x3=k2+ka1+a2+x1+x2;y3=y1-k(x1-x3);

第15頁，共23頁，2023年，2月20日，星期三9.3橢圓曲線的加法原理定理9-1P(x1,y1)，Q(x2,y2)，R=P+Q的坐標？（2）利用-R求R顯然有x4=x3=k2+ka1+a2+x1+x2y3y4

為x=x4

的解故y4=-y3-(a1x+a3)=k(x1-x4)-y1-(a1x4+a3);

第16頁，共23頁，2023年，2月20日，星期三

P

-P

QP+Q9.4密碼學(xué)中的橢圓曲線把橢圓曲線定義在有限域上：離散并不是所有的橢圓曲線都適合加密

第17頁，共23頁，2023年，2月20日，星期三9.4密碼學(xué)中的橢圓曲線Fp上的橢圓曲線的加法1.無窮遠點O∞是零元，有O∞+O∞=O∞，O∞+P=P2.P(x,y)的負元是(x,-y)，有P+(-P)=O∞3.P(x1,y1),Q(x2,y2)的和R(x3,y3)有如下關(guān)系

x3≡k2-x1-x2(modp)

y3≡k(x1-x3)-y1(modp)

其中若P=Q則k=(3x2+a)/2y1

若P≠Q(mào)，則k=(y2-y1)/(x2-x1)第18頁，共23頁，2023年，2月20日，星期三9.4密碼學(xué)中的橢圓曲線橢圓曲線上簡單的加密/解密K=kG

[其中K,G為Ep(a,b)上的點，k為小于n（n是點G的階）的整數(shù)]給定k和G，根據(jù)加法法則，計算K很容易；但給定K和G，求k就相對困難了。這就是橢圓曲線加密算法采用的難題。把點G稱為基點（basepoint）k（k<n，n為基點G的階）為私鑰；K稱為公鑰。第19頁，共23頁，2023年，2月20日，星期三9.4密碼學(xué)中的橢圓曲線下面是一個利用橢圓曲線進行加密通信的過程：1、用戶A選定一條橢圓曲線Ep(a,b)，并取橢圓曲線上一點，作為基點G。2、用戶A選擇一個私有密鑰k，并生成公開密鑰K=kG。3、用戶A將Ep(a,b)和點K，G傳給用戶B。4、用戶B接到信息后，將待傳輸?shù)拿魑木幋a到Ep(a,b)上一點M，并產(chǎn)生一個隨機整數(shù)r（r<n）。5、用戶B計算點C1=M+rK；C2=rG。6、用戶B將C1、C2傳給用戶A。7、用戶A接到信息后，計算C1-kC2，結(jié)果就是點M。因為C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M

8、再對點M進行解碼就可以得到明文。第20頁，共23頁，2023年，2月20日，星期三9.4密碼學(xué)中的橢圓曲線密碼學(xué)中，描述一條Fp上的橢圓曲線，常用到六個參量：

T=(p,a,b,G,n,h)。p、a、b用來確定一條橢圓曲線，G為基點，n為點G的階，h是橢圓曲線上所有點的個數(shù)m與n相除的整數(shù)部分第21頁，共23頁，2023年，2月20日，星期三9.4密碼學(xué)中的橢圓曲線參量取值的選擇，直接影響了加密的安全性。參量值一般要求滿足以下幾個條件：1、p當然越大越安全，但越大，計算速度會變慢，200位左右可以滿足一般安全要求；2、p≠n×h；3、pt≠1(modn)，1≤