素域定义:
有限域最直观的例子就是阶为素数的域。域
G
F
(
p
)
GF(p)
GF(p)的元素可以用整数
0
,
1
,
.
.
.
,
p
−
1
0,1,...,p-1
0,1,...,p−1来表示。域的两种操作就是模整数加法和整数乘法模
p
p
p;
假设 p p p 是一个素数,整数环 Z p Z_p Zp表示为 G F ( p ) GF(p) GF(p),也称为是拥有素数个元素的素数域或伽罗瓦域。 G F ( p ) GF(p) GF(p)中所有的非零元素都存在逆元, G F ( p ) GF(p) GF(p)内的算术运算都是模 p p p 实现的。
椭圆曲线定义:
Z p ( p > 3 ) Z_p(p>3) Zp(p>3)上的椭圆曲线指满足以下条件的所有对 ( x , y ) ∈ Z p (x,y) \in Z_p (x,y)∈Zp的集合 y 2 ≡ x 3 + a ∗ x + b m o d p y^2 \equiv x^3 + a*x + bmodp y2≡x3+a∗x+bmodp 以及一个无穷大的虚数点 σ \sigma σ,其中 a , b ∈ Z p a, b \in Z_p a,b∈Zp 并且满足条件 4 ⋅ a 3 + 27 ⋅ b 2 ≠ 0 m o d p . 4·a^3 + 27 · b^2 ≠ 0mod p. 4⋅a3+27⋅b2=0modp.
椭圆曲线的定义要求该曲线是非奇异的。从地理位置上说,这意味着该曲线的图不会自我相交或没有顶点;如果曲线的判别式 − 16 ( 4 a 3 + 27 b 2 ) -16(4a^3 + 27b^2) −16(4a3+27b2)不等于0,就可以保止这一尽。
假设用加法符号
“
+
”
“+”
“+”表示群操作(注意:将操作选择命名为“加法”完全是随意的,我们也可以将其称为乘法。)
。“加”意味着给定两个点及其对应的坐标,比如
P
=
(
x
1
,
y
1
)
P = (x_1, y_1)
P=(x1,y1)和
Q
=
(
x
2
,
y
2
)
,
Q = (x_2, y_2),
Q=(x2,y2),我们需要计算第三个点
R
R
R的坐标,使得:
P
+
Q
=
R
P + Q = R
P+Q=R
(
x
1
,
y
1
)
+
(
x
2
,
y
2
)
=
(
x
3
,
y
3
)
(x_1, y_1) + (x_2, y_2) = (x_3, y_3)
(x1,y1)+(x2,y2)=(x3,y3)
必须区分两种情况: 两个不同点的加法(即相异点相加) 和 同一点与自身的加法(即相同点相加)。
相异点相加P + Q :这个主要是针对计算
R
=
P
+
Q
R = P + Q
R=P+Q,且
P
≠
Q
P ≠ Q
P=Q的情况。构建的方法为: 画一条经过
Р
Р
Р 和
Q
Q
Q的线,该线与椭圆曲线的交点就是第三个点。根据定义,将第三个点关于
x
x
x轴映射,得到的映射点就是点
R
R
R。图9-4显示了实数上椭圆曲线的相异点相加。
相同点相加P + P: 这主要针对的是
P
+
Q
P + Q
P+Q但
P
=
Q
P = Q
P=Q的情况。因此,可以写作
R
=
P
+
P
=
2
P
R = P+P = 2P
R=P+P=2P。构建方法为:画一条经过
Р
Р
Р点的切线,即可得到此切线与椭圆曲线的第二个交点; 将此交点关于
x
x
x轴映射,得到的对称点就是相同点相加的结果
R
R
R。图9-5显示了实数上椭圆曲线的相同点相加。
事实证明,如果椭圆曲线上的点采用这种方式进行相加,则点的集合也满足群所需的大多数条件,即闭合性、结合性、存在单位元和逆元
。
椭圆曲线上的相同点相加与相异点相加:
x
3
=
s
2
−
x
1
−
x
2
m
o
d
p
x_3 = s^2 - x_1 - x_2 mod p
x3=s2−x1−x2modp
y
3
=
s
(
x
1
−
x
3
)
−
y
1
m
o
d
p
y_3 = s(x_1 - x_3) - y_1 mod p
y3=s(x1−x3)−y1modp 其中
s
=
{
y
2
−
y
1
x
2
−
x
1
m
o
d
p
,
当
P
≠
Q
(相异点相加)
3
x
1
2
+
a
2
y
1
m
o
d
p
,
当
P
=
Q
(相同点相加)
s =
注意: 在相异点加法中,参数 s s s指的是经过 Р Р Р和 Q Q Q的直线的斜率;而在相同点加法中,参数 s s s指的是经过点 P P P的切线的斜率。
那么现在问题来了:椭圆曲线上的所有点是否都满足 P + σ = P P + \sigma = P P+σ=P的单位元(或中性元) σ \sigma σ。事实证明,满足这个条件的点 ( x , y ) (x,y) (x,y)是不存在的。所以,我们将一个无穷的抽象点定义为单位元 σ \sigma σ。这个无穷点可以看作是位于y轴正半轴的无穷远处,或y轴负半轴的无穷远处。
根据群的定义,现在可将任何群元素 P P P的逆元 − P -P −P定义为: P + ( − P ) = σ . P + (-P) = \sigma. P+(−P)=σ.
那么我们如何找到 − P -P −P? 如果使用 tangent-and-chord方法,则点 P = ( x p , y p ) P=(x_p, y_p) P=(xp,yp)的逆元为点 − P = ( x p , − y p ) -P=(x_p, -y_p) −P=(xp,−yp),即其逆元是该点关于 x x x轴对称的点。下图显示了点 Р Р Р与其对应的逆元, 从图中可知,找到点 P = ( x , , y , ) P=(x,,y,) P=(x,,y,)的逆元非常简单,只需得到其 y y y坐标的负数即可。对素数域 G F ( p ) GF(p) GF(p)上的椭圆曲线而言,实现起来非常容易,因为 − y p ≡ p − y p m o d p -y_p \equiv p - y_p mod p −yp≡p−ypmodp,因此可以得到: − P = ( x , p − y p ) 。 -P =(x, p - y_p)。 −P=(x,p−yp)。
示例:考虑小型域
Z
17
Z_{17}
Z17上的曲线:
E
:
y
2
≡
x
3
+
2
x
+
2
m
o
d
17
E: y^2 \equiv x^3 + 2x + 2 mod 17
E:y2≡x3+2x+2mod17点
P
=
(
5
,
1
)
P = (5,1)
P=(5,1)的相同点加法为:
2
P
=
P
+
P
=
(
5
,
1
)
+
(
5
,
1
)
=
(
x
3
,
y
3
)
2P = P + P = (5, 1) + (5, 1) = (x_3, y_3)
2P=P+P=(5,1)+(5,1)=(x3,y3)
s
=
3
x
1
2
+
a
2
y
1
=
(
2
∗
1
)
−
1
(
3
∗
5
2
+
2
)
=
2
−
1
∗
9
≡
9
∗
9
≡
13
m
o
d
17
s = \frac{3x^2_1 + a}{2y_1} = (2*1)^{-1}(3*5^2 + 2) = 2^{-1} * 9 \equiv 9 * 9 \equiv 13 mod 17
s=2y13x12+a=(2∗1)−1(3∗52+2)=2−1∗9≡9∗9≡13mod17
x
3
=
s
2
−
x
1
−
x
2
=
1
3
2
−
5
−
5
=
159
≡
6
m
o
d
17
x_3 = s^2 - x_1 - x_2 = 13^2 - 5 - 5 = 159 \equiv 6 mod 17
x3=s2−x1−x2=132−5−5=159≡6mod17
y
=
s
∗
(
x
1
−
x
3
)
−
y
1
=
13
∗
(
5
−
6
)
−
1
=
−
14
≡
3
m
o
d
17
y =s*(x_1 - x_3) - y_1 = 13*(5 - 6) - 1= -14 \equiv 3 mod 17
y=s∗(x1−x3)−y1=13∗(5−6)−1=−14≡3mod17
2
P
=
(
5
,
1
)
+
(
5
,
1
)
=
(
6
,
3
)
2P = (5, 1) + (5, 1) = (6,3)
2P=(5,1)+(5,1)=(6,3)
检查结果
2
P
=
(
6
,
3
)
2P=(6,3)
2P=(6,3)是否真的是曲线上的一个点:
y
2
≡
x
3
+
2
∗
x
+
2
m
o
d
17
y^2 \equiv x^3 + 2*x + 2 mod 17
y2≡x3+2∗x+2mod17
3
2
≡
6
3
+
2
∗
6
+
2
m
o
d
17
3^2 \equiv 6^3 + 2*6 + 2 mod 17
32≡63+2∗6+2mod17
9
=
230
≡
9
m
o
d
17
9 = 230 \equiv 9 mod 17
9=230≡9mod17
定理一: 曲线上的点与 σ \sigma σ一起构成了循环子群。在某些条件下,椭圆曲线上的所有点可以形成一个循环群。
示例:找到以下曲线上的所有点: E : y 2 ≡ x 3 + 2 x + 2 m o d 17 E: y^2 \equiv x^3 + 2x + 2 mod 17 E:y2≡x3+2x+2mod17 曲线上的所有点恰好形成了一个循环群,而且该群的阶为#E=19。
从本原元
P
=
(
5
,
1
)
P=(5,1)
P=(5,1)开始,计算
P
P
P的所有幂值。更确切地讲,由于群操作为加法,所以需要计算
P
,
2
P
,
.
.
.
,
(
#
E
)
P
P,2P,...,(\#E)P
P,2P,...,(#E)P。以下是得到的元素的列表:
定理二(Hasse’s定理):给定一个椭圆曲线
E
E
E模
p
p
p,曲线上点的个数表示为
#
E
\#E
#E,并且在以下范围内:
p
+
1
−
2
p
≤
#
E
≤
p
+
1
+
2
p
p + 1 - 2\sqrt{p} ≤ \#E ≤ p + 1 + 2\sqrt{p}
p+1−2p≤#E≤p+1+2p
Hasse’s定理也称为Hasse’s边界,它说明了点的个数大概在素数p的范围内。这个结论具有非常大的实用性。例如,如果需要一个拥有 2 160 2^{160} 2160个元素的椭圆曲线,我们必须使用一个长度大约为 160 160 160位的素数。
注意: 在密码体制中, d d d 通常为整数, 也是私钥, 而公钥 T T T是曲线上的一个点, 坐标为 T = ( x T , y T ) T = (x_T, y_T) T=(xT,yT)。
椭圆曲线离散对数问题(ECDLP)
给定一个椭圆曲线 E E E,考虑本原元 Р Р Р和另一个元素 T T T。则 D L DL DL问题是找到整数 ( 1 ≤ d ≤ # E ) (1 ≤ d ≤ \#E) (1≤d≤#E),满足: P + P + … … + P ⏟ d 次 = d P = T . \ \underbrace{P+P+……+P}_{d次} = dP = T. d次 P+P+……+P=dP=T.
可以实现基于椭圆曲线的密钥交换,这也称为椭圆曲线Diffie-Hellman密钥交换或ECDH。首先必须统一域参数,即实现所需要的合适的椭圆曲线以及此曲线上的一个本原元。
ECDH域参数
椭圆曲线 Diffie-Hellman 密钥交换(ECDH)
证明此协议的正确性非常简单。
证明:Alice 计算
a
B
=
a
(
b
P
)
aB= a(bP)
aB=a(bP) 而Bob计算
b
A
=
b
(
a
P
)
.
bA = b(aP).
bA=b(aP).
由于点加法具有结合性(提示:结合性是群的一个属性),双方计算得到的结果相同,即点
T
A
B
=
a
b
P
.
T_{AB}= abP.
TAB=abP.
从协议中可以看出,Alice和 Bob分别选择了自己的私钥 a a a 和 b b b,这两个私钥都是非常大的整数。双方都使用各自的私钥计算出各自的公钥 A A A 和 B B B,而且这两个公钥都是曲线上的点。公钥是通过点乘法计算得到的,双方彼此交换公钥参数。然后,Alice和 Bob利用他们收到的公钥以及各自的私钥参数再次执行点乘计算,便可得到联合密钥 T A B T_{AB} TAB。联合密钥 T A B T_{AB} TAB可以用来得到会话密钥,比如作为AES算法的输入。注意: ( x A B , y A B ) (x_{AB}, y_{AB}) (xAB,yAB)的两个坐标并不是独立的: 给定 x A B x_{AB} xAB,将 x x x的值代入到椭圆曲线方程中就可计算出另一个坐标。因此,会话密钥生成时可以只用其中一个坐标。
示例:对于拥有如下域参数的ECDH。椭圆曲线为
y
2
=
x
3
+
2
∗
x
+
2
m
o
d
17
y^2 =x^3 + 2*x + 2 mod 17
y2=x3+2∗x+2mod17 ,它构成了阶为
#
E
=
19
\#E=19
#E=19的循环群。基点为
P
=
(
5
,
1
)
P=(5,1)
P=(5,1),该协议的工作方式如下:
参考资料:《深入浅出密码学》–Christof Paar,Jan Pelzl著