twistPoint.go

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

     1  package goldilocks
     2  
     3  import (
     4  	"fmt"
     5  
     6  	fp "github.com/cloudflare/circl/math/fp448"
     7  )
     8  
     9  type twistPoint struct{ x, y, z, ta, tb fp.Elt }
    10  
    11  type preTwistPointAffine struct{ addYX, subYX, dt2 fp.Elt }
    12  
    13  type preTwistPointProy struct {
    14  	preTwistPointAffine
    15  	z2 fp.Elt
    16  }
    17  
    18  func (P *twistPoint) String() string {
    19  	return fmt.Sprintf("x: %v\ny: %v\nz: %v\nta: %v\ntb: %v", P.x, P.y, P.z, P.ta, P.tb)
    20  }
    21  
    22  // cneg conditionally negates the point if b=1.
    23  func (P *twistPoint) cneg(b uint) {
    24  	t := &fp.Elt{}
    25  	fp.Neg(t, &P.x)
    26  	fp.Cmov(&P.x, t, b)
    27  	fp.Neg(t, &P.ta)
    28  	fp.Cmov(&P.ta, t, b)
    29  }
    30  
    31  // Double updates P with 2P.
    32  func (P *twistPoint) Double() {
    33  	// This is formula (7) from "Twisted Edwards Curves Revisited" by
    34  	// Hisil H., Wong K.KH., Carter G., Dawson E. (2008)
    35  	// https://doi.org/10.1007/978-3-540-89255-7_20
    36  	Px, Py, Pz, Pta, Ptb := &P.x, &P.y, &P.z, &P.ta, &P.tb
    37  	a, b, c, e, f, g, h := Px, Py, Pz, Pta, Px, Py, Ptb
    38  	fp.Add(e, Px, Py) // x+y
    39  	fp.Sqr(a, Px)     // A = x^2
    40  	fp.Sqr(b, Py)     // B = y^2
    41  	fp.Sqr(c, Pz)     // z^2
    42  	fp.Add(c, c, c)   // C = 2*z^2
    43  	fp.Add(h, a, b)   // H = A+B
    44  	fp.Sqr(e, e)      // (x+y)^2
    45  	fp.Sub(e, e, h)   // E = (x+y)^2-A-B
    46  	fp.Sub(g, b, a)   // G = B-A
    47  	fp.Sub(f, c, g)   // F = C-G
    48  	fp.Mul(Pz, f, g)  // Z = F * G
    49  	fp.Mul(Px, e, f)  // X = E * F
    50  	fp.Mul(Py, g, h)  // Y = G * H, T = E * H
    51  }
    52  
    53  // mixAdd calculates P= P+Q, where Q is a precomputed point with Z_Q = 1.
    54  func (P *twistPoint) mixAddZ1(Q *preTwistPointAffine) {
    55  	fp.Add(&P.z, &P.z, &P.z) // D = 2*z1 (z2=1)
    56  	P.coreAddition(Q)
    57  }
    58  
    59  // coreAddition calculates P=P+Q for curves with A=-1.
    60  func (P *twistPoint) coreAddition(Q *preTwistPointAffine) {
    61  	// This is the formula following (5) from "Twisted Edwards Curves Revisited" by
    62  	// Hisil H., Wong K.KH., Carter G., Dawson E. (2008)
    63  	// https://doi.org/10.1007/978-3-540-89255-7_20
    64  	Px, Py, Pz, Pta, Ptb := &P.x, &P.y, &P.z, &P.ta, &P.tb
    65  	addYX2, subYX2, dt2 := &Q.addYX, &Q.subYX, &Q.dt2
    66  	a, b, c, d, e, f, g, h := Px, Py, &fp.Elt{}, Pz, Pta, Px, Py, Ptb
    67  	fp.Mul(c, Pta, Ptb)  // t1 = ta*tb
    68  	fp.Sub(h, Py, Px)    // y1-x1
    69  	fp.Add(b, Py, Px)    // y1+x1
    70  	fp.Mul(a, h, subYX2) // A = (y1-x1)*(y2-x2)
    71  	fp.Mul(b, b, addYX2) // B = (y1+x1)*(y2+x2)
    72  	fp.Mul(c, c, dt2)    // C = 2*D*t1*t2
    73  	fp.Sub(e, b, a)      // E = B-A
    74  	fp.Add(h, b, a)      // H = B+A
    75  	fp.Sub(f, d, c)      // F = D-C
    76  	fp.Add(g, d, c)      // G = D+C
    77  	fp.Mul(Pz, f, g)     // Z = F * G
    78  	fp.Mul(Px, e, f)     // X = E * F
    79  	fp.Mul(Py, g, h)     // Y = G * H, T = E * H
    80  }
    81  
    82  func (P *preTwistPointAffine) neg() {
    83  	P.addYX, P.subYX = P.subYX, P.addYX
    84  	fp.Neg(&P.dt2, &P.dt2)
    85  }
    86  
    87  func (P *preTwistPointAffine) cneg(b int) {
    88  	t := &fp.Elt{}
    89  	fp.Cswap(&P.addYX, &P.subYX, uint(b))
    90  	fp.Neg(t, &P.dt2)
    91  	fp.Cmov(&P.dt2, t, uint(b))
    92  }
    93  
    94  func (P *preTwistPointAffine) cmov(Q *preTwistPointAffine, b uint) {
    95  	fp.Cmov(&P.addYX, &Q.addYX, b)
    96  	fp.Cmov(&P.subYX, &Q.subYX, b)
    97  	fp.Cmov(&P.dt2, &Q.dt2, b)
    98  }
    99  
   100  // mixAdd calculates P= P+Q, where Q is a precomputed point with Z_Q != 1.
   101  func (P *twistPoint) mixAdd(Q *preTwistPointProy) {
   102  	fp.Mul(&P.z, &P.z, &Q.z2) // D = 2*z1*z2
   103  	P.coreAddition(&Q.preTwistPointAffine)
   104  }
   105  
   106  // oddMultiples calculates T[i] = (2*i-1)P for 0 < i < len(T).
   107  func (P *twistPoint) oddMultiples(T []preTwistPointProy) {
   108  	if n := len(T); n > 0 {
   109  		T[0].FromTwistPoint(P)
   110  		_2P := *P
   111  		_2P.Double()
   112  		R := &preTwistPointProy{}
   113  		R.FromTwistPoint(&_2P)
   114  		for i := 1; i < n; i++ {
   115  			P.mixAdd(R)
   116  			T[i].FromTwistPoint(P)
   117  		}
   118  	}
   119  }
   120  
   121  // cmov conditionally moves Q into P if b=1.
   122  func (P *preTwistPointProy) cmov(Q *preTwistPointProy, b uint) {
   123  	P.preTwistPointAffine.cmov(&Q.preTwistPointAffine, b)
   124  	fp.Cmov(&P.z2, &Q.z2, b)
   125  }
   126  
   127  // FromTwistPoint precomputes some coordinates of Q for missed addition.
   128  func (P *preTwistPointProy) FromTwistPoint(Q *twistPoint) {
   129  	fp.Add(&P.addYX, &Q.y, &Q.x)         // addYX = X + Y
   130  	fp.Sub(&P.subYX, &Q.y, &Q.x)         // subYX = Y - X
   131  	fp.Mul(&P.dt2, &Q.ta, &Q.tb)         // T = ta*tb
   132  	fp.Mul(&P.dt2, &P.dt2, &paramDTwist) // D*T
   133  	fp.Add(&P.dt2, &P.dt2, &P.dt2)       // dt2 = 2*D*T
   134  	fp.Add(&P.z2, &Q.z, &Q.z)            // z2 = 2*Z
   135  }
   136
View as plain text