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 implementor'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         "big"
  17         "crypto/elliptic"
  18         "io"
  19         "os"
  20 )
  21
  22 // PublicKey represents an ECDSA public key.
  23 type PublicKey struct {
  24         *elliptic.Curve
  25         X, Y *big.Int
  26 }
  27
  28 // PrivateKey represents a ECDSA private key.
  29 type PrivateKey struct {
  30         PublicKey
  31         D *big.Int
  32 }
  33
  34 var one = new(big.Int).SetInt64(1)
  35
  36 // randFieldElement returns a random element of the field underlying the given
  37 // curve using the procedure given in [NSA] A.2.1.
  38 func randFieldElement(c *elliptic.Curve, rand io.Reader) (k *big.Int, err os.Error) {
  39         b := make([]byte, c.BitSize/8+8)
  40         _, err = rand.Read(b)
  41         if err != nil {
  42                 return
  43         }
  44
  45         k = new(big.Int).SetBytes(b)
  46         n := new(big.Int).Sub(c.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 os.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.
  70 func hashToInt(hash []byte, c *elliptic.Curve) *big.Int {
  71         orderBits := c.N.BitLen()
  72         orderBytes := (orderBits + 7) / 8
  73         if len(hash) > orderBytes {
  74                 hash = hash[:orderBytes]
  75         }
  76
  77         ret := new(big.Int).SetBytes(hash)
  78         excess := orderBytes*8 - orderBits
  79         if excess > 0 {
  80                 ret.Rsh(ret, uint(excess))
  81         }
  82         return ret
  83 }
  84
  85 // Sign signs an arbitrary length hash (which should be the result of hashing a
  86 // larger message) using the private key, priv. It returns the signature as a
  87 // pair of integers. The security of the private key depends on the entropy of
  88 // rand.
  89 func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err os.Error) {
  90         // See [NSA] 3.4.1
  91         c := priv.PublicKey.Curve
  92
  93         var k, kInv *big.Int
  94         for {
  95                 for {
  96                         k, err = randFieldElement(c, rand)
  97                         if err != nil {
  98                                 r = nil
  99                                 return
 100                         }
 101
 102                         kInv = new(big.Int).ModInverse(k, c.N)
 103                         r, _ = priv.Curve.ScalarBaseMult(k.Bytes())
 104                         r.Mod(r, priv.Curve.N)
 105                         if r.Sign() != 0 {
 106                                 break
 107                         }
 108                 }
 109
 110                 e := hashToInt(hash, c)
 111                 s = new(big.Int).Mul(priv.D, r)
 112                 s.Add(s, e)
 113                 s.Mul(s, kInv)
 114                 s.Mod(s, priv.PublicKey.Curve.N)
 115                 if s.Sign() != 0 {
 116                         break
 117                 }
 118         }
 119
 120         return
 121 }
 122
 123 // Verify verifies the signature in r, s of hash using the public key, pub. It
 124 // returns true iff the signature is valid.
 125 func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool {
 126         // See [NSA] 3.4.2
 127         c := pub.Curve
 128
 129         if r.Sign() == 0 || s.Sign() == 0 {
 130                 return false
 131         }
 132         if r.Cmp(c.N) >= 0 || s.Cmp(c.N) >= 0 {
 133                 return false
 134         }
 135         e := hashToInt(hash, c)
 136         w := new(big.Int).ModInverse(s, c.N)
 137
 138         u1 := e.Mul(e, w)
 139         u2 := w.Mul(r, w)
 140
 141         x1, y1 := c.ScalarBaseMult(u1.Bytes())
 142         x2, y2 := c.ScalarMult(pub.X, pub.Y, u2.Bytes())
 143         if x1.Cmp(x2) == 0 {
 144                 return false
 145         }
 146         x, _ := c.Add(x1, y1, x2, y2)
 147         x.Mod(x, c.N)
 148         return x.Cmp(r) == 0
 149 }