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 []byte // 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 := (&big.Int{}).Mul(x, x)
38 x3.Mul(x3, x)
39 40 threeX := (&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 := (&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 := &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 &big.Int{}, &big.Int{}
91 }
92 93 zinv := (&big.Int{}).ModInverse(z, curve.P)
94 zinvsq := (&big.Int{}).Mul(zinv, zinv)
95 96 xOut = (&big.Int{}).Mul(x, zinvsq)
97 xOut.Mod(xOut, curve.P)
98 zinvsq.Mul(zinvsq, zinv)
99 yOut = (&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 := &big.Int{}, &big.Int{}, &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 := (&big.Int{}).Mul(z1, z1)
143 z1z1.Mod(z1z1, curve.P)
144 z2z2 := (&big.Int{}).Mul(z2, z2)
145 z2z2.Mod(z2z2, curve.P)
146 147 u1 := (&big.Int{}).Mul(x1, z2z2)
148 u1.Mod(u1, curve.P)
149 u2 := (&big.Int{}).Mul(x2, z1z1)
150 u2.Mod(u2, curve.P)
151 h := (&big.Int{}).Sub(u2, u1)
152 xEqual := h.Sign() == 0
153 if h.Sign() == -1 {
154 h.Add(h, curve.P)
155 }
156 i := (&big.Int{}).Lsh(h, 1)
157 i.Mul(i, i)
158 j := (&big.Int{}).Mul(h, i)
159 160 s1 := (&big.Int{}).Mul(y1, z2)
161 s1.Mul(s1, z2z2)
162 s1.Mod(s1, curve.P)
163 s2 := (&big.Int{}).Mul(y2, z1)
164 s2.Mul(s2, z1z1)
165 s2.Mod(s2, curve.P)
166 r := (&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 := (&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 := (&big.Int{}).Mul(z, z)
225 delta.Mod(delta, curve.P)
226 gamma := (&big.Int{}).Mul(y, y)
227 gamma.Mod(gamma, curve.P)
228 alpha := (&big.Int{}).Sub(x, delta)
229 if alpha.Sign() == -1 {
230 alpha.Add(alpha, curve.P)
231 }
232 alpha2 := (&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 := (&big.Int{}).Mul(alpha, alpha)
241 beta8 := (&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 := (&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 := (&big.Int{}).SetInt64(1)
296 x, y, z := &big.Int{}, &big.Int{}, &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