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         "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         b := make([]byte, c.BitSize/8+8)
  39         _, err = io.ReadFull(rand, b)
  40         if err != nil {
  41                 return
  42         }
  43
  44         k = new(big.Int).SetBytes(b)
  45         n := new(big.Int).Sub(c.N, one)
  46         k.Mod(k, n)
  47         k.Add(k, one)
  48         return
  49 }
  50
  51 // GenerateKey generates a public&private key pair.
  52 func GenerateKey(c *elliptic.Curve, rand io.Reader) (priv *PrivateKey, err error) {
  53         k, err := randFieldElement(c, rand)
  54         if err != nil {
  55                 return
  56         }
  57
  58         priv = new(PrivateKey)
  59         priv.PublicKey.Curve = c
  60         priv.D = k
  61         priv.PublicKey.X, priv.PublicKey.Y = c.ScalarBaseMult(k.Bytes())
  62         return
  63 }
  64
  65 // hashToInt converts a hash value to an integer. There is some disagreement
  66 // about how this is done. [NSA] suggests that this is done in the obvious
  67 // manner, but [SECG] truncates the hash to the bit-length of the curve order
  68 // first. We follow [SECG] because that's what OpenSSL does.
  69 func hashToInt(hash []byte, c *elliptic.Curve) *big.Int {
  70         orderBits := c.N.BitLen()
  71         orderBytes := (orderBits + 7) / 8
  72         if len(hash) > orderBytes {
  73                 hash = hash[:orderBytes]
  74         }
  75
  76         ret := new(big.Int).SetBytes(hash)
  77         excess := orderBytes*8 - orderBits
  78         if excess > 0 {
  79                 ret.Rsh(ret, uint(excess))
  80         }
  81         return ret
  82 }
  83
  84 // Sign signs an arbitrary length hash (which should be the result of hashing a
  85 // larger message) using the private key, priv. It returns the signature as a
  86 // pair of integers. The security of the private key depends on the entropy of
  87 // rand.
  88 func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err error) {
  89         // See [NSA] 3.4.1
  90         c := priv.PublicKey.Curve
  91
  92         var k, kInv *big.Int
  93         for {
  94                 for {
  95                         k, err = randFieldElement(c, rand)
  96                         if err != nil {
  97                                 r = nil
  98                                 return
  99                         }
 100
 101                         kInv = new(big.Int).ModInverse(k, c.N)
 102                         r, _ = priv.Curve.ScalarBaseMult(k.Bytes())
 103                         r.Mod(r, priv.Curve.N)
 104                         if r.Sign() != 0 {
 105                                 break
 106                         }
 107                 }
 108
 109                 e := hashToInt(hash, c)
 110                 s = new(big.Int).Mul(priv.D, r)
 111                 s.Add(s, e)
 112                 s.Mul(s, kInv)
 113                 s.Mod(s, priv.PublicKey.Curve.N)
 114                 if s.Sign() != 0 {
 115                         break
 116                 }
 117         }
 118
 119         return
 120 }
 121
 122 // Verify verifies the signature in r, s of hash using the public key, pub. It
 123 // returns true iff the signature is valid.
 124 func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool {
 125         // See [NSA] 3.4.2
 126         c := pub.Curve
 127
 128         if r.Sign() == 0 || s.Sign() == 0 {
 129                 return false
 130         }
 131         if r.Cmp(c.N) >= 0 || s.Cmp(c.N) >= 0 {
 132                 return false
 133         }
 134         e := hashToInt(hash, c)
 135         w := new(big.Int).ModInverse(s, c.N)
 136
 137         u1 := e.Mul(e, w)
 138         u2 := w.Mul(r, w)
 139
 140         x1, y1 := c.ScalarBaseMult(u1.Bytes())
 141         x2, y2 := c.ScalarMult(pub.X, pub.Y, u2.Bytes())
 142         if x1.Cmp(x2) == 0 {
 143                 return false
 144         }
 145         x, _ := c.Add(x1, y1, x2, y2)
 146         x.Mod(x, c.N)
 147         return x.Cmp(r) == 0
 148 }