...
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		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 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 on the curve. On error, x = nil.
   320	func Unmarshal(curve Curve, data []byte) (x, y *big.Int) {
   321		byteLen := (curve.Params().BitSize + 7) >> 3
   322		if len(data) != 1+2*byteLen {
   323			return
   324		}
   325		if data[0] != 4 { // uncompressed form
   326			return
   327		}
   328		x = new(big.Int).SetBytes(data[1 : 1+byteLen])
   329		y = new(big.Int).SetBytes(data[1+byteLen:])
   330		if !curve.IsOnCurve(x, y) {
   331			x, y = nil, nil
   332		}
   333		return
   334	}
   335	
   336	var initonce sync.Once
   337	var p384 *CurveParams
   338	var p521 *CurveParams
   339	
   340	func initAll() {
   341		initP224()
   342		initP256()
   343		initP384()
   344		initP521()
   345	}
   346	
   347	func initP384() {
   348		// See FIPS 186-3, section D.2.4
   349		p384 = &CurveParams{Name: "P-384"}
   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 = &CurveParams{Name: "P-521"}
   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	}
   386	

View as plain text