第九章橢圓曲線

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

；l=(a,b,c)T注意：P=sPl=sl第六頁，共二十三頁，編輯于2023年，星期四9.1射影幾何——齊次坐標(biāo)齊次坐標(biāo)表示無窮遠(yuǎn)點(diǎn)

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

所以無窮遠(yuǎn)點(diǎn)：

（X：Y：0）

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

因?yàn)椋?kx+b)2+a1x(kx+b)+a3(kx+b)=x3+a2x2+a4x+a6

當(dāng)三次項(xiàng)系數(shù)為1時(shí)；-x1x2x3

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

第十五頁，共二十三頁，編輯于2023年，星期四9.3橢圓曲線的加法原理定理9-1P(x1,y1)，Q(x2,y2)，R=P+Q的坐標(biāo)？（2）利用-R求R顯然有x4=x3=k2+ka1+a2+x1+x2y3y4

為x=x4

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

第十六頁，共二十三頁，編輯于2023年，星期四

P

-P

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

第十七頁，共二十三頁，編輯于2023年，星期四9.4密碼學(xué)中的橢圓曲線Fp上的橢圓曲線的加法1.無窮遠(yuǎn)點(diǎn)O∞是零元，有O∞+O∞=O∞，O∞+P=P2.P(x,y)的負(fù)元是(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)第十八頁，共二十三頁，編輯于2023年，星期四9.4密碼學(xué)中的橢圓曲線橢圓曲線上簡單的加密/解密K=kG

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

8、再對(duì)點(diǎn)M進(jìn)行解碼就可以得到明文。第二十頁，共二十三頁，編輯于2023年，星期四9.4密碼學(xué)中的橢圓曲線密碼學(xué)中，描述一條Fp上的橢圓曲線，常用到六個(gè)參量：

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