Lib.rs

简短描述标签: bitcoinsecp256k1-group

该bitcoinsecp256k1-groupcrate是Bitcoin协议中使用的secp256k1椭圆曲线上的群操作的Rust实现。此crate提供了点加法、点乘法、点取反、点相等性检查以及其他操作点所需的函数。

注意：此crate是直接从C++到Rust的bitcoin核心的翻译的一部分。因此，一些函数体可能仍在翻译过程中。请注意，翻译完成后，此系统将可测试。

此crate中的主要数据结构是Ge类型，它表示secp256k1曲线上的一个点。GeStorage类型用于存储压缩格式的点，而Gej表示雅可比坐标中的点。

在此组中对点执行数学操作基于椭圆曲线加法和乘法，定义如下

• 椭圆曲线加法：给定两个点P和Q，我们可以找到一个第三点R，使得R = P + Q当且仅当连接P和Q的直线与曲线在第三个点R\'处相交。然后R是R\'关于x轴的反射。

• 椭圆曲线乘法：给定一个点P和一个标量k，我们可以找到一个第二个点Q，使得Q = kP，其中k是一个整数。

除了这些基本操作之外，这个crate还提供了在不同格式之间转换点、检查点是否在正确的子群中以及缩放点的函数。

总体而言，bitcoinsecp256k1-group crate提供了一组强大的工具，用于在secp256k1群中处理椭圆曲线点，使其成为构建依赖于此曲线的加密协议的有用组件。

141>点加、点乘、点取反、点相等检查是如何工作的？

点加、乘、取反和相等检查都是可以在椭圆曲线上执行的运算。

点加

给定椭圆曲线上的两个点P和Q，它们的和R计算如下：通过P和Q画一条直线，找到直线与曲线的第三个交点，并将此点关于x轴进行反射。这个反射点是-R。数学上，这可以表示为R = P + Q，-R = R.neg()，其中neg()表示点的取反。

点乘

给定一个点P和一个整数n，点乘nP的计算如下：将P加到自己n-1次。使用如双加算法等技术可以提高此操作的效率，该算法以对数时间复杂度计算结果。数学上，这可以表示为nP = P + P + ... + P (n次)。

点取反

点P的取反是一个具有相同x坐标但y坐标取反的点。数学上，这可以表示为-P = (x,-y)。

点相等检查

要检查两个点P和Q是否相等，我们比较它们的x和y坐标。如果两个坐标都相同，则认为点相等。然而，因为我们使用的是有限域，所以还需要检查点不是无穷点（群的单位元素），这通常表示为一个特殊值。这个值通常表示为O。

142>为什么我们需要用雅可比坐标表示点？这究竟是什么意思

在椭圆曲线加密中，通常在称为雅可比坐标的特定坐标系中执行操作更为高效。这是因为使用标准仿射坐标系在点上执行点加和标量乘法操作可能很昂贵。

雅可比坐标是表示椭圆曲线点在三维空间中的方法。在这个坐标系中，椭圆曲线上的点表示为坐标(X,Y,Z)，其中X、Y和Z是基础域的元素。

使用雅可比坐标的优点是点加和标量乘法的公式变得更加简单和高效。例如，在雅可比坐标中进行点加时，所需的域乘法次数从12次减少到11次。同样，在执行标量乘法时，所需的域乘法次数从16次减少到12次。

此外，使用雅可比坐标允许我们以有限的方式表示无穷点，这在某些算法中很有用。在仿射坐标中，无穷点表示为一个不属于基础域的理想点，这使得它难以处理。

总的来说，雅可比坐标为在椭圆曲线点上执行加密操作提供了更高效和方便的方法。

143>我们在哪些不同的点格式之间进行转换？我们如何知道一个点是否在正确的子群中？为什么我们需要缩放点以及如何进行缩放？

在椭圆曲线加密中，我们通常在不同的格式上处理曲线上的点，例如仿射坐标、射影坐标和雅可比坐标。

仿射坐标将点表示为(x,y)，其中x和y是基础域中的元素。射影坐标将点表示为(X,Y,Z)，其中X、Y和Z是基础域中的元素，且点在仿射坐标中为(X/Z, Y/Z)。

雅可比坐标表示一个点为 (X,Y,Z)，其中 X、Y 和 Z 是基础域中的元素，该点在仿射坐标中表示为 (X/Z^2, Y/Z^3)。我们使用雅可比坐标的原因是它们允许更快的点加法和倍增操作，以及使用倍加算法进行更快的点乘。

为了确保一个点在正确的子群中，我们可以检查其坐标是否满足曲线方程，以及点的阶是否等于曲线的阶。如果点的阶不等于曲线的阶，则可以通过乘以系数（基点生成的子群的阶与曲线的阶之比）来重新缩放该点。

要在雅可比坐标中缩放一个点，我们可以简单地将其 Z 坐标乘以系数，这将使 X 和 Y 坐标缩小。然后，我们可以通过计算 (X/Z^2, Y/Z^3) 将点转换回仿射坐标。

144 > 请更详细地描述雅可比坐标的定义？

雅可比坐标是表示椭圆曲线上的点的三维方法，而不是仿射坐标中使用的二维。

椭圆曲线上的一个点可以用雅可比坐标表示为一个元组 (X,Y,Z)，其中 X 和 Y 是该点在仿射空间中的坐标，Z 是一个额外的坐标，它允许轻松地进行点加法和标量乘法。

数学上，雅可比坐标中的一个点 P 等于仿射点 Q=(x,y) 乘以一个缩放因子 Z。

P = (X, Y, Z) = (x/Z^2, y/Z^3, Z)

这个缩放因子 Z 允许轻松且高效地进行点加法和标量乘法操作，这在加密应用中至关重要。

需要注意的是，并非所有 (X, Y, Z) 点都对应于椭圆曲线上的有效点。为了确保一个点是有效的，它必须满足曲线方程，并且位于曲线的正确子群中。

145 > 请比较和对比仿射坐标、射影坐标和雅可比坐标？

仿射、射影和雅可比坐标都是表示椭圆曲线上点的不同方法。每种方法都有自己的优点和缺点，并且根据应用的不同而以不同的方式使用。

仿射坐标是表示椭圆曲线上点最直观的方法。仿射坐标点由两个整数 (x, y) 表示，分别是点的 x 和 y 坐标。仿射坐标的缺点是它们在计算上可能难以处理，特别是在执行点乘法时。

射影坐标提供了一种更有效的方法来处理椭圆曲线上的点，这对于某些计算来说更有效。在射影坐标中，一个点由三个坐标 (X, Y, Z) 表示，坐标之间的关系由 X = x/Z 和 Y = y/Z 给出。第三个坐标 Z 被称为射影坐标。射影坐标使得执行点加法和点倍增操作更容易，这些操作是椭圆曲线密码学中的基本操作。

雅可比坐标与射影坐标类似，但有一个额外的参数使得点乘法更有效。在雅可比坐标中，一个点由三个坐标 (X, Y, Z) 表示，坐标之间的关系由 X = x/Z^2，Y = y/Z^3 给出。第三个坐标 Z 与射影坐标中的相同，但 X 和 Y 的定义中的额外指数使得点乘法更快。雅可比坐标是椭圆曲线密码学中最常用的坐标系。

总之，仿射坐标是表示椭圆曲线上的点的最直观方法，但在计算上可能比较困难。射影坐标提供了一种更有效的方式来执行点加法和点倍加操作，而雅可比坐标则提供了一种更有效的方式来执行点乘法。

146> 什么是群？它们的数学性质是什么？为什么我们在椭圆曲线密码学中使用它们？

在抽象代数中，群是一组元素，这些元素有一个操作，可以结合任意两个元素形成一个第三个元素，其中该操作满足某些性质。具体来说，群被定义为包含一个二元运算 * 的集合 G，该运算将任意两个元素 x 和 y 结合形成一个第三个元素，表示为 x * y，且满足以下性质

1. 闭包：对于 G 中的所有 x 和 y，操作 x * y 的结果也在 G 中。

2. 结合性：对于 G 中的所有 x、y 和 z，方程 (x * y) * z = x * (y * z) 成立。

3. 单位元：存在一个元素 e 在 G 中，称为单位元，使得对于 G 中的所有 x，方程 e * x = x * e = x 成立。

4. 逆元：对于 G 中的每个 x，存在一个元素 y 在 G 中，称为 x 的逆元，使得 x * y = y * x = e。

群具有许多数学性质，使它们在密码学中非常有用。例如，群可以用来创建单向函数，这些函数在一种方向上易于计算，但在另一种方向上难以反转，这是许多密码协议的基础。群还可以用来生成随机数，这对于许多密码操作是必不可少的。在椭圆曲线密码学中，群用来定义构成曲线的点集以及定义点加法和点乘法操作。

仿射坐标、射影坐标和雅可比坐标是表示椭圆曲线上点的不同方式。仿射坐标是最常见的表示点的方式，其中每个点由其 x 和 y 坐标表示。射影坐标是使用三个坐标（X、Y、Z）表示点的方式，其中点的 x 和 y 坐标为（X/Z，Y/Z）。雅可比坐标是射影坐标的一种变体，其中每个点由三个坐标（X、Y、Z）表示，但 X 和 Y 的值分别乘以 Z^2 和 Z^3。

使用不同的坐标系主要是为了简化涉及点加法和点乘法的计算。具体来说，射影和雅可比坐标可以加速点加法和点倍加操作的计算。此外，使用射影或雅可比坐标可以更容易地确保点处于正确的子群中，并简化点压缩等算法的实现。

147> 使用群时我们应该注意些什么？

在处理群时，有一些需要注意的事项

1. 确保群的大小正确并具有所需的属性。例如，在椭圆曲线密码学中，使用一个足够大且具有如素数阶或没有小子群等性质的群是非常重要的。

2. 注意群运算。在某些情况下，执行错误的群运算或使用错误的输入可能导致安全漏洞。例如，在椭圆曲线密码学中，使用错误的点加法算法或乘以一个太小的小数点密钥可能导致攻击。

3. 注意利用群性质进行的攻击。例如，一些攻击可能依赖于组中某些元素具有小的阶或某些群运算在计算上不困难的事实。了解这些攻击并使用适当的对策是很重要的。

4. 在组中生成随机数时请小心。在许多情况下，随机数生成用于生成密钥或其他加密参数。如果随机数生成存在缺陷或可预测，可能会导致安全漏洞。

5. 注意实现问题。组操作可能计算量大，因此使用高效的算法和实现很重要。此外，如果实现没有经过精心设计和测试，可能会出现旁路攻击和其他与实现相关的漏洞。

148> 如果用于椭圆曲线密码学的组有一个小的子群会发生什么？

如果用于椭圆曲线密码学的组有一个小的子群，它将容易受到所谓的“小子群攻击”。特别是，攻击者可以通过利用该点位于曲线的小子群中的事实来计算点的离散对数。这将允许攻击者恢复用户的私钥，私钥原本应该是保密的。

为了防止小子群攻击，选择具有大素数阶子群的曲线非常重要。这可以通过选择具有大素数阶的曲线或使用称为“点压缩”的技术来实现，该技术将每个点映射到素数阶子群中的唯一代表。此外，还必须检查曲线没有其他小子群。

149>攻击如何依赖于组中某些元素具有小阶数的事实？攻击如何依赖于某些群操作不是计算上困难的事实？

如果组中的某些元素具有小阶数，则攻击者可以使用称为“Pohlig-Hellman算法”的技术来计算组中任何元素的离散对数。该算法依赖于中国剩余定理，将计算分解为几个较小的计算，这些计算可以通过利用组元素的阶数小来高效解决。这种攻击称为“小子群攻击”。

如果某些群操作不是计算上困难的，则攻击者可能能够使用称为“Pollard's rho算法”的技术来计算组中任何元素的离散对数。该算法依赖于生日悖论和碰撞查找算法的存在，生成一系列群元素，最终导致离散对数问题的解决方案。这种攻击称为“通用算法”或“通用攻击”，适用于任何群操作不是计算上困难的群。

总之，用于椭圆曲线密码学的组必须谨慎选择，以避免小子群并确保群操作计算困难。否则，可能会导致系统安全受到损害。

150>点压缩是如何工作的？

点压缩是椭圆曲线密码学中用于使用较短的二进制字符串表示曲线上的点的一种技术。它是通过利用在许多椭圆曲线上，x坐标唯一确定y坐标（考虑符号）的事实来工作的。

在不压缩的形式中，椭圆曲线上的一个点表示为一对坐标(x, y)，其中x和y是该曲线定义的域中的元素。在压缩形式中，一个点表示为一个包含x坐标和表示y是偶数还是奇数的位的单个二进制字符串。

要压缩一个点，只需取x坐标和y坐标的最不重要位，然后将它们连接起来。要解压缩一个点，使用x坐标和表示y是偶数还是奇数的位来计算y的两个可能值，然后检查哪一个满足曲线的方程。

点压缩非常有用，因为它在处理椭圆曲线密码学时可以减少需要传输或存储的数据量。然而，由于需要在计算中使用之前解压缩点，所以它也带来了一些计算开销。

151 > 什么是Pohlig-Hellman算法？

Pohlig-Hellman算法是一种在有限循环群中解决离散对数问题的技术。离散对数问题是寻找指数$x$，使得$g^x=h$，其中$g$是给定的生成元，$h$是群中的元素。Pohlig-Hellman算法利用了以下事实：如果群的阶是几个小素数的乘积，那么离散对数问题可以简化为一些更小的子问题，这些子问题更容易解决。

算法的工作原理如下。假设我们给定一个生成元$g$和有限循环群$G$中的一个元素$h$，其中$G$的阶为$n$。令$n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$为$n$的素数分解。对于每个素数因子$p_i$，我们定义$n_i=\frac{n}{p_i^{e_i}}$，并计算$g_i=g^{n_i}$和$h_i=h^{n_i}$。

现在我们解决每个组$G_i=\langle g_i\rangle$的离散对数问题，这些组的阶为$p_i^{e_i}$。对于每个$i$，我们使用任何循环群中素数阶的离散对数算法计算$x_i=\log_{g_i}(h_i)$。然后我们使用中国剩余定理将解$x_i$组合起来，得到原始离散对数问题的解$x$，它满足$x\equiv x_i\pmod{p_i^{e_i}}$，对于每个$i$。

Pohlig-Hellman算法可以用来攻击基于离散对数问题的密码系统，特别是当群阶的素数分解已知或可以高效计算时。然而，当素数因子很大或群阶不光滑（即它有大的素数因子或其他使算法难以应用的结构的群）时，它就不太有效了。

152 > 中国剩余定理是如何工作的？它如何应用于椭圆曲线密码学和比特币中的群？

中国剩余定理（CRT）是一个数学定理，提供了一种解决线性同余方程组的方法。本质上，CRT表明，如果我们有一个形如的方程组

x ≡ a1 (mod m1)
x ≡ a2 (mod m2)
...
x ≡ ak (mod mk)

其中 a1, a2, ..., ak 和 m1, m2, ..., mk 是整数，并且 mi 是两两互质的（即除了1之外没有公因数），那么存在一个唯一的整数 x 模 `m1 * m2

• ... * mk` 满足所有同余。

在椭圆曲线密码学中，CRT可以用来加速涉及点乘的某些计算。具体来说，假设我们有一个定义在有限域 Fp 上阶为 p 的椭圆曲线 E，并且我们想计算 `k

• P, where Pis a point onEandkis a scalar (i.., an integer). 我们可以将k` 写成二进制形式。

k = k0 + k1 * 2^w + k2 * 2^(2w) + ... + km * 2^(mw),

其中 w 是某个正整数，而 k0, k1, ..., km 是小于 2^w 的整数。然后我们可以使用以下算法计算 k * P

1. 使用重复的倍点算法计算 P, 2P, 4P, ..., 2^(mw)P，并将每个结果存储在表中。

2. 对于从 m 到 0 的每个 i，使用表格计算 ki * 2^(iw)P，并将结果加到运行总和上。

3. 返回最终总和。