ecc

README

secp256k1

Golang native implementation of the secp256k1 elliptic curve

Features

• Based on Golang's native crypto/ecdsa and crypto/elliptic package, no external dependency at all
• Full compatible with the secp256k1 signature in go-ethereum

Motivation

Golang's elliptic.Curve implements the short-form Weierstrass curve y² = x³ + ax + b, but only with a = -3, which are the case for NIST-recommended curves P224, P256,P384, and P521. For a general curve with a != -3, one would have to rely on external packages, which is quite an inconvenience.

For example, a very popular curve is secp256k1 with equation y² = x³ + 7, used by many crypto projects such as Bitcoin and Ethereum. In order to use it, one would usually need to import for example go-ethereum, which is a very large package with many dependencies.

This package provides a secp256k1 implementation solely based on Golang's native code. No external dependency is introduced.

How to use

Package's P256k1() method returns a elliptic.Curve that implements the secp256k1 curve, use it the same way as you would use other curves in the ecdsa package.

Or use package's SignBytes() and VerifyBytes() API that signs/verifies the signature as a byte-stream. See example below:

package anyname

import (
	"crypto/ecdsa"
	"crypto/rand"
	"crypto/sha256"
	"fmt"
	
	"github.com/dustinxie/ecc"
)

func signVerify(msg []byte) error {
	// generate secp256k1 private key
	p256k1 := ecc.P256k1()
	privKey, err := ecdsa.GenerateKey(p256k1, rand.Reader)
	if err != nil {
		// handle error
		return err
	}
	
	// sign message
	hash := sha256.Sum256(msg)
	sig, err := ecc.SignBytes(privKey, hash[:], ecc.Normal)
	if err != nil {
		return err
	}
	
	// verify message
	if !ecc.VerifyBytes(&privKey.PublicKey, hash[:], sig, ecc.Normal) {
		return fmt.Errorf("failed to verify secp256k1 signature")
	}
	return nil
}

Signing options

The package provides 2 additional signing options:

• To tackle the ECDSA signature malleability issue (see "Rationale" in here), pass the flag LowerS to signing API. This ensures the resulting s value in the signature is less than or equal to half of N (the order of the curve)

// generate 64-byte signature R || S, with s <= N/2
sig, err := ecc.SignBytes(privKey, hash, ecc.LowerS)
if err != nil {
	return err
}

if !ecc.VerifyBytes(&privKey.PublicKey, hash, sig, ecc.LowerS) {
	return fmt.Errorf("failed to verify secp256k1 signature")
}
return nil

• To return the one-byte recovery ID that can be used to recover public key from the signature, pass the flag RecID to signing API

// generate 65-byte signature R || S || V
sig, err := ecc.SignBytes(privKey, hash, ecc.RecID)
if err != nil {
	return err
}

if !ecc.VerifyBytes(&privKey.PublicKey, hash, sig, ecc.RecID) {
	return fmt.Errorf("failed to verify secp256k1 signature")
}

the resulting 65-byte signature allows you to recover public key from it:

pubKey, err := RecoverPubkey("P-256k1", hash, sig)
if err != nil {
	return err
}

if !pubKey.Equal(&privKey.PublicKey) {
	return fmt.Errorf("recovered public key not equal to signing public key")
}
return nil

The recommendation is to always enable ecc.LowerS option when signing any message. And finally, you can pass both flags to signing API:

sig, err := ecc.SignBytes(privKey, hash, ecc.LowerS | ecc.RecID)

Full Ethereum compatibility

Package also provides the following 3 API that are fully compatible with the official go-ethereum. They are actually just a wrapper of our API using proper options.

func SignEthereum(hash []byte, priv *ecdsa.PrivateKey) ([]byte, error)

func VerifyEthereum(pubkey, hash, sig []byte, isHomestead bool) bool

func RecoverEthereum(hash, sig []byte) ([]byte, error)

Documentation

Overview

Package ecdsa implements the Elliptic Curve Digital Signature Algorithm, as defined in FIPS 186-3.

This implementation derives the nonce from an AES-CTR CSPRNG keyed by:

SHA2-512(priv.D || entropy || hash)[:32]

The CSPRNG key is indifferentiable from a random oracle as shown in [Coron], the AES-CTR stream is indifferentiable from a random oracle under standard cryptographic assumptions (see [Larsson] for examples).

References:

[Coron]
  https://cs.nyu.edu/~dodis/ps/merkle.pdf
[Larsson]
  https://www.nada.kth.se/kurser/kth/2D1441/semteo03/lecturenotes/assump.pdf

Package elliptic implements several standard elliptic curves over prime fields.

Package randutil contains internal randomness utilities for various crypto packages.

Index

• Constants
• Variables
• func MarshalCompressed(curve elliptic.Curve, x, y *big.Int) []byte
• func MaybeReadByte(r io.Reader)
• func P256k1() elliptic.Curve
• func P384() elliptic.Curve
• func P521() elliptic.Curve
• func RecoverEthereum(hash, sig []byte) ([]byte, error)
• func RecoverPubkey(name string, hash, sig []byte) (*ecdsa.PublicKey, error)
• func Sign(rand io.Reader, priv *ecdsa.PrivateKey, hash []byte) (r, s *big.Int, recid byte, err error)
• func SignASN1(rand io.Reader, priv *ecdsa.PrivateKey, hash []byte) ([]byte, error)
• func SignBytes(priv *ecdsa.PrivateKey, hash []byte, flag byte) ([]byte, error)
• func SignEthereum(hash []byte, priv *ecdsa.PrivateKey) ([]byte, error)
• func UnmarshalCompressed(curve elliptic.Curve, data []byte) (x, y *big.Int)
• func Verify(pub *ecdsa.PublicKey, hash []byte, r, s *big.Int) bool
• func VerifyASN1(pub *ecdsa.PublicKey, hash, sig []byte) bool
• func VerifyBytes(pub *ecdsa.PublicKey, hash, sig []byte, flag byte) bool
• func VerifyEthereum(pubkey, hash, sig []byte, isHomestead bool) bool
• type CurveParams
  • func (curve *CurveParams) Add(x1, y1, x2, y2 *big.Int) (*big.Int, *big.Int)
  • func (curve *CurveParams) Double(x1, y1 *big.Int) (*big.Int, *big.Int)
  • func (curve *CurveParams) IsOnCurve(x, y *big.Int) bool
  • func (curve *CurveParams) Params() *elliptic.CurveParams
  • func (curve *CurveParams) ScalarBaseMult(k []byte) (*big.Int, *big.Int)
  • func (curve *CurveParams) ScalarMult(Bx, By *big.Int, k []byte) (*big.Int, *big.Int)

Constants

const (
	Normal byte = 0
	LowerS byte = 1 // return (r, s) with s <= N/2
	RecID  byte = 2 // return recovery id in addition to (r, s)
)

signing options

Variables

var (
	ErrInvalidLength = errors.New("Invalid hash or signature length")
)

errors

Functions

func MarshalCompressed

func MarshalCompressed(curve elliptic.Curve, x, y *big.Int) []byte

MarshalCompressed converts a point on the curve into the compressed form specified in section 4.3.6 of ANSI X9.62.

func MaybeReadByte

func MaybeReadByte(r io.Reader)

MaybeReadByte reads a single byte from r with ~50% probability. This is used to ensure that callers do not depend on non-guaranteed behaviour, e.g. assuming that rsa.GenerateKey is deterministic w.r.t. a given random stream.

This does not affect tests that pass a stream of fixed bytes as the random source (e.g. a zeroReader).

func P256k1

func P256k1() elliptic.Curve

P256k1 returns a Curve which implements secp256k1 (https://www.secg.org/sec2-v2.pdf, section 2.4.1), also known as secp521k1. The CurveParams.Name of this Curve is "P-256k1".

Multiple invocations of this function will return the same value, so it can be used for equality checks and switch statements.

The cryptographic operations do not use constant-time algorithms.

func P384

func P384() elliptic.Curve

P384 returns a Curve which implements NIST P-384 (FIPS 186-3, section D.2.4), also known as secp384r1. The CurveParams.Name of this Curve is "P-384".

Multiple invocations of this function will return the same value, so it can be used for equality checks and switch statements.

The cryptographic operations do not use constant-time algorithms.

func P521

func P521() elliptic.Curve

P521 returns a Curve which implements NIST P-521 (FIPS 186-3, section D.2.5), also known as secp521r1. The CurveParams.Name of this Curve is "P-521".

Multiple invocations of this function will return the same value, so it can be used for equality checks and switch statements.

The cryptographic operations do not use constant-time algorithms.

func RecoverEthereum

func RecoverEthereum(hash, sig []byte) ([]byte, error)

RecoverEthereum returns the public key of the signer

signature must be the 65-byte [R || S || V] format with recovery id as the last byte

func RecoverPubkey

func RecoverPubkey(name string, hash, sig []byte) (*ecdsa.PublicKey, error)

RecoverPubkey recovers the public key from the signature

func Sign

func Sign(rand io.Reader, priv *ecdsa.PrivateKey, hash []byte) (r, s *big.Int, recid byte, err error)

Sign signs a hash (which should be the result of hashing a larger message) using the private key, priv. If the hash is longer than the bit-length of the private key's curve order, the hash will be truncated to that length. It returns the signature as a pair of integers. The security of the private key depends on the entropy of rand.

func SignASN1

func SignASN1(rand io.Reader, priv *ecdsa.PrivateKey, hash []byte) ([]byte, error)

SignASN1 signs a hash (which should be the result of hashing a larger message) using the private key, priv. If the hash is longer than the bit-length of the private key's curve order, the hash will be truncated to that length. It returns the ASN.1 encoded signature. The security of the private key depends on the entropy of rand.

func SignBytes

func SignBytes(priv *ecdsa.PrivateKey, hash []byte, flag byte) ([]byte, error)

SignBytes returns the signature in bytes

func SignEthereum

func SignEthereum(hash []byte, priv *ecdsa.PrivateKey) ([]byte, error)

SignEthereum returns an Ethereum-compatible signature The produced signature is in the 65-byte [R || S || V] format

This function is susceptible to chosen plaintext attackes. The caller is responsible to ensure that the given hash cannot be chosen directly by an attacker. Common solution is to hash any input before calculating the signature

func UnmarshalCompressed

func UnmarshalCompressed(curve elliptic.Curve, data []byte) (x, y *big.Int)

UnmarshalCompressed converts a point, serialized by MarshalCompressed, into an x, y pair. It is an error if the point is not in compressed form or is not on the curve. On error, x = nil.

func Verify

func Verify(pub *ecdsa.PublicKey, hash []byte, r, s *big.Int) bool

Verify verifies the signature in r, s of hash using the public key, pub. Its return value records whether the signature is valid.

func VerifyASN1

func VerifyASN1(pub *ecdsa.PublicKey, hash, sig []byte) bool

VerifyASN1 verifies the ASN.1 encoded signature, sig, of hash using the public key, pub. Its return value records whether the signature is valid.

func VerifyBytes

func VerifyBytes(pub *ecdsa.PublicKey, hash, sig []byte, flag byte) bool

VerifyBytes verifies the signature in bytes

func VerifyEthereum

func VerifyEthereum(pubkey, hash, sig []byte, isHomestead bool) bool

VerifyEthereum verifies an Ethereum signature The public key is either compressed (33-byte) or uncompressed (65-byte) format, and the signature should have the 64-byte [R || S] format

ECDSA malleability issue: For an ECDSA signature (r, s, v), it can be shown that (r, N-s, v^1) is also a valid signature that can correctly recover the public key. Mathematically, this is not a problem but could cause issue where the uniqueness of signature is required for better security

Ethereum handled this issue by requiring the s value to be in the lower half of N (the order of the curve) starting the Homestead hard-fork see https://eips.ethereum.org/EIPS/eip-2 To be specific, the value of s needs to satisfy: 1 <= s <= 0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF5D576E7357A4501DDFE92F46681B20A0 signature with a higher s value will be rejected

For signature before the Homestead hard-fork, call with isHomestead = false

Types

type CurveParams

type CurveParams struct {
	elliptic.CurveParams
	A *big.Int // the linear coefficient of the curve equation
}

CurveParams contains the parameters of an elliptic curve y² = x³ + ax + b, and also provides a generic, non-constant time implementation of Curve.

func (*CurveParams) Add

func (curve *CurveParams) Add(x1, y1, x2, y2 *big.Int) (*big.Int, *big.Int)

Add adds 2 points

func (*CurveParams) Double

func (curve *CurveParams) Double(x1, y1 *big.Int) (*big.Int, *big.Int)

Double doubles the point

func (*CurveParams) IsOnCurve

func (curve *CurveParams) IsOnCurve(x, y *big.Int) bool

IsOnCurve returns whether the point (x, y) lies on the curve or not

func (*CurveParams) Params

func (curve *CurveParams) Params() *elliptic.CurveParams

Params returns the curve params

func (*CurveParams) ScalarBaseMult

func (curve *CurveParams) ScalarBaseMult(k []byte) (*big.Int, *big.Int)

ScalarBaseMult computes scalar multiplication of the base point

func (*CurveParams) ScalarMult

func (curve *CurveParams) ScalarMult(Bx, By *big.Int, k []byte) (*big.Int, *big.Int)

ScalarMult computes scalar multiplication of a given point