1package goldilocks
  2
  3import (
  4	"errors"
  5	"fmt"
  6
  7	fp "github.com/cloudflare/circl/math/fp448"
  8)
  9
 10// Point is a point on the Goldilocks Curve.
 11type Point struct{ x, y, z, ta, tb fp.Elt }
 12
 13func (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.
 18func 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.
 34func 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.
 43func 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.
 80func (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.
 85func (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.
105func (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.
108func (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.
121func (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.
131func (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.
138func (P *Point) UnmarshalBinary(data []byte) error { Q, err := FromBytes(data); *P = *Q; return err }
139
140// Double sets P = 2Q.
141func (P *Point) Double() { P.Add(P) }
142
143// Add sets P =P+Q..
144func (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}