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

View as plain text