免费视频淫片aa毛片_日韩高清在线亚洲专区vr_日韩大片免费观看视频播放_亚洲欧美国产精品完整版
<option id="tjmm6"><wbr id="tjmm6"></wbr></option>
<tbody id="tjmm6"><rt id="tjmm6"><pre id="tjmm6"></pre></rt></tbody>
<tr id="tjmm6"><center id="tjmm6"><tbody id="tjmm6"></tbody></center></tr>
<form id="tjmm6"></form>
打開APP
未登錄
開通VIP，暢享免費電子書等14項超值服
開通VIP
首頁
好書
留言交流
下載APP
聯(lián)系客服
ECC加密算法入門介紹
gpkinger
>《信息技術(shù)》
2006.03.24
關(guān)注
同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)系）的擴(kuò)展。我們知道普通平面直角坐標(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+c
1
Z =0； aX+bY+c
2
Z =0 (c
1
≠c
2
)；
（為什么？提示：可以從斜率考慮，因為平行線斜率相同）；
將二方程聯(lián)立，求解。有c
2
Z= c
1
Z= -（aX+bY），∵c
1
≠c
2
∴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)中的曲線是可以用方程來表示的（比如：單位圓方程是x
2
+y
2
=1）。橢圓曲線是曲線，自然橢圓曲線也有方程。
橢圓曲線的定義：
一條橢圓曲線是在射影平面上滿足方程
Y
2
Z+a
1
XYZ+a
3
YZ
2
=X
3
+a
2
X
2
Z+a
4
XZ
2
+a
6
Z
3
----------------[3-1]
的所有點的集合，且曲線上的每個點都是非奇異（或光滑）的。
定義詳解：
▲ Y
2
Z+a
1
XYZ+a
3
YZ
2
= X
3
+a
2
X
2
Z+a
4
XZ
2
+a
6
Z
3
是Weierstrass方程（維爾斯特拉斯，Karl Theodor Wilhelm Weierstrass,1815-1897），是一個齊次方程。
▲ 橢圓曲線的形狀，并不是橢圓的。只是因為橢圓曲線的描述方程，類似于計算一個橢圓周長的方程（計算橢圓周長的方程，我沒有見過，而對橢圓線積分（設(shè)密度為1）是求不出來的。誰知道這個方程，請告訴我呀^_^），故得名。
我們來看看橢圓曲線是什么樣的。
▲ 所謂“非奇異”或“光滑”的，在數(shù)學(xué)中是指曲線上任意一點的偏導(dǎo)數(shù)F
x
(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]得到：
y
2
+a
1
xy+a
3
y = x
3
+a
2
x
2
+a
4
x+a
6
-------------------------[3-2]
也就是說滿足方程[3-2]的光滑曲線加上一個無窮遠(yuǎn)點O∞，組成了橢圓曲線。為了方便運算，表述，以及理解，今后論述橢圓曲線將主要使用[3-2]的形式。
本節(jié)的最后，我們談一下求橢圓曲線一點的切線斜率問題。
由橢圓曲線的定義可以知道，橢圓曲線是光滑的，所以橢圓曲線上的平常點都有切線。而切線最重要的一個參數(shù)就是斜率k。
例3.1：求橢圓曲線方程y
2
+a
1
xy+a
3
y=x
3
+a
2
x
2
+a
4
x+a
6
上，平常點A(x,y)的切線的斜率k。
解：令F(x,y)= y
2
+a
1
xy+a
3
y-x
3
-a
2
x
2
-a
4
x-a
6
求偏導(dǎo)數(shù)
F
x
(x,y)= a
1
y-3x
2
-2a
2
x-a
4
F
y
(x,y)= 2y+a
1
x +a
3
則導(dǎo)數(shù)為：f‘(x)=- F
x
(x,y)/ F
y
(x,y)=-( a
1
y-3x
2
-2a
2
x-a
4
)/(2y+a
1
x +a
3
)
= (3x
2
+2a
2
x+a
4
-a
1
y) /(2y+a
1
x +a
3
)
所以k=(3x
2
+2a
2
x+a
4
-a
1
y) /(2y+a
1
x +a
3
) ------------------------[3-3]
看不懂解題過程沒有關(guān)系，記住結(jié)論[3-3]就可以了。
練習(xí)：
1、將給出圖例的橢圓曲線方程Y
2
Z=X
3
-XZ
2
和Y
2
Z=X
3
+XZ
2
+Z
3
轉(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)(x
1
,y
1
)，(x
2
,y
2
)，求出R=P+Q的坐標(biāo)(x
4
,y
4
)。
例4.1：求橢圓曲線方程y
2
+a
1
xy+a
3
y=x
3
+a
2
x
2
+a
4
x+a
6
上，平常點P(x
1
,y
1
)，Q(x
2
,y
2
)的和R(x
4
,y
4
)的坐標(biāo)。
解：（1）先求點-R(x
3
,y
3
)
因為P,Q,-R三點共線，故設(shè)共線方程為y=kx+b,其中
若P≠Q(mào)(P,Q兩點不重合) 則
直線斜率k=(y
1
-y
2
)/(x
1
-x
2
)
若P=Q(P,Q兩點重合) 則直線為橢圓曲線的切線，故由例3.1可知：
k=(3x
2
+2a
2
x+a
4
-a
1
y) /(2y+a
1
x+a
3
)
因此P,Q,-R三點的坐標(biāo)值就是方程組：
y
2
+a
1
xy+a
3
y=x
3
+a
2
x
2
+a
4
x+a
6
-----------------[1]
y=(kx+b) -----------------[2]
的解。
將[2]，代入[1] 有
(kx+b)
2
+a
1
x(kx+b)+a
3
(kx+b) =x
3
+a
2
x
2
+a
4
x+a
6
--------[3]
對[3]化為一般方程，根據(jù)三次方程根與系數(shù)關(guān)系（當(dāng)三次項系數(shù)為1時；-x
1
x
2
x
3
等于常數(shù)項系數(shù)， x
1
x
2
+x
2
x
3
+x
3
x
1
等于一次項系數(shù)，-(x
1
+x
2
+x
3
)等于二次項系數(shù)。）
所以-(x
1
+x
2
+x
3
)=a
2
-ka
1
-k
2
x
3
=k
2
+ka
1
+a
2
+x
1
+x
2
;---------------------求出點-R的橫坐標(biāo)
因為k=(y
1
-y
3
)/(x
1
-x
3
) 故
y
3
=y
1
-k(x
1
-x
3
);-------------------------------求出點-R的縱坐標(biāo)
（2）利用-R求R
顯然有 x
4
=x
3
= k
2
+ka
1
+a
2
+x
1
+x
2
; ------------求出點R的橫坐標(biāo)
而y
3
y
4
為 x=x
4
時 方程y
2
+a
1
xy+a
3
y=x
3
+a
2
x
2
+a
4
x+a
6
的解
化為一般方程y
2
+(a
1
x+a
3
)y-(x
3
+a
2
x
2
+a
4
x+a
6
)=0 , 根據(jù)二次方程根與系數(shù)關(guān)系得：
-(a
1
x+a
3
)=y
3
+y
4
故y
4
=-y
3
-(a
1
x+a
3
)=k(x
1
-x
4
)-y
1
-(a
1
x
4
+a
3
); ---------------求出點R的縱坐標(biāo)
即：
x
4
=k
2
+ka
1
+a
2
+x
1
+x
2
;
y
4
=k(x
1
-x
4
)-y
1
-a
1
x
4
-a
3
;
本節(jié)的最后，提醒大家注意一點，以前提供的圖像可能會給大家產(chǎn)生一種錯覺，即橢圓曲線是關(guān)于x軸對稱的。事實上，橢圓曲線并不一定關(guān)于x軸對稱。如下圖的y
2
-xy=x
3
+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),并滿足交換率、分配率。
☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
下面，我們給出一個有限域F
p
，這個域只有有限個元素。
F
p
中只有p（p為素數(shù)）個元素0,1,2 …… p-2,p-1；
F
p
的加法（a+b）法則是 a+b≡c (mod p)；即，(a+c)÷p的余數(shù) 和c÷p的余數(shù)相同。
F
p
的乘法(a×b)法則是 a×b≡c (mod p)；
F
p
的除法(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ù)論，或
我的另一篇文章
）。
F
p
的單位元是1，零元是 0。
同時，并不是所有的橢圓曲線都適合加密。y
2
=x
3
+ax+b是一類可以用來加密的橢圓曲線，也是最為簡單的一類。下面我們就把y
2
=x
3
+ax+b 這條曲線定義在F
p
上：
選擇兩個滿足下列條件的小于p(p為素數(shù))的非負(fù)整數(shù)a、b
4a
3
+27b
2
≠0 (mod p)
則滿足下列方程的所有點(x,y)，再加上 無窮遠(yuǎn)點O∞ ，構(gòu)成一條橢圓曲線。
y
2
=x
3
+ax+b (mod p)
其中 x,y屬于0到p-1間的整數(shù)，并將這條橢圓曲線記為Ep(a,b)。
我們看一下y
2
=x
3
+x+1 (mod 23)的圖像
是不是覺得不可思議？橢圓曲線，怎么變成了這般模樣，成了一個一個離散的點？
橢圓曲線在不同的數(shù)域中會呈現(xiàn)出不同的樣子，但其本質(zhì)仍是一條橢圓曲線。舉一個不太恰當(dāng)?shù)睦樱帽仁撬?，在常溫下，是液體；到了零下，水就變成冰，成了固體；而溫度上升到一百度，水又變成了水蒸氣。但其本質(zhì)仍是H
2
O。
F
p
上的橢圓曲線同樣有加法，但已經(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(x
1
,y
1
),Q(x
2
,y
2
)的和R(x
3
,y
3
) 有如下關(guān)系：
x
3
≡k
2
-x
1
-x
2
(mod p)
y
3
≡k(x
1
-x
3
)-y
1
(mod p)
其中若P=Q 則 k=(3x
2
+a)/2y
1
若P≠Q(mào)，則k=(y
2
-y
1
)/(x
2
-x
1
)
例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=11
2
-3-9=109≡17 (mod 23);
y=11[3-(-6)]-10=89≡20 (mod 23)
故P+Q的坐標(biāo)為(17,20)
3) k=[3(3
2
)+1]/(2*10)=1/4≡6 (mod 23)
x=6
2
-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 求出E
11
(1,6)上所有的點。
2 已知E
11
(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<n，n為基點G的階）稱為私有密鑰（privte key），K稱為公開密鑰（public key)。
現(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)生一個隨機(jī)整數(shù)r（r<n）。
5、用戶B計算點C
1
=M+rK；C
2
=rG。
6、用戶B將C
1
、C
2
傳給用戶A。
7、用戶A接到信息后，計算C
1
-kC
2
，結(jié)果就是點M。因為
C
1
-kC
2
=M+rK-k(rG)=M+rK-r(kG)=M
再對點M進(jìn)行解碼就可以得到明文。
在這個加密通信中，如果有一個偷窺者H ，他只能看到Ep(a,b)、K、G、C
1
、C
2
而通過K、G 求k 或通過C
2
、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、p
t
≠1 (mod n)，1≤t<20；
4、4a
3
+27b
2
≠0 (mod p)；
5、n 為素數(shù)；
6、h≤4。
七、橢圓曲線在軟件注冊保護(hù)的應(yīng)用
我們知道將公開密鑰算法作為軟件注冊算法的好處是Cracker很難通過跟蹤驗證算法得到注冊機(jī)。下面，將簡介一種利用Fp(a,b)橢圓曲線進(jìn)行軟件注冊的方法。
軟件作者按如下方法制作注冊機(jī)（也可稱為簽名過程）
1、選擇一條橢圓曲線Ep(a,b)，和基點G；
2、選擇私有密鑰k（k<n，n為G的階），利用基點G計算公開密鑰K=kG；
3、產(chǎn)生一個隨機(jī)整數(shù)r（r<n），計算點R=rG；
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，及隨機(jī)數(shù)r。
軟件驗證用到了：橢圓曲線Ep(a,b)，基點G，公開密鑰K。
Cracker要想制作注冊機(jī)，只能通過軟件中的Ep(a,b)，點G，公開密鑰K ，并利用K=kG這個關(guān)系獲得k后，才可以。而求k是很困難的。
練習(xí)：
下面也是一種常于軟件保護(hù)的注冊算法，請認(rèn)真閱讀，并試回答簽名過程與驗證過程都用到了那些參數(shù)，Cracker想制作注冊機(jī)，應(yīng)該如何做。
軟件作者按如下方法制作注冊機(jī)（也可稱為簽名過程）
1、選擇一條橢圓曲線Ep(a,b)，和基點G；
2、選擇私有密鑰k（k<n），利用基點G計算公開密鑰K=kG；
3、產(chǎn)生一個隨機(jī)整數(shù)r（r<n），計算點R(x,y)=rG；
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)
2
n域上的橢圓曲線本文也沒有涉及。不過，一些名詞描述的可能還不太精確，希望眾讀者對文章的問題，多多批評指正。我也僅僅把這篇文章作為初稿，我會不斷修訂他的。最后感謝看雪、Sunbird、CCG以及看雪論壇所有成員對我的支持，感謝一切幫助過我的人，沒有你們的鼓勵，這篇文章我是沒有動力寫完的，謝謝，謝謝大家！
2003-5-3 初稿，于看雪論壇
2004-7-11二稿，修正一張圖片
本站僅提供存儲服務(wù)，所有內(nèi)容均由用戶發(fā)布，如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請
點擊舉報
。
打開APP，閱讀全文并永久保存
查看更多類似文章
猜你喜歡
類似文章
ECC橢圓曲線詳解(有具體實例)
淺析橢圓曲線加密算法（ECC）
2011年高考分類匯編之解析幾何（四）
橢圓的參數(shù)方程
2-1第二章2.2.1橢圓方程3
高考數(shù)學(xué)解題技巧
更多類似文章 >>
生活服務(wù)
首頁
萬象
文化
人生
生活
健康
教育
職場
理財
娛樂
藝術(shù)
上網(wǎng)
留言交流
回頂部
聯(lián)系我們
分享
收藏
點擊這里，查看已保存的文章
導(dǎo)長圖
關(guān)注
一鍵復(fù)制
下載文章
綁定賬號成功
后續(xù)可登錄賬號暢享VIP特權(quán)！
如果VIP功能使用有故障，
可點擊這里聯(lián)系客服！
聯(lián)系客服
微信登錄中...
請勿關(guān)閉此頁面
先別劃走！
送你5元優(yōu)惠券，購買VIP限時立減！
5
元
優(yōu)惠券
優(yōu)惠券還有
10:00
過期
馬上使用
×
