曲線加密學基礎知識

㈠ 橢圓曲線密碼學的一些具體的內容

⑴ 無窮遠元素（無窮遠點，無窮遠直線）
平面上任意兩相異直線的位置關系有相交和平行兩種。引入無窮遠點，是兩種不同關系統一。
AB⊥L1， L2∥L1，直線AP由AB起繞A點依逆時針方向轉動，P為AP與L1的交點。
Q=∠BAP→p /2 AP → L2
可設想L1上有一點P∞，它為L2和L1的交點，稱之為無窮遠點。
直線L1上的無窮遠點只能有一個。
（因為過A點只能有一條平行於L1的直線L2，而兩直線的交點只能有一個。）
結論：
1*. 平面上一組相互平行的直線，有公共的無窮遠點。
（為與無窮遠點相區別，把原來平面上的點叫做平常點）
2*.平面上任何相交的兩直線L1,L2有不同的無窮遠點。
原因：若否，則L1和L2有公共的無窮遠點P∞，則過兩相異點A和P ∞有相異兩直線，與公理相矛盾。
3*. 全體無窮遠點構成一條無窮遠直線。
註：歐式平面添加上無窮遠點和無窮遠直線，自然構成射影平面。
⑵ 齊次坐標
解析幾何中引入坐標系，用代數的方法研究歐氏空
間。這樣的坐標法也可推廣至攝影平面上，建立平面攝影
坐標系。
牋 L1,L2
L1: a1x+b1y+c1=0
L2: a2x+b2y+c2=0
其中a1,b1不同時為0；a2,b2也不同時為0。
設
D= a1 b1 Dx= b1 c1 Dy= c1 a1
a2 b2 b2 c2 c2 a2
若D≠0，則兩直線L1,L2相交於一平常點P(x,y），其坐標為x=Dx/D，y=Dy/D.
這組解可表為：x/Dx=y/Dy=1/D
（約定：分母Dx，Dy有為0時，對應的分子也要為0）
上述表示可抽象為（Dx，Dy，D).
若 D=0，則L1∥L2，此時L1和L2交於一個無窮遠點P∞。
這個點P∞可用過原點O且平行於L2的一條直線L來指出他
的方向，而這條直線L的方程就是：a2x+b2y=0.
為把平常點和無窮遠點的坐標統一起來，把點的坐標用
（X，Y，Z）表示，X，Y，Z不能同時為0，且對平常點
（x，y）來說，有Z≠0，x=X/Z，y=Y/Z，於是有：
i.e.
X / Dx = Y / Dy = Z / D，
有更好的坐標抽象，X,Y,Z），這樣對於無窮遠點則有Z=0，
也成立。
註：
a).若實數p≠0，則（pX,pY,pZ）與（X,Y,Z）表示同一個點。實質上用（X:Y:Z）表示。3個分量中，只有兩個是獨立的，</pre>
<pre>；具有這種特徵的坐標就叫齊次坐標。
b).設有歐氏直線L，它在平面直角坐標系Oxy上的方程為：
ax+by+c=0
則L上任一平常點（x,y）的齊次坐標為（X,Y,Z），Z≠0，代入得：
aX+bY+cZ=0
給L添加的無窮遠點的坐標（X,Y,Z）應滿足aX+bY=0，Z=0；平面上無窮遠直線方程自然為：Z=0 !!
⑶任意域上的橢圓曲線
K為域，K上的攝影平面P2(K）是一些等價類的集合{(X:Y:Z)}。考慮下面的Weierstrass方程（次數為3的齊次方程）：
Y2Z+a1XYZ+a3YZ2=X3+a2X2z+a4XZ2+a6Z3
（其中系數ai∈K，或ai∈K為K的代數閉域）
Weierstrass方程被稱為光滑的或非奇異的是指對所有適合
以下方程的射影點P=(X:Y:Z) ∈ P2(K）來說，
F(X,Y,Z)=Y2Z+a1XYZ+a3YZ2-X3-a2X2Z-a4XZ2-a6Z3=0
在P點的三個偏導數 之中至少有一個不為
0若否稱這個方程為奇異的。
橢圓曲線E的定義：
橢圓曲線E是一個光滑的Weierstrass方程在P2(K）中的
全部解集合。
Y2Z+a1XYZ+a3YZ2=X3+a2X2Z+a4XZ2+a6Z3
註：
a) 在橢圓曲線E上恰有一個點，稱之為無窮遠點。即（0:1:0）用θ表示。
b) 可用非齊次坐標的形式來表示橢圓曲線的Weierstrass方程：
設 x=X/Z，y=Y/Z，於是原方程轉化為：
y2+a1xy+a3y=x3+a2x2+a4x+a6 ⑴
此時，橢圓曲線E就是方程⑴在射影平面P2(K）上的全部平常點解，外加一個無窮遠點θ組成的集合。
c) 若a1,a2,a2,a4,a6∈K，此時橢圓曲線E被稱為定義在K上，用E/K表示。如果E能被限定在K上，那麼E的K--</pre>
<pre>；有理點集合表示為E(K），它為E中的全體有理坐標點的集合外加無窮遠點θ.
⑷實域R上的橢圓曲線
設K=R，此時的橢圓曲線可表為平面上的通常曲線上
的點，外加無窮遠點θ。
實域R上橢圓曲線的點的加法運演算法則：
設L ∈ P2(R）為一條直線。因為E的方程是三次的，所以L可與E在P2(R）恰有三個交點，記為P,Q,R
（注意：如果L與E相切，那麼P,Q,R可以不是相異的）。按下述方式定義E上運算⊙：
設P,Q ∈ E，L為聯接P,Q的直線（若P=Q，則L取過P點的切線）；設R為L與E的另一個交點；
再取連接R與無窮遠點的直線L′。則L′與E的另一個交點定義為P ⊙Q。
上頁的實際圖像為橢圓曲線y2=x3 - x的一般化。來自對具體曲線的抽象。對運算更具體一些：
設 P=(x1,y1），Q=(x2,y2），P⊙Q=(x3,y3），
由P Q的定義，設y=αx+β為通過P,Q兩點直線L的方程，可算出：
α=(y2-y1）/(x2-x1），β=y1-αx1
易見，直線L上的一個點（x，αx+β）是在橢圓曲線E上，
當且僅當（αx+β）2= x3 - x。
P⊙Q=(x1,y1） (x2,y2）=(x3,y3） =(x3,-（αx3+β））
其中，x3= α2-x1-x2=((y2-y1） / (x2-x1））2-x1-x2；
y3=-y1+((y2-y1）/(x2-x1））（x1-x3）
當P=Q時：P⊙Q=（x3，y3）算得：
x3=（（3x12-1）/2y1）2-2x1; y3= -y1+（（3x12-1）/2y1）（x1-x3）
註：
a) 如果直線L與E相交與三點P,Q,R（不一定相異），那麼 (P⊙Q)R=θ（從圖中可見）。
b) 任給P∈E,P⊙θ =P （此時設Q= θ ，易見L=L′）
c) 任給P,Q∈E有：P⊙Q =Q⊙P
d) 設P∈E，那麼可以找到 - P∈E使P -P= θ
e) 任給P,Q,R∈E，有（P⊙Q）⊙R= P⊙（Q⊙R)
綜上所述，知E對 運算形成一個Abel群。
f) 上述規則可開拓到任意域上，特別是有限域上。假定
橢圓曲線是定義在有限域Fq上（q=pm），那麼
E(Fq)={(x,y）∈Fq×Fq | y2+a1xy+a3y=x3+a2x2+a4x+a6} ∪{θ}
它對? 斝緯梢桓鋈海?獮bel群。 令Fq表示q個元素的有限域，用E(Fq）表示定義在Fq上
的一個橢圓曲線E。
定理1.(Hass定理） E(Fq）的點數用#E(Fq）表示，則
| #E(Fq)-q-1|≤2q1/2
⑴ Fp（素域，p為素數）上橢圓曲線
牋 p&gt;3 a,b Fp 4a3+27b2 0 a b
義的Fp上的一個橢圓曲線方程為：
y2=x3+ax+b ⑵
它的所有解（x,y），（x Fp，y Fp），連同一個稱為撐耷鈐?
點敚?俏?齲┑腦?刈槌傻募?霞俏狤（Fp），由Hass定理
知：p+1-2p1/2≤#E(Fp) ≤ p+1+2p1/2
集合E(Fp）對應下面的加法規則，且對加法 形成
一個Abel群：
（i) θ⊙ θ=θ （單位元素）
（ii) (x,y）⊙ θ=(x,y），任給（x,y) ∈E(Fp)
（iii) (x,y）⊙ (x,-y)=θ，任給（x,y) ∈E(Fp），即點（x,y）的逆元
為（x,-y).
（iv) 令（x1,y1），（x2,y2）為E(Fp）中非互逆元，則
（x1,y1）⊙ (x2,y2）=(x3,y3），其中
x3=α2-2x1，y3= α（x1-x3）-y1
且α=(y2-y1）/(x2-x1） ⑶
（v）（倍點運算規則）
設（x1,y1） ∈E(Fp),y1≠0，則2(x1,y1）=(x3,y3），其中
x3= α2-2x1,y3=α（x1-x3）-y1
這里α=（3x12+a)/（2y1） ⑷
註：若#E(Fp)=p+1，曲線E(Fp）稱為超奇異的，否則稱為
非超奇異的。
例子：F23上的一個橢圓曲線
令y2=x3+x+1是F23上的一個方程（a=b=1），則該橢圓曲
線方程在F23上的解為（y2=x3+x+1的點）：
（0,1），（0,22），（1,7），（1,16），（3,10），（3,13），（4,0），（5,4），（5,19），（6,4），</pre>
<pre>；（6,19），（7,11），（7,12），（9,7），（9,16），（11,3），（11,20），（12,4），（12,19），（13,7），</pre>
<pre>；（13,16），（17,3），（17,20），（18,3），（18,20），（19,5），（19,18）；θ。
群E(F23）有28個點（包括無窮遠點θ）。
2） F2m上的橢圓曲線
F2m上由參數a,b∈F2m，b≠0定義的一個非超奇異橢
圓曲線E(F2m）是方程
y2+xy=x3+ax2+b ⑸
的解集合（x,y），其中x,y∈F2m，連同θ。
E(F2m）的加法規則如下：
（i) θ +θ= θ
（ii) 任給（x,y) ∈E(F2m），則（x,y）⊙ θ=(x,y)
（iii) 任給（x,y) ∈E(F2m），則（x,y)+(x,x+y)= θ，
即點（x,y）的逆為（x,x+y).
（iv) 兩個相異且不互逆的點的加法規則：
令（x1,y1），（x2,y2） ∈E(F2m）且有x1≠x2則
（x1,y1） (x2,y2）=(x3,y3），其中
x3=α2+α+x1+x2+a；
y3=α（x1+x3）+x3+y1.
其中 α= (y2+y1）/(x2+x1）
（v) 倍點規則
令（x1,y1） ∈E(F2m），其中x1≠0。則
2(x1,y1）=(x3,y3），其中
x3= α 2+ α +a,y3=x12+（α +1）x3，這里α =(x1+y1/x1）
易見，群E(F2m）為Abel群。
例：F24上的一個橢圓曲線
f(x)=x4+x+1為F2上的一個不可約多項式，易見
F24=F2[x] / (f(x)) = {(k0,k1,k2,k3） | (k0,k1,k2,k3）=k0+k1α+k2α2+k3α3， </pre>
<pre>；α為f(x)的零點，ki∈F2}
假定F24上的非超奇異橢圓曲線有下述方程定義：
y2+xy=x3+α4x2+1，注意f（α）=0。
方程應表為：
（1000)y2 + （1000)xy = （1000)x3 + （1100）x2 +（1000) 1985年，N. Koblitz和V. Miller分別獨立提出了橢圓曲線密碼體制（ECC），</pre>
<pre>；其依據就是定義在橢圓曲線點群上的離散對數問題的難解性。
⑴知E(Fq）對點的?斣慫閾緯梢桓鯝bel群
設p∈E(Fq），若p的周期很大，即使
p⊙p⊙ …… ⊙p= θ （共有 t個p相加）
成立的最小正整數 t，希望 t 很大。
（t = p的周期，表示為∏（p)=t）。
並且對Q∈E(Fq），定有某個正整數m使
Q=m&middot;p=p⊙ …… ⊙p （共有t個p相加）
定義
m=㏒pQ (m為以p為底Q的對數）。
橢圓曲線上的點形成的群E(Fq），相關它的離散對數
問題是難處理的。 選取基域Fq，Fq的橢圓曲線具體給定為確定的形式。
在E(Fq）中選一個周期很大的點，如選了一個點P=(xp,yp），
它的周期為一個大的素數n，記∏ (P)=n（素數）。
注意：在這個密碼體制中，具體的曲線及點P和它的n都
是公開信息。密碼體制的形式採用EIGamal體制，是完全
類比過來。
a）密鑰的生成
Bob（使用者）執行了下列計算：
i) 在區間[1,n-1]中隨機選取一個整數d。
ii) 計算點Q:=dP (d個P相）
iii) Bob公開自己的公開密鑰-- (E(Fq),p,n,Q)
iv) Bob的私鑰為整數d！
Alice要發送消息m給Bob，Alice執行：
i) 查找Bob的公鑰（E(Fq),p,n,Q),
ii) 將m表示成一個域元素m∈Fq,
iii) 在區間[1，n-1]內選取一個隨機數k,
iv) 依據Bob的公鑰計算點 (x1,y1）：=kP(k個P相）
v) 計算點（x2,y2）：=kQ，如果x2=0，則回到第iii）步
Ⅵ） 計算C:=m&middot;x2
Ⅶ） 傳送加密數據（x1,y1,C）給Bob
b) Bob的解密過程
Bob收到Alice的密文（x1,y1,C）後，執行
i) 使用私鑰d，計算點（x2，y2）：=d(x1,y1），再計算Fq中x2-1=
通過計算m:=C&middot;x2-1，恢復出明文數據

㈡ ECC橢圓曲線加密演算法：介紹

ECC橢圓曲線加密演算法是一種基於橢圓曲線數學結構的公鑰加密技術，它在現代安全協議中發揮著核心作用。以下是關於ECC橢圓曲線加密演算法的詳細介紹：

1. 基本概念：

   • ECC演算法包括ECC、ECDH和ECDSA，它們共同構成了Web和IT世界的基礎，特別是在TLS、PGP和SSH等安全協議中。

2. 安全性與效率優勢：

   • 與傳統基於RSA、DSA和DH的公鑰加密相比，ECC在相同安全水平下提供了更小的密鑰尺寸和更高的計算效率。這意味著ECC可以在保持高安全性的同時，減少資源消耗和加速加密操作。

3. 數學原理：

   • ECC的安全性基於橢圓曲線上的離散對數問題，這是一個被認為在計算上非常困難的問題。具體來說，給定橢圓曲線上的一個點P和一個標量n，計算nP是容易的；但反過來，給定nP和P，要找到n是非常困難的。這種困難性保證了ECC的安全性。

4. 應用廣泛：

   • ECC不僅在傳統的網路安全協議中發揮著重要作用，還在比特幣和其他加密貨幣的交易中被廣泛應用。由於其高效性和安全性，ECC成為了現代加密技術中不可或缺的一部分。

5. 學習基礎：

   • 要深入理解ECC，需要具備一定的數學基礎，包括集合論、幾何和模運算的基礎知識，以及對稱和非對稱加密演算法的基本概念。同時，了解簡單與困難問題在加密中的角色也是非常重要的。

綜上所述，ECC橢圓曲線加密演算法以其高效性和安全性在現代加密技術中占據了重要地位，是保障網路安全和數據安全的重要手段之一。