五、密碼學(xué)中的橢圓曲線
我們現(xiàn)在基本上對橢圓曲線有了初步的認(rèn)識，這是值得高興的。但請大家注意，前面學(xué)到的橢圓曲線是連續(xù)的，并不適合用于加密；所以，我們必須把橢圓曲線變成離散的點。
讓我們想一想，為什么橢圓曲線為什么連續(xù)？是因為橢圓曲線上點的坐標(biāo)，是實數(shù)的（也就是說前面講到的橢圓曲線是定義在實數(shù)域上的），實數(shù)是連續(xù)的，導(dǎo)致了曲線的連續(xù)。因此，我們要把橢圓曲線定義在有限域上（顧名思義，有限域是一種只有由有限個元素組成的域）。
域的概念是從我們的有理數(shù)，實數(shù)的運算中抽象出來的，嚴(yán)格的定義請參考近世代數(shù)方面的數(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ù)睦樱帽仁撬?，在常溫下，是液體；到了零下，水就變成冰，成了固體；而溫度上升到一百度，水又變成了水蒸氣。但其本質(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所有的值。
我們現(xiàn)在基本上對橢圓曲線有了初步的認(rèn)識，這是值得高興的。但請大家注意，前面學(xué)到的橢圓曲線是連續(xù)的，并不適合用于加密；所以，我們必須把橢圓曲線變成離散的點。
讓我們想一想，為什么橢圓曲線為什么連續(xù)？是因為橢圓曲線上點的坐標(biāo)，是實數(shù)的（也就是說前面講到的橢圓曲線是定義在實數(shù)域上的），實數(shù)是連續(xù)的，導(dǎo)致了曲線的連續(xù)。因此，我們要把橢圓曲線定義在有限域上（顧名思義，有限域是一種只有由有限個元素組成的域）。
域的概念是從我們的有理數(shù)，實數(shù)的運算中抽象出來的，嚴(yán)格的定義請參考近世代數(shù)方面的數(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ù)睦樱帽仁撬?，在常溫下，是液體；到了零下，水就變成冰，成了固體；而溫度上升到一百度，水又變成了水蒸氣。但其本質(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所有的值。