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

View as plain text