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  }
   335
View as plain text