1// Copyright (c) 2017 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package edwards25519
6
7import (
8	"crypto/internal/edwards25519/field"
9	"errors"
10)
11
12// Point types.
13
14type projP1xP1 struct {
15	X, Y, Z, T field.Element
16}
17
18type projP2 struct {
19	X, Y, Z field.Element
20}
21
22// Point represents a point on the edwards25519 curve.
23//
24// This type works similarly to math/big.Int, and all arguments and receivers
25// are allowed to alias.
26//
27// The zero value is NOT valid, and it may be used only as a receiver.
28type Point struct {
29	// Make the type not comparable (i.e. used with == or as a map key), as
30	// equivalent points can be represented by different Go values.
31	_ incomparable
32
33	// The point is internally represented in extended coordinates (X, Y, Z, T)
34	// where x = X/Z, y = Y/Z, and xy = T/Z per https://eprint.iacr.org/2008/522.
35	x, y, z, t field.Element
36}
37
38type incomparable [0]func()
39
40func checkInitialized(points ...*Point) {
41	for _, p := range points {
42		if p.x == (field.Element{}) && p.y == (field.Element{}) {
43			panic("edwards25519: use of uninitialized Point")
44		}
45	}
46}
47
48type projCached struct {
49	YplusX, YminusX, Z, T2d field.Element
50}
51
52type affineCached struct {
53	YplusX, YminusX, T2d field.Element
54}
55
56// Constructors.
57
58func (v *projP2) Zero() *projP2 {
59	v.X.Zero()
60	v.Y.One()
61	v.Z.One()
62	return v
63}
64
65// identity is the point at infinity.
66var identity, _ = new(Point).SetBytes([]byte{
67	1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
68	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0})
69
70// NewIdentityPoint returns a new Point set to the identity.
71func NewIdentityPoint() *Point {
72	return new(Point).Set(identity)
73}
74
75// generator is the canonical curve basepoint. See TestGenerator for the
76// correspondence of this encoding with the values in RFC 8032.
77var generator, _ = new(Point).SetBytes([]byte{
78	0x58, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
79	0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
80	0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
81	0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66})
82
83// NewGeneratorPoint returns a new Point set to the canonical generator.
84func NewGeneratorPoint() *Point {
85	return new(Point).Set(generator)
86}
87
88func (v *projCached) Zero() *projCached {
89	v.YplusX.One()
90	v.YminusX.One()
91	v.Z.One()
92	v.T2d.Zero()
93	return v
94}
95
96func (v *affineCached) Zero() *affineCached {
97	v.YplusX.One()
98	v.YminusX.One()
99	v.T2d.Zero()
100	return v
101}
102
103// Assignments.
104
105// Set sets v = u, and returns v.
106func (v *Point) Set(u *Point) *Point {
107	*v = *u
108	return v
109}
110
111// Encoding.
112
113// Bytes returns the canonical 32-byte encoding of v, according to RFC 8032,
114// Section 5.1.2.
115func (v *Point) Bytes() []byte {
116	// This function is outlined to make the allocations inline in the caller
117	// rather than happen on the heap.
118	var buf [32]byte
119	return v.bytes(&buf)
120}
121
122func (v *Point) bytes(buf *[32]byte) []byte {
123	checkInitialized(v)
124
125	var zInv, x, y field.Element
126	zInv.Invert(&v.z)       // zInv = 1 / Z
127	x.Multiply(&v.x, &zInv) // x = X / Z
128	y.Multiply(&v.y, &zInv) // y = Y / Z
129
130	out := copyFieldElement(buf, &y)
131	out[31] |= byte(x.IsNegative() << 7)
132	return out
133}
134
135var feOne = new(field.Element).One()
136
137// SetBytes sets v = x, where x is a 32-byte encoding of v. If x does not
138// represent a valid point on the curve, SetBytes returns nil and an error and
139// the receiver is unchanged. Otherwise, SetBytes returns v.
140//
141// Note that SetBytes accepts all non-canonical encodings of valid points.
142// That is, it follows decoding rules that match most implementations in
143// the ecosystem rather than RFC 8032.
144func (v *Point) SetBytes(x []byte) (*Point, error) {
145	// Specifically, the non-canonical encodings that are accepted are
146	//   1) the ones where the field element is not reduced (see the
147	//      (*field.Element).SetBytes docs) and
148	//   2) the ones where the x-coordinate is zero and the sign bit is set.
149	//
150	// Read more at https://hdevalence.ca/blog/2020-10-04-its-25519am,
151	// specifically the "Canonical A, R" section.
152
153	y, err := new(field.Element).SetBytes(x)
154	if err != nil {
155		return nil, errors.New("edwards25519: invalid point encoding length")
156	}
157
158	// -x² + y² = 1 + dx²y²
159	// x² + dx²y² = x²(dy² + 1) = y² - 1
160	// x² = (y² - 1) / (dy² + 1)
161
162	// u = y² - 1
163	y2 := new(field.Element).Square(y)
164	u := new(field.Element).Subtract(y2, feOne)
165
166	// v = dy² + 1
167	vv := new(field.Element).Multiply(y2, d)
168	vv = vv.Add(vv, feOne)
169
170	// x = +√(u/v)
171	xx, wasSquare := new(field.Element).SqrtRatio(u, vv)
172	if wasSquare == 0 {
173		return nil, errors.New("edwards25519: invalid point encoding")
174	}
175
176	// Select the negative square root if the sign bit is set.
177	xxNeg := new(field.Element).Negate(xx)
178	xx = xx.Select(xxNeg, xx, int(x[31]>>7))
179
180	v.x.Set(xx)
181	v.y.Set(y)
182	v.z.One()
183	v.t.Multiply(xx, y) // xy = T / Z
184
185	return v, nil
186}
187
188func copyFieldElement(buf *[32]byte, v *field.Element) []byte {
189	copy(buf[:], v.Bytes())
190	return buf[:]
191}
192
193// Conversions.
194
195func (v *projP2) FromP1xP1(p *projP1xP1) *projP2 {
196	v.X.Multiply(&p.X, &p.T)
197	v.Y.Multiply(&p.Y, &p.Z)
198	v.Z.Multiply(&p.Z, &p.T)
199	return v
200}
201
202func (v *projP2) FromP3(p *Point) *projP2 {
203	v.X.Set(&p.x)
204	v.Y.Set(&p.y)
205	v.Z.Set(&p.z)
206	return v
207}
208
209func (v *Point) fromP1xP1(p *projP1xP1) *Point {
210	v.x.Multiply(&p.X, &p.T)
211	v.y.Multiply(&p.Y, &p.Z)
212	v.z.Multiply(&p.Z, &p.T)
213	v.t.Multiply(&p.X, &p.Y)
214	return v
215}
216
217func (v *Point) fromP2(p *projP2) *Point {
218	v.x.Multiply(&p.X, &p.Z)
219	v.y.Multiply(&p.Y, &p.Z)
220	v.z.Square(&p.Z)
221	v.t.Multiply(&p.X, &p.Y)
222	return v
223}
224
225// d is a constant in the curve equation.
226var d, _ = new(field.Element).SetBytes([]byte{
227	0xa3, 0x78, 0x59, 0x13, 0xca, 0x4d, 0xeb, 0x75,
228	0xab, 0xd8, 0x41, 0x41, 0x4d, 0x0a, 0x70, 0x00,
229	0x98, 0xe8, 0x79, 0x77, 0x79, 0x40, 0xc7, 0x8c,
230	0x73, 0xfe, 0x6f, 0x2b, 0xee, 0x6c, 0x03, 0x52})
231var d2 = new(field.Element).Add(d, d)
232
233func (v *projCached) FromP3(p *Point) *projCached {
234	v.YplusX.Add(&p.y, &p.x)
235	v.YminusX.Subtract(&p.y, &p.x)
236	v.Z.Set(&p.z)
237	v.T2d.Multiply(&p.t, d2)
238	return v
239}
240
241func (v *affineCached) FromP3(p *Point) *affineCached {
242	v.YplusX.Add(&p.y, &p.x)
243	v.YminusX.Subtract(&p.y, &p.x)
244	v.T2d.Multiply(&p.t, d2)
245
246	var invZ field.Element
247	invZ.Invert(&p.z)
248	v.YplusX.Multiply(&v.YplusX, &invZ)
249	v.YminusX.Multiply(&v.YminusX, &invZ)
250	v.T2d.Multiply(&v.T2d, &invZ)
251	return v
252}
253
254// (Re)addition and subtraction.
255
256// Add sets v = p + q, and returns v.
257func (v *Point) Add(p, q *Point) *Point {
258	checkInitialized(p, q)
259	qCached := new(projCached).FromP3(q)
260	result := new(projP1xP1).Add(p, qCached)
261	return v.fromP1xP1(result)
262}
263
264// Subtract sets v = p - q, and returns v.
265func (v *Point) Subtract(p, q *Point) *Point {
266	checkInitialized(p, q)
267	qCached := new(projCached).FromP3(q)
268	result := new(projP1xP1).Sub(p, qCached)
269	return v.fromP1xP1(result)
270}
271
272func (v *projP1xP1) Add(p *Point, q *projCached) *projP1xP1 {
273	var YplusX, YminusX, PP, MM, TT2d, ZZ2 field.Element
274
275	YplusX.Add(&p.y, &p.x)
276	YminusX.Subtract(&p.y, &p.x)
277
278	PP.Multiply(&YplusX, &q.YplusX)
279	MM.Multiply(&YminusX, &q.YminusX)
280	TT2d.Multiply(&p.t, &q.T2d)
281	ZZ2.Multiply(&p.z, &q.Z)
282
283	ZZ2.Add(&ZZ2, &ZZ2)
284
285	v.X.Subtract(&PP, &MM)
286	v.Y.Add(&PP, &MM)
287	v.Z.Add(&ZZ2, &TT2d)
288	v.T.Subtract(&ZZ2, &TT2d)
289	return v
290}
291
292func (v *projP1xP1) Sub(p *Point, q *projCached) *projP1xP1 {
293	var YplusX, YminusX, PP, MM, TT2d, ZZ2 field.Element
294
295	YplusX.Add(&p.y, &p.x)
296	YminusX.Subtract(&p.y, &p.x)
297
298	PP.Multiply(&YplusX, &q.YminusX) // flipped sign
299	MM.Multiply(&YminusX, &q.YplusX) // flipped sign
300	TT2d.Multiply(&p.t, &q.T2d)
301	ZZ2.Multiply(&p.z, &q.Z)
302
303	ZZ2.Add(&ZZ2, &ZZ2)
304
305	v.X.Subtract(&PP, &MM)
306	v.Y.Add(&PP, &MM)
307	v.Z.Subtract(&ZZ2, &TT2d) // flipped sign
308	v.T.Add(&ZZ2, &TT2d)      // flipped sign
309	return v
310}
311
312func (v *projP1xP1) AddAffine(p *Point, q *affineCached) *projP1xP1 {
313	var YplusX, YminusX, PP, MM, TT2d, Z2 field.Element
314
315	YplusX.Add(&p.y, &p.x)
316	YminusX.Subtract(&p.y, &p.x)
317
318	PP.Multiply(&YplusX, &q.YplusX)
319	MM.Multiply(&YminusX, &q.YminusX)
320	TT2d.Multiply(&p.t, &q.T2d)
321
322	Z2.Add(&p.z, &p.z)
323
324	v.X.Subtract(&PP, &MM)
325	v.Y.Add(&PP, &MM)
326	v.Z.Add(&Z2, &TT2d)
327	v.T.Subtract(&Z2, &TT2d)
328	return v
329}
330
331func (v *projP1xP1) SubAffine(p *Point, q *affineCached) *projP1xP1 {
332	var YplusX, YminusX, PP, MM, TT2d, Z2 field.Element
333
334	YplusX.Add(&p.y, &p.x)
335	YminusX.Subtract(&p.y, &p.x)
336
337	PP.Multiply(&YplusX, &q.YminusX) // flipped sign
338	MM.Multiply(&YminusX, &q.YplusX) // flipped sign
339	TT2d.Multiply(&p.t, &q.T2d)
340
341	Z2.Add(&p.z, &p.z)
342
343	v.X.Subtract(&PP, &MM)
344	v.Y.Add(&PP, &MM)
345	v.Z.Subtract(&Z2, &TT2d) // flipped sign
346	v.T.Add(&Z2, &TT2d)      // flipped sign
347	return v
348}
349
350// Doubling.
351
352func (v *projP1xP1) Double(p *projP2) *projP1xP1 {
353	var XX, YY, ZZ2, XplusYsq field.Element
354
355	XX.Square(&p.X)
356	YY.Square(&p.Y)
357	ZZ2.Square(&p.Z)
358	ZZ2.Add(&ZZ2, &ZZ2)
359	XplusYsq.Add(&p.X, &p.Y)
360	XplusYsq.Square(&XplusYsq)
361
362	v.Y.Add(&YY, &XX)
363	v.Z.Subtract(&YY, &XX)
364
365	v.X.Subtract(&XplusYsq, &v.Y)
366	v.T.Subtract(&ZZ2, &v.Z)
367	return v
368}
369
370// Negation.
371
372// Negate sets v = -p, and returns v.
373func (v *Point) Negate(p *Point) *Point {
374	checkInitialized(p)
375	v.x.Negate(&p.x)
376	v.y.Set(&p.y)
377	v.z.Set(&p.z)
378	v.t.Negate(&p.t)
379	return v
380}
381
382// Equal returns 1 if v is equivalent to u, and 0 otherwise.
383func (v *Point) Equal(u *Point) int {
384	checkInitialized(v, u)
385
386	var t1, t2, t3, t4 field.Element
387	t1.Multiply(&v.x, &u.z)
388	t2.Multiply(&u.x, &v.z)
389	t3.Multiply(&v.y, &u.z)
390	t4.Multiply(&u.y, &v.z)
391
392	return t1.Equal(&t2) & t3.Equal(&t4)
393}
394
395// Constant-time operations
396
397// Select sets v to a if cond == 1 and to b if cond == 0.
398func (v *projCached) Select(a, b *projCached, cond int) *projCached {
399	v.YplusX.Select(&a.YplusX, &b.YplusX, cond)
400	v.YminusX.Select(&a.YminusX, &b.YminusX, cond)
401	v.Z.Select(&a.Z, &b.Z, cond)
402	v.T2d.Select(&a.T2d, &b.T2d, cond)
403	return v
404}
405
406// Select sets v to a if cond == 1 and to b if cond == 0.
407func (v *affineCached) Select(a, b *affineCached, cond int) *affineCached {
408	v.YplusX.Select(&a.YplusX, &b.YplusX, cond)
409	v.YminusX.Select(&a.YminusX, &b.YminusX, cond)
410	v.T2d.Select(&a.T2d, &b.T2d, cond)
411	return v
412}
413
414// CondNeg negates v if cond == 1 and leaves it unchanged if cond == 0.
415func (v *projCached) CondNeg(cond int) *projCached {
416	v.YplusX.Swap(&v.YminusX, cond)
417	v.T2d.Select(new(field.Element).Negate(&v.T2d), &v.T2d, cond)
418	return v
419}
420
421// CondNeg negates v if cond == 1 and leaves it unchanged if cond == 0.
422func (v *affineCached) CondNeg(cond int) *affineCached {
423	v.YplusX.Swap(&v.YminusX, cond)
424	v.T2d.Select(new(field.Element).Negate(&v.T2d), &v.T2d, cond)
425	return v
426}
427