轉(zhuǎn)：https://blog.csdn.net/qq_30866297/article/details/51175305

SM2橢圓曲線公鑰密碼算法本身是基于ECC橢圓曲線算法的，所以要搞sm2, 先要弄懂ECC。

這里學(xué)習(xí)ECC橢圓曲線算法，主要參考了一位前輩的技術(shù)博客，網(wǎng)名為ZMWorm 的大牛在多年前寫的《橢圓曲線ECC加密算法入門介紹》。

在此特別注明出處：

作者 ?：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的實(shí)質(zhì)（可能我理解力太差）。前些天我從國外網(wǎng)站找到些材料，看完后對ECC似乎懵懂了。于是我想把我對ECC的認(rèn)識(shí)整理一下，與大家分享。當(dāng)然ECC博大精深，我的認(rèn)識(shí)還很膚淺，文章中錯(cuò)誤一定不少，歡迎各路高手批評指正，小弟我洗耳恭聽，并及時(shí)改正。文章將采用連載的方式，我寫好一點(diǎn)就貼出來一點(diǎn)。本文主要側(cè)重理論，代碼實(shí)現(xiàn)暫不涉及。這就要求你要有一點(diǎn)數(shù)學(xué)功底。最好你能理解RSA算法，對公開密鑰算法有一個(gè)了解。《近世代數(shù)基礎(chǔ)》《初等數(shù)論》之類的書，最好您先翻一下，這對您理解本文是有幫助的。別怕，我盡量會(huì)把語言通俗些，希望本文能成為學(xué)習(xí)ECC的敲門磚。

一、從平行線談起。

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

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

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

▲直線L上的無窮遠(yuǎn)點(diǎn)只能有一個(gè)。

（從定義可直接得出）

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

（從定義可直接得出）

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

（否則L1和L2有公共的無窮遠(yuǎn)點(diǎn)P ，則L1和L2有兩個(gè)交點(diǎn)A、P，故假設(shè)錯(cuò)誤。）

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

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

我的補(bǔ)充：

無窮遠(yuǎn)點(diǎn)：射影幾何中直線只有有一個(gè)無窮遠(yuǎn)點(diǎn)就是無窮遠(yuǎn)點(diǎn)，直線的兩端交于無窮遠(yuǎn)點(diǎn)（可把直線看作封閉曲線），.兩條平行的直線可以看作相交在無窮遠(yuǎn)點(diǎn)，所有的平行直線都交于同一個(gè)無窮遠(yuǎn)點(diǎn)。

無窮遠(yuǎn)直線：無窮遠(yuǎn)直線亦稱假直線或理想直線.指歐氏平面上的一條假想直線，它是平面上所有直線上的無窮遠(yuǎn)點(diǎn)的集合.為了區(qū)別起見，平面內(nèi)原有的直線稱為有窮直線、真直線或普通直線.在平面上引進(jìn)無窮遠(yuǎn)直線以后，空間中每兩個(gè)平面都有交線一組平行的平面相交于屬于諸平行平面的一條無窮遠(yuǎn)直線。

射影平面：2維射影空間。它可以視為平面添上一條無窮遠(yuǎn)直線， 它是代數(shù)幾何、射影幾何里最基本的對象。

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

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

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

令x=X/Z ，y=Y/Z（Z≠0）；則A點(diǎn)可以表示為（X:Y:Z）。

變成了有三個(gè)參量的坐標(biāo)點(diǎn)，這就對平面上的點(diǎn)建立了一個(gè)新的坐標(biāo)體系。

例2.1：求點(diǎn)（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)點(diǎn)么？那要讓我們先想想無窮遠(yuǎn)點(diǎn)在哪里。根據(jù)上一節(jié)的知識(shí)，我們知道無窮遠(yuǎn)點(diǎn)是兩條平行直線的交點(diǎn)。那么，如何求兩條直線的交點(diǎn)坐標(biāo)？這是初中的知識(shí)，就是將兩條直線對應(yīng)的方程聯(lián)立求解。平行直線的方程是：aX+bY+c1Z =0； aX+bY+c2Z =0 ?(c1≠c2)；（為什么？提示：可以從斜率考慮，因?yàn)槠叫芯€斜率相同）。將二方程聯(lián)立，求解。有c2Z= c1Z= -（aX+bY），∵c1≠c2 ∴Z=0 ?∴aX+bY=0；所以無窮遠(yuǎn)點(diǎn)就是這種形式（X：Y：0）表示。注意，平常點(diǎn)Z≠0，無窮遠(yuǎn)點(diǎn)Z=0，因此無窮遠(yuǎn)直線對應(yīng)的方程是Z=0。

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

解：因?yàn)長1∥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)，都表示這個(gè)無窮遠(yuǎn)點(diǎn)。

看來這個(gè)新的坐標(biāo)體系能夠表示射影平面上所有的點(diǎn)，我們就把這個(gè)能夠表示射影平面上所有點(diǎn)的坐標(biāo)體系叫做射影平面坐標(biāo)系。

練習(xí)：

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

2、求射影平面坐標(biāo)系下點(diǎn)(4.5:3:0.5)，在普通平面直角坐標(biāo)系下的坐標(biāo)。

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

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

三、橢圓曲線

上一節(jié)，我們建立了射影平面坐標(biāo)系，這一節(jié)我們將在這個(gè)坐標(biāo)系下建立橢圓曲線方程。因?yàn)槲覀冎?，坐?biāo)中的曲線是可以用方程來表示的（比如：單位圓方程是x2+y2=1）。橢圓曲線是曲線，自然橢圓曲線也有方程。

橢圓曲線的定義：

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

的所有點(diǎn)的集合，且曲線上的每個(gè)點(diǎn)都是非奇異（或光滑）的。

定義詳解：

▲ [3-1]是Weierstrass方程（維爾斯特拉斯，Karl Theodor Wilhelm Weierstrass,1815-1897），是一個(gè)齊次方程。

▲ 橢圓曲線的形狀，并不是橢圓的。只是因?yàn)闄E圓曲線的描述方程，類似于計(jì)算一個(gè)橢圓周長的方程（計(jì)算橢圓周長的方程，我沒有見過，而對橢圓線積分（設(shè)密度為1）是求不出來的。誰知道這個(gè)方程，請告訴我呀^_^），故得名。

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

▲ 所謂“非奇異”或“光滑”的，在數(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。如果你沒有學(xué)過高等數(shù)學(xué)，可以這樣理解這個(gè)詞，即滿足方程的任意一點(diǎn)都存在切線。

下面兩個(gè)方程都不是橢圓曲線，盡管他們是方程[3-1]的形式。

因?yàn)樗麄冊冢?:0:1）點(diǎn)處（即原點(diǎn)）沒有切線。

▲橢圓曲線上有一個(gè)無窮遠(yuǎn)點(diǎn)O∞（0:1:0），因?yàn)檫@個(gè)點(diǎn)滿足方程[3-1]。

知道了橢圓曲線上的無窮遠(yuǎn)點(diǎn)。我們就可以把橢圓曲線放到普通平面直角坐標(biāo)系上了。因?yàn)槠胀ㄆ矫嬷苯亲鴺?biāo)系只比射影平面坐標(biāo)系少無窮遠(yuǎn)點(diǎn)。我們在普通平面直角坐標(biāo)系上，求出橢圓曲線上所有平常點(diǎn)組成的曲線方程，再加上無窮遠(yuǎn)點(diǎn)O∞（0:1:0），不就構(gòu)成橢圓曲線了么？

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

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

本節(jié)的最后，我們談一下求橢圓曲線一點(diǎn)的切線斜率問題。

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

例3.1：求橢圓曲線方程[3-2]上，平常點(diǎn)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)

所以

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

練習(xí)：

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

四、橢圓曲線上的加法

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

☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆

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

☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆

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

法則詳解：

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

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

▲根據(jù)這個(gè)法則，可以得到如下結(jié)論 ：如果橢圓曲線上的三個(gè)點(diǎn)A、B、C，處于同一條直線上，那么他們的和等于零元，即A+B+C= O∞

▲k個(gè)相同的點(diǎn)P相加，我們記作kP。如下圖：P+P+P = 2P+P = 3P。

下面，我們利用P、Q點(diǎn)的坐標(biāo)(x1,y1)，(x2,y2)，求出R=P+Q的坐標(biāo)(x4,y4)。

例4.1：求橢圓曲線方程y2+a1xy+a3y=x3+a2x2+a4x+a6上，平常點(diǎn)P(x1,y1)，Q(x2,y2)的和R(x4,y4)的坐標(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)重合) 則直線為橢圓曲線的切線，故由例3.1可知：

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

因此P,Q,-R三點(diǎn)的坐標(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)三次項(xiàng)系數(shù)為1時(shí)；-x1x2x3 等于常數(shù)項(xiàng)系數(shù)， x1x2+x2x3+x3x1等于一次項(xiàng)系數(shù)，-(x1+x2+x3)等于二次項(xiàng)系數(shù)。）

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

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

因?yàn)閗=(y1-y3)/(x1-x3) 故

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

（2）利用-R求R

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

而y3 y4 為 x=x4時(shí) 方程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); —————求出點(diǎn)R的縱坐標(biāo)

即：

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

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

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

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

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

讓我們想一想，為什么橢圓曲線為什么連續(xù)？是因?yàn)闄E圓曲線上點(diǎn)的坐標(biāo)，是實(shí)數(shù)的（也就是說前面講到的橢圓曲線是定義在實(shí)數(shù)域上的），實(shí)數(shù)是連續(xù)的，導(dǎo)致了曲線的連續(xù)。因此，我們要把橢圓曲線定義在有限域上（顧名思義，有限域是一種只有由有限個(gè)元素組成的域）。

☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆

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

☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆

下面，我們給出一個(gè)有限域Fp，這個(gè)域只有有限個(gè)元素。

Fp中只有p（p為素?cái)?shù)）個(gè)元素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也是一個(gè)0到p-1之間的整數(shù)，但滿足b×b-1≡1 (mod p)；具體求法可以參考初等數(shù)論，或我的另一篇文章）。

Fp 的單位元是1，零元是 0。

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

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

4a3+27b2≠0　(mod p)

則滿足下列方程的所有點(diǎn)(x,y)，再加上 無窮遠(yuǎn)點(diǎ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)的圖像

是不是覺得不可思議？橢圓曲線，怎么變成了這般模樣，成了一個(gè)一個(gè)離散的點(diǎn)？

橢圓曲線在不同的數(shù)域中會(huì)呈現(xiàn)出不同的樣子，但其本質(zhì)仍是一條橢圓曲線。舉一個(gè)不太恰當(dāng)?shù)睦?，好比是水，在常溫下，是液體；到了零下，水就變成冰，成了固體；而溫度上升到一百度，水又變成了水蒸氣。但其本質(zhì)仍是H2O。

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

1 無窮遠(yuǎn)點(diǎ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)上兩點(diǎn)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 因?yàn)?*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)

最后，我們講一下橢圓曲線上的點(diǎn)的階。

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

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

練習(xí)：

1 求出E11(1,6)上所有的點(diǎn)。

2 已知E11(1,6)上一點(diǎn)G(2,7)，求2G到13G所有的值。

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

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

考慮如下等式：

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

不難發(fā)現(xiàn)，給定k和G，根據(jù)加法法則，計(jì)算K很容易；但給定K和G，求k就相對困難了。

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

現(xiàn)在我們描述一個(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

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)?/p>

C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M

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

在這個(gè)加密通信中，如果有一個(gè)偷窺者H ，他只能看到Ep(a,b)、K、G、C1、C2 而通過K、G 求k 或通過C2、G求r 都是相對困難的。因此，H無法得到A、B間傳送的明文信息。

密碼學(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ù)部分）

這幾個(gè)參量取值的選擇，直接影響了加密的安全性。參量值一般要求滿足以下幾個(gè)條件：

1、p 當(dāng)然越大越安全，但越大，計(jì)算速度會(huì)變慢，200位左右可以滿足一般安全要求；

2、p≠n×h；

3、pt≠1 (mod n)，1≤t<20；

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

5、n 為素?cái)?shù)；

6、h≤4。

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

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

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

注冊機(jī)：注冊機(jī)分為內(nèi)部注冊機(jī)和外部注冊機(jī)二種，內(nèi)部注冊機(jī)又稱內(nèi)存注冊機(jī)，外部注冊機(jī)又稱算法注冊機(jī)。它們破解軟件注冊信息的過程不盡相同，但結(jié)果是一樣的。

內(nèi)存注冊機(jī)

就是利用內(nèi)存注冊機(jī)駐留在內(nèi)存里，當(dāng)你運(yùn)行軟件時(shí)，注冊機(jī)攔截軟件有關(guān)進(jìn)程，達(dá)到無限制使用該軟件的目的。此類軟件的注冊方法是由注冊機(jī)程序從內(nèi)存中提取注冊碼，然后把注冊碼復(fù)制到注冊對話框中。一般需要把注冊機(jī)程序拷貝到軟件的運(yùn)行目錄下，第一次直接運(yùn)行注冊機(jī)程序，這時(shí)原程序會(huì)開始啟動(dòng)，在注冊對話框中輸入任意字符進(jìn)行注冊，這時(shí)注冊機(jī)程序會(huì)自動(dòng)找到正確的注冊碼并顯示出來，選中復(fù)制后點(diǎn)確定，原注冊對話框會(huì)提示錯(cuò)誤信息。再次進(jìn)行注冊時(shí)把正確的注冊碼粘貼進(jìn)去進(jìn)行注冊即可。內(nèi)部注冊機(jī)在使用時(shí)需導(dǎo)入原程序文件安裝目錄下，點(diǎn)擊后自動(dòng)運(yùn)行，完成破解原程序文件的注冊信息，破解成功后，該軟件就搖身變成了已注冊的正式版軟件了，可以像使用其他正式版軟件一樣，使用其全部功能。?

算法注冊機(jī)

是指根據(jù)軟件反匯編得出來的注冊算法，然后使用編程語言寫出來的程序。它的功能是通過用戶提供的注冊序列號(hào)、注冊名或者機(jī)器碼等去計(jì)算出軟件的注冊碼或注冊序列號(hào)來，然后你再把注冊機(jī)算出的序列號(hào)填入原程序文件注冊序列號(hào)欄中，即完成注冊。。外部注冊機(jī)在使用時(shí)，不需導(dǎo)入原程序文件的安裝目錄下，可以存放在硬盤任何位置。

內(nèi)部注冊機(jī)的版本必須與所要破解的原文件版相一致，否則不能起到破解作用。外部注冊機(jī)有些（通用版）是可以通用的。

1、選擇一條橢圓曲線Ep(a,b)，和基點(diǎn)G；

2、選擇私有密鑰k（k

3、產(chǎn)生一個(gè)隨機(jī)整數(shù)r（r

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

5、計(jì)算sn≡r – Hash * k (mod n)

6、將sn和Hash作為 用戶名username的序列號(hào)

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

1、從用戶輸入的序列號(hào)中，提取sn以及Hash；

2、計(jì)算點(diǎn)R≡sn*G+Hash*K ( mod p )，如果sn、Hash正確，其值等于軟件作者簽名過程中點(diǎn)R(x,y)的坐標(biāo)，因?yàn)?/p>

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、將用戶名和點(diǎn)R的坐標(biāo)值x,y作為參數(shù)，計(jì)算H=SHA(username,x,y)；

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

簡單對比一下兩個(gè)過程：

作者簽名用到了：橢圓曲線Ep(a,b)，基點(diǎn)G，私有密鑰k，及隨機(jī)數(shù)r。

軟件驗(yàn)證用到了：橢圓曲線Ep(a,b)，基點(diǎn)G，公開密鑰K。

Cracker要想制作注冊機(jī)，只能通過軟件中的Ep(a,b)，點(diǎn)G，公開密鑰K ，并利用K=kG這個(gè)關(guān)系獲得k后，才可以。而求k是很困難的。

練習(xí)：

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

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

1、選擇一條橢圓曲線Ep(a,b)，和基點(diǎn)G；

2、選擇私有密鑰k（k

3、產(chǎn)生一個(gè)隨機(jī)整數(shù)r（r

4、將用戶名作為參數(shù)，計(jì)算Hash=SHA(username)；

5、計(jì)算 x’=x ?(mod n)

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

7、將sn和x’作為 用戶名username的序列號(hào)

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

1、從用戶輸入的序列號(hào)中，提取sn以及x’；

2、將用戶名作為參數(shù)，計(jì)算Hash=SHA(username)；

3、計(jì)算 R=(Hash*G+x’*K)/sn，如果sn、Hash正確,其值等于軟件作者簽名過程中點(diǎn)R(x,y)，因?yàn)?/p>

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)半個(gè)多月斷斷續(xù)續(xù)的寫作，這篇拙作終于算告一段落了。為寫這篇文章，我查了大量的資料，但為了使文章更通俗易懂，我盡量避免涉及專業(yè)術(shù)語，F(xiàn)2n域上的橢圓曲線本文也沒有涉及。不過，一些名詞描述的可能還不太精確，希望眾讀者對文章的問題，多多批評指正。我也僅僅把這篇文章作為初稿，我會(huì)不斷修訂他的。最后感謝看雪、Sunbird、CCG以及看雪論壇所有成員對我的支持，感謝一切幫助過我的人，沒有你們的鼓勵(lì)，這篇文章我是沒有動(dòng)力寫完的，謝謝，謝謝大家！

---------------------本文來自 qq_30866297 的CSDN 博客 ，全文地址請點(diǎn)擊：https://blog.csdn.net/qq_30866297/article/details/51175305?utm_source=copy