Skip to content

ECDSA

Created at: Updated at: v1 · 278
Crypto

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

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

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

Keygen

  1. 首先我们定义 secp256k1 这个曲线的参数，其实 go-ethereum 中已有定义，我们手动做一下加深印象。

    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]

    // 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 的具体实现

    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)，可以使用 此工具 进行验证

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

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

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

Comments

Commenting as a guest. A nickname is required; email is optional. Only new comments posted after verifying your email and signing in will appear on your profile. Existing guest comments will not be linked automatically.

Register

Share article

ECDSA

Email X

View original ↗