在双钥系统中,签名可以作为身份认证和授权的手段。
- 对签名方,能提供正确的签名,就意味着他一定有私钥
- 对验证方,验签通过即可保证,消息内容未经篡改,且消息来源可靠
在比特币中也一样,我可以向你提供下列信息,来证明该地址属于我。
项 | 内容 |
---|---|
地址 | 1AfxgwYJrBgriZDLryfyKuSdBsi59jeBX9 |
消息 | 你好世界 |
签名 | H9DnqMSGQmqi0zIWQqVfPXQsq59Qt11F1rUQDxv+4/iUDrSLJ6xHZ7PUSKvVThVWQAy/lLEpE3JeMpOlwUiVGlo= |
使用钱包工具或第三方服务,任何人都能验证。
验签通过即可证明,该地址对应的私钥确实在我手上。请注意,要签名的消息,可以是你我事先商议好的任何内容,这里使用“你好世界”只是演示。
本文将详述如何使用比特币私钥对任意消息签名。
发现“问题”
你注意到没有,文章开头的证明信息里只包含地址、消息和签名,而没有公钥。
但验签操作需要公钥。
能从地址反推吗?不能。地址是公钥哈希的可逆编码,从公钥哈希无法反推公钥,因为哈希是单向运算。所以无法从地址计算公钥。
那么问题来了,没有公钥如何验签?只有一种可能,从 ECDSA 签名可以恢复公钥。
再说 ECDSA 签名
在介绍 ECDSA 时我们强调,签名过程中使用的临时私钥 $k$,保证其绝对私密且生成时足够随机非常重要。
签名和消息是公开的,即已知 $(r, s)$ 和 $e$,如果还知道 $k$,就可以算出私钥。
$$
a = r^{-1}(sk - e) \bmod{n}
$$
进一步的,如果知道的是 $K$,则可以算出公钥。
$$
A = aG = r^{-1}(sk - e) \cdot G = r^{-1}(s \cdot kG - eG) = r^{-1}(sK - eG)
$$
所以从签名恢复公钥的关键,是确定点 $K$ 的坐标 $(x_K, y_K)$。
注意到,对 Secp256k1 的参数 $n$ 和 $p$,有 $n < p$,而 $r = x_K \bmod{n}$。
所以从 $r$ 求 $x_K$,结果不一定唯一。当 $r + n < p$ 时,$x_K = r$ 和 $x_K = r + n$ 都是解。
另外,知道了 $x_K$ 也不能唯一确定 $y_K$。椭圆曲线是上下对称的,若点 $(x, y)$ 在曲线上,则点 $(x, -y \bmod{p})$ 也在曲线上。之前的文章在介绍比特币公钥时提到过,对 Secp256k1,至少要知道点的 X 坐标和 Y 坐标的奇偶,才能唯一确定该点。
让我们总结一下。如果想通过 ECDSA 签名 $(r, s)$ 和消息 $e$ 恢复公钥,还需要知道两个额外的信息:
- $x_K$ 与 $n$ 的大小关系。若 $x_K < n$ 则 $x_K = r$,反之 $x_K = r + n$
- $y_K$ 的奇偶性
Recoverable ECDSA 签名
这个“额外信息”只有四种状态,用 2 个二进制位即可表示。高位是 0 标记 $x_K < n$,低位是 0 标记 $y_K$ 的偶数。
二进制位 | 内容 | 十进制值 |
---|---|---|
00 | $x_K < n$,$y_K$ 是偶数 | 0 |
01 | $x_K < n$,$y_K$ 是奇数 | 1 |
10 | $x_K > n$,$y_K$ 是偶数 | 2 |
11 | $x_K > n$,$y_K$ 是奇数 | 3 |
我们把这个标记,称为recovery_id
或recid
,把包含了此标记的 ECDSA 签名 $(recid, r, s)$,称为“可恢复”签名(recoverable ECDSA signature)或致密签名(compact signature)。
对应代码不难实现,只需在计算 $(r, s)$ 时同时计算recid
即可。
def sign_recoverable(private_key: int, message: bytes) -> tuple: |
计算消息摘要
用私钥对交易签名,实际上是用私钥对交易摘要签名。类似的,对消息签名时,需要先计算消息的摘要,然后对消息摘要签名。
消息摘要有特定的格式。
项 | 内容 |
---|---|
len(H) | H 的字节长度,VarInt 类型表示,定值 0x18 |
H | 字符串 Bitcoin Signed Message:\n 的 UTF-8 编码 |
len(M) | M 的字节长度,VarInt 类型表示 |
M | 消息 $m$ 的 UTF-8 编码 |
def message_bytes(message: str) -> bytes: |
调用message_digest
方法,就可以得到原始消息的消息摘要。
请注意,我们在计算“消息摘要”时并没有使用哈希方法,所以严格来说这个计算的结果不能叫消息的“摘要”,对整个转换过程更准确的描述应该是“消息的格式化”或“消息的序列化”。之所以也使用“摘要”这个词,是为了将它跟之前在介绍对交易签名时提到的“交易摘要”对应起来,方便你整体理解。
序列化签名结果
至此,所有的准备工作均已就绪,在展示最终结果前,还需要序列化。
签名 $(recid, r, s)$ 总会被序列化成 65 字节。
字节长度 | 内容 |
---|---|
1 | 前缀信息 |
32 | 整数 r 按大端模式序列化后的字节流 |
32 | 整数 s 按大端模式序列化后的字节流 |
别忘了,比特币公钥有两种表示法,一种以 0x04 开头有 65 字节,另一种以 0x02 或 0x03 开头有 33 字节,即同一个公钥会对应两个 P2PKH 地址。为了能在验签时同时校验恢复出的公钥的哈希,是否与输入的地址相匹配,还需要在前缀信息里标记公钥的表示方式。
前缀的值 | 内容 |
---|---|
27 + recid + 4 |
公钥用 33 字节表示 |
27 + recid + 0 |
公钥用 65 字节表示 |
最后,用 Base64 编码处理序列化后的签名数据,以方便人们复制和转录。
from base64 import b64encode |
我们写一个简单的例子来测试。
if __name__ == '__main__': |
输出为
使用比特币私钥对任意消息签名 aaron67 |
使用钱包工具或第三方服务验证这个输出,可以验签成功。
验签
在验证对消息的签名时,输入变成了比特币地址、原始消息和序列化后的致密签名,所以对应的验签过程也要微调。
- 从序列化后的签名中,解析出
recid
和 $(r, s)$,同时明确公钥的表示方式 - 恢复公钥
- 用公钥和消息验证签名 $(r, s)$
- 验证恢复出的公钥的哈希,是否与输入的比特币地址相匹配
利用recid
恢复公钥时,需要从点的 X 坐标求对应的 Y 坐标。对 Secp256k1 的曲线方程
$$
y^2 \equiv x^3 + 7 \pmod{p}
$$
知道了 $x$ 就等于知道了 $y^2 \bmod{p}$,为了求 $y$,需要“开方”,这很麻烦,因为有模运算。我们可以用费马小定理来改进。
对整数 $a$ 和质数 $p$,有
$$
a^p \equiv a \pmod{p}
$$
曲线 Secp256k1 的 $p$ 是一个质数,所以有
$$
y^{p} \equiv y \pmod{p}
$$
利用同余关系的性质,将上式两边同时放大 $y$ 倍,有
$$
y^{p+1} \equiv y^2 \pmod{p}
$$
即
$$
(y^2)^{\frac{p+1}{2}} \equiv y^2 \pmod{p}
$$
则
$$
y = (y^2)^{\frac{p+1}{4}} \bmod{p}\ \ \ \ 或\ \ \ \ -(y^2)^{\frac{p+1}{4}} \bmod{p}
$$
注意到,$\frac{p+1}{4}$ 是一个整数。也就是说,通过计算 $y^2$ 的整数次幂,就可以求解 $y$。
有了这些知识,不难写出对应的验签代码,请注意求解point_k
时对费马小定理的应用。
def verify_message(p2pkh_address: str, plain_text: str, signature: str) -> bool: |
我们用其他工具生成的签名作为输入,来检验验签代码的正确性。将私钥导入 ElectrumSV 钱包对消息签名,可以得到结果
IGdzMq98lowek10e3JFXWj909xp0oLRj71aF7jpWRxaabwH+fBia/K2JpoGQlFFbAl/Q5jo2DYSzQw6pZWhmRtk= |
调用验签方法测试。
if __name__ == '__main__': |
运行结果为
True |
输出符合预期。
完整代码
参考
- How does recovering the public key from an ECDSA signature work?
- moneybutton/bsv
- ECDSA Signatures allow recovery of the public key
- How do I get an ECDSA public key from just a Bitcoin signature? … SEC1 4.1.6
- In the sourcecode, what does this line mean that recovers the key from the signature?
- How to determine first byte (recovery ID) for signatures (message signing)?
- SEC 1: Elliptic Curve Cryptography 4.1.6 Public Key Recovery Operation
- Bitcoin how to get X value from Y
- BIP-322
- weex/bitcoin-signature-tool