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 //
  10 // SHA2-512(priv.D || entropy || hash)[:32]
  11 //
  12 // The CSPRNG key is indifferentiable from a random oracle as shown in
  13 // [Coron], the AES-CTR stream is indifferentiable from a random oracle
  14 // under standard cryptographic assumptions (see [Larsson] for examples).
  15 //
  16 // References:
  17 //   [Coron]
  18 //     https://cs.nyu.edu/~dodis/ps/merkle.pdf
  19 //   [Larsson]
  20 //     https://web.archive.org/web/20040719170906/https://www.nada.kth.se/kurser/kth/2D1441/semteo03/lecturenotes/assump.pdf
  21 package ecdsa
  22
  23 // Further references:
  24 //   [NSA]: Suite B implementer's guide to FIPS 186-3
  25 //     https://apps.nsa.gov/iaarchive/library/ia-guidance/ia-solutions-for-classified/algorithm-guidance/suite-b-implementers-guide-to-fips-186-3-ecdsa.cfm
  26 //   [SECG]: SECG, SEC1
  27 //     http://www.secg.org/sec1-v2.pdf
  28
  29 import (
  30         "crypto"
  31         "crypto/aes"
  32         "crypto/cipher"
  33         "crypto/elliptic"
  34         "crypto/internal/randutil"
  35         "crypto/sha512"
  36         "errors"
  37         "io"
  38         "math/big"
  39
  40         "golang.org/x/crypto/cryptobyte"
  41         "golang.org/x/crypto/cryptobyte/asn1"
  42 )
  43
  44 import (
  45         "crypto/internal/boring"
  46         "unsafe"
  47 )
  48
  49 // A invertible implements fast inverse mod Curve.Params().N
  50 type invertible interface {
  51         // Inverse returns the inverse of k in GF(P)
  52         Inverse(k *big.Int) *big.Int
  53 }
  54
  55 // combinedMult implements fast multiplication S1*g + S2*p (g - generator, p - arbitrary point)
  56 type combinedMult interface {
  57         CombinedMult(bigX, bigY *big.Int, baseScalar, scalar []byte) (x, y *big.Int)
  58 }
  59
  60 const (
  61         aesIV = "IV for ECDSA CTR"
  62 )
  63
  64 // PublicKey represents an ECDSA public key.
  65 type PublicKey struct {
  66         elliptic.Curve
  67         X, Y *big.Int
  68
  69         boring unsafe.Pointer
  70 }
  71
  72 // Any methods implemented on PublicKey might need to also be implemented on
  73 // PrivateKey, as the latter embeds the former and will expose its methods.
  74
  75 // Equal reports whether pub and x have the same value.
  76 //
  77 // Two keys are only considered to have the same value if they have the same Curve value.
  78 // Note that for example elliptic.P256() and elliptic.P256().Params() are different
  79 // values, as the latter is a generic not constant time implementation.
  80 func (pub *PublicKey) Equal(x crypto.PublicKey) bool {
  81         xx, ok := x.(*PublicKey)
  82         if !ok {
  83                 return false
  84         }
  85         return pub.X.Cmp(xx.X) == 0 && pub.Y.Cmp(xx.Y) == 0 &&
  86                 // Standard library Curve implementations are singletons, so this check
  87                 // will work for those. Other Curves might be equivalent even if not
  88                 // singletons, but there is no definitive way to check for that, and
  89                 // better to err on the side of safety.
  90                 pub.Curve == xx.Curve
  91 }
  92
  93 // PrivateKey represents an ECDSA private key.
  94 type PrivateKey struct {
  95         PublicKey
  96         D *big.Int
  97
  98         boring unsafe.Pointer
  99 }
 100
 101 // Public returns the public key corresponding to priv.
 102 func (priv *PrivateKey) Public() crypto.PublicKey {
 103         return &priv.PublicKey
 104 }
 105
 106 // Equal reports whether priv and x have the same value.
 107 //
 108 // See PublicKey.Equal for details on how Curve is compared.
 109 func (priv *PrivateKey) Equal(x crypto.PrivateKey) bool {
 110         xx, ok := x.(*PrivateKey)
 111         if !ok {
 112                 return false
 113         }
 114         return priv.PublicKey.Equal(&xx.PublicKey) && priv.D.Cmp(xx.D) == 0
 115 }
 116
 117 // Sign signs digest with priv, reading randomness from rand. The opts argument
 118 // is not currently used but, in keeping with the crypto.Signer interface,
 119 // should be the hash function used to digest the message.
 120 //
 121 // This method implements crypto.Signer, which is an interface to support keys
 122 // where the private part is kept in, for example, a hardware module. Common
 123 // uses should use the Sign function in this package directly.
 124 func (priv *PrivateKey) Sign(rand io.Reader, digest []byte, opts crypto.SignerOpts) ([]byte, error) {
 125         if boring.Enabled && rand == boring.RandReader {
 126                 b, err := boringPrivateKey(priv)
 127                 if err != nil {
 128                         return nil, err
 129                 }
 130                 return boring.SignMarshalECDSA(b, digest)
 131         }
 132         boring.UnreachableExceptTests()
 133
 134         r, s, err := Sign(rand, priv, digest)
 135         if err != nil {
 136                 return nil, err
 137         }
 138
 139         var b cryptobyte.Builder
 140         b.AddASN1(asn1.SEQUENCE, func(b *cryptobyte.Builder) {
 141                 b.AddASN1BigInt(r)
 142                 b.AddASN1BigInt(s)
 143         })
 144         return b.Bytes()
 145 }
 146
 147 var one = new(big.Int).SetInt64(1)
 148
 149 // randFieldElement returns a random element of the field underlying the given
 150 // curve using the procedure given in [NSA] A.2.1.
 151 func randFieldElement(c elliptic.Curve, rand io.Reader) (k *big.Int, err error) {
 152         params := c.Params()
 153         b := make([]byte, params.BitSize/8+8)
 154         _, err = io.ReadFull(rand, b)
 155         if err != nil {
 156                 return
 157         }
 158
 159         k = new(big.Int).SetBytes(b)
 160         n := new(big.Int).Sub(params.N, one)
 161         k.Mod(k, n)
 162         k.Add(k, one)
 163         return
 164 }
 165
 166 // GenerateKey generates a public and private key pair.
 167 func GenerateKey(c elliptic.Curve, rand io.Reader) (*PrivateKey, error) {
 168         if boring.Enabled && rand == boring.RandReader {
 169                 x, y, d, err := boring.GenerateKeyECDSA(c.Params().Name)
 170                 if err != nil {
 171                         return nil, err
 172                 }
 173                 return &PrivateKey{PublicKey: PublicKey{Curve: c, X: x, Y: y}, D: d}, nil
 174         }
 175         boring.UnreachableExceptTests()
 176
 177         k, err := randFieldElement(c, rand)
 178         if err != nil {
 179                 return nil, err
 180         }
 181
 182         priv := new(PrivateKey)
 183         priv.PublicKey.Curve = c
 184         priv.D = k
 185         priv.PublicKey.X, priv.PublicKey.Y = c.ScalarBaseMult(k.Bytes())
 186         return priv, nil
 187 }
 188
 189 // hashToInt converts a hash value to an integer. There is some disagreement
 190 // about how this is done. [NSA] suggests that this is done in the obvious
 191 // manner, but [SECG] truncates the hash to the bit-length of the curve order
 192 // first. We follow [SECG] because that's what OpenSSL does. Additionally,
 193 // OpenSSL right shifts excess bits from the number if the hash is too large
 194 // and we mirror that too.
 195 func hashToInt(hash []byte, c elliptic.Curve) *big.Int {
 196         orderBits := c.Params().N.BitLen()
 197         orderBytes := (orderBits + 7) / 8
 198         if len(hash) > orderBytes {
 199                 hash = hash[:orderBytes]
 200         }
 201
 202         ret := new(big.Int).SetBytes(hash)
 203         excess := len(hash)*8 - orderBits
 204         if excess > 0 {
 205                 ret.Rsh(ret, uint(excess))
 206         }
 207         return ret
 208 }
 209
 210 // fermatInverse calculates the inverse of k in GF(P) using Fermat's method.
 211 // This has better constant-time properties than Euclid's method (implemented
 212 // in math/big.Int.ModInverse) although math/big itself isn't strictly
 213 // constant-time so it's not perfect.
 214 func fermatInverse(k, N *big.Int) *big.Int {
 215         two := big.NewInt(2)
 216         nMinus2 := new(big.Int).Sub(N, two)
 217         return new(big.Int).Exp(k, nMinus2, N)
 218 }
 219
 220 var errZeroParam = errors.New("zero parameter")
 221
 222 // Sign signs a hash (which should be the result of hashing a larger message)
 223 // using the private key, priv. If the hash is longer than the bit-length of the
 224 // private key's curve order, the hash will be truncated to that length. It
 225 // returns the signature as a pair of integers. The security of the private key
 226 // depends on the entropy of rand.
 227 func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err error) {
 228         randutil.MaybeReadByte(rand)
 229
 230         if boring.Enabled && rand == boring.RandReader {
 231                 b, err := boringPrivateKey(priv)
 232                 if err != nil {
 233                         return nil, nil, err
 234                 }
 235                 return boring.SignECDSA(b, hash)
 236         }
 237         boring.UnreachableExceptTests()
 238
 239         // Get 256 bits of entropy from rand.
 240         entropy := make([]byte, 32)
 241         _, err = io.ReadFull(rand, entropy)
 242         if err != nil {
 243                 return
 244         }
 245
 246         // Initialize an SHA-512 hash context; digest ...
 247         md := sha512.New()
 248         md.Write(priv.D.Bytes()) // the private key,
 249         md.Write(entropy)        // the entropy,
 250         md.Write(hash)           // and the input hash;
 251         key := md.Sum(nil)[:32]  // and compute ChopMD-256(SHA-512),
 252         // which is an indifferentiable MAC.
 253
 254         // Create an AES-CTR instance to use as a CSPRNG.
 255         block, err := aes.NewCipher(key)
 256         if err != nil {
 257                 return nil, nil, err
 258         }
 259
 260         // Create a CSPRNG that xors a stream of zeros with
 261         // the output of the AES-CTR instance.
 262         csprng := cipher.StreamReader{
 263                 R: zeroReader,
 264                 S: cipher.NewCTR(block, []byte(aesIV)),
 265         }
 266
 267         // See [NSA] 3.4.1
 268         c := priv.PublicKey.Curve
 269         return sign(priv, &csprng, c, hash)
 270 }
 271
 272 func signGeneric(priv *PrivateKey, csprng *cipher.StreamReader, c elliptic.Curve, hash []byte) (r, s *big.Int, err error) {
 273         N := c.Params().N
 274         if N.Sign() == 0 {
 275                 return nil, nil, errZeroParam
 276         }
 277         var k, kInv *big.Int
 278         for {
 279                 for {
 280                         k, err = randFieldElement(c, *csprng)
 281                         if err != nil {
 282                                 r = nil
 283                                 return
 284                         }
 285
 286                         if in, ok := priv.Curve.(invertible); ok {
 287                                 kInv = in.Inverse(k)
 288                         } else {
 289                                 kInv = fermatInverse(k, N) // N != 0
 290                         }
 291
 292                         r, _ = priv.Curve.ScalarBaseMult(k.Bytes())
 293                         r.Mod(r, N)
 294                         if r.Sign() != 0 {
 295                                 break
 296                         }
 297                 }
 298
 299                 e := hashToInt(hash, c)
 300                 s = new(big.Int).Mul(priv.D, r)
 301                 s.Add(s, e)
 302                 s.Mul(s, kInv)
 303                 s.Mod(s, N) // N != 0
 304                 if s.Sign() != 0 {
 305                         break
 306                 }
 307         }
 308
 309         return
 310 }
 311
 312 // SignASN1 signs a hash (which should be the result of hashing a larger message)
 313 // using the private key, priv. If the hash is longer than the bit-length of the
 314 // private key's curve order, the hash will be truncated to that length. It
 315 // returns the ASN.1 encoded signature. The security of the private key
 316 // depends on the entropy of rand.
 317 func SignASN1(rand io.Reader, priv *PrivateKey, hash []byte) ([]byte, error) {
 318         return priv.Sign(rand, hash, nil)
 319 }
 320
 321 // Verify verifies the signature in r, s of hash using the public key, pub. Its
 322 // return value records whether the signature is valid.
 323 func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool {
 324         if boring.Enabled {
 325                 b, err := boringPublicKey(pub)
 326                 if err != nil {
 327                         return false
 328                 }
 329                 return boring.VerifyECDSA(b, hash, r, s)
 330         }
 331         boring.UnreachableExceptTests()
 332
 333         // See [NSA] 3.4.2
 334         c := pub.Curve
 335         N := c.Params().N
 336
 337         if r.Sign() <= 0 || s.Sign() <= 0 {
 338                 return false
 339         }
 340         if r.Cmp(N) >= 0 || s.Cmp(N) >= 0 {
 341                 return false
 342         }
 343         return verify(pub, c, hash, r, s)
 344 }
 345
 346 func verifyGeneric(pub *PublicKey, c elliptic.Curve, hash []byte, r, s *big.Int) bool {
 347         e := hashToInt(hash, c)
 348         var w *big.Int
 349         N := c.Params().N
 350         if in, ok := c.(invertible); ok {
 351                 w = in.Inverse(s)
 352         } else {
 353                 w = new(big.Int).ModInverse(s, N)
 354         }
 355
 356         u1 := e.Mul(e, w)
 357         u1.Mod(u1, N)
 358         u2 := w.Mul(r, w)
 359         u2.Mod(u2, N)
 360
 361         // Check if implements S1*g + S2*p
 362         var x, y *big.Int
 363         if opt, ok := c.(combinedMult); ok {
 364                 x, y = opt.CombinedMult(pub.X, pub.Y, u1.Bytes(), u2.Bytes())
 365         } else {
 366                 x1, y1 := c.ScalarBaseMult(u1.Bytes())
 367                 x2, y2 := c.ScalarMult(pub.X, pub.Y, u2.Bytes())
 368                 x, y = c.Add(x1, y1, x2, y2)
 369         }
 370
 371         if x.Sign() == 0 && y.Sign() == 0 {
 372                 return false
 373         }
 374         x.Mod(x, N)
 375         return x.Cmp(r) == 0
 376 }
 377
 378 // VerifyASN1 verifies the ASN.1 encoded signature, sig, of hash using the
 379 // public key, pub. Its return value records whether the signature is valid.
 380 func VerifyASN1(pub *PublicKey, hash, sig []byte) bool {
 381         var (
 382                 r, s  = &big.Int{}, &big.Int{}
 383                 inner cryptobyte.String
 384         )
 385         input := cryptobyte.String(sig)
 386         if !input.ReadASN1(&inner, asn1.SEQUENCE) ||
 387                 !input.Empty() ||
 388                 !inner.ReadASN1Integer(r) ||
 389                 !inner.ReadASN1Integer(s) ||
 390                 !inner.Empty() {
 391                 return false
 392         }
 393         return Verify(pub, hash, r, s)
 394 }
 395
 396 type zr struct {
 397         io.Reader
 398 }
 399
 400 // Read replaces the contents of dst with zeros.
 401 func (z *zr) Read(dst []byte) (n int, err error) {
 402         for i := range dst {
 403                 dst[i] = 0
 404         }
 405         return len(dst), nil
 406 }
 407
 408 var zeroReader = &zr{}