libsecp256k1比特币密码算法开源库（八）

2022-01-09 17:50:35

2021SC@SDUSC
本篇博客介绍一些schnorr算法在libsecp256k1比特币密码算法中的使用。
schnorr算法的原理参考博客园《schnorr原理介绍》

schnorr介绍

Schnorr签名原理介绍

Schnorr签名则是一种完全不同的机制。它的运行类似于椭圆曲线数字签名，但却具有更多优点。相比于其他机制Schnorr签名要简单的多。所以，比其他选择要安全的多。乍一看可能意义并不大，但其却有一个强大的特性：直线性。

schnorr签名算法相比ECDSA具有哪些优势

证明安全性：在随机预言模型中很容易证明 Schnorr 签名的安全性，而 ECDSA 不存在这样的证明。
不可延展性：ECDSA 签名具有可塑性，不知晓私钥的第三方可以将给定公钥和消息的现有有效签名更改为对同一私钥和消息的另一个有效签名，而如果使用 Schnorr 签名则可以避免类似的情况出现。
线性：Schnorr 签名是线性的，这一点非常重要。使用 Schnorr 签名的各方可以生成对其各自密钥的签名聚合。以这一特性作为基础，可以构建更高效和隐私性更强的区块链系统。
schnorr 签名算法相比 ECDSA 来讲，对于上述的优点，除了尚未标准化之外几乎没有缺点。而且由于两种算法都基于同一个椭圆曲线，整个关于签名的升级成本也是很低的。

在密码学中，Schnorr 签名是由 Schnorr 签名算法产生的数字签名。它是一种数字签名方案，以其简单高效著称，其安全性基于某些离散对数问题的难处理性。
Schnorr 的原理描述如下：
下面用小写字母表示数字，比如：b = 38。同时我们将使用一些椭圆曲线上的点。这些点是一些满足椭圆曲线方程的大数对。我们将用大写字母来表示这些点，比如：A = （3， 54）。椭圆曲线上的点可进行一些代数运算。其上两个点可以相加可以得到近似随机的第三个点，表示为：C = A + B。某个点可以与自身相加多次：D = C + C + C。当我们讲一个点与自身相加多次时，我们称其为“乘以一个数”：D = 3 * C。显而易见的，如果将一个点 A 与自身相加很多次（或者说将其乘以一个很大的数）然后得到一个点 B ，如果我们只是知道原始点 A 和结果点 B ，计算出与 A 相乘的这个大数是相当困难的。这里的“困难”意思是，如果要计算出这个“大数”，我们不能简单的用 B 除以 A ，只能不断的猜测一个值 x ，计算是否 x * A等于 B 。所以如果这个 x 的值非常大，甚至大于宇宙中所有原子数目的和，猜测这个 x 的值将花费一个难以接受的时间。同时如果某人持有正确的 x ，计算 x * A 是非常迅速的。这种非对称性将作为我们讨论的前提。

小明持有私钥 x ，然后选择一个随机数 r ，以及椭圆曲线上的原点 G ，计算出R ：= r * G，公钥X ：= x * G，使用哈希函数获取一个随机的用于验证的数字e ：= Hash（R， X， message），然后计算 s ：= e * x + r。

小明给小白发送点 R， X， message ，和点数值 s ，小白验证 s * G 等于 R + e * X 。事实上，不仅是小白，这个世界上的任何人都可以独自对这一证明进行验证。一旦s * G = R + e * X通过了验证，既可以证明小明持有私钥 x，并生成了一个合法的签名：（s， e）。
最终，如果要将签名从这一证明中创造出来，小明需要定制一个哈希函数来对她签名的消息的进行哈希计算。这样的话需要确定针对一个消息所计算出的签名，不能被复用给另外一个消息。
这个定制过程可以简单的通过将 R ， X 和签名信息进行哈希来做到：
e ：= Hash（R， X， Message）
一个良好的哈希函数，会在哪怕仅有一个字符有更改的情况下，也会返回完全不同的哈希值，使得计算出 s 的值是不可能的任务

schnorr代码分析

1、定义确定地生成nonce的数据结构。
与secp256k1_nonce函数相同，但接受额外的pubkey参数而不需要尝试参数。pubkey参数可以保护带有密钥前缀的质询哈希输入的签名方案，防止在使用错误的预计算pubkey签名时重用nonce。如果成功生成nonce，则返回1，错误返回0。
输出:nonce32：指向要由函数填充的32字节数组的指针
输入:msg：正在验证的消息。当且仅当msglen为0时为NULL。
key32:指向32字节密钥的指针（不会为空）
xonly_pk32:与key32对应的32字节序列化xonly pubkey（将不为空）
algo：指向描述签名算法的数组的指针（不会为空）
algolen：algo数组的长度
数据：通过的任意数据指针
除了测试用例，这个函数应该计算消息、密钥、公钥、算法描述和数据的一些加密散列。

如果传递了数据指针，则假定它是指向BIP-340中定义的32字节辅助随机数据的指针。如果数据指针为空，则通过将辅助随机数据设置为零，nonce推导过程遵循BIP-340。algo参数必须为非NULL，否则函数将失败并返回0。哈希将用algo标记。因此，要创建符合BIP-340的签名，algo必须设置为“BIP0340/nonce”，algolen必须设置为13。
2、附加参数的数据结构。
通过将schnorrsig_extraparams结构对象设置为SECP256K1_schnorrsig_extraparams_INIT，可以正确初始化它。
成员：
magic：在初始化时设置为SECP256K1_SCHNORRSIG_EXTRAPARAMS_magic，除了确保对象已初始化之外，没有其他功能。
noncefp：指向nonce生成函数的指针。如果为空，则使用secp256k1_nonce_函数_bip340
ndata：指向nonce生成函数使用的任意数据的指针（可以为空）。如果为非空且使用secp256k1_nonce_函数_bip340，则根据BIP-340，ndata必须是指向32字节辅助随机性的指针。

3、创建一个Schnorr签名。
没有严格遵循BIP-340，因为它没有验证生成的签名。此函数仅对32字节的消息进行签名。如果您有不同大小的消息（或相同大小但没有上下文特定的标记前缀），可以使用secp256k1_taged_sha256创建32字节的消息哈希，然后对哈希进行签名。标记哈希允许为域分离提供上下文特定的标记。这会防止签名在多个上下文中意外地有效。
成功时返回1，失败时返回0。
Args:ctx：指向上下文对象的指针，已初始化用于签名。
Out:sig64：指向存储序列化签名的64字节数组的指针。
In:msg32:正在签名的32字节消息。
keypair：指向已初始化密钥对的指针。
aux_rand32:32字节的新随机性。虽然建议提供此选项，但它只是对安全性的补充，可以为NULL。

我们定义几个变量：

G：椭圆曲线。
m：待签名的数据，通常是一个32字节的哈希值。
x：私钥。P = xG，P为x对应的公钥。
H()：哈希函数。

具体实现代码：

循环使用nonces。
生成随机消息，直到尝试了所有挑战。
只有当我们遇到以前从未尝试过的挑战时，我们才能工作。
调用实函数来构造签名
前32个字节必须与指定k的xonly pubkey匹配。
最后32个字节必须与预期的s值匹配
不要重试导致相同质询的其他消息。
4、使用更灵活的API创建Schnorr签名。
参数与secp256k1_schnorrsig_签名相同，只是它允许对可变长度消息进行签名，并接受指向extraparams对象的指针，该对象允许通过传递其他参数自定义签名。如果msglen为32且extraparams.nda与aux_rand32相同，则创建与schnorrsig_签名相同的签名。
In:msg：正在签名的消息。仅当msglen为0时才可以为NULL。
msglen:消息的长度
extraparams：指向extraparams对象的指针（可以为空）

5、验证Schnorr签名。
返回：1：正确的签名
0:签名不正确
Args:ctx:secp256k1上下文对象，已初始化以进行验证。
In:sig64：指向要验证的64字节签名的指针。
消息：正在验证的消息。仅当msglen为0时才可以为NULL。
msglen:消息的长度
pubkey:指向要验证的x-only公钥的指针（不能为NULL）

验证者已知的是：G-椭圆曲线, H()-哈希函数，m-待签名消息, P-公钥，(R, s)-Schnorr签名。
验证如下等式：
sG = R + H(m || R || P)P
若等式成立，则可证明签名合法。
我们推演一下，此过程包含了一个极其重要的理论：椭圆曲线无法进行除法运算。
s值的定义：s = k + H(m || R || P)*x，等式两边都乘以椭圆曲线G，则有：
sG = kG + H(m || R || P)xG，
又因R = kG, P = xG，
则有：
sG = R + H(m || R || P)P，
椭圆曲线无法进行除法运算，所以第3步的等式，无法向前反推出第1步，就不会暴露k值以及x私钥。同时，也完成了等式验证。
代码如下，第一张图是定义的数据结构，后面是实现算法的过程。

算法实现：迭代可能的公钥以进行验证
通过签名中可能有效的前32个字节对应的DL k进行迭代。高于穷举测试顺序/2的值指的是无效\u pubkey \u字节中的条目。
随机生成消息，直到遇到所有挑战。
只有当我们遇到了以前从未尝试过的挑战时，我们才能工作。迭代签名中可能有效的最后32个字节。
0…order=该s值；
顺序+1=随机字节

只有一个s值必须验证，除非R是非法的。
不要重试导致相同质询的其他消息。
6、穷举测试schnorr
验证所有无效的_pubkey_字节实际上都是无效的。