ECDSA

奶爸

29 Oct 2022 ·v1 | 👀232

Crypto

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

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

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

Keygen

首先我们定义 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,
	}
}

随机选取一个私钥 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

推算公钥 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

ECDSA: Elliptic Curve Signatures - Practical Cryptography for Developers. (2023). Retrieved 10 January 2023, from https://cryptobook.nakov.com/digital-signatures/ecdsa-sign-verify-messages
GitHub - starkbank/ecdsa-go: A lightweight and fast pure Go ECDSA library. (2023). Retrieved 10 January 2023, from https://github.com/starkbank/ecdsa-go

Keygen

Sign

Verify

Full code

Resources

Comments