...
Run Format

Source file src/crypto/elliptic/elliptic.go

     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		bitSize := curve.Params().BitSize
   278		byteLen := (bitSize + 7) >> 3
   279		priv = make([]byte, byteLen)
   280	
   281		for x == nil {
   282			_, err = io.ReadFull(rand, priv)
   283			if err != nil {
   284				return
   285			}
   286			// We have to mask off any excess bits in the case that the size of the
   287			// underlying field is not a whole number of bytes.
   288			priv[0] &= mask[bitSize%8]
   289			// This is because, in tests, rand will return all zeros and we don't
   290			// want to get the point at infinity and loop forever.
   291			priv[1] ^= 0x42
   292			x, y = curve.ScalarBaseMult(priv)
   293		}
   294		return
   295	}
   296	
   297	// Marshal converts a point into the form specified in section 4.3.6 of ANSI X9.62.
   298	func Marshal(curve Curve, x, y *big.Int) []byte {
   299		byteLen := (curve.Params().BitSize + 7) >> 3
   300	
   301		ret := make([]byte, 1+2*byteLen)
   302		ret[0] = 4 // uncompressed point
   303	
   304		xBytes := x.Bytes()
   305		copy(ret[1+byteLen-len(xBytes):], xBytes)
   306		yBytes := y.Bytes()
   307		copy(ret[1+2*byteLen-len(yBytes):], yBytes)
   308		return ret
   309	}
   310	
   311	// Unmarshal converts a point, serialized by Marshal, into an x, y pair.
   312	// It is an error if the point is not on the curve. On error, x = nil.
   313	func Unmarshal(curve Curve, data []byte) (x, y *big.Int) {
   314		byteLen := (curve.Params().BitSize + 7) >> 3
   315		if len(data) != 1+2*byteLen {
   316			return
   317		}
   318		if data[0] != 4 { // uncompressed form
   319			return
   320		}
   321		x = new(big.Int).SetBytes(data[1 : 1+byteLen])
   322		y = new(big.Int).SetBytes(data[1+byteLen:])
   323		if !curve.IsOnCurve(x, y) {
   324			x, y = nil, nil
   325		}
   326		return
   327	}
   328	
   329	var initonce sync.Once
   330	var p384 *CurveParams
   331	var p521 *CurveParams
   332	
   333	func initAll() {
   334		initP224()
   335		initP256()
   336		initP384()
   337		initP521()
   338	}
   339	
   340	func initP384() {
   341		// See FIPS 186-3, section D.2.4
   342		p384 = &CurveParams{Name: "P-384"}
   343		p384.P, _ = new(big.Int).SetString("39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319", 10)
   344		p384.N, _ = new(big.Int).SetString("39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643", 10)
   345		p384.B, _ = new(big.Int).SetString("b3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef", 16)
   346		p384.Gx, _ = new(big.Int).SetString("aa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7", 16)
   347		p384.Gy, _ = new(big.Int).SetString("3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f", 16)
   348		p384.BitSize = 384
   349	}
   350	
   351	func initP521() {
   352		// See FIPS 186-3, section D.2.5
   353		p521 = &CurveParams{Name: "P-521"}
   354		p521.P, _ = new(big.Int).SetString("6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151", 10)
   355		p521.N, _ = new(big.Int).SetString("6864797660130609714981900799081393217269435300143305409394463459185543183397655394245057746333217197532963996371363321113864768612440380340372808892707005449", 10)
   356		p521.B, _ = new(big.Int).SetString("051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00", 16)
   357		p521.Gx, _ = new(big.Int).SetString("c6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66", 16)
   358		p521.Gy, _ = new(big.Int).SetString("11839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650", 16)
   359		p521.BitSize = 521
   360	}
   361	
   362	// P256 returns a Curve which implements P-256 (see FIPS 186-3, section D.2.3)
   363	func P256() Curve {
   364		initonce.Do(initAll)
   365		return p256
   366	}
   367	
   368	// P384 returns a Curve which implements P-384 (see FIPS 186-3, section D.2.4)
   369	func P384() Curve {
   370		initonce.Do(initAll)
   371		return p384
   372	}
   373	
   374	// P521 returns a Curve which implements P-521 (see FIPS 186-3, section D.2.5)
   375	func P521() Curve {
   376		initonce.Do(initAll)
   377		return p521
   378	}
   379	

View as plain text