ECDSA：椭圆曲线签名

ECDSA（椭圆曲线数字签名算法）是一种基于椭圆曲线密码学（ECC）的密码学安全数字签名方案。ECDSA 依赖有限域上椭圆曲线循环群的数学原理，以及 ECDLP 问题（椭圆曲线离散对数问题）的困难性。ECDSA 签名/验证算法依赖 EC 点乘法，其工作方式如下。在相同安全级别下，ECDSA 的密钥和签名比 RSA 更短。256 位 ECDSA 签名与 3072 位 RSA 签名具有相同的安全强度。

ECDSA 使用有限域上经典 Weierstrass 形式的密码学椭圆曲线（EC）。这些曲线由其 EC 域参数描述，并由 SECG: SEC 2 和 Brainpool（RFC 5639）等密码学标准规定。密码学中使用的椭圆曲线定义了：

  • 生成元点 G，用于曲线上的标量乘法（整数乘以 EC 点）
  • 由 G 生成的 EC 点子群的阶 n，它决定私钥长度（如 256 位）

例如，256 位椭圆曲线 secp256k1 具有：

  • 阶 n = 115792089237316195423570985008687907852837564279074904382605163141518161494337（素数）
  • 生成元点 G {x = 55066263022277343669578718895168534326250603453777594175500187360389116729240, y = 32670510020758816978083085130507043184471273380659243275938904335757337482424}

密钥生成

ECDSA 密钥对由以下部分组成：

  • 私钥（整数）：privKey
  • 公钥（EC 点）：pubKey = privKey * G

私钥是范围 [0...n-1] 内生成的随机整数。公钥 pubKey 是椭圆曲线上的一个点，通过 EC 点乘法计算：pubKey = privKey * G（私钥乘以生成元点 G）。

公钥 EC 点 {x, y} 可以压缩为其中一个坐标再加 1 位（奇偶性）。对于 secp256k1 曲线，私钥是 256 位整数（32 字节），压缩公钥是 257 位整数（~ 33 字节）。

ECDSA 签名

ECDSA 签名算法（RFC 6979）以消息 msg + 私钥 privKey 作为输入，并输出由一对整数 {r, s} 组成的签名。ECDSA 签名算法基于 ElGamal 签名方案，其工作方式如下（略有简化）：

  1. 使用 SHA-256 等密码学哈希函数计算消息哈希值：h = hash(msg)
  2. 在范围 [1..n-1] 内安全地生成一个随机数 k
    • 对于确定性 ECDSA，值 k 通过 HMAC 从 h + privKey 派生（参见 RFC 6979）
  3. 计算随机点 R = k * G，并取其 x 坐标：r = R.x
  4. 计算签名证明：s = k−1∗(h+r∗privKey)(modn)k^{-1} * (h + r * privKey) \pmod n
    • 模逆元 k−1(modn)k^{-1} \pmod n 是满足 k∗k−1≡1(modn)k * k^{-1} \equiv 1 \pmod n 的整数
  5. 返回签名 {r, s}。

计算出的签名 {r, s} 是一对整数，每个整数都位于范围 [1...n-1] 内。它编码了随机点 R = k * G 以及证明 s，用于确认签名者知道消息 h 和私钥 privKey。从原理上说，可以使用相应的 pubKey 验证证明 s。

对于签名过程中使用的曲线，ECDSA 签名的长度是签名者私钥的 2 倍。例如，对于 256 位椭圆曲线（如 secp256k1），ECDSA 签名为 512 位（64 字节）；对于 521 位曲线（如 secp521r1），签名为 1042 位。

ECDSA 签名验证

验证 ECDSA 签名的算法以已签名消息 msg、签名算法产生的签名 {r, s}，以及与签名者私钥相对应的公钥 pubKey 为输入。输出是布尔值：签名 valid 或 invalid。ECDSA 签名验证算法的工作方式如下（略有简化）：

  1. 使用签名时所用的同一种密码学哈希函数计算消息哈希值：h = hash(msg)
  2. 计算签名证明的模逆元：s1 = s−1(modn)s^{-1} \pmod n
  3. 恢复签名时使用的随机点：R' = (h * s1) * G + (r * s1) * pubKey
  4. 取 R' 的 x 坐标：r' = R'.x
  5. 比较 r' == r，得到签名验证结果

签名验证的总体思路是使用公钥恢复点 R'，并检查它是否与签名过程中随机生成的点 R 相同。

工作原理

可以用下面的简单方式解释 ECDSA 签名 {r, s}：

  • 签名过程使用私钥 privKey 和消息哈希值 h，通过椭圆曲线变换将随机点 R（仅以其 x 坐标表示）编码为数字 s。该数字是消息签名者知道私钥 privKey 的证明。由于 ECDLP 问题的困难性，签名 {r, s} 不会泄露私钥。
  • 签名验证使用公钥 pubKey 和消息哈希值 h，将签名中的证明数字 s 解码回原始点 R，并将恢复出的 R 的 x 坐标与签名中的 r 值进行比较。

ECDSA 签名/验证背后的数学原理

只有在你喜欢数学时才阅读本节。大多数开发者可以跳过。

上述签名/验证方案为何有效？答案并不显而易见，下面通过方程来推导一下。

在签名验证期间计算并恢复点 R' 的方程，可以通过将 pubKey 替换为 privKey * G，变换如下：

R' = (h * s1) * G + (r * s1) * pubKey =\ **** = (h * s1) * G + (r * s1) * privKey * G ****=\ **** = (h + r * privKey) * s1 * G

根据签名过程中计算出的数字 s = k−1∗(h+r∗privKey)(modn)k^{-1} * (h + r * privKey) \pmod n,，可以按如下方式计算 s1 = s−1(modn)s^{-1} \pmod n：

s1 = s−1(modn)s^{-1} \pmod n =\ \= (k−1∗(h+r∗privKey))−1(modn)(k^{-1} * (h + r * privKey))^{-1} \pmod n =\ \= k∗(h+r∗privKey)−1(modn)k * (h + r * privKey)^{-1} \pmod n

现在，替换点 R' 中的 s1。

R' = (h + r * privKey) * s1 * G =\ \= (h+r∗privKey)∗k∗(h+r∗privKey)−1(modn)(h + r * privKey) * k * (h + r * privKey)^{-1} \pmod n * G =\ **** = k * G

最后一步是比较由 pubKey 解码的点 R' 与由 privKey 编码的点 R。实际上，该算法只比较 R' 和 R 的 x 坐标，即整数 r' 和 r。

如果签名有效，应有 r' == r；如果签名、消息或公钥不正确，则有 r' ≠ r。

ECDSA：从签名恢复公钥

需要注意的是，ECDSA 签名方案允许从已签名消息和签名中恢复公钥。恢复过程基于一些数学计算（见 SECG: SEC 1 标准），并返回与签名相对应的 0、1 或 2 个可作为有效公钥的候选 EC 点。为避免这种歧义，一些 ECDSA 实现在签名过程中向签名添加额外的一位 v，使签名形式变为 {r, s, v}。利用这种扩展 ECDSA 签名 {r, s, v} 和已签名消息，可以可靠地恢复签名者的公钥。

在带宽或存储空间受限的环境（如区块链系统）中，如果无法承担传输或存储公钥的开销，从 ECDSA 签名恢复公钥会非常有用。例如，以太坊区块链对链上已签名交易使用扩展签名 {r, s, v}，以节省存储空间和带宽。

基于 ElGamal 签名方案的签名（如 DSA 和 ECDSA）支持公钥恢复。

results matching ""

    No results matching ""