與?RSA（Ron Rivest，Adi Shamir，Len Adleman 三位天才的名字）一樣，ECC（Elliptic Curves Cryptography，橢圓曲線加密）也屬于公開密鑰算法气忠。

一、從平行線談起

平行線赋咽，永不相交旧噪。沒有人懷疑把：）不過到了近代這個結(jié)論遭到了質(zhì)疑。平行線會不會在很遠(yuǎn)很遠(yuǎn)的地方相交了冬耿？事實(shí)上沒有人見到過舌菜。所以“平行線，永不相交”只是假設(shè)（大家想想初中學(xué)習(xí)的平行公理亦镶，是沒有證明的）日月。

既然可以假設(shè)平行線永不相交，也可以假設(shè)平行線在很遠(yuǎn)很遠(yuǎn)的地方相交了缤骨。即平行線相交于無窮遠(yuǎn)點(diǎn)P∞（請大家閉上眼睛爱咬，想象一下那個無窮遠(yuǎn)點(diǎn)P∞，P∞是不是很虛幻绊起，其實(shí)與其說數(shù)學(xué)鍛煉人的抽象能力精拟，還不如說是鍛煉人的想象力）。

給個圖幫助理解一下：

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

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

直線 L 上的無窮遠(yuǎn)點(diǎn)只能有一個萧落。（從定義可直接得出）

平面上一組相互平行的直線有公共的無窮遠(yuǎn)點(diǎn)践美。（從定義可直接得出）

平面上任何相交的兩直線 L1、L2 有不同的無窮遠(yuǎn)點(diǎn)找岖。（否則 L1 和 L2 有公共的無窮遠(yuǎn)點(diǎn) P 陨倡，則 L1 和 L2 有兩個交點(diǎn) A、P许布，故假設(shè)錯誤兴革。）

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

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

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

射影平面坐標(biāo)系是對普通平面直角坐標(biāo)系（就是我們初中學(xué)到的那個笛卡兒平面直角坐標(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）蟹地。

變成了有三個參量的坐標(biāo)點(diǎn)，這就對平面上的點(diǎn)建立了一個新的坐標(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é)的知識荚虚，我們知道無窮遠(yuǎn)點(diǎn)是兩條平行直線的交點(diǎn)。那么籍茧，如何求兩條直線的交點(diǎn)坐標(biāo)版述？這是初中的知識，就是將兩條直線對應(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)?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)點(diǎn)扁耐。

看來這個新的坐標(biāo)體系能夠表示射影平面上所有的點(diǎn)，我們就把這個能夠表示射影平面上所有點(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)铐姚，是否是同一個點(diǎn)策肝？

三、橢圓曲線

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

橢圓曲線的定義：

一條橢圓曲線是在射影平面上滿足如下方程的所有點(diǎn)的集合膘婶，且曲線上的每個點(diǎn)都是非奇異（或光滑）的。

Y2Z+a1XYZ+a3YZ2=X3+a2X2Z+a4XZ2+a6Z3???????????????? [3-1]

定義詳解：

Y2Z+a1XYZ+a3YZ2?= X3+a2X2Z+a4XZ2+a6Z3?是 Weierstrass 方程（維爾斯特拉斯蛀醉，Karl Theodor Wilhelm Weierstrass,1815-1897）悬襟，是一個齊次方程。

橢圓曲線的形狀拯刁，并不是橢圓的脊岳。只是因?yàn)闄E圓曲線的描述方程，類似于計(jì)算一個橢圓周長的方程（計(jì)算橢圓周長的方程，我沒有見過割捅，而對橢圓線積分（設(shè)密度為1）是求不出來的）奶躯，故得名。

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

所謂“非奇異”或“光滑”的嘹黔，在數(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) 不能同時為0参淹。如果你沒有學(xué)過高等數(shù)學(xué)，可以這樣理解這個詞乏悄，即滿足方程的任意一點(diǎn)都存在切線。下面兩個方程都不是橢圓曲線恳不，盡管他們是方程 [3-1] 的形式檩小，因?yàn)樗麄冊冢?:0:1）點(diǎn)處（即原點(diǎn)）沒有切線。

橢圓曲線上有一個無窮遠(yuǎn)點(diǎn)O∞（0:1:0）烟勋，因?yàn)檫@個點(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] 得到：

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

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

本節(jié)的最后彤敛，我們談一下求橢圓曲線一點(diǎn)的切線斜率問題。由橢圓曲線的定義可以知道了赌，橢圓曲線是光滑的墨榄，所以橢圓曲線上的平常點(diǎn)都有切線。而切線最重要的一個參數(shù)就是斜率 k 揍拆。

例 3.1：求橢圓曲線方程 y2+a1xy+a3y=x3+a2x2+a4x+a6上渠概，平常點(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)

所以

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)看到了橢圓曲線的圖象，但點(diǎn)與點(diǎn)之間好象沒有什么聯(lián)系雇庙。我們能不能建立一個類似于在實(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ù)這個法則，可以知道橢圓曲線無窮遠(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∞ 稱為零元。同時我們把 P’ 稱為 P 的負(fù)元（簡稱袖扛，負(fù)P砸泛；記作十籍，-P）。（參見下圖）

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

k 個相同的點(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)?P, 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)系（若方程x3＋ax2＋bx＋c=0 的三個根是 x1砚作、x2窘奏、x3，則： x1＋x2＋x3=－a葫录，x1x2＋x2x3＋x3x1=b着裹，x1x2x2=－c）

所以

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

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

因?yàn)?/p>

k=(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 時 方程 y2+a1xy+a3y=x3+a2x2+a4x+a6 的解化為一般方程 y2+(a1x+a3)y-(x3+a2x2+a4x+a6)=0 , 根據(jù)二次方程根與系數(shù)關(guān)系（如果方程 ax2＋bx＋c=0 的兩根為 x1、x2米同，那么 x1+x2=-b/a骇扇，x1x2=c/a）

得：

-(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)面粮，以前提供的圖像可能會給大家產(chǎn)生一種錯覺少孝，即橢圓曲線是關(guān)于 x 軸對稱的。事實(shí)上熬苍，橢圓曲線并不一定關(guān)于 x 軸對稱稍走。如下圖的 y2-xy=x3+1

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

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

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

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

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

Fp 中只有 p（p為素?cái)?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 為素?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) 的圖像

是不是覺得不可思議？橢圓曲線蒂教，怎么變成了這般模樣巍举，成了一個一個離散的點(diǎn)？橢圓曲線在不同的數(shù)域中會呈現(xiàn)出不同的樣子凝垛，但其本質(zhì)仍是一條橢圓曲線懊悯。舉一個不太恰當(dāng)?shù)睦樱帽仁撬纹ぃ诔叵绿糠郑且后w；到了零下剑肯，水就變成冰捧毛，成了固體；而溫度上升到一百度退子，水又變成了水蒸氣。但其本質(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)?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)

最后，我們講一下橢圓曲線上的點(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 所有的值。

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

公開密鑰算法總是要基于一個數(shù)學(xué)上的難題戳护。比如 RSA 依據(jù)的是：給定兩個素?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（key point）就是私有密鑰凫乖。

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

1确垫、用戶 A 選定一條橢圓曲線 Ep(a,b)，并取橢圓曲線上一點(diǎn)帽芽，作為基點(diǎn) G删掀。

2、用戶 A 選擇一個私有密鑰 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)生一個隨機(jī)整數(shù) r（random）。

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)?C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M?沾谜，再對點(diǎn) 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 為基點(diǎn)漓概，n 為點(diǎn) G 的階漾月，h 是橢圓曲線上所有點(diǎn)的個數(shù) m 與 n 相除的整數(shù)部分。這幾個參量取值的選擇胃珍，直接影響了加密的安全性梁肿。參量值一般要求滿足以下幾個條件：

1蜓陌、p 當(dāng)然越大越安全，但越大吩蔑，計(jì)算速度會變慢钮热，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)用

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

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

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

2、選擇私有密鑰 k械馆；

3胖眷、產(chǎn)生一個隨機(jī)整數(shù) 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 的序列號

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

1劳淆、從用戶輸入的序列號中，提取 sn 以及 Hash默赂；

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

因?yàn)?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)性）。

簡單對比一下兩個過程：

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

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

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

練習(xí)：

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

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

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

2谨敛、選擇私有密鑰 k究履；

3、產(chǎn)生一個隨機(jī)整數(shù) 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 的序列號

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

1全景、從用戶輸入的序列號中，提取 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)?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’ ，則注冊失敗扶镀。

主要參考文獻(xiàn)

張禾瑞蕴侣，《近世代數(shù)基礎(chǔ)》，高等教育出版社臭觉，1978

閔嗣鶴 嚴(yán)士健昆雀，《初等數(shù)論》，高等教育出版社蝠筑，1982

段云所忆肾，《網(wǎng)絡(luò)信息安全》第三講，北大計(jì)算機(jī)系

Michael Rosing 菱肖，chapter5《Implementing Elliptic Curve Cryptography》客冈，Softbound，1998

《SEC 1: Elliptic Curve Cryptography》稳强，Certicom Corp.场仲，2000

《IEEE P1363a / D9》，2001