Source file src/crypto/elliptic/elliptic.go

     1  // Copyright 2010 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 elliptic implements the standard NIST P-224, P-256, P-384, and P-521
     6  // elliptic curves over prime fields.
     7  //
     8  // Direct use of this package is deprecated, beyond the [P224], [P256], [P384],
     9  // and [P521] values necessary to use [crypto/ecdsa]. Most other uses
    10  // should migrate to the more efficient and safer [crypto/ecdh], or to
    11  // third-party modules for lower-level functionality.
    12  package elliptic
    13  
    14  import (
    15  	"io"
    16  	"math/big"
    17  	"sync"
    18  )
    19  
    20  // A Curve represents a short-form Weierstrass curve with a=-3.
    21  //
    22  // The behavior of Add, Double, and ScalarMult when the input is not a point on
    23  // the curve is undefined.
    24  //
    25  // Note that the conventional point at infinity (0, 0) is not considered on the
    26  // curve, although it can be returned by Add, Double, ScalarMult, or
    27  // ScalarBaseMult (but not the [Unmarshal] or [UnmarshalCompressed] functions).
    28  //
    29  // Using Curve implementations besides those returned by [P224], [P256], [P384],
    30  // and [P521] is deprecated.
    31  type Curve interface {
    32  	// Params returns the parameters for the curve.
    33  	Params() *CurveParams
    34  
    35  	// IsOnCurve reports whether the given (x,y) lies on the curve.
    36  	//
    37  	// Deprecated: this is a low-level unsafe API. For ECDH, use the crypto/ecdh
    38  	// package. The NewPublicKey methods of NIST curves in crypto/ecdh accept
    39  	// the same encoding as the Unmarshal function, and perform on-curve checks.
    40  	IsOnCurve(x, y *big.Int) bool
    41  
    42  	// Add returns the sum of (x1,y1) and (x2,y2).
    43  	//
    44  	// Deprecated: this is a low-level unsafe API.
    45  	Add(x1, y1, x2, y2 *big.Int) (x, y *big.Int)
    46  
    47  	// Double returns 2*(x,y).
    48  	//
    49  	// Deprecated: this is a low-level unsafe API.
    50  	Double(x1, y1 *big.Int) (x, y *big.Int)
    51  
    52  	// ScalarMult returns k*(x,y) where k is an integer in big-endian form.
    53  	//
    54  	// Deprecated: this is a low-level unsafe API. For ECDH, use the crypto/ecdh
    55  	// package. Most uses of ScalarMult can be replaced by a call to the ECDH
    56  	// methods of NIST curves in crypto/ecdh.
    57  	ScalarMult(x1, y1 *big.Int, k []byte) (x, y *big.Int)
    58  
    59  	// ScalarBaseMult returns k*G, where G is the base point of the group
    60  	// and k is an integer in big-endian form.
    61  	//
    62  	// Deprecated: this is a low-level unsafe API. For ECDH, use the crypto/ecdh
    63  	// package. Most uses of ScalarBaseMult can be replaced by a call to the
    64  	// PrivateKey.PublicKey method in crypto/ecdh.
    65  	ScalarBaseMult(k []byte) (x, y *big.Int)
    66  }
    67  
    68  var mask = []byte{0xff, 0x1, 0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f}
    69  
    70  // GenerateKey returns a public/private key pair. The private key is
    71  // generated using the given reader, which must return random data.
    72  //
    73  // Deprecated: for ECDH, use the GenerateKey methods of the [crypto/ecdh] package;
    74  // for ECDSA, use the GenerateKey function of the crypto/ecdsa package.
    75  func GenerateKey(curve Curve, rand io.Reader) (priv []byte, x, y *big.Int, err error) {
    76  	N := curve.Params().N
    77  	bitSize := N.BitLen()
    78  	byteLen := (bitSize + 7) / 8
    79  	priv = make([]byte, byteLen)
    80  
    81  	for x == nil {
    82  		_, err = io.ReadFull(rand, priv)
    83  		if err != nil {
    84  			return
    85  		}
    86  		// We have to mask off any excess bits in the case that the size of the
    87  		// underlying field is not a whole number of bytes.
    88  		priv[0] &= mask[bitSize%8]
    89  		// This is because, in tests, rand will return all zeros and we don't
    90  		// want to get the point at infinity and loop forever.
    91  		priv[1] ^= 0x42
    92  
    93  		// If the scalar is out of range, sample another random number.
    94  		if new(big.Int).SetBytes(priv).Cmp(N) >= 0 {
    95  			continue
    96  		}
    97  
    98  		x, y = curve.ScalarBaseMult(priv)
    99  	}
   100  	return
   101  }
   102  
   103  // Marshal converts a point on the curve into the uncompressed form specified in
   104  // SEC 1, Version 2.0, Section 2.3.3. If the point is not on the curve (or is
   105  // the conventional point at infinity), the behavior is undefined.
   106  //
   107  // Deprecated: for ECDH, use the crypto/ecdh package. This function returns an
   108  // encoding equivalent to that of PublicKey.Bytes in crypto/ecdh.
   109  func Marshal(curve Curve, x, y *big.Int) []byte {
   110  	panicIfNotOnCurve(curve, x, y)
   111  
   112  	byteLen := (curve.Params().BitSize + 7) / 8
   113  
   114  	ret := make([]byte, 1+2*byteLen)
   115  	ret[0] = 4 // uncompressed point
   116  
   117  	x.FillBytes(ret[1 : 1+byteLen])
   118  	y.FillBytes(ret[1+byteLen : 1+2*byteLen])
   119  
   120  	return ret
   121  }
   122  
   123  // MarshalCompressed converts a point on the curve into the compressed form
   124  // specified in SEC 1, Version 2.0, Section 2.3.3. If the point is not on the
   125  // curve (or is the conventional point at infinity), the behavior is undefined.
   126  func MarshalCompressed(curve Curve, x, y *big.Int) []byte {
   127  	panicIfNotOnCurve(curve, x, y)
   128  	byteLen := (curve.Params().BitSize + 7) / 8
   129  	compressed := make([]byte, 1+byteLen)
   130  	compressed[0] = byte(y.Bit(0)) | 2
   131  	x.FillBytes(compressed[1:])
   132  	return compressed
   133  }
   134  
   135  // unmarshaler is implemented by curves with their own constant-time Unmarshal.
   136  //
   137  // There isn't an equivalent interface for Marshal/MarshalCompressed because
   138  // that doesn't involve any mathematical operations, only FillBytes and Bit.
   139  type unmarshaler interface {
   140  	Unmarshal([]byte) (x, y *big.Int)
   141  	UnmarshalCompressed([]byte) (x, y *big.Int)
   142  }
   143  
   144  // Assert that the known curves implement unmarshaler.
   145  var _ = []unmarshaler{p224, p256, p384, p521}
   146  
   147  // Unmarshal converts a point, serialized by [Marshal], into an x, y pair. It is
   148  // an error if the point is not in uncompressed form, is not on the curve, or is
   149  // the point at infinity. On error, x = nil.
   150  //
   151  // Deprecated: for ECDH, use the crypto/ecdh package. This function accepts an
   152  // encoding equivalent to that of the NewPublicKey methods in crypto/ecdh.
   153  func Unmarshal(curve Curve, data []byte) (x, y *big.Int) {
   154  	if c, ok := curve.(unmarshaler); ok {
   155  		return c.Unmarshal(data)
   156  	}
   157  
   158  	byteLen := (curve.Params().BitSize + 7) / 8
   159  	if len(data) != 1+2*byteLen {
   160  		return nil, nil
   161  	}
   162  	if data[0] != 4 { // uncompressed form
   163  		return nil, nil
   164  	}
   165  	p := curve.Params().P
   166  	x = new(big.Int).SetBytes(data[1 : 1+byteLen])
   167  	y = new(big.Int).SetBytes(data[1+byteLen:])
   168  	if x.Cmp(p) >= 0 || y.Cmp(p) >= 0 {
   169  		return nil, nil
   170  	}
   171  	if !curve.IsOnCurve(x, y) {
   172  		return nil, nil
   173  	}
   174  	return
   175  }
   176  
   177  // UnmarshalCompressed converts a point, serialized by [MarshalCompressed], into
   178  // an x, y pair. It is an error if the point is not in compressed form, is not
   179  // on the curve, or is the point at infinity. On error, x = nil.
   180  func UnmarshalCompressed(curve Curve, data []byte) (x, y *big.Int) {
   181  	if c, ok := curve.(unmarshaler); ok {
   182  		return c.UnmarshalCompressed(data)
   183  	}
   184  
   185  	byteLen := (curve.Params().BitSize + 7) / 8
   186  	if len(data) != 1+byteLen {
   187  		return nil, nil
   188  	}
   189  	if data[0] != 2 && data[0] != 3 { // compressed form
   190  		return nil, nil
   191  	}
   192  	p := curve.Params().P
   193  	x = new(big.Int).SetBytes(data[1:])
   194  	if x.Cmp(p) >= 0 {
   195  		return nil, nil
   196  	}
   197  	// y² = x³ - 3x + b
   198  	y = curve.Params().polynomial(x)
   199  	y = y.ModSqrt(y, p)
   200  	if y == nil {
   201  		return nil, nil
   202  	}
   203  	if byte(y.Bit(0)) != data[0]&1 {
   204  		y.Neg(y).Mod(y, p)
   205  	}
   206  	if !curve.IsOnCurve(x, y) {
   207  		return nil, nil
   208  	}
   209  	return
   210  }
   211  
   212  func panicIfNotOnCurve(curve Curve, x, y *big.Int) {
   213  	// (0, 0) is the point at infinity by convention. It's ok to operate on it,
   214  	// although IsOnCurve is documented to return false for it. See Issue 37294.
   215  	if x.Sign() == 0 && y.Sign() == 0 {
   216  		return
   217  	}
   218  
   219  	if !curve.IsOnCurve(x, y) {
   220  		panic("crypto/elliptic: attempted operation on invalid point")
   221  	}
   222  }
   223  
   224  var initonce sync.Once
   225  
   226  func initAll() {
   227  	initP224()
   228  	initP256()
   229  	initP384()
   230  	initP521()
   231  }
   232  
   233  // P224 returns a [Curve] which implements NIST P-224 (FIPS 186-3, section D.2.2),
   234  // also known as secp224r1. The CurveParams.Name of this [Curve] is "P-224".
   235  //
   236  // Multiple invocations of this function will return the same value, so it can
   237  // be used for equality checks and switch statements.
   238  //
   239  // The cryptographic operations are implemented using constant-time algorithms.
   240  func P224() Curve {
   241  	initonce.Do(initAll)
   242  	return p224
   243  }
   244  
   245  // P256 returns a [Curve] which implements NIST P-256 (FIPS 186-3, section D.2.3),
   246  // also known as secp256r1 or prime256v1. The CurveParams.Name of this [Curve] is
   247  // "P-256".
   248  //
   249  // Multiple invocations of this function will return the same value, so it can
   250  // be used for equality checks and switch statements.
   251  //
   252  // The cryptographic operations are implemented using constant-time algorithms.
   253  func P256() Curve {
   254  	initonce.Do(initAll)
   255  	return p256
   256  }
   257  
   258  // P384 returns a [Curve] which implements NIST P-384 (FIPS 186-3, section D.2.4),
   259  // also known as secp384r1. The CurveParams.Name of this [Curve] is "P-384".
   260  //
   261  // Multiple invocations of this function will return the same value, so it can
   262  // be used for equality checks and switch statements.
   263  //
   264  // The cryptographic operations are implemented using constant-time algorithms.
   265  func P384() Curve {
   266  	initonce.Do(initAll)
   267  	return p384
   268  }
   269  
   270  // P521 returns a [Curve] which implements NIST P-521 (FIPS 186-3, section D.2.5),
   271  // also known as secp521r1. The CurveParams.Name of this [Curve] is "P-521".
   272  //
   273  // Multiple invocations of this function will return the same value, so it can
   274  // be used for equality checks and switch statements.
   275  //
   276  // The cryptographic operations are implemented using constant-time algorithms.
   277  func P521() Curve {
   278  	initonce.Do(initAll)
   279  	return p521
   280  }
   281  

View as plain text