ECDSA
ECDSA 是一个基于椭圆曲线的签名算法,使用时需要确定一个椭圆曲线,以及它的 base point
本文主要参考了 ECDSA - Wikipedia。
生成 key pair
生成 key pair 的时候,私钥是整数
签名
签名的时候,对于给定的消息
- 计算哈希:
,例如用 SHA 系列的哈希算法 - 考虑到
的位数可能比 的位数更多,取 的高位,使得位数和 一致,得到的结果记为 - 生成一个密码学安全的随机数
- 计算
,取它的 X 坐标为 - 计算
- 计算
- 如果
或者 等于 0,取新的 再重试 - 得到的 ECDSA 签名就是
两个数
验证
验证签名的时候,已知
- 前两步和计算签名的算法一致,求哈希和截断后得到
- 计算
- 计算
,取它的 X 坐标为 - 如果
,则签名合法
上面的过程忽略了一些边界情况的检查,详细版本见 Wikipedia。
下面进行验算:
等式左边的 X 坐标等于等式右边的 X 坐标,等价于
公钥恢复
ECDSA 支持公钥恢复算法,已知
上式中
- 在椭圆曲线上找到 X 坐标模
等于 的点,这个点就是 - 按照计算哈希的前两步,从
计算出 - 按照上述公式,计算出
但是实际上第一步没有这么简单:首先同一个 X 坐标对应椭圆曲线上的两个点,其次
// Source: https://github.com/ethereum/go-ethereum/blob/e1fe6bc8469c626afaa86b1dfb819737e980a574/crypto/secp256k1/libsecp256k1/src/modules/recovery/main_impl.h#L104-L112
if (recid & 2) {
if (secp256k1_fe_cmp_var(&fx, &secp256k1_ecdsa_const_p_minus_order) >= 0) {
return 0;
}
secp256k1_fe_add(&fx, &secp256k1_ecdsa_const_order_as_fe);
}
if (!secp256k1_ge_set_xo_var(&x, &fx, recid & 1)) {
return 0;
}
参考:Crypto Magic: Recovering Alice’s Public Key From An ECDSA Signature 和 Can We Recover The Public Key from an ECDSA Signature?
DSA 公钥恢复
如果在 DSA 算法上尝试上面的公钥恢复流程,就会遇到困难:
此时会发现无法从
更加完整的讨论可以见 Can we recover public key from DSA signatures as we can from ECDSA?。
Nonce Reuse Attack
在生成 ECDSA 签名的时候,注意不能用固定的 nonce(
两次签名的 nonce
签名是公开信息,也就是说
这样就把私钥