Cryptography/椭圆曲线签名与验签

这节介绍椭圆曲线签名算法(Elliptic Curve Digital Signature Algorithm, ECDSA)与其验签步骤. 文章 https://www.cs.miami.edu/home/burt/learning/Csc609.142/ecdsa-cert.pdf 7 章节有详细的介绍, 此处只摘录重要结论.

签名

  1. Select a random or pseudorandom integer k, 1 <= k <= n - 1.
  2. Compute kG = (x1, y1) and convert x1 to integer.
  3. Compute r = x1 mod n. If r = 0 then go to step 1.
  4. Compute k⁻¹ mod n.
  5. Compute SHA-1(m) and convert this bit string to an integer e.
  6. Compute s = k⁻¹(e + d * r) mod n. If s = 0 then go to step 1.
  7. Signature for the message m is (r, s).

ECDSA 十分依赖 k 的随机性. 绝对不能在不同的签名中使用相同的 k. 在两个签名中使用相同的 k, 可以逆推出私钥.

验签

  1. Verify that r and s are integers in the interval [1, n - 1].
  2. Compute SHA-1(m) and convert this bit string to an integer e.
  3. Compute w = s⁻¹ mod n.
  4. Compute u1 = e * w mod n and u2 = r * w mod n.
  5. Compute X = u1 * G + u2 * Q.
  6. If X = 0, then reject the signature. Otherwise, convert the x-coordinate x1 of X to an integer x1, and compute v = x1 mod n.
  7. Accept the signature if and only if v = r.

代码实现

import random
import secp256k1

prikey = 0x5f6717883bef25f45a129c11fcac1567d74bda5a9ad4cbffc8203c0da2a1473c
pubkey = secp256k1.G * prikey

# Hash of messages. Generated by "sha256sum secp256k1.py"
m = 0x72a963cdfb01bc37cd283106875ff1f07f02bc9ad6121b75c3d17629df128d4e
print(f'hash=0x{m:064x}')

# Sign
while True:
    k = random.randint(0, secp256k1.N)
    R = secp256k1.G * k
    r = R.x.x % secp256k1.N
    if r == 0:
        continue
    k_inv = pow(k, -1, secp256k1.N)
    s = ((m + prikey * r) * k_inv) % secp256k1.N
    if s == 0:
        continue
    print(f'sigr=0x{r:064x}')
    print(f'sigs=0x{s:064x}')
    break


# Verify
assert 0 <= r < secp256k1.N
assert 0 <= s < secp256k1.N
w = pow(s, -1, secp256k1.N)
u1 = (m * w) % secp256k1.N
u2 = (r * w) % secp256k1.N
x = secp256k1.G * u1 + pubkey * u2
if x == secp256k1.I:
    print('fail')
v = x.x.x % secp256k1.N
assert v == r
print('pass')

完整代码: https://github.com/mohanson/secp256k1-python

参考