椭圆曲线ECC加密

发表于 2026/05/19 更新于 2026/05/31

作者 youzi

22 分钟阅读

椭圆曲线ECC加密

实数域上的椭圆曲线

椭圆曲线的标准形式

\[\{ (x,y)\in \mathbb{R^2}\ \ | \ \ y^2=x^3+ax+b,\ \ 4a^3+27b^2\neq0 \}\cup \{ 0 \}\]

此处的限定条件 $4a^3+27b^2\neq0$ 是为了保证曲线上不含奇点（尖点，自交点），用0来表示无穷远处的点，作为单位元。从几何上看，随着a，b的不同，曲线会呈现出不同的形状。

现在来定义椭圆曲线上的一个群：

群中的元素就是椭圆曲线上的点。
单位元就是无穷处的点0。
相反数P，是关于X轴对称的另一边的点。
加法规则定义如下：取一条直线上的三点（直线和椭圆曲线相交的三点），P, Q, R（皆非零），他们的总和等于0，P+Q+R=0。

显然，椭圆曲线群上的加法满足交换律和结合律，因此这是一个阿贝尔群。

几何加法

因为椭圆曲线群是一个阿贝尔群，所以可以把P+Q+R=0写成P+Q=-R。由此，我们可以用几何的方法定义实数域上椭圆曲线的加法：

画一条直线通过P，Q，这条线将会和椭圆曲线相交于第三个点，R（因为三次方程不可能有两个根，所以这个点大部分情况下存在）。取它相反的点，-R，这就是P+Q 的结果。

一些特殊情况：

P或Q=0：这种情况下画不出线，但我们已经定义了0为单位元，所以可以计算P+0=P
P=-Q：这种情况下穿过两点的线垂直于x轴，没有第三点，但我们已经定义了相反数，所以P+Q=0
P=Q：即直线与椭圆曲线在P点相切，若切线与曲线交于另一点R，记P+P=-R
P！=Q，但直线与曲线相切，即Q为切点，此时结果为切点的相反，P+Q=-Q

代数加法

进行代数运算求椭圆曲线上点的相加，分为以下几步：

计算直线斜率：P！=Q时，用两点式斜率公式

\[m = \frac{y_P - y_Q}{x_P - x_Q}\]

当P=Q时，隐函数求导得到切线斜率：

\[\boldsymbol{m = \frac{3x_P^2 + a}{2y_P}}\]

直线方程：用点斜式表示

\[y = m(x - x_P) + y_P\]

联立直线与椭圆曲线方程：
将直线方程代入 $y^2 = x^3 + ax + b$，展开整理得到三次方程：

\[x^3 - m^2x^2 + (a + 2m^2x_P - 2my_P)x + (b - m^2x_P^2 + 2my_Px_P - y_P^2) = 0\]

用韦达定理求 $x_R$：
三次方程 $x^3 + c_2x^2 + c_1x + c_0=0$ 的三个根之和等于 $-c_2$ 。这里三个根是 $x_P, x_Q, x_R$ ，因此：

\[x_P + x_Q + x_R = m^2 \implies \boldsymbol{x_R = m^2 - x_P - x_Q}\]

求 $y_R$：
将 $x_R$ 代入直线方程

\[\boldsymbol{y_R = y_P + m(x_R - x_P)}\]

这里用Q点计算也可以

结果：取 $R$ 的对称点

\[\boldsymbol{P+Q = (x_R, -y_R)}\]

标量积

还需要定义一个运算：数乘

\[nP = \underbrace{P+P+\dots+P}_{n次}\]

可以看出，用加n次的方法计算数乘不好，因为假设$n=2^k$ ，当k很大时，复杂度超大。

高效计算标量积用到一种倍加算法：

任何整数 $n$ 都可以唯一表示为二进制形式，也就是2的幂次之和： $n = b_0 \cdot 2^0 + b_1 \cdot 2^1 + b_2 \cdot 2^2 + \dots + b_{k-1} \cdot 2^{k-1}$ 其中 $b_i \in {0,1}$ 是二进制的每一位。

代入标量积的定义，利用加法结合律： $nP = b_0 \cdot 2^0P + b_1 \cdot 2^1P + b_2 \cdot 2^2P + \dots + b_{k-1} \cdot 2^{k-1}P$ 这意味着：

我们只需要预先计算出 $2^0P, 2^1P, 2^2P, \dots, 2^{k-1}P$（每次加倍即可）
然后把二进制位为1对应的项加起来，就是最终结果

总结就是，计算nP只要已知让P加自己，实现翻倍。

代码实现如下：

  
def bits(n):
    while n:
        yield n & 1
        n >>= 1

def double_and_add(n, x):
    result = 0
    addend = x

    for bit in bits(n):
        if bit == 1:
            result += addend
        addend *= 2

    return result

这个算法的复杂度是O(logn)，可以高效计算。

对数现在，对于给定的n和P，我们现在至少有一个多项式最高次幂的算法来计算Q=nP。但是如果知道Q和P，要求n，这就是对数问题。

有限域上的椭圆曲线

有限域Fp

有限域是一个带有有限元素的集合，比如整数模p的集合，可表示为$\mathbb{Z}/p,GF(p),\mathbb{F}_{p}$ 可以简单理解为模p的一个最小完全剩余系

Fp上的椭圆曲线

\[\{ (x,y)\in \mathbb{F}_{p}^{2}\ \ | \ \ y^2=x^3+ax+b\ \ (modp),\ \ 4a^3+27b^2\neq0 \ \ (modp) \}\cup \{ 0 \}\]

这里的0仍然是无限远的点，a和b是Fp上的两个整数。

将之前在实数域上的连续椭圆曲线，搬到了有限域 $\mathbb{F}_p$ 上，让它从一条光滑的曲线变成了一堆离散的点。所有的群性质、点加法公式、弦切法则几乎原封不动地保留了下来。此时，奇点表现为重合的点。

是一堆离散、孤立的点，没有“曲线”的形状
所有点的坐标 $(x,y)$ 都只能取 $0,1,2,\dots,p-1$ 这p个整数
点的总数是有限的，大约等于p个
p越大，点的数量越多，分布越随机，破解难度呈指数级增长。

几何加法

最关键的是，在有限域上，不能再用实数域上三点共线的方法定义加法。类似的，我们用代数定义一条直线：

一条直线是所有满足线性方程 $ax + by + c \equiv 0 \pmod{p}$ 的点 $(x,y) \in \mathbb{F}_p^2$ 的集合。

和实数域一样，一条直线与有限域椭圆曲线最多交于3个点

同样，由于这已经构成一个阿贝尔群，所以满足所有阿贝尔群的基本规则。

代数加法

情况1：$P \neq Q$ 且 $P \neq -Q$

\[\begin{align*} m &\equiv (y_P - y_Q) \cdot (x_P - x_Q)^{-1} \pmod{p} \\ x_R &\equiv m^2 - x_P - x_Q \pmod{p} \\ y_R &\equiv y_P + m(x_R - x_P) \pmod{p} \\ P+Q &\equiv (x_R, -y_R \bmod p) \end{align*}\]

情况2：$P = Q$

\[\begin{align*} m &\equiv (3x_P^2 + a) \cdot (2y_P)^{-1} \pmod{p} \\ x_R &\equiv m^2 - 2x_P \pmod{p} \\ y_R &\equiv y_P + m(x_R - x_P) \pmod{p} \\ 2P &\equiv (x_R, -y_R \bmod p) \end{align*}\]

可以看到，这里与实数域点加法的变化就在于除法变成了乘逆元。

椭圆曲线的阶

这里引入了一个很重要的概念，椭圆曲线群的阶：有限域 $\mathbb{F}_p$ 上的椭圆曲线群 $E(\mathbb{F}_p)$ 中，所有元素的总数，包括无穷远点 $O$，记为 $N$。

简单说，就是曲线上有多少点。

如果让x从0到p-1逐个枚举是否点在曲线上（模p下二次剩余），复杂度为$O(p)$，当p很大时无法完成。

对此，有能在多项式时间内计算椭圆曲线阶的算法Schoof算法以及它的进阶版本Schoof-Elkies-Atkin（SEA）算法。所以，我们能轻松的计算有限域上椭圆曲线的阶。

数乘与循环子群

如果在有限域上的椭圆曲线，对点P进行数乘，那么将会出现循环的性质：

例子：

曲线：$y^2 \equiv x^3 + 2x + 3 \pmod{97}$
点：$P=(3,6)$

我们来手动计算P的所有倍乘，验证原文的结果：

$1P = (3,6)$
$2P=(80, -87 \bmod 97)=(80,10)$
$3P=(80, -10 \bmod 97)=(80,87)$
$4P=(3, -6 \bmod 97)=(3,91)$
$5P=O$ P的倍乘只有5个不同的点：${O, P, 2P, 3P, 4P}$，然后开始循环：$6P=P, 7P=2P, \dots$

有以下重要性质：

$kP = (k \bmod n)P$
n倍的P相加，结果仍然是P的倍数。

从而，nP的集合是椭圆曲线形成的群里的一个具有循环性质的子群，P称作这个循环子群的基点。

我们先定义椭圆曲线上某点的阶：对于椭圆曲线上的一个点P，最小的正整数n，使得 $nP=O$，称为点P的阶。无穷原点0的阶为1。

循环子群的阶，就为这个循环子群基点的阶。

循环子群的阶与椭圆曲线的阶有一定关系，拉格朗日定理告诉我们： 循环子群的阶n，一定整除整个椭圆曲线的阶N。

因此，对于已知的基点P，我们有一套方法来找它生成的循环子群的阶：

使用Schoof的算法去计算椭圆曲线的阶$N$。
找到$N$所有的因子。
对于$N$的每一个因子$n$ ,计算$nP$。
找到最小的满足$nP=0$的n，n就是循环子群的阶。

找基点

在ECC中，我们通常想要高效，可控的找到一个大素数阶循环子群的基点G。

为什么要大素数阶呢，如果为小素数，则可以暴力破解，如果为合数，则可利用Pohlig-Hellman算法，这也是这道题目的漏洞之一。

先分解椭圆曲线的阶N，找一个最大素因子n。辅因子h是椭圆曲线的阶N和子群的阶n的比值： $h = \frac{N}{n}$ 根据拉格朗日定理，n一定整除N，所以h永远是正整数。

对于椭圆曲线群中的任意一个点P，显然有： $NP = O$

把N写成h·n，代入上式： $(h \cdot n)P = O \implies n \cdot (hP) = O$ 这个式子告诉我们一个事实：

对于曲线上任意点P，点 $G = hP$ 一定满足 $nG = O$。也就是说，G的阶一定整除n。

而n为素数，所以G的阶只能是1或n。显然阶不可能是1，所以选择基点hP，则它的阶一定为大素数n。

总结一下找基点的算法：

计算椭圆曲线的阶N。
选择一个阶为n的子群。n必须是素数且必须是N的因子。
计算辅因子h=N/n。
在曲线上选择一个随机的点P。
计算G=hP。
如果G是0，那么回到步骤4。否则我们就已经找到了阶为n和辅因子是h的子群的生成器/基点。

椭圆曲线离散对数问题

给定椭圆曲线上的一个基点 $G$（生成元）和一个点 $Q$，找到整数 $k$，使得： $Q = kG$

Q是公钥，k是随机生成的私钥。正向求公钥简单，但已知公钥反向求私钥很困难。

和普通离散对数问题进行对比：

特性	离散对数问题（DLP）	椭圆曲线离散对数问题（ECDLP）
所在群	模 $p$ 乘法群 $\mathbb{F}_p^\times$	椭圆曲线循环子群 $\langle G \rangle$
基本运算	模幂运算 $a^k \pmod{p}$	标量乘法 $kG$
问题形式	已知 $a, b$，求 $k$ 使得 $b=a^k \pmod{p}$	已知 $G, Q$，求 $k$ 使得 $Q=kG$
求解算法	数域筛法（子指数时间算法）	Pollard’s Rho算法（全指数时间算法）

在有限域上的对数问题比实数域上的难很多，因为实数域上的可以根据有意义的图像进行求解，而有限域上的图像没有规律，是一堆散乱的点。

椭圆曲线的安全性与攻击方法

椭圆曲线参数

所有椭圆曲线密码算法，都运行在一个预先定义好的有限域椭圆曲线循环子群上。这个子群的所有属性，都由一个六元组完全描述： $(p,\ a,\ b,\ G,\ n,\ h)$

p为有限域Fp的阶
a，b为椭圆曲线方程的参数
G为基点
n为循环子群的阶
h为辅因子

另外，还有一个重要的概念嵌入度：对于有限域 $\mathbb{F}_p$ 上的椭圆曲线，以及曲线上一个阶为素数n的点G（我们实际使用的基点），嵌入度k是满足以下条件的最小正整数： $\boldsymbol{n \mid p^k - 1}$

由定义可知嵌入度是针对循环子群的属性。根据费马小定理，嵌入度也一定存在。

嵌入度影响的是DLP的破解难度，如果嵌入度较小，则可以把有限域上的ECDLP转换成DLP，使用数域筛法快速破解。

对于256位安全级别的椭圆曲线，嵌入度k必须大于12。

常见攻击方法

攻击名称	针对的阶	核心攻击条件
Smart攻击	椭圆曲线本身的阶N	$N = p$（反常曲线）
MOV攻击	椭圆曲线本身的阶N	嵌入度很小（通常≤6）
FR攻击	椭圆曲线本身的阶N	嵌入度很小
GLV攻击	椭圆曲线本身的阶N	曲线有高效的自同态，N的分解有特殊结构
Pohlig-Hellman攻击	基点的阶n	n有小素因子
小子群攻击	基点的阶n	n很小，或者曲线中存在其他小阶子群

下面是可以计算椭圆曲线某基点各参数的代码：

def analyze_elliptic_curve(p, a, b, base_point):
    F = GF(p)
    E = EllipticCurve(F, [a, b])
    print(f"曲线: y^2 = x^3 + {a}x + {b}  (mod {p})")
    print(f"基点: G = {base_point}")
    try:
        G = E(base_point)  
    except ValueError:
        raise ValueError(f"点 {base_point} 不在椭圆曲线上")

    if G.is_zero():
        return {
            "curve": E,
            "curve_order": E.order(),
            "base_point": G,
            "subgroup_order": 1,
            "cofactor": E.order(),
            "embedding_degree": 1
        }
    N = E.order()
    print(f"\n1.椭圆曲线本身的阶 N = {N}")
    print(f"N的素因子分解: {factor(N)}")

    n = G.order()
    print(f"\n2.基点G的阶 n = {n}")
    print(f"n的素因子分解: {factor(n)}")

    if N % n != 0:
        raise RuntimeError("不符合拉格朗日定理")

    h = N // n
    print(f"辅因子 h = N / n = {h}")

    k = Mod(p, n).multiplicative_order()
    print(f"\n3.嵌入度 k = {k}")

    

    return {
        "curve": E,
        "curve_order": N,
        "base_point": G,
        "subgroup_order": n,
        "cofactor": h,
        "embedding_degree": k
    }

my_p = 
my_a = 
my_b = 
my_G = (x,y)


result = analyze_elliptic_curve(
    p=my_p,
    a=my_a,
    b=my_b,
    base_point=my_G
)

ECDH

ECDH 是椭圆曲线的Diffe-Hellman算法的变种。

我们需要解决的问题通常是这样的：Alice 和 Bob 想要安全通信，中间人可能会窃听消息，但是没办法解密消息。

ECDH的流程：

Alice 和 Bob 生成各自的私钥和公钥，Alice 的私钥为 $d_A$，公钥为 $H_A = d_A G$。Bob 的私钥为 $d_B$，公钥为 $H_B = d_B G$，注意，Alice 和 Bob 需要使用一样的主要参数：在同一条曲线的同一个有限域上选择一样的基点 G。
Alice 和 Bob 通过不安全信道交换各自的公钥$H_A$ 和 $H_B$，中间人可以窃听到 $H_A$ 和 $H_B$，但是在无法攻破离散对数难题的情况下无法得到 $d_A$ 和 $d_B$。
Alice 计算 $S = d_A H_B$（使用自身的私钥和 Bob 的公钥），Bob 计算 $S = d_B H_A$（使用自身的私钥和 Alice 的公钥），双方求得的 S 是一样的，因为 $S = d_A H_B = d_A(d_B G) = d_B(d_A G) = d_B H_A$

中间人只知道 $H_A$ 和 $H_B$ 以及椭圆的公共参数，是无法算出共享密钥 S 的，这其实就是笛福赫尔曼问题：

给定三个点 P，aP，bP，那么 abP 的结果是什么？

虽然没有数学证明直接说明椭圆曲线上的笛福赫尔曼问题是困难的，但是这个问题已经被公认为是个困难问题。

在有了共享密钥后，可以使用对称加密算法进行通信。

学习参考资料：

Elliptic Curve Cryptography: a gentle introduction - Andrea Corbellini

Elliptic Curve Cryptography: finite fields and discrete logarithms - Andrea Corbellini

Elliptic Curve Cryptography: ECDH and ECDSA - Andrea Corbellini

本文由作者按照 CC BY 4.0 进行授权