libgo/go/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 package ecdsa
   8
   9 // References:
  10 //   [NSA]: Suite B implementer's guide to FIPS 186-3,
  11 //     http://www.nsa.gov/ia/_files/ecdsa.pdf
  12 //   [SECG]: SECG, SEC1
  13 //     http://www.secg.org/download/aid-780/sec1-v2.pdf
  14
  15 import (
  16         "crypto/elliptic"
  17         "io"
  18         "math/big"
  19 )
  20
  21 // PublicKey represents an ECDSA public key.
  22 type PublicKey struct {
  23         elliptic.Curve
  24         X, Y *big.Int
  25 }
  26
  27 // PrivateKey represents a ECDSA private key.
  28 type PrivateKey struct {
  29         PublicKey
  30         D *big.Int
  31 }
  32
  33 var one = new(big.Int).SetInt64(1)
  34
  35 // randFieldElement returns a random element of the field underlying the given
  36 // curve using the procedure given in [NSA] A.2.1.
  37 func randFieldElement(c elliptic.Curve, rand io.Reader) (k *big.Int, err error) {
  38         params := c.Params()
  39         b := make([]byte, params.BitSize/8+8)
  40         _, err = io.ReadFull(rand, b)
  41         if err != nil {
  42                 return
  43         }
  44
  45         k = new(big.Int).SetBytes(b)
  46         n := new(big.Int).Sub(params.N, one)
  47         k.Mod(k, n)
  48         k.Add(k, one)
  49         return
  50 }
  51
  52 // GenerateKey generates a public&private key pair.
  53 func GenerateKey(c elliptic.Curve, rand io.Reader) (priv *PrivateKey, err error) {
  54         k, err := randFieldElement(c, rand)
  55         if err != nil {
  56                 return
  57         }
  58
  59         priv = new(PrivateKey)
  60         priv.PublicKey.Curve = c
  61         priv.D = k
  62         priv.PublicKey.X, priv.PublicKey.Y = c.ScalarBaseMult(k.Bytes())
  63         return
  64 }
  65
  66 // hashToInt converts a hash value to an integer. There is some disagreement
  67 // about how this is done. [NSA] suggests that this is done in the obvious
  68 // manner, but [SECG] truncates the hash to the bit-length of the curve order
  69 // first. We follow [SECG] because that's what OpenSSL does. Additionally,
  70 // OpenSSL right shifts excess bits from the number if the hash is too large
  71 // and we mirror that too.
  72 func hashToInt(hash []byte, c elliptic.Curve) *big.Int {
  73         orderBits := c.Params().N.BitLen()
  74         orderBytes := (orderBits + 7) / 8
  75         if len(hash) > orderBytes {
  76                 hash = hash[:orderBytes]
  77         }
  78
  79         ret := new(big.Int).SetBytes(hash)
  80         excess := len(hash)*8 - orderBits
  81         if excess > 0 {
  82                 ret.Rsh(ret, uint(excess))
  83         }
  84         return ret
  85 }
  86
  87 // Sign signs an arbitrary length hash (which should be the result of hashing a
  88 // larger message) using the private key, priv. It returns the signature as a
  89 // pair of integers. The security of the private key depends on the entropy of
  90 // rand.
  91 func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err error) {
  92         // See [NSA] 3.4.1
  93         c := priv.PublicKey.Curve
  94         N := c.Params().N
  95
  96         var k, kInv *big.Int
  97         for {
  98                 for {
  99                         k, err = randFieldElement(c, rand)
 100                         if err != nil {
 101                                 r = nil
 102                                 return
 103                         }
 104
 105                         kInv = new(big.Int).ModInverse(k, N)
 106                         r, _ = priv.Curve.ScalarBaseMult(k.Bytes())
 107                         r.Mod(r, N)
 108                         if r.Sign() != 0 {
 109                                 break
 110                         }
 111                 }
 112
 113                 e := hashToInt(hash, c)
 114                 s = new(big.Int).Mul(priv.D, r)
 115                 s.Add(s, e)
 116                 s.Mul(s, kInv)
 117                 s.Mod(s, N)
 118                 if s.Sign() != 0 {
 119                         break
 120                 }
 121         }
 122
 123         return
 124 }
 125
 126 // Verify verifies the signature in r, s of hash using the public key, pub. It
 127 // returns true iff the signature is valid.
 128 func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool {
 129         // See [NSA] 3.4.2
 130         c := pub.Curve
 131         N := c.Params().N
 132
 133         if r.Sign() == 0 || s.Sign() == 0 {
 134                 return false
 135         }
 136         if r.Cmp(N) >= 0 || s.Cmp(N) >= 0 {
 137                 return false
 138         }
 139         e := hashToInt(hash, c)
 140         w := new(big.Int).ModInverse(s, N)
 141
 142         u1 := e.Mul(e, w)
 143         u1.Mod(u1, N)
 144         u2 := w.Mul(r, w)
 145         u2.Mod(u2, N)
 146
 147         x1, y1 := c.ScalarBaseMult(u1.Bytes())
 148         x2, y2 := c.ScalarMult(pub.X, pub.Y, u2.Bytes())
 149         x, y := c.Add(x1, y1, x2, y2)
 150         if x.Sign() == 0 && y.Sign() == 0 {
 151                 return false
 152         }
 153         x.Mod(x, N)
 154         return x.Cmp(r) == 0
 155 }