point.go raw

   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