使用比特币私钥对任意消息签名

在双钥系统中,签名可以作为身份认证和授权的手段。

  • 对签名方,能提供正确的签名,就意味着他一定有私钥
  • 对验证方,验签通过即可保证,消息内容未经篡改,且消息来源可靠

在比特币中也一样,我可以向你提供下列信息,来证明该地址属于我。

内容
地址 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_idrecid,把包含了此标记的 ECDSA 签名 $(recid, r, s)$,称为“可恢复”签名(recoverable ECDSA signature)或致密签名(compact signature)。

对应代码不难实现,只需在计算 $(r, s)$ 时同时计算recid即可。

def sign_recoverable(private_key: int, message: bytes) -> tuple:
"""Create recoverable ECDSA signature, aka compact signature, (recovery_id, r, s)"""
e = hash_to_int(message)
recovery_id, r, s = 0, 0, 0
while not r or not s:
k = random.randrange(1, curve.n)
k_x, k_y = scalar_multiply(k, curve.g)
# r
r = k_x % curve.n
recovery_id = 0 | 2 if k_x > curve.n else 0 | k_y % 2
# s
s = ((e + r * private_key) * modular_multiplicative_inverse(k, curve.n)) % curve.n
return recovery_id, r, s

计算消息摘要

用私钥对交易签名,实际上是用私钥对交易摘要签名。类似的,对消息签名时,需要先计算消息的摘要,然后对消息摘要签名。

消息摘要有特定的格式。

内容
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:
"""Serialize plain text message to format (LEN || message.utf-8)"""
msg_bytes = message.encode('utf-8')
return int_to_varint(len(msg_bytes)) + msg_bytes


def message_digest(message: str) -> bytes:
"""Returns the digest of plain text message"""
return message_bytes('Bitcoin Signed Message:\n') + message_bytes(message)

调用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


def sign_message(private_key: int, plain_text: str) -> tuple:
"""Sign arbitrary message with bitcoin private key, returns (p2pkh_address, serialized_compact_signature)"""
d = message_digest(plain_text)
# recovery signature
recovery_id, r, s = sign_recoverable(private_key, d)
# p2pkh address
public_key = scalar_multiply(private_key, curve.g)
p2pkh_address = public_key_to_address(public_key, compressed=True)
# prefix = 27 + recovery_id + (4 if using compressed public key else 0)
prefix = 27 + recovery_id + 4
serialized_sig = prefix.to_bytes(1, byteorder='big') + r.to_bytes(32, byteorder='big') + s.to_bytes(32, byteorder='big')
return p2pkh_address, b64encode(serialized_sig).decode('ascii')

我们写一个简单的例子来测试。

if __name__ == '__main__':
# 私钥
priv_key = 0xf97c89aaacf0cd2e47ddbacc97dae1f88bec49106ac37716c451dcdd008a4b62
# 公钥
pub_key = scalar_multiply(priv_key, curve.g)
# 消息
plain = '使用比特币私钥对任意消息签名 aaron67'
print(plain)
# 签名
print(sign_message(priv_key, plain))

输出为

使用比特币私钥对任意消息签名 aaron67
('1AfxgwYJrBgriZDLryfyKuSdBsi59jeBX9', 'H87QAsj1vFPZBNBCyfJtOK2HW9IpM5Bio5zoeRoMr7Yb4Qr4//4X/C/Ah5d64Lq4P/5EKImfnAIW8x0zx74HQSs=')

使用钱包工具或第三方服务验证这个输出,可以验签成功。

验签

在验证对消息的签名时,输入变成了比特币地址、原始消息和序列化后的致密签名,所以对应的验签过程也要微调。

  1. 从序列化后的签名中,解析出recid和 $(r, s)$,同时明确公钥的表示方式
  2. 恢复公钥
  3. 用公钥和消息验证签名 $(r, s)$
  4. 验证恢复出的公钥的哈希,是否与输入的比特币地址相匹配

利用recid恢复公钥时,需要从点的 X 坐标求对应的 Y 坐标。对 Spec256k1 的曲线方程

$$
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 = y^2 \bmod{p}$,有

$$
Y^{\frac{p+1}{2}} \equiv Y \pmod{p}
$$

$$
y = Y^{\frac{p+1}{4}} \bmod{p}\ \ \ \ 或\ \ \ \ -Y^{\frac{p+1}{4}} \bmod{p}
$$

注意到,$\frac{p+1}{4}$ 是一个整数。也就是说,通过计算 $Y$ 的整数次幂,就可以求解 $y$。

有了这些知识,不难写出对应的验签代码,请注意求解point_k时对费马小定理的应用。

def verify_message(p2pkh_address: str, plain_text: str, signature: str) -> bool:
"""Verify serialized compact signature with p2pkh address and plain text"""
sig_bytes = b64decode(signature)
if len(sig_bytes) != 65:
return False
prefix, r, s = sig_bytes[0], int.from_bytes(sig_bytes[1:33], byteorder='big'), int.from_bytes(sig_bytes[33:], byteorder='big')
# Calculate recovery_id
compressed = False
if prefix < 27 or prefix >= 35:
return False
if prefix >= 31:
compressed = True
prefix -= 4
recovery_id = prefix - 27
# Recover point kG, k is the ephemeral private key
x = r + (curve.n if recovery_id >= 2 else 0)
y_squared = (x * x * x + curve.a * x + curve.b) % curve.p
y = pow(y_squared, (curve.p + 1) // 4, curve.p)
if (y + recovery_id) % 2 != 0:
y = -y % curve.p
point_k = (x, y)
# Calculate point aG, a is the private key
d = message_digest(plain_text)
e = hash_to_int(d)
mod_inv_r = modular_multiplicative_inverse(r, curve.n)
public_key = add(scalar_multiply(mod_inv_r * s, point_k), scalar_multiply(mod_inv_r * (-e % curve.n), curve.g))
# Verify signature
if not verify_signature(public_key, d, (r, s)):
return False
# Check public key hash
if public_key_hash(public_key, compressed) != address_to_public_key_hash(p2pkh_address):
return False
# OK
return True

我们用其他工具生成的签名作为输入,来检验验签代码的正确性。将私钥导入 ElectrumSV 钱包对消息签名,可以得到结果

IGdzMq98lowek10e3JFXWj909xp0oLRj71aF7jpWRxaabwH+fBia/K2JpoGQlFFbAl/Q5jo2DYSzQw6pZWhmRtk=

调用验签方法测试。

if __name__ == '__main__':
# 私钥
priv_key = 0xf97c89aaacf0cd2e47ddbacc97dae1f88bec49106ac37716c451dcdd008a4b62
# 公钥
pub_key = scalar_multiply(priv_key, curve.g)
# 地址
address = public_key_to_address(pub_key, compressed=True)
# 消息
plain = '使用比特币私钥对任意消息签名 aaron67'
# 验证签名
sig_electrum = 'IGdzMq98lowek10e3JFXWj909xp0oLRj71aF7jpWRxaabwH+fBia/K2JpoGQlFFbAl/Q5jo2DYSzQw6pZWhmRtk='
print(verify_message(address, plain, sig_electrum))

运行结果为

True

输出符合预期。

完整代码

sign_message.py

参考