1// Copyright (c) 2019 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	"encoding/hex"
10	"internal/testenv"
11	"reflect"
12	"testing"
13)
14
15var B = NewGeneratorPoint()
16var I = NewIdentityPoint()
17
18func checkOnCurve(t *testing.T, points ...*Point) {
19	t.Helper()
20	for i, p := range points {
21		var XX, YY, ZZ, ZZZZ field.Element
22		XX.Square(&p.x)
23		YY.Square(&p.y)
24		ZZ.Square(&p.z)
25		ZZZZ.Square(&ZZ)
26		// -x² + y² = 1 + dx²y²
27		// -(X/Z)² + (Y/Z)² = 1 + d(X/Z)²(Y/Z)²
28		// (-X² + Y²)/Z² = 1 + (dX²Y²)/Z⁴
29		// (-X² + Y²)*Z² = Z⁴ + dX²Y²
30		var lhs, rhs field.Element
31		lhs.Subtract(&YY, &XX).Multiply(&lhs, &ZZ)
32		rhs.Multiply(d, &XX).Multiply(&rhs, &YY).Add(&rhs, &ZZZZ)
33		if lhs.Equal(&rhs) != 1 {
34			t.Errorf("X, Y, and Z do not specify a point on the curve\nX = %v\nY = %v\nZ = %v", p.x, p.y, p.z)
35		}
36		// xy = T/Z
37		lhs.Multiply(&p.x, &p.y)
38		rhs.Multiply(&p.z, &p.t)
39		if lhs.Equal(&rhs) != 1 {
40			t.Errorf("point %d is not valid\nX = %v\nY = %v\nZ = %v", i, p.x, p.y, p.z)
41		}
42	}
43}
44
45func TestGenerator(t *testing.T) {
46	// These are the coordinates of B from RFC 8032, Section 5.1, converted to
47	// little endian hex.
48	x := "1ad5258f602d56c9b2a7259560c72c695cdcd6fd31e2a4c0fe536ecdd3366921"
49	y := "5866666666666666666666666666666666666666666666666666666666666666"
50	if got := hex.EncodeToString(B.x.Bytes()); got != x {
51		t.Errorf("wrong B.x: got %s, expected %s", got, x)
52	}
53	if got := hex.EncodeToString(B.y.Bytes()); got != y {
54		t.Errorf("wrong B.y: got %s, expected %s", got, y)
55	}
56	if B.z.Equal(feOne) != 1 {
57		t.Errorf("wrong B.z: got %v, expected 1", B.z)
58	}
59	// Check that t is correct.
60	checkOnCurve(t, B)
61}
62
63func TestAddSubNegOnBasePoint(t *testing.T) {
64	checkLhs, checkRhs := &Point{}, &Point{}
65
66	checkLhs.Add(B, B)
67	tmpP2 := new(projP2).FromP3(B)
68	tmpP1xP1 := new(projP1xP1).Double(tmpP2)
69	checkRhs.fromP1xP1(tmpP1xP1)
70	if checkLhs.Equal(checkRhs) != 1 {
71		t.Error("B + B != [2]B")
72	}
73	checkOnCurve(t, checkLhs, checkRhs)
74
75	checkLhs.Subtract(B, B)
76	Bneg := new(Point).Negate(B)
77	checkRhs.Add(B, Bneg)
78	if checkLhs.Equal(checkRhs) != 1 {
79		t.Error("B - B != B + (-B)")
80	}
81	if I.Equal(checkLhs) != 1 {
82		t.Error("B - B != 0")
83	}
84	if I.Equal(checkRhs) != 1 {
85		t.Error("B + (-B) != 0")
86	}
87	checkOnCurve(t, checkLhs, checkRhs, Bneg)
88}
89
90func TestComparable(t *testing.T) {
91	if reflect.TypeOf(Point{}).Comparable() {
92		t.Error("Point is unexpectedly comparable")
93	}
94}
95
96func TestInvalidEncodings(t *testing.T) {
97	// An invalid point, that also happens to have y > p.
98	invalid := "efffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f"
99	p := NewGeneratorPoint()
100	if out, err := p.SetBytes(decodeHex(invalid)); err == nil {
101		t.Error("expected error for invalid point")
102	} else if out != nil {
103		t.Error("SetBytes did not return nil on an invalid encoding")
104	} else if p.Equal(B) != 1 {
105		t.Error("the Point was modified while decoding an invalid encoding")
106	}
107	checkOnCurve(t, p)
108}
109
110func TestNonCanonicalPoints(t *testing.T) {
111	type test struct {
112		name                string
113		encoding, canonical string
114	}
115	tests := []test{
116		// Points with x = 0 and the sign bit set. With x = 0 the curve equation
117		// gives y² = 1, so y = ±1. 1 has two valid encodings.
118		{
119			"y=1,sign-",
120			"0100000000000000000000000000000000000000000000000000000000000080",
121			"0100000000000000000000000000000000000000000000000000000000000000",
122		},
123		{
124			"y=p+1,sign-",
125			"eeffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
126			"0100000000000000000000000000000000000000000000000000000000000000",
127		},
128		{
129			"y=p-1,sign-",
130			"ecffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
131			"ecffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
132		},
133
134		// Non-canonical y encodings with values 2²⁵⁵-19 (p) to 2²⁵⁵-1 (p+18).
135		{
136			"y=p,sign+",
137			"edffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
138			"0000000000000000000000000000000000000000000000000000000000000000",
139		},
140		{
141			"y=p,sign-",
142			"edffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
143			"0000000000000000000000000000000000000000000000000000000000000080",
144		},
145		{
146			"y=p+1,sign+",
147			"eeffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
148			"0100000000000000000000000000000000000000000000000000000000000000",
149		},
150		// "y=p+1,sign-" is already tested above.
151		// p+2 is not a valid y-coordinate.
152		{
153			"y=p+3,sign+",
154			"f0ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
155			"0300000000000000000000000000000000000000000000000000000000000000",
156		},
157		{
158			"y=p+3,sign-",
159			"f0ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
160			"0300000000000000000000000000000000000000000000000000000000000080",
161		},
162		{
163			"y=p+4,sign+",
164			"f1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
165			"0400000000000000000000000000000000000000000000000000000000000000",
166		},
167		{
168			"y=p+4,sign-",
169			"f1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
170			"0400000000000000000000000000000000000000000000000000000000000080",
171		},
172		{
173			"y=p+5,sign+",
174			"f2ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
175			"0500000000000000000000000000000000000000000000000000000000000000",
176		},
177		{
178			"y=p+5,sign-",
179			"f2ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
180			"0500000000000000000000000000000000000000000000000000000000000080",
181		},
182		{
183			"y=p+6,sign+",
184			"f3ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
185			"0600000000000000000000000000000000000000000000000000000000000000",
186		},
187		{
188			"y=p+6,sign-",
189			"f3ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
190			"0600000000000000000000000000000000000000000000000000000000000080",
191		},
192		// p+7 is not a valid y-coordinate.
193		// p+8 is not a valid y-coordinate.
194		{
195			"y=p+9,sign+",
196			"f6ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
197			"0900000000000000000000000000000000000000000000000000000000000000",
198		},
199		{
200			"y=p+9,sign-",
201			"f6ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
202			"0900000000000000000000000000000000000000000000000000000000000080",
203		},
204		{
205			"y=p+10,sign+",
206			"f7ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
207			"0a00000000000000000000000000000000000000000000000000000000000000",
208		},
209		{
210			"y=p+10,sign-",
211			"f7ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
212			"0a00000000000000000000000000000000000000000000000000000000000080",
213		},
214		// p+11 is not a valid y-coordinate.
215		// p+12 is not a valid y-coordinate.
216		// p+13 is not a valid y-coordinate.
217		{
218			"y=p+14,sign+",
219			"fbffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
220			"0e00000000000000000000000000000000000000000000000000000000000000",
221		},
222		{
223			"y=p+14,sign-",
224			"fbffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
225			"0e00000000000000000000000000000000000000000000000000000000000080",
226		},
227		{
228			"y=p+15,sign+",
229			"fcffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
230			"0f00000000000000000000000000000000000000000000000000000000000000",
231		},
232		{
233			"y=p+15,sign-",
234			"fcffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
235			"0f00000000000000000000000000000000000000000000000000000000000080",
236		},
237		{
238			"y=p+16,sign+",
239			"fdffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
240			"1000000000000000000000000000000000000000000000000000000000000000",
241		},
242		{
243			"y=p+16,sign-",
244			"fdffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
245			"1000000000000000000000000000000000000000000000000000000000000080",
246		},
247		// p+17 is not a valid y-coordinate.
248		{
249			"y=p+18,sign+",
250			"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
251			"1200000000000000000000000000000000000000000000000000000000000000",
252		},
253		{
254			"y=p+18,sign-",
255			"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
256			"1200000000000000000000000000000000000000000000000000000000000080",
257		},
258	}
259	for _, tt := range tests {
260		t.Run(tt.name, func(t *testing.T) {
261			p1, err := new(Point).SetBytes(decodeHex(tt.encoding))
262			if err != nil {
263				t.Fatalf("error decoding non-canonical point: %v", err)
264			}
265			p2, err := new(Point).SetBytes(decodeHex(tt.canonical))
266			if err != nil {
267				t.Fatalf("error decoding canonical point: %v", err)
268			}
269			if p1.Equal(p2) != 1 {
270				t.Errorf("equivalent points are not equal: %v, %v", p1, p2)
271			}
272			if encoding := hex.EncodeToString(p1.Bytes()); encoding != tt.canonical {
273				t.Errorf("re-encoding does not match canonical; got %q, expected %q", encoding, tt.canonical)
274			}
275			checkOnCurve(t, p1, p2)
276		})
277	}
278}
279
280var testAllocationsSink byte
281
282func TestAllocations(t *testing.T) {
283	testenv.SkipIfOptimizationOff(t)
284
285	if allocs := testing.AllocsPerRun(100, func() {
286		p := NewIdentityPoint()
287		p.Add(p, NewGeneratorPoint())
288		s := NewScalar()
289		testAllocationsSink ^= s.Bytes()[0]
290		testAllocationsSink ^= p.Bytes()[0]
291	}); allocs > 0 {
292		t.Errorf("expected zero allocations, got %0.1v", allocs)
293	}
294}
295
296func decodeHex(s string) []byte {
297	b, err := hex.DecodeString(s)
298	if err != nil {
299		panic(err)
300	}
301	return b
302}
303
304func BenchmarkEncodingDecoding(b *testing.B) {
305	p := new(Point).Set(dalekScalarBasepoint)
306	for i := 0; i < b.N; i++ {
307		buf := p.Bytes()
308		_, err := p.SetBytes(buf)
309		if err != nil {
310			b.Fatal(err)
311		}
312	}
313}
314