# ECDSA

Original: <https://lifelonglearn.ing/ecdsa>

Author: [奶爸](https://lifelonglearn.ing/users/3b04650c-8231-499b-8ef0-381fc4d7efb0)

Published: 2022-10-29T15:03:32Z

Updated: 2026-09-27T06:57:43Z

Version: 1

关于 ECDSA 的介绍在本文中不再赘述，只提示你 ECDSA 没有想象中那么复杂，曲线都是密码学专家们选择的，我们只需要使用一个经验证的曲线和参数即可，此文章 「[SafeCurves:choosing safe curves for elliptic-curve cryptography](https://lifelonglearn.ing/r/go?url=aHR0cDovL3NhZmVjdXJ2ZXMuY3IueXAudG8vcmlnaWQuaHRtbA==)」中列出了一些常见曲线。

签名算法是区块链账户体系的本源，是账户与链交互，确定账户归属的根本。

接下来我们使用 以太坊 和 比特币 都在使用的 **secp256k1** 曲线来手工复现密钥的生成与签名过程。

## Keygen

1. 首先我们定义 [secp256k1](https://lifelonglearn.ing/r/go?url=aHR0cHM6Ly9uZXVyb21hbmNlci5zay9zdGQvc2VjZy9zZWNwMjU2azE=) 这个曲线的参数，其实 `go-ethereum` 中已有定义，我们手动做一下加深印象。
   ```go
   package main

   import (
   	"crypto/rand"
   	"crypto/sha256"
   	"encoding/hex"
   	"fmt"
   	"math/big"

   	"github.com/ethereum/go-ethereum/common/math"
   	"github.com/ethereum/go-ethereum/crypto/secp256k1"
   	cmath "github.com/starkbank/ecdsa-go/ellipticcurve/math"
   	"github.com/starkbank/ecdsa-go/ellipticcurve/point"
   )

   type _G struct {
   	x, y *big.Int
   }

   var P, A, B, N *big.Int
   var G *_G

   // 这里提供了开箱即用的加法乘法运算
   var curve *secp256k1.BitCurve

   func init() {
   	P = new(big.Int)
   	P.SetString("fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f", 16)

   	A = new(big.Int)
   	B = big.NewInt(7)

   	G = &_G{
   		x: new(big.Int),
   		y: new(big.Int),
   	}
   	G.x.SetString("79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798", 16)
   	G.y.SetString("483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8", 16)

   	N = new(big.Int)
   	N.SetString("fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141", 16)

   	curve = &secp256k1.BitCurve{
   		P:       P,
   		B:       B,
   		N:       N,
   		Gx:      G.x,
   		Gy:      G.y,
   		BitSize: 256,
   	}
   }
   ```
2. 随机选取一个私钥 d \in [0...N-1]
   ```go
   // d, err := rand.Int(rand.Reader, N)
   dBytes, err := hex.DecodeString("42243a2e1088468b5fca38e1c696633348846b2c0794c44cd8ed05953c7f2950")
   if err != nil {
   	panic(err)
   }
   d := new(big.Int).SetBytes(dBytes)
   fmt.Printf("private key: %x\n", d)
   // private key: 42243a2e1088468b5fca38e1c696633348846b2c0794c44cd8ed05953c7f2950
   ```
3. 推算公钥 Q = d \cdot G，`d` 就是我们生成的大随机数，`G` 为 `secp256k1` 这条曲线选定的生成元，[multiple](https://lifelonglearn.ing/r/go?url=aHR0cHM6Ly9naXRodWIuY29tL2V0aGVyZXVtL2dvLWV0aGVyZXVtL2Jsb2IvdjEuMTAuMjUvY3J5cHRvL3NlY3AyNTZrMS9zY2FsYXJfbXVsdF9jZ28uZ28jTDI0) 的具体实现
   ```go
   pX, pY := curve.ScalarBaseMult(d.Bytes())
   fmt.Printf("isOnCurve: %v\n", curve.IsOnCurve(pX, pY))
   // isOnCurve: true
   fmt.Printf("public key: %x\n", curve.Marshal(pX, pY))
   // public key: 0480840c35efafb8d5fc5c2edcf41b276bdf80ac888d51cc71c8eb4795488275e6b3ab36e01e8cb8e78842d675ac111833eb9f00bd29472c28fae256f1912e38b5
   ```

## Sign

对消息 「奶爸」进行签名，取消息的哈希 msgHash=sha256(奶爸)，取随机数 `k`，得到 R = kG，然后得到 r = Rx \mod N，s = k^{-1}(z+dr) \mod N，最终签名就是 `(r,s)`，可以使用 [此工具](https://lifelonglearn.ing/r/go?url=aHR0cDovL2tqdXIuZ2l0aHViLmlvL2pzcnNhc2lnbi9zYW1wbGUvc2FtcGxlLWVjZHNhLmh0bWw=) 进行验证

```go
func sign(msg string, privateKey *big.Int) (*big.Int, *big.Int, *big.Int) {
	// random K
	k, err := rand.Int(rand.Reader, math.MaxBig256)
	if err != nil {
		panic(err)
	}
	// msgHash = sha256(msg)
	h := sha256.Sum256([]byte(msg))
	msgHash := new(big.Int).SetBytes(h[:])
	// R = k*G
	Rx, _ := curve.ScalarBaseMult(k.Bytes())
	// r = Rx
	r := Rx
	// s = K^-1 * (msgHash + r*d) mod N
	rd := new(big.Int).Mul(privateKey, r)
	s := new(big.Int).Mod(new(big.Int).Mul(new(big.Int).Add(msgHash, rd), new(big.Int).ModInverse(k, N)), N)
	return r, s, k
}
```

## Verify

```go
func verify(msg string, r, s *big.Int, publicKey point.Point) bool {
	// msgHash = sha256(msg)
	h := sha256.Sum256([]byte(msg))
	msgHash := new(big.Int).SetBytes(h[:])
	// s1 = s^-1
	s1 := new(big.Int).ModInverse(s, N)
	// R' = (msgHash*s1)*G + (r*s1)*publicKey
	hs1 := new(big.Int).Mul(msgHash, s1)
	rs1 := new(big.Int).Mul(r, s1)
	hs1G := cmath.Multiply(point.Point{
		X: G.x,
		Y: G.y,
	}, hs1, N, A, P)
	rs1Q := cmath.Multiply(publicKey, rs1, N, A, P)
	R1 := cmath.Add(hs1G, rs1Q, A, P)
	// r' = R'.x
	r1 := R1.X
	// check r' = r
	return new(big.Int).Mod(r1, curve.N).Cmp(r) == 0
}
```

## Full code

```go
package main

import (
	"crypto/rand"
	"crypto/sha256"
	"encoding/hex"
	"fmt"
	"math/big"

	"github.com/ethereum/go-ethereum/common/math"
	"github.com/ethereum/go-ethereum/crypto/secp256k1"
	cmath "github.com/starkbank/ecdsa-go/ellipticcurve/math"
	"github.com/starkbank/ecdsa-go/ellipticcurve/point"
)

type _G struct {
	x, y *big.Int
}

var P, A, B, N *big.Int
var G *_G

// 这里提供了开箱即用的加法乘法运算
var curve *secp256k1.BitCurve

func init() {
	P = new(big.Int)
	P.SetString("fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f", 16)

	A = new(big.Int)
	B = big.NewInt(7)

	G = &_G{
		x: new(big.Int),
		y: new(big.Int),
	}
	G.x.SetString("79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798", 16)
	G.y.SetString("483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8", 16)

	N = new(big.Int)
	N.SetString("fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141", 16)

	curve = &secp256k1.BitCurve{
		P:       P,
		B:       B,
		N:       N,
		Gx:      G.x,
		Gy:      G.y,
		BitSize: 256,
	}
}

func main() {
	// d, err := rand.Int(rand.Reader, N)
	dBytes, err := hex.DecodeString("42243a2e1088468b5fca38e1c696633348846b2c0794c44cd8ed05953c7f2950")
	if err != nil {
		panic(err)
	}
	d := new(big.Int).SetBytes(dBytes)
	fmt.Printf("private key: %x\n", d)
	// private key: 42243a2e1088468b5fca38e1c696633348846b2c0794c44cd8ed05953c7f2950
	pX, pY := curve.ScalarBaseMult(d.Bytes())
	fmt.Printf("isOnCurve: %v\n", curve.IsOnCurve(pX, pY))
	// isOnCurve: true
	fmt.Printf("public key: %x\n", curve.Marshal(pX, pY))
	// public key: 0480840c35efafb8d5fc5c2edcf41b276bdf80ac888d51cc71c8eb4795488275e6b3ab36e01e8cb8e78842d675ac111833eb9f00bd29472c28fae256f1912e38b5
	r, s, _ := sign("奶爸", d)
	fmt.Printf("signature: %x\n", serializeSignatureToDERFormat(r, s))
	// signature: 304402200a1448bacf06a3a00581fcb1325b2c31a594731af53f1bb45d6fee37a9af700f022062d579453bd4bbf308786afdba6d0d86ff58ab12c541cfed617d6d82e27351d9
	fmt.Printf("verified: %v\n", verify("奶爸", r, s, point.Point{X: pX, Y: pY}))
}

func sign(msg string, privateKey *big.Int) (*big.Int, *big.Int, *big.Int) {
	// random K
	k, err := rand.Int(rand.Reader, math.MaxBig256)
	if err != nil {
		panic(err)
	}
	// msgHash = sha256(msg)
	h := sha256.Sum256([]byte(msg))
	msgHash := new(big.Int).SetBytes(h[:])
	// R = k*G
	Rx, _ := curve.ScalarBaseMult(k.Bytes())
	// r = Rx
	r := Rx
	// s = K^-1 * (msgHash + r*d) mod N
	rd := new(big.Int).Mul(privateKey, r)
	s := new(big.Int).Mod(new(big.Int).Mul(new(big.Int).Add(msgHash, rd), new(big.Int).ModInverse(k, N)), N)
	return r, s, k
}

func verify(msg string, r, s *big.Int, publicKey point.Point) bool {
	// msgHash = sha256(msg)
	h := sha256.Sum256([]byte(msg))
	msgHash := new(big.Int).SetBytes(h[:])
	// s1 = s^-1
	s1 := new(big.Int).ModInverse(s, N)
	// R' = (msgHash*s1)*G + (r*s1)*publicKey
	hs1 := new(big.Int).Mul(msgHash, s1)
	rs1 := new(big.Int).Mul(r, s1)
	hs1G := cmath.Multiply(point.Point{
		X: G.x,
		Y: G.y,
	}, hs1, N, A, P)
	rs1Q := cmath.Multiply(publicKey, rs1, N, A, P)
	R1 := cmath.Add(hs1G, rs1Q, A, P)
	// r' = R'.x
	r1 := R1.X
	// check r' = r
	return new(big.Int).Mod(r1, curve.N).Cmp(r) == 0
}

func serializeSignatureToDERFormat(r, s *big.Int) []byte {
	rb := r.Bytes()
	s1 := append([]byte{0x02}, byte(len(rb)))
	s1 = append(s1, rb...)

	sb := s.Bytes()
	s2 := append(s1, []byte{0x02, byte(len(sb))}...)
	s2 = append(s2, sb...)

	s3 := append([]byte{0x30}, byte(len(s2)))
	s3 = append(s3, s2...)
	return s3
}
```

## Resources

* ECDSA: Elliptic Curve Signatures - Practical Cryptography for Developers. (2023). Retrieved 10 January 2023, from [https://cryptobook.nakov.com/digital-signatures/ecdsa-sign-verify-messages](https://lifelonglearn.ing/r/go?url=aHR0cHM6Ly9jcnlwdG9ib29rLm5ha292LmNvbS9kaWdpdGFsLXNpZ25hdHVyZXMvZWNkc2Etc2lnbi12ZXJpZnktbWVzc2FnZXM=)
* GitHub - starkbank/ecdsa-go: A lightweight and fast pure Go ECDSA library. (2023). Retrieved 10 January 2023, from [https://github.com/starkbank/ecdsa-go](https://lifelonglearn.ing/r/go?url=aHR0cHM6Ly9naXRodWIuY29tL3N0YXJrYmFuay9lY2RzYS1nbw==)