btcec_test.go raw
1 // Copyright 2011 The Go Authors. All rights reserved.
2 // Copyright 2011 ThePiachu. All rights reserved.
3 // Copyright 2013-2016 The btcsuite developers
4 // Use of this source code is governed by an ISC
5 // license that can be found in the LICENSE file.
6
7 package btcec
8
9 import (
10 "crypto/rand"
11 "fmt"
12 "math/big"
13 "testing"
14 )
15
16 // isJacobianOnS256Curve returns boolean if the point (x,y,z) is on the
17 // secp256k1 curve.
18 func isJacobianOnS256Curve(point *JacobianPoint) bool {
19 // Elliptic curve equation for secp256k1 is: y^2 = x^3 + 7
20 // In Jacobian coordinates, Y = y/z^3 and X = x/z^2
21 // Thus:
22 // (y/z^3)^2 = (x/z^2)^3 + 7
23 // y^2/z^6 = x^3/z^6 + 7
24 // y^2 = x^3 + 7*z^6
25 var y2, z2, x3, result FieldVal
26 y2.SquareVal(&point.Y).Normalize()
27 z2.SquareVal(&point.Z)
28 x3.SquareVal(&point.X).Mul(&point.X)
29 result.SquareVal(&z2).Mul(&z2).MulInt(7).Add(&x3).Normalize()
30 return y2.Equals(&result)
31 }
32
33 // TestAddJacobian tests addition of points projected in Jacobian coordinates.
34 func TestAddJacobian(t *testing.T) {
35 tests := []struct {
36 x1, y1, z1 string // Coordinates (in hex) of first point to add
37 x2, y2, z2 string // Coordinates (in hex) of second point to add
38 x3, y3, z3 string // Coordinates (in hex) of expected point
39 }{
40 // Addition with a point at infinity (left hand side).
41 // ∞ + P = P
42 {
43 "0",
44 "0",
45 "0",
46 "d74bf844b0862475103d96a611cf2d898447e288d34b360bc885cb8ce7c00575",
47 "131c670d414c4546b88ac3ff664611b1c38ceb1c21d76369d7a7a0969d61d97d",
48 "1",
49 "d74bf844b0862475103d96a611cf2d898447e288d34b360bc885cb8ce7c00575",
50 "131c670d414c4546b88ac3ff664611b1c38ceb1c21d76369d7a7a0969d61d97d",
51 "1",
52 },
53 // Addition with a point at infinity (right hand side).
54 // P + ∞ = P
55 {
56 "d74bf844b0862475103d96a611cf2d898447e288d34b360bc885cb8ce7c00575",
57 "131c670d414c4546b88ac3ff664611b1c38ceb1c21d76369d7a7a0969d61d97d",
58 "1",
59 "0",
60 "0",
61 "0",
62 "d74bf844b0862475103d96a611cf2d898447e288d34b360bc885cb8ce7c00575",
63 "131c670d414c4546b88ac3ff664611b1c38ceb1c21d76369d7a7a0969d61d97d",
64 "1",
65 },
66 // Addition with z1=z2=1 different x values.
67 {
68 "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
69 "0b71ea9bd730fd8923f6d25a7a91e7dd7728a960686cb5a901bb419e0f2ca232",
70 "1",
71 "d74bf844b0862475103d96a611cf2d898447e288d34b360bc885cb8ce7c00575",
72 "131c670d414c4546b88ac3ff664611b1c38ceb1c21d76369d7a7a0969d61d97d",
73 "1",
74 "0cfbc7da1e569b334460788faae0286e68b3af7379d5504efc25e4dba16e46a6",
75 "e205f79361bbe0346b037b4010985dbf4f9e1e955e7d0d14aca876bfa79aad87",
76 "44a5646b446e3877a648d6d381370d9ef55a83b666ebce9df1b1d7d65b817b2f",
77 },
78 // Addition with z1=z2=1 same x opposite y.
79 // P(x, y, z) + P(x, -y, z) = infinity
80 {
81 "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
82 "0b71ea9bd730fd8923f6d25a7a91e7dd7728a960686cb5a901bb419e0f2ca232",
83 "1",
84 "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
85 "f48e156428cf0276dc092da5856e182288d7569f97934a56fe44be60f0d359fd",
86 "1",
87 "0",
88 "0",
89 "0",
90 },
91 // Addition with z1=z2=1 same point.
92 // P(x, y, z) + P(x, y, z) = 2P
93 {
94 "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
95 "0b71ea9bd730fd8923f6d25a7a91e7dd7728a960686cb5a901bb419e0f2ca232",
96 "1",
97 "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
98 "0b71ea9bd730fd8923f6d25a7a91e7dd7728a960686cb5a901bb419e0f2ca232",
99 "1",
100 "ec9f153b13ee7bd915882859635ea9730bf0dc7611b2c7b0e37ee64f87c50c27",
101 "b082b53702c466dcf6e984a35671756c506c67c2fcb8adb408c44dd0755c8f2a",
102 "16e3d537ae61fb1247eda4b4f523cfbaee5152c0d0d96b520376833c1e594464",
103 },
104
105 // Addition with z1=z2 (!=1) different x values.
106 {
107 "d3e5183c393c20e4f464acf144ce9ae8266a82b67f553af33eb37e88e7fd2718",
108 "5b8f54deb987ec491fb692d3d48f3eebb9454b034365ad480dda0cf079651190",
109 "2",
110 "5d2fe112c21891d440f65a98473cb626111f8a234d2cd82f22172e369f002147",
111 "98e3386a0a622a35c4561ffb32308d8e1c6758e10ebb1b4ebd3d04b4eb0ecbe8",
112 "2",
113 "cfbc7da1e569b334460788faae0286e68b3af7379d5504efc25e4dba16e46a60",
114 "817de4d86ef80d1ac0ded00426176fd3e787a5579f43452b2a1db021e6ac3778",
115 "129591ad11b8e1de99235b4e04dc367bd56a0ed99baf3a77c6c75f5a6e05f08d",
116 },
117 // Addition with z1=z2 (!=1) same x opposite y.
118 // P(x, y, z) + P(x, -y, z) = infinity
119 {
120 "d3e5183c393c20e4f464acf144ce9ae8266a82b67f553af33eb37e88e7fd2718",
121 "5b8f54deb987ec491fb692d3d48f3eebb9454b034365ad480dda0cf079651190",
122 "2",
123 "d3e5183c393c20e4f464acf144ce9ae8266a82b67f553af33eb37e88e7fd2718",
124 "a470ab21467813b6e0496d2c2b70c11446bab4fcbc9a52b7f225f30e869aea9f",
125 "2",
126 "0",
127 "0",
128 "0",
129 },
130 // Addition with z1=z2 (!=1) same point.
131 // P(x, y, z) + P(x, y, z) = 2P
132 {
133 "d3e5183c393c20e4f464acf144ce9ae8266a82b67f553af33eb37e88e7fd2718",
134 "5b8f54deb987ec491fb692d3d48f3eebb9454b034365ad480dda0cf079651190",
135 "2",
136 "d3e5183c393c20e4f464acf144ce9ae8266a82b67f553af33eb37e88e7fd2718",
137 "5b8f54deb987ec491fb692d3d48f3eebb9454b034365ad480dda0cf079651190",
138 "2",
139 "9f153b13ee7bd915882859635ea9730bf0dc7611b2c7b0e37ee65073c50fabac",
140 "2b53702c466dcf6e984a35671756c506c67c2fcb8adb408c44dd125dc91cb988",
141 "6e3d537ae61fb1247eda4b4f523cfbaee5152c0d0d96b520376833c2e5944a11",
142 },
143
144 // Addition with z1!=z2 and z2=1 different x values.
145 {
146 "d3e5183c393c20e4f464acf144ce9ae8266a82b67f553af33eb37e88e7fd2718",
147 "5b8f54deb987ec491fb692d3d48f3eebb9454b034365ad480dda0cf079651190",
148 "2",
149 "d74bf844b0862475103d96a611cf2d898447e288d34b360bc885cb8ce7c00575",
150 "131c670d414c4546b88ac3ff664611b1c38ceb1c21d76369d7a7a0969d61d97d",
151 "1",
152 "3ef1f68795a6ccd1181e23eab80a1b9a2cebdcde755413bf097936eb5b91b4f3",
153 "0bef26c377c068d606f6802130bb7e9f3c3d2abcfa1a295950ed81133561cb04",
154 "252b235a2371c3bd3246b69c09b86cf7aad41db3375e74ef8d8ebeb4dc0be11a",
155 },
156 // Addition with z1!=z2 and z2=1 same x opposite y.
157 // P(x, y, z) + P(x, -y, z) = infinity
158 {
159 "d3e5183c393c20e4f464acf144ce9ae8266a82b67f553af33eb37e88e7fd2718",
160 "5b8f54deb987ec491fb692d3d48f3eebb9454b034365ad480dda0cf079651190",
161 "2",
162 "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
163 "f48e156428cf0276dc092da5856e182288d7569f97934a56fe44be60f0d359fd",
164 "1",
165 "0",
166 "0",
167 "0",
168 },
169 // Addition with z1!=z2 and z2=1 same point.
170 // P(x, y, z) + P(x, y, z) = 2P
171 {
172 "d3e5183c393c20e4f464acf144ce9ae8266a82b67f553af33eb37e88e7fd2718",
173 "5b8f54deb987ec491fb692d3d48f3eebb9454b034365ad480dda0cf079651190",
174 "2",
175 "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
176 "0b71ea9bd730fd8923f6d25a7a91e7dd7728a960686cb5a901bb419e0f2ca232",
177 "1",
178 "9f153b13ee7bd915882859635ea9730bf0dc7611b2c7b0e37ee65073c50fabac",
179 "2b53702c466dcf6e984a35671756c506c67c2fcb8adb408c44dd125dc91cb988",
180 "6e3d537ae61fb1247eda4b4f523cfbaee5152c0d0d96b520376833c2e5944a11",
181 },
182
183 // Addition with z1!=z2 and z2!=1 different x values.
184 // P(x, y, z) + P(x, y, z) = 2P
185 {
186 "d3e5183c393c20e4f464acf144ce9ae8266a82b67f553af33eb37e88e7fd2718",
187 "5b8f54deb987ec491fb692d3d48f3eebb9454b034365ad480dda0cf079651190",
188 "2",
189 "91abba6a34b7481d922a4bd6a04899d5a686f6cf6da4e66a0cb427fb25c04bd4",
190 "03fede65e30b4e7576a2abefc963ddbf9fdccbf791b77c29beadefe49951f7d1",
191 "3",
192 "3f07081927fd3f6dadd4476614c89a09eba7f57c1c6c3b01fa2d64eac1eef31e",
193 "949166e04ebc7fd95a9d77e5dfd88d1492ecffd189792e3944eb2b765e09e031",
194 "eb8cba81bcffa4f44d75427506737e1f045f21e6d6f65543ee0e1d163540c931",
195 }, // Addition with z1!=z2 and z2!=1 same x opposite y.
196 // P(x, y, z) + P(x, -y, z) = infinity
197 {
198 "d3e5183c393c20e4f464acf144ce9ae8266a82b67f553af33eb37e88e7fd2718",
199 "5b8f54deb987ec491fb692d3d48f3eebb9454b034365ad480dda0cf079651190",
200 "2",
201 "dcc3768780c74a0325e2851edad0dc8a566fa61a9e7fc4a34d13dcb509f99bc7",
202 "cafc41904dd5428934f7d075129c8ba46eb622d4fc88d72cd1401452664add18",
203 "3",
204 "0",
205 "0",
206 "0",
207 },
208 // Addition with z1!=z2 and z2!=1 same point.
209 // P(x, y, z) + P(x, y, z) = 2P
210 {
211 "d3e5183c393c20e4f464acf144ce9ae8266a82b67f553af33eb37e88e7fd2718",
212 "5b8f54deb987ec491fb692d3d48f3eebb9454b034365ad480dda0cf079651190",
213 "2",
214 "dcc3768780c74a0325e2851edad0dc8a566fa61a9e7fc4a34d13dcb509f99bc7",
215 "3503be6fb22abd76cb082f8aed63745b9149dd2b037728d32ebfebac99b51f17",
216 "3",
217 "9f153b13ee7bd915882859635ea9730bf0dc7611b2c7b0e37ee65073c50fabac",
218 "2b53702c466dcf6e984a35671756c506c67c2fcb8adb408c44dd125dc91cb988",
219 "6e3d537ae61fb1247eda4b4f523cfbaee5152c0d0d96b520376833c2e5944a11",
220 },
221 }
222
223 t.Logf("Running %d tests", len(tests))
224 for i, test := range tests {
225 // Convert hex to Jacobian points.
226 p1 := jacobianPointFromHex(test.x1, test.y1, test.z1)
227 p2 := jacobianPointFromHex(test.x2, test.y2, test.z2)
228 want := jacobianPointFromHex(test.x3, test.y3, test.z3)
229 // Ensure the test data is using points that are actually on
230 // the curve (or the point at infinity).
231 if !p1.Z.IsZero() && !isJacobianOnS256Curve(&p1) {
232 t.Errorf(
233 "#%d first point is not on the curve -- "+
234 "invalid test data", i,
235 )
236 continue
237 }
238 if !p2.Z.IsZero() && !isJacobianOnS256Curve(&p2) {
239 t.Errorf(
240 "#%d second point is not on the curve -- "+
241 "invalid test data", i,
242 )
243 continue
244 }
245 if !want.Z.IsZero() && !isJacobianOnS256Curve(&want) {
246 t.Errorf(
247 "#%d expected point is not on the curve -- "+
248 "invalid test data", i,
249 )
250 continue
251 }
252 // Add the two points.
253 var r JacobianPoint
254 AddNonConst(&p1, &p2, &r)
255
256 // Ensure result matches expected.
257 if !r.X.Equals(&want.X) || !r.Y.Equals(&want.Y) || !r.Z.Equals(&want.Z) {
258 t.Errorf(
259 "#%d wrong result\ngot: (%v, %v, %v)\n"+
260 "want: (%v, %v, %v)", i, r.X, r.Y, r.Z, want.X, want.Y,
261 want.Z,
262 )
263 continue
264 }
265 }
266 }
267
268 // TestAddAffine tests addition of points in affine coordinates.
269 func TestAddAffine(t *testing.T) {
270 tests := []struct {
271 x1, y1 string // Coordinates (in hex) of first point to add
272 x2, y2 string // Coordinates (in hex) of second point to add
273 x3, y3 string // Coordinates (in hex) of expected point
274 }{
275 // Addition with a point at infinity (left hand side).
276 // ∞ + P = P
277 {
278 "0",
279 "0",
280 "d74bf844b0862475103d96a611cf2d898447e288d34b360bc885cb8ce7c00575",
281 "131c670d414c4546b88ac3ff664611b1c38ceb1c21d76369d7a7a0969d61d97d",
282 "d74bf844b0862475103d96a611cf2d898447e288d34b360bc885cb8ce7c00575",
283 "131c670d414c4546b88ac3ff664611b1c38ceb1c21d76369d7a7a0969d61d97d",
284 },
285 // Addition with a point at infinity (right hand side).
286 // P + ∞ = P
287 {
288 "d74bf844b0862475103d96a611cf2d898447e288d34b360bc885cb8ce7c00575",
289 "131c670d414c4546b88ac3ff664611b1c38ceb1c21d76369d7a7a0969d61d97d",
290 "0",
291 "0",
292 "d74bf844b0862475103d96a611cf2d898447e288d34b360bc885cb8ce7c00575",
293 "131c670d414c4546b88ac3ff664611b1c38ceb1c21d76369d7a7a0969d61d97d",
294 },
295
296 // Addition with different x values.
297 {
298 "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
299 "0b71ea9bd730fd8923f6d25a7a91e7dd7728a960686cb5a901bb419e0f2ca232",
300 "d74bf844b0862475103d96a611cf2d898447e288d34b360bc885cb8ce7c00575",
301 "131c670d414c4546b88ac3ff664611b1c38ceb1c21d76369d7a7a0969d61d97d",
302 "fd5b88c21d3143518d522cd2796f3d726793c88b3e05636bc829448e053fed69",
303 "21cf4f6a5be5ff6380234c50424a970b1f7e718f5eb58f68198c108d642a137f",
304 },
305 // Addition with same x opposite y.
306 // P(x, y) + P(x, -y) = infinity
307 {
308 "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
309 "0b71ea9bd730fd8923f6d25a7a91e7dd7728a960686cb5a901bb419e0f2ca232",
310 "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
311 "f48e156428cf0276dc092da5856e182288d7569f97934a56fe44be60f0d359fd",
312 "0",
313 "0",
314 },
315 // Addition with same point.
316 // P(x, y) + P(x, y) = 2P
317 {
318 "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
319 "0b71ea9bd730fd8923f6d25a7a91e7dd7728a960686cb5a901bb419e0f2ca232",
320 "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
321 "0b71ea9bd730fd8923f6d25a7a91e7dd7728a960686cb5a901bb419e0f2ca232",
322 "59477d88ae64a104dbb8d31ec4ce2d91b2fe50fa628fb6a064e22582196b365b",
323 "938dc8c0f13d1e75c987cb1a220501bd614b0d3dd9eb5c639847e1240216e3b6",
324 },
325 }
326 t.Logf("Running %d tests", len(tests))
327 for i, test := range tests {
328 // Convert hex to field values.
329 x1, y1 := fromHex(test.x1), fromHex(test.y1)
330 x2, y2 := fromHex(test.x2), fromHex(test.y2)
331 x3, y3 := fromHex(test.x3), fromHex(test.y3)
332 // Ensure the test data is using points that are actually on
333 // the curve (or the point at infinity).
334 if !(x1.Sign() == 0 && y1.Sign() == 0) && !S256().IsOnCurve(x1, y1) {
335 t.Errorf(
336 "#%d first point is not on the curve -- "+
337 "invalid test data", i,
338 )
339 continue
340 }
341 if !(x2.Sign() == 0 && y2.Sign() == 0) && !S256().IsOnCurve(x2, y2) {
342 t.Errorf(
343 "#%d second point is not on the curve -- "+
344 "invalid test data", i,
345 )
346 continue
347 }
348 if !(x3.Sign() == 0 && y3.Sign() == 0) && !S256().IsOnCurve(x3, y3) {
349 t.Errorf(
350 "#%d expected point is not on the curve -- "+
351 "invalid test data", i,
352 )
353 continue
354 }
355 // Add the two points.
356 rx, ry := S256().Add(x1, y1, x2, y2)
357
358 // Ensure result matches expected.
359 if rx.Cmp(x3) != 00 || ry.Cmp(y3) != 0 {
360 t.Errorf(
361 "#%d wrong result\ngot: (%x, %x)\n"+
362 "want: (%x, %x)", i, rx, ry, x3, y3,
363 )
364 continue
365 }
366 }
367 }
368
369 // isStrictlyEqual returns whether or not the two Jacobian points are strictly
370 // equal for use in the tests. Recall that several Jacobian points can be
371 // equal in affine coordinates, while not having the same coordinates in
372 // projective space, so the two points not being equal doesn't necessarily mean
373 // they aren't actually the same affine point.
374 func isStrictlyEqual(p, other *JacobianPoint) bool {
375 return p.X.Equals(&other.X) && p.Y.Equals(&other.Y) && p.Z.Equals(&other.Z)
376 }
377
378 // TestDoubleJacobian tests doubling of points projected in Jacobian
379 // coordinates.
380 func TestDoubleJacobian(t *testing.T) {
381 tests := []struct {
382 x1, y1, z1 string // Coordinates (in hex) of point to double
383 x3, y3, z3 string // Coordinates (in hex) of expected point
384 }{
385 // Doubling a point at infinity is still infinity.
386 {
387 "0",
388 "0",
389 "0",
390 "0",
391 "0",
392 "0",
393 },
394 // Doubling with z1=1.
395 {
396 "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
397 "0b71ea9bd730fd8923f6d25a7a91e7dd7728a960686cb5a901bb419e0f2ca232",
398 "1",
399 "ec9f153b13ee7bd915882859635ea9730bf0dc7611b2c7b0e37ee64f87c50c27",
400 "b082b53702c466dcf6e984a35671756c506c67c2fcb8adb408c44dd0755c8f2a",
401 "16e3d537ae61fb1247eda4b4f523cfbaee5152c0d0d96b520376833c1e594464",
402 },
403 // Doubling with z1!=1.
404 {
405 "d3e5183c393c20e4f464acf144ce9ae8266a82b67f553af33eb37e88e7fd2718",
406 "5b8f54deb987ec491fb692d3d48f3eebb9454b034365ad480dda0cf079651190",
407 "2",
408 "9f153b13ee7bd915882859635ea9730bf0dc7611b2c7b0e37ee65073c50fabac",
409 "2b53702c466dcf6e984a35671756c506c67c2fcb8adb408c44dd125dc91cb988",
410 "6e3d537ae61fb1247eda4b4f523cfbaee5152c0d0d96b520376833c2e5944a11",
411 },
412 // From btcd issue #709.
413 {
414 "201e3f75715136d2f93c4f4598f91826f94ca01f4233a5bd35de9708859ca50d",
415 "bdf18566445e7562c6ada68aef02d498d7301503de5b18c6aef6e2b1722412e1",
416 "0000000000000000000000000000000000000000000000000000000000000001",
417 "4a5e0559863ebb4e9ed85f5c4fa76003d05d9a7626616e614a1f738621e3c220",
418 "00000000000000000000000000000000000000000000000000000001b1388778",
419 "7be30acc88bceac58d5b4d15de05a931ae602a07bcb6318d5dedc563e4482993",
420 },
421 }
422 t.Logf("Running %d tests", len(tests))
423 for i, test := range tests {
424 // Convert hex to field values.
425 p1 := jacobianPointFromHex(test.x1, test.y1, test.z1)
426 want := jacobianPointFromHex(test.x3, test.y3, test.z3)
427 // Ensure the test data is using points that are actually on
428 // the curve (or the point at infinity).
429 if !p1.Z.IsZero() && !isJacobianOnS256Curve(&p1) {
430 t.Errorf(
431 "#%d first point is not on the curve -- "+
432 "invalid test data", i,
433 )
434 continue
435 }
436 if !want.Z.IsZero() && !isJacobianOnS256Curve(&want) {
437 t.Errorf(
438 "#%d expected point is not on the curve -- "+
439 "invalid test data", i,
440 )
441 continue
442 }
443 // Double the point.
444 var result JacobianPoint
445 DoubleNonConst(&p1, &result)
446 // Ensure result matches expected.
447 if !isStrictlyEqual(&result, &want) {
448 t.Errorf(
449 "#%d wrong result\ngot: (%v, %v, %v)\n"+
450 "want: (%v, %v, %v)", i, result.X, result.Y, result.Z,
451 want.X, want.Y, want.Z,
452 )
453 continue
454 }
455 }
456 }
457
458 // TestDoubleAffine tests doubling of points in affine coordinates.
459 func TestDoubleAffine(t *testing.T) {
460 tests := []struct {
461 x1, y1 string // Coordinates (in hex) of point to double
462 x3, y3 string // Coordinates (in hex) of expected point
463 }{
464 // Doubling a point at infinity is still infinity.
465 // 2*∞ = ∞ (point at infinity)
466 {
467 "0",
468 "0",
469 "0",
470 "0",
471 },
472 // Random points.
473 {
474 "e41387ffd8baaeeb43c2faa44e141b19790e8ac1f7ff43d480dc132230536f86",
475 "1b88191d430f559896149c86cbcb703193105e3cf3213c0c3556399836a2b899",
476 "88da47a089d333371bd798c548ef7caae76e737c1980b452d367b3cfe3082c19",
477 "3b6f659b09a362821dfcfefdbfbc2e59b935ba081b6c249eb147b3c2100b1bc1",
478 },
479 {
480 "b3589b5d984f03ef7c80aeae444f919374799edf18d375cab10489a3009cff0c",
481 "c26cf343875b3630e15bccc61202815b5d8f1fd11308934a584a5babe69db36a",
482 "e193860172998751e527bb12563855602a227fc1f612523394da53b746bb2fb1",
483 "2bfcf13d2f5ab8bb5c611fab5ebbed3dc2f057062b39a335224c22f090c04789",
484 },
485 {
486 "2b31a40fbebe3440d43ac28dba23eee71c62762c3fe3dbd88b4ab82dc6a82340",
487 "9ba7deb02f5c010e217607fd49d58db78ec273371ea828b49891ce2fd74959a1",
488 "2c8d5ef0d343b1a1a48aa336078eadda8481cb048d9305dc4fdf7ee5f65973a2",
489 "bb4914ac729e26d3cd8f8dc8f702f3f4bb7e0e9c5ae43335f6e94c2de6c3dc95",
490 },
491 {
492 "61c64b760b51981fab54716d5078ab7dffc93730b1d1823477e27c51f6904c7a",
493 "ef6eb16ea1a36af69d7f66524c75a3a5e84c13be8fbc2e811e0563c5405e49bd",
494 "5f0dcdd2595f5ad83318a0f9da481039e36f135005420393e72dfca985b482f4",
495 "a01c849b0837065c1cb481b0932c441f49d1cab1b4b9f355c35173d93f110ae0",
496 },
497 }
498
499 t.Logf("Running %d tests", len(tests))
500 for i, test := range tests {
501 // Convert hex to field values.
502 x1, y1 := fromHex(test.x1), fromHex(test.y1)
503 x3, y3 := fromHex(test.x3), fromHex(test.y3)
504 // Ensure the test data is using points that are actually on
505 // the curve (or the point at infinity).
506 if !(x1.Sign() == 0 && y1.Sign() == 0) && !S256().IsOnCurve(x1, y1) {
507 t.Errorf(
508 "#%d first point is not on the curve -- "+
509 "invalid test data", i,
510 )
511 continue
512 }
513 if !(x3.Sign() == 0 && y3.Sign() == 0) && !S256().IsOnCurve(x3, y3) {
514 t.Errorf(
515 "#%d expected point is not on the curve -- "+
516 "invalid test data", i,
517 )
518 continue
519 }
520 // Double the point.
521 rx, ry := S256().Double(x1, y1)
522
523 // Ensure result matches expected.
524 if rx.Cmp(x3) != 00 || ry.Cmp(y3) != 0 {
525 t.Errorf(
526 "#%d wrong result\ngot: (%x, %x)\n"+
527 "want: (%x, %x)", i, rx, ry, x3, y3,
528 )
529 continue
530 }
531 }
532 }
533
534 func TestOnCurve(t *testing.T) {
535 s256 := S256()
536 if !s256.IsOnCurve(s256.Params().Gx, s256.Params().Gy) {
537 t.Errorf("FAIL S256")
538 }
539 }
540
541 type baseMultTest struct {
542 k string
543 x, y string
544 }
545
546 // TODO: add more test vectors
547 var s256BaseMultTests = []baseMultTest{
548 {
549 "AA5E28D6A97A2479A65527F7290311A3624D4CC0FA1578598EE3C2613BF99522",
550 "34F9460F0E4F08393D192B3C5133A6BA099AA0AD9FD54EBCCFACDFA239FF49C6",
551 "B71EA9BD730FD8923F6D25A7A91E7DD7728A960686CB5A901BB419E0F2CA232",
552 },
553 {
554 "7E2B897B8CEBC6361663AD410835639826D590F393D90A9538881735256DFAE3",
555 "D74BF844B0862475103D96A611CF2D898447E288D34B360BC885CB8CE7C00575",
556 "131C670D414C4546B88AC3FF664611B1C38CEB1C21D76369D7A7A0969D61D97D",
557 },
558 {
559 "6461E6DF0FE7DFD05329F41BF771B86578143D4DD1F7866FB4CA7E97C5FA945D",
560 "E8AECC370AEDD953483719A116711963CE201AC3EB21D3F3257BB48668C6A72F",
561 "C25CAF2F0EBA1DDB2F0F3F47866299EF907867B7D27E95B3873BF98397B24EE1",
562 },
563 {
564 "376A3A2CDCD12581EFFF13EE4AD44C4044B8A0524C42422A7E1E181E4DEECCEC",
565 "14890E61FCD4B0BD92E5B36C81372CA6FED471EF3AA60A3E415EE4FE987DABA1",
566 "297B858D9F752AB42D3BCA67EE0EB6DCD1C2B7B0DBE23397E66ADC272263F982",
567 },
568 {
569 "1B22644A7BE026548810C378D0B2994EEFA6D2B9881803CB02CEFF865287D1B9",
570 "F73C65EAD01C5126F28F442D087689BFA08E12763E0CEC1D35B01751FD735ED3",
571 "F449A8376906482A84ED01479BD18882B919C140D638307F0C0934BA12590BDE",
572 },
573 }
574
575 // TODO: test different curves as well?
576 func TestBaseMult(t *testing.T) {
577 s256 := S256()
578 for i, e := range s256BaseMultTests {
579 k, ok := new(big.Int).SetString(e.k, 16)
580 if !ok {
581 t.Errorf("%d: bad value for k: %s", i, e.k)
582 }
583 x, y := s256.ScalarBaseMult(k.Bytes())
584 if fmt.Sprintf("%X", x) != e.x || fmt.Sprintf("%X", y) != e.y {
585 t.Errorf(
586 "%d: bad output for k=%s: got (%X, %X), want (%s, %s)", i,
587 e.k, x, y, e.x, e.y,
588 )
589 }
590 if testing.Short() && i > 5 {
591 break
592 }
593 }
594 }
595
596 func TestBaseMultVerify(t *testing.T) {
597 s256 := S256()
598 for bytes := 1; bytes < 40; bytes++ {
599 for i := 0; i < 30; i++ {
600 data := make([]byte, bytes)
601 _, err := rand.Read(data)
602 if err != nil {
603 t.Errorf("failed to read random data for %d", i)
604 continue
605 }
606 x, y := s256.ScalarBaseMult(data)
607 xWant, yWant := s256.ScalarMult(s256.Gx, s256.Gy, data)
608 if x.Cmp(xWant) != 0 || y.Cmp(yWant) != 0 {
609 t.Errorf(
610 "%d: bad output for %X: got (%X, %X), want (%X, %X)",
611 i, data, x, y, xWant, yWant,
612 )
613 }
614 if testing.Short() && i > 2 {
615 break
616 }
617 }
618 }
619 }
620
621 func TestScalarMult(t *testing.T) {
622 tests := []struct {
623 x string
624 y string
625 k string
626 rx string
627 ry string
628 }{
629 // base mult, essentially.
630 {
631 "79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798",
632 "483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8",
633 "18e14a7b6a307f426a94f8114701e7c8e774e7f9a47e2c2035db29a206321725",
634 "50863ad64a87ae8a2fe83c1af1a8403cb53f53e486d8511dad8a04887e5b2352",
635 "2cd470243453a299fa9e77237716103abc11a1df38855ed6f2ee187e9c582ba6",
636 },
637 // From btcd issue #709.
638 {
639 "000000000000000000000000000000000000000000000000000000000000002c",
640 "420e7a99bba18a9d3952597510fd2b6728cfeafc21a4e73951091d4d8ddbe94e",
641 "a2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba219b51835b55cc30ebfe2f6599bc56f58",
642 "a2112dcdfbcd10ae1133a358de7b82db68e0a3eb4b492cc8268d1e7118c98788",
643 "27fc7463b7bb3c5f98ecf2c84a6272bb1681ed553d92c69f2dfe25a9f9fd3836",
644 },
645 }
646 s256 := S256()
647 for i, test := range tests {
648 x, _ := new(big.Int).SetString(test.x, 16)
649 y, _ := new(big.Int).SetString(test.y, 16)
650 k, _ := new(big.Int).SetString(test.k, 16)
651 xWant, _ := new(big.Int).SetString(test.rx, 16)
652 yWant, _ := new(big.Int).SetString(test.ry, 16)
653 xGot, yGot := s256.ScalarMult(x, y, k.Bytes())
654 if xGot.Cmp(xWant) != 0 || yGot.Cmp(yWant) != 0 {
655 t.Fatalf(
656 "%d: bad output: got (%X, %X), want (%X, %X)", i, xGot,
657 yGot, xWant, yWant,
658 )
659 }
660 }
661 }
662
663 func TestScalarMultRand(t *testing.T) {
664 // Strategy for this test:
665 // Get a random exponent from the generator point at first
666 // This creates a new point which is used in the next iteration
667 // Use another random exponent on the new point.
668 // We use BaseMult to verify by multiplying the previous exponent
669 // and the new random exponent together (mod no)
670 s256 := S256()
671 x, y := s256.Gx, s256.Gy
672 exponent := big.NewInt(1)
673 for i := 0; i < 1024; i++ {
674 data := make([]byte, 32)
675 _, err := rand.Read(data)
676 if err != nil {
677 t.Fatalf("failed to read random data at %d", i)
678 break
679 }
680 x, y = s256.ScalarMult(x, y, data)
681 exponent.Mul(exponent, new(big.Int).SetBytes(data))
682 xWant, yWant := s256.ScalarBaseMult(exponent.Bytes())
683 if x.Cmp(xWant) != 0 || y.Cmp(yWant) != 0 {
684 t.Fatalf(
685 "%d: bad output for %X: got (%X, %X), want (%X, %X)", i,
686 data, x, y, xWant, yWant,
687 )
688 break
689 }
690 }
691 }
692
693 var (
694 // Next 6 constants are from Hal Finney's bitcointalk.org post:
695 // https://bitcointalk.org/index.php?topic=3238.msg45565#msg45565
696 // May he rest in peace.
697 //
698 // They have also been independently derived from the code in the
699 // EndomorphismVectors function in genstatics.go.
700 endomorphismLambda = fromHex("5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72")
701 endomorphismBeta = hexToFieldVal("7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee")
702 endomorphismA1 = fromHex("3086d221a7d46bcde86c90e49284eb15")
703 endomorphismB1 = fromHex("-e4437ed6010e88286f547fa90abfe4c3")
704 endomorphismA2 = fromHex("114ca50f7a8e2f3f657c1108d9d44cfd8")
705 endomorphismB2 = fromHex("3086d221a7d46bcde86c90e49284eb15")
706 )
707
708 // splitK returns a balanced length-two representation of k and their signs.
709 // This is algorithm 3.74 from [GECC].
710 //
711 // One thing of note about this algorithm is that no matter what c1 and c2 are,
712 // the final equation of k = k1 + k2 * lambda (mod n) will hold. This is
713 // provable mathematically due to how a1/b1/a2/b2 are computed.
714 //
715 // c1 and c2 are chosen to minimize the max(k1,k2).
716 func splitK(k []byte) ([]byte, []byte, int, int) {
717 // All math here is done with big.Int, which is slow.
718 // At some point, it might be useful to write something similar to
719 // FieldVal but for no instead of P as the prime field if this ends up
720 // being a bottleneck.
721 bigIntK := new(big.Int)
722 c1, c2 := new(big.Int), new(big.Int)
723 tmp1, tmp2 := new(big.Int), new(big.Int)
724 k1, k2 := new(big.Int), new(big.Int)
725 bigIntK.SetBytes(k)
726 // c1 = round(b2 * k / n) from step 4.
727 // Rounding isn't really necessary and costs too much, hence skipped
728 c1.Mul(endomorphismB2, bigIntK)
729 c1.Div(c1, Params().N)
730 // c2 = round(b1 * k / n) from step 4 (sign reversed to optimize one step)
731 // Rounding isn't really necessary and costs too much, hence skipped
732 c2.Mul(endomorphismB1, bigIntK)
733 c2.Div(c2, Params().N)
734 // k1 = k - c1 * a1 - c2 * a2 from step 5 (note c2's sign is reversed)
735 tmp1.Mul(c1, endomorphismA1)
736 tmp2.Mul(c2, endomorphismA2)
737 k1.Sub(bigIntK, tmp1)
738 k1.Add(k1, tmp2)
739 // k2 = - c1 * b1 - c2 * b2 from step 5 (note c2's sign is reversed)
740 tmp1.Mul(c1, endomorphismB1)
741 tmp2.Mul(c2, endomorphismB2)
742 k2.Sub(tmp2, tmp1)
743 // Note Bytes() throws out the sign of k1 and k2. This matters
744 // since k1 and/or k2 can be negative. Hence, we pass that
745 // back separately.
746 return k1.Bytes(), k2.Bytes(), k1.Sign(), k2.Sign()
747 }
748
749 func TestSplitK(t *testing.T) {
750 tests := []struct {
751 k string
752 k1, k2 string
753 s1, s2 int
754 }{
755 {
756 "6df2b5d30854069ccdec40ae022f5c948936324a4e9ebed8eb82cfd5a6b6d766",
757 "00000000000000000000000000000000b776e53fb55f6b006a270d42d64ec2b1",
758 "00000000000000000000000000000000d6cc32c857f1174b604eefc544f0c7f7",
759 -1, -1,
760 },
761 {
762 "6ca00a8f10632170accc1b3baf2a118fa5725f41473f8959f34b8f860c47d88d",
763 "0000000000000000000000000000000007b21976c1795723c1bfbfa511e95b84",
764 "00000000000000000000000000000000d8d2d5f9d20fc64fd2cf9bda09a5bf90",
765 1, -1,
766 },
767 {
768 "b2eda8ab31b259032d39cbc2a234af17fcee89c863a8917b2740b67568166289",
769 "00000000000000000000000000000000507d930fecda7414fc4a523b95ef3c8c",
770 "00000000000000000000000000000000f65ffb179df189675338c6185cb839be",
771 -1, -1,
772 },
773 {
774 "f6f00e44f179936f2befc7442721b0633f6bafdf7161c167ffc6f7751980e3a0",
775 "0000000000000000000000000000000008d0264f10bcdcd97da3faa38f85308d",
776 "0000000000000000000000000000000065fed1506eb6605a899a54e155665f79",
777 -1, -1,
778 },
779 {
780 "8679085ab081dc92cdd23091ce3ee998f6b320e419c3475fae6b5b7d3081996e",
781 "0000000000000000000000000000000089fbf24fbaa5c3c137b4f1cedc51d975",
782 "00000000000000000000000000000000d38aa615bd6754d6f4d51ccdaf529fea",
783 -1, -1,
784 },
785 {
786 "6b1247bb7931dfcae5b5603c8b5ae22ce94d670138c51872225beae6bba8cdb3",
787 "000000000000000000000000000000008acc2a521b21b17cfb002c83be62f55d",
788 "0000000000000000000000000000000035f0eff4d7430950ecb2d94193dedc79",
789 -1, -1,
790 },
791 {
792 "a2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba219b51835b55cc30ebfe2f6599bc56f58",
793 "0000000000000000000000000000000045c53aa1bb56fcd68c011e2dad6758e4",
794 "00000000000000000000000000000000a2e79d200f27f2360fba57619936159b",
795 -1, -1,
796 },
797 }
798 s256 := S256()
799 for i, test := range tests {
800 k, ok := new(big.Int).SetString(test.k, 16)
801 if !ok {
802 t.Errorf("%d: bad value for k: %s", i, test.k)
803 }
804 k1, k2, k1Sign, k2Sign := splitK(k.Bytes())
805 k1str := fmt.Sprintf("%064x", k1)
806 if test.k1 != k1str {
807 t.Errorf("%d: bad k1: got %v, want %v", i, k1str, test.k1)
808 }
809 k2str := fmt.Sprintf("%064x", k2)
810 if test.k2 != k2str {
811 t.Errorf("%d: bad k2: got %v, want %v", i, k2str, test.k2)
812 }
813 if test.s1 != k1Sign {
814 t.Errorf("%d: bad k1 sign: got %d, want %d", i, k1Sign, test.s1)
815 }
816 if test.s2 != k2Sign {
817 t.Errorf("%d: bad k2 sign: got %d, want %d", i, k2Sign, test.s2)
818 }
819 k1Int := new(big.Int).SetBytes(k1)
820 k1SignInt := new(big.Int).SetInt64(int64(k1Sign))
821 k1Int.Mul(k1Int, k1SignInt)
822 k2Int := new(big.Int).SetBytes(k2)
823 k2SignInt := new(big.Int).SetInt64(int64(k2Sign))
824 k2Int.Mul(k2Int, k2SignInt)
825 gotK := new(big.Int).Mul(k2Int, endomorphismLambda)
826 gotK.Add(k1Int, gotK)
827 gotK.Mod(gotK, s256.N)
828 if k.Cmp(gotK) != 0 {
829 t.Errorf("%d: bad k: got %X, want %X", i, gotK.Bytes(), k.Bytes())
830 }
831 }
832 }
833
834 func TestSplitKRand(t *testing.T) {
835 s256 := S256()
836 for i := 0; i < 1024; i++ {
837 bytesK := make([]byte, 32)
838 _, err := rand.Read(bytesK)
839 if err != nil {
840 t.Fatalf("failed to read random data at %d", i)
841 break
842 }
843 k := new(big.Int).SetBytes(bytesK)
844 k1, k2, k1Sign, k2Sign := splitK(bytesK)
845 k1Int := new(big.Int).SetBytes(k1)
846 k1SignInt := new(big.Int).SetInt64(int64(k1Sign))
847 k1Int.Mul(k1Int, k1SignInt)
848 k2Int := new(big.Int).SetBytes(k2)
849 k2SignInt := new(big.Int).SetInt64(int64(k2Sign))
850 k2Int.Mul(k2Int, k2SignInt)
851 gotK := new(big.Int).Mul(k2Int, endomorphismLambda)
852 gotK.Add(k1Int, gotK)
853 gotK.Mod(gotK, s256.N)
854 if k.Cmp(gotK) != 0 {
855 t.Errorf("%d: bad k: got %X, want %X", i, gotK.Bytes(), k.Bytes())
856 }
857 }
858 }
859
860 // Test this curve's usage with the ecdsa package.
861
862 func testKeyGeneration(t *testing.T, c *KoblitzCurve, tag string) {
863 priv, err := NewSecretKey()
864 if err != nil {
865 t.Errorf("%s: error: %s", tag, err)
866 return
867 }
868 pub := priv.PubKey()
869 if !c.IsOnCurve(pub.X(), pub.Y()) {
870 t.Errorf("%s: public key invalid: %s", tag, err)
871 }
872 }
873
874 func TestKeyGeneration(t *testing.T) {
875 testKeyGeneration(t, S256(), "S256")
876 }
877
878 // checkNAFEncoding returns an error if the provided positive and negative
879 // portions of an overall NAF encoding do not adhere to the requirements or they
880 // do not sum back to the provided original value.
881 func checkNAFEncoding(pos, neg []byte, origValue *big.Int) error {
882 // NAF must not have a leading zero byte and the number of negative
883 // bytes must not exceed the positive portion.
884 if len(pos) > 0 && pos[0] == 0 {
885 return fmt.Errorf("positive has leading zero -- got %x", pos)
886 }
887 if len(neg) > len(pos) {
888 return fmt.Errorf(
889 "negative has len %d > pos len %d", len(neg),
890 len(pos),
891 )
892 }
893 // Ensure the result doesn't have any adjacent non-zero digits.
894 gotPos := new(big.Int).SetBytes(pos)
895 gotNeg := new(big.Int).SetBytes(neg)
896 posOrNeg := new(big.Int).Or(gotPos, gotNeg)
897 prevBit := posOrNeg.Bit(0)
898 for bit := 1; bit < posOrNeg.BitLen(); bit++ {
899 thisBit := posOrNeg.Bit(bit)
900 if prevBit == 1 && thisBit == 1 {
901 return fmt.Errorf(
902 "adjacent non-zero digits found at bit pos %d",
903 bit-1,
904 )
905 }
906 prevBit = thisBit
907 }
908 // Ensure the resulting positive and negative portions of the overall
909 // NAF representation sum back to the original value.
910 gotValue := new(big.Int).Sub(gotPos, gotNeg)
911 if origValue.Cmp(gotValue) != 0 {
912 return fmt.Errorf(
913 "pos-neg is not original value: got %x, want %x",
914 gotValue, origValue,
915 )
916 }
917 return nil
918 }
919