Black Lives Matter. Support the Equal Justice Initiative.

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

View as plain text