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$。这些差异在实践中并不重要。大多数情况下，加密协议并不关心群的基本性质，它们往往使用乘法表示群运算，但在基于椭圆曲线群定义的协议更倾向于使用加法表示群运算。

签名

1. 计算消息哈希：$m=hash(msg)$ mod $n$，相当于将消息映射到了椭圆曲线上
2. 取 nonce：$k\in [1,n-1]$。注意，每次签名都有选取不同的随机数，否则可以从两次的签名中反推私钥。通常推荐 $k$ 的计算方法：$k=hash(x,msg)$ mod $n$
3. 计算点 $R=k\cdot G$，得到 $R$ 的 x 坐标 $r=R.x$ mod $n$，如果为 0，返回第 1 步
4. 计算签名的 proof：$s=k^{-1}(m+r\cdot x)$ mod $n$，如果为 0，返回第 1 步
5. 返回签名 signature {$r$, $s$}

验签

1. 计算消息哈希：$m=hash(msg)$ mod $n$
2. 计算 $R^{\prime }=s^{-1}m\cdot G+s^{-1}r\cdot X$
3. 取 $R^{\prime }$ 的横坐标 $r^{\prime }=R^{\prime }.x$ mod $n$，校验 $r==r^{\prime }$

推导：

$$\begin{array}{rl}{R}^{\prime }& =(s^{-1}m)\cdot G+(s^{-1}xr)\cdot G\\ & =(s^{-1}(m+rx))\cdot G\\ & =k^{-1}\cdot G\\ & =R\end{array}$$

安全机制

• 签名：将随机点 $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）和消息及时的值。

1. 计算公钥：$X=x\cdot G$
2. 取 nonce：$k\in [1,n-1]$。注意，每次签名都有选取不同的随机数。
3. 计算 nonce 的承诺：$R=k\cdot G$
4. 计算挑战：$e=hash(msg,R)$ mod $n$
5. 计算证据：$s=k+e\cdot x$ mod $n$
6. $\{R,s\}$

验签

1. $e=hash(msg,R)$ mod $n$
2. $P_1=s\cdot G$
3. $P_2=R+e\cdot X$
4. $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 }

1. 私钥为 $d$，计算 $(lo{w}_{bit},h{i}_{bit})=sha512(d)$

   则签名密钥为 $x=lo{w}_{bit}$

   nonce 为 $k=sha256(h{i}_{bit},msg)$ mod $n$

2. 计算公钥 $X=x\cdot G$
3. 计算 nonce 的承诺：$R=k\cdot G$
4. 计算挑战：$e=hash(R,X,msg)$ mod $n$
5. 计算证据：$s=(k+e\cdot x)$ mod $n$
6. {$R,s$}

验签

EdDSA_signature_verify(msg, pubKey, signature { R, s } ) --> valid / invalid

1. $e=hash(R,X,msg)$ mod $n$
2. $P_1=s\cdot G$
3. $P_2=R+e\cdot X$
4. $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]

ECDSA: Elliptic Curve Signatures

Schnorr Digital Signature

eddsa-and-ed25519

【新火公开课】密码学基础系列课程2(下): 数字签名