# 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
4
5  // Package elliptic implements the standard NIST P-224, P-256, P-384, and P-521
6  // elliptic curves over prime fields.
7  package elliptic
8
9  import (
10  	"io"
11  	"math/big"
12  	"sync"
13  )
14
15  // A Curve represents a short-form Weierstrass curve with a=-3.
16  //
17  // The behavior of Add, Double, and ScalarMult when the input is not a point on
18  // the curve is undefined.
19  //
20  // Note that the conventional point at infinity (0, 0) is not considered on the
21  // curve, although it can be returned by Add, Double, ScalarMult, or
22  // ScalarBaseMult (but not the Unmarshal or UnmarshalCompressed functions).
23  type Curve interface {
24  	// Params returns the parameters for the curve.
25  	Params() *CurveParams
26  	// IsOnCurve reports whether the given (x,y) lies on the curve.
27  	IsOnCurve(x, y *big.Int) bool
28  	// Add returns the sum of (x1,y1) and (x2,y2)
29  	Add(x1, y1, x2, y2 *big.Int) (x, y *big.Int)
30  	// Double returns 2*(x,y)
31  	Double(x1, y1 *big.Int) (x, y *big.Int)
32  	// ScalarMult returns k*(Bx,By) where k is a number in big-endian form.
33  	ScalarMult(x1, y1 *big.Int, k []byte) (x, y *big.Int)
34  	// ScalarBaseMult returns k*G, where G is the base point of the group
35  	// and k is an integer in big-endian form.
36  	ScalarBaseMult(k []byte) (x, y *big.Int)
37  }
38
39  func matchesSpecificCurve(params *CurveParams, available ...Curve) (Curve, bool) {
40  	for _, c := range available {
41  		if params == c.Params() {
42  			return c, true
43  		}
44  	}
45  	return nil, false
46  }
47
48  // CurveParams contains the parameters of an elliptic curve and also provides
49  // a generic, non-constant time implementation of Curve.
50  type CurveParams struct {
51  	P       *big.Int // the order of the underlying field
52  	N       *big.Int // the order of the base point
53  	B       *big.Int // the constant of the curve equation
54  	Gx, Gy  *big.Int // (x,y) of the base point
55  	BitSize int      // the size of the underlying field
56  	Name    string   // the canonical name of the curve
57  }
58
59  func (curve *CurveParams) Params() *CurveParams {
60  	return curve
61  }
62
63  // CurveParams operates, internally, on Jacobian coordinates. For a given
64  // (x, y) position on the curve, the Jacobian coordinates are (x1, y1, z1)
65  // where x = x1/z1² and y = y1/z1³. The greatest speedups come when the whole
66  // calculation can be performed within the transform (as in ScalarMult and
67  // ScalarBaseMult). But even for Add and Double, it's faster to apply and
68  // reverse the transform than to operate in affine coordinates.
69
70  // polynomial returns x³ - 3x + b.
71  func (curve *CurveParams) polynomial(x *big.Int) *big.Int {
72  	x3 := new(big.Int).Mul(x, x)
73  	x3.Mul(x3, x)
74
75  	threeX := new(big.Int).Lsh(x, 1)
77
78  	x3.Sub(x3, threeX)
80  	x3.Mod(x3, curve.P)
81
82  	return x3
83  }
84
85  func (curve *CurveParams) IsOnCurve(x, y *big.Int) bool {
86  	// If there is a dedicated constant-time implementation for this curve operation,
87  	// use that instead of the generic one.
88  	if specific, ok := matchesSpecificCurve(curve, p224, p384, p521); ok {
89  		return specific.IsOnCurve(x, y)
90  	}
91
92  	if x.Sign() < 0 || x.Cmp(curve.P) >= 0 ||
93  		y.Sign() < 0 || y.Cmp(curve.P) >= 0 {
94  		return false
95  	}
96
97  	// y² = x³ - 3x + b
98  	y2 := new(big.Int).Mul(y, y)
99  	y2.Mod(y2, curve.P)
100
101  	return curve.polynomial(x).Cmp(y2) == 0
102  }
103
104  // zForAffine returns a Jacobian Z value for the affine point (x, y). If x and
105  // y are zero, it assumes that they represent the point at infinity because (0,
106  // 0) is not on the any of the curves handled here.
107  func zForAffine(x, y *big.Int) *big.Int {
108  	z := new(big.Int)
109  	if x.Sign() != 0 || y.Sign() != 0 {
110  		z.SetInt64(1)
111  	}
112  	return z
113  }
114
115  // affineFromJacobian reverses the Jacobian transform. See the comment at the
116  // top of the file. If the point is ∞ it returns 0, 0.
117  func (curve *CurveParams) affineFromJacobian(x, y, z *big.Int) (xOut, yOut *big.Int) {
118  	if z.Sign() == 0 {
119  		return new(big.Int), new(big.Int)
120  	}
121
122  	zinv := new(big.Int).ModInverse(z, curve.P)
123  	zinvsq := new(big.Int).Mul(zinv, zinv)
124
125  	xOut = new(big.Int).Mul(x, zinvsq)
126  	xOut.Mod(xOut, curve.P)
127  	zinvsq.Mul(zinvsq, zinv)
128  	yOut = new(big.Int).Mul(y, zinvsq)
129  	yOut.Mod(yOut, curve.P)
130  	return
131  }
132
133  func (curve *CurveParams) Add(x1, y1, x2, y2 *big.Int) (*big.Int, *big.Int) {
134  	// If there is a dedicated constant-time implementation for this curve operation,
135  	// use that instead of the generic one.
136  	if specific, ok := matchesSpecificCurve(curve, p224, p384, p521); ok {
137  		return specific.Add(x1, y1, x2, y2)
138  	}
139
140  	z1 := zForAffine(x1, y1)
141  	z2 := zForAffine(x2, y2)
142  	return curve.affineFromJacobian(curve.addJacobian(x1, y1, z1, x2, y2, z2))
143  }
144
145  // addJacobian takes two points in Jacobian coordinates, (x1, y1, z1) and
146  // (x2, y2, z2) and returns their sum, also in Jacobian form.
147  func (curve *CurveParams) addJacobian(x1, y1, z1, x2, y2, z2 *big.Int) (*big.Int, *big.Int, *big.Int) {
149  	x3, y3, z3 := new(big.Int), new(big.Int), new(big.Int)
150  	if z1.Sign() == 0 {
151  		x3.Set(x2)
152  		y3.Set(y2)
153  		z3.Set(z2)
154  		return x3, y3, z3
155  	}
156  	if z2.Sign() == 0 {
157  		x3.Set(x1)
158  		y3.Set(y1)
159  		z3.Set(z1)
160  		return x3, y3, z3
161  	}
162
163  	z1z1 := new(big.Int).Mul(z1, z1)
164  	z1z1.Mod(z1z1, curve.P)
165  	z2z2 := new(big.Int).Mul(z2, z2)
166  	z2z2.Mod(z2z2, curve.P)
167
168  	u1 := new(big.Int).Mul(x1, z2z2)
169  	u1.Mod(u1, curve.P)
170  	u2 := new(big.Int).Mul(x2, z1z1)
171  	u2.Mod(u2, curve.P)
172  	h := new(big.Int).Sub(u2, u1)
173  	xEqual := h.Sign() == 0
174  	if h.Sign() == -1 {
176  	}
177  	i := new(big.Int).Lsh(h, 1)
178  	i.Mul(i, i)
179  	j := new(big.Int).Mul(h, i)
180
181  	s1 := new(big.Int).Mul(y1, z2)
182  	s1.Mul(s1, z2z2)
183  	s1.Mod(s1, curve.P)
184  	s2 := new(big.Int).Mul(y2, z1)
185  	s2.Mul(s2, z1z1)
186  	s2.Mod(s2, curve.P)
187  	r := new(big.Int).Sub(s2, s1)
188  	if r.Sign() == -1 {
190  	}
191  	yEqual := r.Sign() == 0
192  	if xEqual && yEqual {
193  		return curve.doubleJacobian(x1, y1, z1)
194  	}
195  	r.Lsh(r, 1)
196  	v := new(big.Int).Mul(u1, i)
197
198  	x3.Set(r)
199  	x3.Mul(x3, x3)
200  	x3.Sub(x3, j)
201  	x3.Sub(x3, v)
202  	x3.Sub(x3, v)
203  	x3.Mod(x3, curve.P)
204
205  	y3.Set(r)
206  	v.Sub(v, x3)
207  	y3.Mul(y3, v)
208  	s1.Mul(s1, j)
209  	s1.Lsh(s1, 1)
210  	y3.Sub(y3, s1)
211  	y3.Mod(y3, curve.P)
212
214  	z3.Mul(z3, z3)
215  	z3.Sub(z3, z1z1)
216  	z3.Sub(z3, z2z2)
217  	z3.Mul(z3, h)
218  	z3.Mod(z3, curve.P)
219
220  	return x3, y3, z3
221  }
222
223  func (curve *CurveParams) Double(x1, y1 *big.Int) (*big.Int, *big.Int) {
224  	// If there is a dedicated constant-time implementation for this curve operation,
225  	// use that instead of the generic one.
226  	if specific, ok := matchesSpecificCurve(curve, p224, p384, p521); ok {
227  		return specific.Double(x1, y1)
228  	}
229
230  	z1 := zForAffine(x1, y1)
231  	return curve.affineFromJacobian(curve.doubleJacobian(x1, y1, z1))
232  }
233
234  // doubleJacobian takes a point in Jacobian coordinates, (x, y, z), and
235  // returns its double, also in Jacobian form.
236  func (curve *CurveParams) doubleJacobian(x, y, z *big.Int) (*big.Int, *big.Int, *big.Int) {
237  	// See https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-2001-b
238  	delta := new(big.Int).Mul(z, z)
239  	delta.Mod(delta, curve.P)
240  	gamma := new(big.Int).Mul(y, y)
241  	gamma.Mod(gamma, curve.P)
242  	alpha := new(big.Int).Sub(x, delta)
243  	if alpha.Sign() == -1 {
245  	}
247  	alpha.Mul(alpha, alpha2)
248  	alpha2.Set(alpha)
249  	alpha.Lsh(alpha, 1)
251
252  	beta := alpha2.Mul(x, gamma)
253
254  	x3 := new(big.Int).Mul(alpha, alpha)
255  	beta8 := new(big.Int).Lsh(beta, 3)
256  	beta8.Mod(beta8, curve.P)
257  	x3.Sub(x3, beta8)
258  	if x3.Sign() == -1 {
260  	}
261  	x3.Mod(x3, curve.P)
262
264  	z3.Mul(z3, z3)
265  	z3.Sub(z3, gamma)
266  	if z3.Sign() == -1 {
268  	}
269  	z3.Sub(z3, delta)
270  	if z3.Sign() == -1 {
272  	}
273  	z3.Mod(z3, curve.P)
274
275  	beta.Lsh(beta, 2)
276  	beta.Sub(beta, x3)
277  	if beta.Sign() == -1 {
279  	}
280  	y3 := alpha.Mul(alpha, beta)
281
282  	gamma.Mul(gamma, gamma)
283  	gamma.Lsh(gamma, 3)
284  	gamma.Mod(gamma, curve.P)
285
286  	y3.Sub(y3, gamma)
287  	if y3.Sign() == -1 {
289  	}
290  	y3.Mod(y3, curve.P)
291
292  	return x3, y3, z3
293  }
294
295  func (curve *CurveParams) ScalarMult(Bx, By *big.Int, k []byte) (*big.Int, *big.Int) {
296  	// If there is a dedicated constant-time implementation for this curve operation,
297  	// use that instead of the generic one.
298  	if specific, ok := matchesSpecificCurve(curve, p224, p256, p384, p521); ok {
299  		return specific.ScalarMult(Bx, By, k)
300  	}
301
302  	Bz := new(big.Int).SetInt64(1)
303  	x, y, z := new(big.Int), new(big.Int), new(big.Int)
304
305  	for _, byte := range k {
306  		for bitNum := 0; bitNum < 8; bitNum++ {
307  			x, y, z = curve.doubleJacobian(x, y, z)
308  			if byte&0x80 == 0x80 {
309  				x, y, z = curve.addJacobian(Bx, By, Bz, x, y, z)
310  			}
311  			byte <<= 1
312  		}
313  	}
314
315  	return curve.affineFromJacobian(x, y, z)
316  }
317
318  func (curve *CurveParams) ScalarBaseMult(k []byte) (*big.Int, *big.Int) {
319  	// If there is a dedicated constant-time implementation for this curve operation,
320  	// use that instead of the generic one.
321  	if specific, ok := matchesSpecificCurve(curve, p224, p256, p384, p521); ok {
322  		return specific.ScalarBaseMult(k)
323  	}
324
325  	return curve.ScalarMult(curve.Gx, curve.Gy, k)
326  }
327
328  var mask = []byte{0xff, 0x1, 0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f}
329
330  // GenerateKey returns a public/private key pair. The private key is
331  // generated using the given reader, which must return random data.
332  func GenerateKey(curve Curve, rand io.Reader) (priv []byte, x, y *big.Int, err error) {
333  	N := curve.Params().N
334  	bitSize := N.BitLen()
335  	byteLen := (bitSize + 7) / 8
336  	priv = make([]byte, byteLen)
337
338  	for x == nil {
339  		_, err = io.ReadFull(rand, priv)
340  		if err != nil {
341  			return
342  		}
343  		// We have to mask off any excess bits in the case that the size of the
344  		// underlying field is not a whole number of bytes.
346  		// This is because, in tests, rand will return all zeros and we don't
347  		// want to get the point at infinity and loop forever.
348  		priv[1] ^= 0x42
349
350  		// If the scalar is out of range, sample another random number.
351  		if new(big.Int).SetBytes(priv).Cmp(N) >= 0 {
352  			continue
353  		}
354
355  		x, y = curve.ScalarBaseMult(priv)
356  	}
357  	return
358  }
359
360  // Marshal converts a point on the curve into the uncompressed form specified in
361  // SEC 1, Version 2.0, Section 2.3.3. If the point is not on the curve (or is
362  // the conventional point at infinity), the behavior is undefined.
363  func Marshal(curve Curve, x, y *big.Int) []byte {
364  	byteLen := (curve.Params().BitSize + 7) / 8
365
366  	ret := make([]byte, 1+2*byteLen)
367  	ret[0] = 4 // uncompressed point
368
369  	x.FillBytes(ret[1 : 1+byteLen])
370  	y.FillBytes(ret[1+byteLen : 1+2*byteLen])
371
372  	return ret
373  }
374
375  // MarshalCompressed converts a point on the curve into the compressed form
376  // specified in SEC 1, Version 2.0, Section 2.3.3. If the point is not on the
377  // curve (or is the conventional point at infinity), the behavior is undefined.
378  func MarshalCompressed(curve Curve, x, y *big.Int) []byte {
379  	byteLen := (curve.Params().BitSize + 7) / 8
380  	compressed := make([]byte, 1+byteLen)
381  	compressed[0] = byte(y.Bit(0)) | 2
382  	x.FillBytes(compressed[1:])
383  	return compressed
384  }
385
386  // Unmarshal converts a point, serialized by Marshal, into an x, y pair. It is
387  // an error if the point is not in uncompressed form, is not on the curve, or is
388  // the point at infinity. On error, x = nil.
389  func Unmarshal(curve Curve, data []byte) (x, y *big.Int) {
390  	byteLen := (curve.Params().BitSize + 7) / 8
391  	if len(data) != 1+2*byteLen {
392  		return nil, nil
393  	}
394  	if data[0] != 4 { // uncompressed form
395  		return nil, nil
396  	}
397  	p := curve.Params().P
398  	x = new(big.Int).SetBytes(data[1 : 1+byteLen])
399  	y = new(big.Int).SetBytes(data[1+byteLen:])
400  	if x.Cmp(p) >= 0 || y.Cmp(p) >= 0 {
401  		return nil, nil
402  	}
403  	if !curve.IsOnCurve(x, y) {
404  		return nil, nil
405  	}
406  	return
407  }
408
409  // UnmarshalCompressed converts a point, serialized by MarshalCompressed, into
410  // an x, y pair. It is an error if the point is not in compressed form, is not
411  // on the curve, or is the point at infinity. On error, x = nil.
412  func UnmarshalCompressed(curve Curve, data []byte) (x, y *big.Int) {
413  	byteLen := (curve.Params().BitSize + 7) / 8
414  	if len(data) != 1+byteLen {
415  		return nil, nil
416  	}
417  	if data[0] != 2 && data[0] != 3 { // compressed form
418  		return nil, nil
419  	}
420  	p := curve.Params().P
421  	x = new(big.Int).SetBytes(data[1:])
422  	if x.Cmp(p) >= 0 {
423  		return nil, nil
424  	}
425  	// y² = x³ - 3x + b
426  	y = curve.Params().polynomial(x)
427  	y = y.ModSqrt(y, p)
428  	if y == nil {
429  		return nil, nil
430  	}
431  	if byte(y.Bit(0)) != data[0]&1 {
432  		y.Neg(y).Mod(y, p)
433  	}
434  	if !curve.IsOnCurve(x, y) {
435  		return nil, nil
436  	}
437  	return
438  }
439
440  var initonce sync.Once
441
442  func initAll() {
443  	initP224()
444  	initP256()
445  	initP384()
446  	initP521()
447  }
448
449  // P224 returns a Curve which implements NIST P-224 (FIPS 186-3, section D.2.2),
450  // also known as secp224r1. The CurveParams.Name of this Curve is "P-224".
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 are implemented using constant-time algorithms.
456  func P224() Curve {
457  	initonce.Do(initAll)
458  	return p224
459  }
460
461  // P256 returns a Curve which implements NIST P-256 (FIPS 186-3, section D.2.3),
462  // also known as secp256r1 or prime256v1. The CurveParams.Name of this Curve is
463  // "P-256".
464  //
465  // Multiple invocations of this function will return the same value, so it can
466  // be used for equality checks and switch statements.
467  //
468  // ScalarMult and ScalarBaseMult are implemented using constant-time algorithms.
469  func P256() Curve {
470  	initonce.Do(initAll)
471  	return p256
472  }
473
474  // P384 returns a Curve which implements NIST P-384 (FIPS 186-3, section D.2.4),
475  // also known as secp384r1. The CurveParams.Name of this Curve is "P-384".
476  //
477  // Multiple invocations of this function will return the same value, so it can
478  // be used for equality checks and switch statements.
479  //
480  // The cryptographic operations are implemented using constant-time algorithms.
481  func P384() Curve {
482  	initonce.Do(initAll)
483  	return p384
484  }
485
486  // P521 returns a Curve which implements NIST P-521 (FIPS 186-3, section D.2.5),
487  // also known as secp521r1. The CurveParams.Name of this Curve is "P-521".
488  //
489  // Multiple invocations of this function will return the same value, so it can
490  // be used for equality checks and switch statements.
491  //
492  // The cryptographic operations are implemented using constant-time algorithms.
493  func P521() Curve {
494  	initonce.Do(initAll)
495  	return p521
496  }
497
```

View as plain text