一场椭圆曲线的寻根问祖之旅_语言 & 开发_李辉忠

Python 还能承担下一个时代的发展重任吗？Mojo 语言的横空出世对 AI 研发生态有什么影响？了解详情 



 写点什么

本文介绍密码学中常见的椭圆曲线以及他们之间的关系，介绍不同标准体系的命名规则，尝试描述椭圆曲线之间的家族演义关系。文章试图讲清椭圆曲线相关概念和功能，不涉及复杂的数学证明和推理，欢迎感兴趣的同学阅读。

笔者主要参考 Wikipedia 和相关组织网站的信息进行整理，不排除出现纰漏的可能，欢迎专家批评指正。

一个可能你没关心过的问题

在《一个数字引发的探索——ECDSA解析》中提到的椭圆曲线 secp256k1，它有一些特性，可以快速计算出 recoveryID。

这个 secp256k1 为什么如此命名？

不怕各位笑话，我在弄清楚它之前，经常拼写错，写成 sec256pk1，seck256p1 等。

咬文嚼字 secp256k1

搞清楚 secp256k1 的命名含义其实很简单，搜索引擎可以快速为你定位到答案，它出自一个密码协议标准，每一个字母和数字都代表着特定含义，我们来逐一解析。

1、密码协议标准

第一部分是「sec」，sec 是 Standards for Efficient Cryptography 的简称，是 SECG 发布的一种密码学协议标准。

SECG 发布的「SEC 1」和「SEC 2」两个关于椭圆曲线的协议标准，在「SEC 2」中有详细说明 secp256k1 以及其他曲线的参数定义。

除了「sec」，还有众多其他关于椭圆曲线的协议标准，从「SafeCurve」中可以看到有下列不同类型的标准。

「SafeCurve」此处较久没有更新，有些标准已经更新了多次，例如 NIST 关于数字签名的标准 FIPS 186 目前在用的是第四版，第五版也在起草中了，从「NIST」官网中可见。

NIST 是美国的国家标准技术研究所（National Institute of Standards and Technology），因此，NIST 的标准也是美国标准。

「NIST FIPS 186-4」标准中定义了若干椭圆曲线标准，例如 NIST P-256、NIST P-384 等，其中开头 NIST 也代表密码协议标准的名字。后续描述都是围绕这两个标准来解析。

2、有限域

第二部分是「p」，p 表示该椭圆曲线是基于素数有限域 Fp。有限域是离散数学中的概念，此处不做展开，简单来说，它是一个由有限数量元素组成的集合，元素之间可以进行加法和乘法计算，具备一些独特的属性。

密码学中使用椭圆曲线都是基于有限域的，除了素数有限域 Fp 之外，还有另一种特征为 2 的有限域 F2m（因格式问题，2m 应为 2 的 m 次方，下同），Fp 的大小（元素个数）为 p，F2m 的大小为 2m。

基于 Fp 的椭圆曲线为：

基于 F2m 的椭圆曲线为：

在「SEC 2」中还定义了 sect163k1、sect163r1 等曲线，其中，t 表示的是该曲线基于 F2m。在「NIST FIPS 186-4」中定了 P-256、B-163 等曲线，P-表示基于 Fp，B-表示基于 F2m。

3、有限域大小

每个椭圆曲线 E 都有若干关键参数，包括阶为 n 的基点 G 和系数 h 等，其中，n 为一个大素数，n*h 为椭圆曲线上点的数量。为了计算效率考虑，h 通常设置为 1、2 或 4。

通俗地讲，如果椭圆曲线上的点数量越多，那么这条椭圆曲线的安全度就越高，因此 n 的取值是影响曲线安全的关键。

椭圆曲线又都是基于有限域的，曲线上的点都是有限域中的元素，因此，有限域大小决定了曲线安全度。

第三部分「256」就是有限域大小的表现形式，还有更多其他如 192、224、384 等，在「NIST FIPS 186-4」中有个表格展现了 Fp 和 F2m 两个域的各种不同大小配置。

SEC 标准在这块的设置和 NIST 标准类似，我们会看到 p 系列的曲线有 p192、p224、p256（secp256k1 就是其中一种）、p384 和 p521，t/B 系列有 t163/B-163、t233/B-233 等。

4、Koblitz Curve

第四部分「k」表示该曲线是 Koblitz Curve，从「SEC 2」中可以看到还有此处标记为 r 的曲线（如 secp256r1），r 表示该曲线是伪随机曲线 Pesudo-Random Curve。

Koblitz Curve 命名源自数学家「Neal Koblitz」，它是一种特殊的曲线，它的一些参数是精心挑选设置的。Koblitz Curve 具有自同态的性质，可以通过优化大幅提升计算效率。

相比之下，Pesudo-Random Curve 的对应参数是通过随机种子计算出来的，有标准的检验算法可以检测所有参数是随机种子产生而来。

对应「2、有限域」中的两个椭圆曲线，Koblitz Curve 分别简化为：

例如，secp256k1 对应的曲线 b=7，即曲线表示为

在「NIST FIPS 186-4」中 Koblitz Curve 曲线以「K-」标记开头，分别有 K-163、K-233 等。

5、末位标记

到了第五部分「1」，这是代表在前 4 个条件下提供了多种推荐参数设置，在 SEC 标准中大部分该位都是 1，即只提供一种推荐参数，sect163r2 是一个例外。

下面把 SEC 和 NIST 两个标准推荐的曲线分别列一下，二者有较大部分是相同的参数设置。

上述表格中，同一行中 SEC 和 NIST 都出现的，两个曲线虽然名字不同，但参数完全相同，也就是说其实一样的。

橙色底纹的几个 SEC 曲线没有对应的 NIST 曲线，因此 SEC 标准包含的曲线比 NIST 多一些，本文开头提到的 secp256k1 就是 SEC 单独存在的。

说到这里，不得不提一个正经八卦。据说，NIST 推荐的 Pesudo-Random Curve，也就是 P 和 B 系列，并没有公布随机数挑选规则，外界存在一种疑虑，可能 NSA（美国国家安全局）掌握了后门，能够轻易破解这些密码协议。

有兴趣的同学可以搜索「Dual_EC_DRBG 后门」，更大的八卦是据说中本聪选择 secp256k1 作为比特币签名算法的曲线，而没有选择更常用的 secp256r1，也是因为这个潜藏的风险。

椭圆曲线族谱

调研发现，「STD」记录了比「SafeCurve」更为详细的标准和曲线，感觉这可以算是椭圆曲线族谱了。翻阅该网站记录的所有曲线，发现绝大部分还是基于「（2）有限域」中的曲线，推荐的参数不同而已。

但是，在「other」中存在几种例外，E-222 采用 Edward Curve，Curve25519 采用 Montgomery Curve，Ed448 采用 Twisted Edward Curve。

Edward Curve 是什么？Montgomery Curve 又是怎样的？Edward 与 Twisted Edward Curve 又有什么关系？

上述问题再一次触碰到我的知识盲区，所以接下来只好以截图为主，内容源自 Wikipedia，如果觉得看着有点晕，可直接跳过看结论。

「Edward Curve」定义如下：

「Montgomery Curve」定义如下：

「Twisted Edward Curve」定义如下：

「Curve25519」定义如下：

「Ed25519」的定义如下：

根据 Wikipedia，大概可以整理出这么几个信息：

Edward Curve 是 Twisted Edward Curve 中的一种；
Twisted Edward Curve 和 Montgomery Curve 可以互相转换；
Edward Curve 和 Montgomery Curve 这两种曲线都具有特殊属性，例如能够为计算加速；
Curve25519 是一种曲线，Ed25519 是一种签名算法；
Curve25519 又是精选的 Montgomery Curve，具有更高的计算效率；
Curve25519 和 Ed25519 采用的曲线是一致的，一个是 Montgomery 表现形式，一个是 Twisted Edward Curve 表现形式；
25519 的取名来自于该曲线的有限域参数 p=2 的 225 次方-19；

在阅读 Wikipedia 的过程中发现一个名字「Weierstrass equation」，原来它才是这些曲线的鼻祖，在一个域 k 上的任何一个平面曲线，都可以表示成 Weierstrass equation。

不难发现，前面提到过的各个公式都是 Weierstrass equation 的一种演化版本（Twisted Edward Curve 看起来不是，但是它可以转换到 Montgomery Curve，本质上也一样）

到此，为椭圆曲线寻根问到祖，并且从「STD」也获知了椭圆曲线家族的族谱。

「STD」中罗列了多个其他标准，例如 Brainpool 曲线系列、BN 曲线系列、MNT 曲线系列等，这些系列的背后都代表了一种独特的曲线生成哲学，或是为了提供可验证的随机数，或是为了提供满足 Paring 的特性，或是为了提高抗攻击的能力等等，每一份精心选择的参数都是一群数学家们巧夺天工的设计。