...
Run Format

Source file src/crypto/ecdsa/ecdsa.go

     1	// Copyright 2011 The Go Authors. All rights reserved.
     2	// Use of this source code is governed by a BSD-style
     3	// license that can be found in the LICENSE file.
     4	
     5	// Package ecdsa implements the Elliptic Curve Digital Signature Algorithm, as
     6	// defined in FIPS 186-3.
     7	//
     8	// This implementation  derives the nonce from an AES-CTR CSPRNG keyed by
     9	// ChopMD(256, SHA2-512(priv.D || entropy || hash)). The CSPRNG key is IRO by
    10	// a result of Coron; the AES-CTR stream is IRO under standard assumptions.
    11	package ecdsa
    12	
    13	// References:
    14	//   [NSA]: Suite B implementer's guide to FIPS 186-3,
    15	//     http://www.nsa.gov/ia/_files/ecdsa.pdf
    16	//   [SECG]: SECG, SEC1
    17	//     http://www.secg.org/sec1-v2.pdf
    18	
    19	import (
    20		"crypto"
    21		"crypto/aes"
    22		"crypto/cipher"
    23		"crypto/elliptic"
    24		"crypto/sha512"
    25		"encoding/asn1"
    26		"errors"
    27		"io"
    28		"math/big"
    29	)
    30	
    31	// A invertible implements fast inverse mod Curve.Params().N
    32	type invertible interface {
    33		// Inverse returns the inverse of k in GF(P)
    34		Inverse(k *big.Int) *big.Int
    35	}
    36	
    37	// combinedMult implements fast multiplication S1*g + S2*p (g - generator, p - arbitrary point)
    38	type combinedMult interface {
    39		CombinedMult(bigX, bigY *big.Int, baseScalar, scalar []byte) (x, y *big.Int)
    40	}
    41	
    42	const (
    43		aesIV = "IV for ECDSA CTR"
    44	)
    45	
    46	// PublicKey represents an ECDSA public key.
    47	type PublicKey struct {
    48		elliptic.Curve
    49		X, Y *big.Int
    50	}
    51	
    52	// PrivateKey represents a ECDSA private key.
    53	type PrivateKey struct {
    54		PublicKey
    55		D *big.Int
    56	}
    57	
    58	type ecdsaSignature struct {
    59		R, S *big.Int
    60	}
    61	
    62	// Public returns the public key corresponding to priv.
    63	func (priv *PrivateKey) Public() crypto.PublicKey {
    64		return &priv.PublicKey
    65	}
    66	
    67	// Sign signs msg with priv, reading randomness from rand. This method is
    68	// intended to support keys where the private part is kept in, for example, a
    69	// hardware module. Common uses should use the Sign function in this package
    70	// directly.
    71	func (priv *PrivateKey) Sign(rand io.Reader, msg []byte, opts crypto.SignerOpts) ([]byte, error) {
    72		r, s, err := Sign(rand, priv, msg)
    73		if err != nil {
    74			return nil, err
    75		}
    76	
    77		return asn1.Marshal(ecdsaSignature{r, s})
    78	}
    79	
    80	var one = new(big.Int).SetInt64(1)
    81	
    82	// randFieldElement returns a random element of the field underlying the given
    83	// curve using the procedure given in [NSA] A.2.1.
    84	func randFieldElement(c elliptic.Curve, rand io.Reader) (k *big.Int, err error) {
    85		params := c.Params()
    86		b := make([]byte, params.BitSize/8+8)
    87		_, err = io.ReadFull(rand, b)
    88		if err != nil {
    89			return
    90		}
    91	
    92		k = new(big.Int).SetBytes(b)
    93		n := new(big.Int).Sub(params.N, one)
    94		k.Mod(k, n)
    95		k.Add(k, one)
    96		return
    97	}
    98	
    99	// GenerateKey generates a public and private key pair.
   100	func GenerateKey(c elliptic.Curve, rand io.Reader) (*PrivateKey, error) {
   101		k, err := randFieldElement(c, rand)
   102		if err != nil {
   103			return nil, err
   104		}
   105	
   106		priv := new(PrivateKey)
   107		priv.PublicKey.Curve = c
   108		priv.D = k
   109		priv.PublicKey.X, priv.PublicKey.Y = c.ScalarBaseMult(k.Bytes())
   110		return priv, nil
   111	}
   112	
   113	// hashToInt converts a hash value to an integer. There is some disagreement
   114	// about how this is done. [NSA] suggests that this is done in the obvious
   115	// manner, but [SECG] truncates the hash to the bit-length of the curve order
   116	// first. We follow [SECG] because that's what OpenSSL does. Additionally,
   117	// OpenSSL right shifts excess bits from the number if the hash is too large
   118	// and we mirror that too.
   119	func hashToInt(hash []byte, c elliptic.Curve) *big.Int {
   120		orderBits := c.Params().N.BitLen()
   121		orderBytes := (orderBits + 7) / 8
   122		if len(hash) > orderBytes {
   123			hash = hash[:orderBytes]
   124		}
   125	
   126		ret := new(big.Int).SetBytes(hash)
   127		excess := len(hash)*8 - orderBits
   128		if excess > 0 {
   129			ret.Rsh(ret, uint(excess))
   130		}
   131		return ret
   132	}
   133	
   134	// fermatInverse calculates the inverse of k in GF(P) using Fermat's method.
   135	// This has better constant-time properties than Euclid's method (implemented
   136	// in math/big.Int.ModInverse) although math/big itself isn't strictly
   137	// constant-time so it's not perfect.
   138	func fermatInverse(k, N *big.Int) *big.Int {
   139		two := big.NewInt(2)
   140		nMinus2 := new(big.Int).Sub(N, two)
   141		return new(big.Int).Exp(k, nMinus2, N)
   142	}
   143	
   144	var errZeroParam = errors.New("zero parameter")
   145	
   146	// Sign signs a hash (which should be the result of hashing a larger message)
   147	// using the private key, priv. If the hash is longer than the bit-length of the
   148	// private key's curve order, the hash will be truncated to that length.  It
   149	// returns the signature as a pair of integers. The security of the private key
   150	// depends on the entropy of rand.
   151	func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err error) {
   152		// Get min(log2(q) / 2, 256) bits of entropy from rand.
   153		entropylen := (priv.Curve.Params().BitSize + 7) / 16
   154		if entropylen > 32 {
   155			entropylen = 32
   156		}
   157		entropy := make([]byte, entropylen)
   158		_, err = io.ReadFull(rand, entropy)
   159		if err != nil {
   160			return
   161		}
   162	
   163		// Initialize an SHA-512 hash context; digest ...
   164		md := sha512.New()
   165		md.Write(priv.D.Bytes()) // the private key,
   166		md.Write(entropy)        // the entropy,
   167		md.Write(hash)           // and the input hash;
   168		key := md.Sum(nil)[:32]  // and compute ChopMD-256(SHA-512),
   169		// which is an indifferentiable MAC.
   170	
   171		// Create an AES-CTR instance to use as a CSPRNG.
   172		block, err := aes.NewCipher(key)
   173		if err != nil {
   174			return nil, nil, err
   175		}
   176	
   177		// Create a CSPRNG that xors a stream of zeros with
   178		// the output of the AES-CTR instance.
   179		csprng := cipher.StreamReader{
   180			R: zeroReader,
   181			S: cipher.NewCTR(block, []byte(aesIV)),
   182		}
   183	
   184		// See [NSA] 3.4.1
   185		c := priv.PublicKey.Curve
   186		N := c.Params().N
   187		if N.Sign() == 0 {
   188			return nil, nil, errZeroParam
   189		}
   190		var k, kInv *big.Int
   191		for {
   192			for {
   193				k, err = randFieldElement(c, csprng)
   194				if err != nil {
   195					r = nil
   196					return
   197				}
   198	
   199				if in, ok := priv.Curve.(invertible); ok {
   200					kInv = in.Inverse(k)
   201				} else {
   202					kInv = fermatInverse(k, N) // N != 0
   203				}
   204	
   205				r, _ = priv.Curve.ScalarBaseMult(k.Bytes())
   206				r.Mod(r, N)
   207				if r.Sign() != 0 {
   208					break
   209				}
   210			}
   211	
   212			e := hashToInt(hash, c)
   213			s = new(big.Int).Mul(priv.D, r)
   214			s.Add(s, e)
   215			s.Mul(s, kInv)
   216			s.Mod(s, N) // N != 0
   217			if s.Sign() != 0 {
   218				break
   219			}
   220		}
   221	
   222		return
   223	}
   224	
   225	// Verify verifies the signature in r, s of hash using the public key, pub. Its
   226	// return value records whether the signature is valid.
   227	func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool {
   228		// See [NSA] 3.4.2
   229		c := pub.Curve
   230		N := c.Params().N
   231	
   232		if r.Sign() <= 0 || s.Sign() <= 0 {
   233			return false
   234		}
   235		if r.Cmp(N) >= 0 || s.Cmp(N) >= 0 {
   236			return false
   237		}
   238		e := hashToInt(hash, c)
   239	
   240		var w *big.Int
   241		if in, ok := c.(invertible); ok {
   242			w = in.Inverse(s)
   243		} else {
   244			w = new(big.Int).ModInverse(s, N)
   245		}
   246	
   247		u1 := e.Mul(e, w)
   248		u1.Mod(u1, N)
   249		u2 := w.Mul(r, w)
   250		u2.Mod(u2, N)
   251	
   252		// Check if implements S1*g + S2*p
   253		var x, y *big.Int
   254		if opt, ok := c.(combinedMult); ok {
   255			x, y = opt.CombinedMult(pub.X, pub.Y, u1.Bytes(), u2.Bytes())
   256		} else {
   257			x1, y1 := c.ScalarBaseMult(u1.Bytes())
   258			x2, y2 := c.ScalarMult(pub.X, pub.Y, u2.Bytes())
   259			x, y = c.Add(x1, y1, x2, y2)
   260		}
   261	
   262		if x.Sign() == 0 && y.Sign() == 0 {
   263			return false
   264		}
   265		x.Mod(x, N)
   266		return x.Cmp(r) == 0
   267	}
   268	
   269	type zr struct {
   270		io.Reader
   271	}
   272	
   273	// Read replaces the contents of dst with zeros.
   274	func (z *zr) Read(dst []byte) (n int, err error) {
   275		for i := range dst {
   276			dst[i] = 0
   277		}
   278		return len(dst), nil
   279	}
   280	
   281	var zeroReader = &zr{}
   282	

View as plain text