国家标准全文公开系统：http://openstd.samr.gov.cn/
椭圆曲线
-
有限域
- 素域：
F
p
≅
Z
p
F_p \cong Z_p
Fp≅Zp
- 元素：模 p p p剩余系
- 加法：整数的模 p p p加法
- 乘法：整数的模 p p p乘法
- 二元扩域：
F
2
m
≅
Z
2
[
x
]
/
(
f
(
x
)
)
,
deg
f
=
m
F_{2^m} \cong Z_2[x]/(f(x)),\, \deg f = m
F2m≅Z2[x]/(f(x)),degf=m
- 元素： Z 2 Z_2 Z2上多项式，表示为 m m m长比特串
- 加法：比特串异或
- 乘法：多项式的模 f f f乘法
- 素域：
F
p
≅
Z
p
F_p \cong Z_p
Fp≅Zp
-
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 ⟺字节串
- 若 a ∈ F p a \in F_p a∈Fp，那么 a ∈ [ 0 , p ) ∩ Z a \in [0,p) \cap Z a∈[0,p)∩Z，整数 ⟺ \iff ⟺字节串
- 若 a ∈ F 2 m a \in F_{2^m} a∈F2m，那么 a ∈ { 0 , 1 } m a \in \{0,1\}^m a∈{0,1}m，比特串 ⟺ \iff ⟺字节串
-
域元素 ⟺ \iff ⟺字节串 ⟺ \iff ⟺整数
-
点 P = ( x P , y P ) ≠ O ⟺ P=(x_P,y_P) \not = O\iff P=(xP,yP)=O⟺字节串
- 标识字节PC
- 无穷远点 O O O， P C = 00 PC=00 PC=00
- 压缩表示： P C = 02 或 03 PC=02或03 PC=02或03
- 未压缩表示： P C = 04 PC = 04 PC=04
- 混合表示： P C = 06 或 07 PC=06或07 PC=06或07
- 压缩表示
- 将域元素 x P x_P xP转换为字节串 X X X
- 计算 y ˉ P \bar y_P yˉP，若等于 0 0 0那么 P C = 02 PC=02 PC=02，若等于 1 1 1那么 P C = 03 PC=03 PC=03
- 字节串为 S = P C ∥ X S = PC \| X S=PC∥X
- 未压缩表示
- 将域元素 x P , y P x_P,y_P xP,yP转换为字节串 X , Y X,Y X,Y
- 令 P C = 04 PC=04 PC=04
- 字节串为 S = P C ∥ X ∥ Y S = PC \| X \| Y S=PC∥X∥Y
- 混合表示
- 将域元素 x P , y P x_P,y_P xP,yP转换为字节串 X , Y X,Y X,Y
- 计算 y ˉ P \bar y_P yˉP，若等于 0 0 0那么 P C = 06 PC=06 PC=06，若等于 1 1 1那么 P C = 07 PC=07 PC=07
- 字节串为 S = P C ∥ X ∥ Y S = PC \| X \| Y S=PC∥X∥Y
- 标识字节PC
-
点的压缩和解压缩
-
E
(
F
p
)
E(F_p)
E(Fp)上一点
P
=
(
x
P
,
y
P
)
P=(x_P,y_P)
P=(xP,yP)，曲线
y
2
=
x
3
+
a
x
+
b
y^2 = x^3+ax+b
y2=x3+ax+b
- 压缩： y ˉ P \bar y_P yˉP是 y P y_P yP的最低比特位
- 解压：计算 α = x P 3 + a x P + b m o d p \alpha=x^3_P+ax_P+b \mod p α=xP3+axP+bmodp，再计算平方根 β 2 = α m o d p \beta^2 = \alpha \mod p β2=αmodp；检查 β \beta β的最低比特位，若等于 y ˉ P \bar y_P yˉP，令 y P = β y_P=\beta yP=β，否则令 y P = p − β y_P=p-\beta yP=p−β
-
E
(
F
2
m
)
E(F_{2^m})
E(F2m)上一点
P
=
(
x
P
,
y
P
)
P=(x_P,y_P)
P=(xP,yP)，曲线
y
2
+
x
y
=
x
3
+
a
x
2
+
b
y^2+xy = x^3+ax^2+b
y2+xy=x3+ax2+b
- 压缩：若 x P = 0 x_P=0 xP=0那么 y ˉ P = 0 \bar y_P=0 yˉP=0，否则 y ˉ P \bar y_P yˉP是域元素 y P ⋅ x P − 1 y_P \cdot x_P^{-1} yP⋅xP−1的最低比特位
- 解压：若 x P = 0 x_P=0 xP=0那么 y P = b 2 m − 1 y_P=b^{2^{m-1}} yP=b2m−1，否则计算 β = x P + a + b x P − 1 \beta = x_P + a + bx_P^{-1} β=xP+a+bxP−1，寻找域元素 z 2 + z = β z^2+z=\beta z2+z=β，记最低比特位为 z ˉ \bar z zˉ；若 y P ≠ z ˉ y_P \not = \bar z yP=zˉ，置 z = z + 1 z=z+1 z=z+1，其中 1 1 1是幺元；最后计算 y P = x P ⋅ z y_P=x_P \cdot z yP=xP⋅z
-
E
(
F
p
)
E(F_p)
E(Fp)上一点
P
=
(
x
P
,
y
P
)
P=(x_P,y_P)
P=(xP,yP)，曲线
y
2
=
x
3
+
a
x
+
b
y^2 = x^3+ax+b
y2=x3+ax+b