ECDSA 签名
在相同的安全级别下,ECDSA 的密钥和签名比 RSA 短。256-bit 的 ECDSA 签名与 3071-bit 的 RSA 签名有着相同的安全性。
定义
基点 $G$:用于曲线上标量乘法,对于 secp256k1,有
x = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 y = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
阶 n:椭圆曲线群上点的个数,对于 secp256k1,有
0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
基域 $F_q$:椭圆曲线上点的坐标的取值范围,比 $n$ 稍大,对于 secp256k1,有
0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f (prime number)
- 私钥 $x$:随机数,取值范围为 [0, n-1]
公钥 $X$ = $x \cdot G$,是标量 $x$ 与基点 $G$ 的标量乘积
在椭圆曲线中,常用加法符号表示群运算(根据椭圆曲线点语法,将标量放在括号里),但是如果想用乘法表示法,也可以写为 $X = G^x$。这些差异在实践中并不重要。大多数情况下,加密协议并不关心群的基本性质,它们往往使用乘法表示群运算,但在基于椭圆曲线群定义的协议更倾向于使用加法表示群运算。
签名
- 计算消息哈希:$m = hash(msg)$ mod $n$,相当于将消息映射到了椭圆曲线上
- 取 nonce:$k \in [1, n-1]$。注意,每次签名都有选取不同的随机数,否则可以从两次的签名中反推私钥。通常推荐 $k$ 的计算方法:$k=hash(x, msg)$ mod $n$
- 计算点 $R = k \cdot G$,得到 $R$ 的 x 坐标 $r = R.x$ mod $n$,如果为 0,返回第 1 步
- 计算签名的 proof:$s = k^{-1}(m + r \cdot x)$ mod $n$,如果为 0,返回第 1 步
- 返回签名 signature {$r$, $s$}
验签
- 计算消息哈希:$m = hash(msg)$ mod $n$
- 计算 $R' = s^{-1}m \cdot G + s^{-1}r \cdot X$
- 取 $R'$ 的横坐标 $r'=R'.x$ mod $n$,校验 $r==r'$
推导:
$$ \begin{align} R'&=(s^{-1}m) \cdot G + (s^{-1}xr) \cdot G \\ &=(s^{-1}(m + rx)) \cdot G \\ &=k^{-1} \cdot G \\ &=R \end{align} $$
安全机制
- 签名:将随机点 $R$ 通过私钥 $x$ 和消息的哈希 $m$ 编码为一个数字 $s$,该数字是签名者知道私钥的 proof。由于 ECDLP problem,无法从签名 {$r$, $s$} 反推私钥。
- 验签:使用公钥 $X$ 和消息的哈希 $m$ 将 $s$ 解码,还原出点 $R$,通过比对 $R.x$ 与签名中的 $r$ 完成验证
Schnorr 签名
Schnorr 相对于 ECCSA 来说,更快速(没有求逆运算),并且可以实现多签。不过不像 ECDSA,Schnorr 不提供恢复签名者的公钥机制。
签名
schnorr 签名本质上是两个值,R 和 s,其中 R 是对某个秘密随机值的承诺(通常称秘密值为 nonce,因为它对每个签名都是唯一的),s 是通过承诺 R、私钥(见证 x)和消息及时的值。
- 计算公钥:$X = x \cdot G$
- 取 nonce:$k \in [1, n-1]$。注意,每次签名都有选取不同的随机数。
- 计算 nonce 的承诺:$R = k \cdot G$
- 计算挑战:$e = hash(msg, R)$ mod $n$
- 计算证据:$s=k + e \cdot x$ mod $n$
- $\left\{R, s\right\}$
验签
- $e = hash(msg, R)$ mod $n$
- $P_1 = s \cdot G$
- $P_2 = R + e \cdot X$
- $P_1 == P_2$
推导:
$P_1 = s \cdot G = (k + e \cdot x) \cdot G = k \cdot G + e \cdot x \cdot G = R + e \cdot X = P_2$
EdDSA 签名
EdDSA (Edwards-curve Digital Signature Algorithm) 是一个现代的、安全带签名算法,Ed25519 是它的变种。
EdDSA 比 ECDSA 更安全,更简单,更容易理解和实现。对于大多数曲线(比如 edwards25519),EdDSA 算法比 ECDSA 更快。不过不像 ECDSA,EdDSA 不提供恢复签名者的公钥机制。
EdDSA 一个特殊之处在于,该方案不需要每次签名都使用全新的随机数。而对于 ECDSA,如果两次签名使用了相同的随机数,会导致私钥泄露。
EdDSA 签名与 Schnorr 签名类似,不同之处在于
- EdDSA 用密钥和消息确定性地生成 nonce,确保了只要消息不同,生成的 nonce 不同,避免了两次签名因 nonce 相同而导致密钥泄露
- 签名者的公钥包含在挑战中
签名
EdDSA 不直接生成签名密钥,而是首先生成一个密钥并用它派生实际的签名密钥 x 和 nonce 密钥。
EdDSA_sign(msg, privKey) --> { R, s }
私钥为 $d$,计算 $(low_{bit}, hi_{bit}) = sha512(d)$
则签名密钥为 $x=low_{bit}$
nonce 为 $k=sha256(hi_{bit}, msg)$ mod $ n$
- 计算公钥 $X = x \cdot G$
- 计算 nonce 的承诺:$R = k \cdot G$
- 计算挑战:$e = hash(R, X, msg)$ mod $n$
- 计算证据:$s = (k + e \cdot x)$ mod $n$
- {$R, s$}
验签
EdDSA_signature_verify(msg, pubKey, signature { R, s } ) --> valid / invalid
- $e = hash(R, X, msg)$ mod $n$
- $P_1 = s \cdot G$
- $P_2 = R + e \cdot X$
- $P_1 == P_2$
推导:
$P_1 = s \cdot G = (k + e \cdot x) \cdot G = k \cdot G + e \cdot x \cdot G = R + e \cdot X = P_2$
参考
戴维-王. 深入浅出密码学[M]
没有评论