libsecp256k1教程 - Pieter Wuille

2025年6月

libsecp256k1 教程

• 1. 抽象代数
  • 1.1. 引言
  • 1.2. 循环群
  • 1.3. 有限域
  • 1.4. 同构
  • 1.5. 标量
• 2. secp256k1 曲线
  • 2.1. 坐标域
  • 2.2. 曲线群
    • 2.2.1. 群运算
    • 2.2.2. 标量乘法
  • 2.3. 标量与点之间的同构
    • 2.3.1. secp256k1 生成元
    • 2.3.2. 标量域
  • 2.4. GLV 自同态
  • 2.5. 雅可比坐标
• 3. libsecp256k1 指南
  • 3.1. 公开 API
  • 3.2. 主要库代码 (secp256k1.c)
    • 3.2.1. 无其他依赖的通用工具
    • 3.2.2. scalar: 模群阶的整数
    • 3.2.3. int128, 128 位算术实现
    • 3.2.4. field: 有限域元素表示
    • 3.2.5. modinv32 和 modinv64: 模逆
    • 3.2.6 group: secp256k1 曲线群上的群运算
    • 3.2.7. 标量乘法: ecmult, ecmult_gen, ecmult_const
    • 3.2.8. 核心公开 API 实现
  • 3.3. 测试
    • 3.3.1. 单元测试
    • 3.3.2. 穷举群测试
    • 3.3.3. 恒定时间测试
  • 3.4. 基准测试
  • 3.5. 示例
• 练习
• 更新日志

1. 抽象代数

这是关于群和域作为抽象数学对象的总结，以及与它们相关的性质。它介于速查表和完整课程之间，没有证明或严谨的定理，但提供了进一步阅读的链接。

1.1. 引言

抽象代数的思想及其对它的用处在于，我们不是处理具体的对象（如整数、分数、椭圆曲线点以及它们之间的加法和乘法运算），而是先引入一层抽象。作为一个编程类比，可以想象多个实现共同接口的情况。例如，一个映射/字典数据结构可能实现为红黑树或哈希表，虽然内部细节完全不同，但它们表现出可能相同的接口。类似地，我们可以将群和域等代数结构视为接口，由一组运算和相关的要求性质组成，这些性质可以适用于多种不同的具体结构。

在许多情况下，仅用几个定义性质来描述数学对象就足够了——当从这个视角观察时，它们的区别和复杂性就消失了。就像在软件开发中，将逻辑的实现细节隐藏在抽象层后面，允许程序员专注于更高级的性质，这同样适用。这里也是如此。有许多不同的具体结构，但通常对于更高级的协议和推理来说，重要的只是它们表现出的几个性质。

运行示例。考虑以下 4 个例子：

• 示例 1：集合 {0,1,2,3} 与“模 4 加法”运算
• 示例 2：集合 {0,1,2,3} 与“XOR”运算
• 示例 3：集合 {1,3,7,9} 与“模 10 乘法”运算
• 示例 4：90° 倍数旋转的集合与“组合旋转”运算。

我们可以使用所谓的 Cayley 表 来展示相关运算符的全部效果：

示例 1	示例 2	示例 3	示例 4
		0	1
---	---	---	---
0	0	1	2
1	1	2	3
2	2	3	0
3	3	0	1
---	---	---	---
0	0	1	2
1	1	0	3
2	2	3	0
3	3	2	1
---	---	---	---
1	1	3	7
3	3	9	1
7	7	1	9
9	9	7	3
---	---	---	---
·	·	↶	⇅
↶	↶	⇅	↷
⇅	⇅	↷	·
↷	↷	·	↶

这些表中哪些看起来“相似”？

• 示例 1 和示例 4 虽然使用了不同的符号，但显然行为相似，因为表格是对应的。示例 1 中的每个数字 $n$ 变成 $n\times 90^\circ$ 的左旋转。
• 示例 1 和示例 3 实际上行为也相似，但需要重新排列表中的元素（交换第 2 行和第 3 行，以及第 2 列和第 3 列）：${0\rightarrow 1, 1\rightarrow 3, 2\rightarrow 9, 3\rightarrow 7}$。
• 然而，示例 1 和示例 2 是根本不同的。注意表中的对角线包含所有相同的元素，这在其他任何示例中都不成立。示例 1（或 3 或 4）的元素之间没有任何映射能实现这个性质。

因此我们得出结论，即使操作的元素个数相同，许多不同（甚至看起来非常不同）的运算在根本上可以是相同的，但看起来相似的运算也可能在根本上不同（例如示例 1 和示例 2）。

接下来的部分将更深入地讨论：

• 群：具有一个运算（通常是 $+$ 或 $\times$）和一些特定性质的结构，特别是循环群。
• 域：具有两个运算（通常同时有 $+$ 和 $\times$）和一些特定性质的结构，特别是素数阶域。
• 同构：在结构之间进行映射的同时保持结构的映射，比如上面的 $\rightarrow$。结构之间同构的存在表明，就接口而言，所涉及的结构是不可区分的。

1.2. 循环群

背景：https://en.wikipedia.org/wiki/Group_(mathematics) 和 https://en.wikipedia.org/wiki/Cyclic_group。这是对我们关心的内容的总结。在列出定理的地方，我不期望你能证明它们，只要求理解所断言的内容，并认为它听起来合理。自己动手做一些例子可能会有所帮助。

一个群 $G$ 是一个代数结构，包含一个集合 $X$ 和一个称为群运算的二元运算（它接受 $X$ 的两个元素，并返回 $X$ 的一个元素），它们一起满足下面列出的一些性质。群运算通常表示为 $+$ 或 $\times$，但也可以是任何东西。群的记法是 $G=(X,+)$ 或 $G=(X,\times)$。

• 群运算必须是封闭的：将群运算应用于 $X$ 中的两个元素，结果必须是 $X$ 中的一个元素。
• 集合必须有一个单位元，通常称为 $0$ 或 $1$，使得对于每个 $a$ 都有 $a+0=0+a=a$（加法写法）或 $a1=1a=a$（乘法写法）。注意这个单位元必然是唯一的（否则对两个不同单位元应用群运算会得到什么结果？）。
• 群运算必须是**结合的**：对于集合中的所有 $a, b, c$，有 $a+(b+c)=(a+b)+c$（加法写法），或 $a(bc)=(ab)c$（乘法写法）。
• 每个群元素必须有一个逆元：对于集合中的每个 $a$，存在一个 $x$ 使得 $x+a=a+x=0$（加法），或 $xa=ax=1$（乘法）。$a$ 的逆元必然是唯一的，记作 $-a$（加法）或 $a^{-1}$（乘法）。

还存在许多其他具有一个二元运算但缺少某些性质的类群结构，包括 magma、半群 和 幺半群。它们对我们来说不重要，但你可能会遇到这些名称。

我们遇到的大多数群将采用加法写法（群运算是 $+$，单位元是 $0$，逆元是 $-x$）或乘法写法（群运算是 $\times$，单位元是 $1$，逆元是 $^{-1}$）。但是，也存在不使用这些记法的群，例如群运算写作 $\circ$ 或 $\oplus$，或者单位元可能写作 $e$。

一个群中元素的个数称为它的**阶**，可以是正整数或无穷大。存在阶为任意严格正整数的群（阶不能为 $0$，因为这意味着没有单位元）。

一个阿贝尔群是具有一个额外性质的群：交换律。存在非阿贝尔群，它们往往更难以研究。我们不需要它们，所以不多讨论。非阿贝尔群的例子包括可逆方阵的乘法，或魔方变换的集合。

• 在阿贝尔群中，群运算必须是可交换的：$a+b=b+a$ 或 $ab=ba$。

一个群同构是一个保持群结构的双射函数。也就是说，它将一个群中的单位元映射到另一个群中的单位元，并且保持群运算：如果两个群中的运算都用 $+$ 表示，则 $f(a+b)=f(a)+f(b)$。

运行示例。从示例 1 到示例 3 的映射 ${0\rightarrow 1, 1\rightarrow 3, 2\rightarrow 9, 3\rightarrow 7}$（等价于 $f(x)=3^x \pmod{10}$）是一个群同构。

另一个例子。从 $(\mathbb{R},+)$ 到 $(\mathbb{R}_{>0},\times)$ 的函数 $f(x)=\exp(x)$，因为 $f(a+b)=\exp(a+b)=\exp(a)\times\exp(b)=f(a)\times f(b)$。第一个群的单位元是 $0$，第二个群的单位元是 $1$。

如果两个群之间存在一个同构，则称这些群是同构的（或“在同构意义下相等”），并且本质上“行为”相同，只是元素和运算的写法不同。同构群的记法是 $G_1 \cong G_2$。

一个群是另一个群的子群，如果它的集合是子集，并且运算相同但限制在子集上，结果仍然是一个群。拉格朗日定理指出：子群的阶总是整除它所属的群的阶。给定一个群 $G$ 及其中的一个元素 $g$，群 $\langle g\rangle$ 由集合 ${0, g, g+g, g+g+g, \ldots}$ 组成，使用相同的运算符 $+$（如果采用乘法写法，则是 ${1, g, g^2, g^3, g^4, \ldots}$）。这称为由 $g$ 生成的子群，因为它总是一个群。如果一个群有一个元素生成整个群，即存在至少一个元素 $g$ 使得 $\langle g\rangle = G$，则该群称为循环群，$g$ 称为该群的生成元。一个循环群可能有多个生成元，每个都能单独生成整个群。对于给定元素 $g$，生成子群的阶也称为元素 $g$ 的阶。作为拉格朗日定理的推论，任何元素的阶都整除群的阶。

运行示例。在上面的示例 1（模 4 整数加法，也记作 $(\mathbb{Z}/4\mathbb{Z},+)$）中，元素 ${1,3}$ 是生成元，例如 $3$ 按顺序生成 $[0,3,2,1,0,3,\ldots]$，包含整个集合，因此示例 1 构成一个循环群，与之同构的示例 3 和 4 也是如此。然而，$2$ 不是生成元，因为它只生成 $[0,2,0,2,\ldots]$，这确实构成了一个集合为 ${0,2}$ 的子群。上面的示例 2 没有任何生成元能生成整个群：$1$ 生成 $[0,1,0,\ldots]$，$2$ 生成 $[0,2,0,\ldots]$，$3$ 生成 $[0,3,0,\ldots]$。因此，示例 2 不是循环群。

接下来，有一个记法用于重复应用群运算将很有用。在加法记法的群中，我们将使用 $n\cdot x$ 表示 $x+x+x+\ldots+x$，重复 $n$ 次 $x$。通常也直接写作 $nx$ 表示此含义，但为了避免与乘法群运算混淆，下面我们将专门使用 $\cdot$。在乘法记法的群中，$x^n$ 用于表示 $n$ 次重复应用群运算。注意在这些记法中，$n$ 是非负整数，不是群元素。

在群中，我们可以定义离散对数 $\log_b(a)$ 或 $\operatorname{DL}_b(a)$，其中 $a$ 和 $b$ 是群中的元素，它是满足将对 $b$ 重复应用群运算 $x$ 次后得到 $a$ 的最小非负整数 $x$。换句话说，$a=x\cdot b$（加法）或 $a=b^x$（乘法）。只有当 $a$ 属于 $b$ 生成的群时，离散对数才存在。在循环群中，离散对数对于任何生成元 $b$ 和任何 $a$ 都是良定义的。

循环群有许多有趣的性质：

• 每个循环群都是阿贝尔群。
• 对于给定阶 $n$，所有 $n$ 阶循环群都是同构的。因此我们可以称“那个” $n$ 阶循环群为 $C_n$。
• 对于有限 $n$，每个 $n$ 阶循环群同构于模 $n$ 整数加法群：$C_n\cong (\mathbb{Z}/n\mathbb{Z},+)$。
• 对于无限 $n$，每个循环群同构于整数加法群：$C_\infty\cong (\mathbb{Z},+)$。

群可以通过多种方式复合与分解，但这里我们只关心一种：直积。给定两个群 $G_1=(X_1,+)$ 和 $G_2=(X_2,+)$，它们的直积 $G_1\times G_2$ 是一个群，其集合是 $X_1$ 和 $X_2$ 的笛卡尔积（所有第一个元素属于 $X_1$、第二个元素属于 $X_2$ 的元组），其运算定义为 $(a,b)+(c,d)=(a+c,b+d)$。

有限阿贝尔群基本定理指出，每个有限阿贝尔群同构于一个或多个素数幂阶循环群的直积。这个基本定理意味着，通常当在一个阶可以分解为多个素数幂的群中工作时，可以切换到每个大小的子群中，在这些子群中解决问题，然后组合结果。

示例。例如，$C_{12}\cong C_4\times C_3$。使用模 12、模 4 和模 3 的整数加法作为实例，我们可能有函数 $f((a,b)) = 3a + 8b \pmod{12}$（整数加法）。在模 4 下，$2+3=1$；在模 3 下，$2+2=1$，所以$(2,2)+(3,2)=(1,1)$（在直积中）。因此，$f((2,2))+f((3,2))=f((1,1))$（模 12），这确实成立，因为 $10+1=11$（模 12）。然而，$C_8\not\cong C_4\times C_2\not\cong C_2\times C_2\times C_2$，因为 4 和 8 已经是素数幂。

运行示例。示例 1 是 $C_4$，示例 3 和 4 与之同构。但是，示例 2 同构于 $C_2\times C_2$，这是不同的。

素数阶群是其阶为素数的群。它们总是循环的（且阿贝尔的），因此同构于 $C_p$。此外，除了单位元外的每个元素都是生成元，因此它们的离散对数可以用任何非单位元元素作为底数。由于子群的阶也整除原群的阶，素数阶群没有非平凡子群（只有单元素群和自身）。这使得它们在密码学中特别有用，因为其中的问题不能轻易地被分割成较小的子群再组合，而基本定理则允许这样做。

1.3. 有限域

背景：https://en.wikipedia.org/wiki/Finite_field，但涉及非素数域的部分可以跳过。

域大致对应于我们称之为“类数”的东西：数学结构，其中大多数传统解方程的技术都有效：你可以将项取反并移到等式另一边，可以将两边同时除以同一个非零值，等等。最熟悉的域包括有理数 $\mathbb{Q}$、实数 $\mathbb{R}$、复数 $\mathbb{C}$，但还有（这将是我们关心的）素数的模算术，以及其他许多域（见下文）。

形式上，一个域是一个代数结构，包含一个集合 $X$ 和两个二元运算符，通常记作 $+$ 和 $\times$（不同于只有一个运算的群）。它要求其运算具有以下性质：

• $(X,+)$ 构成一个阿贝尔群，通常采用加法写法（即封闭、交换、有单位元 $0$，每个元素都有加法逆元 $-x$ 使得 $x+(-x)=0$）。
• $(X\setminus{0},\times)$ 构成一个阿贝尔群，通常采用乘法写法（即封闭、交换、有单位元 $1$，每个元素都有乘法逆元 $x^{-1}$ 使得 $xx^{-1}=x^{-1}x=1$）。
• $\times$ 对 $+$ 满足分配律：$a(b+c)=ab+ac$。
• $0x=0$ 对所有 $x$ 成立。

域阶是域中元素的个数，可以是整数 $q$ 或无穷大。域特征是最小的非零正整数 $n$，使得 $1$ 自加 $n$ 次得到 $0$，如果这样的 $n$ 存在。否则特征为 $0$。

有限域或 Galois 域是有限阶的域。有限域的阶总是素数幂 $q=p^m$，其中 $p$ 为素数，$m$ 为严格正整数。不可能构造出具有所有域性质的其他有限大小的结构。所有同阶的有限域（关于 $+$ 和 $\times$ 运算）彼此同构。因此，我们可以谈论阶为 $q=p^m$ 的“那个”域，称为 $\operatorname{GF}(q)$。域的乘法群 $(X\setminus{0},\times)$ 总是一个循环群 $C_{q-1}$。换句话说，在每个有限域中，每个非零元素都可以写成某个固定常元素（域中元素）的幂。这样的生成元称为域的一个本原元。$\operatorname{GF}(p^m)$ 的特征是 $p$。

素数阶域是 $m=1$ 或 $q=p$ 的有限域。构造素数阶域 $p$ 的标准方法是 $\operatorname{GF}(p)\cong (\mathbb{Z}/p\mathbb{Z},+,\times)$，即模 $p$ 的整数（运算为模加法和模乘法）。由于所有等阶有限域都是同构的，所以每个 $p$ 阶域都同构于这个域。注意，尽管存在非素数阶的有限域（$m>1$），但这些有限域不是通过模整数的整数加法/乘法构造的，而是使用扩域，这超出了这里的范围。

示例。例如，存在阶为 $9$ 的域，但 $\mathbb{Z}/9\mathbb{Z}$（模 9 的整数加法/乘法）没有 $3$ 的模逆。

也存在比域更弱、具有两个二元运算的结构，如**环或整环**，它们与域类似但缺少某些性质。它们对我们不重要，但你可能会遇到它们的名称。

其他类数运算可以扩展到一般域：

• $a-b$ 定义为 $a+(-b)$。
• $a/b$ 定义为 $ab^{-1}$，其中 $b$ 非零。这里的 $b^{-1}$ 指乘法逆。对于素数阶整数模算术域 $(\mathbb{Z}/p\mathbb{Z},+,\times)$，这是模逆，可以计算为 $x^{-1}=x^{p-2}$。也可以基于扩展欧几里得算法计算。
• $\sqrt{a}$ 定义为满足 $x^2 = a$ 的元素 $x$。在某些有限域中（特别地，特征为 $2$ 的域），每个元素恰好有一个平方根。在其他域中，有些元素有 $2$ 个平方根，而有些则没有。更多信息见下文。

1.4. 同构

背景：https://en.wikipedia.org/wiki/Homomorphism（定义、例子、特殊同态）。以下是我们关心的内容的总结：

给定两个结构（一个具有一个或多个关联运算的集合，如群或域），一个函数 $f$ 是从一个结构到另一个结构的同构，如果：

• 它是双射的：第二个结构中的每个元素恰好是第一个结构中一个元素的像，反之亦然。
• 它保持结构，即：一个结构上的运算映射到另一个结构上的运算。在两个采用加法记法的群中，这意味着对所有 $x$ 和 $y$ 有 $f(x+y)=f(x)+f(y)$。在两个域之间，这意味着同时有 $f(x+y)=f(x)+f(y)$ 和 $f(xy)=f(x)f(y)$。这特别要求加法和乘法单位元被映射到另一个结构中的对应单位元。

运行示例。回顾一下，示例 1 是 ${0,1,2,3}$ 上的模 4 加法，示例 2 是同一集合上的 XOR 运算，示例 3 是 ${1,3,7,9}$ 上的模 10 乘法，示例 4 是 $90^\circ$ 倍数的旋转。

在示例 1、示例 3 和示例 4 之间存在同构。从 1 到 3 是 $f(x)=3^x \pmod{10}$。从 1 到 4 是 $f(x)=$ 向左旋转 $90x^\circ$。示例 2 与其他示例之间不存在同构。

有一些相关术语：

• 同态：保持结构，但不要求函数是双射的。例如 $f(x)=|x|$ 从 $\mathbb{R}$ 到 $\mathbb{R}_{\ge 0}$，两者都用 $\times$ 运算。
• 自同态：同态，但两个结构（集合和运算）相同。
• 自同构：同构，但两个结构相同。自同构既是同构又是自同态。例如，群 $(\mathbb{R},+)$ 中的 $f(x) = -3x$。但这不是域自同态，因为 $f(xy) = -3xy \neq 3xy = (-3x)(-3y) = f(x)f(y)$。复数 $(\mathbb{C},+,\times)$ 确实有一个众所周知的域自同构：共轭运算。

运行示例。

• 同态的一个例子是从示例 1 到示例 3 的映射 $f(x)=9^x \pmod{10}$。它从未到达示例 3 中的元素 $3$ 或 $7$，但结构仍然保持。
• 自同态的一个例子是示例 1 中的 $f(x)=2x \pmod{4}$（或 $f(x)=x$ 或 $f(x)=3x$），或者等价地，示例 3 中的 $f(x)=x^2 \pmod{10}$，或示例 4 中的“旋转两次”。
• 自同构的一个例子是示例 2 内非零元素的任意置换，例如将 $2$ 映射到 $3$ 并将 $3$ 映射到 $2$。

1.5. 标量

假设我们有一个加法写法的循环群 $G=(X,+)$，阶为 $n$，有一个生成元 $g$。使用哪个生成元并不重要，但固定一个。设 $f(a)=a\cdot g$，将参数（标量 $a$）与 $g$ 相乘的函数。

现在观察到：

• $f(0)=0$。
• $f(n)=f(0)=0$，因为群是阶为 $n$ 的循环群。如果对于某个 $0<k<n$ 有 $f(k)=0$，那么 $g$ 不会生成所有 $n$ 个元素，因此 $g$ 就不是生成元。
• $f(a)+f(b)=f(a+b)$，由于群的可结合性。
• 由于上述原因，$f(a)=f(a \pmod{n})$。

换句话说，$f$ 是从 $C_n$（模 $n$ 整数加法）到 $G$ 的同构，而 $f^{-1}$（从群回到 $C_n$ 的逆函数）实际上是离散对数 $\operatorname{DL}_g$。

当然，我们也可以在这个集合中将乘法定义为模 $n$ 的乘法，从而得到标量的 $(\mathbb{Z}/n\mathbb{Z},+,\times)$。如果 $n$ 是素数，这就是域 $\operatorname{GF}(n)$。它的加法群与 $G$ 同构，但乘法也是有意义的，因为 $a\cdot f(b)=f(ab)=b\cdot f(a)=ab\cdot f(1)$。

这让我们能够回答诸如如何执行“群折半”（即与将 $G$ 中一个元素自加相反的操作）的问题。对于给定的 $x$，我们想要找到 $y$ 使得 $y+y=x$。如果 $x=f(d)$，则 $2\cdot y=f(d)$，即 $y=f(d/2)$，其中 $/2$ 是在 $\operatorname{GF}(n)$ 中求值的，即 $2$ 对模 $n$ 的乘法逆，于是 $y=f((2^{-1} \pmod{n})\times d)$，或 $y=(2^{-1} \pmod{n})\cdot f(d)$，且 $y=(2^{-1} \pmod{n})\cdot x$。

这可以推广：我们可以通过乘以模群阶的模逆来执行循环群中的标量除法。如果群阶是素数，则该逆对于每个不被群阶整除的除数都存在。

如果逆不存在，除法可能仍然可行，但没那么简单。例如，在偶阶群中，群折半是可能的，如果该元素（相对于任何生成元）具有偶离散对数，则通过对离散对数进行折半（并可选地加上半个群阶）。例如，在 $(\mathbb{Z}/34\mathbb{Z},+)$ 中，$18$ 的一半可以是 $9$ 或 $26$。事实上，对乘法群这样做可以让我们计算 $\operatorname{GF}(p)$ 中的平方根。一般来说，可以使用 Tonelli-Shanks 算法 来实现（本质上是一个通用的群折半算法），尽管对于 $\operatorname{GF}(p)$ 中 $p\equiv 3 \pmod{4}$ 的特殊情况，它简化为 $\sqrt{x}=x^{\frac{p+1}{4}}$。

就记法而言，在素数阶群中，我们将把标量（标量乘法中的数值参数）以及离散对数视为属于 $\operatorname{GF}(n)$，因此我们可以写作 $\frac{2}{3}\cdot x$ 表示 $(2\times 3^{-1} \pmod{n})\cdot x$。

额外理论。可以在不需要固定特定生成元 $g$ 的情况下形式化这些性质。

考虑所有形如 $m_a(x)=a\cdot x$ 的函数的集合 $M$，即对于任意整数 $a$ 和群元素 $x\in X$ 的“标量乘以常数整数 $a$”函数。例如，$m_0$ 是乘以 $0$ 的函数，即常函数 $m_0(P)=0$。函数 $m_1(x)=x$ 是恒等函数。函数 $m_2(x)=2\cdot x=x+x$ 是群倍乘函数。在这个集合上定义两个运算：

• $(m_a+m_b)(x)=m_a(x)+m_b(x)=m_{a+b}(x)$，即我们可以将 $m_2+m_3$ 理解为 $m_5$ 函数。该运算以 $m_0$ 为单位元，以 $m_{ -a \pmod{n} }$ 为 $m_a$ 的逆。
• $(m_a\times m_b)(x)=m_a(m_b(x))=m_{ab}(x)$，即我们可以将 $m_2\times m_3$ 理解为 $m_6$ 函数。该运算以 $m_1$ 为单位元，以 $m_{ a^{-1} \pmod{n} }$ 为 $m_a$ 的逆。

当 $n$ 是素数时，这个结构 $(M,+,\times)$ 同构于 $\operatorname{GF}(n)$。如果不是，它是一个环（像域那样的双运算结构，但不要求每个非零元素都有乘法逆）。它被称为自同态环，因为 $m_a\in M$ 的函数集合是我们原始群 $G$ 的所有自同态。每个阿贝尔群都有一个自同态环。如果群是循环的，自同态环同构于模阶的整数加法和乘法。如果群是素数阶的，自同态环就是一个域。

现在，群中除以 $a$ 的标量除法可以看作函数 $(m_a)^{-1}$，即 $M$ 中乘以 $a$ 的乘法逆。如果我们在一个域中工作，这个逆总是存在。

在基于群的密码学中（包括椭圆曲线密码学、Diffie-Hellman，以及 DSA 和原始的非 ECC Schnorr 签名方案），上述同构 $f$ 正是私钥（标量）和公钥（群元素）之间的映射。

注意标量除法与离散对数非常不同。标量除法是将一个群元素除以一个整数，在上述任何素数阶群中都很容易地完成。计算离散对数是将一个群元素除以另一个群元素，这个运算（据我们所知）在用于密码学的大型群中非常困难。

继抽象代数概述之后，是时候深入我们关心的实际循环群——secp256k1 曲线了。

这里你会找到它的定义、性质、各种来源的链接以及一些不那么有趣的相关信息。底部有练习题。请随意发布或通过私信发送你的答案给我。

2. secp256k1 曲线

在本节中，我们将定义 secp256k1 曲线并讨论其性质。

它是一条由 SECG（高效密码学标准组织）定义的椭圆曲线。他们的一般椭圆曲线密码学标准可以在 SEC1 标准中找到，而 secp256k1 曲线的具体规范可以在 SEC2 标准中找到。

libsecp256k1 仓库包含定义所有曲线参数的 Sage 代码。Sage 是一个基于 Python 的开源数学软件系统。我鼓励你用它做实验。

2.1. 坐标域

曲线的点的坐标是有限域 $F=(\mathbb{Z}/p\mathbb{Z},+,\times)$ 或 $\operatorname{GF}(p)$ 中的元素，其中 $p=2^{256}-2^{32}-977$，即 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f，也就是模 $p$ 的整数加法和乘法。它的加法群和乘法群都是循环的。$p\equiv 3 \pmod{4}$，所以平方根可以计算为 $x^{\frac{p+1}{4}}$。模逆可以计算为 $x^{p-2}$（这源自费马小定理），但使用扩展欧几里得算法的方法更高效（见后面章节）。

2.2. 曲线群

secp256k1 曲线 $E$ 由满足 $y^2=x^3+7$ 的点 $(x,y)\in F\times F$ 加上一个特殊的无穷远点组成，记作 $0$（也有 $\mathcal{O}$ 和 $O$ 的用法）。无穷远点构成椭圆曲线群的单位元。它没有坐标；它存在于曲线之外，但仍然是群的一部分。

这使得它成为短 Weierstrass 曲线（形式为 $y^2=x^3+ax+b$ 的曲线）的一个实例，对于 secp256k1，系数 $a=0$ 和 $b=7$。$a=0$ 这一事实使得 secp256k1 曲线能采用许多特定的优化，这在用于密码学的椭圆曲线中并不常见。

注意曲线关于 $X$ 轴对称（如果 $(x,y)\in E$ 则 $(x,-y)\in E$ 也成立，因为 $y$ 只以平方形式出现）。如果你在 $\mathbb{R}$ 上绘制曲线，这在几何上成立，而且对于我们有限域 $F$ 也成立。

2.2.1. 群运算

群运算定义如下：

• 由于无穷远点 $0$ 是单位元，$0+(x,y)=(x,y)+0=(x,y)$。
• 将关于 $X$ 轴对称的两个点相加得到无穷远点：$(x,y)+(x,-y)=0$。这意味着 $(x,-y)$ 是加法逆元，即 $(x,-y)=-(x,y)$。
• 当将两个 $X$ 坐标不同的非无穷远点相加时，找到通过它们的直线，找到该直线与曲线的第三个交点（必然存在），然后将该交点取反。这意味着只要 $3$ 个曲线点 $P$、$Q$、$R$ 共线，它们的和 $P+Q+R=0$。
• 当把一个点加到自身时，使用该点处曲线的切线。

在代数上，这意味着（非无穷远）点加法 $(x_R,y_R)=(x_P,y_P)+(x_Q,y_Q)$ 定义为：

• 计算相关直线的斜率 $\lambda$：
  • 对于点加法，通过 $P$ 和 $Q$ 的直线，$\lambda=\frac{y_Q-y_P}{x_Q-x_P}$。
  • 对于点倍乘（即点加到自身），通过 $P=Q$ 的切线，$\lambda=\frac{3x_P^2+a}{2y_P}$（对于 secp256k1，$a=0$）。
• 结果的 $X$ 坐标 $x_R=\lambda^2-(x_P+x_Q)$。
• 结果的 $Y$ 坐标 $y_R=\lambda(x_P-x_R)-y_P=\lambda(2x_P+x_Q-\lambda^2)-y_P$。

更多信息见点运算。

请注意，“通过...的直线”和“切线”等术语在有限域中实际上并没有几何意义（至少不在传统的欧几里得几何中）。然而，可以使用与实数 ($\mathbb{R}$) 几何相同的公式，只是将算术运算重新解释为相应的有限域运算。

所有这些规则一起构成了一个阿贝尔群。很容易证明它是封闭的，每个元素都有逆元，并且是可交换的，但证明结合律则不那么简单。所有有限域上的椭圆曲线都是阿贝尔群（除了少数退化情况如 $y^2=x^3$），并且要么是循环的，要么恰好是两个循环群的直积。secp256k1 群是循环的，并且具有素数阶 $n$ = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141。

当像通常那样将坐标表示为 $[0,p)$ 范围内的整数时，将一个非零值取反会改变其奇偶性（偶数变奇数，奇数变偶数）。因为对于给定的 $X$ 坐标，两个 $Y$ 坐标互为相反数，恰好一个是偶数，另一个是奇数。类似地，恰好一个小于 $p/2$（整数除法，非模运算），另一个大于 $p/2$。最后，恰好一个有平方根，另一个没有。

关于曲线阶的注释。所有有限域上的椭圆曲线都满足 Hasse 定理，该定理大致说曲线群的阶 $n$ 非常接近域的大小 $q$（具体地，$|n-(q+1)|<2\sqrt{q}$）。这个定理在 1930 年代已知，并且确实适用于 secp256k1，其中 $n-(p+1)\approx -1.270769397\sqrt{p}$。

历史。有趣的是，直到 1980 年代，随着 Schoof 算法 以及后来的 Schoof-Elkies-Atkin 算法，才在计算上可行地准确计算椭圆曲线上的点数（对于 secp256k1，在现代计算机上需要几秒钟）。没有这个，我们所知道的椭圆曲线密码学就不可能实现。但多亏了它，我们知道了 secp256k1 的 $n$，更重要的是，secp256k1 的设计者能够使用该算法选择曲线参数，使得曲线具有所需的性质（如具有素数群阶）。

2.2.2. 标量乘法

在椭圆曲线中重复应用群运算称为标量乘法或点乘法，我们记作 $v\cdot P = P+P+\ldots+P$，尽管 $v\times P$ 或 $vP$ 也很常见（以及 $Pv$，见下文）。存在高效的算法来计算大 $v$（在我们的情况下是 256 位数字）的 $v\cdot P$，类似于模算术中的平方-乘算法。例如：

我们要计算 $571\cdot P$。标量 $571=1000111011_2$ 二进制，即 $v=571=2^9+2^5+2^4+2^3+2^1+2^0$。通过将 $P$ 加倍 9 次，我们可以预计算 $P_i = 2^i\cdot P$，$i=0\ldots 9$。那么 $571\cdot P$ 就是 $P_9+P_5+P_4+P_3+P_1+P_0$。因此，我们仅用了 9 次点倍乘和 5 次点加法就计算出了结果，远好于天真地需要的 570 次点加法。

这只是一个非常基础的标量乘法算法，但它给出了直觉：为什么标量乘法的计算只需要 $O(\log_2(v))$ 次点运算，而不是 $O(v)$ 次点运算。稍后我们将更详细地讨论实际使用的算法（它们改善了算法的常数因子和内存使用，但复杂度基本保持不变）。

加法 vs. 乘法记法。虽然上述描述以及本文其余部分对椭圆曲线群使用加法记法，但使用乘法记法也很常见。这种差异源于两个科学领域的融合。在椭圆曲线的数学描述中（代数几何领域），加法记法是常见的，使用诸如点加法之类的术语。在密码学领域，许多方案最初是在非椭圆曲线群（它们很少特定于椭圆曲线）上制定的，特别是在定义为模一个大素数的整数乘法的群上（如 Diffie-Hellman、非 EC DSA、原始的 Schnorr 签名 方案等）。由于这段使用（字面上的）乘法作为群运算的历史，那里通常使用乘法记法。

这也是“离散对数”这个术语的起源。逻辑上，在加法群中，离散对数问题应该被称为“离散除法”问题，但在两种设置中都称为离散对数。

最激烈的 Twitter 争论之一涉及密码学家们关于椭圆曲线群记法的争论。

2.3. 标量与点之间的同构

2.3.1. secp256k1 生成元

由于 secp256k1 群是素数阶的，所有除 $0$ 外的元素都是生成元。然而，许多建立在其上的密码学方案需要一个固定的、良定义的生成元。对于 secp256k1，这是点 $G$，其 $X$ 坐标为 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798，$Y$ 坐标为 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8。

secp256k1 生成元的起源。尚不清楚标准化它的实体是如何选取这个点的，但它有一个显著的性质，几乎肯定揭示了部分创建故事。如果 $H$ 是满足 $G=2\cdot H$ 的点（即 $G$ 的点折半），那么 $H$ 的 $X$ 坐标是 0x3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63，一个 166 位的数字，这太小了，不可能是巧合。据推测，这个 $H$ 点是以某种方式先构造出来的，然后加倍得到 $G$。对于大多数协议，生成元的选取不影响其安全性，因此关于构造的不确定性不必担心；它只是非常奇特。另请参见 Nadia Heninger 关于该主题的简短演讲这个视频。

2.3.2. 标量域

考虑函数 $f(a)=a\cdot G$，它将标量映射到生成元 $G$ 的对应标量倍数，那么得到以下性质：

• $f(n)=0$
• $f(a)+f(b)=a\cdot G+b\cdot G=(a+b)\cdot G=f(a+b)$
• $v\cdot f(a)=v\cdot (a\cdot G)=va\cdot G=f(va)$
• $-f(a)=-(a\cdot G)=n\cdot G+-(a\cdot G)=(n-a)\cdot G=f(n-a)$

这个函数 $f$ 是 $(\mathbb{Z}/n\mathbb{Z},+)$（模 $n$ 整数加法）与 secp256k1 椭圆曲线群之间的同构，其中 $n$ 是上面给出的 secp256k1 群阶。

逆运算 $f^{-1}$，从群元素（椭圆曲线点）回到标量（模 $n$ 的整数），正是以 $G$ 为底的离散对数。这个逆运算被认为是困难的，这是椭圆曲线密码学的基础。一种用于执行此运算的算法，Pollard 的 rho，需要大约 $2^{129}\approx 10^{39}$ 次群加法和倍乘，但只需要 $O(1)$ 内存。存在更高级的算法可以利用 secp256k1 的特殊性质，或利用 CPU-内存权衡，但只能将这个数字提高一个小的常数因子。注意，并没有证明不存在更高效的算法；群的安全性（实际上，几乎所有实际使用的密码构造的安全性）依赖于一个未经证明的假设，即对于 secp256k1 曲线（或一般的椭圆曲线）不会发现（显著）更好的算法。确实存在 Shoup 在 1997 年的一篇论文中的证明：如果攻击者（在通用群模型 (GGM) 下）只能使用群运算，而不能利用椭圆曲线群特有的任何性质，那么在像我们这样的素数阶群中计算离散对数确实需要 $O(\sqrt{n})$ 次群运算。

由于 $n$ 是素数，我们可以将标量视为属于域 $\operatorname{GF}(n)$，它也具有对所有标量（当然除以 $0$ 除外）良定义的乘法和除法运算。例如，这允许我们写作 $H=f(1/2)$（对于上面定义的半生成元 $H$），或者不使用 $f$ 函数，写作 $H=(1/2)\cdot G$。

注意坐标域 $\operatorname{GF}(p)$ 和标量域 $\operatorname{GF}(n)$ 是不同的。$\operatorname{GF}(p)$ 是曲线 $X$ 和 $Y$ 坐标所属的空间。$\operatorname{GF}(n)$ 是私钥所属的空间，并且与 secp256k1 群本身同构。将 $\operatorname{GF}(p)$（以及常数 $p$）视为 secp256k1 曲线的内部实现细节，只有当你关心自己实现群运算时才重要。$\operatorname{GF}(n)$（以及常数 $n$）是群的外部可观察性质；可以称之为它的“公共 API”的一部分。

2.4. GLV 自同态

secp256k1 曲线表现出一种在用于密码学的椭圆曲线中不常见的性质，即可高效计算的 GLV 自同态，以发明者 (Gallant, Lambert, Vanstone) 命名。它使得 secp256k1 的实现能够进行一种特定的优化，由 Hal Finney 指出，并且是导致开发将成为 libsecp256k1 的代码库的直接动机。然而，GLV 自同态曾受专利限制，直到 2020 年专利到期才在 libsecp256k1 中默认启用。

为了稍微说明这一点，请注意一个显著的性质：$-(x,y)=(x,-y)$。因为我们处于阶为 $n$ 的循环群中，$-(x,y)$ 等同于 $(n-1)\cdot(x,y)$，我们发现 $(n-1)\cdot(x,y)=(x,(-1)\times y)$。然而，$n-1$ 是一个巨大的（256 位）数字，通常需要用到相对较慢的标量乘法算法（涉及数百次群运算）。尽管如此，对于这个非常特定的标量，只需简单地取反 $Y$ 坐标就足够了。

结果证明，特别地对于 secp256k1，存在另一个具有类似性质的标量。设：

• $\lambda =$ 0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72（$\operatorname{GF}(n)$ 中满足 $\lambda^3=1$ 的元素）
• $\beta =$ 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee（$\operatorname{GF}(p)$ 中满足 $\beta^3=1$ 的元素）
• 对于曲线上的每个 $P=(x,y)$，都有 $\lambda\cdot P=(\beta x, y)$。

简而言之，这意味着可以通过将群元素的 $X$ 坐标乘以 $\beta$ 来将其乘以 $\lambda$。由于这个操作可以重复第二次，所以将一个点乘以 $\lambda^2$ 等同于将其 $X$ 坐标乘以 $\beta^2$。做第三次不会产生有趣的结果，因为 $\lambda^3=1$（这也意味着 $\beta^3=1$，因为乘以 $1$ 必须是恒等）。但它可以与取反 $Y$ 坐标的性质组合。设 $h((X,Y))=(\beta X, -Y)$，然后我们得到

$(-\lambda)^0\cdot (x,y) = 1\cdot (x,y) = h^0(x,y) = (x,y) = (x,y)$ $(-\lambda)^1\cdot (x,y) = -\lambda\cdot (x,y) = h^1(x,y) = h((x,y)) = (\beta x, -y)$ $(-\lambda)^2\cdot (x,y) = \lambda^2\cdot (x,y) = h^2(x,y) = h(h((x,y))) = (\beta^2 x, y)$ $(-\lambda)^3\cdot (x,y) = -(x,y) = h^3(x,y) = h(h(h((x,y)))) = (x, -y)$ $(-\lambda)^4\cdot (x,y) = \lambda\cdot (x,y) = h^4(x,y) = h(h(h(h((x,y))))) = (\beta x, y)$ $(-\lambda)^5\cdot (x,y) = -\lambda^2\cdot (x,y) = h^5(x,y) = h(h(h(h(h((x,y)))))) = (\beta^2 x, -y)$

我们将在后面关于高效标量乘法算法的部分中讨论这个性质为什么有用。现在，知道某些特定的标量乘法可以比一般的便宜（多）就足够了。

2.5. 雅可比坐标

到目前为止我们引入的坐标系统，即满足方程 $y^2=x^3+7$ 的 $(x,y)$ 对，称为仿射坐标。当在这些坐标中实现群运算时，我们注意到在斜率 $\lambda$ 的计算中涉及除法（注意：与 GLV 自同态中使用的常数 $\lambda$ 不同）。在我们的域中，这些对应于模逆运算，相对较慢（在实践中大约比域乘法慢 50 到 100 倍）。由于天真地每次点加法或点倍乘都需要计算一个 $\lambda$，这些运算将压倒性地主导大多数涉及椭圆曲线点的操作的总运行时间。

一种可能的解决方案是将域元素表示为分数，使用规则如 $\frac{n_1}{d_1}\times\frac{n_2}{d_2} = \frac{n_1 n_2}{d_1 d_2}$, $\frac{n_1}{d_1}/\frac{n_2}{d_2} = \frac{n_1 d_2}{n_2 d_1}$, 以及 $\frac{n_1}{d_1}+\frac{n_2}{d_2} = \frac{n_1 d_2 + n_2 d_1}{d_1 d_2}$。这让我们避免了所有除法，而是将它们重写为（两）次乘法，但代价是将加法和减法也转换为三次乘法。只有在最后，当需要将坐标序列化为整数时，才需要一次求逆来将 $\frac{n}{d}$ 转换为 $n d^{-1}$。

事实证明，我们可以做得比这更好。我们不为每个坐标指定分母，而是为每个点使用一个公共分母。而且，由于这样可以得到更简单的公式，分母分别以 $X$ 和 $Y$ 坐标的二次和三次幂出现。具体来说，我们将使用坐标三元组 $(X,Y,Z)$，其中 $Z$ 是“分母”，表示仿射坐标 $(X/Z^2, Y/Z^3)$。这些被称为雅可比坐标。注意这些不是唯一的：$(X,Y,Z)$ 和 $(q^2 X, q^3 Y, q Z)$（$q$ 非零）表示同一个点。

有趣的是，也可以将它们视为直接定义椭圆曲线的一种方式，而不仅仅是编码仿射坐标的一种方法。在这种情况下，曲线方程变为 $Y^2 = X^3 + a X Z^4 + b Z^6$（对于 secp256k1，$a=0$ 和 $b=7$）。显式公式数据库 (EFD) 站点有大量以算法形式列出的公式，用于在这些雅可比坐标上执行点加法、点倍乘等。此外，任何仿射坐标 $(x,y)$ 都可以被转换为雅可比坐标 $(x,y,1)$，这允许构造混合加法公式，将给定雅可比和仿射坐标的点相加在一起。这主要是 libsecp256k1 内部采用的方法。

3. libsecp256k1 指南

语言 库 libsecp256k1 是用近乎纯的 C89 编写的（为了兼容旧/弱设备），加上它需要 uint64_t、int64_t，并可选择使用一些其他东西如 __int128，或汇编优化例程。

库接口 它旨在高级实现与 secp256k1 相关的密码学，即协议。它提供的函数实现了 ECDSA、BIP340 Schnorr 签名、BIP327 Musig2、BIP324 ElligatorSwift、ECDH。它还提供密钥生成和密钥调整函数（用于 BIP32、BIP38、BIP341）。它目前不打算直接公开低级操作，如有限域、标量整数或 secp256k1 群算术，尽管它包含这些操作的实现，目的是：

• 安全：目标是使特定目的使用库的最简单方式成为正确/最安全的方式。当暴露低级操作时，这更难实现。
• 性能：有许多重要的优化涉及以非平凡的方式表示数学对象（第 2 周的材料有一个例子，雅可比坐标系统）。通过不暴露内部，更容易更改表示，并在不同系统上使用不同表示。如下所示，一些内部操作使用起来非常不平凡（特别是具有大小/归一化约束的有限域元素）。
• API 稳定性：与上一点相关，当表示在不同版本之间可能不同时，更难保持 API 稳定性。

一个更底层的接口，没有稳定性保证且有一定的性能开销，可能会通过 hazmat 模块添加。

重点 该库专注于安全性（通过小型功能集、高级接口、最佳实践如恒定时间操作以避免侧信道攻击、测试和审查）和性能。

3.1. 公开 API

库暴露的公开 API 可以在 include/ 目录中找到。它被分成几个 .h 文件，一个主要的 secp256k1.h 用于核心库例程的接口，以及每个模块的 secp256k1_M.h 文件（模块是库的可选编译组件）。当前模块有：

• modules/ecdh：通用 ECDH 实现（使用用户提供的函数来哈希共享点）。
• modules/recovery：ECDSA 签名/验证的一种变体，支持公钥恢复（获得给定签名/消息有效的公钥）。
• modules/extrakeys：处理密钥对和仅 x 坐标密钥的例程。
• modules/schnorrsig：BIP340 中指定的 secp256k1 Schnorr 签名实现。
• modules/ellswift：公钥的 ElligatorSwift 编码实现，以及基于它们的仅 x 坐标 Diffie-Hellman（在 BIP324 中指定）。
• modules/musig：MuSig2 实现（在 BIP327 中指定）。

模块基本上是如何向库添加所有新功能的方式，因为它们避免了杂乱的主 API，并允许分阶段引入变更。

我建议至少完整阅读 secp256k1.h 文件，因为它包含了关于所提供接口的广泛文档，并给出了事物通常如何做的好概念。

3.2. 主要库代码 (secp256k1.c)

单一编译单元 主要库代码是从 secp256k1.c 构建的单一 C 编译单元（以最大化内联函数的能力），但实际代码的绝大部分在于由它直接或间接包含的 .h 文件中。这提供了一定程度的代码组织，尽管所有内容都在一个编译单元中。这些通常被分成“层”（这个术语是我为了这个写作临时起的），由 L.h 文件（定义接口的“头文件”）和包含相应实现代码的 L_impl.h 文件组成。对于其中一些，存在多个具有相应实现的可选定义（通常针对 32 位和 64 位代码）。这些采用名称 L_V.h 和 L_V_impl.h，其中 V 是变体名称。在这种情况下，仍然存在一个 L.h 描述两个变体暴露的（公共）接口；L_V.h 仅包含表示特定的定义。

主要库代码使用的层如下（下面的名称去掉了 .h 和 _impl.h 后缀），从低到高（后面的层只依赖于前面的层）：

• 通用工具：util、hsort、assumptions、checkmem。
• 围绕128 位整数算术的抽象层：int128
  • 变体 int128_struct 和 int128_native。
• SHA256 和 HMAC-SHA256 的内部（不公开）实现：hash。
• 用于模逆的 safegcd 算法：modinv32 和 modinv64。
• 标量域（模 $n$ 的整数，群阶）代码：scalar。
  • 变体 scalar_4x64、scalar_8x32、scalar_low
• 曲线坐标的有限域（模 $p$ 的整数）代码：field。
  • 变体 field_10x26 和 field_5x52（由于历史原因，一些代码在 field_5x82_int128 中）。
• secp256k1 群实现，包括仿射和雅可比点运算：group。
• 三个不同的层实现了标量-点乘法的变体：
  1. 可变时间点乘法，包括多基点乘法（例如 $a\cdot P+b\cdot G$）在 ecmult 中。
     1. 这使用（编译时）预计算表，包含 $G$ 的倍数，在 precomputed_ecmult.c 中，通过 ecmult_compute_table 中的代码生成。
  2. 与生成元 $G$ 的恒定时间点乘法在 ecmult_gen 中。 2. 这使用（编译时）预计算表，包含 $G$ 的倍数，在 precomputed_ecmult_gen.c 中，通过 ecmult_gen_compute_table 中的代码生成。
  3. 与任意基点 $P$ 的恒定时间点乘法在 ecmult_const 中。
• 私钥/公钥的序列化、反序列化和调整在 eckey 中。
• ECDSA 签名的序列化、反序列化、签名和验证在 ecdsa 中。
• 使用上述所有内容的核心公开函数在 secp256k1.c 中。
• 然后有多个**“模块”**（可以可选地编译进来以提供额外功能的组件）在 modules/ 目录中。每个都有一个 main 层（即 main_impl.h），如果相应的模块被启用，就会被包含到 secp256k1.c 中。

下面我们更深入一些。注意它们呈现的顺序不同于上面的分层顺序，我认为这样更容易理解。

3.2.1. 无其他依赖的通用工具

• util：几个通用整数函数
• hsort：堆排序的实现（因为内建的 C 函数 qsort 不能保证对恶意输入高效，尽管实践中大多数实现是高效的）。
• assumptions：使用 C89 hack 实现 C++ static_assert 的等价物，验证一些本质上是普遍的假设，但 C 语言并不保证（如有符号和无符号之间转换时的二进制补码行为）。
• checkmem：libsecp256k1 为恒定时间性进行测试（见下文），这可以通过在 valgrind 中运行，或使用 MemorySanitizer 进行编译来完成。checkmem 提供了一个与任一种交互的包装器。

3.2.2. scalar: 模群阶的整数

scalar 提供了 secp256k1_scalar 类型，表示模群阶的整数。它有三个变体：

• scalar_4x64，面向 64 位系统。
• scalar_8x32，面向 32 位系统。
• scalar_low，仅在穷举测试中使用（见下文）。

大整数算术。 secp256k1_scalar 类型表示 256 位数字（模 $n$，群阶），这带来了挑战。引用我在 StackExchange 上对一个关于该主题的有些恼人的问题的回答：

计算机通常不能处理任意长度的数字。硬件一般只能执行最多 32 或 64 位大小的整数算术。其他一切最终都必须在软件中实现。许多语言提供了隐藏这种复杂性的便利函数；例如，Python 在其标准库中包含通用任意长度整数，但这仅仅意味着 Python 解释器将对这些表面数据类型上的操作翻译成许多小的单个指令，每个指令仅操作 64 位整数。如果你想知道这是如何工作的，想象你过去是如何学习使用超过 1 位的数字进行算术的。这里的“数字”（通常称为“肢”，因为它们比数字大）本身是 64 位整数，因此一个 256 位整数可以看作由 4 个这样的肢组成的数字。对这些数字的许多操作（加法、乘法……）与你在纸上对十进制数字所做的非常相似。

libsecp256k1 不是用 Python 编写的，而是用 C 编写的，而 C 一般不提供大于 CPU 内部支持的整数类型。因此，它没有使用现成的大整数算术代码的奢侈，必须手动实现。当然，这就是关键所在：libsecp256k1 旨在快速运行，通过为这个特定应用量身定制的自定义整数代码，它可以比任何 Python 实现所能达到的快许多倍。

此外，这是必要的。即使可用，任意长度整数类型通常也不适合实现密码学。我们旨在设计恒定时间运行的代码，这样攻击者无法通过观察对私钥的操作耗时来了解任何关于私钥的信息。可变长度类型显然不能是恒定时间的，因为对它们的操作取决于数字的长度。

scalar_4x64 和 scalar_8x32 使用这种方法，它们分别用四个 64 位肢或八个 32 位肢来表示标量数字。具体来说，scalar_4x64（见下文）将 256 位 $x$ 表示为 $(x_0, x_1, x_2, x_3)$，使得 $x = x_0 + 2^{64}x_1 + 2^{128}x_2 + 2^{192}x_3 \pmod{n}$

加法 在两个这样的数字之间进行类似学校笔算：将最低值的肢相加，取结果的低 64 位作为输出肢，并将溢出（如果有）作为进位位加到下一个最低值的肢上。这意味着至少需要执行四次“实际”加法，但处理进位有时意味着需要更多。如果当加完最高值的肢后仍有进位，我们就会得到一个 $\ge 2^{256}$ 的结果。如果发生这种情况，或者甚至如果表示的值之和 $\ge n$，就从结果中减去 $n$，以保持求和表示在范围 $[0,n)$ 内。

乘法 也大致遵循学校方法。首先，所有 16 对两个肢相乘，结果按得到的 $2^{64}$ 的幂次排列，然后带进位相加，得到一个由 8 个肢组成的 512 位乘法结果。 $x = x \times y = (x_0,x_1,x_2,x_3) \times (y_0,y_1,y_2,y_3) = x_0 \times (y_0 + 2^{64}y_1 + 2^{128}y_2 + 2^{192}y_3) + x_1 \times (2^{64}y_0 + 2^{128}y_1 + 2^{192}y_2 + 2^{256}y_3) + x_2 \times (2^{128}y_0 + 2^{192}y_1 + 2^{256}y_2 + 2^{320}y_3) + x_3 \times (2^{192}y_0 + 2^{256}y_1 + 2^{320}y_2 + 2^{384}y_3)$ $= 2^{0}(x_0 y_0) + 2^{64}(x_0 y_1 + x_1 y_0) + 2^{128}(x_0 y_2 + x_1 y_1 + x_2 y_0) + 2^{192}(x_0 y_3 + x_1 y_2 + x_2 y_1 + x_3 y_0) + 2^{256}(x_1 y_3 + x_2 y_2 + x_3 y_1) + 2^{320}(x_2 y_3 + x_3 y_2) + 2^{384}(x_3 y_3)$ 计算出这个 512 位结果后，通过几个步骤将其归约到 $[0,n)$ 范围内的值。

• 第一步是将数字分成高和低 256 位部分 $z = z_{\text{low}} + 2^{256} z_{\text{high}}$（即将最低的 4 个肢和最高的 4 个肢分开处理）。设 $c = 2^{256} \bmod n = 2^{256} - n$，并设 $z' = z_{\text{low}} + c z_{\text{high}}$。注意，由于 $c = 2^{256} \pmod{n}$，也有 $z = z' \pmod{n}$。由于 $c$ 只是一个 129 位的数字，$z'$ 只有 385 位，从 512 位降下来，适合 7 个肢（或 6 个肢加一个溢出位）。
• 所以我们可以重复同样的过程，将数字分成低 256 位部分和高 129 位部分，并再次计算 $z_{\text{low}} + c z_{\text{high}}$。结果现在是一个 258 位的值，可以用 5 个肢表示。
• 现在第三次执行此操作，使我们达到 257 位。
• 最后一步，如果最高位被设置，或结果超过 $n$，则减去 $n$。

scalar_4x64 在 secp256k1_scalar_add 和 secp256k1_scalar_mul 中实现了这些，还有许多其他函数实现了对标量的各种操作，但它们大多使用相同的原理。对于 x86_64 系统，包含了汇编代码，因为从 C 语言无法实际观察到执行 64 位整数加法时的进位（溢出）位，尽管硬件会计算它。因此，纯 C 版本不得不采用一种 hack（检查和是否小于其中一个输入），但汇编版本可以直接使用硬件进位标志，通过使用带进位加法指令。

scalar_8x32 使用所有相同的原理，但使用底数 $2^{32}$ 和 32 位肢。这适用于硬件不提供本机 64 位算术的系统（因为这种算术无论如何需要由编译器模拟，或由我们模拟，见下面的 int128）。

3.2.3. int128, 128 位算术实现

当实现 scalar_4x64 时，我们面临一个问题：中间肢乘法结果（如 $x_1 y_3$ 等）是 128 位的值，而 C 语言（按标准）没有 128 位整数类型。因此，将两个 uint64_t 相乘通常只返回结果的低 64 位，丢弃高 64 位。然而，典型的 64 位硬件确实支持计算乘法的完整 128 位结果，尽管它可能没有 128 位寄存器。64 位 ARM 通过有两个单独的指令来解决这个问题，一个用于计算乘法结果的低 64 位，另一个用于高 64 位。64 位 x86_64 通过有一个指令来解决，该指令将低和高 64 位放入两个独立的寄存器。

我们确实想使用这些指令，因为替代方案是将数字表示为八个 32 位肢，将单个乘法指令的数量从 16 提高到 64，这将是一个非常严重的性能损失。

一种选择是依赖汇编代码，但这意味着许多不同的版本，每个支持的平台一个。但许多 C 编译器确实提供了访问完整 128 位结果的方法，而无需诉诸汇编。GCC 和 Clang 提供了一个非标准的 __int128 类型，它在硬件上对应于一对两个 64 位寄存器/变量，否则在软件中模拟，但允许通过此类型计算 uint64_t $\times$ uint64_t $\rightarrow$ __int128 的结果。MSVC 提供了一个特殊的内置函数用于宽乘法，它返回一对两个 uint64_t。

int128 层提供了对这些各种编译器相关方式来访问 128 位乘法结果的抽象，并在其他一些方式中使用它们（足以在 scalar_4x64 中实现乘法逻辑）。它有两个变体：

• int128_native，使用 __int128（仅当编译器提供时）。
• int128_struct，将 128 位整数表示为 64 位整数对。这内部使用编译器内置函数（如果可用，如 MSVC），或使用基于天真的 uint64_t 实现的软件模拟。后者主要用于测试和形式化验证；对于没有 64x64->128 乘法的系统上的生产代码，会完全避免 128 位结果（例如，通过使用 scalar_8x32）。

在下文中，我将使用 uint32_t 表示的数字、但乘法和其他临时结果在 uint64_t 中的算术称为 32/64 位算术，使用 uint64_t 表示的数字、但乘法和其他临时结果在 int128 中的算术称为 64/128 位算术。

3.2.4. field: 有限域元素表示

field 提供了 secp256k1_fe 类型，表示模 $p=2^{256}-2^{32}-977$ 的整数，以及其上的许多算术运算。它有两个变体：

• field_10x26 使用 10 个 uint32_t 肢，底数为 $2^{26}$，因此 $(x_0, x_1, \ldots, x_9)$ 表示域元素 $x_0 + x_1 2^{26} + x_2 2^{52} + x_3 2^{78} + \ldots + x_9 2^{234} \pmod{p}$。实现使用 32/64 位算术。
• field_5x52 使用 5 个 uint64_t 肢，底数为 $2^{52}$，因此 $(x_0, x_1, \ldots, x_4)$ 表示域元素 $x_0 + x_1 2^{52} + x_2 2^{104} + x_3 2^{156} + x_4 2^{208} \pmod{p}$。实现使用 64/128 位算术（使用 int128 层）。

过完备表示。 尽管实现了与 scalar 非常相似的功能（只是模数不同），但它使用了相当不同的表示和不同的算法来实现它们。具体来说，它使用比所需多 25% 的肢，并允许每个肢超过其正常范围。例如，在 field_5x52 中，$2^{100}$ 可以表示为 $(0, 2^{48}, 0, 0, 0)$，但也可以表示为 $(2^{52}, 2^{48}-1, 0, 0, 0)$ 或 $(2^{55}, 2^{48}-8, 0, 0, 0)$，或者许多其他形式。这有两个优点：

• 执行加法时不需要进位；肢可以简单地成对相加。
• 加法后通常可以避免模归约。

性能影响。 域逻辑主要用于实现群运算（点倍乘/加法），在这种情况下，经常有多个域加法和其他操作的序列可以利用这些相同的优点，如取反和与小常数相乘。通过使用这样的过完备表示，我们通常可以避免许多模归约和进位。然而，这是有代价的，因为有 5 个肢，乘法现在需要 25 次 uint64_t 乘法而不是 16 次，或 100 次而不是 64 次（对于 32 位代码）。在 libsecp256k1 最初开发时，这仍然是一个胜利，特别是对于纯 C 代码（需要 hack 来确定进位标志，见上文）。然而，可以引入使用非常不同表示的新域变体。手写汇编的实验表明，对于现代平台，使用四个（有时是五个）64 位肢（而不是 52 位肢）的表示性能可能更好一些。然而，实际使用这些将需要一些 CPU 自动检测代码，以及基于该检测进行分派的方法。

量级。 当然，我们需要小心，不要执行太多加法，否则我们可能会遇到域元素表示的肢超过整数类型范围（field_10x26 变体中的 uint32_t，field_5x52 变体中的 uint64_t）的情况，因为那样进位位实际上会丢失，而没有实际执行进位的代码。为此，我们给每个域元素分配一个“量级”值，以跟踪允许超过 $2^{26}$ 或 $2^{52}$ 的幅度。一个数字的“正常”表示（所有肢都在其正常范围内）被赋予量级 1。将两个量级分别为 $m_1$ 和 $m_2$ 的域元素相加，得到一个量级为 $m_1+m_2$ 的域元素。量级不允许超过 32。如果一个数字会变得太大，调用代码需要调用一个函数来显式地将其量级减少到 1（secp256k1_fe_normalize 和一些变体）。

所有 field.h 操作都记录了函数如何传播量级，以及它们对量级施加了什么约束。field_5x52.h 和 field_10x26.h 文件记录了实际使用的表示，以及量级对它们意味着什么。

域元素的量级是代码的编译时属性，它们实际上不在运行时被追踪（除了在调试模式下，使用 VERIFY 宏），而是更高级代码使用的接口的一部分。如果我们使用类型系统更丰富的语言，就可以将量级作为类型的一个属性（例如作为 C++ 模板参数），但由于这是 C，它只是代码用户（即 libsecp256k1 中的更上层）被期望跟踪的属性，尽管在调试构建中也会被检查（通过断言）。

归一化。 还有另一个类似的属性。一个域元素可能有量级 1，即所有肢都在其正常范围内，但该数字并未完全模 $p$ 归约。例如，$(2^{52}-1, 2^{52}-1, 2^{52}-1, 2^{52}-1, 2^{48}-1)$ 表示 $2^{256}-1 \pmod{p}$，但 $(2^{32}+976, 0, 0, 0, 0)$ 也表示同样的值。大多数操作可以处理两者，但如果我们即将将一个数字序列化为字节以从 API 调用返回，或者如果我们想确定一个数是奇数还是偶数，则必须完全归约，这样我们才能谈论表示数字的规范方式。为此，我们为数字添加了一个类似量级的编译时属性，即归一化，它同样只在调试模式下被显式跟踪。

同时乘法和归约。 由于模数 $p$ 具有如此简单的结构（$p=2^{256}-2^{32}-977$），模归约甚至比标量情况更简单：如果 $x = h_{\text{low}} + 2^{256} h_{\text{high}}$，且 $x' = h_{\text{low}} + (2^{32}+977) h_{\text{high}}$，则 $x = x' \pmod{p}$。这种将高肢通过乘以 $2^{32}+977$ 变成低肢的操作非常简单，以至于域乘法代码（secp256k1_fe_mul）和平方代码（secp256k1_fe_sqr）在乘法过程中同时进行此操作，而不是像 scalar 层那样在后续单独阶段进行。

调试模式。 可以通过设置 VERIFY 宏以调试模式编译库。在这种模式下，field_impl.h 为所有由 field_5x52_impl.h 和 field_10x26_impl.h 提供的函数引入包装器，这些包装器实现了对量级和归一化标志的跟踪和检查，以及更多。CI 涉及设置此标志的测试。

3.2.5. modinv32 和 modinv64: 模逆

这些是通用模逆计算算法和Jacobi 符号计算（Legendre 符号的推广，用于确定一个数是否是模平方）的实现，使用 safegcd 算法的变体。实现了 3 个变体：

• 恒定时间模逆（secp256k1_modinv32 和 secp256k1_modinv64）。
• 可变时间模逆（secp256k1_modinv32_var 和 secp256k1_modinv64_var）。
• 可变时间 Jacobi 符号（secp256k1_jacobi32_maybe_var 和 secp256k1_jacobi64_maybe_var）。maybe 部分表明这些函数可能失败，因此调用者需要提供一个后备方案（通过尝试计算完全平方根来实现）。

表示 在内部，这些算法使用有符号数位表示。modinv64 使用五个基 $2^{62}$ 的 int64_t 肢（允许为负），内部使用 64/128 位算术。modinv32 使用九个基 $2^{30}$ 的 int32_t 肢，使用 32/64 位算术。有符号数位表示使得可以在内部轻松地对值取反，并且也允许更稀疏的模数表示（例如，$p$ 可以表示为 $(-(2^{32}+977), 0, 0, 0, 2^8)$）。

用途 它们被用在 scalar 和 field 内部，以计算模各自素数模 $n$ 和 $p$ 的模逆和 Jacobi 符号。64 位变体（scalar_4x64 和 field_5x52）使用 modinv64，而 32 位变体（scalar_8x32 和 field_10x26）使用 modinv32。

Safegcd 是一种非常快速、现代（2019 年）的算法，用于在恒定时间内计算 GCD 和模逆。其最新变体有 libsecp256k1 贡献者的几项贡献，它的汇编实现是已知最快的恒定时间模逆算法（论文即将发表，希望如此）- libsecp256k1 中的纯 C 实现慢大约 2-2.5 倍，但仍然非常快（在现代桌面系统上大约 1-2 微秒的顺序）。如果你对更多细节感兴趣，我建议查看关于它在 libsecp256k1 中使用的解释器（带有 Python 伪代码）。

3.2.6 group: secp256k1 曲线群上的群运算

这一层实现了点加法、点倍乘和点取反，用于以仿射 $(x,y)$ 坐标（类型 secp256k1_ge）或雅可比 $(X,Y,Z)$ 坐标（类型 secp256k1_gej）表示的点，以及两者之间的转换。还有实现混合加法的变体，其中一个操作数是仿射，一个操作数是雅可比，输出是雅可比。

雅可比坐标的目的是避免求逆。使用基于 safegcd 的逆（见上文），计算一个逆相对较快，但仍然比域乘法慢许多倍（域乘法大约几十纳秒）。完全仿射点加法每个群运算至少需要一个逆（在斜率 $\lambda = \frac{y_2 - y_1}{x_2 - x_1}$ 的计算中），这将完全主导点加法的成本。$Z$ 坐标的作用有点像 $X$ 和 $Y$ 的共享“分母”，允许将所有除法重写为乘法，类似于 $\frac{a}{b} + \frac{c}{d} = \frac{ad+bc}{bd}$。

许多函数有恒定时间和非常数时间变体。恒定时间变体用于处理私钥或其他秘密材料，而（更快的）可变时间变体在其名称中显式带有 _var 后缀（整个代码库中的常见约定）。

在短 Weierstrass 曲线（如 secp256k1）上的恒定时间点加法是一个争议点。该曲线没有任何对所有曲线上的操作数都能正确工作的统一公式，因此需要特殊情况来处理倍乘、添加无穷远点以及添加互为相反数的点。其他曲线，如 ed25519，承认一个对所有情况都统一的公式，这使得恒定时间实现相对更容易。对于 secp256k1，它基本上需要评估所有变体，然后以恒定时间（使用位操作技巧）选择其中之一（参见 secp256k1_fe_cmov，它以恒定时间选择两个域元素之一）。在 libsecp256k1 中，恒定时间点加法在 secp256k1_ge_add_gej 中实现，它执行恒定时间混合加法，并要求仿射输入不是无穷远点。这可行，因为它用于仿射参数来自预计算表的上下文中，所以我们可以知道它不是无穷远点。

这个 secp256k1_ge_add_gej 函数的旧版本没有正确执行此操作，并且它可能是 libsecp256k1 有史以来最接近安全漏洞的一次，尽管我们相信它是不可利用的。使用了一篇论文中的算法，并针对 secp256k1 进行了改编，该论文声称有一个统一的加法公式（我们现在知道对于 secp256k1 不存在），忽略了它只适用于没有两个不同点具有相反 $Y$ 坐标的曲线这个事实。在发现该 bug 后，算法被改编，通过使用更多的 secp256k1_fe_cmov 操作，即使 $Y$ 坐标相等也能工作，结果比总是计算加法和倍乘然后选择两者之一要快一些，但代价是一些复杂性。然而，我们现在也有 Sage 代码 证明从代数上来说，该算法对所有输入都有效（并且，相同的 Sage 代码在旧算法上运行时确实失败）。

3.2.7. 标量乘法: ecmult, ecmult_gen, ecmult_const.

对于常见协议操作，libsecp256k1 中花费的很大一部分时间（我预计至少 80%）是在标量乘法中。因此，代码库的很大一部分致力于使其高效，这并不奇怪。

虽然确切使用的算法太详细无法在此讨论，但有一些它们所基于的技术，了解这些很有用。

计算 $a\cdot P$ 的最简单标量乘法算法包括首先通过重复倍乘计算 $P_i = 2^i \cdot P$，$i\in{0\ldots 255}$，并将 $a[i]$ 定义为 $a$ 的二进制表示的第 $i$ 位。然后最终结果是 $\sum_{i=0}^{255} a[i] \cdot P_i$，选择二进制表示中所有为 1 的位，并将相应的预计算 $P_i$ 倍数相加。

我们经常希望一次计算多个标量乘法的和。例如，在 ECDSA 验证中，需要计算 $u_1 \cdot G + u_2 \cdot Q$。通过从高位到低位工作，我们只需执行 255 次倍乘一次，而不是两次。

假设我们想计算 $101100101_2 \cdot G + 011001110_2 \cdot Q$。每一步我们都会将当前结果加倍，然后 - 从高到低 - 如果相应位被设置，就将 $G$ 或 $Q$ 加到结果中：

• 开始：$R:=0$
• 位 1, 0：$R:=2\cdot R + G$（$1_2 \cdot G + 0_2 \cdot Q$）。
• 位 0, 1：$R:=2\cdot R + Q$（$10_2 \cdot G + 01_2 \cdot Q$）。
• 位 1, 1：$R:=2\cdot R + G + Q$（$101_2 \cdot G + 011_2 \cdot Q$）。
• 位 1, 0：$R:=2\cdot R + G$（$1011_2 \cdot G + 0110_2 \cdot Q$）。
• 位 0, 0：$R:=2\cdot R$（$10110_2 \cdot G + 01100_2 \cdot Q$）。
• 位 0, 1：$R:=2\cdot R + Q$（$101100_2 \cdot G + 011001_2 \cdot Q$）。
• 位 1, 1：$R:=2\cdot R + G + Q$（$1011001_2 \cdot G + 0110011_2 \cdot Q$）。
• 位 0, 1：$R:=2\cdot R + Q$（$10110010_2 \cdot G + 01100111_2 \cdot Q$）。
• 位 1, 0：$R:=2\cdot R + G$（$101100101_2 \cdot G + 011001110_2 \cdot Q$）。

因此，只需每个最大标量每比特 1 次倍乘，以及每个设置位 1 次加法，我们就计算出了结果。使用天真方法预计算 $G$ 和 $Q$ 的 2 次幂然后相加，将需要所有标量合起来每比特 1 次倍乘，以及每个设置位 1 次加法。这个原理是批处理验证加速的基础，因为它意味着一个具有更多乘法的单一方程可以比多个独立方程更高效地验证，且总乘法次数相同。

这称为 Shamir 技巧，它是一个更通用算法 Strauss 技术 的特例。不逐比特工作，而是可以计算一些倍数（例如 ${0,1,2,3,4,5,6,7}$ 乘以每个输入基点），然后将标量分成 3 比特一组，然后通过将结果加倍 3 次，然后对于任何标量中每组非零的 3 比特执行一次添加表项的操作。这增加了一些预计算成本，但将需要执行的加法次数减少了 $\sim 3\times$。

现在注意到，添加一个椭圆曲线点与减去一个点一样困难（它只需要在添加前取反 $Y$ 坐标）。这意味着我们可以有效地将这种技术推广到以允许负数的数制表示的标量。这可以被利用来引入更多的零，从而得到更少的加法。这称为非邻接形式（NAF），因为它从不需要两个相邻的非零数字。它可以与 Strauss 技术结合得到 wNAF（窗口化非邻接形式）。

最后，还有 GLV 自同态，它允许将每个输入乘法对 $a \times P$ 写为 $a_1 P + a_\lambda \cdot (\lambda \cdot P)$，其中 $a_1$ 和 $a_\lambda$ 只是 128 位标量，而 $\lambda \cdot P$ 可以高效计算。因此我们可以将要执行的乘法数量加倍，并且使它们全部长度减半。这是有益的，因为它意味着只需要 127 次倍乘而不是 255 次，同时保持点加法次数不变。

所有这些，加上其他一些更复杂的优化，如有效仿射技术，都在可变时间 ecmult 层中实现，该层用于验证和公钥调整（因为这些不涉及任何私钥材料）。

两个恒定时间变体 ecmult_gen 和 ecmult_const 基于 Mike Hamburg 一篇论文第 3.3 节中描述的有符号数位多组合技术（SDMC）。在 ecmult_const 的情况下，它还与 GLV 自同态结合（代码中记录了一个推导）。对于 ecmult_gen，使用了一个大型的预计算表，包含 $G$ 的倍数，倍乘的成本在表生成时承担，因此 GLV 在那里对于在运行时避免它们没有帮助。

3.2.8. 核心公开 API 实现

最后，secp256k1.c 本身依赖于上述所有层（通过 #include 它们的 _impl.h 文件）和更多，提供了使用上述实现代码实现公开 API 的薄包装器。

这通常涉及在每次调用时在外部和内部表示之间转换输入和输出参数。例如，公钥在内部通常表示为 secp256k1_ge，包含一个 $X$ 和 $Y$ 坐标，加上一个“无穷远”标志。它的大小是平台相关的，在典型系统上为 84 或 88 字节（每个 secp256k1_fe 坐标 40 字节，加上无穷远标志和对齐填充）。我们不希望公开 API 暴露这种平台依赖性，也不希望我们无法在某个或所有系统上使用不同大小的更高效表示（并非不可能！）时更改内部表示。因此，在 API 中，公钥被表示为另一种恰好 64 字节的 secp256k1_pubkey 类型，并且所有 API 调用在必要时在两种表示之间进行转换。

secp256k1.c 还 #include 每个已启用模块的 main_impl.h 文件，这可能会引入模块目录中的更多层。这些添加了以这种方式导出的额外功能。

3.3. 测试

代码通过几种方法进行了广泛测试，并且预期所有新增功能都有测试。直到最近，我们还通过 cryptofuzz 进行差分模糊测试，尽管我不确定那个项目的现状。

3.3.1. 单元测试

测试代码主要在 tests.c 中，一个舒适的 7800 行文件，包含所有核心层的测试。它测试外部 API 和内部层，因此像 secp256k1.c 一样 #include 被测试层的 _impl.h 文件。

每个模块都有其自己的测试，位于模块的 module/M/tests_impl.h 文件中，如果编译了该模块，则被包含在 tests.c 中。这些一起包含另外 3500 行测试。

3.3.2. 穷举群测试

libsecp256k1 中使用的一种新颖的测试技术是所谓的穷举测试，从 tests_exhaustive.c 执行。此文件设置一个特殊的宏 EXHAUSTIVE_TEST_ORDER，导致构建群和标量代码的一个变体。

不实现 secp256k1 曲线 $y^2=x^3+7$，而是实现曲线 $y^2=x^3+2$，带有一个不生成整个群、而只生成阶为 $13$ 的子群的生成元。同样，标量代码现在不实现模 256 位 secp256k1 曲线阶的算术，而是简单地模 $13$（这就是上面提到的 scalar_low 变体发挥作用的地方）。

由于曲线上只有 13 个点，可以用（很大程度上）与生产代码相同的实现来穷举检查许多密码学性质。例如，我们可以测试对于每一个 ECDSA 签名（$R,s$ 对），每一个消息（只有 13 个），以及每一个私钥，签名逻辑是否返回一个有效签名。

3.3.3. 恒定时间测试

时序攻击。 为了保护库免受时序侧信道攻击，我们想确保运行时不会泄露有关它可能操作的私钥材料的任何信息。这在硬件钱包等环境中运行时尤其重要，但在理论上在更多设置中可能是一个问题。

恒定时间代码。 保证此属性的最佳实践是使代码恒定时间。这个术语是用词不当，因为运行时不需要（通常也不是）真的是常数。这通常是不可能的，例如，取决于 CPU 还在做什么，或者 CPU 缓存的状态，可能会有更多或更少的内存访问。实际需要的是运行时不受任何秘密信息的影响。为了实现这一点，通常需要：

• 没有基于秘密信息的代码分支（if、for、while 等）。
• 没有基于秘密信息的内存访问（例如数组索引）。
• 没有涉及秘密信息的可变时间 CPU 指令（例如 x86 上的 div 指令的运行时取决于被除的值）。

Valgrind。 这三个中的最后一个很难保证，但前两个（也许令人惊讶地）可以相当容易地测试。valgrind 工具可以在 CPU 模拟器中运行正常编译的二进制文件，它有能力跟踪使用未初始化内存导致的未定义行为。它的工作方式是维护所有内存的位图，对于每位内存，其值是否已初始化。它相当智能，在某些情况下不会抱怨使用未初始化内存，而是传播它。例如，如果将未初始化内存复制到其他地方，操作会成功，但只是将结果也标记为未初始化。它甚至可以对之执行算术或位运算，只是跟踪哪些值受到未初始化性的影响。

事实上，valgrind 会抱怨的唯一操作是当分支的选择依赖于未初始化内存时，或者当它被用作内存地址时。这些恰好与我们关心的恒定时间性情况相匹配，只是在那里是代码/内存依赖于秘密而不是未初始化内存。

ctgrind。 这在 ctgrind 技术中被利用。编写一个测试程序，使用未初始化内存作为要测试函数的秘密输入，并通过 valgrind 运行它。如果该函数没有表现出任何非常数时间行为，则应该成功。

我们不使用 ctgrind 本身，而是在我们的 ctime_tests.c 代码中实现该技术。为了将输入标记为“未初始化”，它使用 valgrind API，该 API 明确允许我们将内存字节标记为未初始化。相反的情况也用于“解密”某些例程的输出（例如，点乘法的仿射结果可以被认为不是秘密，即使其标量是秘密，如果我们假设离散对数困难）。注意，这不适用于秘密乘法的雅可比结果，因为 $Z$ 坐标可能在理论上揭示一些东西。

注意，非常数时间性依赖于编译器。实际上没有 C 编译器能保证生成恒定时间代码，随着编译器中的优化步骤变得更加复杂，很可能以前产生恒定时间结果的代码在将来版本中不再如此。事实上，版本 0.3.1 和 0.3.2 都是专门为了引入对 Clang 14 和 GCC 13 在某些平台上开始编译为可变时间的解决方法而发布的。注意 -O3 会使这种行为更糟。

MemorySanitizer。 Valgrind 并非在所有平台上都可用，但在其中一些平台上，我们可以使用 msan 作为替代方案，它使用非常相似的内存初始化跟踪和传播，并且也暴露了一个 API 来将内存标记为已初始化或未初始化。

3.4. 基准测试

存在基准测试，分为 3 个程序：bench.c、bench_ecmult.c 和 bench_internal.c。第一个对公开 API 进行基准测试，因此与库链接。最后两个对内部层的函数进行基准测试，因此 #include 相关层。

3.5. 示例

库还包含演示如何使用 API 的示例，位于项目根目录的 examples/ 目录中（在 src/ 之外）。

---

练习

练习 1. 使用你选择的编程语言，为 secp256k1 实现仿射点加法。由于表示标量和域元素将是后面部分的话题，现在不必关注它，因此请随意使用提供大整数算术的语言或库。

测试向量。 全部以十进制仿射 $(x, y)$ 坐标对给出，其中 $x$ 和 $y$ 已模 $p$ 归约到 $[0,p)$ 范围。

(67021774492365321256634043516869791044054964063002935266026048760627130221114, 22817883221438079958217963063610327523693969913024717835557258242342029550595) + (61124938217888369397608518626468079588341162087856379517664485009963441753645, 5723382937169086635766392599511664586625983027860520036338464885987365575658) = (78518484088348927894279633941273782106215956054783044881924083038087974375069, 18400956471605157290158330638123206056219981947313880254846397293938760781200)
(44797955726860071483167773525787460171685721903803276437396496681708013097206, 112878323467240798018200025047246733779416351939079609883282945822975931592141) + (44797955726860071483167773525787460171685721903803276437396496681708013097206, 2913765770075397405370959961441174073853632726560954156174638184932903079522) = 0
(95200151225387174391707134980196577229773167465894787919263504089948495725202, 94213123740092242124032541289267941722641721980066680728855126898974205181980) + (95200151225387174391707134980196577229773167465894787919263504089948495725202, 94213123740092242124032541289267941722641721980066680728855126898974205181980) = (5909177817561749019375996132097716007690336893057112295739767175467136927121, 32162989297956602751967132742255814558956860587998309119003795115938320862381)
(24050370140998638157368766089090079788245793492514664296883668741529047882113, 14478882322437672032054487172211630444001167135141445302555096737662467817571) + (15045863282447234231848775263852322721143017336655001075698483887751182719636, 14478882322437672032054487172211630444001167135141445302555096737662467817571) = (76695855813870323034353443655745505343881173836470898666875431378628604069914, 101313206914878523391516497836476277409268817530499118736902487270246366854092)
(14256779447437936128616290794341059890063336098474125854681710102809814868320, 90566103014364716248988921534849031279541603477816641946022463390335657035131) + (2303067510121489830312323422056091166740725427601969990117485452141659178613, 25225986222951479174582063473838876573728381187823922093435120617573177636532) = (95430772898311369787541983276504378677140303663720683940530878996024106515165, 48068184564993462938397020947826677061288691733511084479824032705110581338856)

练习 2. （可选）参考这个页面上的雅可比点加法算法，并实现它。你也可以从上面链接的 EFD 站点选择一个公式（但要注意，你需要检测输入是否可能是 $P+P$ 或 $P+(-P)$ 的情况，这需要特殊处理），并为 secp256k1 实现雅可比点加法。

测试向量。 所有输入以十进制仿射 $(X, Y, Z)$ 元组给出。输出以仿射坐标给出（因为雅可比结果不唯一）。

(61168739479711927142764658335960185139044138470269152817362835609619277248733, 21365265259791813296359020025112135293342760115353080382870338561918313862807, 37064183328797598544560694959943799168750358913858865780091974718018553562419) + (75776791705958340557958402430698975706422201066979121642449913138944604425660, 66383280047496136929271400526347103822935621943780462161181840552194350141564, 75975606300704613123930174557625573844043347281105167940536468038500802717509) = (72863032945283280953636129059545959529634042357753453132026174732744194676931, 111529132148508388427246132585785101600429639308058372390604751264868469767543)
(89959325059742944430358451400705002920926825355225869621717936807494095714290, 96093053924735119484524007701924861311484651710593769022900107977673928960245, 66142611799578950251083409575885695298839488135797694779041885661190727675299) + (61152793683249667605361745755257610395039301799655537107480658643593848781730, 108824838086741573141078213715633247883899533027170274847878148878014138167046, 20026567909062914103680712539641599080083135680565932483453732406779235372092) = 0
(1547568827951595983041825486208171785819741431893371520256763714464258127790, 87153109579099129796596751254693228766379983077346253255841414029284516911078, 105104885998309941273615701006706417602105584887217436384728254947105995740715) + (102754269592907928248165438489539780821724369832426272173645274109108284691770, 38298190034438650883752719589335983487411860447931052099125319988280170002045, 56745928453254477537417735654158445415425453625586007664329168279192608303666) = (21324256287414615615026299379536579336529998865990184416926039607504524853626, 96719670966356830360698314514227297774284915420887284954650836535688914930874)

练习 3. 使用你在上面实现的仿射或雅可比点加法，为 secp256k1 实现标量乘法。

测试向量。

23529072936145521956642440150769408702836782170707519110832596096096916532363 * (94777218176490725267733209794395406270863807953747235979017564313980479098344, 53121120406880321033414824968851949358991212541220678285657788880408683486672) = (81492582484984365721511233996054540050314813088236204730182464710703690737195, 84165397430175583340352582740254662715932722835371860159802475562062898918484)
77770687059601253501098075906318324640585620643934538062621691587089455400301 * (5187380010089560191829928600869675928625207216422014112981972591844926771008, 75026050083095897004323393777174635055491620440662638678606562665317466685019) = (76999255841974189685876230118581110410155956505185745130247574937430232984638, 87571171775685157828750403037960903210473289232782306139148947195874900187006)
3747619523960563074315083315669137577217731866086110333821423552891044218266 * (66371586610273545144505648512343824229224003523952192165787799288317344396675, 6489011411151914877089190610663845093649879070897583530615192453262848111419) = (109441138145498884726545575659592733193661671281368885246963601136369148387669, 83708880322787879701338478937074052809697986569225329829504559758598509123336)

练习 4. 设 $P=(-6p+29, 1)$ 是 secp256k1 曲线上的一个点。设 $Q$ 是曲线上满足 $3\cdot Q = 5\cdot G - \lambda \cdot P$ 的点。$Q$ 的仿射坐标是什么？

其 $X$ 坐标的最后 3 个十进制数字是 452。

练习 5. （额外）定义 $P_0=G$，以及 $P_{i+1}=P_i+P_i$，第一个满足 $P_i=G$ 的整数 $i>0$ 是多少？

提示：如果你因某种原因需要分解一个相当大的数字，可以尝试 Wolfram Alpha。

答案的最后 3 个十进制数字是 349。

更新日志

• 2026 Apr 14: 移到这里
• 2025 Aug 11: 第 3 部分作为密码学训练营的一部分发布
• 2025 Jul 04: 第 2 部分作为密码学训练营的一部分发布
• 2025 Jun 22: 第 1 部分作为密码学训练营的一部分发布（其他资料见这里）。

• 原文链接： wuille.net/posts/secp256...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～