四、橢圓曲線上的加法

上一節，我們已經看到了橢圓曲線的圖象，但點與點之間好象沒有什么聯系。我們能不能建立一個類似于在實數軸上加法的運算法則呢？天才的數學家找到了這一運算法則

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

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

法則詳解：

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

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

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

：

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

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

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

解：(1)先求點-R(x3,y3)

因為P,Q,-R三點共線，故設共線方程為y=kx+b,其中

若P≠Q(P,Q兩點不重合) 則

直線斜率k=(y1-y2)/(x1-x2)

若P=Q(P,Q兩點重合) 則直線為橢圓曲線的切線，故由例3.1可知：

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

因此P,Q,-R三點的坐標值就是方程組：

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]化為一般方程，根據三次方程根與系數關系(當三次項系數為1時；-x1x2x3 等于常數項系數， x1x2+x2x3+x3x1等于一次項系數，-(x1+x2+x3)等于二次項系數。)

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

x3=k2+ka1+a2+x1+x2;---------------------求出點-R的橫坐標

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

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

(2)利用-R求R

顯然有 x4=x3= k2+ka1+a2+x1+x2; ------------求出點R的橫坐標

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

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

-(a1x+a3)=y3+y4

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

即：

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

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

本節的最后，提醒大家注意一點，以前提供的圖像可能會給大家產生一種錯覺，即橢圓曲線是關于x軸對稱的。事實上，橢圓曲線并不一定關于x軸對稱。如下圖的y2-xy=x3+1

：

五、密碼學中的橢圓曲線

我們現在基本上對橢圓曲線有了初步的認識，這是值得高興的。但請大家注意，前面學到的橢圓曲線是連續的，并不適合用于加密；所以，我們必須把橢圓曲線變成離散的點。

讓我們想一想，為什么橢圓曲線為什么連續？是因為橢圓曲線上點的坐標，是實數的(也就是說前面講到的橢圓曲線是定義在實數域上的)，實數是連續的，導致了曲線的連續。因此，我們要把橢圓曲線定義在有限域上(顧名思義，有限域是一種只有由有限個元素組成的域)。

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

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

Fp中只有p(p為素數)個元素0,1,2 …… p-2,p-1；

Fp 的加法(a+b)法則是 a+b≡c (mod p)；即，(a+c)÷p的余數 和c÷p的余數相同。

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之間的整數，但滿足b×b-1≡1 (mod p)；具體求法可以參考初等數論，或我的另一篇文章)。

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

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

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

4a3+27b2≠0　(mod p)

則滿足下列方程的所有點(x,y)，再加上 無窮遠點O∞ ，構成一條橢圓曲線。

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

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

：

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

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

橢圓曲線在不同的數域中會呈現出不同的樣子，但其本質仍是一條橢圓曲線。舉一個不太恰當的例子，好比是水，在常溫下，是液體；到了零下，水就變成冰，成了固體；而溫度上升到一百度，水又變成了水蒸氣。但其本質仍是H2O。

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

1. 無窮遠點 O∞是零元，有O∞+ O∞= O∞，O∞+P=P

2. P(x,y)的負元是 (x,-y)，有P+(-P)= O∞

3. P(x1,y1),Q(x2,y2)的和R(x3,y3) 有如下關系：

x3≡k2-x1-x2(mod p)

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

其中若P=Q 則 k=(3x2+a)/2y1? 若P≠Q，則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的坐標為(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的坐標為(7,12)

最后，我們講一下橢圓曲線上的點的階。

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

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

練習：

1． 求出E11(1,6)上所有的點。

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

總結

以上是生活随笔為你收集整理的椭圆曲线图像加密 matlab,椭圆曲线ECC加密算法入门介绍（三、四）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。