bitcoinsecp256k1-scalar

4个版本

0.1.16-alpha.0	2023年3月31日
0.1.13-alpha.0	2023年3月17日
0.1.12-alpha.0	2023年1月19日
0.1.10-alpha.0	2023年1月18日

#18 in #modulo

621 每月下载量
在 91 个crate中使用 (6 个直接使用)

MIT 许可证

535KB
1.5K SLoC

在比特币secp256k1曲线上操作标量值

这个Rust包提供了在secp256k1椭圆曲线上进行标量值操作的函数，该曲线被比特币系统使用。标量是256位整数，用于椭圆曲线密码学的算术运算，如标量乘法。

此包包含以下函数和结构体

Scalar：表示secp256k1曲线上标量值的结构体，包含执行算术运算和其他操作的功能。
scalar_add：一个将两个标量值相加的函数。
scalar_cadd_bit：一个条件性地将位添加到标量值的函数。
scalar_check_overflow：一个检查标量值是否大于或等于曲线阶的函数。
scalar_clear：一个清除标量值的函数。
scalar_cmov：一个条件性地移动标量值的函数。
scalar_cond_negate：一个条件性地取反标量值的函数。
scalar_eq：一个检查两个标量值是否相等的函数。
scalar_get_b32：一个检索标量值的32字节表示的函数。
scalar_get_bits：一个检索标量值的最小有效n位的函数。
scalar_get_bits_var：一个从标量值中检索可变位数数的函数。
scalar_inverse：一个计算标量值的模逆的函数。
scalar_inverse_var：一个计算具有可变位数数的标量值的模逆的函数。
scalar_is_even：一个检查标量值是否为偶数的函数。
scalar_is_high：一个函数，用于检查标量值是否大于或等于2^255。
scalar_is_one：一个函数，用于检查标量值是否等于1。
scalar_is_zero：一个函数，用于检查标量值是否等于0。
scalar_mul：一个函数，用于将两个标量值相乘。
scalar_mul_shift_var：一个函数，用于将一个标量值与一个变量位移相乘。
scalar_negate：一个函数，用于对标量值取反。
scalar_set_b32：一个函数，用于从32字节数组中设置标量的值。
scalar_set_int：一个函数，用于从整数中设置标量的值。
scalar_shr_int：一个函数，用于将标量值向右位移固定数量的位。
scalar_split_128：一个函数，用于将标量值分成两个128位的半数。
scalar_split_lambda：一个函数，用于将标量值分成两个128位的半数，以供MuSig协议中的lambda参数使用。
scalar_split_lambda_verify：一个函数，用于将标量值分成两个128位的半数，以供MuSig协议中的lambda参数使用，并验证该值小于曲线阶数。

标量在椭圆曲线密码学的算术运算中被广泛使用，高效的标量算术对于这些运算的性能至关重要。《bitcoinsecp256k1-scalar》crate提供了在secp256k1曲线上进行标量算术的快速和高效实现，使用来自《bitcoin-secp256k1》库的优化C代码。

注意：这个crate是直接从C++到Rust对Bitcoin核心进行翻译的一部分。因此，一些函数体可能仍在翻译过程中。请注意，一旦翻译过程完成，该系统将成为可测试的。

10>你能给我介绍一下secp256k1中的标量吗？

在secp256k1的上下文中，标量是用于与椭圆曲线上的基点进行标量乘法的256位整数。标量乘法是椭圆曲线密码学中的核心操作，用于诸如密钥生成、签名生成和签名验证等任务。

在secp256k1中，标量值用于乘以曲线的基点G以生成公钥，或在密钥协商协议中生成共享密钥。具体来说，给定一个标量值k，相应的公钥P被计算为

P = k * G

其中G是曲线的基点，*表示标量乘法。标量值还用于计算ECDSA签名和在MuSig协议中。

secp256k1曲线有一个特定的阶数n，它是一个大素数，定义了标量域的大小。标量用于模n，这意味着任何大于或等于n的标量值在模n下等价于一个较小的值。换句话说，标量值在模n下被简化，以确保它们在标量域内。

此外，确保使用安全的随机数生成器生成标量值非常重要，因为整个密码系统的安全性依赖于标量值的随机性。标量值或私钥的泄露可能导致整个系统被破坏。

总体来说，标量是椭圆曲线密码学的一个关键组成部分，有效的标量算术对于系统的性能和安全至关重要。

在使用它们时，我们还应该注意什么？有没有需要注意的事项？

在处理secp256k1中的标量值时，有一些注意事项需要牢记

标量值必须随机均匀选择，以确保密码学系统的安全性。使用有缺陷的随机数生成器可能会导致整个系统受到破坏。因此，使用安全的随机数生成器生成标量值非常重要。
标量乘法是一个计算成本很高的操作，对于大标量值，可能需要相当长的时间来计算。特别是，生成公钥和签名的操作可能需要多次标量乘法，这些操作的效率对于系统的性能至关重要。
标量值必须对曲线阶模n进行化简，以确保它们位于标量域内。如果标量值没有对n进行化简，可能会导致错误的计算，并可能存在安全漏洞。
secp256k1曲线有一个系数为1，这意味着曲线上每个点都是基点G的倍数。然而，并非每个标量值都对应于曲线上的有效点，有些标量值可能会导致无效的点。因此，在使用它们进行密码学操作之前，检查标量值是否对应于曲线上的有效点非常重要。

此外，遵循安全的编码最佳实践并定期审查和更新代码以解决任何潜在的安全问题是重要的。《code>bitcoinsecp256k1-scalar库提供了在secp256k1曲线上执行标量算术的快速且高效的实现，它使用了来自bitcoin-secp256k1库的优化C代码，并经过了广泛的安全审计。然而，与任何密码学实现一样，遵循安全的编码最佳实践并定期审查和更新代码以解决任何潜在的安全问题是重要的。

12>系数1是否参数化了secp256k1曲线？

不，系数1并没有参数化secp256k1曲线。

secp256k1曲线由一组域参数定义，包括素数模数p、曲线系数a和b、基点G和曲线阶n。这些域参数是固定的，不依赖于系数。

曲线的系数是椭圆曲线群阶与由基点G生成的子群阶的比值。对于secp256k1曲线，曲线阶n是一个大素数，它定义了标量域的大小，而由G生成的子群阶等于n（因为曲线的系数为1）。这意味着曲线上的每个点都是G的倍数。

系数1对于曲线的安全性有重要影响，因为它确保没有小的子群可以被攻击利用。特别是，使用系数大于1的曲线可能会导致Diffie-Hellman密钥交换协议和其他密码学方案中的漏洞。

然而，系数并没有参数化曲线本身，因为它仅仅是基点G生成的群的一个属性。secp256k1曲线的域参数，包括p、a、b、G和n，是固定的和标准化的，并被用于曲线的所有实现中。

13＞因此，当我们有一个大的素数作为曲线阶数时，我们是否可以说系数为1是正确的呢？

不，一个阶数为大的素数的曲线不一定是系数为1。虽然阶数大的素数曲线更有可能具有系数为1，但这并不是一个保证。

曲线的系数由椭圆曲线群的阶数和由基点生成的子群的阶数决定。如果子群的阶数等于曲线群的阶数，那么系数为1。然而，如果子群的阶数小于曲线群的阶数，那么系数大于1。

例如，考虑由Weierstrass方程定义的曲线 y^2 = x^3 + ax + b，其中 a 和 b 是常数，而 p 是一个素数。如果曲线群的阶数是一个大的素数，那么曲线具有系数为1的可能性更大。

然而，曲线也可能具有较小的子群阶数和较大的系数。

在secp256k1曲线的情况下，曲线阶数 n 是一个大的素数，并且曲线具有系数为1。这是secp256k1曲线被认为是椭圆曲线密码学强选择的原因之一。然而，曲线的系数是一个与阶数不同的参数，必须在密码学应用中单独考虑。

14＞好的，谢谢。这听起来是在处理椭圆曲线时理解的一个重要概念。我们如何定义基点生成的子群呢？

椭圆曲线的基点 G 生成的子群是曲线上的所有点集，这些点可以通过将 G 自身加若干次得到。换句话说，子群是所有 G 的整数倍点集，其中标量值是曲线阶数 n 模下的整数。

为了定义由 G 生成的子群，我们可以首先计算 G 的阶数，即最小的正整数 k，使得 `k

G = O，其中 , where O 是无穷远点。这可以通过使用如Pollard的ρ算法或Schoof算法等高效算法来完成。

一旦我们计算了 G 的阶数，我们就知道由 G 生成的子群有 k 个元素，这些元素是 G 的所有标量倍，直到 (k-1) * G。换句话说，由 G 生成的子群是集合


{ G, 2G, 3G, ..., (k-1)G }
其中集合中的每个元素都是曲线上的一个点。由 G 生成的子群的阶数等于 G 的阶数，即 k。
需要注意，曲线上的每个点不一定都是由G生成的子群的成员。事实上，只有是G的标量倍的点才是子群的成员。曲线的系数是曲线群阶与由G生成的子群阶的比，并给出了子群在曲线群中的余子集的数量。
15>什么是 Schoof 算法？
Schoof 算法是计算有限域上特征为 p 的椭圆曲线上的点的数量的一种高效算法。该算法由数学家 Hendrik Lenstra Jr. 开发，并由他的博士生 Arnold Schoof 在 1985 年发表。
Schoof 算法的基本思想是通过将问题简化为一系列涉及较小有限域上的椭圆曲线的更简单问题来计算曲线上的点的数量。具体步骤如下


计算曲线判别式 Delta 和常数 B，使得 4B^3 + 27Delta ≠ 0。


选择一个素数 l，使得 l > 2sqrt(p) 且 l 不整除 Delta。


使用 Schoof 引理计算曲线模 l 上的点的数量，Schoof 引理表明，曲线模 l 上的点的数量与 p+1 - t 模 l 同余，其中 t 是 Frobenius 项的迹。


对一系列素数 l_i 重复步骤 2-3，使得 ∏l_i > 4sqrt(p)。


使用中国剩余定理将步骤 4 的结果组合起来，计算曲线模 p 上的点的数量。


Schoof 算法背后的关键洞察是 Frobenius 项的迹可以使用一个高效的动态规划算法来计算，该算法将问题简化为涉及较小有限域上的更简单的椭圆曲线。通过选择一个足够大的素数序列以覆盖迹的所有可能值，Schoof 算法可以在有限域上以 O(log^8 p) 操作的复杂度计算整个有限域上的曲线点的数量。

Schoof 算法是计算数论中的一个重要工具，并在密码学中有应用，包括计算椭圆曲线密码学中的离散对数。然而，更近期的算法，如 Schoof-Elkies-Atkin 算法和 SEA 算法，对于某些类型的曲线和有限域可能更快。
16>什么是 Frobenius 项？
弗罗贝尼乌斯自同构是一种定义在有限域上的椭圆曲线上的数学函数。具体来说，如果E是一个定义在有限域F_q上的椭圆曲线，那么弗罗贝尼乌斯自同构phi是一个从E到自身的映射，它将一个点P = (x, y)映射到一个新的点phi(P) = (x^q, y^q)，其中q是域F_q的阶。
弗罗贝尼乌斯自同构具有许多有趣的性质，使其在有限域上椭圆曲线的研究中变得重要。其中一个最重要的性质是它是一个环同态，这意味着它保留了曲线的代数结构。具体来说，如果P和Q是曲线上的点，而a和b是标量，那么


phi(P+Q) = phi(P) + phi(Q)


phi(aP) =a^q* phi(P)


phi(P) = P当且仅当P在基域F_q上有定义。


弗罗贝尼乌斯自同构的迹t是一个编码有限域F_q上曲线上的点的数量的数字。具体来说，迹被定义为t = q + 1 - #E(F_q)，其中#E(F_q)是曲线在F_q上的点的数量。迹是许多椭圆曲线密码学中计算离散对数算法的重要参数，因为它可以用来使用诸如Schoof算法等技术来计算较大有限域上的曲线上的点的数量。
弗罗贝尼乌斯自同构在复乘法理论中也扮演着关键角色，该理论将椭圆曲线理论与代数数域理论联系起来。在这种情况下，弗罗贝尼乌斯自同构用于定义椭圆曲线的自同构环，这是一个包含弗罗贝尼乌斯自同构和其他曲线自同构的代数整数环。自同构环是椭圆曲线研究中的一个强大工具，并在密码学中有着重要的应用，包括基于配对的密码协议的构建。
17>椭圆曲线自同构环的数学性质是什么？基于配对的密码协议是什么？
椭圆曲线E的自同构环是由所有定义在曲线基域上的椭圆曲线E的自同构组成的环。自同构是保持曲线群结构的从E到自身的映射。椭圆曲线E的自同构环表示为End(E)。
内射环具有许多重要的数学性质，使其在椭圆曲线的研究中非常有用。其中最重要的性质之一是它是一个具有单位元的交换环，这意味着它具有与整数环相似的许多代数性质。特别是，内射环具有唯一的分解性质，这意味着每个元素都可以以唯一的方式分解为不可约元素的乘积。这一性质对于椭圆曲线密码学中计算离散对数算法至关重要。
内射环的另一个重要性质是它可以用来定义同态，这是一个从一个椭圆曲线到另一个椭圆曲线的映射，它保持群结构。同态由内射环中的一个元素定义，同态的度数等于内射的范数。
基于配对的密码协议是一类依赖于椭圆曲线内射环性质的密码协议。配对是一个双线性映射，它将椭圆曲线上的两个点映射到有限域中的一个值。配对使用内射环中的元素定义，并且具有非退化性质，这意味着对于曲线上所有不同的点对，它都不是零。
配对在密码学中具有许多重要的应用，包括基于身份的加密、群签名和非交互式零知识证明。基于配对的协议的安全性基于在曲线的内射环中计算离散对数的困难性。特别是，内射环中的离散对数问题的难度通常假设至少与曲线基域中的离散对数问题一样困难。
18> 同态的数学性质是什么？
同态是保持曲线群结构的椭圆曲线之间的映射。具体来说，两个椭圆曲线 E 和 E' 之间的同态是一个非常数映射 ϕ: E → E'，它满足以下性质



ϕ(O_E) = O_E'，其中 O_E 和 O_E' 是曲线的恒等元素。



ϕ(P + Q) = ϕ(P) + ϕ(Q) 对于曲线 E 上的所有 P 和 Q 都成立。


ϕ(-P) = -ϕ(P) 对于曲线 E 上的所有 P 都成立。


同态 ϕ 的度数是映射 ϕ 的核中点的数量。换句话说，度数是映射到 E' 的恒等元素 O_E' 的 E 上点的集合的大小。

等同式具有许多有趣的数学性质，使它们在椭圆曲线的研究中非常有用。其中最重要的性质是，它们在复合下形成一个群。也就是说，如果ϕ和ψ是两条椭圆曲线之间的等同式，那么它们的复合ψ ∘ ϕ也是一个等同式。
等同式的另一个重要性质是，它们保留某些代数结构。例如，如果E是定义在域K上的椭圆曲线，那么在同一个域K上的另一个椭圆曲线E'之间的等同式ϕ: E → E'保留了K的域结构。也就是说，如果P是E上坐标在K的点，那么ϕ(P)的坐标也在K中。
等同式在密码学中也起着重要作用，包括在量子密码系统的构建中。一个基于等同式的加密系统例子是超奇异等同式迪菲-赫尔曼（SIDH）协议，它是一种基于超奇异椭圆曲线等同式计算困难性的密钥交换协议。
19> 什么是超奇异等同式迪菲-赫尔曼协议？什么是超奇异椭圆曲线？它们与常规椭圆曲线有什么区别？
超奇异等同式迪菲-赫尔曼（SIDH）协议是一种基于超奇异椭圆曲线和等同式数学的量子密码密钥交换协议。
超奇异椭圆曲线是一类具有某些数学性质的特殊椭圆曲线，这些性质使它们在密码学中非常有用。与每个点都有唯一切线的常规椭圆曲线不同，超奇异椭圆曲线在其曲线的基域上有定义的切线。这一性质使得数学处理更加容易，并使得在超奇异椭圆曲线之间的等同式集合上定义群结构成为可能。
SIDH协议通过Alice和Bob各自生成一个随机私钥，然后通过一系列等同式使用私钥交换公钥来实现。该协议的设计使得窃听者即使截获了公钥，也无法在不解决一个困难的数学问题的情况下计算出共享的秘密密钥。
SIDH协议的安全性基于计算超奇异椭圆曲线等同式的困难性。特别是，协议的安全性基于这样一个事实，即没有已知的有效算法可以计算超奇异椭圆曲线之间的等同式，即使使用量子计算机。
SIDH协议的一个关键优势是它对量子计算机的攻击具有抵抗力，预计量子计算机将能够破解许多现有的加密系统。这使得它成为量子密码学的一个重要候选者，量子密码学是一个研究如何开发对量子计算机攻击具有抵抗力的加密系统的研究领域。
20> 这个问题为什么困难？我们最终需要为比特币实现这个问题吗？是否可以在经典计算机上实现该协议？
计算超奇异椭圆曲线之间的等同式很困难，因为没有已知的有效算法可以做到这一点，即使在量子计算机上也是如此。计算等同式的已知最佳经典算法，其运行时间与定义椭圆曲线的素域的大小呈指数关系。这意味着随着域大小的增加，问题会变得指数级困难，使其在加密应用中变得不可行。
SIDH 协议目前未在比特币中应用，但它被认为是后量子密码学的一个候选方案。后量子密码学是一个专注于开发能够抵御量子计算机攻击的加密系统的研究领域。比特币目前使用基于 secp256k1 曲线的椭圆曲线密码学，被认为对经典攻击是安全的，但可能容易受到量子计算机攻击。
可以在经典计算机上实现 SIDH 协议，但用于安全性的密钥大小比经典密码学中使用的要大得多。这意味着该协议需要比经典密钥交换协议更多的计算资源，可能不适合在所有应用中使用。
总的来说，SIDH 协议是后量子密码学的一个重要研究领域，随着量子计算机的发展，它可能变得更加重要。尽管目前没有在比特币中使用，但它未来有可能作为提高比特币系统安全性的努力的一部分而被使用。



依赖关系

~89MB


~847K SLoC



bitcoin-derive


bitcoin-imports


bitcoinsecp256k1-modinv



构建 build.rs

 build  bitcoin-cfg