1. 从三次方程到椭圆曲线为什么这东西值得研究我最早接触椭圆曲线纯属被名字坑了。当年在资料里看到“椭圆曲线”四个字第一反应是画一条扁扁的椭圆结果发现自己根本画不出来还把方程 y² x³ ax b 丢进绘图软件出来的曲线是一段一段弯来弯去的波浪。后来才搞清楚这东西和椭圆的关系非常遥远只是历史沿革留下的一个名字。但这不妨碍它成为整个数论、代数几何和现代密码学里最炙手可热的结构之一几乎所有做数学或计算机方向的人都绕不开它。这篇文章我想聊聊椭圆曲线以及它身上最重要的代数结构群结构。你可以把它理解成在一条曲线上定义一种加法让所有点之间可以进行运算而这个运算满足交换律、结合律、有单位元、有逆元。一旦这个结构立住椭圆曲线就从一个静态的几何图形变成一个可以“做算术”的代数对象。这篇文章适合谁看呢如果你是数学系低年级学生、自学密码学的程序员、或者对抽象代数和数论感兴趣但一直没找到入口的爱好者都很合适。我会尽可能把群论里那些绕口的概念用几何和算例讲清楚还会附上可以直接运行的代码带你亲手算一遍椭圆曲线上的加法。我建议你先在纸上写下这个方程y² x³ ax b。等号右边是x的三次多项式等号左边是y的平方。这看起来只是多项式但它的形状非常特殊。为了让这条曲线“好相处”我们通常要求右边三次多项式没有重根也就是判别式不发生退化这一步后续会详细讲。一旦这个条件成立再补上一个人为规定的“无穷远点”整条曲线上的点就能构成一个阿贝尔群也就是交换群。这是椭圆曲线能成为密码学基石的核心原因一个庞大但封闭的有限集合加上一种难以逆转的运算恰好就是很多安全协议需要的“舞台”。1.1 椭圆曲线的标准形式为什么长这样椭圆曲线的标准形式通常写成 y² x³ ax b这叫做魏尔斯特拉斯Weierstrass标准型。你可能疑惑为什么一定要y的平方配上x的三次方这背后的原因其实和椭圆积分的历史有关。早先数学家在研究椭圆周长时遭遇了形如 ∫ dx / √(x³ ax b) 这类积分。这类积分的反函数定义出来的曲线被叫作椭圆曲线。后来人们发现研究这类曲线时直接把它写成代数方程更省事于是就把目光聚焦到 y² x³ ax b 这条光滑的三次曲线上。你可以把“椭圆”二字理解为它的历史血统而不是它的几何形状。真正在坐标平面上画出来它更像一条扭来扭去的三次曲线。从代数结构的角度看这个方程之所以“好用”是因为三次曲线有一个非常棒的几何性质一条直线如果穿过曲线上两个点它必然还会穿过第三个点在复数域上计数偶尔会重合需要算重数。这个二推三的性质是后面定义群运算的关键素材。如果是二次曲线这条性质不成立如果次数超过三计算又太复杂。三次正好卡在“简单但结构丰富”的甜点上。1.2 从积分到曲线名字里藏着的历史包袱简单说说历史。椭圆曲线的名号源于椭圆周长计算中出现的椭圆积分。很多教材会一笔带过但我觉得知道来龙去脉有助于你想明白为什么曲线和“椭圆”纠缠不清。椭圆在第一象限的参数方程可以写成 x a·sinθy b·cosθ弧长积分算下来会出现 √(1 - k²sin²θ) 这类根式。换元整理后积分中就出现了三次多项式的平方根。十九世纪阿贝尔和雅可比等数学家在研究这类积分时发现它们的反函数具有“加法性质”也就是两个积分值相加可以通过解一个代数方程得到第三个值。这个加法性质最终被抽象成椭圆曲线上的群运算。知道了这段历史你再看椭圆曲线的群运算就不会觉得它凭空而降。它其实是古代椭圆积分加法公式的几何化版本。数学家们发现把积分反函数定义的点放在曲线的坐标系上它们的“加法”恰好就是几何上三点共线的规律。这样一来椭圆的物理问题、曲线的代数方程、点的群运算三个看似无关的东西就串成了一条线。2. 点集的群结构如何给曲线上的点做加法现在进入正题。椭圆曲线的点集能带上一个群结构这是它最迷人的地方。群这个抽象代数概念许多人在抽象代数课程里学过但不知道它怎么落到具体的几何对象上。椭圆曲线是个特别好的例子它的元素就是曲线上的点运算则是定义在几何画法之上的“加法”。先想象一条椭圆曲线y² x³ - x坐标平面上有它的图像。现在我们给曲线上的任意两个点P和Q定义一个“加法”结果R。几何步骤如下用一条直线连接P和Q如果P等于Q就用曲线在P点的切线这条直线一定会与曲线产生第三个交点设为S。接下来把S关于x轴做对称对称后的点就是P Q的结果R。这里对称操作不是为了好看而是为了确保群运算的单位元能够自然出现这一点我马上解释。这套几何定义做了两件关键的事。第一它把直线的“三交点”性质和群的封闭性绑定。任何两个点加出来的结果仍然在曲线上绝不会跑出去。第二它让“无穷远点”成为加法单位元。如果你取P的对称点-P则P和(-P)的连线是一条竖直直线。从图形上看这条竖直线与曲线的交点是P、-P以及无穷远点。规定P (-P) 无穷远点等价于把S第三个交点对x轴对称回来结果就是“无穷远方向的点”。这样一来逆元的存在性也有了。2.1 几何视角下的加法规则连线、取交点、做镜像我从实际操作的角度把加法步骤复述一遍。设曲线上有两点P(x₁, y₁)和Q(x₂, y₂)。如果P ≠ Q连接P和Q画一条直线。这条直线与椭圆曲线相交于第三个点S。将S沿x轴翻折到曲线另一侧的对称点即得到P Q。如果P Q也就是要计算“倍点”2P P P就改成过P点作曲线的切线切线与曲线的另一个交点S翻折后得到2P。为什么非要翻折这里有个特别巧妙的逻辑。如果只取直线与曲线的三个交点直接定义“第三个交点为和”那这个运算不满足交换律吗其实是满足的因为连线谁先谁后不影响第三个交点。但它带来的单位元问题不好处理。你算P (-P)时第三个交点恰好是无穷远点如果把无穷远点当作结果那它就天然成为单位元。但这样定义出来的看起来更像“三元运算”。翻折一次之后运算就变成标准的二元运算而且单位元非常清晰。你可以拿尺规在纸上画一条具体的曲线然后选两个点实测一下。找一条光滑的椭圆曲线用直尺连线肉眼判断第三个交点再关于x轴对称检验加出来的点是否还落在曲线上。我当初这么干了很多次才真正接受这套几何定义不只是一个花架子它背后有着严密的代数逻辑支撑。2.2 代数公式把画图变成坐标运算几何画法虽然直观但想要编程实现或者严格计算就必须落成坐标公式。假设曲线为 y² x³ ax b且P ≠ Q令连接P和Q的直线斜率为λ (y₂ - y₁)/(x₂ - x₁)则P Q的坐标满足x₃ λ² - x₁ - x₂y₃ λ(x₁ - x₃) - y₁。这里x₃和y₃就是P Q的结果。看起来简单但它背后其实走了一遍直线代入曲线方程、解三次方程求根的过程。三次方程的三个根分别是x₁、x₂和x₃利用韦达定理就能得到上述公式。如果是倍点P Q令λ (3x₁² a)/(2y₁)则x₂P λ² - 2x₁y₂P λ(x₁ - x₂P) - y₁。手动推一遍可能更好理解。把直线方程y λ(x - x₁) y₁代入曲线方程整理后是一个关于x的三次方程。因为已知两根x₁和x₂或倍点时两根都是x₁用韦达定理求出第三根x₃再代回直线方程求出y₃。看到这个推导过程你就会明白为什么前面强调曲线必须是三次方程为什么判别式必须非零因为一旦退化成带尖点的曲线切线斜率可能不存在整个公式组就崩溃了。2.3 群公理的验证为什么它真的能构成群我直接给结论椭圆曲线上的点集构成一个阿贝尔群单位元是无穷远点O逆元是(x, y)对应的(x, -y)。这里我稍稍展开讲毕竟是“代数结构”这篇文章的核心。封闭性两个点相加的结果还是一个点由公式保证。交换律连线不受方向影响公式也不依赖谁先谁后当然成立。结合律这是最复杂的。几何上可以用九点定理证明代数上则是暴力计算。让人欣慰的是结合律确实成立但绝不是“一眼就能看出来”的。我建议你找一本椭圆曲线教材看看结合律的证明哪怕是看个大概也会对群结构有更深理解。单位元O P P需要特别处理。如果P是无穷远点或者P和Q是竖直对称点直接用公式会除零所以要单独判断。逆元P(x, y)的逆元是(x, -y)因为P (x, -y) O。注意到这些点以后你会理解为什么教科书总要强调“添加无穷远点”。没有无穷远点群的单位元无法在坐标系里直观呈现逆元的定义也不完整。从几何上看无穷远点是所有竖直方向的公共交汇点。从代数射影几何来看它把仿射平面补全成射影平面让所有直线“都有交点”从而让很多论证变得干净利落。3. 实操环节用Python亲手实现群运算数学定义再漂亮不落在代码里总觉得不够踏实。这一节我分享一段可以直接运行的Python代码用来在实数域的椭圆曲线上做点加法和倍点运算。虽然密码学中真正使用的通常是有限域上的椭圆曲线但先搞懂实数的版本后面转有限域就很容易。我选的曲线是 y² x³ - x其中a -1b 0。这条曲线好处是判别式不为零且有很多整数点方便验证。class EllipticCurvePoint: def __init__(self, x, y, a, b): self.x x self.y y self.a a self.b b # 检查点是否在曲线上排除无穷远点的情况 if self.y is not None and self.y**2 ! self.x**3 self.a * self.x self.b: raise ValueError(f点({x}, {y})不在曲线 y^2 x^3 {a}x {b} 上) def __eq__(self, other): return self.x other.x and self.y other.y and self.a other.a and self.b other.b def __add__(self, other): if self.a ! other.a or self.b ! other.b: raise ValueError(两条不同的曲线上的点不能相加) # 处理无穷远点 if self.y is None: return other if other.y is None: return self # 处理逆元相加 if self.x other.x and self.y -other.y: return EllipticCurvePoint(None, None, self.a, self.b) # 倍点公式 if self other: if self.y 0: return EllipticCurvePoint(None, None, self.a, self.b) lam (3 * self.x**2 self.a) / (2 * self.y) else: lam (other.y - self.y) / (other.x - self.x) x3 lam**2 - self.x - other.x y3 lam * (self.x - x3) - self.y return EllipticCurvePoint(x3, y3, self.a, self.b)上面这段代码用了直接的操作逻辑没有重载运算符。使用起来是这样# 定义曲线 y^2 x^3 - x 上的两个点 a, b -1, 0 P EllipticCurvePoint(0, 0, a, b) Q EllipticCurvePoint(1, 0, a, b) # 注意P和Q都在x轴上它们的和会怎样实际测试的时候我建议选一些不在x轴上的点比如(2, √6)之类的否则很容易遇到加出来是无穷远点的情况不利于感受运算过程。比较直观的整数点其实不少比如(2, -2)这里我直接算一个更直观的例子。我选一条更方便验证的曲线 y² x³ 2x 3上面有一个点P (0, √3)但为了好算干脆我编一个带整点的例子y² x³ - 7x 10点P (1, 2)点Q (3, 4)。你可以验证这两个点确实在曲线上。用上面的公式手算一遍λ (4 - 2) / (3 - 1) 1x₃ 1² - 1 - 3 -3y₃ 1 × (1 - (-3)) - 2 2。所以P Q (-3, 2)。代入曲线方程验证一下(-3)³ - 7×(-3) 10 -27 21 10 4而y² 2² 4恰好成立。为了让你能快速玩起来我建议把上面的类保存为一个文件比如ecc.py然后写一段测试P EllipticCurvePoint(1, 2, -7, 10) Q EllipticCurvePoint(3, 4, -7, 10) R P Q print(R.x, R.y) # 输出应该是 -3, 2如果你想再体验一下结合律可以继续取一个点S然后分别计算(P Q) S和P (Q S)看看结果是否一致。我当初跑这个验证的时候心里其实捏了把汗毕竟理论证明和程序跑出来是两码事看到输出一致才彻底放心。3.1 带坐标的类型设计为什么用类而不是裸元组我用一个类来表示点而不是简单的(x, y)元组是为了把曲线参数a、b一起封装进去并且可以在构造时校验点是否在曲线上。这是我在实际写代码时踩过坑之后总结的经验。如果只用裸元组很容易出现把两条不同曲线的点加到一起的荒唐情况而且出了错误很难排查。把曲线参数放进点对象里相当于给每个点挂上了“身份标签”相加前先检查是否属于同一曲线代码的自解释性也强很多。另外类里我特意定义了__eq__方法否则Python会默认按对象身份比较两个坐标相同的点会被当作不同对象。这个坑虽然低级但新手很容易踩。如果你直接用元组就能天然避免但元组又没法携带曲线参数所以两害相权取其轻我还是选择了类。3.2 初步测试跑通最朴素的点加法我把上面手算的例子跑一遍curve_a, curve_b -7, 10 P EllipticCurvePoint(1, 2, curve_a, curve_b) Q EllipticCurvePoint(3, 4, curve_a, curve_b) R P Q print(R.x, R.y)输出应该是-3.0 2.0。这里出现浮点数很正常因为直线斜率λ通常不是整数。如果你想要高精度计算可以考虑用 fractions 模块或 sympy但初学阶段浮点足够。如果你想玩得更细可以自己写一个检验函数判断计算结果仍然落在曲线上def assert_on_curve(point, a, b): if point.y is None: return assert abs(point.y**2 - (point.x**3 a*point.x b)) 1e-9有了这个断言你可以在每次加法后都做验证确保程序没有bug。这一步虽然简单但能帮你建立自信尤其是后面填了负数、逆元、无穷远点等边界条件之后。4. 实操中常见的问题与排查技巧数学上干净利落的群运算落到代码和手算里总会遇到一堆边界情况。这一节我把自己踩过的坑和排查思路整理成清单方便你对照着检查。4.1 无穷远点怎么表示代码里的“None”与数学里的“O”无穷远点是椭圆曲线群的单位元。在代码里我选择把它表示为xNoneyNone并在加法函数里单独处理。这是最容易遗漏的一条分支。如果你忘了处理无穷远点那么当P (-P)时就会出现除零错误因为连接两点是竖直线斜率的分子为0还是分母为0要看你怎么定义。具体来说如果两个点满足x相等、y互为相反数代码里如果直接走一般公式分母x₂ - x₁ 0程序直接崩溃。我的处理方式是先判逆元再判倍点最后才走一般公式。排查这类问题的技巧是写一组测试用例覆盖P O、O P、P (-P)、O O四种情况确保输出符合群的公理P O PO P PP (-P) OO O O4.2 切线斜率不存在的情况如何正确做倍点计算2P时公式要求使用切线斜率λ (3x₁² a)/(2y₁)。如果y₁恰好等于0那就意味着P点在x轴上此时切线是竖直的切线与曲线的第三个交点就是无穷远点。数学上2P O代码里如果不做判断分母为0也会崩溃。所以在倍点分支里我先判断y是否等于0如果是就直接返回无穷远点。很多资料里会提到“特征2和特征3的椭圆曲线公式不同”这里先不用管那么深但在实数域上y0这个边界必须处理。我在代码中已经写了if self.y 0的判断就是为了避免这个坑。4.3 曲线必须非奇异判别式为何不能为零三次方程x³ ax b如果有重根曲线就会出现尖点或自交点这种曲线叫奇异曲线。奇异曲线上的群结构会塌掉因为几何上“第三个交点唯一性”被破坏了。判别式Δ -16(4a³ 27b²)由于常数-16在特征不为2、3的域上不影响是否为零一般直接说4a³ 27b² ≠ 0即可。例如y² x³这条曲线a 0b 0判别式为0它在原点有一个尖点不能用椭圆曲线群运算。我在上面代码的构造函数里没有加这个检查严格来说应该加上。建议你实际使用的时候补一个判断if 4a**3 27b**2 0: raise ValueError(奇异曲线)。排查技巧当你发现某个点代入曲线恒成立但加法结果总是怪异时先检查是不是曲线选错了。我做过一次y² x³的实验计算结果乱成一锅粥后来才回想起是尖点破坏了群律。4.4 有限域上的计算为什么实数上没问题一上密码学就变了上面所有公式在实数域上都能跑通但密码学里使用的却是有限域上的椭圆曲线记作GF(p)或GF(2^m)。原因很简单实数域上的点有无穷多个计算机没法枚举也无法保证计算难度。而有限域上的点虽然也多但有限且离散对数问题比有限域乘法更难以拆解。从实数域切换到有限域核心公式基本不变只是把加、减、乘、除换成模运算。除法的逻辑要改成模逆运算比如计算斜率λ (y₂ - y₁)/(x₂ - x₁)时分母实际上是乘以它的模逆元。我建议你先在实数域把代码调通然后再扩展成模算术版本。如果直接上有限域一旦出bug很难分辨是数学问题还是编码问题。这里给一个模逆运算的实现提示。设模为p用扩展欧几里得算法求inv(a, p)然后乘法代替除法。如果使用Python 3.8以上版本可以直接用pow(a, -1, p)。4.5 快速排查清单我把自己排查问题时常用的检查项整理成一个表症状可能原因检查方法除零错误两个点x坐标相同但y相反在一般加法前判断逆元结果不在曲线上曲线判别式为0或构造函数没校验检查4a³ 27b²是否为零单位元错乱没有处理无穷远点或无穷远点表示冲突跑一遍P O、O P的用例倍点结果异常y0时未做边界处理测试x轴上交点的倍点结合律不成立可能用了错误曲线参数随机取3个点验证结合律5. 群结构为何重要从数学结构到密码学应用讲完了群运算和代码实现我想把视野拉高一点谈谈这个代数结构到底有什么用。为什么金融系统、数字签名、区块链密钥体系里都能看到椭圆曲线的影子关键在于一个问题给定曲线上一点P和一个整数k计算kP是很容易的就是从P开始反复加法。但反过来给你P和kP让你反推出k这就非常难了。这个问题叫椭圆曲线离散对数问题ECDLP。它的“难”与群结构本身密切相关。在实数域上这个反推问题没有密码学意义因为点坐标是浮点数误差会放大但在有限域上点的集合是有限的运算无法借助实分析的逼近手段目前也没有多项式时间算法能解决暴力尝试又是天文数字级别的规模。所以你会发现群结构提供了“加法”这种运算方式而有限域提供了“离散”的集合。两者结合才催生了ECC密码体制。经典场景是密钥协商双方各自选一个私钥k₁和k₂公开参数P然后互相交换k₁P和k₂P双方都能算出共享密钥k₁k₂P但窃听者拿不到k₁和k₂无法高效算出同样的值。需要特别注意的是密码学中使用的曲线参数都是经过严格挑选的并非随便拿一条曲线就能用于安全通信。实际系统里常见的曲线如P-256、secp256k1都是经过特殊设计避开弱曲线以及各种攻击面。除了密码学椭圆曲线的群结构在数论里还有更深的用处。一个经典结论是定义在有限域上的椭圆曲线的点数N满足 |N - (p1)| ≤ 2√p这叫做Hasse界。这个结论之所以重要是因为它告诉我们曲线上的点不会太多也不会太少。点数的精确计算算法如Schoof算法就是基于群结构做各种模运算和除法最后推出精确点数。你看从一条曲线到一个群再到计数、协议设计整个故事线都串起来了。5.1 为什么有限域上的点构成有限群实数域上椭圆曲线有无数个点怎么换到有限域变成有限群呢因为有限域GF(p)本身就只有p个元素点的坐标(x, y)都落在GF(p)里所以最多只有p²个点再加无穷远点总数有限。每两个点加法结果仍然落在这个有限集里所以它天然就是有限群。理解这个转变之后你就会明白一个很微妙的事情有限域上的椭圆曲线图形不再是连续曲线而是一堆离散点组成的集合。所谓“曲线”只是一个名字真实场景里是一堆满足方程的点的集合。这一点初学者特别容易误解以为密码学里用的“椭圆曲线”还是一条可以画出来的平滑曲线其实根本不是。我建议你找个小素数p17枚举一下y² x³ 2x 3在GF(17)上的点亲眼看到点集是离散的才能真正接受这个事实。5.2 结合律在密码学中的意义标量乘法能够安全展开密码学里计算kP时通常使用“倍增与累加”的方法把k写成二进制从高往低扫描每次对当前点做倍点遇到1就多加一个P。这个过程之所以成立完全依赖群运算的结合律。如果结合律不成立简单的重复加法就会出现歧义根本没法安全展开。你可能觉得“结合律是群的基本要求有什么可稀罕的”。但在椭圆曲线上结合律并不是免费的午餐正是这套几何加法的精妙之处。撰写标准库、设计加密协议的工程师们最先验证的往往就是参数曲线上的群运算是否正确实现因为他们知道任何一点微小的错误都会破坏这个基础。6. 写在最后我踩过的一些坑和给你的练习建议聊了这么多关于椭圆曲线和代数结构的美妙之处我还有一个很深的体会很多人一上来就学有限域上的群运算结果被一堆模运算细节淹没反而忘了背后的几何直觉。我的建议是先在实数域上用“连线取交点再对称”的方式理解群运算手推两三个例子再用代码验证最后再切换到有限域。这个顺序能帮你把抽象代数中的群概念牢牢锚定在一个可见、可算的几何对象上。我当年最容易混淆的概念是群运算的单位元为什么是无穷远点而不是(0, 0)。后来我画了很多图又手工算了几次P (-P)才彻底明白。对初学者来说这部分需要用一点耐心因为它实在太反直觉了。如果一次没理解不妨把手算的每一步写清楚尤其是处理无穷远点的分支别跳过。至于后续扩展你可以从两条路线继续往下走。一条是往代数数论方向研究椭圆曲线的秩、Torsion子群、Mordell定理另一条是往应用密码学方向去读secp256k1的参数文档自己实现一个有限域上的点加法和标量乘法然后跑一遍密钥协商协议。这两条路线都很能锻炼人而且会不断加深你对“代数结构如何赋能实际问题”的理解。最后再分享一个小技巧当你写代码或者手算遇到奇怪的不一致时先用“结合律”做一次冒烟测试。随机生成三个点P、Q、R验证(P Q) R等于P (Q R)。如果这一步都过不了其他任何结论都不可信。群运算就像一台精密的机器结合律是它的轴承一旦轴承坏掉整台机器都会散架。先保住这个核心你后续的探索会顺畅很多。
椭圆曲线与群结构：从几何加法到密码学实践
1. 从三次方程到椭圆曲线为什么这东西值得研究我最早接触椭圆曲线纯属被名字坑了。当年在资料里看到“椭圆曲线”四个字第一反应是画一条扁扁的椭圆结果发现自己根本画不出来还把方程 y² x³ ax b 丢进绘图软件出来的曲线是一段一段弯来弯去的波浪。后来才搞清楚这东西和椭圆的关系非常遥远只是历史沿革留下的一个名字。但这不妨碍它成为整个数论、代数几何和现代密码学里最炙手可热的结构之一几乎所有做数学或计算机方向的人都绕不开它。这篇文章我想聊聊椭圆曲线以及它身上最重要的代数结构群结构。你可以把它理解成在一条曲线上定义一种加法让所有点之间可以进行运算而这个运算满足交换律、结合律、有单位元、有逆元。一旦这个结构立住椭圆曲线就从一个静态的几何图形变成一个可以“做算术”的代数对象。这篇文章适合谁看呢如果你是数学系低年级学生、自学密码学的程序员、或者对抽象代数和数论感兴趣但一直没找到入口的爱好者都很合适。我会尽可能把群论里那些绕口的概念用几何和算例讲清楚还会附上可以直接运行的代码带你亲手算一遍椭圆曲线上的加法。我建议你先在纸上写下这个方程y² x³ ax b。等号右边是x的三次多项式等号左边是y的平方。这看起来只是多项式但它的形状非常特殊。为了让这条曲线“好相处”我们通常要求右边三次多项式没有重根也就是判别式不发生退化这一步后续会详细讲。一旦这个条件成立再补上一个人为规定的“无穷远点”整条曲线上的点就能构成一个阿贝尔群也就是交换群。这是椭圆曲线能成为密码学基石的核心原因一个庞大但封闭的有限集合加上一种难以逆转的运算恰好就是很多安全协议需要的“舞台”。1.1 椭圆曲线的标准形式为什么长这样椭圆曲线的标准形式通常写成 y² x³ ax b这叫做魏尔斯特拉斯Weierstrass标准型。你可能疑惑为什么一定要y的平方配上x的三次方这背后的原因其实和椭圆积分的历史有关。早先数学家在研究椭圆周长时遭遇了形如 ∫ dx / √(x³ ax b) 这类积分。这类积分的反函数定义出来的曲线被叫作椭圆曲线。后来人们发现研究这类曲线时直接把它写成代数方程更省事于是就把目光聚焦到 y² x³ ax b 这条光滑的三次曲线上。你可以把“椭圆”二字理解为它的历史血统而不是它的几何形状。真正在坐标平面上画出来它更像一条扭来扭去的三次曲线。从代数结构的角度看这个方程之所以“好用”是因为三次曲线有一个非常棒的几何性质一条直线如果穿过曲线上两个点它必然还会穿过第三个点在复数域上计数偶尔会重合需要算重数。这个二推三的性质是后面定义群运算的关键素材。如果是二次曲线这条性质不成立如果次数超过三计算又太复杂。三次正好卡在“简单但结构丰富”的甜点上。1.2 从积分到曲线名字里藏着的历史包袱简单说说历史。椭圆曲线的名号源于椭圆周长计算中出现的椭圆积分。很多教材会一笔带过但我觉得知道来龙去脉有助于你想明白为什么曲线和“椭圆”纠缠不清。椭圆在第一象限的参数方程可以写成 x a·sinθy b·cosθ弧长积分算下来会出现 √(1 - k²sin²θ) 这类根式。换元整理后积分中就出现了三次多项式的平方根。十九世纪阿贝尔和雅可比等数学家在研究这类积分时发现它们的反函数具有“加法性质”也就是两个积分值相加可以通过解一个代数方程得到第三个值。这个加法性质最终被抽象成椭圆曲线上的群运算。知道了这段历史你再看椭圆曲线的群运算就不会觉得它凭空而降。它其实是古代椭圆积分加法公式的几何化版本。数学家们发现把积分反函数定义的点放在曲线的坐标系上它们的“加法”恰好就是几何上三点共线的规律。这样一来椭圆的物理问题、曲线的代数方程、点的群运算三个看似无关的东西就串成了一条线。2. 点集的群结构如何给曲线上的点做加法现在进入正题。椭圆曲线的点集能带上一个群结构这是它最迷人的地方。群这个抽象代数概念许多人在抽象代数课程里学过但不知道它怎么落到具体的几何对象上。椭圆曲线是个特别好的例子它的元素就是曲线上的点运算则是定义在几何画法之上的“加法”。先想象一条椭圆曲线y² x³ - x坐标平面上有它的图像。现在我们给曲线上的任意两个点P和Q定义一个“加法”结果R。几何步骤如下用一条直线连接P和Q如果P等于Q就用曲线在P点的切线这条直线一定会与曲线产生第三个交点设为S。接下来把S关于x轴做对称对称后的点就是P Q的结果R。这里对称操作不是为了好看而是为了确保群运算的单位元能够自然出现这一点我马上解释。这套几何定义做了两件关键的事。第一它把直线的“三交点”性质和群的封闭性绑定。任何两个点加出来的结果仍然在曲线上绝不会跑出去。第二它让“无穷远点”成为加法单位元。如果你取P的对称点-P则P和(-P)的连线是一条竖直直线。从图形上看这条竖直线与曲线的交点是P、-P以及无穷远点。规定P (-P) 无穷远点等价于把S第三个交点对x轴对称回来结果就是“无穷远方向的点”。这样一来逆元的存在性也有了。2.1 几何视角下的加法规则连线、取交点、做镜像我从实际操作的角度把加法步骤复述一遍。设曲线上有两点P(x₁, y₁)和Q(x₂, y₂)。如果P ≠ Q连接P和Q画一条直线。这条直线与椭圆曲线相交于第三个点S。将S沿x轴翻折到曲线另一侧的对称点即得到P Q。如果P Q也就是要计算“倍点”2P P P就改成过P点作曲线的切线切线与曲线的另一个交点S翻折后得到2P。为什么非要翻折这里有个特别巧妙的逻辑。如果只取直线与曲线的三个交点直接定义“第三个交点为和”那这个运算不满足交换律吗其实是满足的因为连线谁先谁后不影响第三个交点。但它带来的单位元问题不好处理。你算P (-P)时第三个交点恰好是无穷远点如果把无穷远点当作结果那它就天然成为单位元。但这样定义出来的看起来更像“三元运算”。翻折一次之后运算就变成标准的二元运算而且单位元非常清晰。你可以拿尺规在纸上画一条具体的曲线然后选两个点实测一下。找一条光滑的椭圆曲线用直尺连线肉眼判断第三个交点再关于x轴对称检验加出来的点是否还落在曲线上。我当初这么干了很多次才真正接受这套几何定义不只是一个花架子它背后有着严密的代数逻辑支撑。2.2 代数公式把画图变成坐标运算几何画法虽然直观但想要编程实现或者严格计算就必须落成坐标公式。假设曲线为 y² x³ ax b且P ≠ Q令连接P和Q的直线斜率为λ (y₂ - y₁)/(x₂ - x₁)则P Q的坐标满足x₃ λ² - x₁ - x₂y₃ λ(x₁ - x₃) - y₁。这里x₃和y₃就是P Q的结果。看起来简单但它背后其实走了一遍直线代入曲线方程、解三次方程求根的过程。三次方程的三个根分别是x₁、x₂和x₃利用韦达定理就能得到上述公式。如果是倍点P Q令λ (3x₁² a)/(2y₁)则x₂P λ² - 2x₁y₂P λ(x₁ - x₂P) - y₁。手动推一遍可能更好理解。把直线方程y λ(x - x₁) y₁代入曲线方程整理后是一个关于x的三次方程。因为已知两根x₁和x₂或倍点时两根都是x₁用韦达定理求出第三根x₃再代回直线方程求出y₃。看到这个推导过程你就会明白为什么前面强调曲线必须是三次方程为什么判别式必须非零因为一旦退化成带尖点的曲线切线斜率可能不存在整个公式组就崩溃了。2.3 群公理的验证为什么它真的能构成群我直接给结论椭圆曲线上的点集构成一个阿贝尔群单位元是无穷远点O逆元是(x, y)对应的(x, -y)。这里我稍稍展开讲毕竟是“代数结构”这篇文章的核心。封闭性两个点相加的结果还是一个点由公式保证。交换律连线不受方向影响公式也不依赖谁先谁后当然成立。结合律这是最复杂的。几何上可以用九点定理证明代数上则是暴力计算。让人欣慰的是结合律确实成立但绝不是“一眼就能看出来”的。我建议你找一本椭圆曲线教材看看结合律的证明哪怕是看个大概也会对群结构有更深理解。单位元O P P需要特别处理。如果P是无穷远点或者P和Q是竖直对称点直接用公式会除零所以要单独判断。逆元P(x, y)的逆元是(x, -y)因为P (x, -y) O。注意到这些点以后你会理解为什么教科书总要强调“添加无穷远点”。没有无穷远点群的单位元无法在坐标系里直观呈现逆元的定义也不完整。从几何上看无穷远点是所有竖直方向的公共交汇点。从代数射影几何来看它把仿射平面补全成射影平面让所有直线“都有交点”从而让很多论证变得干净利落。3. 实操环节用Python亲手实现群运算数学定义再漂亮不落在代码里总觉得不够踏实。这一节我分享一段可以直接运行的Python代码用来在实数域的椭圆曲线上做点加法和倍点运算。虽然密码学中真正使用的通常是有限域上的椭圆曲线但先搞懂实数的版本后面转有限域就很容易。我选的曲线是 y² x³ - x其中a -1b 0。这条曲线好处是判别式不为零且有很多整数点方便验证。class EllipticCurvePoint: def __init__(self, x, y, a, b): self.x x self.y y self.a a self.b b # 检查点是否在曲线上排除无穷远点的情况 if self.y is not None and self.y**2 ! self.x**3 self.a * self.x self.b: raise ValueError(f点({x}, {y})不在曲线 y^2 x^3 {a}x {b} 上) def __eq__(self, other): return self.x other.x and self.y other.y and self.a other.a and self.b other.b def __add__(self, other): if self.a ! other.a or self.b ! other.b: raise ValueError(两条不同的曲线上的点不能相加) # 处理无穷远点 if self.y is None: return other if other.y is None: return self # 处理逆元相加 if self.x other.x and self.y -other.y: return EllipticCurvePoint(None, None, self.a, self.b) # 倍点公式 if self other: if self.y 0: return EllipticCurvePoint(None, None, self.a, self.b) lam (3 * self.x**2 self.a) / (2 * self.y) else: lam (other.y - self.y) / (other.x - self.x) x3 lam**2 - self.x - other.x y3 lam * (self.x - x3) - self.y return EllipticCurvePoint(x3, y3, self.a, self.b)上面这段代码用了直接的操作逻辑没有重载运算符。使用起来是这样# 定义曲线 y^2 x^3 - x 上的两个点 a, b -1, 0 P EllipticCurvePoint(0, 0, a, b) Q EllipticCurvePoint(1, 0, a, b) # 注意P和Q都在x轴上它们的和会怎样实际测试的时候我建议选一些不在x轴上的点比如(2, √6)之类的否则很容易遇到加出来是无穷远点的情况不利于感受运算过程。比较直观的整数点其实不少比如(2, -2)这里我直接算一个更直观的例子。我选一条更方便验证的曲线 y² x³ 2x 3上面有一个点P (0, √3)但为了好算干脆我编一个带整点的例子y² x³ - 7x 10点P (1, 2)点Q (3, 4)。你可以验证这两个点确实在曲线上。用上面的公式手算一遍λ (4 - 2) / (3 - 1) 1x₃ 1² - 1 - 3 -3y₃ 1 × (1 - (-3)) - 2 2。所以P Q (-3, 2)。代入曲线方程验证一下(-3)³ - 7×(-3) 10 -27 21 10 4而y² 2² 4恰好成立。为了让你能快速玩起来我建议把上面的类保存为一个文件比如ecc.py然后写一段测试P EllipticCurvePoint(1, 2, -7, 10) Q EllipticCurvePoint(3, 4, -7, 10) R P Q print(R.x, R.y) # 输出应该是 -3, 2如果你想再体验一下结合律可以继续取一个点S然后分别计算(P Q) S和P (Q S)看看结果是否一致。我当初跑这个验证的时候心里其实捏了把汗毕竟理论证明和程序跑出来是两码事看到输出一致才彻底放心。3.1 带坐标的类型设计为什么用类而不是裸元组我用一个类来表示点而不是简单的(x, y)元组是为了把曲线参数a、b一起封装进去并且可以在构造时校验点是否在曲线上。这是我在实际写代码时踩过坑之后总结的经验。如果只用裸元组很容易出现把两条不同曲线的点加到一起的荒唐情况而且出了错误很难排查。把曲线参数放进点对象里相当于给每个点挂上了“身份标签”相加前先检查是否属于同一曲线代码的自解释性也强很多。另外类里我特意定义了__eq__方法否则Python会默认按对象身份比较两个坐标相同的点会被当作不同对象。这个坑虽然低级但新手很容易踩。如果你直接用元组就能天然避免但元组又没法携带曲线参数所以两害相权取其轻我还是选择了类。3.2 初步测试跑通最朴素的点加法我把上面手算的例子跑一遍curve_a, curve_b -7, 10 P EllipticCurvePoint(1, 2, curve_a, curve_b) Q EllipticCurvePoint(3, 4, curve_a, curve_b) R P Q print(R.x, R.y)输出应该是-3.0 2.0。这里出现浮点数很正常因为直线斜率λ通常不是整数。如果你想要高精度计算可以考虑用 fractions 模块或 sympy但初学阶段浮点足够。如果你想玩得更细可以自己写一个检验函数判断计算结果仍然落在曲线上def assert_on_curve(point, a, b): if point.y is None: return assert abs(point.y**2 - (point.x**3 a*point.x b)) 1e-9有了这个断言你可以在每次加法后都做验证确保程序没有bug。这一步虽然简单但能帮你建立自信尤其是后面填了负数、逆元、无穷远点等边界条件之后。4. 实操中常见的问题与排查技巧数学上干净利落的群运算落到代码和手算里总会遇到一堆边界情况。这一节我把自己踩过的坑和排查思路整理成清单方便你对照着检查。4.1 无穷远点怎么表示代码里的“None”与数学里的“O”无穷远点是椭圆曲线群的单位元。在代码里我选择把它表示为xNoneyNone并在加法函数里单独处理。这是最容易遗漏的一条分支。如果你忘了处理无穷远点那么当P (-P)时就会出现除零错误因为连接两点是竖直线斜率的分子为0还是分母为0要看你怎么定义。具体来说如果两个点满足x相等、y互为相反数代码里如果直接走一般公式分母x₂ - x₁ 0程序直接崩溃。我的处理方式是先判逆元再判倍点最后才走一般公式。排查这类问题的技巧是写一组测试用例覆盖P O、O P、P (-P)、O O四种情况确保输出符合群的公理P O PO P PP (-P) OO O O4.2 切线斜率不存在的情况如何正确做倍点计算2P时公式要求使用切线斜率λ (3x₁² a)/(2y₁)。如果y₁恰好等于0那就意味着P点在x轴上此时切线是竖直的切线与曲线的第三个交点就是无穷远点。数学上2P O代码里如果不做判断分母为0也会崩溃。所以在倍点分支里我先判断y是否等于0如果是就直接返回无穷远点。很多资料里会提到“特征2和特征3的椭圆曲线公式不同”这里先不用管那么深但在实数域上y0这个边界必须处理。我在代码中已经写了if self.y 0的判断就是为了避免这个坑。4.3 曲线必须非奇异判别式为何不能为零三次方程x³ ax b如果有重根曲线就会出现尖点或自交点这种曲线叫奇异曲线。奇异曲线上的群结构会塌掉因为几何上“第三个交点唯一性”被破坏了。判别式Δ -16(4a³ 27b²)由于常数-16在特征不为2、3的域上不影响是否为零一般直接说4a³ 27b² ≠ 0即可。例如y² x³这条曲线a 0b 0判别式为0它在原点有一个尖点不能用椭圆曲线群运算。我在上面代码的构造函数里没有加这个检查严格来说应该加上。建议你实际使用的时候补一个判断if 4a**3 27b**2 0: raise ValueError(奇异曲线)。排查技巧当你发现某个点代入曲线恒成立但加法结果总是怪异时先检查是不是曲线选错了。我做过一次y² x³的实验计算结果乱成一锅粥后来才回想起是尖点破坏了群律。4.4 有限域上的计算为什么实数上没问题一上密码学就变了上面所有公式在实数域上都能跑通但密码学里使用的却是有限域上的椭圆曲线记作GF(p)或GF(2^m)。原因很简单实数域上的点有无穷多个计算机没法枚举也无法保证计算难度。而有限域上的点虽然也多但有限且离散对数问题比有限域乘法更难以拆解。从实数域切换到有限域核心公式基本不变只是把加、减、乘、除换成模运算。除法的逻辑要改成模逆运算比如计算斜率λ (y₂ - y₁)/(x₂ - x₁)时分母实际上是乘以它的模逆元。我建议你先在实数域把代码调通然后再扩展成模算术版本。如果直接上有限域一旦出bug很难分辨是数学问题还是编码问题。这里给一个模逆运算的实现提示。设模为p用扩展欧几里得算法求inv(a, p)然后乘法代替除法。如果使用Python 3.8以上版本可以直接用pow(a, -1, p)。4.5 快速排查清单我把自己排查问题时常用的检查项整理成一个表症状可能原因检查方法除零错误两个点x坐标相同但y相反在一般加法前判断逆元结果不在曲线上曲线判别式为0或构造函数没校验检查4a³ 27b²是否为零单位元错乱没有处理无穷远点或无穷远点表示冲突跑一遍P O、O P的用例倍点结果异常y0时未做边界处理测试x轴上交点的倍点结合律不成立可能用了错误曲线参数随机取3个点验证结合律5. 群结构为何重要从数学结构到密码学应用讲完了群运算和代码实现我想把视野拉高一点谈谈这个代数结构到底有什么用。为什么金融系统、数字签名、区块链密钥体系里都能看到椭圆曲线的影子关键在于一个问题给定曲线上一点P和一个整数k计算kP是很容易的就是从P开始反复加法。但反过来给你P和kP让你反推出k这就非常难了。这个问题叫椭圆曲线离散对数问题ECDLP。它的“难”与群结构本身密切相关。在实数域上这个反推问题没有密码学意义因为点坐标是浮点数误差会放大但在有限域上点的集合是有限的运算无法借助实分析的逼近手段目前也没有多项式时间算法能解决暴力尝试又是天文数字级别的规模。所以你会发现群结构提供了“加法”这种运算方式而有限域提供了“离散”的集合。两者结合才催生了ECC密码体制。经典场景是密钥协商双方各自选一个私钥k₁和k₂公开参数P然后互相交换k₁P和k₂P双方都能算出共享密钥k₁k₂P但窃听者拿不到k₁和k₂无法高效算出同样的值。需要特别注意的是密码学中使用的曲线参数都是经过严格挑选的并非随便拿一条曲线就能用于安全通信。实际系统里常见的曲线如P-256、secp256k1都是经过特殊设计避开弱曲线以及各种攻击面。除了密码学椭圆曲线的群结构在数论里还有更深的用处。一个经典结论是定义在有限域上的椭圆曲线的点数N满足 |N - (p1)| ≤ 2√p这叫做Hasse界。这个结论之所以重要是因为它告诉我们曲线上的点不会太多也不会太少。点数的精确计算算法如Schoof算法就是基于群结构做各种模运算和除法最后推出精确点数。你看从一条曲线到一个群再到计数、协议设计整个故事线都串起来了。5.1 为什么有限域上的点构成有限群实数域上椭圆曲线有无数个点怎么换到有限域变成有限群呢因为有限域GF(p)本身就只有p个元素点的坐标(x, y)都落在GF(p)里所以最多只有p²个点再加无穷远点总数有限。每两个点加法结果仍然落在这个有限集里所以它天然就是有限群。理解这个转变之后你就会明白一个很微妙的事情有限域上的椭圆曲线图形不再是连续曲线而是一堆离散点组成的集合。所谓“曲线”只是一个名字真实场景里是一堆满足方程的点的集合。这一点初学者特别容易误解以为密码学里用的“椭圆曲线”还是一条可以画出来的平滑曲线其实根本不是。我建议你找个小素数p17枚举一下y² x³ 2x 3在GF(17)上的点亲眼看到点集是离散的才能真正接受这个事实。5.2 结合律在密码学中的意义标量乘法能够安全展开密码学里计算kP时通常使用“倍增与累加”的方法把k写成二进制从高往低扫描每次对当前点做倍点遇到1就多加一个P。这个过程之所以成立完全依赖群运算的结合律。如果结合律不成立简单的重复加法就会出现歧义根本没法安全展开。你可能觉得“结合律是群的基本要求有什么可稀罕的”。但在椭圆曲线上结合律并不是免费的午餐正是这套几何加法的精妙之处。撰写标准库、设计加密协议的工程师们最先验证的往往就是参数曲线上的群运算是否正确实现因为他们知道任何一点微小的错误都会破坏这个基础。6. 写在最后我踩过的一些坑和给你的练习建议聊了这么多关于椭圆曲线和代数结构的美妙之处我还有一个很深的体会很多人一上来就学有限域上的群运算结果被一堆模运算细节淹没反而忘了背后的几何直觉。我的建议是先在实数域上用“连线取交点再对称”的方式理解群运算手推两三个例子再用代码验证最后再切换到有限域。这个顺序能帮你把抽象代数中的群概念牢牢锚定在一个可见、可算的几何对象上。我当年最容易混淆的概念是群运算的单位元为什么是无穷远点而不是(0, 0)。后来我画了很多图又手工算了几次P (-P)才彻底明白。对初学者来说这部分需要用一点耐心因为它实在太反直觉了。如果一次没理解不妨把手算的每一步写清楚尤其是处理无穷远点的分支别跳过。至于后续扩展你可以从两条路线继续往下走。一条是往代数数论方向研究椭圆曲线的秩、Torsion子群、Mordell定理另一条是往应用密码学方向去读secp256k1的参数文档自己实现一个有限域上的点加法和标量乘法然后跑一遍密钥协商协议。这两条路线都很能锻炼人而且会不断加深你对“代数结构如何赋能实际问题”的理解。最后再分享一个小技巧当你写代码或者手算遇到奇怪的不一致时先用“结合律”做一次冒烟测试。随机生成三个点P、Q、R验证(P Q) R等于P (Q R)。如果这一步都过不了其他任何结论都不可信。群运算就像一台精密的机器结合律是它的轴承一旦轴承坏掉整台机器都会散架。先保住这个核心你后续的探索会顺畅很多。
