ECC的数学须知

AiY0u2025-07-202025-07-22

椭圆曲线密码学(Elliptic Curve Cryptography,ECC)

是一种基于椭圆曲线数学理论的非对称加密算法。它和我们已经学习过的RSA一样，依靠陷门函数来保证加密算法的安全性。

要学习ECC，我们先要学习一些前置知识

椭圆曲线

它并非指椭圆的边界线，而是指满足特定方程的曲线。

最基础的研究场景是复数域，在其中椭圆曲线的标准方程为：
y²=x³+ax+b（Weierstrass形式）

a和b为常数，且满足Δ=−16(4a³+27b²)≠0(非奇异条件)

曲线方程有多种形式。这里只给出了Weierstrass形式

而在实际应用中，椭圆曲线一般定义在有限域上，此时该方程在有限域内进行。

我们知道有限域内的元素是有限个，因此椭圆曲线作为一种点的集合，其中的点也是有限个。

同时，该椭圆曲线满足非奇异条件确保曲线上每个点都有唯一一条切线（后面会用到）

点加法

我们在椭圆曲线所在的有限域上定义运算“点加法”

倘若我们在椭圆曲线上寻找两个点P和Q，做直线PQ与椭圆曲线交于第三点R，然后再对R的y值取相反数，得到R’

那我们就说P+Q = R’

那么如果出现直线PQ与椭圆曲线没有第三个交点呢？

我们定义一个无穷远的点O，作为该加法的单位元，即对任意点P，有P+O = P

那么如果是P+P呢？

我们做出P点的切线，和前面两种情况一样，找该切线与椭圆曲线的交点

同时P+P我们称之为点的倍乘，点的多次倍乘拓展为标量乘法

kP = P+P+P+P+……

至此我们已经摸到了椭圆曲线的核心：

标量乘法容易计算，而已知kP和P求k极其困难

这就构成了一个陷门函数，我们利用它来进行加密

代数计算公式

我们已经知道了点加法的定义，显然上述定义是从几何直观上来讲的，我们需要具体计算R点的坐标还是需要使用代数方法求解

方法很简单：已知P(x1,y1),Q(x2,y2) p≠Q

设直线斜率 $\lambda = \frac{(y_2-y_1)}{(x_2-x_1)}$

那么直线方程为： $y = \lambda(x-x_1) + y_1$

与椭圆曲线方程联立，消去y以后展开多项式

平方项的系数为 $-\lambda^2$

有三次方程的韦达定理，可知 $x_1+x_2+x_3=\lambda^2$

$x_3 = \lambda^2-x_1-x_2$

再将x3代入直线表达式，很容易得到

$y_3 = \lambda(x_1-x_3)-y_1$

综上：

$x_3 = \lambda^2 - x_1 - x_2 \\ y_3 =\lambda(x_1-x_3)-y_1$

而在P=Q的情况下，x1 = x2 ，y1 = y2

我们的计算公式和上面完全一致

只是m根据求切线斜率应当为 $\lambda = \frac{(3x_1^2+a)}{2y_1}$

python实现：

from gmpy2 import invert

def point_add(p,q,a,n):  #p和q使用元组
    if p == (0,0):
        return q
    elif q == (0,0):
        return p
    else:
        x1 = p[0]
        y1 = p[1]
        x2 = q[0]
        y2 = q[1]
    if x1 == x2 and y1 == n-y2:
        return (0,0)
    else:
        if p != q:
            k = (y2-y1)*invert((x2-x1),n)
        else:
            k = (3*x1*x1 + a)*invert((2*y1))
    x3 = (k*k - x1 -x2) % n
    y3 = (k*(x1 - x3) - y1) % n
    return (x3,y3)

密钥交换流程

ECC的密钥交换流程与DH的有点像，可以拿来比对记忆

Alice和Bob确定要使用的有限域和椭圆曲线（并且确定好了点P）
Alice选定随机数 $k_a$ ，并计算 $k_ap$ 的坐标，记为A发送给Bob
Bob选定随机数 $k_b$ ,并计算 $k_bp$ 的坐标，记为B发送给Alice
Alice计算 $s_1=k_aB=k_ak_bp$

Bob计算 $s_2=k_bA=k_ak_bp$

这样它们就实现了密钥交换