Debian Codegraph @

libgo/go/crypto/ed25519/internal/edwards25519/edwards25519_test.go

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