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