nistec.go

     1  // Copyright 2013 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
     6  
     7  import (
     8  	"crypto/internal/fips140/nistec"
     9  	"errors"
    10  	"math/big"
    11  )
    12  
    13  var p224 = &nistCurve[*nistec.P224Point]{
    14  	newPoint: nistec.NewP224Point,
    15  }
    16  
    17  func initP224() {
    18  	p224.params = &CurveParams{
    19  		Name:    "P-224",
    20  		BitSize: 224,
    21  		// SP 800-186, Section 3.2.1.2
    22  		P:  bigFromDecimal("26959946667150639794667015087019630673557916260026308143510066298881"),
    23  		N:  bigFromDecimal("26959946667150639794667015087019625940457807714424391721682722368061"),
    24  		B:  bigFromHex("b4050a850c04b3abf54132565044b0b7d7bfd8ba270b39432355ffb4"),
    25  		Gx: bigFromHex("b70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21"),
    26  		Gy: bigFromHex("bd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34"),
    27  	}
    28  }
    29  
    30  var p256 = &nistCurve[*nistec.P256Point]{
    31  	newPoint: nistec.NewP256Point,
    32  }
    33  
    34  func initP256() {
    35  	p256.params = &CurveParams{
    36  		Name:    "P-256",
    37  		BitSize: 256,
    38  		// SP 800-186, Section 3.2.1.3
    39  		P:  bigFromDecimal("115792089210356248762697446949407573530086143415290314195533631308867097853951"),
    40  		N:  bigFromDecimal("115792089210356248762697446949407573529996955224135760342422259061068512044369"),
    41  		B:  bigFromHex("5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b"),
    42  		Gx: bigFromHex("6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296"),
    43  		Gy: bigFromHex("4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5"),
    44  	}
    45  }
    46  
    47  var p384 = &nistCurve[*nistec.P384Point]{
    48  	newPoint: nistec.NewP384Point,
    49  }
    50  
    51  func initP384() {
    52  	p384.params = &CurveParams{
    53  		Name:    "P-384",
    54  		BitSize: 384,
    55  		// SP 800-186, Section 3.2.1.4
    56  		P: bigFromDecimal("394020061963944792122790401001436138050797392704654" +
    57  			"46667948293404245721771496870329047266088258938001861606973112319"),
    58  		N: bigFromDecimal("394020061963944792122790401001436138050797392704654" +
    59  			"46667946905279627659399113263569398956308152294913554433653942643"),
    60  		B: bigFromHex("b3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088" +
    61  			"f5013875ac656398d8a2ed19d2a85c8edd3ec2aef"),
    62  		Gx: bigFromHex("aa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741" +
    63  			"e082542a385502f25dbf55296c3a545e3872760ab7"),
    64  		Gy: bigFromHex("3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da31" +
    65  			"13b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f"),
    66  	}
    67  }
    68  
    69  var p521 = &nistCurve[*nistec.P521Point]{
    70  	newPoint: nistec.NewP521Point,
    71  }
    72  
    73  func initP521() {
    74  	p521.params = &CurveParams{
    75  		Name:    "P-521",
    76  		BitSize: 521,
    77  		// SP 800-186, Section 3.2.1.5
    78  		P: bigFromDecimal("68647976601306097149819007990813932172694353001433" +
    79  			"0540939446345918554318339765605212255964066145455497729631139148" +
    80  			"0858037121987999716643812574028291115057151"),
    81  		N: bigFromDecimal("68647976601306097149819007990813932172694353001433" +
    82  			"0540939446345918554318339765539424505774633321719753296399637136" +
    83  			"3321113864768612440380340372808892707005449"),
    84  		B: bigFromHex("0051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8" +
    85  			"b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef" +
    86  			"451fd46b503f00"),
    87  		Gx: bigFromHex("00c6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f8" +
    88  			"28af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf9" +
    89  			"7e7e31c2e5bd66"),
    90  		Gy: bigFromHex("011839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817" +
    91  			"afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088" +
    92  			"be94769fd16650"),
    93  	}
    94  }
    95  
    96  // nistCurve is a Curve implementation based on a nistec Point.
    97  //
    98  // It's a wrapper that exposes the big.Int-based Curve interface and encodes the
    99  // legacy idiosyncrasies it requires, such as invalid and infinity point
   100  // handling.
   101  //
   102  // To interact with the nistec package, points are encoded into and decoded from
   103  // properly formatted byte slices. All big.Int use is limited to this package.
   104  // Encoding and decoding is 1/1000th of the runtime of a scalar multiplication,
   105  // so the overhead is acceptable.
   106  type nistCurve[Point nistPoint[Point]] struct {
   107  	newPoint func() Point
   108  	params   *CurveParams
   109  }
   110  
   111  // nistPoint is a generic constraint for the nistec Point types.
   112  type nistPoint[T any] interface {
   113  	Bytes() []byte
   114  	SetBytes([]byte) (T, error)
   115  	Add(T, T) T
   116  	Double(T) T
   117  	ScalarMult(T, []byte) (T, error)
   118  	ScalarBaseMult([]byte) (T, error)
   119  }
   120  
   121  func (curve *nistCurve[Point]) Params() *CurveParams {
   122  	return curve.params
   123  }
   124  
   125  func (curve *nistCurve[Point]) IsOnCurve(x, y *big.Int) bool {
   126  	// IsOnCurve is documented to reject (0, 0), the conventional point at
   127  	// infinity, which however is accepted by pointFromAffine.
   128  	if x.Sign() == 0 && y.Sign() == 0 {
   129  		return false
   130  	}
   131  	_, err := curve.pointFromAffine(x, y)
   132  	return err == nil
   133  }
   134  
   135  func (curve *nistCurve[Point]) pointFromAffine(x, y *big.Int) (p Point, err error) {
   136  	// (0, 0) is by convention the point at infinity, which can't be represented
   137  	// in affine coordinates. See Issue 37294.
   138  	if x.Sign() == 0 && y.Sign() == 0 {
   139  		return curve.newPoint(), nil
   140  	}
   141  	// Reject values that would not get correctly encoded.
   142  	if x.Sign() < 0 || y.Sign() < 0 {
   143  		return p, errors.New("negative coordinate")
   144  	}
   145  	if x.BitLen() > curve.params.BitSize || y.BitLen() > curve.params.BitSize {
   146  		return p, errors.New("overflowing coordinate")
   147  	}
   148  	// Encode the coordinates and let SetBytes reject invalid points.
   149  	byteLen := (curve.params.BitSize + 7) / 8
   150  	buf := make([]byte, 1+2*byteLen)
   151  	buf[0] = 4 // uncompressed point
   152  	x.FillBytes(buf[1 : 1+byteLen])
   153  	y.FillBytes(buf[1+byteLen : 1+2*byteLen])
   154  	return curve.newPoint().SetBytes(buf)
   155  }
   156  
   157  func (curve *nistCurve[Point]) pointToAffine(p Point) (x, y *big.Int) {
   158  	out := p.Bytes()
   159  	if len(out) == 1 && out[0] == 0 {
   160  		// This is the encoding of the point at infinity, which the affine
   161  		// coordinates API represents as (0, 0) by convention.
   162  		return new(big.Int), new(big.Int)
   163  	}
   164  	byteLen := (curve.params.BitSize + 7) / 8
   165  	x = new(big.Int).SetBytes(out[1 : 1+byteLen])
   166  	y = new(big.Int).SetBytes(out[1+byteLen:])
   167  	return x, y
   168  }
   169  
   170  func (curve *nistCurve[Point]) Add(x1, y1, x2, y2 *big.Int) (*big.Int, *big.Int) {
   171  	p1, err := curve.pointFromAffine(x1, y1)
   172  	if err != nil {
   173  		panic("crypto/elliptic: Add was called on an invalid point")
   174  	}
   175  	p2, err := curve.pointFromAffine(x2, y2)
   176  	if err != nil {
   177  		panic("crypto/elliptic: Add was called on an invalid point")
   178  	}
   179  	return curve.pointToAffine(p1.Add(p1, p2))
   180  }
   181  
   182  func (curve *nistCurve[Point]) Double(x1, y1 *big.Int) (*big.Int, *big.Int) {
   183  	p, err := curve.pointFromAffine(x1, y1)
   184  	if err != nil {
   185  		panic("crypto/elliptic: Double was called on an invalid point")
   186  	}
   187  	return curve.pointToAffine(p.Double(p))
   188  }
   189  
   190  // normalizeScalar brings the scalar within the byte size of the order of the
   191  // curve, as expected by the nistec scalar multiplication functions.
   192  func (curve *nistCurve[Point]) normalizeScalar(scalar []byte) []byte {
   193  	byteSize := (curve.params.N.BitLen() + 7) / 8
   194  	if len(scalar) == byteSize {
   195  		return scalar
   196  	}
   197  	s := new(big.Int).SetBytes(scalar)
   198  	if len(scalar) > byteSize {
   199  		s.Mod(s, curve.params.N)
   200  	}
   201  	out := make([]byte, byteSize)
   202  	return s.FillBytes(out)
   203  }
   204  
   205  func (curve *nistCurve[Point]) ScalarMult(Bx, By *big.Int, scalar []byte) (*big.Int, *big.Int) {
   206  	p, err := curve.pointFromAffine(Bx, By)
   207  	if err != nil {
   208  		panic("crypto/elliptic: ScalarMult was called on an invalid point")
   209  	}
   210  	scalar = curve.normalizeScalar(scalar)
   211  	p, err = p.ScalarMult(p, scalar)
   212  	if err != nil {
   213  		panic("crypto/elliptic: nistec rejected normalized scalar")
   214  	}
   215  	return curve.pointToAffine(p)
   216  }
   217  
   218  func (curve *nistCurve[Point]) ScalarBaseMult(scalar []byte) (*big.Int, *big.Int) {
   219  	scalar = curve.normalizeScalar(scalar)
   220  	p, err := curve.newPoint().ScalarBaseMult(scalar)
   221  	if err != nil {
   222  		panic("crypto/elliptic: nistec rejected normalized scalar")
   223  	}
   224  	return curve.pointToAffine(p)
   225  }
   226  
   227  func (curve *nistCurve[Point]) Unmarshal(data []byte) (x, y *big.Int) {
   228  	if len(data) == 0 || data[0] != 4 {
   229  		return nil, nil
   230  	}
   231  	// Use SetBytes to check that data encodes a valid point.
   232  	_, err := curve.newPoint().SetBytes(data)
   233  	if err != nil {
   234  		return nil, nil
   235  	}
   236  	// We don't use pointToAffine because it involves an expensive field
   237  	// inversion to convert from Jacobian to affine coordinates, which we
   238  	// already have.
   239  	byteLen := (curve.params.BitSize + 7) / 8
   240  	x = new(big.Int).SetBytes(data[1 : 1+byteLen])
   241  	y = new(big.Int).SetBytes(data[1+byteLen:])
   242  	return x, y
   243  }
   244  
   245  func (curve *nistCurve[Point]) UnmarshalCompressed(data []byte) (x, y *big.Int) {
   246  	if len(data) == 0 || (data[0] != 2 && data[0] != 3) {
   247  		return nil, nil
   248  	}
   249  	p, err := curve.newPoint().SetBytes(data)
   250  	if err != nil {
   251  		return nil, nil
   252  	}
   253  	return curve.pointToAffine(p)
   254  }
   255  
   256  func bigFromDecimal(s string) *big.Int {
   257  	b, ok := new(big.Int).SetString(s, 10)
   258  	if !ok {
   259  		panic("crypto/elliptic: internal error: invalid encoding")
   260  	}
   261  	return b
   262  }
   263  
   264  func bigFromHex(s string) *big.Int {
   265  	b, ok := new(big.Int).SetString(s, 16)
   266  	if !ok {
   267  		panic("crypto/elliptic: internal error: invalid encoding")
   268  	}
   269  	return b
   270  }
   271
View as plain text