point.go

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

     1  package goldilocks
     2  
     3  import (
     4  	"errors"
     5  	"fmt"
     6  
     7  	fp "github.com/cloudflare/circl/math/fp448"
     8  )
     9  
    10  // Point is a point on the Goldilocks Curve.
    11  type Point struct{ x, y, z, ta, tb fp.Elt }
    12  
    13  func (P Point) String() string {
    14  	return fmt.Sprintf("x: %v\ny: %v\nz: %v\nta: %v\ntb: %v", P.x, P.y, P.z, P.ta, P.tb)
    15  }
    16  
    17  // FromAffine creates a point from affine coordinates.
    18  func FromAffine(x, y *fp.Elt) (*Point, error) {
    19  	P := &Point{
    20  		x:  *x,
    21  		y:  *y,
    22  		z:  fp.One(),
    23  		ta: *x,
    24  		tb: *y,
    25  	}
    26  	if !(Curve{}).IsOnCurve(P) {
    27  		return P, errors.New("point not on curve")
    28  	}
    29  	return P, nil
    30  }
    31  
    32  // isLessThan returns true if 0 <= x < y, and assumes that slices are of the
    33  // same length and are interpreted in little-endian order.
    34  func isLessThan(x, y []byte) bool {
    35  	i := len(x) - 1
    36  	for i > 0 && x[i] == y[i] {
    37  		i--
    38  	}
    39  	return x[i] < y[i]
    40  }
    41  
    42  // FromBytes returns a point from the input buffer.
    43  func FromBytes(in []byte) (*Point, error) {
    44  	if len(in) < fp.Size+1 {
    45  		return nil, errors.New("wrong input length")
    46  	}
    47  	err := errors.New("invalid decoding")
    48  	P := &Point{}
    49  	signX := in[fp.Size] >> 7
    50  	copy(P.y[:], in[:fp.Size])
    51  	p := fp.P()
    52  	if !isLessThan(P.y[:], p[:]) {
    53  		return nil, err
    54  	}
    55  
    56  	u, v := &fp.Elt{}, &fp.Elt{}
    57  	one := fp.One()
    58  	fp.Sqr(u, &P.y)                // u = y^2
    59  	fp.Mul(v, u, &paramD)          // v = dy^2
    60  	fp.Sub(u, u, &one)             // u = y^2-1
    61  	fp.Sub(v, v, &one)             // v = dy^2-1
    62  	isQR := fp.InvSqrt(&P.x, u, v) // x = sqrt(u/v)
    63  	if !isQR {
    64  		return nil, err
    65  	}
    66  	fp.Modp(&P.x) // x = x mod p
    67  	if fp.IsZero(&P.x) && signX == 1 {
    68  		return nil, err
    69  	}
    70  	if signX != (P.x[0] & 1) {
    71  		fp.Neg(&P.x, &P.x)
    72  	}
    73  	P.ta = P.x
    74  	P.tb = P.y
    75  	P.z = fp.One()
    76  	return P, nil
    77  }
    78  
    79  // IsIdentity returns true is P is the identity Point.
    80  func (P *Point) IsIdentity() bool {
    81  	return fp.IsZero(&P.x) && !fp.IsZero(&P.y) && !fp.IsZero(&P.z) && P.y == P.z
    82  }
    83  
    84  // IsEqual returns true if P is equivalent to Q.
    85  func (P *Point) IsEqual(Q *Point) bool {
    86  	l, r := &fp.Elt{}, &fp.Elt{}
    87  	fp.Mul(l, &P.x, &Q.z)
    88  	fp.Mul(r, &Q.x, &P.z)
    89  	fp.Sub(l, l, r)
    90  	b := fp.IsZero(l)
    91  	fp.Mul(l, &P.y, &Q.z)
    92  	fp.Mul(r, &Q.y, &P.z)
    93  	fp.Sub(l, l, r)
    94  	b = b && fp.IsZero(l)
    95  	fp.Mul(l, &P.ta, &P.tb)
    96  	fp.Mul(l, l, &Q.z)
    97  	fp.Mul(r, &Q.ta, &Q.tb)
    98  	fp.Mul(r, r, &P.z)
    99  	fp.Sub(l, l, r)
   100  	b = b && fp.IsZero(l)
   101  	return b
   102  }
   103  
   104  // Neg obtains the inverse of the Point.
   105  func (P *Point) Neg() { fp.Neg(&P.x, &P.x); fp.Neg(&P.ta, &P.ta) }
   106  
   107  // ToAffine returns the x,y affine coordinates of P.
   108  func (P *Point) ToAffine() (x, y fp.Elt) {
   109  	fp.Inv(&P.z, &P.z)       // 1/z
   110  	fp.Mul(&P.x, &P.x, &P.z) // x/z
   111  	fp.Mul(&P.y, &P.y, &P.z) // y/z
   112  	fp.Modp(&P.x)
   113  	fp.Modp(&P.y)
   114  	fp.SetOne(&P.z)
   115  	P.ta = P.x
   116  	P.tb = P.y
   117  	return P.x, P.y
   118  }
   119  
   120  // ToBytes stores P into a slice of bytes.
   121  func (P *Point) ToBytes(out []byte) error {
   122  	if len(out) < fp.Size+1 {
   123  		return errors.New("invalid decoding")
   124  	}
   125  	x, y := P.ToAffine()
   126  	out[fp.Size] = (x[0] & 1) << 7
   127  	return fp.ToBytes(out[:fp.Size], &y)
   128  }
   129  
   130  // MarshalBinary encodes the receiver into a binary form and returns the result.
   131  func (P *Point) MarshalBinary() (data []byte, err error) {
   132  	data = make([]byte, fp.Size+1)
   133  	err = P.ToBytes(data[:fp.Size+1])
   134  	return data, err
   135  }
   136  
   137  // UnmarshalBinary must be able to decode the form generated by MarshalBinary.
   138  func (P *Point) UnmarshalBinary(data []byte) error { Q, err := FromBytes(data); *P = *Q; return err }
   139  
   140  // Double sets P = 2Q.
   141  func (P *Point) Double() { P.Add(P) }
   142  
   143  // Add sets P =P+Q..
   144  func (P *Point) Add(Q *Point) {
   145  	// This is formula (5) from "Twisted Edwards Curves Revisited" by
   146  	// Hisil H., Wong K.KH., Carter G., Dawson E. (2008)
   147  	// https://doi.org/10.1007/978-3-540-89255-7_20
   148  	x1, y1, z1, ta1, tb1 := &P.x, &P.y, &P.z, &P.ta, &P.tb
   149  	x2, y2, z2, ta2, tb2 := &Q.x, &Q.y, &Q.z, &Q.ta, &Q.tb
   150  	x3, y3, z3, E, H := &P.x, &P.y, &P.z, &P.ta, &P.tb
   151  	A, B, C, D := &fp.Elt{}, &fp.Elt{}, &fp.Elt{}, &fp.Elt{}
   152  	t1, t2, F, G := C, D, &fp.Elt{}, &fp.Elt{}
   153  	fp.Mul(t1, ta1, tb1)  // t1 = ta1*tb1
   154  	fp.Mul(t2, ta2, tb2)  // t2 = ta2*tb2
   155  	fp.Mul(A, x1, x2)     // A = x1*x2
   156  	fp.Mul(B, y1, y2)     // B = y1*y2
   157  	fp.Mul(C, t1, t2)     // t1*t2
   158  	fp.Mul(C, C, &paramD) // C = d*t1*t2
   159  	fp.Mul(D, z1, z2)     // D = z1*z2
   160  	fp.Add(F, x1, y1)     // x1+y1
   161  	fp.Add(E, x2, y2)     // x2+y2
   162  	fp.Mul(E, E, F)       // (x1+y1)*(x2+y2)
   163  	fp.Sub(E, E, A)       // (x1+y1)*(x2+y2)-A
   164  	fp.Sub(E, E, B)       // E = (x1+y1)*(x2+y2)-A-B
   165  	fp.Sub(F, D, C)       // F = D-C
   166  	fp.Add(G, D, C)       // G = D+C
   167  	fp.Sub(H, B, A)       // H = B-A
   168  	fp.Mul(z3, F, G)      // Z = F * G
   169  	fp.Mul(x3, E, F)      // X = E * F
   170  	fp.Mul(y3, G, H)      // Y = G * H, T = E * H
   171  }
   172
View as plain text