# 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
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