椭圆曲线密码学（ECC）

椭圆曲线密码学（ECC）是一个现代公钥密码系统家族，其基础是有限域上椭圆曲线的代数结构，以及椭圆曲线离散对数问题（ECDLP）的求解难度。

ECC 实现了非对称密码系统的所有主要能力：加密、签名和密钥交换。

ECC 密码学被认为是 RSA 密码系统在现代的自然继任者，因为在相同安全级别下，ECC 使用的密钥更小、签名更短，而且能够实现非常快速的密钥生成、快速的密钥协商和快速的签名。

ECC 密钥

ECC 中的私钥是整数（取值范围由曲线的域大小决定，通常为 256 位整数）。下面是一个 256 位 ECC 私钥示例（十六进制编码，32 字节，64 个十六进制数字）：0x51897b64e85c3f714bba707e867914295a1377a7463a9dae8ea6a8b914246319。

ECC 密码学中的密钥生成只需在特定范围内安全地生成一个随机整数，因此速度极快。该范围内的任何数都是有效的 ECC 私钥。

ECC 中的公钥是EC 点，即位于曲线上的一对整数坐标 {x, y}。由于其特殊性质，EC 点可以压缩为一个坐标 + 1 位（奇或偶）。因此，与 256 位 ECC 私钥对应的压缩公钥是一个 257 位整数。下面是一个 ECC 公钥示例（对应上述私钥，以 Ethereum 格式编码为带 02 或 03 前缀的十六进制数）：0x02f54ba86dc1ccb5bed0224d23f01ed87e4a443c47fc690d7797a13d41d2340e1a。在这种格式中，公钥实际占用 33 字节（66 个十六进制数字），还可以优化为恰好 257 位。

曲线与密钥长度

ECC 密码算法可以使用不同的底层椭圆曲线。不同曲线提供不同的安全级别（密码强度）、性能（速度）和密钥长度，也可能涉及不同的算法。

流行密码库和安全标准采用的 ECC 曲线具有名称（命名曲线，例如 secp256k1 或 Curve25519）、域大小（决定密钥长度，例如 256 位）、安全强度（通常为域大小 / 2 或更低）、性能（每秒运算次数）以及许多其他参数。

ECC 密钥具有长度，该长度直接取决于底层曲线。在大多数应用（如 OpenSSL、OpenSSH 和 Bitcoin）中，ECC 私钥的默认密钥长度为 256 位；但根据曲线的不同，还可以使用许多其他 ECC 密钥大小：192 位（曲线 secp192r1）、233 位（曲线 sect233k1）、224 位（曲线 secp224k1）、256 位（曲线 secp256k1 和 Curve25519）、283 位（曲线 sect283k1）、384 位（曲线 p384 和 secp384r1）、409 位（曲线 sect409r1）、414 位（曲线 Curve41417）、448 位（曲线 Curve448-Goldilocks）、511 位（曲线 M-511）、521 位（曲线 P-521）、571 位（曲线 sect571k1）等。

ECC 算法

椭圆曲线密码学（ECC）基于有限域上椭圆曲线的数学原理，提供以下几类算法：

• ECC 数字签名算法，例如用于经典曲线的 ECDSA 和用于扭曲 Edwards 曲线的 EdDSA。
• ECC 加密算法和混合加密方案，例如 ECIES 集成加密方案和 EEECC（基于 EC 的 ElGamal）。
• ECC 密钥协商算法，例如 ECDH、X25519 和 FHMQV。

所有这些算法都使用一条底层曲线（如 secp256k1、curve25519 或 p521）进行计算，并依赖 ECDLP（椭圆曲线离散对数问题）的求解难度。所有这些算法都使用公私钥对，其中私钥是整数，公钥是椭圆曲线上的点（EC 点）。下面详细了解有限域上的椭圆曲线。

椭圆曲线

在数学中，椭圆曲线是平面代数曲线，由方程所描述的所有点 {x, y} 组成：

密码学使用简化形式（Weierstrass 形式）的椭圆曲线，其定义如下：

• y^2 = x^3 + a_x + b_

例如，NIST 曲线 secp256k1（用于 Bitcoin）基于以下形式的椭圆曲线：

• y^2 = x^3 + 7（上述椭圆曲线方程，其中 a = 0 且 b = 7）

上述椭圆曲线的可视化如下：

要进一步了解椭圆曲线方程及其形状，可以尝试这个在线椭圆曲线可视化工具：https://www.desmos.com/calculator/ialhd71we3。

有限域上的椭圆曲线

椭圆曲线密码学（ECC）使用定义在有限域 𝔽p（其中 p 为素数且 p > 3）或 𝔽2m（其中域大小 p = 2_m_）上的椭圆曲线。这意味着该域是大小为 p x p 的方阵，曲线上的点仅限于该域内的整数坐标。域内的所有代数运算（如点加法和乘法）都会得到域内的另一个点。有限域 𝔽p 上的椭圆曲线方程采用以下模形式：

• y^2 ≡ x^3 + a_x + b (mod p_)

相应地，“Bitcoin 曲线”secp256k1 采用以下形式：

• y^2 ≡ x^3 + 7 (mod p)

与将范围 [0...p-1] 内的整数（域 ℤp）用作密钥空间的 RSA 不同，ECC 使用 Galois 域 𝔽p 中的点 {x, y}（其中 x 和 y 是范围 [0...p-1] 内的整数）。

有限域 𝔽p 上的椭圆曲线由以下内容组成：

• 一组整数坐标 {x, y}，满足 0 ≤ x, y < p
• 位于椭圆曲线上：y^2 ≡ x^3 + a_x + b_ (mod p)

有限域 𝔽17 上的椭圆曲线示例：

• y^2 ≡ x^3 + 7 (mod 17)

𝔽17 上的这条椭圆曲线如下所示：

请注意，有限域上的椭圆曲线 y^2 ≡ x^3 + 7 (mod 17) 由上图中的蓝色点组成。也就是说，密码学中使用的“椭圆曲线”实际上是“方阵中的点集”，而不是经典意义上的“曲线”。

上述曲线仅用于“教学”，其密钥长度非常短（4-5 位）。在实际应用中，开发者通常使用 256 位或更高位数的曲线。

有限域上的椭圆曲线：计算

判断某个点是否属于有限域上的某条椭圆曲线非常容易。例如，当且仅当满足以下条件时，点 {x, y} 属于曲线 y^2 ≡ x^3 + 7 (mod 17)：

• x^3 + 7 - y^2 ≡ 0 (mod 17)

点 P {5, 8} 属于该曲线，因为 (5**3 + 7 - 8**2) % 17 == 0。点 {9, 15} 不属于该曲线，因为 (9**3 + 7 - 15**2) % 17 != 0。这些计算采用 Python 风格。下面将上述椭圆曲线以及点 {5, 8} 和 {9, 15} 可视化：

ECC 点乘以整数

椭圆曲线上的两个点（EC 点）可以相加，结果是另一个点。这一运算称为 EC 点加法。如果将点 G 与自身相加，结果为 G + G = 2 * G。如果再将 G 与该结果相加，就会得到 3 * G，依此类推。这就是 EC 点乘法的定义。

有限域上椭圆曲线的点 G（EC 点）可以乘以整数 k，结果是同一曲线上的另一个 EC 点 P，而且该运算速度很快：

• P = k * G

上述运算涉及一些公式和变换，为简单起见，这里将其略过。需要重点了解的是，EC 点乘以整数会得到同一曲线上的另一个 EC 点，而且这一运算速度很快。EC 点乘以 0 会得到一个称为“无穷远点”的特殊 EC 点。

可以在 Wikipedia 上进一步了解 EC 点乘法。

示例：EC 点乘以整数

对于不同的曲线表示形式，EC 乘法公式也不同。在本例中，我们将使用经典 Weierstrass 形式的椭圆曲线。

例如，取有限域上椭圆曲线 y^2 ≡ x^3 + 7 (mod 17) 的 EC 点 G = {15, 13}，并将其乘以 k = 6。我们将得到 EC 点 P = {5, 8}：

• P = k * G = 6 * {15, 13} = {5, 8}

下图将这个 EC 点乘法示例可视化：

椭圆曲线的阶与余因子

有限域上的椭圆曲线可以形成一个有限循环代数群，其中包含曲线上的所有点。在循环群中，将两个 EC 点相加或将一个 EC 点乘以整数，结果仍是同一循环群（及同一曲线）中的另一个 EC 点。曲线的阶是曲线上 EC 点的总数。这一总数还包括一个称为“无穷远点”的特殊点，它在点乘以 0 时得到。

有些曲线形成单个循环群（包含其全部 EC 点），另一些曲线则形成若干互不重叠的循环子群（每个子群包含曲线 EC 点的一个子集）。在后一种情况下，曲线上的点被划分为 h 个循环子群（分区），每个子群的阶为 r（每个子群包含相同数量的点）。整个群的阶为 n = h * r（子群数量乘以每个子群中的点数）。包含这些 EC 点的子群数量 h 称为余因子。

余因子通常用以下公式表示：

• h = n / r

其中：

• n 是曲线的阶（曲线上所有点的数量）
• h 是曲线的余因子（互不重叠的点子群数量，这些子群共同包含曲线上的所有点）
• r 是子群的阶（每个子群中的点数，包括每个子群的无穷远点）

换言之，椭圆曲线上的点位于一个或多个互不重叠的子集中，这些子集称为循环子群。子群的数量称为“余因子”。所有子群中的点总数称为曲线的“阶”，通常以 n 表示。如果曲线仅由一个循环子群组成，其余因子 h = 1。如果曲线由多个子群组成，则其余因子 > 1。

• 余因子 = 1 的椭圆曲线示例是 secp256k1。
• 余因子 = 8 的椭圆曲线示例是 Curve25519。
• 余因子 = 4 的椭圆曲线示例是 Curve448。

ECC 中的“生成点”

对于有限域上的椭圆曲线，ECC 密码系统会预先定义一个特殊的常量 EC 点，称为生成点 G（基点）。通过将 G 乘以范围 [0...r] 内的某个整数，可以生成椭圆曲线上其子群内的任何其他点。数 r 称为循环子群的“阶”（子群中所有点的总数）。

对于余因子 = 1 的曲线，只有一个子群，曲线的阶 n（曲线上不同点的总数，包括无穷远点）等于数 r。

当 G 和 n 经过精心选择且余因子 = 1 时，通过将生成点 G 乘以范围 [1...n] 内的整数，可以生成曲线上所有可能的 EC 点（包括特殊的无穷远点）。这个整数 n 称为“曲线的阶”。

需要注意的是，由某个 EC 生成点 G 得到的子群阶 r（可能不同于曲线的阶）决定了该曲线所有可能私钥的总数：r = n / h（曲线阶除以曲线余因子）。密码学家会精心选择椭圆曲线的域参数（曲线方程、生成点、余因子等），以确保对于特定密码强度而言，密钥空间足够大。

总而言之，在 ECC 密码学中，EC 点与生成点 G 共同形成循环群（或循环子群）。这意味着存在一个数 r（r > 1），使得 r * G = 0 * G = infinity，且子群中的所有点都可以通过将 G 乘以范围 [1...r] 内的整数获得。数 r 称为群（或子群）的阶。

椭圆曲线子群通常有许多生成点，但密码学家会从中精心选择一个既能生成整个群（或子群）、又适合优化计算性能的点。这个生成点称为“G”。

已知对于某些曲线，不同生成点会生成不同阶的子群。更准确地说，如果群的阶为 n，那么对于每个能整除 n 的素数 d，都存在一个点 Q，使得 d * Q = infinity。这意味着同一曲线上的某些点用作生成点时，会生成比其他点更小的子群。如果群很小，安全性就很弱。这称为“小子群”攻击。因此，密码学家通常选择一个素数作为子群阶 r。

对于余因子 h > 1 的椭圆曲线，不同基点可以生成曲线上不同的 EC 点子群。选择某个生成点，就意味着选择在曲线上的某个点子群中进行运算，大多数 EC 点运算和 ECC 密码算法都能正常工作。但在某些情况下仍需格外注意，因此建议只使用经过验证的 ECC 实现、算法和软件包。

生成点——示例

在上述示例（有限域上的 EC：y^2 ≡ x^3 + 7 mod 17）中，如果将点 G = {15, 13} 作为生成点，那么将 G 乘以范围 [1...18] 内的某个整数，就能得到曲线上的任何其他点。因此，该 EC 的阶为 n = 18，余因子为 h = 1。

请注意，该曲线有 17 个普通 EC 点（如上图所示）+ 一个特殊的“无穷远点”，它们全都位于同一个子群中，因此曲线的阶为 18（而不是 17）。

还要注意，如果将点 {5, 9} 作为生成点，它将只生成 3 个 EC 点：{5, 8}、{5, 9} 和 infinity。由于曲线阶不是素数，不同生成点可能会生成不同阶的子群。这很好地说明了为什么不应为密码学用途自行“发明”椭圆曲线，而应使用经过验证的曲线。

ECC 中的私钥、公钥与生成点

在 ECC 中，将固定 EC 点 G（生成点）乘以某个整数 k（k 可视为私钥），就会得到 EC 点 P（其对应的公钥）。

因此，ECC 包含以下元素：

• 有限域 𝔽p 上的椭圆曲线（EC）
• G == 生成点（固定常量，EC 上的基点）
• k == 私钥（整数）
• P == 公钥（点）

使用著名的 ECC 乘法算法，可以在 log_2(k_) 时间内非常快速地计算 P = k * G，例如“倍点加算法”。对于 256 位曲线，只需进行数百次简单的 EC 运算。

计算 k = P / G 的速度极其缓慢（对于较大的 k，被认为不可行）。

这种不对称性（乘法很快，逆运算却慢到不可行）是 ECC 密码学安全强度的基础，也称为 ECDLP 问题。

椭圆曲线离散对数问题（ECDLP）

计算机科学中的椭圆曲线离散对数问题（ECDLP）定义如下：

• 给定有限域 𝔽p 上的椭圆曲线、曲线上的生成点 G 和点 P，求整数 k（如果存在），使得 P = k * G

对于密码学家精心选择的有限域和椭圆曲线，ECDLP 问题没有高效解法。

群 𝔽p 中椭圆曲线点的乘法类似于群 ℤp 中整数的幂运算（这称为乘法记法），这也说明了 ECDLP 问题与 DLP 问题（离散对数问题）的相似之处。

在 ECC 密码学中，许多算法都依赖于精心选择的域 𝔽p 和椭圆曲线上的 ECDLP 问题的计算难度，目前不存在高效算法可以解决该问题。

ECC 与曲线安全强度

由于目前解决大小为 k 的密钥所对应 ECDLP 的最快已知算法需要 $$\sqrt{k}$$ 步，因此，要达到 k 位安全强度，至少需要 2*k位曲线。所以，256 位椭圆曲线（域大小 p 为 256 位数）通常能提供接近 128 位的安全强度。

实际上，其强度会略低一些，因为曲线的阶（n）通常小于域大小（p），曲线的余因子也可能满足 h > 1（且子群阶 r = n / h，小于 n），并且所需步数并非恰好为 $$\sqrt{k}$$，而是 $$0.886 * \sqrt{k}$$。此处给出了最流行标准椭圆曲线的精确安全强度估算：http://safecurves.cr.yp.to/rho.html。

例如，secp256k1（p = 256）曲线提供 ~ 128 位安全性（准确地说是 127.8 位），而 Curve448（p = 448）提供 ~ 224 位安全性（准确地说是 222.8 位）。

EC 点乘法——Python 示例

了解这些概念后，下面来编写一些代码。我们将使用 Python 库 tinyec，它提供 ECC 原语，例如循环群（SubGroup 类）、有限域上的椭圆曲线（Curve 类）和 EC 点（Point 类）。首先安装 tinyec 包：

pip install tinyec

我们将使用前面示例中的教学曲线 y^2 ≡ x^3 + 7 (mod 17)，其生成点为 G = {15, 13}，阶为 n = 18。我们将其命名为 p1707。

from tinyec.ec import SubGroup, Curve

field = SubGroup(p=17, g=(15, 13), n=18, h=1)
curve = Curve(a=0, b=7, field=field, name='p1707')
print('curve:', curve)

for k in range(0, 25):
    p = k * curve.g
    print(f"{k} * G = ({p.x}, {p.y})")

运行上述代码示例：https://repl.it/@nakov/EC-points-in-Python。上述代码演示了 EC 乘法，它将生成点 G 分别乘以 0、1、2、...、24。上述程序的输出如下：

curve: "p1707" => y^2 = x^3 + 0x + 7 (mod 17)
0 * G = (None, None)
1 * G = (15, 13)
2 * G = (2, 10)
3 * G = (8, 3)
4 * G = (12, 1)
5 * G = (6, 6)
6 * G = (5, 8)
7 * G = (10, 15)
8 * G = (1, 12)
9 * G = (3, 0)
10 * G = (1, 5)
11 * G = (10, 2)
12 * G = (5, 9)
13 * G = (6, 11)
14 * G = (12, 16)
15 * G = (8, 14)
16 * G = (2, 7)
17 * G = (15, 4)
18 * G = (None, None)
19 * G = (15, 13)
20 * G = (2, 10)
21 * G = (8, 3)
22 * G = (12, 1)
23 * G = (6, 6)
24 * G = (5, 8)

可以看到 0 * G = infinity。还可以清楚看出，EC 群是循环的，其阶为 n = 18，因为从 k = 18 开始，后续各点会重复最初的点：

• 18 * G = 0 * G = infinity
• 19 * G = 1 * G = {15, 13}
• 20 * G = 2 * G = {2, 10}
• 21 * G = 3 * G = {8, 3}
• 依此类推。

生成点 G 分别乘以 2、3、4、...、17 所生成的 EC 点如下图所示：

稍微修改上述示例，将生成点改为 G' = {5, 9}。输出将发生显著变化：

from tinyec.ec import SubGroup, Curve

field = SubGroup(p=17, g=(5, 9), n=18, h=1)
curve = Curve(a=0, b=7, field=field, name='p1707')
print('curve:', curve)

for k in range(0, 25):
    p = k * curve.g
    print(f"{k} * G' = ({p.x}, {p.y})")

运行上述代码示例：https://repl.it/@nakov/EC-points-by-generator-point-in-Python。输出表明，新生成点的子群阶不是 18，而是 3。这是可能的，因为 18 不是素数。从输出可以清楚看出，3 * G' = infinity，所得子群阶为 3：

curve: "p1707" => y^2 = x^3 + 0x + 7 (mod 17)
0 * G' = (None, None)
1 * G' = (5, 9)
2 * G' = (5, 8)
3 * G' = (None, None)
4 * G' = (5, 9)
5 * G' = (5, 8)
6 * G' = (None, None)
...

上述示例再次说明，用于密码学的椭圆曲线应由密码学家设计，而不是由开发者设计。开发者应依赖成熟的密码标准和经过验证的密码库。

EC 点乘法——Python 实际应用示例

现在编写一个实际应用示例。我们不再使用教学曲线 p1707（4-5 位曲线，p = 17），而是使用 192 位密码学曲线 secp192r1（192 位，p = 6277101735386680763835789423207666416083908700390324961279）。下面的示例与前一个示例类似：

from tinyec import registry

curve = registry.get_curve('secp192r1')
print('curve:', curve)

for k in range(0, 10):
    p = k * curve.g
    print(f"{k} * G = ({p.x}, {p.y})")

print("Cofactor =", curve.field.h)

print('Cyclic group order =', curve.field.n)

nG = curve.field.n * curve.g
print(f"n * G = ({nG.x}, {nG.y})")

运行上述代码示例：https://repl.it/@nakov/EC-points-in-real-world-in-Python。其输出也与前一个示例类似：

curve: "secp192r1" => y^2 = x^3 + 6277101735386680763835789423207666416083908700390324961276x + 2455155546008943817740293915197451784769108058161191238065 (mod 6277101735386680763835789423207666416083908700390324961279)
0 * G = (None, None)
1 * G = (602046282375688656758213480587526111916698976636884684818, 174050332293622031404857552280219410364023488927386650641)
2 * G = (5369744403678710563432458361254544170966096384586764429448, 5429234379789071039750654906915254128254326554272718558123)
3 * G = (2915109630280678890720206779706963455590627465886103135194, 2946626711558792003980654088990112021985937607003425539581)
4 * G = (1305994880430903997305943738697779408316929565234787837114, 3981863977451150342116987835776121688410789618551673306674)
5 * G = (410283251116784874018993562136566870110676706936762660240, 1206654674899825246688205669651974202006189255452737318561)
6 * G = (4008504146453526025173196900303594155799995627910231899946, 3263759301305176906990806636587838100022690095020155627760)
7 * G = (3473339081378406123852871299395262476289672479707038350589, 2152713176906603604200842901176476029776544337891569565621)
8 * G = (1167950611014894512313033362696697441497340081390841490910, 4002177906111215127148483369584652296488769677804145538752)
9 * G = (3176317450453705650283775811228493626776489433309636475023, 44601893774669384766793803854980115179612118075017062201)
Cofactor = 1
Cyclic group order = 6277101735386680763835789423176059013767194773182842284081
n * G = (None, None)

曲线 secp192r1 使用一个阶非常大的循环群，其 n = 6277101735386680763835789423176059013767194773182842284081（素数），余因子 h = 1。正如预期，n * G = infinity，与前面的教学曲线示例一样。

现在生成一个随机私钥 privKey（范围 [0...n-1] 内的整数）及其对应的公钥 pubKey = privKey * G：

from tinyec import registry
import secrets

curve = registry.get_curve('secp192r1')

privKey = secrets.randbelow(curve.field.n)
pubKey = privKey * curve.g
print("private key:", privKey)
print("public key:", pubKey)

运行上述代码示例：https://repl.it/@nakov/EC-points-private-public-keys-in-Python。上述代码将生成如下输出：

private key: 4225655318977962031264230130242180748818603147467615868902
public key: (5396030834456770190396776530938374882273836179487834152291, 3422160588166914010077732710830109086004758012634997793937) on "secp192r1" => y^2 = x^3 + 6277101735386680763835789423207666416083908700390324961276x + 2455155546008943817740293915197451784769108058161191238065 (mod 6277101735386680763835789423207666416083908700390324961279)

稍后将使用这样的 ECC 密钥对 {私钥, 公钥} 来加密数据、签署消息和验证签名。

请注意，在实际项目中，192 位曲线被认为较弱，因此建议使用 256 位或更高位数的曲线，其密钥也相应为 256 位或更长。上述示例使用 192 位曲线只是为了缩短示例输出。

椭圆曲线密码系统中的公钥压缩

有限域 𝔽p 上的椭圆曲线（Weierstrass 形式）中，每个 x 坐标最多对应 2 个点（奇数 y 和偶数 y）。这一性质源于椭圆曲线方程本身，如下图所示：

由于这一性质，椭圆曲线点（以及相应的 ECC 公钥）P {x, y} 可以压缩为 C {x, odd/even)。这意味着从点中去掉 y 坐标，并用 1 位表示它（奇数 y 或偶数 y）。

压缩 EC 点是将 EC 点 {x, y} 表示为更短的形式 {x, odd / even}。ECC 公钥是 EC 点，因此也可以用相同方式压缩。

要解压缩一个点，可以使用以下公式计算其两个可能的 y 坐标：

• y1 = mod_sqrt(x^3 + ax + b, p)
• y2 = p - mod_sqrt(x^3 + ax + b, p)

然后根据压缩表示中的附加奇偶校验位，从上述坐标中选择奇数或偶数坐标。

模平方根（mod_sqrt）可以使用 Tonelli–Shanks 算法计算。

来看一个示例：在椭圆曲线 y^2 ≡ x^3 + 7 (mod 17) 上，点 P {10, 15} 可以压缩为 C {10, odd}。进行解压缩时，首先使用上述公式计算 x = 10 对应的两个可能 y 坐标：y1 = 2 和 y2 = 15。然后选择其中的奇数：y = 15。解压缩后的点为 {10, 15}。

压缩 EC 点 / 公钥——Python 示例

下面的代码使用 Python 实现公钥压缩和解压缩。由于 Python 不提供“模平方根”函数，因此代码使用名为 nummaster 的库。首先安装 nummaster 包：

pip install nummaster

现在使用 Python 实现 EC 点压缩和解压缩函数：

from nummaster.basic import sqrtmod

def compress_point(point):
    return (point[0], point[1] % 2)

def uncompress_point(compressed_point, p, a, b):
    x, is_odd = compressed_point
    y = sqrtmod(pow(x, 3, p) + a * x + b, p)
    if bool(is_odd) == bool(y & 1):
        return (x, y)
    return (x, p - y)

最后，以曲线 y^2 ≡ x^3 + 7 (mod 17) 上的点 {10, 15} 为例，对其进行压缩和解压缩：

p, a, b = 17, 0, 7
point = (10, 15)
print(f"original point = {point}")
compressed_p = compress_point(point)
print(f"compressed = {compressed_p}")
restored_p = uncompress_point(compressed_p, p, a, b)
print(f"uncompressed = {restored_p}")

运行上述代码示例：https://repl.it/@nakov/EC-point-compression-decompression-in-Python。上述代码的输出为：

original point = (10, 15)
compressed = (10, 1)
uncompressed = (10, 15)

ECC 的椭圆曲线域参数

ECC 椭圆曲线由一组椭圆曲线域参数描述，例如曲线方程参数、域参数和生成点坐标。这些参数由密码学标准规定，例如：

• SEC 2：推荐的椭圆曲线域参数
• NIST FIPS PUB 186-4 数字签名标准（DSS）
• Brainpool ECC 标准（RFC-5639）

这些标准定义了一组命名曲线的参数，例如 secp256k1、P-521 和 brainpoolP512t1。这些密码标准所描述的有限域椭圆曲线已由密码学家进行了充分研究和分析，并被认为具有特定的安全强度，相应强度也在这些标准中有所说明。

一些密码学家（如 Daniel Bernstein）认为，官方密码标准中描述的大多数曲线“不安全”，并制定了自己的密码标准，从更广泛的层面考量 ECC 安全性。

Bernstein 的 SafeCurves 标准列出了根据一系列 ECC 安全要求被认为安全的曲线。该标准可在 https://safecurves.cr.yp.to 查看。

为 ECC 选择椭圆曲线

要使用 ECC，所有通信方都应就 EC 域参数（定义椭圆曲线的所有元素）达成一致。强烈建议使用上述标准中的命名曲线，且模数至少为 256 位。标准曲线经过密码学家的充分研究，其安全强度更有保障。

不要使用自己设计的椭圆曲线（采用非标准域参数），除非你是经验丰富的密码学家，并且非常清楚自己在做什么！许多曲线存在弱点，会降低 ECDLP 问题的难度并损害安全性。如果担心曲线中存在后门，请使用 SafeCurves 列表中的标准安全曲线。

命名曲线——示例

ECC 密码学使用有限域上的椭圆曲线，其中模数 p 和阶 n 是非常大的整数（n 通常是素数），例如 256 位数。曲线的有限域呈大小为 p x p 的方形，其规模极其庞大；曲线上所有可能的 EC 点数量（曲线的阶 n）也是一个非常大的整数，例如 256 位。以 secp256k1 曲线（Bitcoin 曲线）为例，其域参数定义如下：

• p（模数）= 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
• n（阶；大小；所有可能 EC 点的数量）= 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
• a（y^2 ≡ x^3 + a*x + b (mod p) 中的常量“a”）= 0x0000000000000000000000000000000000000000000000000000000000000000
• b（y^2 ≡ x^3 + a*x + b (mod p) 中的常量“b”）= 0x0000000000000000000000000000000000000000000000000000000000000007
• g（曲线生成点 G {x, y}）= (0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)
• h（余因子，通常为 1）= 01

我们已经知道，256 位曲线（即 p 和 n 都是 256 位数）提供 128 位安全强度，这意味着，要根据公钥或签名找出私钥，已知最优的非量子算法大约需要 2^128 次运算。上述 ECC 曲线 secp256k1 具有 128 位强度。

使用“secp256k1”曲线的 Python 示例

现在实际使用上述 secp256k1 曲线的域参数。下面定义 EC，并为某个私钥计算公钥：

from tinyec.ec import SubGroup, Curve

# Domain parameters for the `secp256k1` curve
# (as defined in http://www.secg.org/sec2-v2.pdf)
name = 'secp256k1'
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
a = 0x0000000000000000000000000000000000000000000000000000000000000000
b = 0x0000000000000000000000000000000000000000000000000000000000000007
g = (0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,
     0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)
h = 1
curve = Curve(a, b, SubGroup(p, g, n, h), name)
print('curve:', curve)

privKey = int('0x51897b64e85c3f714bba707e867914295a1377a7463a9dae8ea6a8b914246319', 16)
print('privKey:', hex(privKey)[2:])

pubKey = curve.g * privKey
pubKeyCompressed = '0' + str(2 + pubKey.y % 2) + str(hex(pubKey.x)[2:])
print('pubKey:', pubKeyCompressed)

运行上述代码示例：https://repl.it/@nakov/secp256k1-curve-in-Python。上述代码通过域参数定义 secp256k1 曲线，并根据给定私钥计算公钥。具体做法是将曲线生成点 G 乘以私钥。从程序输出可以看出，结果是正确的：

curve: "secp256k1" => y^2 = x^3 + 0x + 7 (mod 115792089237316195423570985008687907853269984665640564039457584007908834671663)
privKey: 51897b64e85c3f714bba707e867914295a1377a7463a9dae8ea6a8b914246319
pubKey: 02f54ba86dc1ccb5bed0224d23f01ed87e4a443c47fc690d7797a13d41d2340e1a

公钥经过压缩，并以标准格式编码（将 y 坐标编码为前缀 02 或 03）。

Edwards 曲线

椭圆曲线密码学（ECC）中的椭圆曲线可以采用多种形式（表示），这些形式已被证明是双有理等价的（同构）：

• 椭圆曲线的 Weierstrass 形式：
  • y^2 = x^3 + a_x + b_
  • ECC 中使用的 Weierstrass 曲线示例是 secp256k1，其形式为 y^2 = x^3 + 7
• 椭圆曲线的 Montgomery 形式：
  • B_y^2 = x^3 + A_x^2 + x
  • ECC 中使用的 Montgomery 曲线示例是 Curve25519，其形式为 y^2 = x^3 + _486662_x^2 + x
• 椭圆曲线的 Edwards 形式：
  • x^2 + y^2 = 1 + _d_x^2y^2
  • ECC 中使用的 Edwards 曲线示例是 Curve448，其形式为 x^2 + y^2 = 1 - _39081_x^2y^2

出于性能考虑，椭圆曲线密码学（ECC）有时会使用Edwards 曲线，即采用以下形式的椭圆曲线：

• x^2 + y^2 = 1 + _d_x^2y^2

例如，当 d = 300 时，Edwards 曲线 x^2 + y^2 = 1 + _300_x^2y^2 如下所示：

每条 Edwards 曲线都与一条 Weierstrass 形式的椭圆曲线（y^2 = x^3 + a_x + b_）双有理等价，因此具有与经典椭圆曲线相同的性质。

有限素域 𝔽p 上的 Edwards 曲线（其中 p 是大素数）能够快速执行整数与 EC 点的乘法，具有与经典椭圆曲线相似的密码学性质，而且其 ECDLP 问题具有相同的计算难度，适合用于密码学。

有限素域上著名的密码学 Edwards 椭圆曲线示例包括：Curve1174（251 位）、Curve25519（255 位）、Curve383187（383 位）、Curve41417（414 位）、Curve448（448 位）、E-521（521 位）等。

Curve25519、X25519 和 Ed25519

通过精心选择曲线参数，有限域上的 Edwards 曲线可以实现 ECC 密码系统，以非常高的性能提供 ECDH 密钥协商方案、数字签名和混合加密方案。

例如，Curve25519 是一条 Edwards 曲线，由以下 Montgomery 形式的椭圆曲线方程定义：

• y^2 = x^3 + 486662x^2 + x

它定义在有限素域 𝔽p 上，其中 p = 2^255 - 19（该曲线为 255 位）。

实际上，上述方程并不直接符合 Edwards 曲线方程，但已证明它与以下扭曲 Edwards 曲线（称为 edwards25519）双有理等价：

• -x^2 + y^2 = 1 + 37095705934669439343138083508754565189542113879843219016388785533085940283555x^2y^2

椭圆曲线 Curve25519 由所有整数坐标点 {x, y} 组成，并由以下模方程定义：

• y^2 ≡ x^3 + 486662x^2 + x (mod 2^255 - 19)

上述方程在经典椭圆曲线 Weierstrass 形式（y^2 = x^3 + a_x + b_）中有其等价形式，但上面的形式专为速度优化而设计。

Curve25519 由 Daniel Bernstein 领导的密码学家团队精心设计，在设计和实现的多个层面进行了优化，以便在不牺牲安全性的前提下实现极高速度。

Curve25519 的阶（在其底层循环群中）为 n = 2^252 + 0x14def9dea2f79cd65812631a5cf5d3ed，余因子为 h = 8，并提供 125.8 位安全强度（有时称为 ~ 128 位安全性）。Curve25519 的私钥为 251 位，通常编码为 256 位整数（32 字节，64 个十六进制数字）。公钥通常也编码为 256 位整数（255 位 y 坐标 + 1 位 x 坐标），这对开发者非常方便。

基于 Curve25519 派生出名为 X25519 的 ECDH 函数（用于椭圆曲线 Diffie–Hellman 密钥协商方案），还基于 EdDSA 算法派生出名为 Ed25519 的快速数字签名方案。这些方案速度非常快，因为其中涉及小整数的乘法和其他简单运算（大多为 32 位算术），可以在现代微处理器（CPU）中高效实现。请注意，X25519 和 Ed25519 对 EC 点使用不同的编码，因此不能直接兼容；如果要使用同一公私钥对，则需要进行转换。

Curve448、X448 和 Ed448

Curve448（Curve448-Goldilocks）是一条非扭曲 Edwards 曲线，由以下方程定义：

• x^2 + y^2 = 1 - 39081x^2y^2

它定义在有限素域 𝔽p 上，其中 p = 2^448 - 2^224 - 1。其阶为 n = 2^446 - 0x8335dc163bb124b65129c96fde933d8d723a70aadc873d6d54a7bb0d，余因子为 h = 4。与其他 Edwards 曲线一样，Curve448 在 Weierstrass 形式（y^2 = x^3 + a_x + b_）中存在等价形式，但上述 Edwards 形式可以显著优化 EC 点计算并提升性能。

Curve448 提供 ~ 224 位安全级别（更准确地说是 222.8 位）。Curve448 的私钥为 446 位，通常编码为 448 位整数（56 字节，112 个十六进制数字）。公钥也编码为 448 位整数。

Curve448 适用于 ECDH 密钥协商（称为 X448 的 ECDH 函数）和快速数字签名（称为 Ed448 或 edwards448 的 EdDSA 算法）。请注意，X448 和 Ed448 对 EC 点使用不同的编码，因此不能直接兼容；如果要使用同一公私钥对，则需要进行转换。

Curve25519 还是 Curve448？

当应用需要更高的安全级别时，应优先选择 Curve448 而不是 Curve25519；但请注意，Curve448 的速度大约比 Curve25519 慢 3 倍，并且使用更长的密钥和签名。

当需要更好的性能以及更小的密钥和签名时，应优先选择 Curve25519 而不是 Curve448。

可以从以下资料中深入了解 Curve25519 和 Curve448 的技术细节：

• RFC 7748——用于安全的椭圆曲线：实现 X25519 和 X448 密钥交换协议的互联网技术标准。
• RFC 8032——Edwards 曲线数字签名算法（EdDSA）：实现 Ed25519 和 EdDSA-Ed448 签名方案的互联网技术标准。

通常应注意，Curve25519 的速度更快，优于 secp256k1 及其他 256 位标准 NIST 曲线，而且被认为更加安全，因此是实现 ~ 128 位安全性的推荐选择。同样，Curve448 的性能优于密钥长度相近的经典曲线，因此是实现 ~ 224 位安全性的推荐曲线。

Curve25519——Python 示例

为了演示椭圆曲线 Curve25519 的实际用法，首先安装 Python 密码库 pynacl：

pip install pynacl

网络与密码学（NaCl）库的 Python 绑定（PyNaCl）实现了许多现代密码算法，包括 Curve25519 上的 EC 点算术和 Ed25519 签名。

接下来，在 Curve25519 上生成一个随机的 252 位私钥及其对应的公钥（EC 点）；两个密钥在内部都将编码为 256 位整数：

from nacl.public import PrivateKey
import binascii

privKey = PrivateKey.generate()
pubKey = privKey.public_key

print("privKey:", binascii.hexlify(bytes(privKey)))
print("pubKey: ", binascii.hexlify(bytes(pubKey)))

运行上述代码示例：https://repl.it/@nakov/Curve25519-in-Python。上述代码的示例输出表明，Curve25519 上的公钥和私钥（秘密密钥）都编码为 256 位整数（64 个十六进制数字，32 字节），这简化了开发工作：

privKey: b'8175f7cd524a59b6efbd447985ce5d97c546b319521ff236203970e50052c641'
pubKey:  b'cf97a96568fee4ddb232f617fd5b9df2d2e5b90e68ba7f6d5129ea92d7d8f95e'

实际上，不同密码库可能使用不同的密钥编码。X25519 ECDH 密钥的编码通常与 Ed25519 密钥不同（Montgomery 曲线坐标与扭曲 Edwards 曲线坐标）。