国家标准全文公开系统:http://openstd.samr.gov.cn/
有限域
F p F_p Fp上椭圆曲线群
椭圆曲线方程:
y
2
=
x
3
+
a
x
+
b
,
a
,
b
∈
F
p
4
a
3
+
27
b
2
m
o
d
p
≠
0
y^2 = x^3+ax+b,\, a,b \in F_p\\ 4a^3+27b^2\mod p \not = 0
y2=x3+ax+b,a,b∈Fp4a3+27b2modp=0
椭圆曲线:
E
(
F
p
)
:
=
{
(
x
,
y
)
∣
x
,
y
∈
F
p
,
满
足
椭
圆
曲
线
方
程
}
∪
{
O
:
无
穷
远
点
}
E(F_p):=\{(x,y) \mid x,y \in F_p,满足椭圆曲线方程\} \cup \{O:无穷远点\}
E(Fp):={(x,y)∣x,y∈Fp,满足椭圆曲线方程}∪{O:无穷远点}
椭圆曲线的阶:
∣
E
(
F
p
)
∣
:
=
#
E
(
F
p
)
|E(F_p)| := \#E(F_p)
∣E(Fp)∣:=#E(Fp)
椭圆曲线
E
(
F
p
)
E(F_p)
E(Fp)上的点构成交换群:
单位元: O + O = O O+O=O O+O=O, P + O = O + P = P P+O=O+P=P P+O=O+P=P
逆元: P = ( x , y ) ≠ O , − P = ( x , − y ) P=(x,y) \not = O,\, -P=(x,-y) P=(x,y)=O,−P=(x,−y),且 P + ( − P ) = O P+(-P)=O P+(−P)=O
加法:
P
1
=
(
x
1
,
y
1
)
≠
O
,
P
2
=
(
x
2
,
y
2
)
≠
O
,
x
1
≠
x
2
P_1=(x_1,y_1) \not = O,\, P_2=(x_2,y_2) \not = O,\, x_1 \not = x_2
P1=(x1,y1)=O,P2=(x2,y2)=O,x1=x2,令
P
3
=
P
1
+
P
2
=
(
x
3
,
y
3
)
P_3=P_1+P_2=(x_3,y_3)
P3=P1+P2=(x3,y3),则
{
λ
=
y
2
−
y
1
x
2
−
x
1
x
3
=
λ
2
−
x
1
−
x
2
y
3
=
λ
(
x
1
−
x
3
)
−
y
1
\left\{ \begin{aligned} \lambda &= \frac{y_2 - y_1}{x_2 - x_1}\\ x_3 &= \lambda^2 - x_1 - x_2\\ y_3 &= \lambda(x_1-x_3)-y_1 \end{aligned} \right.
⎩⎪⎪⎪⎨⎪⎪⎪⎧λx3y3=x2−x1y2−y1=λ2−x1−x2=λ(x1−x3)−y1
倍点:
P
1
=
(
x
1
,
y
1
)
≠
O
,
y
1
≠
0
P_1=(x_1,y_1) \neq O,\, y_1 \not = 0
P1=(x1,y1)=O,y1=0,令
P
3
=
P
1
+
P
1
=
(
x
3
,
y
3
)
P_3 = P_1+P_1 = (x_3,y_3)
P3=P1+P1=(x3,y3),则
{
λ
=
3
x
1
2
+
a
2
y
1
x
3
=
λ
2
−
2
x
1
y
3
=
λ
(
x
1
−
x
3
)
−
y
1
\left\{ \begin{aligned} \lambda &= \frac{3x_1^2+a}{2y_1}\\ x_3 &= \lambda^2 - 2x_1\\ y_3 &= \lambda(x_1-x_3)-y_1 \end{aligned} \right.
⎩⎪⎪⎪⎨⎪⎪⎪⎧λx3y3=2y13x12+a=λ2−2x1=λ(x1−x3)−y1
F 2 m F_{2^m} F2m上椭圆曲线群
椭圆曲线方程:
y
2
+
x
y
=
x
3
+
a
x
2
+
b
a
,
b
∈
F
2
m
,
b
≠
0
y^2+xy = x^3+ax^2+b\\ a,b \in F_{2^m},\,b \not = 0
y2+xy=x3+ax2+ba,b∈F2m,b=0
椭圆曲线:
E
(
F
p
)
:
=
{
(
x
,
y
)
∣
x
,
y
∈
F
2
m
,
满
足
椭
圆
曲
线
方
程
}
∪
{
O
:
无
穷
远
点
}
E(F_p):=\{(x,y) \mid x,y \in F_{2^m},满足椭圆曲线方程\} \cup \{O:无穷远点\}
E(Fp):={(x,y)∣x,y∈F2m,满足椭圆曲线方程}∪{O:无穷远点}
椭圆曲线的阶:
∣
E
(
F
2
m
)
∣
:
=
#
E
(
F
2
m
)
|E(F_{2^m})| := \#E(F_{2^m})
∣E(F2m)∣:=#E(F2m)
椭圆曲线
E
(
F
2
m
)
E(F_{2^m})
E(F2m)上的点构成交换群:
单位元: O + O = O O+O=O O+O=O, P + O = O + P = P P+O=O+P=P P+O=O+P=P
逆元: P = ( x , y ) ≠ O , − P = ( x , x + y ) P=(x,y) \not = O,\, -P=(x,x+y) P=(x,y)=O,−P=(x,x+y),且 P + ( − P ) = O P+(-P)=O P+(−P)=O
加法:
P
1
=
(
x
1
,
y
1
)
≠
O
,
P
2
=
(
x
2
,
y
2
)
≠
O
,
x
1
≠
x
2
P_1=(x_1,y_1) \not = O,\, P_2=(x_2,y_2) \not = O,\, x_1 \not = x_2
P1=(x1,y1)=O,P2=(x2,y2)=O,x1=x2,令
P
3
=
P
1
+
P
2
=
(
x
3
,
y
3
)
P_3=P_1+P_2=(x_3,y_3)
P3=P1+P2=(x3,y3),则
{
λ
=
y
2
+
y
1
x
2
+
x
1
x
3
=
λ
2
+
λ
+
x
1
+
x
2
+
a
y
3
=
λ
(
x
1
+
x
3
)
+
x
3
+
y
1
\left\{ \begin{aligned} \lambda &= \frac{y_2 + y_1}{x_2 + x_1}\\ x_3 &= \lambda^2 + \lambda + x_1 + x_2 + a\\ y_3 &= \lambda(x_1 + x_3) + x_3 + y_1 \end{aligned} \right.
⎩⎪⎪⎪⎨⎪⎪⎪⎧λx3y3=x2+x1y2+y1=λ2+λ+x1+x2+a=λ(x1+x3)+x3+y1
倍点:
P
1
=
(
x
1
,
y
1
)
≠
O
,
x
1
≠
0
P_1=(x_1,y_1) \neq O,\, x_1 \not = 0
P1=(x1,y1)=O,x1=0,令
P
3
=
P
1
+
P
1
=
(
x
3
,
y
3
)
P_3 = P_1+P_1 = (x_3,y_3)
P3=P1+P1=(x3,y3),则
{
λ
=
x
1
+
y
1
x
1
x
3
=
λ
2
+
λ
+
a
y
3
=
x
1
2
+
(
λ
+
1
)
x
3
\left\{ \begin{aligned} \lambda &= x_1 + \frac{y_1}{x_1}\\ x_3 &= \lambda^2 + \lambda + a\\ y_3 &= x_1^2 + (\lambda+1)x_3 \end{aligned} \right.
⎩⎪⎪⎨⎪⎪⎧λx3y3=x1+x1y1=λ2+λ+a=x12+(λ+1)x3
椭圆曲线上离散对数问题 (ECDLP) :已知 E ( F q ) E(F_q) E(Fq), n n n阶点 G ∈ E ( F q ) G \in E(F_q) G∈E(Fq),以及 Q ∈ < G > Q \in <G> Q∈<G>,计算 l ∈ [ 0 , n ) ∩ Z l \in [0,n) \cap Z l∈[0,n)∩Z,使得 Q = [ l ] G Q=[l]G Q=[l]G;这里的 [ l ] G [l]G [l]G是多倍点。
数据类型:点、域元素、整数、比特串、字节串
整数 ⟺ \iff ⟺字节串
比特串 ⟺ \iff ⟺字节串
域元素 ⟺ \iff ⟺字节串
域元素 ⟺ \iff ⟺字节串 ⟺ \iff ⟺整数
点 P = ( x P , y P ) ≠ O ⟺ P=(x_P,y_P) \not = O\iff P=(xP,yP)=O⟺字节串
点的压缩和解压缩