密码学
ECC

ECC

椭圆曲线定义

椭圆曲线加密算法(Elliptic curve cryptography)简称 ECC, 是一种非对称加密算法。方程式为

y2=x3+ax+b, 4a3+27b20y^2 = x^3 + ax +b, \ 4a^3 + 27b^2 \neq 0

不同的参数 a 和 b 会产生不同的曲线,如下图所示

从图中可以看出,椭圆曲线关于 XX 轴对称。

需要注意的是 aabb 须满足条件 4a3+27b204a^3 + 27b^2 \neq 0, 这个条件确保了曲线的光滑, 即曲线中不存在尖点,自相交点和孤立点, 从而保证曲线上的点都有切线。

加法运算

椭圆曲线的加法运算指曲线上的两个点相加得到第三个点的过程。有几种不同的情况:

点加

已知椭圆曲线上的点 PP 和点 QQ, 过这两点做直线,与椭圆曲线相交于第三个点 RR, RR 关于 XX 轴的对称点 RR' 就是 PPQQ 相加的结果, 即 P+Q=RP + Q = R'

假设 P=(x1,y1)P = (x_1, y_1), Q=(x2,y2)Q = (x_2, y_2), 点 PPQQ 所在直线的斜率是 m=y2y1x2x1m = \frac{y_2 - y_1}{x_2 - x_1},

根据点斜式方程 yy1=m(xx1)y - y_1 = m(x - x_1), 得到直线方程 y=m(xx1)+y1y = m(x - x_1) + y_1

椭圆曲线方程与直线方程联立:

(m(xx1)+y1)2=x3+ax+bm2(xx1)2+2y1m(xx1)+y12=x3+ax+bm2(x22xx1+x12)+2y1m(xx1)+y12=x3+ax+bm2x22xx1m2+m2x12+2y1mx2y1mx1+y12=x3+ax+bx3+ax+bm2x2+2xx1m2m2x122y1mx+2y1mx1y12=0x3m2x2+(a+2x1m22y1m)x+(bm2x12+2y1mx1y12)=0\begin{aligned} (m(x - x_1) + y_1)^2=x^3+ax+b \\ m^2(x-x_1)^2+2y_1m(x-x_1)+y_1^2=x^3+ax+b \\ m^2(x^2-2xx_1+x_1^2)+2y_1m(x-x_1)+y_1^2=x^3+ax+b \\ m^2x^2-2xx_1m^2+m^2x_1^2+2y_1mx-2y_1mx_1+y_1^2=x^3+ax+b \\ x^3+ax+b-m^2x^2+2xx_1m^2-m^2x_1^2-2y_1mx+2y_1mx_1-y_1^2=0 \\ x^3-m^2x^2+(a + 2x_1m^2-2y_1m)x + (b - m^2x_1^2 +2y_1mx_1 - y_1^2) = 0 \end{aligned}

对于三次方程x3+px2+qx+r=0x^3+px^2+qx+r=0, 根据韦达定理,其根 x1,x2,x3x_1, x_2, x_3 满足 x1+x2+x3=px_1+x_2+x_3=-p

根据推导 p=m2p=m^2, 故 x3=m2x1x2x_3=m^2-x_1-x_2, 代入得到 y3=m(x3x1)+y1y_3=m(x_3-x_1)+y_1

最终 R=(x3,y3)=(m2x1x2,m(x1x3)y1)R' = (x_3, -y_3) = (m^2 - x_1 - x_2, m(x_1 - x_3) - y_1)

点倍乘

P=QP=Q 时,相当于过点 PP 做曲线的切线,相交于点RR, RR 关于 XX 轴的对称点 RR' 就是相加得到的点。 P+P=2P=RP + P = 2P = R'

应用隐函数求导计算切线斜率 m=3x12+a2y1m = \frac{3x_1^2 + a}{2y_1}, 其余部分的计算同上。

逆元

Q=PQ=-P 时,即 QQPP 在椭圆曲线上关于 XX 轴的对称点,此时过这两点做直线。没有相交的第三个点。则 P+Q=P+(P)=OP + Q = P + (-P) = O

OO 是一个无穷远点,也叫加法的单位元。曲线上任意点与单位元相加都等于其自身。 P+O=PP + O = P

有限域椭圆曲线

在实数域上的椭圆曲线具有连续性的, 这种连续性并不适用于安全加密。采用取模的方式将椭圆曲线的运算结果固定在一个范围内变成离散的点。

椭圆曲线上的坐标 xxyy 都是整数, 取值在包含有限个元素的有限域中, 记作GF(p)GF_{(p)}𝔽p𝔽_p, 其中 pp 是素数。

例如 𝔽5={0,1,2,3,4}𝔽_5=\{0, 1, 2, 3, 4\}, 表示 xxyy 坐标的值只能是 {0,1,2,3,4}\{0,1,2,3,4\} 中的一个。

取模 pp 的有限域椭圆曲线方程为 y2=x3+ax+bmodpy^2 = x^3 + ax + b \mod p, 记作 Ep(a,b)E_{p}(a,b)。例如: E5(1,1):y2=x3+x+1mod 5E_{5}(1, 1): y^2 = x^3 + x + 1\mod\ 5

计算有限域椭圆曲线上的点时, 首先是确定 pp 的值。然后通过 xx 的值计算 yy 的值,如果 yy 的值不在 00p1p-1 之间, 则为无效点。

例如 E5(1,1):y2=x3+x+1mod 5,𝔽5={0,1,2,3,4}E_{5}(1, 1): y^2 = x^3 +x + 1\mod\ 5, 𝔽_5=\{0, 1, 2, 3, 4\},

由于 xxyy 的取值是在有限域中整数,因此对于上式中有多个可组合的点:

  • x=0,y=1x=0, y=1, 等式两边值为 y2=1y^2=1x3+x+1=1x^3 +x + 1 = 1, 各对 5 取模结果都为 1, 该点有效
  • x=0,y=2x = 0, y = 2, 等式左边对 5 取模结果为 4, 等式右边对 5 取模结果为 1, 该点无效
  • x=0,y=4x = 0, y = 4, 等式两边对 5 取模结果都为 1, 该点有效

如此遍历下去,便能确定最终的有效点为(0,1) (0,4) (2,1) (2,4), (3,1) (3,4) (4,2) (4,3)(0, 1)\ (0,4)\ (2, 1)\ (2, 4), \ (3, 1)\ (3, 4)\ (4,2)\ (4,3)

Curve:
a
b
Mod:
p
P:
x
y
Q:
x
y
P + Q:
x
y
有效点数量: 1(包括无穷远点)

从图中可以看出, 相同 xx 坐标, 会有一个关于 p2\frac {p}{2} 的对称点。并且相同 xx 坐标的 yy 坐标值一个是奇数一个是偶数。

点加

有限域椭圆曲线的点加是椭圆曲线密码学的核心。

已知点 P(x1,y1)P(x_1, y_1) 和点 Q(x2,y2)Q(x_2, y_2) 是有限域椭圆曲线上的两个点, 计算这两个点的和 P+QP + Q 的步骤如下:

计算斜率 m=y2y1x2x1mod pm = \frac{y_2 - y_1}{x_2 - x_1} \mod \ p, 如果 P=QP = Q,则 m=3x12+a2y1mod pm = \frac{3x_1^2 + a}{2y_1} \mod \ p

在实数域上的椭圆曲线加法, 需要计算 PPQQ 连接的直线与椭圆曲线的交点 RR, 在有限域椭圆曲线上同理。

假设有限域椭圆曲线E127(1,3):y2=x3x+3mod 127E_{127}(-1, 3): y^2=x^3 -x +3 \mod \ 127

P=(16,20)P=(16, 20), 点Q=(41,120)Q =(41,120)P+QP+Q 的坐标点R(xy)R'(x', y')

首先计算连接PPQQ 直线的斜率m=yPyQxPxQmod p=201201641mod 127=4mod 127=4m = \frac {y_P - y_Q}{x_P - x_Q} \mod \ p= \frac {20-120}{16-41} \mod \ 127=4 \mod\ 127 = 4

接着计算直线和曲线相交的第三个点的坐标R(x,y)R(x, y), 按照之前推导的公式:

xR=m2xPxQmod p=161641mod 127=41mod 127=86x_R = m^2 - x_P - x_Q \mod \ p = 16-16-41 \mod\ 127 = -41 \mod\ 127 = 86

yR=m(xRxP)+yPmod p=4(8616)+20mod 127=300mod 127=46y_R= m(x_R-x_P) + y_P \mod \ p = 4(86 - 16) + 20 \mod\ 127 = 300\mod\ 127 = 46

RR'RR 关于 XX 轴的对称点,所以

xR=xR=86x_{R'} = x_R = 86, yR=yRmodp=46mod127=81y_{R'} = -y_R \mod p = -46 \mod 127 = 81

所以 P+Q=(86,81)P+Q = (86, 81)

Curve:
a
b
Mod:
p
P:
x
y
Q:
x
y
P + Q:
x
y
有效点数量: 1(包括无穷远点)

点倍乘

在实数域中的乘法定义为:nP=P+P++PnP = P + P +\cdots + P, 对PP逐次累加计算。在有限域中同样可以这样计算。

但在有限域中椭圆曲线中的乘法会存在一个循环。

例如: 有限域椭圆曲线E97(2,3):y2=x3+2x+3mod 97E_{97}(2, 3): y^2=x^3+2x+3 \mod\ 97 和点P(3,6)P(3, 6)

  • 1P=(3,6)1P = (3, 6)
  • 2P=P+P=(80,10)2P = P + P = (80, 10)
  • 3P=2P+P=(80,87)3P=2P+P=(80, 87)
  • 4P=3P+P(3,91)4P=3P+P(3, 91)
  • 5P=4P+P=O5P = 4P+P=O
  • 6P=5P+P=(3,6)6P=5P+P=(3, 6)
  • 7P=6P+P=(80,10)7P =6P+P =(80, 10)
  • \cdots

P(3,6)P(3, 6) 的循环次数为 5, 以及循环计算得到的点集称循环子群。该点集的数量就叫做阶。即 5 是点P(3,6)P(3,6)的阶。

另一种更简单的计算方式是:

  • 计算椭圆曲线的阶 NN (NN 是有限域上椭圆曲线的有效点的数量)
  • 找出 NN 的所有因子
  • 对每个因子计算 nPnP
  • 找到最小的且满足 nP=OnP=Onn, nn 就是该点的阶

对于椭圆曲线E37(1,3):y2=x3x+3mod 37E_{37}(-1, 3): y^2=x^3-x+3 \mod\ 37

Curve:
a
b
Mod:
p
P:
x
y
Q:
x
y
P + Q:
x
y
有效点数量: 1(包括无穷远点)
P: (2, 3)
阶: 0
子群:

共有 42 个点,因此 N=42N = 42。42 的因子有 1,2,3,6,7,14,21,421,2,3,6,7,14,21,42 依次与点P(2,3)P(2,3) 相乘

1PO,2PO,,7P=O1P\neq O, 2P\neq O,\cdots,7P=O, 因此 PP 的阶是 7。

公私钥

在椭圆曲线加密算法中,给定椭圆曲线 EE 和 曲线上的基点 GG。 计算出 GG 的阶为 nn, 之后在{1,,n1}\{1,\cdots,n-1\} 中随机选择一个整数 kk 作为私钥,公钥H=kGH=kGHH 为曲线上的一个有效点。

在已知 HHGG 的情况下,计算 kk 是非常困难的。因为计算 kk 并不能用简单的线性运算 k=HGk=\frac{H}{G} 求出结果。

HHkkGG 相加的结果, 这种加法的计算并不是简单的代数运算。如果直接给出一个点 HH, 无法直接计算是由多少 kkGG 点相加的结果。只能从 1G,2G,3G,...1G, 2G, 3G, ... 如此不断地尝试, 直到结果等于 HH, 才能得到 kk

kk 是一个很大的数时, 这个过程的难度将变的非常大, 即使以现在最快的计算机, 尝试所有可能的 kk 值也需要远超过宇宙年龄的时间。 这也是为什么 ECC 安全性高的原因。

Copyright © 2025 HeapUp