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