轉(zhuǎn)：https://www.pediy.com/kssd/pediy06/pediy6014.htm

作者 ?：ZMWorm[CCG]?

E-Mail：zmworm@sohu.com?

主頁 ?：Http://ZMWorm.Yeah.Net/?

前言?

同RSA（Ron Rivest姥闪，Adi Shamir，Len Adleman三位天才的名字）一樣，ECC（Elliptic Curves Cryptography，橢圓曲線密碼編碼學(xué)）也屬于公開密鑰算法。目前，國內(nèi)詳細(xì)介紹ECC的公開文獻(xiàn)并不多（反正我沒有找到）。有一些簡介蝶怔，也是泛泛而談，看完后依然理解不了ECC的實質(zhì)（可能我理解力太差）兄墅。前些天我從國外網(wǎng)站找到些材料踢星，看完后對ECC似乎懵懂了。于是我想把我對ECC的認(rèn)識整理一下隙咸，與大家分享沐悦。當(dāng)然ECC博大精深，我的認(rèn)識還很膚淺五督，文章中錯誤一定不少藏否，歡迎各路高手批評指正，小弟我洗耳恭聽充包，并及時改正副签。文章將采用連載的方式，我寫好一點就貼出來一點基矮。本文主要側(cè)重理論淆储，代碼實現(xiàn)暫不涉及。這就要求你要有一點數(shù)學(xué)功底愈捅。最好你能理解RSA算法，對公開密鑰算法有一個了解慈鸠±督鳎《近世代數(shù)基礎(chǔ)》《初等數(shù)論》之類的書，最好您先翻一下青团，這對您理解本文是有幫助的譬巫。別怕，我盡量會把語言通俗些督笆，希望本文能成為學(xué)習(xí)ECC的敲門磚芦昔。?

一、從平行線談起娃肿。?

平行線咕缎，永不相交珠十。沒有人懷疑把：）不過到了近代這個結(jié)論遭到了質(zhì)疑。平行線會不會在很遠(yuǎn)很遠(yuǎn)的地方相交了凭豪？事實上沒有人見到過焙蹭。所以“平行線，永不相交”只是假設(shè)（大家想想初中學(xué)習(xí)的平行公理嫂伞，是沒有證明的）孔厉。既然可以假設(shè)平行線永不相交，也可以假設(shè)平行線在很遠(yuǎn)很遠(yuǎn)的地方相交了帖努。即平行線相交于無窮遠(yuǎn)點P∞（請大家閉上眼睛撰豺，想象一下那個無窮遠(yuǎn)點P∞，P∞是不是很虛幻拼余，其實與其說數(shù)學(xué)鍛煉人的抽象能力污桦，還不如說是鍛煉人的想象力）。給個圖幫助理解一下：?

直線上出現(xiàn)P∞點姿搜，所帶來的好處是所有的直線都相交了寡润，且只有一個交點。這就把直線的平行與相交統(tǒng)一了舅柜。為與無窮遠(yuǎn)點相區(qū)別把原來平面上的點叫做平常點梭纹。?

以下是無窮遠(yuǎn)點的幾個性質(zhì)。?

▲直線L上的無窮遠(yuǎn)點只能有一個致份。?

（從定義可直接得出）?

▲平面上一組相互平行的直線有公共的無窮遠(yuǎn)點变抽。?

（從定義可直接得出）?

▲ 平面上任何相交的兩直線L1,L2有不同的無窮遠(yuǎn)點。?

（否則L1和L2有公共的無窮遠(yuǎn)點P 氮块，則L1和L2有兩個交點A绍载、P，故假設(shè)錯誤滔蝉。）?

▲平面上全體無窮遠(yuǎn)點構(gòu)成一條無窮遠(yuǎn)直線击儡。（自己想象一下這條直線吧）?

▲平面上全體無窮遠(yuǎn)點與全體平常點構(gòu)成射影平面。?

二蝠引、射影平面坐標(biāo)系?

射影平面坐標(biāo)系是對普通平面直角坐標(biāo)系（就是我們初中學(xué)到的那個笛卡兒平面直角坐標(biāo)系）的擴展阳谍。我們知道普通平面直角坐標(biāo)系沒有為無窮遠(yuǎn)點設(shè)計坐標(biāo)，不能表示無窮遠(yuǎn)點螃概。為了表示無窮遠(yuǎn)點矫夯，產(chǎn)生了射影平面坐標(biāo)系品洛，當(dāng)然射影平面坐標(biāo)系同樣能很好的表示舊有的平常點（數(shù)學(xué)也是“向下兼容”的）宫纬。?

我們對普通平面直角坐標(biāo)系上的點A的坐標(biāo)（x,y）做如下改造：?

令x=X/Z ，y=Y/Z（Z≠0）康二；則A點可以表示為（X:Y:Z）冒窍。?

變成了有三個參量的坐標(biāo)點递沪，這就對平面上的點建立了一個新的坐標(biāo)體系豺鼻。?

? ?例2.1：求點（1,2）在新的坐標(biāo)體系下的坐標(biāo)。?

解：∵X/Z=1 区拳，Y/Z=2（Z≠0）∴X=Z拘领，Y=2Z ∴坐標(biāo)為（Z:2Z:Z），Z≠0樱调。即（1:2:1）（2:4:2）（1.2:2.4:1.2）等形如（Z:2Z:Z）约素，Z≠0的坐標(biāo)，都是（1,2）在新的坐標(biāo)體系下的坐標(biāo)笆凌。

我們也可以得到直線的方程aX+bY+cZ=0（想想為什么圣猎？提示：普通平面直角坐標(biāo)系下直線一般方程是ax+by+c=0）。新的坐標(biāo)體系能夠表示無窮遠(yuǎn)點么乞而？那要讓我們先想想無窮遠(yuǎn)點在哪里送悔。根據(jù)上一節(jié)的知識，我們知道無窮遠(yuǎn)點是兩條平行直線的交點爪模。那么欠啤，如何求兩條直線的交點坐標(biāo)？這是初中的知識屋灌，就是將兩條直線對應(yīng)的方程聯(lián)立求解洁段。平行直線的方程是：?

aX+bY+c1Z =0； aX+bY+c2Z =0 ?(c1≠c2)共郭；?

（為什么祠丝？提示：可以從斜率考慮，因為平行線斜率相同）除嘹；?

? ?將二方程聯(lián)立写半，求解。有c2Z= c1Z= -（aX+bY）尉咕，∵c1≠c2?∴Z=0 ?∴aX+bY=0叠蝇；?

所以無窮遠(yuǎn)點就是這種形式（X：Y：0）表示。注意年缎，平常點Z≠0悔捶，無窮遠(yuǎn)點Z=0，因此無窮遠(yuǎn)直線對應(yīng)的方程是Z=0晦款。?

? ?例2.2：求平行線L1：X+2Y+3Z=0 與L2：X+2Y+Z=0 相交的無窮遠(yuǎn)點炎功。?

解：因為L1∥L2 所以有Z=0枚冗， X+2Y=0缓溅；所以坐標(biāo)為（-2Y:Y:0），Y≠0赁温。即（-2:1:0）（-4:2:0）（-2.4:1.2:0）等形如（-2Y:Y:0）坛怪，Y≠0的坐標(biāo)淤齐，都表示這個無窮遠(yuǎn)點。

? ?看來這個新的坐標(biāo)體系能夠表示射影平面上所有的點袜匿，我們就把這個能夠表示射影平面上所有點的坐標(biāo)體系叫做射影平面坐標(biāo)系更啄。?

練習(xí)：?

1、求點A(2,4) 在射影平面坐標(biāo)系下的坐標(biāo)居灯。?

2祭务、求射影平面坐標(biāo)系下點(4.5:3:0.5)，在普通平面直角坐標(biāo)系下的坐標(biāo)怪嫌。?

3义锥、求直線X+Y+Z=0上無窮遠(yuǎn)點的坐標(biāo)。?

4岩灭、判斷：直線aX+bY+cZ=0上的無窮遠(yuǎn)點 和 無窮遠(yuǎn)直線與直線aX+bY=0的交點拌倍，是否是同一個點？?

三噪径、橢圓曲線?

? ?上一節(jié)柱恤，我們建立了射影平面坐標(biāo)系，這一節(jié)我們將在這個坐標(biāo)系下建立橢圓曲線方程找爱。因為我們知道梗顺，坐標(biāo)中的曲線是可以用方程來表示的（比如：單位圓方程是x2+y2=1）。橢圓曲線是曲線缴允，自然橢圓曲線也有方程荚守。?

橢圓曲線的定義：?

? ?一條橢圓曲線是在射影平面上滿足方程?

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

?----------------[3-1]?

? ?的所有點的集合，且曲線上的每個點都是非奇異（或光滑）的练般。?

定義詳解：?

? ?▲ Y2Z+a1XYZ+a3YZ2?= X3+a2X2Z+a4XZ2+a6Z3是Weierstrass方程（維爾斯特拉斯矗漾，Karl Theodor Wilhelm Weierstrass,1815-1897），是一個齊次方程薄料。?

▲ 橢圓曲線的形狀敞贡，并不是橢圓的。只是因為橢圓曲線的描述方程摄职，類似于計算一個橢圓周長的方程（計算橢圓周長的方程誊役，我沒有見過，而對橢圓線積分（設(shè)密度為1）是求不出來的谷市。誰知道這個方程蛔垢，請告訴我呀^_^），故得名迫悠。?

我們來看看橢圓曲線是什么樣的鹏漆。?

? ?▲ 所謂“非奇異”或“光滑”的，在數(shù)學(xué)中是指曲線上任意一點的偏導(dǎo)數(shù)Fx(x,y,z)，F(xiàn)y(x,y,z)艺玲，F(xiàn)z(x,y,z)不能同時為0括蝠。如果你沒有學(xué)過高等數(shù)學(xué)，可以這樣理解這個詞饭聚，即滿足方程的任意一點都存在切線忌警。?

下面兩個方程都不是橢圓曲線，盡管他們是方程[3-1]的形式秒梳。?

因為他們在（0:0:1）點處（即原點）沒有切線法绵。?

▲橢圓曲線上有一個無窮遠(yuǎn)點O∞（0:1:0），因為這個點滿足方程[3-1]酪碘。?

知道了橢圓曲線上的無窮遠(yuǎn)點礼烈。我們就可以把橢圓曲線放到普通平面直角坐標(biāo)系上了。因為普通平面直角坐標(biāo)系只比射影平面坐標(biāo)系少無窮遠(yuǎn)點婆跑。我們在普通平面直角坐標(biāo)系上此熬，求出橢圓曲線上所有平常點組成的曲線方程，再加上無窮遠(yuǎn)點O∞（0:1:0）滑进，不就構(gòu)成橢圓曲線了么犀忱？?

我們設(shè)x=X/Z ，y=Y/Z代入方程[3-1]得到：?

? ?y2+a1xy+a3y = x3+a2x2+a4x+a6?-------------------------[3-2]?

也就是說滿足方程[3-2]的光滑曲線加上一個無窮遠(yuǎn)點O∞扶关，組成了橢圓曲線阴汇。為了方便運算，表述节槐，以及理解搀庶，今后論述橢圓曲線將主要使用[3-2]的形式。?

本節(jié)的最后铜异，我們談一下求橢圓曲線一點的切線斜率問題哥倔。?

由橢圓曲線的定義可以知道，橢圓曲線是光滑的揍庄，所以橢圓曲線上的平常點都有切線咆蒿。而切線最重要的一個參數(shù)就是斜率k。?

? ?例3.1：求橢圓曲線方程y2+a1xy+a3y=x3+a2x2+a4x+a6上蚂子，平常點A(x,y)的切線的斜率k沃测。?

解：令F(x,y)= y2+a1xy+a3y-x3-a2x2-a4x-a6?

求偏導(dǎo)數(shù)?

Fx(x,y)= a1y-3x2-2a2x-a4?

Fy(x,y)= 2y+a1x +a3?

則導(dǎo)數(shù)為：f'(x)=- Fx(x,y)/ Fy(x,y)=-( a1y-3x2-2a2x-a4)/(2y+a1x +a3)?

= (3x2+2a2x+a4-a1y) /(2y+a1x +a3)?

所以k=(3x2+2a2x+a4-a1y) /(2y+a1x +a3) ?------------------------[3-3]?

看不懂解題過程沒有關(guān)系，記住結(jié)論[3-3]就可以了食茎。?

練習(xí)：?

1蒂破、將給出圖例的橢圓曲線方程Y2Z=X3-XZ2?和Y2Z=X3+XZ2+Z3轉(zhuǎn)換成普通平面直角坐標(biāo)系上的方程。?

四别渔、橢圓曲線上的加法?

上一節(jié)附迷，我們已經(jīng)看到了橢圓曲線的圖象田巴，但點與點之間好象沒有什么聯(lián)系。我們能不能建立一個類似于在實數(shù)軸上加法的運算法則呢挟秤？天才的數(shù)學(xué)家找到了這一運算法則?

☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆?

自從近世紀(jì)代數(shù)學(xué)引入了群、環(huán)抄伍、域的概念艘刚，使得代數(shù)運算達(dá)到了高度的統(tǒng)一。比如數(shù)學(xué)家總結(jié)了普通加法的主要特征截珍，提出了加群（也叫交換群攀甚，或Abel（阿貝爾）群），在加群的眼中岗喉。實數(shù)的加法和橢圓曲線的上的加法沒有什么區(qū)別秋度。這也許就是數(shù)學(xué)抽象把：）。關(guān)于群以及加群的具體概念請參考近世代數(shù)方面的數(shù)學(xué)書钱床。?

☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆?

? ?運算法則：任意取橢圓曲線上兩點P荚斯、Q （若P、Q兩點重合查牌，則做P點的切線）做直線交于橢圓曲線的另一點R’事期，過R’做y軸的平行線交于R。我們規(guī)定P+Q=R纸颜。（如圖）?

法則詳解：?

▲這里的+不是實數(shù)中普通的加法兽泣，而是從普通加法中抽象出來的加法，他具備普通加法的一些性質(zhì)胁孙，但具體的運算法則顯然與普通加法不同唠倦。?

▲根據(jù)這個法則，可以知道橢圓曲線無窮遠(yuǎn)點O∞與橢圓曲線上一點P的連線交于P’涮较，過P’作y軸的平行線交于P稠鼻，所以有 無窮遠(yuǎn)點 O∞+ P = P 。這樣狂票，無窮遠(yuǎn)點 O∞的作用與普通加法中零的作用相當(dāng)（0+2=2）枷餐，我們把無窮遠(yuǎn)點 O∞ 稱為?零元。同時我們把P’稱為P的負(fù)元（簡稱苫亦，負(fù)P毛肋；記作，-P）屋剑。（參見下圖）?

▲根據(jù)這個法則润匙，可以得到如下結(jié)論 ：如果橢圓曲線上的三個點A、B唉匾、C孕讳，處于同一條直線上匠楚，那么他們的和等于零元，即A+B+C= O∞?

? ?▲k個相同的點P相加厂财，我們記作kP芋簿。如下圖：P+P+P = 2P+P = 3P。

? ?下面璃饱，我們利用P与斤、Q點的坐標(biāo)(x1,y1)，(x2,y2)荚恶，求出R=P+Q的坐標(biāo)(x4,y4)撩穿。?

例4.1：求橢圓曲線方程y2+a1xy+a3y=x3+a2x2+a4x+a6上，平常點P(x1,y1)谒撼，Q(x2,y2)的和R(x4,y4)的坐標(biāo)食寡。?

解：（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兩點重合) 則直線為橢圓曲線的切線廓潜，故由例3.1可知：?

k=(3x2+2a2x+a4?-a1y) /(2y+a1x+a3)?

因此P,Q,-R三點的坐標(biāo)值就是方程組：?

y2+a1xy+a3y=x3+a2x2+a4x+a6?-----------------[1]?

y=(kx+b) ? ? ? ? ? ? ? ? ? ? -----------------[2]?

的解抵皱。?

將[2]，代入[1] 有?

(kx+b)2+a1x(kx+b)+a3(kx+b) =x3+a2x2+a4x+a6?--------[3]?

對[3]化為一般方程辩蛋，根據(jù)三次方程根與系數(shù)關(guān)系（當(dāng)三次項系數(shù)為1時叨叙；-x1x2x3?等于常數(shù)項系數(shù)， x1x2+x2x3+x3x1等于一次項系數(shù)堪澎，-(x1+x2+x3)等于二次項系數(shù)擂错。）?

所以-(x1+x2+x3)=a2-ka1-k2?

x3=k2+ka1+a2+x1+x2;---------------------求出點-R的橫坐標(biāo)?

因為k=(y1-y3)/(x1-x3) 故?

y3=y1-k(x1-x3);-------------------------------求出點-R的縱坐標(biāo)?

（2）利用-R求R?

顯然有 x4=x3= k2+ka1+a2+x1+x2; ------------求出點R的橫坐標(biāo)?

而y3?y4?為 x=x4時 方程y2+a1xy+a3y=x3+a2x2+a4x+a6的解?

化為一般方程y2+(a1x+a3)y-(x3+a2x2+a4x+a6)=0 , 根據(jù)二次方程根與系數(shù)關(guān)系得：?

-(a1x+a3)=y3+y4?

故y4=-y3-(a1x+a3)=k(x1-x4)-y1-(a1x4+a3); ---------------求出點R的縱坐標(biāo)?

即：?

x4=k2+ka1+a2+x1+x2;?

y4=k(x1-x4)-y1-a1x4-a3;?

? ?本節(jié)的最后，提醒大家注意一點樱蛤，以前提供的圖像可能會給大家產(chǎn)生一種錯覺钮呀，即橢圓曲線是關(guān)于x軸對稱的。事實上昨凡，橢圓曲線并不一定關(guān)于x軸對稱爽醋。如下圖的y2-xy=x3+1?

五、密碼學(xué)中的橢圓曲線?

我們現(xiàn)在基本上對橢圓曲線有了初步的認(rèn)識便脊，這是值得高興的蚂四。但請大家注意，前面學(xué)到的橢圓曲線是連續(xù)的哪痰，并不適合用于加密遂赠；所以，我們必須把橢圓曲線變成離散的點晌杰。?

讓我們想一想跷睦，為什么橢圓曲線為什么連續(xù)？是因為橢圓曲線上點的坐標(biāo)肋演，是實數(shù)的（也就是說前面講到的橢圓曲線是定義在實數(shù)域上的）抑诸，實數(shù)是連續(xù)的烂琴，導(dǎo)致了曲線的連續(xù)。因此蜕乡，我們要把橢圓曲線定義在有限域上（顧名思義奸绷，有限域是一種只有由有限個元素組成的域）。?

☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆?

域的概念是從我們的有理數(shù)层玲，實數(shù)的運算中抽象出來的号醉，嚴(yán)格的定義請參考近世代數(shù)方面的書。簡單的說称簿，域中的元素同有理數(shù)一樣，有自己得的加法惰帽、乘法憨降、除法、單位元(1)该酗，零元(0),并滿足交換率授药、分配率。?

☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆?

? ?下面呜魄，我們給出一個有限域Fp悔叽，這個域只有有限個元素。?

Fp中只有p（p為素數(shù)）個元素0,1,2 …… p-2,p-1爵嗅；?

Fp?的加法（a+b）法則是 a+b≡c (mod p)娇澎；即，(a+c)÷p的余數(shù) 和c÷p的余數(shù)相同睹晒。?

Fp?的乘法(a×b)法則是 ?a×b≡c (mod p)趟庄；?

Fp?的除法(a÷b)法則是 ?a/b≡c (mod p)；即 a×b-1≡c ?(mod p)伪很；（b-1也是一個0到p-1之間的整數(shù)戚啥，但滿足b×b-1≡1 (mod p)；具體求法可以參考初等數(shù)論锉试，或

我的另一篇文章）猫十。?

Fp?的單位元是1，零元是 0呆盖。?

? ?同時拖云，并不是所有的橢圓曲線都適合加密。y2=x3+ax+b是一類可以用來加密的橢圓曲線应又，也是最為簡單的一類江兢。下面我們就把y2=x3+ax+b 這條曲線定義在Fp上：?

選擇兩個滿足下列條件的小于p(p為素數(shù))的非負(fù)整數(shù)a、b?

4a3+27b2≠0　(mod p)?

則滿足下列方程的所有點(x,y)丁频，再加上 無窮遠(yuǎn)點O∞ 杉允，構(gòu)成一條橢圓曲線邑贴。?

y2=x3+ax+b ?(mod p)?

其中 x,y屬于0到p-1間的整數(shù)，并將這條橢圓曲線記為Ep(a,b)叔磷。?

? ?我們看一下y2=x3+x+1 ?(mod 23)的圖像?

是不是覺得不可思議拢驾？橢圓曲線，怎么變成了這般模樣改基，成了一個一個離散的點繁疤？?

? ?橢圓曲線在不同的數(shù)域中會呈現(xiàn)出不同的樣子，但其本質(zhì)仍是一條橢圓曲線秕狰。舉一個不太恰當(dāng)?shù)睦映砝埃帽仁撬诔叵旅В且后w架忌；到了零下，水就變成冰我衬，成了固體叹放；而溫度上升到一百度，水又變成了水蒸氣挠羔。但其本質(zhì)仍是H2O井仰。?

? ?Fp上的橢圓曲線同樣有加法，但已經(jīng)不能給以幾何意義的解釋破加。不過俱恶，加法法則和實數(shù)域上的差不多，請讀者自行對比范舀。?

1 無窮遠(yuǎn)點 O∞是零元速那，有O∞+ O∞= O∞，O∞+P=P?

2 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(mod p)?

y3≡k(x1-x3)-y1(mod p)?

其中若P=Q 則 k=(3x2+a)/2y1?若P≠Q(mào)端仰，則k=(y2-y1)/(x2-x1)?

例5.1 已知E23(1,1)上兩點P(3,10)，Q(9,7)田藐，求1)-P荔烧，2)P+Q，3) 2P汽久。?

解 1) ?–P的值為(3,-10)?

2) ?k=(7-10)/(9-3)=-1/2鹤竭，2的乘法逆元為12 因為2*12≡1 (mod 23)?

k≡-1*12 (mod 23) 故 k=11。?

x=112-3-9=109≡17 (mod 23);?

y=11[3-(-6)]-10=89≡20 (mod 23)?

故P+Q的坐標(biāo)為(17,20)?

3) ?k=[3(32)+1]/(2*10)=1/4≡6 (mod 23)?

x=62-3-3=30≡20 (mod 23)?

y=6(3-7)-10=-34≡12 (mod 23)?

故2P的坐標(biāo)為(7,12)?

最后景醇，我們講一下橢圓曲線上的點的階臀稚。?

如果橢圓曲線上一點P，存在最小的正整數(shù)n三痰，使得數(shù)乘nP=O∞吧寺，則將n稱為P的?階窜管，若n不存在，我們說P是無限階的稚机。?

事實上幕帆，在有限域上定義的橢圓曲線上所有的點的階n都是存在的（證明，請參考近世代數(shù)方面的書）?

練習(xí)：?

1 求出E11(1,6)上所有的點赖条。?

2 已知E11(1,6)上一點G(2,7)失乾，求2G到13G所有的值。?

六纬乍、橢圓曲線上簡單的加密/解密?

公開密鑰算法總是要基于一個數(shù)學(xué)上的難題碱茁。比如RSA 依據(jù)的是：給定兩個素數(shù)p、q 很容易相乘得到n仿贬，而對n進(jìn)行因式分解卻相對困難纽竣。那橢圓曲線上有什么難題呢？?

考慮如下等式：?

K=kG ?[其中 K,G為Ep(a,b)上的點诅蝶，k為小于n（n是點G的階）的整數(shù)]?

不難發(fā)現(xiàn)退个，給定k和G募壕，根據(jù)加法法則调炬，計算K很容易；但給定K和G舱馅，求k就相對困難了缰泡。?

這就是橢圓曲線加密算法采用的難題。我們把點G稱為基點（base point）代嗤，k（k

現(xiàn)在我們描述一個利用橢圓曲線進(jìn)行加密通信的過程：?

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

? ?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?

再對點M進(jìn)行解碼就可以得到明文傲醉。?

? ?在這個加密通信中蝇闭，如果有一個偷窺者H ，他只能看到Ep(a,b)硬毕、K呻引、G、C1吐咳、C2?而通過K逻悠、G 求k 或通過C2、G求r 都是相對困難的韭脊。因此童谒，H無法得到A、B間傳送的明文信息沪羔。?

密碼學(xué)中饥伊，描述一條Fp上的橢圓曲線，常用到六個參量：?

T=(p,a,b,G,n,h)蔫饰。?

（p 琅豆、a 、b 用來確定一條橢圓曲線篓吁，?

G為基點茫因，?

n為點G的階，?

h 是橢圓曲線上所有點的個數(shù)m與n相除的整數(shù)部分）?

這幾個參量取值的選擇杖剪，直接影響了加密的安全性冻押。參量值一般要求滿足以下幾個條件：?

1、p 當(dāng)然越大越安全摘盆，但越大翼雀，計算速度會變慢，200位左右可以滿足一般安全要求孩擂；?

2狼渊、p≠n×h；?

3、pt≠1 (mod n)狈邑，1≤t<20城须；?

4、4a3+27b2≠0 (mod p)米苹；?

5糕伐、n 為素數(shù)；?

6蘸嘶、h≤4良瞧。?

七、橢圓曲線在軟件注冊保護(hù)的應(yīng)用?

我們知道將公開密鑰算法作為軟件注冊算法的好處是Cracker很難通過跟蹤驗證算法得到注冊機训唱。下面褥蚯，將簡介一種利用Fp(a,b)橢圓曲線進(jìn)行軟件注冊的方法。?

軟件作者按如下方法制作注冊機（也可稱為簽名過程）?

1况增、選擇一條橢圓曲線Ep(a,b)赞庶，和基點G；?

2澳骤、選擇私有密鑰k（k

3歧强、產(chǎn)生一個隨機整數(shù)r（r

4、將用戶名和點R的坐標(biāo)值x,y作為參數(shù)为肮，計算SHA（Secure Hash Algorithm 安全散列算法摊册，類似于MD5）值，即Hash=SHA(username,x,y)弥锄；?

5丧靡、計算sn≡r - Hash * k (mod n)?

6蟆沫、將sn和Hash作為 用戶名username的序列號?

軟件驗證過程如下：（軟件中存有橢圓曲線Ep(a,b)籽暇，和基點G，公開密鑰K）?

1饭庞、從用戶輸入的序列號中戒悠，提取sn以及Hash；?

2舟山、計算點R≡sn*G+Hash*K ( mod p )绸狐，如果sn、Hash正確累盗，其值等于軟件作者簽名過程中點R(x,y)的坐標(biāo)寒矿，因為?

sn≡r-Hash*k （mod n）?

所以?

sn*G + Hash*K?

=(r-Hash*k)*G+Hash*K?

=rG-Hash*kG+Hash*K?

=rG- Hash*K+ Hash*K?

=rG=R ；?

3若债、將用戶名和點R的坐標(biāo)值x,y作為參數(shù)符相，計算H=SHA(username,x,y)；?

4、如果H=Hash 則注冊成功啊终。如果H≠Hash 镜豹，則注冊失敗(為什么？提示注意點R與Hash的關(guān)聯(lián)性)蓝牲。?

簡單對比一下兩個過程：?

作者簽名用到了：橢圓曲線Ep(a,b)趟脂，基點G，私有密鑰k例衍，及隨機數(shù)r昔期。?

軟件驗證用到了：橢圓曲線Ep(a,b)，基點G佛玄，公開密鑰K镇眷。?

Cracker要想制作注冊機，只能通過軟件中的Ep(a,b)翎嫡，點G欠动，公開密鑰K ，并利用K=kG這個關(guān)系獲得k后惑申，才可以具伍。而求k是很困難的。?

練習(xí)：?

下面也是一種常于軟件保護(hù)的注冊算法圈驼，請認(rèn)真閱讀人芽，并試回答簽名過程與驗證過程都用到了那些參數(shù)，Cracker想制作注冊機绩脆，應(yīng)該如何做萤厅。?

軟件作者按如下方法制作注冊機（也可稱為簽名過程）?

1、選擇一條橢圓曲線Ep(a,b)靴迫，和基點G惕味；?

2、選擇私有密鑰k（k

3玉锌、產(chǎn)生一個隨機整數(shù)r（r

4名挥、將用戶名作為參數(shù)，計算Hash=SHA(username)主守；?

5禀倔、計算 x’=x ?(mod n)?

6、計算sn≡(Hash+x’*k)/r (mod n)?

7参淫、將sn和x’作為 用戶名username的序列號?

軟件驗證過程如下：(軟件中存有橢圓曲線Ep(a,b)救湖，和基點G，公開密鑰K)?

1涎才、從用戶輸入的序列號中鞋既，提取sn以及x’；?

2、將用戶名作為參數(shù)涛救，計算Hash=SHA(username)畏邢；?

3、計算 R=(Hash*G+x’*K)/sn检吆，如果sn舒萎、Hash正確,其值等于軟件作者簽名過程中點R(x,y)，因為?

sn≡(Hash+x’*k)/r (mod n)?

所以?

(Hash*G+x’*K)/sn?

=(Hash*G+x’*K)/[(Hash+x’*k)/r]?

=(Hash*G+x’*K)/[(Hash*G+x’*k*G)/(rG)]?

=rG*[(Hash*G+x’*K)/(Hash*G+x’*K)]?

=rG=R (mod p)?

4蹭沛、v≡x (mod n)?

5臂寝、如果v=x’ 則注冊成功。如果v≠x’ 摊灭，則注冊失敗咆贬。?

八、結(jié)語?

? ?歷經(jīng)半個多月斷斷續(xù)續(xù)的寫作帚呼，這篇拙作終于算告一段落了掏缎。為寫這篇文章，我查了大量的資料煤杀，但為了使文章更通俗易懂眷蜈，我盡量避免涉及專業(yè)術(shù)語，F(xiàn)2n域上的橢圓曲線本文也沒有涉及沈自。不過酌儒，一些名詞描述的可能還不太精確，希望眾讀者對文章的問題枯途，多多批評指正忌怎。我也僅僅把這篇文章作為初稿，我會不斷修訂他的酪夷。最后感謝看雪榴啸、Sunbird、CCG以及看雪論壇所有成員對我的支持捶索，感謝一切幫助過我的人插掂，沒有你們的鼓勵灰瞻，這篇文章我是沒有動力寫完的腥例，謝謝，謝謝大家酝润！?

2003-5-3 初稿燎竖，于看雪論壇?

2004-7-11二稿，修正一張圖片

<全文完>?

主要參考文獻(xiàn)?

張禾瑞要销，《近世代數(shù)基礎(chǔ)》构回，高等教育出版社，1978?

閔嗣鶴 嚴(yán)士健，《初等數(shù)論》纤掸，高等教育出版社脐供，1982?

段云所，《網(wǎng)絡(luò)信息安全》第三講借跪，北大計算機系?

Michael Rosing 政己，chapter5《Implementing Elliptic Curve Cryptography》，Softbound掏愁，1998?

《SEC 1: Elliptic Curve Cryptography》歇由，Certicom Corp.，2000?

《IEEE P1363a / D9》果港，2001?

┌───┐ ?▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓?

│\ ? ╱│ ?▓ ?☆ ? ? ? ?ECC加密算法入門介紹 ? ? ? ? ? ★ ?▓?

│ \╱/ │ ?▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓?

│╱∨ ?│ ?▓ ?☆版權(quán)所有 ZMWorm[CCG], 轉(zhuǎn)載請保留完整性★ ?▓?

└─┴─┘ ?▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓?