...

Source file src/crypto/elliptic/params.go

Documentation: crypto/elliptic

```     1  // Copyright 2021 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
6
7  import "math/big"
8
9  // CurveParams contains the parameters of an elliptic curve and also provides
10  // a generic, non-constant time implementation of [Curve].
11  //
12  // The generic Curve implementation is deprecated, and using custom curves
13  // (those not returned by [P224], [P256], [P384], and [P521]) is not guaranteed
14  // to provide any security property.
15  type CurveParams struct {
16  	P       *big.Int // the order of the underlying field
17  	N       *big.Int // the order of the base point
18  	B       *big.Int // the constant of the curve equation
19  	Gx, Gy  *big.Int // (x,y) of the base point
20  	BitSize int      // the size of the underlying field
21  	Name    string   // the canonical name of the curve
22  }
23
24  func (curve *CurveParams) Params() *CurveParams {
25  	return curve
26  }
27
28  // CurveParams operates, internally, on Jacobian coordinates. For a given
29  // (x, y) position on the curve, the Jacobian coordinates are (x1, y1, z1)
30  // where x = x1/z1² and y = y1/z1³. The greatest speedups come when the whole
31  // calculation can be performed within the transform (as in ScalarMult and
32  // ScalarBaseMult). But even for Add and Double, it's faster to apply and
33  // reverse the transform than to operate in affine coordinates.
34
35  // polynomial returns x³ - 3x + b.
36  func (curve *CurveParams) polynomial(x *big.Int) *big.Int {
37  	x3 := new(big.Int).Mul(x, x)
38  	x3.Mul(x3, x)
39
40  	threeX := new(big.Int).Lsh(x, 1)
41  	threeX.Add(threeX, x)
42
43  	x3.Sub(x3, threeX)
44  	x3.Add(x3, curve.B)
45  	x3.Mod(x3, curve.P)
46
47  	return x3
48  }
49
50  // IsOnCurve implements [Curve.IsOnCurve].
51  //
52  // Deprecated: the [CurveParams] methods are deprecated and are not guaranteed to
53  // provide any security property. For ECDH, use the [crypto/ecdh] package.
54  // For ECDSA, use the [crypto/ecdsa] package with a [Curve] value returned directly
55  // from [P224], [P256], [P384], or [P521].
56  func (curve *CurveParams) IsOnCurve(x, y *big.Int) bool {
57  	// If there is a dedicated constant-time implementation for this curve operation,
58  	// use that instead of the generic one.
59  	if specific, ok := matchesSpecificCurve(curve); ok {
60  		return specific.IsOnCurve(x, y)
61  	}
62
63  	if x.Sign() < 0 || x.Cmp(curve.P) >= 0 ||
64  		y.Sign() < 0 || y.Cmp(curve.P) >= 0 {
65  		return false
66  	}
67
68  	// y² = x³ - 3x + b
69  	y2 := new(big.Int).Mul(y, y)
70  	y2.Mod(y2, curve.P)
71
72  	return curve.polynomial(x).Cmp(y2) == 0
73  }
74
75  // zForAffine returns a Jacobian Z value for the affine point (x, y). If x and
76  // y are zero, it assumes that they represent the point at infinity because (0,
77  // 0) is not on the any of the curves handled here.
78  func zForAffine(x, y *big.Int) *big.Int {
79  	z := new(big.Int)
80  	if x.Sign() != 0 || y.Sign() != 0 {
81  		z.SetInt64(1)
82  	}
83  	return z
84  }
85
86  // affineFromJacobian reverses the Jacobian transform. See the comment at the
87  // top of the file. If the point is ∞ it returns 0, 0.
88  func (curve *CurveParams) affineFromJacobian(x, y, z *big.Int) (xOut, yOut *big.Int) {
89  	if z.Sign() == 0 {
90  		return new(big.Int), new(big.Int)
91  	}
92
93  	zinv := new(big.Int).ModInverse(z, curve.P)
94  	zinvsq := new(big.Int).Mul(zinv, zinv)
95
96  	xOut = new(big.Int).Mul(x, zinvsq)
97  	xOut.Mod(xOut, curve.P)
98  	zinvsq.Mul(zinvsq, zinv)
99  	yOut = new(big.Int).Mul(y, zinvsq)
100  	yOut.Mod(yOut, curve.P)
101  	return
102  }
103
104  // Add implements [Curve.Add].
105  //
106  // Deprecated: the [CurveParams] methods are deprecated and are not guaranteed to
107  // provide any security property. For ECDH, use the [crypto/ecdh] package.
108  // For ECDSA, use the [crypto/ecdsa] package with a [Curve] value returned directly
109  // from [P224], [P256], [P384], or [P521].
110  func (curve *CurveParams) Add(x1, y1, x2, y2 *big.Int) (*big.Int, *big.Int) {
111  	// If there is a dedicated constant-time implementation for this curve operation,
112  	// use that instead of the generic one.
113  	if specific, ok := matchesSpecificCurve(curve); ok {
114  		return specific.Add(x1, y1, x2, y2)
115  	}
116  	panicIfNotOnCurve(curve, x1, y1)
117  	panicIfNotOnCurve(curve, x2, y2)
118
119  	z1 := zForAffine(x1, y1)
120  	z2 := zForAffine(x2, y2)
121  	return curve.affineFromJacobian(curve.addJacobian(x1, y1, z1, x2, y2, z2))
122  }
123
124  // addJacobian takes two points in Jacobian coordinates, (x1, y1, z1) and
125  // (x2, y2, z2) and returns their sum, also in Jacobian form.
126  func (curve *CurveParams) addJacobian(x1, y1, z1, x2, y2, z2 *big.Int) (*big.Int, *big.Int, *big.Int) {
127  	// See https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-2007-bl
128  	x3, y3, z3 := new(big.Int), new(big.Int), new(big.Int)
129  	if z1.Sign() == 0 {
130  		x3.Set(x2)
131  		y3.Set(y2)
132  		z3.Set(z2)
133  		return x3, y3, z3
134  	}
135  	if z2.Sign() == 0 {
136  		x3.Set(x1)
137  		y3.Set(y1)
138  		z3.Set(z1)
139  		return x3, y3, z3
140  	}
141
142  	z1z1 := new(big.Int).Mul(z1, z1)
143  	z1z1.Mod(z1z1, curve.P)
144  	z2z2 := new(big.Int).Mul(z2, z2)
145  	z2z2.Mod(z2z2, curve.P)
146
147  	u1 := new(big.Int).Mul(x1, z2z2)
148  	u1.Mod(u1, curve.P)
149  	u2 := new(big.Int).Mul(x2, z1z1)
150  	u2.Mod(u2, curve.P)
151  	h := new(big.Int).Sub(u2, u1)
152  	xEqual := h.Sign() == 0
153  	if h.Sign() == -1 {
154  		h.Add(h, curve.P)
155  	}
156  	i := new(big.Int).Lsh(h, 1)
157  	i.Mul(i, i)
158  	j := new(big.Int).Mul(h, i)
159
160  	s1 := new(big.Int).Mul(y1, z2)
161  	s1.Mul(s1, z2z2)
162  	s1.Mod(s1, curve.P)
163  	s2 := new(big.Int).Mul(y2, z1)
164  	s2.Mul(s2, z1z1)
165  	s2.Mod(s2, curve.P)
166  	r := new(big.Int).Sub(s2, s1)
167  	if r.Sign() == -1 {
168  		r.Add(r, curve.P)
169  	}
170  	yEqual := r.Sign() == 0
171  	if xEqual && yEqual {
172  		return curve.doubleJacobian(x1, y1, z1)
173  	}
174  	r.Lsh(r, 1)
175  	v := new(big.Int).Mul(u1, i)
176
177  	x3.Set(r)
178  	x3.Mul(x3, x3)
179  	x3.Sub(x3, j)
180  	x3.Sub(x3, v)
181  	x3.Sub(x3, v)
182  	x3.Mod(x3, curve.P)
183
184  	y3.Set(r)
185  	v.Sub(v, x3)
186  	y3.Mul(y3, v)
187  	s1.Mul(s1, j)
188  	s1.Lsh(s1, 1)
189  	y3.Sub(y3, s1)
190  	y3.Mod(y3, curve.P)
191
192  	z3.Add(z1, z2)
193  	z3.Mul(z3, z3)
194  	z3.Sub(z3, z1z1)
195  	z3.Sub(z3, z2z2)
196  	z3.Mul(z3, h)
197  	z3.Mod(z3, curve.P)
198
199  	return x3, y3, z3
200  }
201
202  // Double implements [Curve.Double].
203  //
204  // Deprecated: the [CurveParams】 methods are deprecated and are not guaranteed to
205  // provide any security property. For ECDH, use the [crypto/ecdh] package.
206  // For ECDSA, use the [crypto/ecdsa] package with a [Curve] value returned directly
207  // from [P224], [P256], [P384], or [P521].
208  func (curve *CurveParams) Double(x1, y1 *big.Int) (*big.Int, *big.Int) {
209  	// If there is a dedicated constant-time implementation for this curve operation,
210  	// use that instead of the generic one.
211  	if specific, ok := matchesSpecificCurve(curve); ok {
212  		return specific.Double(x1, y1)
213  	}
214  	panicIfNotOnCurve(curve, x1, y1)
215
216  	z1 := zForAffine(x1, y1)
217  	return curve.affineFromJacobian(curve.doubleJacobian(x1, y1, z1))
218  }
219
220  // doubleJacobian takes a point in Jacobian coordinates, (x, y, z), and
221  // returns its double, also in Jacobian form.
222  func (curve *CurveParams) doubleJacobian(x, y, z *big.Int) (*big.Int, *big.Int, *big.Int) {
223  	// See https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-2001-b
224  	delta := new(big.Int).Mul(z, z)
225  	delta.Mod(delta, curve.P)
226  	gamma := new(big.Int).Mul(y, y)
227  	gamma.Mod(gamma, curve.P)
228  	alpha := new(big.Int).Sub(x, delta)
229  	if alpha.Sign() == -1 {
230  		alpha.Add(alpha, curve.P)
231  	}
232  	alpha2 := new(big.Int).Add(x, delta)
233  	alpha.Mul(alpha, alpha2)
234  	alpha2.Set(alpha)
235  	alpha.Lsh(alpha, 1)
236  	alpha.Add(alpha, alpha2)
237
238  	beta := alpha2.Mul(x, gamma)
239
240  	x3 := new(big.Int).Mul(alpha, alpha)
241  	beta8 := new(big.Int).Lsh(beta, 3)
242  	beta8.Mod(beta8, curve.P)
243  	x3.Sub(x3, beta8)
244  	if x3.Sign() == -1 {
245  		x3.Add(x3, curve.P)
246  	}
247  	x3.Mod(x3, curve.P)
248
249  	z3 := new(big.Int).Add(y, z)
250  	z3.Mul(z3, z3)
251  	z3.Sub(z3, gamma)
252  	if z3.Sign() == -1 {
253  		z3.Add(z3, curve.P)
254  	}
255  	z3.Sub(z3, delta)
256  	if z3.Sign() == -1 {
257  		z3.Add(z3, curve.P)
258  	}
259  	z3.Mod(z3, curve.P)
260
261  	beta.Lsh(beta, 2)
262  	beta.Sub(beta, x3)
263  	if beta.Sign() == -1 {
264  		beta.Add(beta, curve.P)
265  	}
266  	y3 := alpha.Mul(alpha, beta)
267
268  	gamma.Mul(gamma, gamma)
269  	gamma.Lsh(gamma, 3)
270  	gamma.Mod(gamma, curve.P)
271
272  	y3.Sub(y3, gamma)
273  	if y3.Sign() == -1 {
274  		y3.Add(y3, curve.P)
275  	}
276  	y3.Mod(y3, curve.P)
277
278  	return x3, y3, z3
279  }
280
281  // ScalarMult implements [Curve.ScalarMult].
282  //
283  // Deprecated: the [CurveParams] methods are deprecated and are not guaranteed to
284  // provide any security property. For ECDH, use the [crypto/ecdh] package.
285  // For ECDSA, use the [crypto/ecdsa] package with a [Curve] value returned directly
286  // from [P224], [P256], [P384], or [P521].
287  func (curve *CurveParams) ScalarMult(Bx, By *big.Int, k []byte) (*big.Int, *big.Int) {
288  	// If there is a dedicated constant-time implementation for this curve operation,
289  	// use that instead of the generic one.
290  	if specific, ok := matchesSpecificCurve(curve); ok {
291  		return specific.ScalarMult(Bx, By, k)
292  	}
293  	panicIfNotOnCurve(curve, Bx, By)
294
295  	Bz := new(big.Int).SetInt64(1)
296  	x, y, z := new(big.Int), new(big.Int), new(big.Int)
297
298  	for _, byte := range k {
299  		for bitNum := 0; bitNum < 8; bitNum++ {
300  			x, y, z = curve.doubleJacobian(x, y, z)
301  			if byte&0x80 == 0x80 {
302  				x, y, z = curve.addJacobian(Bx, By, Bz, x, y, z)
303  			}
304  			byte <<= 1
305  		}
306  	}
307
308  	return curve.affineFromJacobian(x, y, z)
309  }
310
311  // ScalarBaseMult implements [Curve.ScalarBaseMult].
312  //
313  // Deprecated: the [CurveParams] methods are deprecated and are not guaranteed to
314  // provide any security property. For ECDH, use the [crypto/ecdh] package.
315  // For ECDSA, use the [crypto/ecdsa] package with a [Curve] value returned directly
316  // from [P224], [P256], [P384], or [P521].
317  func (curve *CurveParams) ScalarBaseMult(k []byte) (*big.Int, *big.Int) {
318  	// If there is a dedicated constant-time implementation for this curve operation,
319  	// use that instead of the generic one.
320  	if specific, ok := matchesSpecificCurve(curve); ok {
321  		return specific.ScalarBaseMult(k)
322  	}
323
324  	return curve.ScalarMult(curve.Gx, curve.Gy, k)
325  }
326
327  func matchesSpecificCurve(params *CurveParams) (Curve, bool) {
328  	for _, c := range []Curve{p224, p256, p384, p521} {
329  		if params == c.Params() {
330  			return c, true
331  		}
332  	}
333  	return nil, false
334  }
335
```

View as plain text