椭圆曲线数字签名算法

在文章非对称加密和签名认证中,我们介绍了双钥系统的两种应用场景:

  • 加密解密时,公钥用于加密,私钥用于解密
  • 身份认证时,私钥用于签名,公钥用于验证

椭圆曲线密码学(ECC,Elliptic Curve Cryptogphay)是一种流行的非对称加密算法,其背后的数学原理,是椭圆曲线上的离散对数难题。我们还知道,ECC 的私钥,本质是一个整数,其对应的公钥,是椭圆曲线上的一个点。

在将 ECC 作为双钥系统使用时,针对不通过的应用场景,会涉及到不同的算法。常见的有

  • 在加密和解密时使用的椭圆曲线集成加密框架(ECIES,Elliptic Curve Integrated Encryption Schema)
  • 用于协商和交换公共密钥的椭圆曲线 Diffie-Hellman 密钥交换算法(ECDH,Elliptic Curve Diffie-Hellman Key Exchange)
  • 用于生成和验证数字签名的椭圆曲线数字签名算法(ECDSA,Elliptic Curve Digital Signature Algorithm)

本文将介绍并实现 ECDSA 的相关内容。

签名

用私钥 $a$ 对消息 $m$ 签名,得到的结果是两个整数 $(r, s)$ ,计算过程如下。

  • 随机生成临时私钥 $k$,并计算其对应的公钥 $K = k \cdot G = (x_K, y_K)$
  • 计算 $r = x_K \bmod{n}$,若 $r$ 为 0,则回到第一步
  • 计算消息 $m$ 的哈希 $e = hash(m)$,并将 $e$ 的二进制序列转成一个整数
  • 计算 $s = k^{-1}(e + ra) \bmod{n}$,若 $s$ 为 0,则回到第一步
  • 得到签名 $(r, s)$
import hashlib


def sha256(payload: bytes) -> bytes:
return hashlib.sha256(payload).digest()


def double_sha256(payload: bytes) -> bytes:
return sha256(sha256(payload))
import random


def hash_to_int(message: bytes) -> int:
"""Calculate the bitcoin double-sha256 hash of the message, return as an integer"""
h = double_sha256(message)
return int.from_bytes(h, byteorder='big')


def sign(private_key: int, message: bytes) -> tuple:
"""Create ECDSA signature (r, s)"""
e = hash_to_int(message)
r, s = 0, 0
while not r or not s:
k = random.randrange(1, curve.n)
k_x, _ = scalar_multiply(k, curve.g)
r = k_x % curve.n
s = ((e + r * private_key) * modular_multiplicative_inverse(k, curve.n)) % curve.n
return r, s

如果每次签名都使用相同的 $k$,当知道了消息 $e_1$、$e_2$ 和签名 $(r_1, s_1)$、$(r_2, s_2)$ 时,有

  • $r_1 = r_2$,因为 $k$ 相同
  • 根据 $s$ 的定义,有 $s_1 - s_2 = k^{-1}(e_1 - e_2) \bmod{n}$
  • 将上式两边同时乘以 $k$ 再除以 $(s_1 - s_2)$,有 $k = (s_1 - s_2)^{-1}(e_1 - e_2) \bmod{n}$

这样就得到了 $k$,再根据 $s = k^{-1}(e + ra) \bmod{n}$,从而反推出 $a = r^{-1}(sk - e) \bmod{n}$。类似的攻击方法在 $k$ 值可预测时也能使用。

所以请务必注意,每次签名时使用的 $k$,都需要保证绝对私密且生成时足够随机,以保证私钥 $a$ 的安全。

验签

用公钥 $A$ 和消息 $m$ 验证签名 $(r, s)$,过程如下。

  • 计算消息 $m$ 的哈希 $e = hash(m)$,并将 $e$ 的二进制序列转成一个整数
  • 计算整数 $u_1 = s^{-1}e \bmod{n}$
  • 计算整数 $u_2 = s^{-1}r \bmod{n}$
  • 计算点 $P = u_1 \cdot G + u_2 \cdot A = (x_P, y_P)$
  • 当且仅当 $r = x_P \bmod{n}$ 时,验签成功
def verify_signature(public_key: tuple, message: bytes, signature: tuple) -> bool:
"""Verify signature with public key and message"""
e = hash_to_int(message)
r, s = signature
w = modular_multiplicative_inverse(s, curve.n)
u1 = (w * e) % curve.n
u2 = (w * r) % curve.n
x, _ = add(scalar_multiply(u1, curve.g), scalar_multiply(u2, public_key))
return r == (x % curve.n)

证明

在开始之前,需要先明确一点:椭圆曲线上点的加法运算,符合交换律和结合律。

所以有 $aG + bG = (a + b) \cdot G$,因为

$$
aG + bG = \underbrace{G + G + … + G}_{a\ 个} + \underbrace{G + G + … + G}_{b\ 个} = \underbrace{G + G + … + G}_{(a + b)\ 个} = (a + b) \cdot G
$$

进一步的,有 $a \cdot bG = ab \cdot G$,因为

$$
a \cdot bG = \underbrace{bG + bG + … + bG}_{a\ 个} = \underbrace{(G + … + G) + … + (G + … + G)}_{a\ 个} = \underbrace{G + G + … + G}_{ab\ 个} = ab \cdot G
$$

让我们借助上面这两个推论,通过公式变换,证明验签过程的正确性。

已知 $A = aG$,则

$$
P = u_1 \cdot G + u_2 \cdot A = u_1 \cdot G + u_2 \cdot aG = (u_1 + u_2a) \cdot G
$$

带入 $u_1$ 和 $u_2$ 的定义,则

$$
P = (u_1 + u_2a) \cdot G = (s^{-1}e + s^{-1}ra) \cdot G = s^{-1}(e + ra) \cdot G
$$

请注意,这里我们忽略了 $u_1$ 和 $u_2$ 定义中的模 $n$ 运算,这不会有任何问题,因为 $a \cdot G = (a \bmod{n}) \cdot G$。如果你想知道为什么,可以搜索关键字“循环子群”阅读更多资料。

我们还知道 $s = k^{-1}(e + ra) \bmod{n}$,将等式两边同时乘以 $k$ 再除以 $s$,就会得到

$$
k = s^{-1}(e + ra) \bmod{n}
$$

也就是说,如果 $(r, s)$ 正确,验签时计算出的点 $P$ 就是签名时临时私钥 $k$ 对应的公钥。

$$
P = s^{-1}(e + ra) \cdot G = k \cdot G = (x_P, y_P)
$$

根据 $r$ 的定义,即当且仅当 $r = x_P \bmod{n}$ 时,验签成功。

验证

我们可以写一个简单的例子来测试代码。

if __name__ == '__main__':
# 私钥
priv_key = 0xf97c89aaacf0cd2e47ddbacc97dae1f88bec49106ac37716c451dcdd008a4b62
# 公钥
pub_key = scalar_multiply(priv_key, curve.g)
# 要签名的消息
m = '你好世界'.encode('utf-8')
# 签名
sig_r, sig_s = sign(priv_key, m)
print('r =', sig_r)
print('s =', sig_s)
# 验证签名 (r, s)
print(verify_signature(pub_key, m, (sig_r, sig_s)))

运行结果为

r = 114587593887127314608220924841831336233967095853165151956820984900193959037698
s = 24000727837347392504013031837120627225728348681623127776947626422811445180558
True

输出符合预期。

签名的“对称性”

对 ECDSA 签名 $(r, s)$,在验证时如果使用 $(r, -s \bmod{n})$,则也能验签成功。

if __name__ == '__main__':
#
# ...
#
# 验证签名 (r, -s)
negative_s = -sig_s % curve.n
print('-s =', negative_s)
print(verify_signature(pub_key, m, (sig_r, negative_s)))

运行结果为

 r = 106466997694091524629965845090867478458136818253940782993316021692670806749258
s = 62904381853960967395432938678025872957596216909471919761592805395928247608025
True
-s = 52887707383355228028138046330662034895241347369602984621012357745589913886312
True

这个“特性”本文暂不展开介绍,直接把结论放在这里,以保证整体内容的完整性。

完整代码

sign.py

参考