Black Lives Matter. Support the Equal Justice Initiative.

Source file src/crypto/elliptic/elliptic.go

Documentation: crypto/elliptic

     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 several standard elliptic curves over prime
     6  // fields.
     7  package elliptic
     8  
     9  // This package operates, internally, on Jacobian coordinates. For a given
    10  // (x, y) position on the curve, the Jacobian coordinates are (x1, y1, z1)
    11  // where x = x1/z1² and y = y1/z1³. The greatest speedups come when the whole
    12  // calculation can be performed within the transform (as in ScalarMult and
    13  // ScalarBaseMult). But even for Add and Double, it's faster to apply and
    14  // reverse the transform than to operate in affine coordinates.
    15  
    16  import (
    17  	"io"
    18  	"math/big"
    19  	"sync"
    20  )
    21  
    22  // A Curve represents a short-form Weierstrass curve with a=-3.
    23  //
    24  // Note that the point at infinity (0, 0) is not considered on the curve, and
    25  // although it can be returned by Add, Double, ScalarMult, or ScalarBaseMult, it
    26  // can't be marshaled or unmarshaled, and IsOnCurve will return false for it.
    27  type Curve interface {
    28  	// Params returns the parameters for the curve.
    29  	Params() *CurveParams
    30  	// IsOnCurve reports whether the given (x,y) lies on the curve.
    31  	IsOnCurve(x, y *big.Int) bool
    32  	// Add returns the sum of (x1,y1) and (x2,y2)
    33  	Add(x1, y1, x2, y2 *big.Int) (x, y *big.Int)
    34  	// Double returns 2*(x,y)
    35  	Double(x1, y1 *big.Int) (x, y *big.Int)
    36  	// ScalarMult returns k*(Bx,By) where k is a number in big-endian form.
    37  	ScalarMult(x1, y1 *big.Int, k []byte) (x, y *big.Int)
    38  	// ScalarBaseMult returns k*G, where G is the base point of the group
    39  	// and k is an integer in big-endian form.
    40  	ScalarBaseMult(k []byte) (x, y *big.Int)
    41  }
    42  
    43  func matchesSpecificCurve(params *CurveParams, available ...Curve) (Curve, bool) {
    44  	for _, c := range available {
    45  		if params == c.Params() {
    46  			return c, true
    47  		}
    48  	}
    49  	return nil, false
    50  }
    51  
    52  // CurveParams contains the parameters of an elliptic curve and also provides
    53  // a generic, non-constant time implementation of Curve.
    54  type CurveParams struct {
    55  	P       *big.Int // the order of the underlying field
    56  	N       *big.Int // the order of the base point
    57  	B       *big.Int // the constant of the curve equation
    58  	Gx, Gy  *big.Int // (x,y) of the base point
    59  	BitSize int      // the size of the underlying field
    60  	Name    string   // the canonical name of the curve
    61  }
    62  
    63  func (curve *CurveParams) Params() *CurveParams {
    64  	return curve
    65  }
    66  
    67  // polynomial returns x³ - 3x + b.
    68  func (curve *CurveParams) polynomial(x *big.Int) *big.Int {
    69  	x3 := new(big.Int).Mul(x, x)
    70  	x3.Mul(x3, x)
    71  
    72  	threeX := new(big.Int).Lsh(x, 1)
    73  	threeX.Add(threeX, x)
    74  
    75  	x3.Sub(x3, threeX)
    76  	x3.Add(x3, curve.B)
    77  	x3.Mod(x3, curve.P)
    78  
    79  	return x3
    80  }
    81  
    82  func (curve *CurveParams) IsOnCurve(x, y *big.Int) bool {
    83  	// If there is a dedicated constant-time implementation for this curve operation,
    84  	// use that instead of the generic one.
    85  	if specific, ok := matchesSpecificCurve(curve, p224, p521); ok {
    86  		return specific.IsOnCurve(x, y)
    87  	}
    88  
    89  	// y² = x³ - 3x + b
    90  	y2 := new(big.Int).Mul(y, y)
    91  	y2.Mod(y2, curve.P)
    92  
    93  	return curve.polynomial(x).Cmp(y2) == 0
    94  }
    95  
    96  // zForAffine returns a Jacobian Z value for the affine point (x, y). If x and
    97  // y are zero, it assumes that they represent the point at infinity because (0,
    98  // 0) is not on the any of the curves handled here.
    99  func zForAffine(x, y *big.Int) *big.Int {
   100  	z := new(big.Int)
   101  	if x.Sign() != 0 || y.Sign() != 0 {
   102  		z.SetInt64(1)
   103  	}
   104  	return z
   105  }
   106  
   107  // affineFromJacobian reverses the Jacobian transform. See the comment at the
   108  // top of the file. If the point is ∞ it returns 0, 0.
   109  func (curve *CurveParams) affineFromJacobian(x, y, z *big.Int) (xOut, yOut *big.Int) {
   110  	if z.Sign() == 0 {
   111  		return new(big.Int), new(big.Int)
   112  	}
   113  
   114  	zinv := new(big.Int).ModInverse(z, curve.P)
   115  	zinvsq := new(big.Int).Mul(zinv, zinv)
   116  
   117  	xOut = new(big.Int).Mul(x, zinvsq)
   118  	xOut.Mod(xOut, curve.P)
   119  	zinvsq.Mul(zinvsq, zinv)
   120  	yOut = new(big.Int).Mul(y, zinvsq)
   121  	yOut.Mod(yOut, curve.P)
   122  	return
   123  }
   124  
   125  func (curve *CurveParams) Add(x1, y1, x2, y2 *big.Int) (*big.Int, *big.Int) {
   126  	// If there is a dedicated constant-time implementation for this curve operation,
   127  	// use that instead of the generic one.
   128  	if specific, ok := matchesSpecificCurve(curve, p224, p521); ok {
   129  		return specific.Add(x1, y1, x2, y2)
   130  	}
   131  
   132  	z1 := zForAffine(x1, y1)
   133  	z2 := zForAffine(x2, y2)
   134  	return curve.affineFromJacobian(curve.addJacobian(x1, y1, z1, x2, y2, z2))
   135  }
   136  
   137  // addJacobian takes two points in Jacobian coordinates, (x1, y1, z1) and
   138  // (x2, y2, z2) and returns their sum, also in Jacobian form.
   139  func (curve *CurveParams) addJacobian(x1, y1, z1, x2, y2, z2 *big.Int) (*big.Int, *big.Int, *big.Int) {
   140  	// See https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-2007-bl
   141  	x3, y3, z3 := new(big.Int), new(big.Int), new(big.Int)
   142  	if z1.Sign() == 0 {
   143  		x3.Set(x2)
   144  		y3.Set(y2)
   145  		z3.Set(z2)
   146  		return x3, y3, z3
   147  	}
   148  	if z2.Sign() == 0 {
   149  		x3.Set(x1)
   150  		y3.Set(y1)
   151  		z3.Set(z1)
   152  		return x3, y3, z3
   153  	}
   154  
   155  	z1z1 := new(big.Int).Mul(z1, z1)
   156  	z1z1.Mod(z1z1, curve.P)
   157  	z2z2 := new(big.Int).Mul(z2, z2)
   158  	z2z2.Mod(z2z2, curve.P)
   159  
   160  	u1 := new(big.Int).Mul(x1, z2z2)
   161  	u1.Mod(u1, curve.P)
   162  	u2 := new(big.Int).Mul(x2, z1z1)
   163  	u2.Mod(u2, curve.P)
   164  	h := new(big.Int).Sub(u2, u1)
   165  	xEqual := h.Sign() == 0
   166  	if h.Sign() == -1 {
   167  		h.Add(h, curve.P)
   168  	}
   169  	i := new(big.Int).Lsh(h, 1)
   170  	i.Mul(i, i)
   171  	j := new(big.Int).Mul(h, i)
   172  
   173  	s1 := new(big.Int).Mul(y1, z2)
   174  	s1.Mul(s1, z2z2)
   175  	s1.Mod(s1, curve.P)
   176  	s2 := new(big.Int).Mul(y2, z1)
   177  	s2.Mul(s2, z1z1)
   178  	s2.Mod(s2, curve.P)
   179  	r := new(big.Int).Sub(s2, s1)
   180  	if r.Sign() == -1 {
   181  		r.Add(r, curve.P)
   182  	}
   183  	yEqual := r.Sign() == 0
   184  	if xEqual && yEqual {
   185  		return curve.doubleJacobian(x1, y1, z1)
   186  	}
   187  	r.Lsh(r, 1)
   188  	v := new(big.Int).Mul(u1, i)
   189  
   190  	x3.Set(r)
   191  	x3.Mul(x3, x3)
   192  	x3.Sub(x3, j)
   193  	x3.Sub(x3, v)
   194  	x3.Sub(x3, v)
   195  	x3.Mod(x3, curve.P)
   196  
   197  	y3.Set(r)
   198  	v.Sub(v, x3)
   199  	y3.Mul(y3, v)
   200  	s1.Mul(s1, j)
   201  	s1.Lsh(s1, 1)
   202  	y3.Sub(y3, s1)
   203  	y3.Mod(y3, curve.P)
   204  
   205  	z3.Add(z1, z2)
   206  	z3.Mul(z3, z3)
   207  	z3.Sub(z3, z1z1)
   208  	z3.Sub(z3, z2z2)
   209  	z3.Mul(z3, h)
   210  	z3.Mod(z3, curve.P)
   211  
   212  	return x3, y3, z3
   213  }
   214  
   215  func (curve *CurveParams) Double(x1, y1 *big.Int) (*big.Int, *big.Int) {
   216  	// If there is a dedicated constant-time implementation for this curve operation,
   217  	// use that instead of the generic one.
   218  	if specific, ok := matchesSpecificCurve(curve, p224, p521); ok {
   219  		return specific.Double(x1, y1)
   220  	}
   221  
   222  	z1 := zForAffine(x1, y1)
   223  	return curve.affineFromJacobian(curve.doubleJacobian(x1, y1, z1))
   224  }
   225  
   226  // doubleJacobian takes a point in Jacobian coordinates, (x, y, z), and
   227  // returns its double, also in Jacobian form.
   228  func (curve *CurveParams) doubleJacobian(x, y, z *big.Int) (*big.Int, *big.Int, *big.Int) {
   229  	// See https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-2001-b
   230  	delta := new(big.Int).Mul(z, z)
   231  	delta.Mod(delta, curve.P)
   232  	gamma := new(big.Int).Mul(y, y)
   233  	gamma.Mod(gamma, curve.P)
   234  	alpha := new(big.Int).Sub(x, delta)
   235  	if alpha.Sign() == -1 {
   236  		alpha.Add(alpha, curve.P)
   237  	}
   238  	alpha2 := new(big.Int).Add(x, delta)
   239  	alpha.Mul(alpha, alpha2)
   240  	alpha2.Set(alpha)
   241  	alpha.Lsh(alpha, 1)
   242  	alpha.Add(alpha, alpha2)
   243  
   244  	beta := alpha2.Mul(x, gamma)
   245  
   246  	x3 := new(big.Int).Mul(alpha, alpha)
   247  	beta8 := new(big.Int).Lsh(beta, 3)
   248  	beta8.Mod(beta8, curve.P)
   249  	x3.Sub(x3, beta8)
   250  	if x3.Sign() == -1 {
   251  		x3.Add(x3, curve.P)
   252  	}
   253  	x3.Mod(x3, curve.P)
   254  
   255  	z3 := new(big.Int).Add(y, z)
   256  	z3.Mul(z3, z3)
   257  	z3.Sub(z3, gamma)
   258  	if z3.Sign() == -1 {
   259  		z3.Add(z3, curve.P)
   260  	}
   261  	z3.Sub(z3, delta)
   262  	if z3.Sign() == -1 {
   263  		z3.Add(z3, curve.P)
   264  	}
   265  	z3.Mod(z3, curve.P)
   266  
   267  	beta.Lsh(beta, 2)
   268  	beta.Sub(beta, x3)
   269  	if beta.Sign() == -1 {
   270  		beta.Add(beta, curve.P)
   271  	}
   272  	y3 := alpha.Mul(alpha, beta)
   273  
   274  	gamma.Mul(gamma, gamma)
   275  	gamma.Lsh(gamma, 3)
   276  	gamma.Mod(gamma, curve.P)
   277  
   278  	y3.Sub(y3, gamma)
   279  	if y3.Sign() == -1 {
   280  		y3.Add(y3, curve.P)
   281  	}
   282  	y3.Mod(y3, curve.P)
   283  
   284  	return x3, y3, z3
   285  }
   286  
   287  func (curve *CurveParams) ScalarMult(Bx, By *big.Int, k []byte) (*big.Int, *big.Int) {
   288  	// If there is a dedicated constant-time implementation for this curve operation,
   289  	// use that instead of the generic one.
   290  	if specific, ok := matchesSpecificCurve(curve, p224, p256, p521); ok {
   291  		return specific.ScalarMult(Bx, By, k)
   292  	}
   293  
   294  	Bz := new(big.Int).SetInt64(1)
   295  	x, y, z := new(big.Int), new(big.Int), new(big.Int)
   296  
   297  	for _, byte := range k {
   298  		for bitNum := 0; bitNum < 8; bitNum++ {
   299  			x, y, z = curve.doubleJacobian(x, y, z)
   300  			if byte&0x80 == 0x80 {
   301  				x, y, z = curve.addJacobian(Bx, By, Bz, x, y, z)
   302  			}
   303  			byte <<= 1
   304  		}
   305  	}
   306  
   307  	return curve.affineFromJacobian(x, y, z)
   308  }
   309  
   310  func (curve *CurveParams) ScalarBaseMult(k []byte) (*big.Int, *big.Int) {
   311  	// If there is a dedicated constant-time implementation for this curve operation,
   312  	// use that instead of the generic one.
   313  	if specific, ok := matchesSpecificCurve(curve, p224, p256, p521); ok {
   314  		return specific.ScalarBaseMult(k)
   315  	}
   316  
   317  	return curve.ScalarMult(curve.Gx, curve.Gy, k)
   318  }
   319  
   320  var mask = []byte{0xff, 0x1, 0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f}
   321  
   322  // GenerateKey returns a public/private key pair. The private key is
   323  // generated using the given reader, which must return random data.
   324  func GenerateKey(curve Curve, rand io.Reader) (priv []byte, x, y *big.Int, err error) {
   325  	N := curve.Params().N
   326  	bitSize := N.BitLen()
   327  	byteLen := (bitSize + 7) / 8
   328  	priv = make([]byte, byteLen)
   329  
   330  	for x == nil {
   331  		_, err = io.ReadFull(rand, priv)
   332  		if err != nil {
   333  			return
   334  		}
   335  		// We have to mask off any excess bits in the case that the size of the
   336  		// underlying field is not a whole number of bytes.
   337  		priv[0] &= mask[bitSize%8]
   338  		// This is because, in tests, rand will return all zeros and we don't
   339  		// want to get the point at infinity and loop forever.
   340  		priv[1] ^= 0x42
   341  
   342  		// If the scalar is out of range, sample another random number.
   343  		if new(big.Int).SetBytes(priv).Cmp(N) >= 0 {
   344  			continue
   345  		}
   346  
   347  		x, y = curve.ScalarBaseMult(priv)
   348  	}
   349  	return
   350  }
   351  
   352  // Marshal converts a point on the curve into the uncompressed form specified in
   353  // section 4.3.6 of ANSI X9.62.
   354  func Marshal(curve Curve, x, y *big.Int) []byte {
   355  	byteLen := (curve.Params().BitSize + 7) / 8
   356  
   357  	ret := make([]byte, 1+2*byteLen)
   358  	ret[0] = 4 // uncompressed point
   359  
   360  	x.FillBytes(ret[1 : 1+byteLen])
   361  	y.FillBytes(ret[1+byteLen : 1+2*byteLen])
   362  
   363  	return ret
   364  }
   365  
   366  // MarshalCompressed converts a point on the curve into the compressed form
   367  // specified in section 4.3.6 of ANSI X9.62.
   368  func MarshalCompressed(curve Curve, x, y *big.Int) []byte {
   369  	byteLen := (curve.Params().BitSize + 7) / 8
   370  	compressed := make([]byte, 1+byteLen)
   371  	compressed[0] = byte(y.Bit(0)) | 2
   372  	x.FillBytes(compressed[1:])
   373  	return compressed
   374  }
   375  
   376  // Unmarshal converts a point, serialized by Marshal, into an x, y pair.
   377  // It is an error if the point is not in uncompressed form or is not on the curve.
   378  // On error, x = nil.
   379  func Unmarshal(curve Curve, data []byte) (x, y *big.Int) {
   380  	byteLen := (curve.Params().BitSize + 7) / 8
   381  	if len(data) != 1+2*byteLen {
   382  		return nil, nil
   383  	}
   384  	if data[0] != 4 { // uncompressed form
   385  		return nil, nil
   386  	}
   387  	p := curve.Params().P
   388  	x = new(big.Int).SetBytes(data[1 : 1+byteLen])
   389  	y = new(big.Int).SetBytes(data[1+byteLen:])
   390  	if x.Cmp(p) >= 0 || y.Cmp(p) >= 0 {
   391  		return nil, nil
   392  	}
   393  	if !curve.IsOnCurve(x, y) {
   394  		return nil, nil
   395  	}
   396  	return
   397  }
   398  
   399  // UnmarshalCompressed converts a point, serialized by MarshalCompressed, into an x, y pair.
   400  // It is an error if the point is not in compressed form or is not on the curve.
   401  // On error, x = nil.
   402  func UnmarshalCompressed(curve Curve, data []byte) (x, y *big.Int) {
   403  	byteLen := (curve.Params().BitSize + 7) / 8
   404  	if len(data) != 1+byteLen {
   405  		return nil, nil
   406  	}
   407  	if data[0] != 2 && data[0] != 3 { // compressed form
   408  		return nil, nil
   409  	}
   410  	p := curve.Params().P
   411  	x = new(big.Int).SetBytes(data[1:])
   412  	if x.Cmp(p) >= 0 {
   413  		return nil, nil
   414  	}
   415  	// y² = x³ - 3x + b
   416  	y = curve.Params().polynomial(x)
   417  	y = y.ModSqrt(y, p)
   418  	if y == nil {
   419  		return nil, nil
   420  	}
   421  	if byte(y.Bit(0)) != data[0]&1 {
   422  		y.Neg(y).Mod(y, p)
   423  	}
   424  	if !curve.IsOnCurve(x, y) {
   425  		return nil, nil
   426  	}
   427  	return
   428  }
   429  
   430  var initonce sync.Once
   431  var p384 *CurveParams
   432  
   433  func initAll() {
   434  	initP224()
   435  	initP256()
   436  	initP384()
   437  	initP521()
   438  }
   439  
   440  func initP384() {
   441  	// See FIPS 186-3, section D.2.4
   442  	p384 = &CurveParams{Name: "P-384"}
   443  	p384.P, _ = new(big.Int).SetString("39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319", 10)
   444  	p384.N, _ = new(big.Int).SetString("39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643", 10)
   445  	p384.B, _ = new(big.Int).SetString("b3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef", 16)
   446  	p384.Gx, _ = new(big.Int).SetString("aa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7", 16)
   447  	p384.Gy, _ = new(big.Int).SetString("3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f", 16)
   448  	p384.BitSize = 384
   449  }
   450  
   451  // P256 returns a Curve which implements NIST P-256 (FIPS 186-3, section D.2.3),
   452  // also known as secp256r1 or prime256v1. The CurveParams.Name of this Curve is
   453  // "P-256".
   454  //
   455  // Multiple invocations of this function will return the same value, so it can
   456  // be used for equality checks and switch statements.
   457  //
   458  // ScalarMult and ScalarBaseMult are implemented using constant-time algorithms.
   459  func P256() Curve {
   460  	initonce.Do(initAll)
   461  	return p256
   462  }
   463  
   464  // P384 returns a Curve which implements NIST P-384 (FIPS 186-3, section D.2.4),
   465  // also known as secp384r1. The CurveParams.Name of this Curve is "P-384".
   466  //
   467  // Multiple invocations of this function will return the same value, so it can
   468  // be used for equality checks and switch statements.
   469  //
   470  // The cryptographic operations do not use constant-time algorithms.
   471  func P384() Curve {
   472  	initonce.Do(initAll)
   473  	return p384
   474  }
   475  
   476  // P521 returns a Curve which implements NIST P-521 (FIPS 186-3, section D.2.5),
   477  // also known as secp521r1. The CurveParams.Name of this Curve is "P-521".
   478  //
   479  // Multiple invocations of this function will return the same value, so it can
   480  // be used for equality checks and switch statements.
   481  //
   482  // The cryptographic operations are implemented using constant-time algorithms.
   483  func P521() Curve {
   484  	initonce.Do(initAll)
   485  	return p521
   486  }
   487  

View as plain text