curve_test.go raw
1 // Copyright (c) 2015-2022 The Decred developers
2 // Copyright 2013-2016 The btcsuite developers
3 // Use of this source code is governed by an ISC
4 // license that can be found in the LICENSE file.
5
6 package secp256k1
7
8 import (
9 "fmt"
10 "math/big"
11 "math/bits"
12 "math/rand"
13 "testing"
14 "time"
15
16 "next.orly.dev/pkg/lol/chk"
17 )
18
19 var (
20 // oneModN is simply the number 1 as a mod n scalar.
21 oneModN = hexToModNScalar("1")
22 // endoLambda is the positive version of the lambda constant used in the
23 // endomorphism. It is stored here for convenience and to avoid recomputing
24 // it throughout the tests.
25 endoLambda = new(ModNScalar).NegateVal(endoNegLambda)
26 )
27
28 // isValidJacobianPoint returns true if the point (x,y,z) is on the secp256k1
29 // curve or is the point at infinity.
30 func isValidJacobianPoint(point *JacobianPoint) bool {
31 if (point.X.IsZero() && point.Y.IsZero()) || point.Z.IsZero() {
32 return true
33 }
34 // Elliptic curve equation for secp256k1 is: y^2 = x^3 + 7
35 // In Jacobian coordinates, Y = y/z^3 and X = x/z^2
36 // Thus:
37 // (y/z^3)^2 = (x/z^2)^3 + 7
38 // y^2/z^6 = x^3/z^6 + 7
39 // y^2 = x^3 + 7*z^6
40 var y2, z2, x3, result FieldVal
41 y2.SquareVal(&point.Y).Normalize()
42 z2.SquareVal(&point.Z)
43 x3.SquareVal(&point.X).Mul(&point.X)
44 result.SquareVal(&z2).Mul(&z2).MulInt(7).Add(&x3).Normalize()
45 return y2.Equals(&result)
46 }
47
48 // jacobianPointFromHex decodes the passed big-endian hex strings into a
49 // Jacobian point with its internal fields set to the resulting values. Only
50 // the first 32-bytes are used.
51 func jacobianPointFromHex(x, y, z string) JacobianPoint {
52 var p JacobianPoint
53 p.X.SetHex(x)
54 p.Y.SetHex(y)
55 p.Z.SetHex(z)
56 return p
57 }
58
59 // IsStrictlyEqual returns whether or not the two Jacobian points are strictly
60 // equal for use in the tests. Recall that several Jacobian points can be equal
61 // in affine coordinates, while not having the same coordinates in projective
62 // space, so the two points not being equal doesn't necessarily mean they aren't
63 // actually the same affine point.
64 func (p *JacobianPoint) IsStrictlyEqual(other *JacobianPoint) bool {
65 return p.X.Equals(&other.X) && p.Y.Equals(&other.Y) && p.Z.Equals(&other.Z)
66 }
67
68 // TestAddJacobian tests addition of points projected in Jacobian coordinates
69 // works as intended.
70 func TestAddJacobian(t *testing.T) {
71 tests := []struct {
72 name string // test description
73 x1, y1, z1 string // hex encoded coordinates of first point to add
74 x2, y2, z2 string // hex encoded coordinates of second point to add
75 x3, y3, z3 string // hex encoded coordinates of expected point
76 }{
77 {
78 // Addition with the point at infinity (left hand side).
79 name: "∞ + P = P",
80 x1: "0",
81 y1: "0",
82 z1: "0",
83 x2: "d74bf844b0862475103d96a611cf2d898447e288d34b360bc885cb8ce7c00575",
84 y2: "131c670d414c4546b88ac3ff664611b1c38ceb1c21d76369d7a7a0969d61d97d",
85 z2: "1",
86 x3: "d74bf844b0862475103d96a611cf2d898447e288d34b360bc885cb8ce7c00575",
87 y3: "131c670d414c4546b88ac3ff664611b1c38ceb1c21d76369d7a7a0969d61d97d",
88 z3: "1",
89 }, {
90 // Addition with the point at infinity (right hand side).
91 name: "P + ∞ = P",
92 x1: "d74bf844b0862475103d96a611cf2d898447e288d34b360bc885cb8ce7c00575",
93 y1: "131c670d414c4546b88ac3ff664611b1c38ceb1c21d76369d7a7a0969d61d97d",
94 z1: "1",
95 x2: "0",
96 y2: "0",
97 z2: "0",
98 x3: "d74bf844b0862475103d96a611cf2d898447e288d34b360bc885cb8ce7c00575",
99 y3: "131c670d414c4546b88ac3ff664611b1c38ceb1c21d76369d7a7a0969d61d97d",
100 z3: "1",
101 }, {
102 // Addition with z1=z2=1 different x values.
103 name: "P(x1, y1, 1) + P(x2, y1, 1)",
104 x1: "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
105 y1: "0b71ea9bd730fd8923f6d25a7a91e7dd7728a960686cb5a901bb419e0f2ca232",
106 z1: "1",
107 x2: "d74bf844b0862475103d96a611cf2d898447e288d34b360bc885cb8ce7c00575",
108 y2: "131c670d414c4546b88ac3ff664611b1c38ceb1c21d76369d7a7a0969d61d97d",
109 z2: "1",
110 x3: "0cfbc7da1e569b334460788faae0286e68b3af7379d5504efc25e4dba16e46a6",
111 y3: "e205f79361bbe0346b037b4010985dbf4f9e1e955e7d0d14aca876bfa79aad87",
112 z3: "44a5646b446e3877a648d6d381370d9ef55a83b666ebce9df1b1d7d65b817b2f",
113 }, {
114 // Addition with z1=z2=1 same x opposite y.
115 name: "P(x, y, 1) + P(x, -y, 1) = ∞",
116 x1: "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
117 y1: "0b71ea9bd730fd8923f6d25a7a91e7dd7728a960686cb5a901bb419e0f2ca232",
118 z1: "1",
119 x2: "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
120 y2: "f48e156428cf0276dc092da5856e182288d7569f97934a56fe44be60f0d359fd",
121 z2: "1",
122 x3: "0",
123 y3: "0",
124 z3: "0",
125 }, {
126 // Addition with z1=z2=1 same point.
127 name: "P(x, y, 1) + P(x, y, 1) = 2P",
128 x1: "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
129 y1: "0b71ea9bd730fd8923f6d25a7a91e7dd7728a960686cb5a901bb419e0f2ca232",
130 z1: "1",
131 x2: "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
132 y2: "0b71ea9bd730fd8923f6d25a7a91e7dd7728a960686cb5a901bb419e0f2ca232",
133 z2: "1",
134 x3: "ec9f153b13ee7bd915882859635ea9730bf0dc7611b2c7b0e37ee64f87c50c27",
135 y3: "b082b53702c466dcf6e984a35671756c506c67c2fcb8adb408c44dd0755c8f2a",
136 z3: "16e3d537ae61fb1247eda4b4f523cfbaee5152c0d0d96b520376833c1e594464",
137 }, {
138 // Addition with z1=z2 (!=1) different x values.
139 name: "P(x1, y1, 2) + P(x2, y2, 2)",
140 x1: "d3e5183c393c20e4f464acf144ce9ae8266a82b67f553af33eb37e88e7fd2718",
141 y1: "5b8f54deb987ec491fb692d3d48f3eebb9454b034365ad480dda0cf079651190",
142 z1: "2",
143 x2: "5d2fe112c21891d440f65a98473cb626111f8a234d2cd82f22172e369f002147",
144 y2: "98e3386a0a622a35c4561ffb32308d8e1c6758e10ebb1b4ebd3d04b4eb0ecbe8",
145 z2: "2",
146 x3: "cfbc7da1e569b334460788faae0286e68b3af7379d5504efc25e4dba16e46a60",
147 y3: "817de4d86ef80d1ac0ded00426176fd3e787a5579f43452b2a1db021e6ac3778",
148 z3: "129591ad11b8e1de99235b4e04dc367bd56a0ed99baf3a77c6c75f5a6e05f08d",
149 }, {
150 // Addition with z1=z2 (!=1) same x opposite y.
151 name: "P(x, y, 2) + P(x, -y, 2) = ∞",
152 x1: "d3e5183c393c20e4f464acf144ce9ae8266a82b67f553af33eb37e88e7fd2718",
153 y1: "5b8f54deb987ec491fb692d3d48f3eebb9454b034365ad480dda0cf079651190",
154 z1: "2",
155 x2: "d3e5183c393c20e4f464acf144ce9ae8266a82b67f553af33eb37e88e7fd2718",
156 y2: "a470ab21467813b6e0496d2c2b70c11446bab4fcbc9a52b7f225f30e869aea9f",
157 z2: "2",
158 x3: "0",
159 y3: "0",
160 z3: "0",
161 }, {
162 // Addition with z1=z2 (!=1) same point.
163 name: "P(x, y, 2) + P(x, y, 2) = 2P",
164 x1: "d3e5183c393c20e4f464acf144ce9ae8266a82b67f553af33eb37e88e7fd2718",
165 y1: "5b8f54deb987ec491fb692d3d48f3eebb9454b034365ad480dda0cf079651190",
166 z1: "2",
167 x2: "d3e5183c393c20e4f464acf144ce9ae8266a82b67f553af33eb37e88e7fd2718",
168 y2: "5b8f54deb987ec491fb692d3d48f3eebb9454b034365ad480dda0cf079651190",
169 z2: "2",
170 x3: "9f153b13ee7bd915882859635ea9730bf0dc7611b2c7b0e37ee65073c50fabac",
171 y3: "2b53702c466dcf6e984a35671756c506c67c2fcb8adb408c44dd125dc91cb988",
172 z3: "6e3d537ae61fb1247eda4b4f523cfbaee5152c0d0d96b520376833c2e5944a11",
173 }, {
174 // Addition with z1!=z2 and z2=1 different x values.
175 name: "P(x1, y1, 2) + P(x2, y2, 1)",
176 x1: "d3e5183c393c20e4f464acf144ce9ae8266a82b67f553af33eb37e88e7fd2718",
177 y1: "5b8f54deb987ec491fb692d3d48f3eebb9454b034365ad480dda0cf079651190",
178 z1: "2",
179 x2: "d74bf844b0862475103d96a611cf2d898447e288d34b360bc885cb8ce7c00575",
180 y2: "131c670d414c4546b88ac3ff664611b1c38ceb1c21d76369d7a7a0969d61d97d",
181 z2: "1",
182 x3: "3ef1f68795a6ccd1181e23eab80a1b9a2cebdcde755413bf097936eb5b91b4f3",
183 y3: "0bef26c377c068d606f6802130bb7e9f3c3d2abcfa1a295950ed81133561cb04",
184 z3: "252b235a2371c3bd3246b69c09b86cf7aad41db3375e74ef8d8ebeb4dc0be11a",
185 }, {
186 // Addition with z1!=z2 and z2=1 same x opposite y.
187 name: "P(x, y, 2) + P(x, -y, 1) = ∞",
188 x1: "d3e5183c393c20e4f464acf144ce9ae8266a82b67f553af33eb37e88e7fd2718",
189 y1: "5b8f54deb987ec491fb692d3d48f3eebb9454b034365ad480dda0cf079651190",
190 z1: "2",
191 x2: "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
192 y2: "f48e156428cf0276dc092da5856e182288d7569f97934a56fe44be60f0d359fd",
193 z2: "1",
194 x3: "0",
195 y3: "0",
196 z3: "0",
197 }, {
198 // Addition with z1!=z2 and z2=1 same point.
199 name: "P(x, y, 2) + P(x, y, 1) = 2P",
200 x1: "d3e5183c393c20e4f464acf144ce9ae8266a82b67f553af33eb37e88e7fd2718",
201 y1: "5b8f54deb987ec491fb692d3d48f3eebb9454b034365ad480dda0cf079651190",
202 z1: "2",
203 x2: "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
204 y2: "0b71ea9bd730fd8923f6d25a7a91e7dd7728a960686cb5a901bb419e0f2ca232",
205 z2: "1",
206 x3: "9f153b13ee7bd915882859635ea9730bf0dc7611b2c7b0e37ee65073c50fabac",
207 y3: "2b53702c466dcf6e984a35671756c506c67c2fcb8adb408c44dd125dc91cb988",
208 z3: "6e3d537ae61fb1247eda4b4f523cfbaee5152c0d0d96b520376833c2e5944a11",
209 }, {
210 // Addition with z1!=z2 and z2!=1 different x values.
211 name: "P(x1, y1, 2) + P(x2, y2, 3)",
212 x1: "d3e5183c393c20e4f464acf144ce9ae8266a82b67f553af33eb37e88e7fd2718",
213 y1: "5b8f54deb987ec491fb692d3d48f3eebb9454b034365ad480dda0cf079651190",
214 z1: "2",
215 x2: "91abba6a34b7481d922a4bd6a04899d5a686f6cf6da4e66a0cb427fb25c04bd4",
216 y2: "03fede65e30b4e7576a2abefc963ddbf9fdccbf791b77c29beadefe49951f7d1",
217 z2: "3",
218 x3: "3f07081927fd3f6dadd4476614c89a09eba7f57c1c6c3b01fa2d64eac1eef31e",
219 y3: "949166e04ebc7fd95a9d77e5dfd88d1492ecffd189792e3944eb2b765e09e031",
220 z3: "eb8cba81bcffa4f44d75427506737e1f045f21e6d6f65543ee0e1d163540c931",
221 }, {
222 // Addition with z1!=z2 and z2!=1 same x opposite y.
223 name: "P(x, y, 2) + P(x, -y, 3) = ∞",
224 x1: "d3e5183c393c20e4f464acf144ce9ae8266a82b67f553af33eb37e88e7fd2718",
225 y1: "5b8f54deb987ec491fb692d3d48f3eebb9454b034365ad480dda0cf079651190",
226 z1: "2",
227 x2: "dcc3768780c74a0325e2851edad0dc8a566fa61a9e7fc4a34d13dcb509f99bc7",
228 y2: "cafc41904dd5428934f7d075129c8ba46eb622d4fc88d72cd1401452664add18",
229 z2: "3",
230 x3: "0",
231 y3: "0",
232 z3: "0",
233 }, {
234 // Addition with z1!=z2 and z2!=1 same point.
235 name: "P(x, y, 2) + P(x, y, 3) = 2P",
236 x1: "d3e5183c393c20e4f464acf144ce9ae8266a82b67f553af33eb37e88e7fd2718",
237 y1: "5b8f54deb987ec491fb692d3d48f3eebb9454b034365ad480dda0cf079651190",
238 z1: "2",
239 x2: "dcc3768780c74a0325e2851edad0dc8a566fa61a9e7fc4a34d13dcb509f99bc7",
240 y2: "3503be6fb22abd76cb082f8aed63745b9149dd2b037728d32ebfebac99b51f17",
241 z2: "3",
242 x3: "9f153b13ee7bd915882859635ea9730bf0dc7611b2c7b0e37ee65073c50fabac",
243 y3: "2b53702c466dcf6e984a35671756c506c67c2fcb8adb408c44dd125dc91cb988",
244 z3: "6e3d537ae61fb1247eda4b4f523cfbaee5152c0d0d96b520376833c2e5944a11",
245 },
246 }
247 for _, test := range tests {
248 // Convert hex to Jacobian points.
249 p1 := jacobianPointFromHex(test.x1, test.y1, test.z1)
250 p2 := jacobianPointFromHex(test.x2, test.y2, test.z2)
251 want := jacobianPointFromHex(test.x3, test.y3, test.z3)
252
253 // Ensure the test data is using points that are actually on the curve
254 // (or the point at infinity).
255 if !isValidJacobianPoint(&p1) {
256 t.Errorf("%s: first point is not on the curve", test.name)
257 continue
258 }
259 if !isValidJacobianPoint(&p2) {
260 t.Errorf("%s: second point is not on the curve", test.name)
261 continue
262 }
263 if !isValidJacobianPoint(&want) {
264 t.Errorf("%s: expected point is not on the curve", test.name)
265 continue
266 }
267 // Add the two points.
268 var r JacobianPoint
269 AddNonConst(&p1, &p2, &r)
270 // Ensure result matches expected.
271 if !r.IsStrictlyEqual(&want) {
272 t.Errorf(
273 "%s: wrong result\ngot: (%v, %v, %v)\nwant: (%v, %v, %v)",
274 test.name, r.X, r.Y, r.Z, want.X, want.Y, want.Z,
275 )
276 continue
277 }
278 }
279 }
280
281 // TestDoubleJacobian tests doubling of points projected in Jacobian coordinates
282 // works as intended for some edge cases and known good values.
283 func TestDoubleJacobian(t *testing.T) {
284 tests := []struct {
285 name string // test description
286 x1, y1, z1 string // hex encoded coordinates of point to double
287 x3, y3, z3 string // hex encoded coordinates of expected point
288 }{
289 {
290 // Doubling the point at infinity is still infinity.
291 name: "2*∞ = ∞ (point at infinity)",
292 x1: "0",
293 y1: "0",
294 z1: "0",
295 x3: "0",
296 y3: "0",
297 z3: "0",
298 }, {
299 // Doubling with z1=1.
300 name: "2*P(x, y, 1)",
301 x1: "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
302 y1: "0b71ea9bd730fd8923f6d25a7a91e7dd7728a960686cb5a901bb419e0f2ca232",
303 z1: "1",
304 x3: "ec9f153b13ee7bd915882859635ea9730bf0dc7611b2c7b0e37ee64f87c50c27",
305 y3: "b082b53702c466dcf6e984a35671756c506c67c2fcb8adb408c44dd0755c8f2a",
306 z3: "16e3d537ae61fb1247eda4b4f523cfbaee5152c0d0d96b520376833c1e594464",
307 }, {
308 // Doubling with z1!=1.
309 name: "2*P(x, y, 2)",
310 x1: "d3e5183c393c20e4f464acf144ce9ae8266a82b67f553af33eb37e88e7fd2718",
311 y1: "5b8f54deb987ec491fb692d3d48f3eebb9454b034365ad480dda0cf079651190",
312 z1: "2",
313 x3: "9f153b13ee7bd915882859635ea9730bf0dc7611b2c7b0e37ee65073c50fabac",
314 y3: "2b53702c466dcf6e984a35671756c506c67c2fcb8adb408c44dd125dc91cb988",
315 z3: "6e3d537ae61fb1247eda4b4f523cfbaee5152c0d0d96b520376833c2e5944a11",
316 }, {
317 // From btcd issue #709.
318 name: "carry to bit 256 during normalize",
319 x1: "201e3f75715136d2f93c4f4598f91826f94ca01f4233a5bd35de9708859ca50d",
320 y1: "bdf18566445e7562c6ada68aef02d498d7301503de5b18c6aef6e2b1722412e1",
321 z1: "0000000000000000000000000000000000000000000000000000000000000001",
322 x3: "4a5e0559863ebb4e9ed85f5c4fa76003d05d9a7626616e614a1f738621e3c220",
323 y3: "00000000000000000000000000000000000000000000000000000001b1388778",
324 z3: "7be30acc88bceac58d5b4d15de05a931ae602a07bcb6318d5dedc563e4482993",
325 },
326 }
327 for _, test := range tests {
328 // Convert hex to field values.
329 p1 := jacobianPointFromHex(test.x1, test.y1, test.z1)
330 want := jacobianPointFromHex(test.x3, test.y3, test.z3)
331
332 // Ensure the test data is using points that are actually on the curve
333 // (or the point at infinity).
334 if !isValidJacobianPoint(&p1) {
335 t.Errorf("%s: first point is not on the curve", test.name)
336 continue
337 }
338 if !isValidJacobianPoint(&want) {
339 t.Errorf("%s: expected point is not on the curve", test.name)
340 continue
341 }
342 // Double the point.
343 var result JacobianPoint
344 DoubleNonConst(&p1, &result)
345 // Ensure result matches expected.
346 if !result.IsStrictlyEqual(&want) {
347 t.Errorf(
348 "%s: wrong result\ngot: (%v, %v, %v)\nwant: (%v, %v, %v)",
349 test.name, result.X, result.Y, result.Z, want.X, want.Y,
350 want.Z,
351 )
352 continue
353 }
354 }
355 }
356
357 // checkNAFEncoding returns an error if the provided positive and negative
358 // portions of an overall NAF encoding do not adhere to the requirements or they
359 // do not sum back to the provided original value.
360 func checkNAFEncoding(pos, neg []byte, origValue *big.Int) (err error) {
361 // NAF must not have a leading zero byte and the number of negative
362 // bytes must not exceed the positive portion.
363 if len(pos) > 0 && pos[0] == 0 {
364 return fmt.Errorf("positive has leading zero -- got %x", pos)
365 }
366 if len(neg) > len(pos) {
367 return fmt.Errorf(
368 "negative has len %d > pos len %d", len(neg),
369 len(pos),
370 )
371 }
372 // Ensure the result doesn't have any adjacent non-zero digits.
373 gotPos := new(big.Int).SetBytes(pos)
374 gotNeg := new(big.Int).SetBytes(neg)
375 posOrNeg := new(big.Int).Or(gotPos, gotNeg)
376 prevBit := posOrNeg.Bit(0)
377 for bit := 1; bit < posOrNeg.BitLen(); bit++ {
378 thisBit := posOrNeg.Bit(bit)
379 if prevBit == 1 && thisBit == 1 {
380 return fmt.Errorf(
381 "adjacent non-zero digits found at bit pos %d",
382 bit-1,
383 )
384 }
385 prevBit = thisBit
386 }
387 // Ensure the resulting positive and negative portions of the overall
388 // NAF representation sum back to the original value.
389 gotValue := new(big.Int).Sub(gotPos, gotNeg)
390 if origValue.Cmp(gotValue) != 0 {
391 return fmt.Errorf(
392 "pos-neg is not original value: got %x, want %x",
393 gotValue, origValue,
394 )
395 }
396 return nil
397 }
398
399 // TestNAF ensures encoding various edge cases and values to non-adjacent form
400 // produces valid results.
401 func TestNAF(t *testing.T) {
402 tests := []struct {
403 name string // test description
404 in string // hex encoded test value
405 }{
406 {
407 name: "empty is zero",
408 in: "",
409 }, {
410 name: "zero",
411 in: "00",
412 }, {
413 name: "just before first carry",
414 in: "aa",
415 }, {
416 name: "first carry",
417 in: "ab",
418 }, {
419 name: "leading zeroes",
420 in: "002f20569b90697ad471c1be6107814f53f47446be298a3a2a6b686b97d35cf9",
421 }, {
422 name: "257 bits when NAF encoded",
423 in: "c000000000000000000000000000000000000000000000000000000000000001",
424 }, {
425 name: "32-byte scalar",
426 in: "6df2b5d30854069ccdec40ae022f5c948936324a4e9ebed8eb82cfd5a6b6d766",
427 }, {
428 name: "first term of balanced length-two representation #1",
429 in: "b776e53fb55f6b006a270d42d64ec2b1",
430 }, {
431 name: "second term balanced length-two representation #1",
432 in: "d6cc32c857f1174b604eefc544f0c7f7",
433 }, {
434 name: "first term of balanced length-two representation #2",
435 in: "45c53aa1bb56fcd68c011e2dad6758e4",
436 }, {
437 name: "second term of balanced length-two representation #2",
438 in: "a2e79d200f27f2360fba57619936159b",
439 },
440 }
441 for _, test := range tests {
442 // Ensure the resulting positive and negative portions of the overall
443 // NAF representation adhere to the requirements of NAF encoding and
444 // they sum back to the original value.
445 result := naf(hexToBytes(test.in))
446 pos, neg := result.Pos(), result.Neg()
447 if err := checkNAFEncoding(pos, neg, fromHex(test.in)); chk.T(err) {
448 t.Errorf("%q: %v", test.name, err)
449 }
450 }
451 }
452
453 // TestNAFRandom ensures that encoding randomly-generated values to non-adjacent
454 // form produces valid results.
455 func TestNAFRandom(t *testing.T) {
456 // Use a unique random seed each test instance and log it if the tests fail.
457 seed := time.Now().Unix()
458 rng := rand.New(rand.NewSource(seed))
459 defer func(t *testing.T, seed int64) {
460 if t.Failed() {
461 t.Logf("random seed: %d", seed)
462 }
463 }(t, seed)
464 for i := 0; i < 100; i++ {
465 // Ensure the resulting positive and negative portions of the overall
466 // NAF representation adhere to the requirements of NAF encoding and
467 // they sum back to the original value.
468 bigIntVal, modNVal := randIntAndModNScalar(t, rng)
469 valBytes := modNVal.Bytes()
470 result := naf(valBytes[:])
471 pos, neg := result.Pos(), result.Neg()
472 if err := checkNAFEncoding(pos, neg, bigIntVal); chk.T(err) {
473 t.Fatalf(
474 "encoding err: %v\nin: %x\npos: %x\nneg: %x", err,
475 bigIntVal, pos, neg,
476 )
477 }
478 }
479 }
480
481 // TestScalarBaseMultJacobian ensures multiplying a given scalar by the base
482 // point projected in Jacobian coordinates works as intended for some edge cases
483 // and known values. It also verifies in affine coordinates as well.
484 func TestScalarBaseMultJacobian(t *testing.T) {
485 tests := []struct {
486 name string // test description
487 k string // hex encoded scalar
488 x1, y1, z1 string // hex encoded Jacobian coordinates of expected point
489 x2, y2 string // hex encoded affine coordinates of expected point
490 }{
491 {
492 name: "zero",
493 k: "0000000000000000000000000000000000000000000000000000000000000000",
494 x1: "0000000000000000000000000000000000000000000000000000000000000000",
495 y1: "0000000000000000000000000000000000000000000000000000000000000000",
496 z1: "0000000000000000000000000000000000000000000000000000000000000001",
497 x2: "0000000000000000000000000000000000000000000000000000000000000000",
498 y2: "0000000000000000000000000000000000000000000000000000000000000000",
499 }, {
500 name: "one (aka 1*G = G)",
501 k: "0000000000000000000000000000000000000000000000000000000000000001",
502 x1: "79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798",
503 y1: "483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8",
504 z1: "0000000000000000000000000000000000000000000000000000000000000001",
505 x2: "79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798",
506 y2: "483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8",
507 }, {
508 name: "group order - 1 (aka -1*G = -G)",
509 k: "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140",
510 x1: "667d5346809ba7602db1ea0bd990eee6ff75d7a64004d563534123e6f12a12d7",
511 y1: "344f2f772f8f4cbd04709dba7837ff1422db8fa6f99a00f93852de2c45284838",
512 z1: "19e5a058ef4eaada40d19063917bb4dc07f50c3a0f76bd5348a51057a3721c57",
513 x2: "79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798",
514 y2: "b7c52588d95c3b9aa25b0403f1eef75702e84bb7597aabe663b82f6f04ef2777",
515 }, {
516 name: "known good point 1",
517 k: "aa5e28d6a97a2479a65527f7290311a3624d4cc0fa1578598ee3c2613bf99522",
518 x1: "5f64fd9364bac24dc32bc01b7d63aaa8249babbdc26b03233e14120840ae20f6",
519 y1: "a4ced9be1e1ed6ef73bec6866c3adc0695347303c30b814fb0dfddb3a22b090d",
520 z1: "931a3477a1b1d866842b22577618e134c89ba12e5bb38c465265c8a2cefa69dc",
521 x2: "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
522 y2: "0b71ea9bd730fd8923f6d25a7a91e7dd7728a960686cb5a901bb419e0f2ca232",
523 }, {
524 name: "known good point 2",
525 k: "7e2b897b8cebc6361663ad410835639826d590f393d90a9538881735256dfae3",
526 x1: "c2cb761af4d6410bea0ed7d5f3c7397b63739b0f37e5c3047f8a45537a9d413e",
527 y1: "34b9204c55336d2fb94e20e53d5aa2ffe4da6f80d72315b4dcafca11e7c0f768",
528 z1: "ca5d9e8024575c80fe185416ff4736aff8278873da60cf101d10ab49780ee33b",
529 x2: "d74bf844b0862475103d96a611cf2d898447e288d34b360bc885cb8ce7c00575",
530 y2: "131c670d414c4546b88ac3ff664611b1c38ceb1c21d76369d7a7a0969d61d97d",
531 }, {
532 name: "known good point 3",
533 k: "6461e6df0fe7dfd05329f41bf771b86578143d4dd1f7866fb4ca7e97c5fa945d",
534 x1: "09160b87ee751ef9fd51db49afc7af9c534917fad72bf461d21fec2590878267",
535 y1: "dbc2757c5038e0b059d1e05c2d3706baf1a164e3836a02c240173b22c92da7c0",
536 z1: "c157ea3f784c37603d9f55e661dd1d6b8759fccbfb2c8cf64c46529d94c8c950",
537 x2: "e8aecc370aedd953483719a116711963ce201ac3eb21d3f3257bb48668c6a72f",
538 y2: "c25caf2f0eba1ddb2f0f3f47866299ef907867b7d27e95b3873bf98397b24ee1",
539 }, {
540 name: "known good point 4",
541 k: "376a3a2cdcd12581efff13ee4ad44c4044b8a0524c42422a7e1e181e4deeccec",
542 x1: "7820c46de3b5a0202bea06870013fcb23adb4a000f89d5b86fe1df24be58fa79",
543 y1: "95e5a977eb53a582677ff0432eef5bc66f1dd983c3e8c07e1c77c3655542c31e",
544 z1: "7d71ecfdfa66b003fe96f925b5907f67a1a4a6489f4940ec3b78edbbf847334f",
545 x2: "14890e61fcd4b0bd92e5b36c81372ca6fed471ef3aa60a3e415ee4fe987daba1",
546 y2: "297b858d9f752ab42d3bca67ee0eb6dcd1c2b7b0dbe23397e66adc272263f982",
547 }, {
548 name: "known good point 5",
549 k: "1b22644a7be026548810c378d0b2994eefa6d2b9881803cb02ceff865287d1b9",
550 x1: "68a934fa2d28fb0b0d2b6801a9335d62e65acef9467be2ea67f5b11614b59c78",
551 y1: "5edd7491e503acf61ed651a10cf466de06bf5c6ba285a7a2885a384bbdd32898",
552 z1: "f3b28d36c3132b6f4bd66bf0da64b8dc79d66f9a854ba8b609558b6328796755",
553 x2: "f73c65ead01c5126f28f442d087689bfa08e12763e0cec1d35b01751fd735ed3",
554 y2: "f449a8376906482a84ed01479bd18882b919c140d638307f0c0934ba12590bde",
555 },
556 }
557 for _, test := range tests {
558 // Parse test data.
559 want := jacobianPointFromHex(test.x1, test.y1, test.z1)
560 wantAffine := jacobianPointFromHex(test.x2, test.y2, "01")
561 k := hexToModNScalar(test.k)
562 // Ensure the test data is using points that are actually on the curve
563 // (or the point at infinity).
564 if !isValidJacobianPoint(&want) {
565 t.Errorf("%q: expected point is not on the curve", test.name)
566 continue
567 }
568 if !isValidJacobianPoint(&wantAffine) {
569 t.Errorf("%q: expected affine point is not on the curve", test.name)
570 continue
571 }
572 // Ensure the result matches the expected value in Jacobian coordinates.
573 var r JacobianPoint
574 ScalarBaseMultNonConst(k, &r)
575 if !r.IsStrictlyEqual(&want) {
576 t.Errorf(
577 "%q: wrong result:\ngot: (%s, %s, %s)\nwant: (%s, %s, %s)",
578 test.name, r.X, r.Y, r.Z, want.X, want.Y, want.Z,
579 )
580 continue
581 }
582 // Ensure the result matches the expected value in affine coordinates.
583 r.ToAffine()
584 if !r.IsStrictlyEqual(&wantAffine) {
585 t.Errorf(
586 "%q: wrong affine result:\ngot: (%s, %s)\nwant: (%s, %s)",
587 test.name, r.X, r.Y, wantAffine.X, wantAffine.Y,
588 )
589 continue
590 }
591 }
592 }
593
594 // modNBitLen returns the minimum number of bits required to represent the mod n
595 // scalar. The result is 0 when the value is 0.
596 func modNBitLen(s *ModNScalar) uint16 {
597 if w := s.n[7]; w > 0 {
598 return uint16(bits.Len32(w)) + 224
599 }
600 if w := s.n[6]; w > 0 {
601 return uint16(bits.Len32(w)) + 192
602 }
603 if w := s.n[5]; w > 0 {
604 return uint16(bits.Len32(w)) + 160
605 }
606 if w := s.n[4]; w > 0 {
607 return uint16(bits.Len32(w)) + 128
608 }
609 if w := s.n[3]; w > 0 {
610 return uint16(bits.Len32(w)) + 96
611 }
612 if w := s.n[2]; w > 0 {
613 return uint16(bits.Len32(w)) + 64
614 }
615 if w := s.n[1]; w > 0 {
616 return uint16(bits.Len32(w)) + 32
617 }
618 return uint16(bits.Len32(s.n[0]))
619 }
620
621 // checkLambdaDecomposition returns an error if the provided decomposed scalars
622 // do not satisfy the required equation or they are not small in magnitude.
623 func checkLambdaDecomposition(origK, k1, k2 *ModNScalar) (err error) {
624 // Recompose the scalar from the decomposed scalars to ensure they satisfy
625 // the required equation.
626 calcK := new(ModNScalar).Mul2(k2, endoLambda).Add(k1)
627 if !calcK.Equals(origK) {
628 return fmt.Errorf("recomposed scalar %v != orig scalar", calcK)
629 }
630 // Ensure the decomposed scalars are small in magnitude by affirming their
631 // bit lengths do not exceed one more than half of the bit size of the
632 // underlying field. This value is max(||v1||, ||v2||), where:
633 //
634 // vector v1 = <endoA1, endoB1>
635 // vector v2 = <endoA2, endoB2>
636 const maxBitLen = 129
637 if k1.IsOverHalfOrder() {
638 k1.Negate()
639 }
640 if k2.IsOverHalfOrder() {
641 k2.Negate()
642 }
643 k1BitLen, k2BitLen := modNBitLen(k1), modNBitLen(k2)
644 if k1BitLen > maxBitLen {
645 return fmt.Errorf(
646 "k1 scalar bit len %d > max allowed %d",
647 k1BitLen, maxBitLen,
648 )
649 }
650 if k2BitLen > maxBitLen {
651 return fmt.Errorf(
652 "k2 scalar bit len %d > max allowed %d",
653 k2BitLen, maxBitLen,
654 )
655 }
656 return nil
657 }
658
659 // TestSplitK ensures decomposing various edge cases and values into a balanced
660 // length-two representation produces valid results.
661 func TestSplitK(t *testing.T) {
662 // Values computed from the group half order and lambda such that they
663 // exercise the decomposition edge cases and maximize the bit lengths of the
664 // produced scalars.
665 h := "7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0"
666 negOne := new(ModNScalar).NegateVal(oneModN)
667 halfOrder := hexToModNScalar(h)
668 halfOrderMOne := new(ModNScalar).Add2(halfOrder, negOne)
669 halfOrderPOne := new(ModNScalar).Add2(halfOrder, oneModN)
670 lambdaMOne := new(ModNScalar).Add2(endoLambda, negOne)
671 lambdaPOne := new(ModNScalar).Add2(endoLambda, oneModN)
672 negLambda := new(ModNScalar).NegateVal(endoLambda)
673 halfOrderMOneMLambda := new(ModNScalar).Add2(halfOrderMOne, negLambda)
674 halfOrderMLambda := new(ModNScalar).Add2(halfOrder, negLambda)
675 halfOrderPOneMLambda := new(ModNScalar).Add2(halfOrderPOne, negLambda)
676 lambdaPHalfOrder := new(ModNScalar).Add2(endoLambda, halfOrder)
677 lambdaPOnePHalfOrder := new(ModNScalar).Add2(lambdaPOne, halfOrder)
678 tests := []struct {
679 name string // test description
680 k *ModNScalar // scalar to decompose
681 }{
682 {
683 name: "zero",
684 k: new(ModNScalar),
685 }, {
686 name: "one",
687 k: oneModN,
688 }, {
689 name: "group order - 1 (aka -1 mod N)",
690 k: negOne,
691 }, {
692 name: "group half order - 1 - lambda",
693 k: halfOrderMOneMLambda,
694 }, {
695 name: "group half order - lambda",
696 k: halfOrderMLambda,
697 }, {
698 name: "group half order + 1 - lambda",
699 k: halfOrderPOneMLambda,
700 }, {
701 name: "group half order - 1",
702 k: halfOrderMOne,
703 }, {
704 name: "group half order",
705 k: halfOrder,
706 }, {
707 name: "group half order + 1",
708 k: halfOrderPOne,
709 }, {
710 name: "lambda - 1",
711 k: lambdaMOne,
712 }, {
713 name: "lambda",
714 k: endoLambda,
715 }, {
716 name: "lambda + 1",
717 k: lambdaPOne,
718 }, {
719 name: "lambda + group half order",
720 k: lambdaPHalfOrder,
721 }, {
722 name: "lambda + 1 + group half order",
723 k: lambdaPOnePHalfOrder,
724 },
725 }
726 for _, test := range tests {
727 // Decompose the scalar and ensure the resulting decomposition satisfies
728 // the required equation and consists of scalars that are small in
729 // magnitude.
730 k1, k2 := splitK(test.k)
731 if err := checkLambdaDecomposition(test.k, &k1, &k2); chk.T(err) {
732 t.Errorf("%q: %v", test.name, err)
733 }
734 }
735 }
736
737 // TestSplitKRandom ensures that decomposing randomly-generated scalars into a
738 // balanced length-two representation produces valid results.
739 func TestSplitKRandom(t *testing.T) {
740 // Use a unique random seed each test instance and log it if the tests fail.
741 seed := time.Now().Unix()
742 rng := rand.New(rand.NewSource(seed))
743 defer func(t *testing.T, seed int64) {
744 if t.Failed() {
745 t.Logf("random seed: %d", seed)
746 }
747 }(t, seed)
748 for i := 0; i < 100; i++ {
749 // Generate a random scalar, decompose it, and ensure the resulting
750 // decomposition satisfies the required equation and consists of scalars
751 // that are small in magnitude.
752 origK := randModNScalar(t, rng)
753 k1, k2 := splitK(origK)
754 if err := checkLambdaDecomposition(origK, &k1, &k2); chk.T(err) {
755 t.Fatalf(
756 "decomposition err: %v\nin: %v\nk1: %v\nk2: %v", err,
757 origK, k1, k2,
758 )
759 }
760 }
761 }
762
763 // TestScalarMultJacobianRandom ensures scalar point multiplication with points
764 // projected into Jacobian coordinates works as intended for randomly-generated
765 // scalars and points.
766 func TestScalarMultJacobianRandom(t *testing.T) {
767 // Use a unique random seed each test instance and log it if the tests fail.
768 seed := time.Now().Unix()
769 rng := rand.New(rand.NewSource(seed))
770 defer func(t *testing.T, seed int64) {
771 if t.Failed() {
772 t.Logf("random seed: %d", seed)
773 }
774 }(t, seed)
775 // isSamePoint returns whether the two Jacobian points represent the
776 // same affine point without modifying the provided points.
777 isSamePoint := func(p1, p2 *JacobianPoint) bool {
778 var p1Affine, p2Affine JacobianPoint
779 p1Affine.Set(p1)
780 p1Affine.ToAffine()
781 p2Affine.Set(p2)
782 p2Affine.ToAffine()
783 return p1Affine.IsStrictlyEqual(&p2Affine)
784 }
785 // The overall idea is to compute the same point different ways. The
786 // strategy uses two properties:
787 //
788 // 1) Compatibility of scalar multiplication with field multiplication
789 // 2) A point added to its negation is the point at infinity (P+(-P) = ∞)
790 //
791 // First, calculate a "chained" point by starting with the base (generator)
792 // point and then consecutively multiply the resulting points by a series of
793 // random scalars.
794 //
795 // Then, multiply the base point by the product of all of the random scalars
796 // and ensure the "chained" point matches.
797 //
798 // In other words:
799 //
800 // k[n]*(...*(k[2]*(k[1]*(k[0]*G)))) = (k[0]*k[1]*k[2]*...*k[n])*G
801 //
802 // Along the way, also calculate (-k)*P for each chained point and ensure it
803 // sums with the current point to the point at infinity.
804 //
805 // That is:
806 //
807 // k*P + ((-k)*P) = ∞
808 const numIterations = 1024
809 var infinity JacobianPoint
810 var chained, negChained, result JacobianPoint
811 var negK ModNScalar
812 bigAffineToJacobian(curveParams.Gx, curveParams.Gy, &chained)
813 product := new(ModNScalar).SetInt(1)
814 for i := 0; i < numIterations; i++ {
815 // Generate a random scalar and calculate:
816 //
817 // P = k*P
818 // -P = (-k)*P
819 //
820 // Notice that this is intentionally doing the full scalar mult with -k
821 // as opposed to just flipping the Y coordinate in order to test scalar
822 // multiplication.
823 k := randModNScalar(t, rng)
824 negK.NegateVal(k)
825 ScalarMultNonConst(&negK, &chained, &negChained)
826 ScalarMultNonConst(k, &chained, &chained)
827
828 // Ensure kP + ((-k)P) = ∞.
829 AddNonConst(&chained, &negChained, &result)
830 if !isSamePoint(&result, &infinity) {
831 t.Fatalf(
832 "%d: expected point at infinity\ngot (%v, %v, %v)\n", i,
833 result.X, result.Y, result.Z,
834 )
835 }
836 product.Mul(k)
837 }
838 // Ensure the point calculated above matches the product of the scalars
839 // times the base point.
840 ScalarBaseMultNonConst(product, &result)
841 if !isSamePoint(&chained, &result) {
842 t.Fatalf(
843 "unexpected result \ngot (%v, %v, %v)\n"+
844 "want (%v, %v, %v)", chained.X, chained.Y, chained.Z, result.X,
845 result.Y, result.Z,
846 )
847 }
848 }
849
850 // TestDecompressY ensures that decompressY works as expected for some edge
851 // cases.
852 func TestDecompressY(t *testing.T) {
853 tests := []struct {
854 name string // test description
855 x string // hex encoded x coordinate
856 valid bool // expected decompress result
857 wantOddY string // hex encoded expected odd y coordinate
858 wantEvenY string // hex encoded expected even y coordinate
859 }{
860 {
861 name: "x = 0 -- not a point on the curve",
862 x: "0",
863 valid: false,
864 wantOddY: "",
865 wantEvenY: "",
866 }, {
867 name: "x = 1",
868 x: "1",
869 valid: true,
870 wantOddY: "bde70df51939b94c9c24979fa7dd04ebd9b3572da7802290438af2a681895441",
871 wantEvenY: "4218f20ae6c646b363db68605822fb14264ca8d2587fdd6fbc750d587e76a7ee",
872 }, {
873 name: "x = secp256k1 prime (aka 0) -- not a point on the curve",
874 x: "fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f",
875 valid: false,
876 wantOddY: "",
877 wantEvenY: "",
878 }, {
879 name: "x = secp256k1 prime - 1 -- not a point on the curve",
880 x: "fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2e",
881 valid: false,
882 wantOddY: "",
883 wantEvenY: "",
884 }, {
885 name: "x = secp256k1 group order",
886 x: "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141",
887 valid: true,
888 wantOddY: "670999be34f51e8894b9c14211c28801d9a70fde24b71d3753854b35d07c9a11",
889 wantEvenY: "98f66641cb0ae1776b463ebdee3d77fe2658f021db48e2c8ac7ab4c92f83621e",
890 }, {
891 name: "x = secp256k1 group order - 1 -- not a point on the curve",
892 x: "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140",
893 valid: false,
894 wantOddY: "",
895 wantEvenY: "",
896 },
897 }
898 for _, test := range tests {
899 // Decompress the test odd y coordinate for the given test x coordinate
900 // and ensure the returned validity flag matches the expected result.
901 var oddY FieldVal
902 fx := new(FieldVal).SetHex(test.x)
903 valid := DecompressY(fx, true, &oddY)
904 if valid != test.valid {
905 t.Errorf(
906 "%s: unexpected valid flag -- got: %v, want: %v",
907 test.name, valid, test.valid,
908 )
909 continue
910 }
911 // Decompress the test even y coordinate for the given test x coordinate
912 // and ensure the returned validity flag matches the expected result.
913 var evenY FieldVal
914 valid = DecompressY(fx, false, &evenY)
915 if valid != test.valid {
916 t.Errorf(
917 "%s: unexpected valid flag -- got: %v, want: %v",
918 test.name, valid, test.valid,
919 )
920 continue
921 }
922 // Skip checks related to the y coordinate when there isn't one.
923 if !valid {
924 continue
925 }
926 // Ensure the decompressed odd Y coordinate is the expected value.
927 oddY.Normalize()
928 wantOddY := new(FieldVal).SetHex(test.wantOddY)
929 if !wantOddY.Equals(&oddY) {
930 t.Errorf(
931 "%s: mismatched odd y\ngot: %v, want: %v", test.name,
932 oddY, wantOddY,
933 )
934 continue
935 }
936 // Ensure the decompressed even Y coordinate is the expected value.
937 evenY.Normalize()
938 wantEvenY := new(FieldVal).SetHex(test.wantEvenY)
939 if !wantEvenY.Equals(&evenY) {
940 t.Errorf(
941 "%s: mismatched even y\ngot: %v, want: %v", test.name,
942 evenY, wantEvenY,
943 )
944 continue
945 }
946 // Ensure the decompressed odd y coordinate is actually odd.
947 if !oddY.IsOdd() {
948 t.Errorf("%s: odd y coordinate is even", test.name)
949 continue
950 }
951 // Ensure the decompressed even y coordinate is actually even.
952 if evenY.IsOdd() {
953 t.Errorf("%s: even y coordinate is odd", test.name)
954 continue
955 }
956 }
957 }
958
959 // TestDecompressYRandom ensures that decompressY works as expected with
960 // randomly-generated x coordinates.
961 func TestDecompressYRandom(t *testing.T) {
962 // Use a unique random seed each test instance and log it if the tests fail.
963 seed := time.Now().Unix()
964 rng := rand.New(rand.NewSource(seed))
965 defer func(t *testing.T, seed int64) {
966 if t.Failed() {
967 t.Logf("random seed: %d", seed)
968 }
969 }(t, seed)
970 for i := 0; i < 100; i++ {
971 origX := randFieldVal(t, rng)
972 // Calculate both corresponding y coordinates for the random x when it
973 // is a valid coordinate.
974 var oddY, evenY FieldVal
975 x := new(FieldVal).Set(origX)
976 oddSuccess := DecompressY(x, true, &oddY)
977 evenSuccess := DecompressY(x, false, &evenY)
978 // Ensure that the decompression success matches for both the even and
979 // odd cases depending on whether or not x is a valid coordinate.
980 if oddSuccess != evenSuccess {
981 t.Fatalf(
982 "mismatched decompress success for x = %v -- odd: %v, "+
983 "even: %v", x, oddSuccess, evenSuccess,
984 )
985 }
986 if !oddSuccess {
987 continue
988 }
989 // Ensure the x coordinate was not changed.
990 if !x.Equals(origX) {
991 t.Fatalf("x coordinate changed -- orig: %v, changed: %v", origX, x)
992 }
993 // Ensure that the resulting y coordinates match their respective
994 // expected oddness.
995 oddY.Normalize()
996 evenY.Normalize()
997 if !oddY.IsOdd() {
998 t.Fatalf("requested odd y is even for x = %v", x)
999 }
1000 if evenY.IsOdd() {
1001 t.Fatalf("requested even y is odd for x = %v", x)
1002 }
1003 // Ensure that the resulting x and y coordinates are actually on the
1004 // curve for both cases.
1005 if !isOnCurve(x, &oddY) {
1006 t.Fatalf("(%v, %v) is not a valid point", x, oddY)
1007 }
1008 if !isOnCurve(x, &evenY) {
1009 t.Fatalf("(%v, %v) is not a valid point", x, evenY)
1010 }
1011 }
1012 }
1013