point.go

Documentation: github.com/cloudflare/circl/ecc/p384

     1  //go:build (!noasm && arm64) || (!noasm && amd64)
     2  // +build !noasm,arm64 !noasm,amd64
     3  
     4  package p384
     5  
     6  import (
     7  	"fmt"
     8  	"math/big"
     9  )
    10  
    11  // affinePoint represents an affine point of the curve. The point at
    12  // infinity is (0,0) leveraging that it is not an affine point.
    13  type affinePoint struct{ x, y fp384 }
    14  
    15  func newAffinePoint(x, y *big.Int) *affinePoint {
    16  	var P affinePoint
    17  	P.x.SetBigInt(x)
    18  	P.y.SetBigInt(y)
    19  	montEncode(&P.x, &P.x)
    20  	montEncode(&P.y, &P.y)
    21  	return &P
    22  }
    23  
    24  func zeroPoint() *affinePoint { return &affinePoint{} }
    25  
    26  func (ap affinePoint) String() string {
    27  	if ap.isZero() {
    28  		return "inf"
    29  	}
    30  	return fmt.Sprintf("x: %v\ny: %v", ap.x, ap.y)
    31  }
    32  
    33  func (ap *affinePoint) isZero() bool {
    34  	zero := fp384{}
    35  	return ap.x == zero && ap.y == zero
    36  }
    37  
    38  func (ap *affinePoint) neg() { fp384Neg(&ap.y, &ap.y) }
    39  
    40  func (ap *affinePoint) toInt() (x, y *big.Int) {
    41  	var x1, y1 fp384
    42  	montDecode(&x1, &ap.x)
    43  	montDecode(&y1, &ap.y)
    44  	return x1.BigInt(), y1.BigInt()
    45  }
    46  
    47  func (ap *affinePoint) toJacobian() *jacobianPoint {
    48  	var P jacobianPoint
    49  	if ap.isZero() {
    50  		montEncode(&P.x, &fp384{1})
    51  		montEncode(&P.y, &fp384{1})
    52  	} else {
    53  		P.x = ap.x
    54  		P.y = ap.y
    55  		montEncode(&P.z, &fp384{1})
    56  	}
    57  	return &P
    58  }
    59  
    60  func (ap *affinePoint) toProjective() *projectivePoint {
    61  	var P projectivePoint
    62  	if ap.isZero() {
    63  		montEncode(&P.y, &fp384{1})
    64  	} else {
    65  		P.x = ap.x
    66  		P.y = ap.y
    67  		montEncode(&P.z, &fp384{1})
    68  	}
    69  	return &P
    70  }
    71  
    72  // OddMultiples calculates the points iP for i={1,3,5,7,..., 2^(n-1)-1}
    73  // Ensure that 1 < n < 31, otherwise it returns an empty slice.
    74  func (ap affinePoint) oddMultiples(n uint) []jacobianPoint {
    75  	var t []jacobianPoint
    76  	if n > 1 && n < 31 {
    77  		P := ap.toJacobian()
    78  		s := int32(1) << (n - 1)
    79  		t = make([]jacobianPoint, s)
    80  		t[0] = *P
    81  		_2P := *P
    82  		_2P.double()
    83  		for i := int32(1); i < s; i++ {
    84  			t[i].add(&t[i-1], &_2P)
    85  		}
    86  	}
    87  	return t
    88  }
    89  
    90  // p2Point is a point in P^2
    91  type p2Point struct{ x, y, z fp384 }
    92  
    93  func (P *p2Point) String() string {
    94  	return fmt.Sprintf("x: %v\ny: %v\nz: %v", P.x, P.y, P.z)
    95  }
    96  
    97  func (P *p2Point) neg() { fp384Neg(&P.y, &P.y) }
    98  
    99  // condNeg if P is negated if b=1.
   100  func (P *p2Point) cneg(b int) {
   101  	var mY fp384
   102  	fp384Neg(&mY, &P.y)
   103  	fp384Cmov(&P.y, &mY, b)
   104  }
   105  
   106  // cmov sets P to Q if b=1.
   107  func (P *p2Point) cmov(Q *p2Point, b int) {
   108  	fp384Cmov(&P.x, &Q.x, b)
   109  	fp384Cmov(&P.y, &Q.y, b)
   110  	fp384Cmov(&P.z, &Q.z, b)
   111  }
   112  
   113  func (P *p2Point) toInt() (x, y, z *big.Int) {
   114  	var x1, y1, z1 fp384
   115  	montDecode(&x1, &P.x)
   116  	montDecode(&y1, &P.y)
   117  	montDecode(&z1, &P.z)
   118  	return x1.BigInt(), y1.BigInt(), z1.BigInt()
   119  }
   120  
   121  // jacobianPoint represents a point in Jacobian coordinates. The point at
   122  // infinity is any point (x,y,0) such that x and y are different from 0.
   123  type jacobianPoint struct{ p2Point }
   124  
   125  func (P *jacobianPoint) isZero() bool {
   126  	zero := fp384{}
   127  	return P.x != zero && P.y != zero && P.z == zero
   128  }
   129  
   130  func (P *jacobianPoint) toAffine() *affinePoint {
   131  	var aP affinePoint
   132  	z, z2 := &fp384{}, &fp384{}
   133  	fp384Inv(z, &P.z)
   134  	fp384Sqr(z2, z)
   135  	fp384Mul(&aP.x, &P.x, z2)
   136  	fp384Mul(&aP.y, &P.y, z)
   137  	fp384Mul(&aP.y, &aP.y, z2)
   138  	return &aP
   139  }
   140  
   141  func (P *jacobianPoint) cmov(Q *jacobianPoint, b int) { P.p2Point.cmov(&Q.p2Point, b) }
   142  
   143  // add calculates P=Q+R such that Q and R are different than the identity point,
   144  // and Q!==R. This function cannot be used for doublings.
   145  func (P *jacobianPoint) add(Q, R *jacobianPoint) {
   146  	if Q.isZero() {
   147  		*P = *R
   148  		return
   149  	} else if R.isZero() {
   150  		*P = *Q
   151  		return
   152  	}
   153  
   154  	// Cohen-Miyagi-Ono (1998)
   155  	// https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-1998-cmo-2
   156  	X1, Y1, Z1 := &Q.x, &Q.y, &Q.z
   157  	X2, Y2, Z2 := &R.x, &R.y, &R.z
   158  	Z1Z1, Z2Z2, U1, U2 := &fp384{}, &fp384{}, &fp384{}, &fp384{}
   159  	H, HH, HHH, RR := &fp384{}, &fp384{}, &fp384{}, &fp384{}
   160  	V, t4, t5, t6, t7, t8 := &fp384{}, &fp384{}, &fp384{}, &fp384{}, &fp384{}, &fp384{}
   161  	t0, t1, t2, t3, S1, S2 := &fp384{}, &fp384{}, &fp384{}, &fp384{}, &fp384{}, &fp384{}
   162  	fp384Sqr(Z1Z1, Z1)     // Z1Z1 = Z1 ^ 2
   163  	fp384Sqr(Z2Z2, Z2)     // Z2Z2 = Z2 ^ 2
   164  	fp384Mul(U1, X1, Z2Z2) // U1 = X1 * Z2Z2
   165  	fp384Mul(U2, X2, Z1Z1) // U2 = X2 * Z1Z1
   166  	fp384Mul(t0, Z2, Z2Z2) // t0 = Z2 * Z2Z2
   167  	fp384Mul(S1, Y1, t0)   // S1 = Y1 * t0
   168  	fp384Mul(t1, Z1, Z1Z1) // t1 = Z1 * Z1Z1
   169  	fp384Mul(S2, Y2, t1)   // S2 = Y2 * t1
   170  	fp384Sub(H, U2, U1)    // H = U2 - U1
   171  	fp384Sqr(HH, H)        // HH = H ^ 2
   172  	fp384Mul(HHH, H, HH)   // HHH = H * HH
   173  	fp384Sub(RR, S2, S1)   // r = S2 - S1
   174  	fp384Mul(V, U1, HH)    // V = U1 * HH
   175  	fp384Sqr(t2, RR)       // t2 = r ^ 2
   176  	fp384Add(t3, V, V)     // t3 = V + V
   177  	fp384Sub(t4, t2, HHH)  // t4 = t2 - HHH
   178  	fp384Sub(&P.x, t4, t3) // X3 = t4 - t3
   179  	fp384Sub(t5, V, &P.x)  // t5 = V - X3
   180  	fp384Mul(t6, S1, HHH)  // t6 = S1 * HHH
   181  	fp384Mul(t7, RR, t5)   // t7 = r * t5
   182  	fp384Sub(&P.y, t7, t6) // Y3 = t7 - t6
   183  	fp384Mul(t8, Z2, H)    // t8 = Z2 * H
   184  	fp384Mul(&P.z, Z1, t8) // Z3 = Z1 * t8
   185  }
   186  
   187  // mixadd calculates P=Q+R such that P and Q different than the identity point,
   188  // and Q not in {P,-P, O}.
   189  func (P *jacobianPoint) mixadd(Q *jacobianPoint, R *affinePoint) {
   190  	if Q.isZero() {
   191  		*P = *R.toJacobian()
   192  		return
   193  	} else if R.isZero() {
   194  		*P = *Q
   195  		return
   196  	}
   197  
   198  	z1z1, u2 := &fp384{}, &fp384{}
   199  	fp384Sqr(z1z1, &Q.z)
   200  	fp384Mul(u2, &R.x, z1z1)
   201  
   202  	s2 := &fp384{}
   203  	fp384Mul(s2, &R.y, &Q.z)
   204  	fp384Mul(s2, s2, z1z1)
   205  	if Q.x == *u2 {
   206  		if Q.y != *s2 {
   207  			*P = *(zeroPoint().toJacobian())
   208  			return
   209  		}
   210  		*P = *Q
   211  		P.double()
   212  		return
   213  	}
   214  
   215  	h, r := &fp384{}, &fp384{}
   216  	fp384Sub(h, u2, &Q.x)
   217  	fp384Mul(&P.z, h, &Q.z)
   218  	fp384Sub(r, s2, &Q.y)
   219  
   220  	h2, h3 := &fp384{}, &fp384{}
   221  	fp384Sqr(h2, h)
   222  	fp384Mul(h3, h2, h)
   223  	h3y1 := &fp384{}
   224  	fp384Mul(h3y1, h3, &Q.y)
   225  
   226  	h2x1 := &fp384{}
   227  	fp384Mul(h2x1, h2, &Q.x)
   228  
   229  	fp384Sqr(&P.x, r)
   230  	fp384Sub(&P.x, &P.x, h3)
   231  	fp384Sub(&P.x, &P.x, h2x1)
   232  	fp384Sub(&P.x, &P.x, h2x1)
   233  
   234  	fp384Sub(&P.y, h2x1, &P.x)
   235  	fp384Mul(&P.y, &P.y, r)
   236  	fp384Sub(&P.y, &P.y, h3y1)
   237  }
   238  
   239  func (P *jacobianPoint) double() {
   240  	delta, gamma, alpha, alpha2 := &fp384{}, &fp384{}, &fp384{}, &fp384{}
   241  	fp384Sqr(delta, &P.z)
   242  	fp384Sqr(gamma, &P.y)
   243  	fp384Sub(alpha, &P.x, delta)
   244  	fp384Add(alpha2, &P.x, delta)
   245  	fp384Mul(alpha, alpha, alpha2)
   246  	*alpha2 = *alpha
   247  	fp384Add(alpha, alpha, alpha)
   248  	fp384Add(alpha, alpha, alpha2)
   249  
   250  	beta := &fp384{}
   251  	fp384Mul(beta, &P.x, gamma)
   252  
   253  	beta8 := &fp384{}
   254  	fp384Sqr(&P.x, alpha)
   255  	fp384Add(beta8, beta, beta)
   256  	fp384Add(beta8, beta8, beta8)
   257  	fp384Add(beta8, beta8, beta8)
   258  	fp384Sub(&P.x, &P.x, beta8)
   259  
   260  	fp384Add(&P.z, &P.y, &P.z)
   261  	fp384Sqr(&P.z, &P.z)
   262  	fp384Sub(&P.z, &P.z, gamma)
   263  	fp384Sub(&P.z, &P.z, delta)
   264  
   265  	fp384Add(beta, beta, beta)
   266  	fp384Add(beta, beta, beta)
   267  	fp384Sub(beta, beta, &P.x)
   268  
   269  	fp384Mul(&P.y, alpha, beta)
   270  
   271  	fp384Sqr(gamma, gamma)
   272  	fp384Add(gamma, gamma, gamma)
   273  	fp384Add(gamma, gamma, gamma)
   274  	fp384Add(gamma, gamma, gamma)
   275  	fp384Sub(&P.y, &P.y, gamma)
   276  }
   277  
   278  func (P *jacobianPoint) toProjective() *projectivePoint {
   279  	var hP projectivePoint
   280  	hP.y = P.y
   281  	fp384Mul(&hP.x, &P.x, &P.z)
   282  	fp384Sqr(&hP.z, &P.z)
   283  	fp384Mul(&hP.z, &hP.z, &P.z)
   284  	return &hP
   285  }
   286  
   287  // projectivePoint represents a point in projective homogeneous coordinates.
   288  // The point at infinity is (0,y,0) such that y is different from 0.
   289  type projectivePoint struct{ p2Point }
   290  
   291  func (P *projectivePoint) isZero() bool {
   292  	zero := fp384{}
   293  	return P.x == zero && P.y != zero && P.z == zero
   294  }
   295  
   296  func (P *projectivePoint) toAffine() *affinePoint {
   297  	var aP affinePoint
   298  	z := &fp384{}
   299  	fp384Inv(z, &P.z)
   300  	fp384Mul(&aP.x, &P.x, z)
   301  	fp384Mul(&aP.y, &P.y, z)
   302  	return &aP
   303  }
   304  
   305  // add calculates P=Q+R using complete addition formula for prime groups.
   306  func (P *projectivePoint) completeAdd(Q, R *projectivePoint) {
   307  	// Reference:
   308  	//   "Complete addition formulas for prime order elliptic curves" by
   309  	//   Costello-Renes-Batina. [Alg.4] (eprint.iacr.org/2015/1060).
   310  	X1, Y1, Z1 := &Q.x, &Q.y, &Q.z
   311  	X2, Y2, Z2 := &R.x, &R.y, &R.z
   312  	X3, Y3, Z3 := &fp384{}, &fp384{}, &fp384{}
   313  	t0, t1, t2, t3, t4 := &fp384{}, &fp384{}, &fp384{}, &fp384{}, &fp384{}
   314  	fp384Mul(t0, X1, X2)  // 1.  t0 ← X1 · X2
   315  	fp384Mul(t1, Y1, Y2)  // 2.  t1 ← Y1 · Y2
   316  	fp384Mul(t2, Z1, Z2)  // 3.  t2 ← Z1 · Z2
   317  	fp384Add(t3, X1, Y1)  // 4.  t3 ← X1 + Y1
   318  	fp384Add(t4, X2, Y2)  // 5.  t4 ← X2 + Y2
   319  	fp384Mul(t3, t3, t4)  // 6.  t3 ← t3 · t4
   320  	fp384Add(t4, t0, t1)  // 7.  t4 ← t0 + t1
   321  	fp384Sub(t3, t3, t4)  // 8.  t3 ← t3 − t4
   322  	fp384Add(t4, Y1, Z1)  // 9.  t4 ← Y1 + Z1
   323  	fp384Add(X3, Y2, Z2)  // 10. X3 ← Y2 + Z2
   324  	fp384Mul(t4, t4, X3)  // 11. t4 ← t4 · X3
   325  	fp384Add(X3, t1, t2)  // 12. X3 ← t1 + t2
   326  	fp384Sub(t4, t4, X3)  // 13. t4 ← t4 − X3
   327  	fp384Add(X3, X1, Z1)  // 14. X3 ← X1 + Z1
   328  	fp384Add(Y3, X2, Z2)  // 15. Y3 ← X2 + Z2
   329  	fp384Mul(X3, X3, Y3)  // 16. X3 ← X3 · Y3
   330  	fp384Add(Y3, t0, t2)  // 17. Y3 ← t0 + t2
   331  	fp384Sub(Y3, X3, Y3)  // 18. Y3 ← X3 − Y3
   332  	fp384Mul(Z3, &bb, t2) // 19. Z3 ←  b · t2
   333  	fp384Sub(X3, Y3, Z3)  // 20. X3 ← Y3 − Z3
   334  	fp384Add(Z3, X3, X3)  // 21. Z3 ← X3 + X3
   335  	fp384Add(X3, X3, Z3)  // 22. X3 ← X3 + Z3
   336  	fp384Sub(Z3, t1, X3)  // 23. Z3 ← t1 − X3
   337  	fp384Add(X3, t1, X3)  // 24. X3 ← t1 + X3
   338  	fp384Mul(Y3, &bb, Y3) // 25. Y3 ←  b · Y3
   339  	fp384Add(t1, t2, t2)  // 26. t1 ← t2 + t2
   340  	fp384Add(t2, t1, t2)  // 27. t2 ← t1 + t2
   341  	fp384Sub(Y3, Y3, t2)  // 28. Y3 ← Y3 − t2
   342  	fp384Sub(Y3, Y3, t0)  // 29. Y3 ← Y3 − t0
   343  	fp384Add(t1, Y3, Y3)  // 30. t1 ← Y3 + Y3
   344  	fp384Add(Y3, t1, Y3)  // 31. Y3 ← t1 + Y3
   345  	fp384Add(t1, t0, t0)  // 32. t1 ← t0 + t0
   346  	fp384Add(t0, t1, t0)  // 33. t0 ← t1 + t0
   347  	fp384Sub(t0, t0, t2)  // 34. t0 ← t0 − t2
   348  	fp384Mul(t1, t4, Y3)  // 35. t1 ← t4 · Y3
   349  	fp384Mul(t2, t0, Y3)  // 36. t2 ← t0 · Y3
   350  	fp384Mul(Y3, X3, Z3)  // 37. Y3 ← X3 · Z3
   351  	fp384Add(Y3, Y3, t2)  // 38. Y3 ← Y3 + t2
   352  	fp384Mul(X3, t3, X3)  // 39. X3 ← t3 · X3
   353  	fp384Sub(X3, X3, t1)  // 40. X3 ← X3 − t1
   354  	fp384Mul(Z3, t4, Z3)  // 41. Z3 ← t4 · Z3
   355  	fp384Mul(t1, t3, t0)  // 42. t1 ← t3 · t0
   356  	fp384Add(Z3, Z3, t1)  // 43. Z3 ← Z3 + t1
   357  	P.x, P.y, P.z = *X3, *Y3, *Z3
   358  }
   359
View as plain text