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

View as plain text