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 //     https://apps.nsa.gov/iaarchive/library/ia-guidance/ia-solutions-for-classified/algorithm-guidance/suite-b-implementers-guide-to-fips-186-3-ecdsa.cfm
  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/internal/randutil"
  25         "crypto/sha512"
  26         "encoding/asn1"
  27         "errors"
  28         "io"
  29         "math/big"
  30 )
  31
  32 import (
  33         "crypto/internal/boring"
  34         "unsafe"
  35 )
  36
  37 // A invertible implements fast inverse mod Curve.Params().N
  38 type invertible interface {
  39         // Inverse returns the inverse of k in GF(P)
  40         Inverse(k *big.Int) *big.Int
  41 }
  42
  43 // combinedMult implements fast multiplication S1*g + S2*p (g - generator, p - arbitrary point)
  44 type combinedMult interface {
  45         CombinedMult(bigX, bigY *big.Int, baseScalar, scalar []byte) (x, y *big.Int)
  46 }
  47
  48 const (
  49         aesIV = "IV for ECDSA CTR"
  50 )
  51
  52 // PublicKey represents an ECDSA public key.
  53 type PublicKey struct {
  54         elliptic.Curve
  55         X, Y *big.Int
  56
  57         boring unsafe.Pointer
  58 }
  59
  60 // PrivateKey represents an ECDSA private key.
  61 type PrivateKey struct {
  62         PublicKey
  63         D *big.Int
  64
  65         boring unsafe.Pointer
  66 }
  67
  68 type ecdsaSignature struct {
  69         R, S *big.Int
  70 }
  71
  72 // Public returns the public key corresponding to priv.
  73 func (priv *PrivateKey) Public() crypto.PublicKey {
  74         return &priv.PublicKey
  75 }
  76
  77 // Sign signs digest with priv, reading randomness from rand. The opts argument
  78 // is not currently used but, in keeping with the crypto.Signer interface,
  79 // should be the hash function used to digest the message.
  80 //
  81 // This method implements crypto.Signer, which is an interface to support keys
  82 // where the private part is kept in, for example, a hardware module. Common
  83 // uses should use the Sign function in this package directly.
  84 func (priv *PrivateKey) Sign(rand io.Reader, digest []byte, opts crypto.SignerOpts) ([]byte, error) {
  85         if boring.Enabled && rand == boring.RandReader {
  86                 b, err := boringPrivateKey(priv)
  87                 if err != nil {
  88                         return nil, err
  89                 }
  90                 return boring.SignMarshalECDSA(b, digest)
  91         }
  92         boring.UnreachableExceptTests()
  93
  94         r, s, err := Sign(rand, priv, digest)
  95         if err != nil {
  96                 return nil, err
  97         }
  98
  99         return asn1.Marshal(ecdsaSignature{r, s})
 100 }
 101
 102 var one = new(big.Int).SetInt64(1)
 103
 104 // randFieldElement returns a random element of the field underlying the given
 105 // curve using the procedure given in [NSA] A.2.1.
 106 func randFieldElement(c elliptic.Curve, rand io.Reader) (k *big.Int, err error) {
 107         params := c.Params()
 108         b := make([]byte, params.BitSize/8+8)
 109         _, err = io.ReadFull(rand, b)
 110         if err != nil {
 111                 return
 112         }
 113
 114         k = new(big.Int).SetBytes(b)
 115         n := new(big.Int).Sub(params.N, one)
 116         k.Mod(k, n)
 117         k.Add(k, one)
 118         return
 119 }
 120
 121 // GenerateKey generates a public and private key pair.
 122 func GenerateKey(c elliptic.Curve, rand io.Reader) (*PrivateKey, error) {
 123         if boring.Enabled && rand == boring.RandReader {
 124                 x, y, d, err := boring.GenerateKeyECDSA(c.Params().Name)
 125                 if err != nil {
 126                         return nil, err
 127                 }
 128                 return &PrivateKey{PublicKey: PublicKey{Curve: c, X: x, Y: y}, D: d}, nil
 129         }
 130         boring.UnreachableExceptTests()
 131
 132         k, err := randFieldElement(c, rand)
 133         if err != nil {
 134                 return nil, err
 135         }
 136
 137         priv := new(PrivateKey)
 138         priv.PublicKey.Curve = c
 139         priv.D = k
 140         priv.PublicKey.X, priv.PublicKey.Y = c.ScalarBaseMult(k.Bytes())
 141         return priv, nil
 142 }
 143
 144 // hashToInt converts a hash value to an integer. There is some disagreement
 145 // about how this is done. [NSA] suggests that this is done in the obvious
 146 // manner, but [SECG] truncates the hash to the bit-length of the curve order
 147 // first. We follow [SECG] because that's what OpenSSL does. Additionally,
 148 // OpenSSL right shifts excess bits from the number if the hash is too large
 149 // and we mirror that too.
 150 func hashToInt(hash []byte, c elliptic.Curve) *big.Int {
 151         orderBits := c.Params().N.BitLen()
 152         orderBytes := (orderBits + 7) / 8
 153         if len(hash) > orderBytes {
 154                 hash = hash[:orderBytes]
 155         }
 156
 157         ret := new(big.Int).SetBytes(hash)
 158         excess := len(hash)*8 - orderBits
 159         if excess > 0 {
 160                 ret.Rsh(ret, uint(excess))
 161         }
 162         return ret
 163 }
 164
 165 // fermatInverse calculates the inverse of k in GF(P) using Fermat's method.
 166 // This has better constant-time properties than Euclid's method (implemented
 167 // in math/big.Int.ModInverse) although math/big itself isn't strictly
 168 // constant-time so it's not perfect.
 169 func fermatInverse(k, N *big.Int) *big.Int {
 170         two := big.NewInt(2)
 171         nMinus2 := new(big.Int).Sub(N, two)
 172         return new(big.Int).Exp(k, nMinus2, N)
 173 }
 174
 175 var errZeroParam = errors.New("zero parameter")
 176
 177 // Sign signs a hash (which should be the result of hashing a larger message)
 178 // using the private key, priv. If the hash is longer than the bit-length of the
 179 // private key's curve order, the hash will be truncated to that length.  It
 180 // returns the signature as a pair of integers. The security of the private key
 181 // depends on the entropy of rand.
 182 func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err error) {
 183         randutil.MaybeReadByte(rand)
 184
 185         if boring.Enabled && rand == boring.RandReader {
 186                 b, err := boringPrivateKey(priv)
 187                 if err != nil {
 188                         return nil, nil, err
 189                 }
 190                 return boring.SignECDSA(b, hash)
 191         }
 192         boring.UnreachableExceptTests()
 193
 194         // Get min(log2(q) / 2, 256) bits of entropy from rand.
 195         entropylen := (priv.Curve.Params().BitSize + 7) / 16
 196         if entropylen > 32 {
 197                 entropylen = 32
 198         }
 199         entropy := make([]byte, entropylen)
 200         _, err = io.ReadFull(rand, entropy)
 201         if err != nil {
 202                 return
 203         }
 204
 205         // Initialize an SHA-512 hash context; digest ...
 206         md := sha512.New()
 207         md.Write(priv.D.Bytes()) // the private key,
 208         md.Write(entropy)        // the entropy,
 209         md.Write(hash)           // and the input hash;
 210         key := md.Sum(nil)[:32]  // and compute ChopMD-256(SHA-512),
 211         // which is an indifferentiable MAC.
 212
 213         // Create an AES-CTR instance to use as a CSPRNG.
 214         block, err := aes.NewCipher(key)
 215         if err != nil {
 216                 return nil, nil, err
 217         }
 218
 219         // Create a CSPRNG that xors a stream of zeros with
 220         // the output of the AES-CTR instance.
 221         csprng := cipher.StreamReader{
 222                 R: zeroReader,
 223                 S: cipher.NewCTR(block, []byte(aesIV)),
 224         }
 225
 226         // See [NSA] 3.4.1
 227         c := priv.PublicKey.Curve
 228         e := hashToInt(hash, c)
 229         r, s, err = sign(priv, &csprng, c, e)
 230         return
 231 }
 232
 233 func signGeneric(priv *PrivateKey, csprng *cipher.StreamReader, c elliptic.Curve, e *big.Int) (r, s *big.Int, err error) {
 234         N := c.Params().N
 235         if N.Sign() == 0 {
 236                 return nil, nil, errZeroParam
 237         }
 238
 239         var k, kInv *big.Int
 240         for {
 241                 for {
 242                         k, err = randFieldElement(c, *csprng)
 243                         if err != nil {
 244                                 r = nil
 245                                 return
 246                         }
 247
 248                         if in, ok := priv.Curve.(invertible); ok {
 249                                 kInv = in.Inverse(k)
 250                         } else {
 251                                 kInv = fermatInverse(k, N) // N != 0
 252                         }
 253
 254                         r, _ = priv.Curve.ScalarBaseMult(k.Bytes())
 255                         r.Mod(r, N)
 256                         if r.Sign() != 0 {
 257                                 break
 258                         }
 259                 }
 260                 s = new(big.Int).Mul(priv.D, r)
 261                 s.Add(s, e)
 262                 s.Mul(s, kInv)
 263                 s.Mod(s, N) // N != 0
 264                 if s.Sign() != 0 {
 265                         break
 266                 }
 267         }
 268         return
 269 }
 270
 271 // Verify verifies the signature in r, s of hash using the public key, pub. Its
 272 // return value records whether the signature is valid.
 273 func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool {
 274         if boring.Enabled {
 275                 b, err := boringPublicKey(pub)
 276                 if err != nil {
 277                         return false
 278                 }
 279                 return boring.VerifyECDSA(b, hash, r, s)
 280         }
 281         boring.UnreachableExceptTests()
 282
 283         // See [NSA] 3.4.2
 284         c := pub.Curve
 285         N := c.Params().N
 286
 287         if r.Sign() <= 0 || s.Sign() <= 0 {
 288                 return false
 289         }
 290         if r.Cmp(N) >= 0 || s.Cmp(N) >= 0 {
 291                 return false
 292         }
 293         e := hashToInt(hash, c)
 294         return verify(pub, c, e, r, s)
 295 }
 296
 297 func verifyGeneric(pub *PublicKey, c elliptic.Curve, e, r, s *big.Int) bool {
 298         var w *big.Int
 299         N := c.Params().N
 300         if in, ok := c.(invertible); ok {
 301                 w = in.Inverse(s)
 302         } else {
 303                 w = new(big.Int).ModInverse(s, N)
 304         }
 305
 306         u1 := e.Mul(e, w)
 307         u1.Mod(u1, N)
 308         u2 := w.Mul(r, w)
 309         u2.Mod(u2, N)
 310
 311         // Check if implements S1*g + S2*p
 312         var x, y *big.Int
 313         if opt, ok := c.(combinedMult); ok {
 314                 x, y = opt.CombinedMult(pub.X, pub.Y, u1.Bytes(), u2.Bytes())
 315         } else {
 316                 x1, y1 := c.ScalarBaseMult(u1.Bytes())
 317                 x2, y2 := c.ScalarMult(pub.X, pub.Y, u2.Bytes())
 318                 x, y = c.Add(x1, y1, x2, y2)
 319         }
 320
 321         if x.Sign() == 0 && y.Sign() == 0 {
 322                 return false
 323         }
 324         x.Mod(x, N)
 325         return x.Cmp(r) == 0
 326 }
 327
 328 type zr struct {
 329         io.Reader
 330 }
 331
 332 // Read replaces the contents of dst with zeros.
 333 func (z *zr) Read(dst []byte) (n int, err error) {
 334         for i := range dst {
 335                 dst[i] = 0
 336         }
 337         return len(dst), nil
 338 }
 339
 340 var zeroReader = &zr{}