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