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

View as plain text