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

View as plain text