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