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

View as plain text