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.
7package 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
16import (
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
24type 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.
42type 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
51func (curve *CurveParams) Params() *CurveParams {
52	return curve
53}
54
55func (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.
76func 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.
86func (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
102func (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.
110func (curve *CurveParams) addJacobian(x1, y1, z1, x2, y2, z2 *big.Int) (*big.Int, *big.Int, *big.Int) {
111	// See http://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
186func (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.
193func (curve *CurveParams) doubleJacobian(x, y, z *big.Int) (*big.Int, *big.Int, *big.Int) {
194	// See http://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	x3.Sub(x3, beta8)
214	for x3.Sign() == -1 {
215		x3.Add(x3, curve.P)
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 {
223		z3.Add(z3, curve.P)
224	}
225	z3.Sub(z3, delta)
226	if z3.Sign() == -1 {
227		z3.Add(z3, curve.P)
228	}
229	z3.Mod(z3, curve.P)
230
231	beta.Lsh(beta, 2)
232	beta.Sub(beta, x3)
233	if beta.Sign() == -1 {
234		beta.Add(beta, curve.P)
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 {
244		y3.Add(y3, curve.P)
245	}
246	y3.Mod(y3, curve.P)
247
248	return x3, y3, z3
249}
250
251func (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
268func (curve *CurveParams) ScalarBaseMult(k []byte) (*big.Int, *big.Int) {
269	return curve.ScalarMult(curve.Gx, curve.Gy, k)
270}
271
272var 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.
276func 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.
305func 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.
321func 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
341var initonce sync.Once
342var p384 *CurveParams
343var p521 *CurveParams
344
345func initAll() {
346	initP224()
347	initP256()
348	initP384()
349	initP521()
350}
351
352func 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
363func 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.
377func 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.
385func 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.
393func P521() Curve {
394	initonce.Do(initAll)
395	return p521
396}
397