...
Run Format

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 http://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 http://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 http://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  	x3.Sub(x3, beta8)
   214  	for x3.Sign() == -1 {
   215  		x3.Add(x3, curve.P)
   216  	}
   217  	x3.Mod(x3, curve.P)
   218  
   219  	z3 := new(big.Int).Add(y, z)
   220  	z3.Mul(z3, z3)
   221  	z3.Sub(z3, gamma)
   222  	if z3.Sign() == -1 {
   223  		z3.Add(z3, curve.P)
   224  	}
   225  	z3.Sub(z3, delta)
   226  	if z3.Sign() == -1 {
   227  		z3.Add(z3, curve.P)
   228  	}
   229  	z3.Mod(z3, curve.P)
   230  
   231  	beta.Lsh(beta, 2)
   232  	beta.Sub(beta, x3)
   233  	if beta.Sign() == -1 {
   234  		beta.Add(beta, curve.P)
   235  	}
   236  	y3 := alpha.Mul(alpha, beta)
   237  
   238  	gamma.Mul(gamma, gamma)
   239  	gamma.Lsh(gamma, 3)
   240  	gamma.Mod(gamma, curve.P)
   241  
   242  	y3.Sub(y3, gamma)
   243  	if y3.Sign() == -1 {
   244  		y3.Add(y3, curve.P)
   245  	}
   246  	y3.Mod(y3, curve.P)
   247  
   248  	return x3, y3, z3
   249  }
   250  
   251  func (curve *CurveParams) ScalarMult(Bx, By *big.Int, k []byte) (*big.Int, *big.Int) {
   252  	Bz := new(big.Int).SetInt64(1)
   253  	x, y, z := new(big.Int), new(big.Int), new(big.Int)
   254  
   255  	for _, byte := range k {
   256  		for bitNum := 0; bitNum < 8; bitNum++ {
   257  			x, y, z = curve.doubleJacobian(x, y, z)
   258  			if byte&0x80 == 0x80 {
   259  				x, y, z = curve.addJacobian(Bx, By, Bz, x, y, z)
   260  			}
   261  			byte <<= 1
   262  		}
   263  	}
   264  
   265  	return curve.affineFromJacobian(x, y, z)
   266  }
   267  
   268  func (curve *CurveParams) ScalarBaseMult(k []byte) (*big.Int, *big.Int) {
   269  	return curve.ScalarMult(curve.Gx, curve.Gy, k)
   270  }
   271  
   272  var mask = []byte{0xff, 0x1, 0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f}
   273  
   274  // GenerateKey returns a public/private key pair. The private key is
   275  // generated using the given reader, which must return random data.
   276  func GenerateKey(curve Curve, rand io.Reader) (priv []byte, x, y *big.Int, err error) {
   277  	N := curve.Params().N
   278  	bitSize := N.BitLen()
   279  	byteLen := (bitSize + 7) >> 3
   280  	priv = make([]byte, byteLen)
   281  
   282  	for x == nil {
   283  		_, err = io.ReadFull(rand, priv)
   284  		if err != nil {
   285  			return
   286  		}
   287  		// We have to mask off any excess bits in the case that the size of the
   288  		// underlying field is not a whole number of bytes.
   289  		priv[0] &= mask[bitSize%8]
   290  		// This is because, in tests, rand will return all zeros and we don't
   291  		// want to get the point at infinity and loop forever.
   292  		priv[1] ^= 0x42
   293  
   294  		// If the scalar is out of range, sample another random number.
   295  		if new(big.Int).SetBytes(priv).Cmp(N) >= 0 {
   296  			continue
   297  		}
   298  
   299  		x, y = curve.ScalarBaseMult(priv)
   300  	}
   301  	return
   302  }
   303  
   304  // Marshal converts a point into the uncompressed form specified in section 4.3.6 of ANSI X9.62.
   305  func Marshal(curve Curve, x, y *big.Int) []byte {
   306  	byteLen := (curve.Params().BitSize + 7) >> 3
   307  
   308  	ret := make([]byte, 1+2*byteLen)
   309  	ret[0] = 4 // uncompressed point
   310  
   311  	xBytes := x.Bytes()
   312  	copy(ret[1+byteLen-len(xBytes):], xBytes)
   313  	yBytes := y.Bytes()
   314  	copy(ret[1+2*byteLen-len(yBytes):], yBytes)
   315  	return ret
   316  }
   317  
   318  // Unmarshal converts a point, serialized by Marshal, into an x, y pair.
   319  // It is an error if the point is not in uncompressed form or is not on the curve.
   320  // On error, x = nil.
   321  func Unmarshal(curve Curve, data []byte) (x, y *big.Int) {
   322  	byteLen := (curve.Params().BitSize + 7) >> 3
   323  	if len(data) != 1+2*byteLen {
   324  		return
   325  	}
   326  	if data[0] != 4 { // uncompressed form
   327  		return
   328  	}
   329  	p := curve.Params().P
   330  	x = new(big.Int).SetBytes(data[1 : 1+byteLen])
   331  	y = new(big.Int).SetBytes(data[1+byteLen:])
   332  	if x.Cmp(p) >= 0 || y.Cmp(p) >= 0 {
   333  		return nil, nil
   334  	}
   335  	if !curve.IsOnCurve(x, y) {
   336  		return nil, nil
   337  	}
   338  	return
   339  }
   340  
   341  var initonce sync.Once
   342  var p384 *CurveParams
   343  var p521 *CurveParams
   344  
   345  func initAll() {
   346  	initP224()
   347  	initP256()
   348  	initP384()
   349  	initP521()
   350  }
   351  
   352  func initP384() {
   353  	// See FIPS 186-3, section D.2.4
   354  	p384 = &CurveParams{Name: "P-384"}
   355  	p384.P, _ = new(big.Int).SetString("39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319", 10)
   356  	p384.N, _ = new(big.Int).SetString("39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643", 10)
   357  	p384.B, _ = new(big.Int).SetString("b3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef", 16)
   358  	p384.Gx, _ = new(big.Int).SetString("aa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7", 16)
   359  	p384.Gy, _ = new(big.Int).SetString("3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f", 16)
   360  	p384.BitSize = 384
   361  }
   362  
   363  func initP521() {
   364  	// See FIPS 186-3, section D.2.5
   365  	p521 = &CurveParams{Name: "P-521"}
   366  	p521.P, _ = new(big.Int).SetString("6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151", 10)
   367  	p521.N, _ = new(big.Int).SetString("6864797660130609714981900799081393217269435300143305409394463459185543183397655394245057746333217197532963996371363321113864768612440380340372808892707005449", 10)
   368  	p521.B, _ = new(big.Int).SetString("051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00", 16)
   369  	p521.Gx, _ = new(big.Int).SetString("c6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66", 16)
   370  	p521.Gy, _ = new(big.Int).SetString("11839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650", 16)
   371  	p521.BitSize = 521
   372  }
   373  
   374  // P256 returns a Curve which implements P-256 (see FIPS 186-3, section D.2.3)
   375  //
   376  // The cryptographic operations are implemented using constant-time algorithms.
   377  func P256() Curve {
   378  	initonce.Do(initAll)
   379  	return p256
   380  }
   381  
   382  // P384 returns a Curve which implements P-384 (see FIPS 186-3, section D.2.4)
   383  //
   384  // The cryptographic operations do not use constant-time algorithms.
   385  func P384() Curve {
   386  	initonce.Do(initAll)
   387  	return p384
   388  }
   389  
   390  // P521 returns a Curve which implements P-521 (see FIPS 186-3, section D.2.5)
   391  //
   392  // The cryptographic operations do not use constant-time algorithms.
   393  func P521() Curve {
   394  	initonce.Do(initAll)
   395  	return p521
   396  }
   397  

View as plain text