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