...

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

View as plain text