src/crypto/elliptic/params.go

   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 }