Source file src/pkg/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 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 http://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 returns true if 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	}
49
50	func (curve *CurveParams) Params() *CurveParams {
51		return curve
52	}
53
54	func (curve *CurveParams) IsOnCurve(x, y *big.Int) bool {
55		// y² = x³ - 3x + b
56		y2 := new(big.Int).Mul(y, y)
57		y2.Mod(y2, curve.P)
58
59		x3 := new(big.Int).Mul(x, x)
60		x3.Mul(x3, x)
61
62		threeX := new(big.Int).Lsh(x, 1)
64
65		x3.Sub(x3, threeX)
67		x3.Mod(x3, curve.P)
68
69		return x3.Cmp(y2) == 0
70	}
71
72	// zForAffine returns a Jacobian Z value for the affine point (x, y). If x and
73	// y are zero, it assumes that they represent the point at infinity because (0,
74	// 0) is not on the any of the curves handled here.
75	func zForAffine(x, y *big.Int) *big.Int {
76		z := new(big.Int)
77		if x.Sign() != 0 || y.Sign() != 0 {
78			z.SetInt64(1)
79		}
80		return z
81	}
82
83	// affineFromJacobian reverses the Jacobian transform. See the comment at the
84	// top of the file. If the point is ∞ it returns 0, 0.
85	func (curve *CurveParams) affineFromJacobian(x, y, z *big.Int) (xOut, yOut *big.Int) {
86		if z.Sign() == 0 {
87			return new(big.Int), new(big.Int)
88		}
89
90		zinv := new(big.Int).ModInverse(z, curve.P)
91		zinvsq := new(big.Int).Mul(zinv, zinv)
92
93		xOut = new(big.Int).Mul(x, zinvsq)
94		xOut.Mod(xOut, curve.P)
95		zinvsq.Mul(zinvsq, zinv)
96		yOut = new(big.Int).Mul(y, zinvsq)
97		yOut.Mod(yOut, curve.P)
98		return
99	}
100
101	func (curve *CurveParams) Add(x1, y1, x2, y2 *big.Int) (*big.Int, *big.Int) {
102		z1 := zForAffine(x1, y1)
103		z2 := zForAffine(x2, y2)
104		return curve.affineFromJacobian(curve.addJacobian(x1, y1, z1, x2, y2, z2))
105	}
106
107	// addJacobian takes two points in Jacobian coordinates, (x1, y1, z1) and
108	// (x2, y2, z2) and returns their sum, also in Jacobian form.
109	func (curve *CurveParams) addJacobian(x1, y1, z1, x2, y2, z2 *big.Int) (*big.Int, *big.Int, *big.Int) {
111		x3, y3, z3 := new(big.Int), new(big.Int), new(big.Int)
112		if z1.Sign() == 0 {
113			x3.Set(x2)
114			y3.Set(y2)
115			z3.Set(z2)
116			return x3, y3, z3
117		}
118		if z2.Sign() == 0 {
119			x3.Set(x1)
120			y3.Set(y1)
121			z3.Set(z1)
122			return x3, y3, z3
123		}
124
125		z1z1 := new(big.Int).Mul(z1, z1)
126		z1z1.Mod(z1z1, curve.P)
127		z2z2 := new(big.Int).Mul(z2, z2)
128		z2z2.Mod(z2z2, curve.P)
129
130		u1 := new(big.Int).Mul(x1, z2z2)
131		u1.Mod(u1, curve.P)
132		u2 := new(big.Int).Mul(x2, z1z1)
133		u2.Mod(u2, curve.P)
134		h := new(big.Int).Sub(u2, u1)
135		xEqual := h.Sign() == 0
136		if h.Sign() == -1 {
138		}
139		i := new(big.Int).Lsh(h, 1)
140		i.Mul(i, i)
141		j := new(big.Int).Mul(h, i)
142
143		s1 := new(big.Int).Mul(y1, z2)
144		s1.Mul(s1, z2z2)
145		s1.Mod(s1, curve.P)
146		s2 := new(big.Int).Mul(y2, z1)
147		s2.Mul(s2, z1z1)
148		s2.Mod(s2, curve.P)
149		r := new(big.Int).Sub(s2, s1)
150		if r.Sign() == -1 {
152		}
153		yEqual := r.Sign() == 0
154		if xEqual && yEqual {
155			return curve.doubleJacobian(x1, y1, z1)
156		}
157		r.Lsh(r, 1)
158		v := new(big.Int).Mul(u1, i)
159
160		x3.Set(r)
161		x3.Mul(x3, x3)
162		x3.Sub(x3, j)
163		x3.Sub(x3, v)
164		x3.Sub(x3, v)
165		x3.Mod(x3, curve.P)
166
167		y3.Set(r)
168		v.Sub(v, x3)
169		y3.Mul(y3, v)
170		s1.Mul(s1, j)
171		s1.Lsh(s1, 1)
172		y3.Sub(y3, s1)
173		y3.Mod(y3, curve.P)
174
176		z3.Mul(z3, z3)
177		z3.Sub(z3, z1z1)
178		z3.Sub(z3, z2z2)
179		z3.Mul(z3, h)
180		z3.Mod(z3, curve.P)
181
182		return x3, y3, z3
183	}
184
185	func (curve *CurveParams) Double(x1, y1 *big.Int) (*big.Int, *big.Int) {
186		z1 := zForAffine(x1, y1)
187		return curve.affineFromJacobian(curve.doubleJacobian(x1, y1, z1))
188	}
189
190	// doubleJacobian takes a point in Jacobian coordinates, (x, y, z), and
191	// returns its double, also in Jacobian form.
192	func (curve *CurveParams) doubleJacobian(x, y, z *big.Int) (*big.Int, *big.Int, *big.Int) {
193		// See http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-2001-b
194		delta := new(big.Int).Mul(z, z)
195		delta.Mod(delta, curve.P)
196		gamma := new(big.Int).Mul(y, y)
197		gamma.Mod(gamma, curve.P)
198		alpha := new(big.Int).Sub(x, delta)
199		if alpha.Sign() == -1 {
201		}
203		alpha.Mul(alpha, alpha2)
204		alpha2.Set(alpha)
205		alpha.Lsh(alpha, 1)
207
208		beta := alpha2.Mul(x, gamma)
209
210		x3 := new(big.Int).Mul(alpha, alpha)
211		beta8 := new(big.Int).Lsh(beta, 3)
212		x3.Sub(x3, beta8)
213		for x3.Sign() == -1 {
215		}
216		x3.Mod(x3, curve.P)
217
219		z3.Mul(z3, z3)
220		z3.Sub(z3, gamma)
221		if z3.Sign() == -1 {
223		}
224		z3.Sub(z3, delta)
225		if z3.Sign() == -1 {
227		}
228		z3.Mod(z3, curve.P)
229
230		beta.Lsh(beta, 2)
231		beta.Sub(beta, x3)
232		if beta.Sign() == -1 {
234		}
235		y3 := alpha.Mul(alpha, beta)
236
237		gamma.Mul(gamma, gamma)
238		gamma.Lsh(gamma, 3)
239		gamma.Mod(gamma, curve.P)
240
241		y3.Sub(y3, gamma)
242		if y3.Sign() == -1 {
244		}
245		y3.Mod(y3, curve.P)
246
247		return x3, y3, z3
248	}
249
250	func (curve *CurveParams) ScalarMult(Bx, By *big.Int, k []byte) (*big.Int, *big.Int) {
251		Bz := new(big.Int).SetInt64(1)
252		x, y, z := new(big.Int), new(big.Int), new(big.Int)
253
254		for _, byte := range k {
255			for bitNum := 0; bitNum < 8; bitNum++ {
256				x, y, z = curve.doubleJacobian(x, y, z)
257				if byte&0x80 == 0x80 {
258					x, y, z = curve.addJacobian(Bx, By, Bz, x, y, z)
259				}
260				byte <<= 1
261			}
262		}
263
264		return curve.affineFromJacobian(x, y, z)
265	}
266
267	func (curve *CurveParams) ScalarBaseMult(k []byte) (*big.Int, *big.Int) {
268		return curve.ScalarMult(curve.Gx, curve.Gy, k)
269	}
270
271	var mask = []byte{0xff, 0x1, 0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f}
272
273	// GenerateKey returns a public/private key pair. The private key is
274	// generated using the given reader, which must return random data.
275	func GenerateKey(curve Curve, rand io.Reader) (priv []byte, x, y *big.Int, err error) {
276		bitSize := curve.Params().BitSize
277		byteLen := (bitSize + 7) >> 3
278		priv = make([]byte, byteLen)
279
280		for x == nil {
281			_, err = io.ReadFull(rand, priv)
282			if err != nil {
283				return
284			}
285			// We have to mask off any excess bits in the case that the size of the
286			// underlying field is not a whole number of bytes.
288			// This is because, in tests, rand will return all zeros and we don't
289			// want to get the point at infinity and loop forever.
290			priv[1] ^= 0x42
291			x, y = curve.ScalarBaseMult(priv)
292		}
293		return
294	}
295
296	// Marshal converts a point into the form specified in section 4.3.6 of ANSI X9.62.
297	func Marshal(curve Curve, x, y *big.Int) []byte {
298		byteLen := (curve.Params().BitSize + 7) >> 3
299
300		ret := make([]byte, 1+2*byteLen)
301		ret[0] = 4 // uncompressed point
302
303		xBytes := x.Bytes()
304		copy(ret[1+byteLen-len(xBytes):], xBytes)
305		yBytes := y.Bytes()
306		copy(ret[1+2*byteLen-len(yBytes):], yBytes)
307		return ret
308	}
309
310	// Unmarshal converts a point, serialized by Marshal, into an x, y pair. On error, x = nil.
311	func Unmarshal(curve Curve, data []byte) (x, y *big.Int) {
312		byteLen := (curve.Params().BitSize + 7) >> 3
313		if len(data) != 1+2*byteLen {
314			return
315		}
316		if data[0] != 4 { // uncompressed form
317			return
318		}
319		x = new(big.Int).SetBytes(data[1 : 1+byteLen])
320		y = new(big.Int).SetBytes(data[1+byteLen:])
321		return
322	}
323
324	var initonce sync.Once
325	var p384 *CurveParams
326	var p521 *CurveParams
327
328	func initAll() {
329		initP224()
330		initP256()
331		initP384()
332		initP521()
333	}
334
335	func initP384() {
336		// See FIPS 186-3, section D.2.4
337		p384 = new(CurveParams)
338		p384.P, _ = new(big.Int).SetString("39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319", 10)
339		p384.N, _ = new(big.Int).SetString("39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643", 10)
340		p384.B, _ = new(big.Int).SetString("b3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef", 16)
341		p384.Gx, _ = new(big.Int).SetString("aa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7", 16)
342		p384.Gy, _ = new(big.Int).SetString("3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f", 16)
343		p384.BitSize = 384
344	}
345
346	func initP521() {
347		// See FIPS 186-3, section D.2.5
348		p521 = new(CurveParams)
349		p521.P, _ = new(big.Int).SetString("6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151", 10)
350		p521.N, _ = new(big.Int).SetString("6864797660130609714981900799081393217269435300143305409394463459185543183397655394245057746333217197532963996371363321113864768612440380340372808892707005449", 10)
351		p521.B, _ = new(big.Int).SetString("051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00", 16)
352		p521.Gx, _ = new(big.Int).SetString("c6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66", 16)
353		p521.Gy, _ = new(big.Int).SetString("11839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650", 16)
354		p521.BitSize = 521
355	}
356
357	// P256 returns a Curve which implements P-256 (see FIPS 186-3, section D.2.3)
358	func P256() Curve {
359		initonce.Do(initAll)
360		return p256
361	}
362
363	// P384 returns a Curve which implements P-384 (see FIPS 186-3, section D.2.4)
364	func P384() Curve {
365		initonce.Do(initAll)
366		return p384
367	}
368
369	// P521 returns a Curve which implements P-521 (see FIPS 186-3, section D.2.5)
370	func P521() Curve {
371		initonce.Do(initAll)
372		return p521
373	}
```

View as plain text