在文章非对称加密和签名认证中,我们介绍了双钥系统的两种应用场景:
- 加密解密时,公钥用于加密,私钥用于解密
- 身份认证时,私钥用于签名,公钥用于验证
椭圆曲线密码学(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 |
import random |
如果每次签名都使用相同的 $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: |
证明
在开始之前,需要先明确一点:椭圆曲线上点的加法运算,符合交换律和结合律。
所以有 $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__': |
运行结果为
r = 114587593887127314608220924841831336233967095853165151956820984900193959037698 |
输出符合预期。
签名的“对称性”
对 ECDSA 签名 $(r, s)$,在验证时如果使用 $(r, -s \bmod{n})$,则也能验签成功。
if __name__ == '__main__': |
运行结果为
r = 106466997694091524629965845090867478458136818253940782993316021692670806749258 |
这个“特性”本文暂不展开介绍,直接把结论放在这里,以保证整体内容的完整性。
完整代码
参考
- Elliptic Curve Cryptography: a gentle introduction 原文 译文
- Elliptic Curve Cryptography: finite fields and discrete logarithms 原文 译文
- Elliptic Curve Cryptography: ECDH and ECDSA 原文 译文
- GitHub andreacorbellini/ecc
- ECDSA 详解
- 椭圆曲线加密算法
- Digital Signatures (Signing & Verifying)