基本概念
設
K
K
K是一個域，域
K
K
K上的Weierstrass(威爾斯特拉斯)方程如下:
y
2
+
a
1
x
y
+
a
3
y
=
x
3
+
a
2
x
2
+
a
4
x
+
a
6
y^2 + a_1xy +a_3y=x^3+a_2x^2+a_4x+a_6
y2+a1?xy+a3?y=x3+a2?x2+a4?x+a6?，其中
a
1
,
a
2
,
a
3
,
a
4
,
a
6
∈
K
a_1, a_2, a_3, a_4, a_6 \in K
a1?,a2?,a3?,a4?,a6?∈K.
對于任意的域
K
K
K, Weierstrass方程的判別式是
Δ
=
?
b
2
2
b
8
?
8
b
4
3
?
27
b
6
2
+
9
b
2
b
4
b
6
\Delta = -b_2^2b_8-8b_4^3-27b_6^2+9b_2b_4b_6
Δ=?b22?b8??8b43??27b62?+9b2?b4?b6?
其中上述判別式中
f
(
x
)
=
{
b
2
=
a
1
2
+
4
a
2
b
4
=
a
1
a
3
+
2
a
4
b
6
=
a
3
2
+
4
a
6
b
8
=
a
1
2
a
6
?
a
1
a
3
a
4
+
4
a
2
a
6
+
a
2
a
3
2
?
a
4
2
f(x)=\left\{ \begin{aligned} b_2 & = & a_1^2+4a_2 \\ b_4 & = & a_1a_3+2a_4 \\ b_6 & = & a_3^2 + 4a_6 \\ b_8 & = & a_1^2a_6 -a_1a_3a_4+4a_2a_6+a_2a_3^2-a_4^2 \end{aligned} \right.
f(x)=????????????b2?b4?b6?b8??====?a12?+4a2?a1?a3?+2a4?a32?+4a6?a12?a6??a1?a3?a4?+4a2?a6?+a2?a32??a42??
定義(橢圓曲線)： 當
Δ
≠
0
\Delta \neq0
Δ?=0時，域
K
K
K上的點集
E
:
=
(
x
,
y
)
∣
y
2
+
a
1
x
y
+
a
3
y
=
x
3
+
a
2
x
2
+
a
4
x
+
a
6
∪
{
O
}
E:={(x,y)|y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6}\cup \{O\}
E:=(x,y)∣y2+a1?xy+a3?y=x3+a2?x2+a4?x+a6?∪{O}, 其中
a
1
,
a
2
,
a
3
,
a
4
,
a
6
∈
K
a_1, a_2, a_3, a_4, a_6 \in K
a1?,a2?,a3?,a4?,a6?∈K,
{
O
}
\{O\}
{O}為無窮遠點，叫做域K上的橢圓曲線，
j
=
c
4
3
Δ
j=\frac{c_4^3}{\Delta}
j=Δc43??叫做橢圓曲線E的
j
?
j-
j?不變數,記做
j
(
E
)
j(E)
j(E).
運算( ⊕ \oplus ⊕)
橢圓曲線上的運演算法則記為
⊕
\oplus
⊕,
運演算法則定義如下:設
P
,
Q
P,Q
P,Q是
E
E
E上的兩個點，
L
L
L是過
P
P
P和
Q
Q
Q的直線(當
P
,
Q
P,Q
P,Q是同一個點時，過
P
P
P點的切線)，
R
′
R^{'}
R′是
L
L
L與曲線
E
E
E相交的第三點，設
L
′
L^{'}
L′是過
R
′
R^{'}
R′和
O
O
O的直線，則
P
⊕
Q
P\oplus Q
P⊕Q就是
L
′
L^{'}
L′與E相交的第三點R，
運算性質
橢圓曲線E上運演算法則
⊕
\oplus
⊕具有如下性質：
如果直線
L
L
L交
E
E
E于點
P
,
Q
,
R
P,Q,R
P,Q,R(可以相同)，則
(
P
⊕
Q
)
⊕
R
=
O
(P\oplus Q)\oplus R=O
(P⊕Q)⊕R=O;
對任意
P
∈
E
P\in E
P∈E,
P
⊕
O
=
P
P\oplus O = P
P⊕O=P;
對任意
P
,
Q
∈
E
P, Q\in E
P,Q∈E,
P
⊕
Q
=
Q
⊕
P
P\oplus Q=Q\oplus P
P⊕Q=Q⊕P;
設
P
∈
E
P\in E
P∈E,存在一個點，記做
?
P
-P
?P,使得
P
⊕
(
?
P
)
=
O
P\oplus (-P)=O
P⊕(?P)=O;
對任意
P
,
Q
,
R
∈
E
P,Q,R\in E
P,Q,R∈E, 有
(
P
⊕
Q
)
⊕
R
=
P
⊕
(
Q
⊕
R
)
(P\oplus Q)\oplus R=P\oplus(Q\oplus R)
(P⊕Q)⊕R=P⊕(Q⊕R);
綜上所述，E對于運算規則
⊕
\oplus
⊕構成一個交換群，
橢圓曲線密碼
密碼學中橢圓曲線密碼采用的是有限域上的橢圓曲線，有限域上的橢圓曲線是指Weierstrass方程中的稀疏是由某一有限域 F p F_p Fp?中的元素(其中p為一大素數)， y 2 ≡ x 3 + a x + b ( m o d p ) ( a , b ∈ F p , 4 a 3 + 27 b 2 ( m o d p ) ≠ 0 ) y^2 \equiv x^3+ax+b(mod p)(a,b \in F_p, 4a^3+27b^2(mod p)\neq 0) y2≡x3+ax+b(modp)(a,b∈Fp?,4a3+27b2(modp)?=0)
E p ( a , b ) E_p(a,b) Ep?(a,b)
產生
- 對 ? x ∈ [ 0 , p ) \forall x\in [0,p) ?x∈[0,p)且 x x x為整數，計算 x 3 + a x + b ( m o d p ) x^3+ax+b(mod p) x3+ax+b(modp);
- 判斷上述的計算結果在模P下是否有平方根，如果沒有則曲線上沒有與這一 x x x相對應的點；如果有，則求出兩個平發根( y = 0 y=0 y=0時只有一個平方根)，
加法
- P + O = P P+O=P P+O=P；
- 如果 P = ( x , y ) , ? P = ( x , ? y ) P=(x,y), -P=(x, -y) P=(x,y),?P=(x,?y)是P的加法逆元；
- 點P的倍數:在P點做橢圓曲線的切線，設切線與曲線交于點 S S S,定義 2 P = P + P = ? S 2P=P+P=-S 2P=P+P=?S,類似的可定義 3 P = P + P + P 3P=P+P+P 3P=P+P+P.
- 設 P = ( x 1 , y 1 ) , Q = ( x 2 , y 2 ) , P ≠ Q P=(x_1, y_1), Q=(x_2, y_2), P\neq Q P=(x1?,y1?),Q=(x2?,y2?),P?=Q,則 P + Q = ( x 3 , y 3 ) P+Q =(x_3, y_3) P+Q=(x3?,y3?)由以下規則確定: x 3 ≡ λ 2 ? x 1 ? x 2 ( m o d p ) x_3\equiv \lambda ^2- x_1-x_2(mod p) x3?≡λ2?x1??x2?(modp) y 3 ≡ λ ( x 1 ? x 3 ) ? y 1 ( m o d p ) y_3 \equiv \lambda(x_1-x_3)-y_1(mod p) y3?≡λ(x1??x3?)?y1?(modp),其中 λ = { b 2 = y 2 ? y 1 x 2 ? x 1 , P ≠ Q b 4 = 3 x 1 2 + a 2 y 1 , P = Q ( m o d p ) \lambda=\left\{ \begin{aligned} b_2 & = & \frac{y_2-y_1}{x_2-x_1}, P\neq Q \\ b_4 & = & \frac{3x_1^2+a}{2_y1}, P =Q \\ \end{aligned} (mod p)\right . λ=????????b2?b4??==?x2??x1?y2??y1??,P?=Q2y?13x12?+a?,P=Q?(modp)
橢圓曲線密碼演算法
橢圓曲線密碼演算法(Elliptic curve cryptography， ECC)的安全性依賴于有限域上點群元素求解，同樣屬于離散對數難題，令 F p F_p Fp?為有限域，E為 F p F_p Fp?上的橢圓曲線， P P P為 E E E上的點，且階為素數n,并記 D = 1 , 2 , . . . , n ? 1 D={1,2,...,n-1} D=1,2,...,n?1.演算法如下：
- 通過使用引數 ( p , E , P , n ) (p,E,P,n) (p,E,P,n)選取私鑰 d ∈ D d\in D d∈D,并計算公鑰 Q = d P Q=dP Q=dP;
- 發送者將要發送的資訊M表示為E上的點；
- 隨機選擇 k ∈ D k\in D k∈D,并利用接受者的公鑰Q計算和發送 C = ( C 1 , C 2 ) = ( k P , M + k Q ) C=(C_1, C_2)=(kP, M+kQ) C=(C1?,C2?)=(kP,M+kQ);
- 資訊接收者用自己保存的私鑰d進行解密: M = C 2 ? d C 1 M=C_2-dC_1 M=C2??dC1?.
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/243631.html
標籤：區塊鏈