ECDSA keygen & sign 链的本源

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

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

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

  1. 打开 「这篇文章」跟着文章的步伐一步一步生成 keypair 然后签名。里面包含一个完整的 Ruby 实现,因为奶爸对 Go 更熟悉,我们就用 Go 来重新实现一下吧。

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

    package main
    
    import (
    	"crypto/rand"
    	"fmt"
    	"math/big"
    
    	"github.com/ethereum/go-ethereum/crypto/secp256k1"
    )
    
    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 = big.NewInt(0)
    	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,
    	}
    }
    
  3. 随机选取一个私钥 d \in [0...N-1]

    d, err := rand.Int(rand.Reader, N)
    if err != nil {
    	panic(err)
    }
    fmt.Printf("private key: %x\n", d)
    // private key: 2f06a50827d822133ada5993d5fa522743b0735f45875323cc01a88d55f3cb6d
    
  4. 推算公钥 Q = d \cdot Gd 就是我们生成的大随机数,Gsecp256k1 这条曲线选定的生成元,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: 043e4668749f476e9b00376d2b1658a4d0f68be1ffb931594d83e1a34375df0b55d434e28d9e95518394ef07e5aac832dc1c28768f2575af6807faedc94304b619
    
  5. 对消息 「奶爸」进行签名,取消息的哈希 z=sha256(奶爸),取随机数 k,得到 R = kG,然后得到 r = Rx \mod Ns = k^{-1}(z+dr) \mod N,最终签名就是 (r,s),可以使用 此工具 进行验证

    k, err := rand.Int(rand.Reader, math.MaxBig256)
    if err != nil {
    	panic(err)
    }
    // hash := sha256.New()
    // h := hash.Sum([]byte("奶爸"))
    // fmt.Printf("hash: %x\n", h)
    h, _ := hex.DecodeString("ee68b25d37a15999563122295cc0c1c9878ccaff36624f9f7ad99f5109650bbc")
    z := new(big.Int).SetBytes(h)
    Rx, _ := curve.ScalarBaseMult(k.Bytes())
    r := new(big.Int).Mod(Rx, N)
    dr := new(big.Int).Mul(d, r)
    s := new(big.Int).Mod(new(big.Int).Mul(new(big.Int).Add(z, dr), new(big.Int).ModInverse(k, N)), N)
    fmt.Printf("signature: %x\n", serializeSignatureToDERFormat(r, s))
    // signature: 30440220b47a40580e0f8c08e44d9a5306e7c50c5ac1e6bbc08dd05c1019eefe4f250165022096c9cd5ad24fd85d7eb8997b9f772d3c0834df76552bf4fea43295eafe0be525
    
  6. 完整代码

    package main
    
    import (
    	"crypto/rand"
    	"encoding/hex"
    	"fmt"
    	"math/big"
    
    	"github.com/ethereum/go-ethereum/common/math"
    	"github.com/ethereum/go-ethereum/crypto/secp256k1"
    )
    
    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)
    	if err != nil {
    		panic(err)
    	}
    	fmt.Printf("private key: %x\n", d)
    	// private key: 2f06a50827d822133ada5993d5fa522743b0735f45875323cc01a88d55f3cb6d
    
    	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: 043e4668749f476e9b00376d2b1658a4d0f68be1ffb931594d83e1a34375df0b55d434e28d9e95518394ef07e5aac832dc1c28768f2575af6807faedc94304b619
    
    	k, err := rand.Int(rand.Reader, math.MaxBig256)
    	if err != nil {
    		panic(err)
    	}
    	// hash := sha256.New()
    	// h := hash.Sum([]byte("奶爸"))
    	// fmt.Printf("hash: %x\n", h)
    	h, _ := hex.DecodeString("ee68b25d37a15999563122295cc0c1c9878ccaff36624f9f7ad99f5109650bbc")
    	z := new(big.Int).SetBytes(h)
    	Rx, _ := curve.ScalarBaseMult(k.Bytes())
    	r := new(big.Int).Mod(Rx, N)
    	dr := new(big.Int).Mul(d, r)
    	s := new(big.Int).Mod(new(big.Int).Mul(new(big.Int).Add(z, dr), new(big.Int).ModInverse(k, N)), N)
    	fmt.Printf("signature: %x\n", serializeSignatureToDERFormat(r, s))
    	// signature: 30440220b47a40580e0f8c08e44d9a5306e7c50c5ac1e6bbc08dd05c1019eefe4f250165022096c9cd5ad24fd85d7eb8997b9f772d3c0834df76552bf4fea43295eafe0be525
    }
    
    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
    }
    

Comments