ellipticadaptor_test.go raw
1 // Copyright (c) 2020-2022 The Decred developers
2 // Use of this source code is governed by an ISC
3 // license that can be found in the LICENSE file.
4
5 package secp256k1
6
7 import (
8 "math/big"
9 "math/rand"
10 "testing"
11 "time"
12
13 "next.orly.dev/pkg/lol/chk"
14 )
15
16 // randBytes returns a byte slice of the required size created from a random
17 // value generated by the passed rng.
18 func randBytes(t *testing.T, rng *rand.Rand, numBytes uint8) []byte {
19 t.Helper()
20
21 buf := make([]byte, numBytes)
22 if _, err := rng.Read(buf); chk.T(err) {
23 t.Fatalf("failed to read random: %v", err)
24 }
25
26 return buf
27 }
28
29 // TestIsOnCurveAdaptor ensures the IsOnCurve method used to satisfy the
30 // elliptic.Curve interface works as intended.
31 func TestIsOnCurveAdaptor(t *testing.T) {
32 s256 := S256()
33 if !s256.IsOnCurve(s256.Params().Gx, s256.Params().Gy) {
34 t.Fatal("generator point does not claim to be on the curve")
35 }
36 }
37
38 // isValidAffinePoint returns true if the point (x,y) is on the secp256k1 curve
39 // or is the point at infinity.
40 func isValidAffinePoint(x, y *big.Int) bool {
41 if x.Sign() == 0 && y.Sign() == 0 {
42 return true
43 }
44 return S256().IsOnCurve(x, y)
45 }
46
47 // TestAddAffineAdaptor tests addition of points in affine coordinates via the
48 // method used to satisfy the elliptic.Curve interface works as intended for
49 // some edge cases and known good values.
50 func TestAddAffineAdaptor(t *testing.T) {
51 tests := []struct {
52 name string // test description
53 x1, y1 string // hex encoded coordinates of first point to add
54 x2, y2 string // hex encoded coordinates of second point to add
55 x3, y3 string // hex encoded coordinates of expected point
56 }{
57 {
58 // Addition with the point at infinity (left hand side).
59 name: "∞ + P = P",
60 x1: "0",
61 y1: "0",
62 x2: "d74bf844b0862475103d96a611cf2d898447e288d34b360bc885cb8ce7c00575",
63 y2: "131c670d414c4546b88ac3ff664611b1c38ceb1c21d76369d7a7a0969d61d97d",
64 x3: "d74bf844b0862475103d96a611cf2d898447e288d34b360bc885cb8ce7c00575",
65 y3: "131c670d414c4546b88ac3ff664611b1c38ceb1c21d76369d7a7a0969d61d97d",
66 }, {
67 // Addition with the point at infinity (right hand side).
68 name: "P + ∞ = P",
69 x1: "d74bf844b0862475103d96a611cf2d898447e288d34b360bc885cb8ce7c00575",
70 y1: "131c670d414c4546b88ac3ff664611b1c38ceb1c21d76369d7a7a0969d61d97d",
71 x2: "0",
72 y2: "0",
73 x3: "d74bf844b0862475103d96a611cf2d898447e288d34b360bc885cb8ce7c00575",
74 y3: "131c670d414c4546b88ac3ff664611b1c38ceb1c21d76369d7a7a0969d61d97d",
75 }, {
76 // Addition with different x values.
77 name: "P(x1, y1) + P(x2, y2)",
78 x1: "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
79 y1: "0b71ea9bd730fd8923f6d25a7a91e7dd7728a960686cb5a901bb419e0f2ca232",
80 x2: "d74bf844b0862475103d96a611cf2d898447e288d34b360bc885cb8ce7c00575",
81 y2: "131c670d414c4546b88ac3ff664611b1c38ceb1c21d76369d7a7a0969d61d97d",
82 x3: "fd5b88c21d3143518d522cd2796f3d726793c88b3e05636bc829448e053fed69",
83 y3: "21cf4f6a5be5ff6380234c50424a970b1f7e718f5eb58f68198c108d642a137f",
84 }, {
85 // Addition with same x opposite y.
86 name: "P(x, y) + P(x, -y) = ∞",
87 x1: "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
88 y1: "0b71ea9bd730fd8923f6d25a7a91e7dd7728a960686cb5a901bb419e0f2ca232",
89 x2: "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
90 y2: "f48e156428cf0276dc092da5856e182288d7569f97934a56fe44be60f0d359fd",
91 x3: "0",
92 y3: "0",
93 }, {
94 // Addition with same point.
95 name: "P(x, y) + P(x, y) = 2P",
96 x1: "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
97 y1: "0b71ea9bd730fd8923f6d25a7a91e7dd7728a960686cb5a901bb419e0f2ca232",
98 x2: "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
99 y2: "0b71ea9bd730fd8923f6d25a7a91e7dd7728a960686cb5a901bb419e0f2ca232",
100 x3: "59477d88ae64a104dbb8d31ec4ce2d91b2fe50fa628fb6a064e22582196b365b",
101 y3: "938dc8c0f13d1e75c987cb1a220501bd614b0d3dd9eb5c639847e1240216e3b6",
102 },
103 }
104 curve := S256()
105 for _, test := range tests {
106 // Parse the test data.
107 x1, y1 := fromHex(test.x1), fromHex(test.y1)
108 x2, y2 := fromHex(test.x2), fromHex(test.y2)
109 x3, y3 := fromHex(test.x3), fromHex(test.y3)
110 // Ensure the test data is using points that are actually on the curve
111 // (or the point at infinity).
112 if !isValidAffinePoint(x1, y1) {
113 t.Errorf("%s: first point is not on curve", test.name)
114 continue
115 }
116 if !isValidAffinePoint(x2, y2) {
117 t.Errorf("%s: second point is not on curve", test.name)
118 continue
119 }
120 if !isValidAffinePoint(x3, y3) {
121 t.Errorf("%s: expected point is not on curve", test.name)
122 continue
123 }
124 // Add the two points and ensure the result matches expected.
125 rx, ry := curve.Add(x1, y1, x2, y2)
126 if rx.Cmp(x3) != 0 || ry.Cmp(y3) != 0 {
127 t.Errorf(
128 "%s: wrong result\ngot: (%x, %x)\nwant: (%x, %x)",
129 test.name, rx, ry, x3, y3,
130 )
131 continue
132 }
133 }
134 }
135
136 // TestDoubleAffineAdaptor tests doubling of points in affine coordinates via
137 // the method used to satisfy the elliptic.Curve interface works as intended for
138 // some edge cases and known good values.
139 func TestDoubleAffineAdaptor(t *testing.T) {
140 tests := []struct {
141 name string // test description
142 x1, y1 string // hex encoded coordinates of point to double
143 x3, y3 string // hex encoded coordinates of expected point
144 }{
145 {
146 // Doubling the point at infinity is still the point at infinity.
147 name: "2*∞ = ∞ (point at infinity)",
148 x1: "0",
149 y1: "0",
150 x3: "0",
151 y3: "0",
152 }, {
153 name: "random point 1",
154 x1: "e41387ffd8baaeeb43c2faa44e141b19790e8ac1f7ff43d480dc132230536f86",
155 y1: "1b88191d430f559896149c86cbcb703193105e3cf3213c0c3556399836a2b899",
156 x3: "88da47a089d333371bd798c548ef7caae76e737c1980b452d367b3cfe3082c19",
157 y3: "3b6f659b09a362821dfcfefdbfbc2e59b935ba081b6c249eb147b3c2100b1bc1",
158 }, {
159 name: "random point 2",
160 x1: "b3589b5d984f03ef7c80aeae444f919374799edf18d375cab10489a3009cff0c",
161 y1: "c26cf343875b3630e15bccc61202815b5d8f1fd11308934a584a5babe69db36a",
162 x3: "e193860172998751e527bb12563855602a227fc1f612523394da53b746bb2fb1",
163 y3: "2bfcf13d2f5ab8bb5c611fab5ebbed3dc2f057062b39a335224c22f090c04789",
164 }, {
165 name: "random point 3",
166 x1: "2b31a40fbebe3440d43ac28dba23eee71c62762c3fe3dbd88b4ab82dc6a82340",
167 y1: "9ba7deb02f5c010e217607fd49d58db78ec273371ea828b49891ce2fd74959a1",
168 x3: "2c8d5ef0d343b1a1a48aa336078eadda8481cb048d9305dc4fdf7ee5f65973a2",
169 y3: "bb4914ac729e26d3cd8f8dc8f702f3f4bb7e0e9c5ae43335f6e94c2de6c3dc95",
170 }, {
171 name: "random point 4",
172 x1: "61c64b760b51981fab54716d5078ab7dffc93730b1d1823477e27c51f6904c7a",
173 y1: "ef6eb16ea1a36af69d7f66524c75a3a5e84c13be8fbc2e811e0563c5405e49bd",
174 x3: "5f0dcdd2595f5ad83318a0f9da481039e36f135005420393e72dfca985b482f4",
175 y3: "a01c849b0837065c1cb481b0932c441f49d1cab1b4b9f355c35173d93f110ae0",
176 },
177 }
178 curve := S256()
179 for _, test := range tests {
180 // Parse test data.
181 x1, y1 := fromHex(test.x1), fromHex(test.y1)
182 x3, y3 := fromHex(test.x3), fromHex(test.y3)
183 // Ensure the test data is using points that are actually on
184 // the curve (or the point at infinity).
185 if !isValidAffinePoint(x1, y1) {
186 t.Errorf("%s: first point is not on the curve", test.name)
187 continue
188 }
189 if !isValidAffinePoint(x3, y3) {
190 t.Errorf("%s: expected point is not on the curve", test.name)
191 continue
192 }
193 // Double the point and ensure the result matches expected.
194 rx, ry := curve.Double(x1, y1)
195 if rx.Cmp(x3) != 0 || ry.Cmp(y3) != 0 {
196 t.Errorf(
197 "%s: wrong result\ngot: (%x, %x)\nwant: (%x, %x)",
198 test.name, rx, ry, x3, y3,
199 )
200 continue
201 }
202 }
203 }
204
205 // TestScalarBaseMultAdaptor ensures the ScalarBaseMult method used to satisfy
206 // the elliptic.Curve interface works as intended for some edge cases and known
207 // good values.
208 func TestScalarBaseMultAdaptor(t *testing.T) {
209 tests := []struct {
210 name string // test description
211 k string // hex encoded scalar
212 rx, ry string // hex encoded coordinates of expected point
213 }{
214 {
215 name: "zero",
216 k: "0000000000000000000000000000000000000000000000000000000000000000",
217 rx: "0000000000000000000000000000000000000000000000000000000000000000",
218 ry: "0000000000000000000000000000000000000000000000000000000000000000",
219 }, {
220 name: "one (aka 1*G = G)",
221 k: "0000000000000000000000000000000000000000000000000000000000000001",
222 rx: "79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798",
223 ry: "483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8",
224 }, {
225 name: "group order - 1 (aka -1*G = -G)",
226 k: "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140",
227 rx: "79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798",
228 ry: "b7c52588d95c3b9aa25b0403f1eef75702e84bb7597aabe663b82f6f04ef2777",
229 }, {
230 name: "known good point 1",
231 k: "aa5e28d6a97a2479a65527f7290311a3624d4cc0fa1578598ee3c2613bf99522",
232 rx: "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
233 ry: "0b71ea9bd730fd8923f6d25a7a91e7dd7728a960686cb5a901bb419e0f2ca232",
234 }, {
235 name: "known good point 2",
236 k: "7e2b897b8cebc6361663ad410835639826d590f393d90a9538881735256dfae3",
237 rx: "d74bf844b0862475103d96a611cf2d898447e288d34b360bc885cb8ce7c00575",
238 ry: "131c670d414c4546b88ac3ff664611b1c38ceb1c21d76369d7a7a0969d61d97d",
239 }, {
240 name: "known good point 3",
241 k: "6461e6df0fe7dfd05329f41bf771b86578143d4dd1f7866fb4ca7e97c5fa945d",
242 rx: "e8aecc370aedd953483719a116711963ce201ac3eb21d3f3257bb48668c6a72f",
243 ry: "c25caf2f0eba1ddb2f0f3f47866299ef907867b7d27e95b3873bf98397b24ee1",
244 }, {
245 name: "known good point 4",
246 k: "376a3a2cdcd12581efff13ee4ad44c4044b8a0524c42422a7e1e181e4deeccec",
247 rx: "14890e61fcd4b0bd92e5b36c81372ca6fed471ef3aa60a3e415ee4fe987daba1",
248 ry: "297b858d9f752ab42d3bca67ee0eb6dcd1c2b7b0dbe23397e66adc272263f982",
249 }, {
250 name: "known good point 5",
251 k: "1b22644a7be026548810c378d0b2994eefa6d2b9881803cb02ceff865287d1b9",
252 rx: "f73c65ead01c5126f28f442d087689bfa08e12763e0cec1d35b01751fd735ed3",
253 ry: "f449a8376906482a84ed01479bd18882b919c140d638307f0c0934ba12590bde",
254 },
255 }
256 curve := S256()
257 for _, test := range tests {
258 // Parse the test data.
259 k := fromHex(test.k)
260 xWant, yWant := fromHex(test.rx), fromHex(test.ry)
261 // Ensure the test data is using points that are actually on the curve
262 // (or the point at infinity).
263 if !isValidAffinePoint(xWant, yWant) {
264 t.Errorf("%s: expected point is not on curve", test.name)
265 continue
266 }
267 rx, ry := curve.ScalarBaseMult(k.Bytes())
268 if rx.Cmp(xWant) != 0 || ry.Cmp(yWant) != 0 {
269 t.Errorf(
270 "%s: wrong result:\ngot (%x, %x)\nwant (%x, %x)",
271 test.name, rx, ry, xWant, yWant,
272 )
273 }
274 }
275 }
276
277 // TestScalarBaseMultAdaptorRandom ensures that the ScalarBaseMult method used
278 // to satisfy the elliptic.Curve interface works as intended for
279 // randomly-generated scalars of all lengths up to 40 bytes.
280 func TestScalarBaseMultAdaptorRandom(t *testing.T) {
281 // Use a unique random seed each test instance and log it if the tests fail.
282 seed := time.Now().Unix()
283 rng := rand.New(rand.NewSource(seed))
284 defer func(t *testing.T, seed int64) {
285 if t.Failed() {
286 t.Logf("random seed: %d", seed)
287 }
288 }(t, seed)
289 s256 := S256()
290 const maxBytes = 40
291 const iterations = 10
292 for numBytes := uint8(1); numBytes < maxBytes; numBytes++ {
293 for i := 0; i < iterations; i++ {
294 // Generate a random scalar of the current length.
295 k := randBytes(t, rng, numBytes)
296 // Ensure the correct results by performing the multiplication with
297 // both the func under test as well as the generic scalar mult func.
298 x, y := s256.ScalarBaseMult(k)
299 xWant, yWant := s256.ScalarMult(s256.Gx, s256.Gy, k)
300 if x.Cmp(xWant) != 0 || y.Cmp(yWant) != 0 {
301 t.Errorf(
302 "bad output for %x: got (%x, %x), want (%x, %x)", k,
303 x, y, xWant, yWant,
304 )
305 continue
306 }
307 }
308 }
309 }
310
311 // TestScalarMultAdaptor ensures the ScalarMult method used to satisfy the
312 // elliptic.Curve interface works as intended for some edge cases and known good
313 // values.
314 func TestScalarMultAdaptor(t *testing.T) {
315 tests := []struct {
316 name string // test description
317 k string // hex encoded scalar
318 x, y string // hex encoded coordinates of point to multiply
319 rx, ry string // hex encoded coordinates of expected point
320 }{
321 {
322 name: "0*P = ∞ (point at infinity)",
323 k: "0",
324 x: "7e660beda020e9cc20391cef85374576853b0f22b8925d5d81c5845bb834c21e",
325 y: "2d114a5edb320cc9806527d1daf1bbb96a8fedc6f9e8ead421eaef2c7208e409",
326 rx: "0",
327 ry: "0",
328 }, {
329 name: "1*P = P",
330 k: "1",
331 x: "c00be8830995d1e44f1420dd3b90d3441fb66f6861c84a35f959c495a3be5440",
332 y: "ecf9665e6eba45720de652a340600c7356efe24d228bfe6ea2043e7791c51bb7",
333 rx: "c00be8830995d1e44f1420dd3b90d3441fb66f6861c84a35f959c495a3be5440",
334 ry: "ecf9665e6eba45720de652a340600c7356efe24d228bfe6ea2043e7791c51bb7",
335 }, {
336 name: "(group order - 1)*P = -P (aka -1*P = -P)",
337 k: "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140",
338 x: "74a1ad6b5f76e39db2dd249410eac7f99e74c59cb83d2d0ed5ff1543da7703e9",
339 y: "cc6157ef18c9c63cd6193d83631bbea0093e0968942e8c33d5737fd790e0db08",
340 rx: "74a1ad6b5f76e39db2dd249410eac7f99e74c59cb83d2d0ed5ff1543da7703e9",
341 ry: "339ea810e73639c329e6c27c9ce4415ff6c1f6976bd173cc2a8c80276f1f2127",
342 }, {
343 name: "(group order - 1)*-P = P (aka -1*-P = -P, with P from prev test)",
344 k: "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140",
345 x: "74a1ad6b5f76e39db2dd249410eac7f99e74c59cb83d2d0ed5ff1543da7703e9",
346 y: "339ea810e73639c329e6c27c9ce4415ff6c1f6976bd173cc2a8c80276f1f2127",
347 rx: "74a1ad6b5f76e39db2dd249410eac7f99e74c59cb83d2d0ed5ff1543da7703e9",
348 ry: "cc6157ef18c9c63cd6193d83631bbea0093e0968942e8c33d5737fd790e0db08",
349 }, {
350 name: "known good point from base mult tests (aka k*G)",
351 k: "aa5e28d6a97a2479a65527f7290311a3624d4cc0fa1578598ee3c2613bf99522",
352 x: "79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798",
353 y: "483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8",
354 rx: "34f9460f0e4f08393d192b3c5133a6ba099aa0ad9fd54ebccfacdfa239ff49c6",
355 ry: "0b71ea9bd730fd8923f6d25a7a91e7dd7728a960686cb5a901bb419e0f2ca232",
356 }, {
357 name: "known good result 1",
358 k: "7e2b897b8cebc6361663ad410835639826d590f393d90a9538881735256dfae3",
359 x: "1697ffa6fd9de627c077e3d2fe541084ce13300b0bec1146f95ae57f0d0bd6a5",
360 y: "b9c398f186806f5d27561506e4557433a2cf15009e498ae7adee9d63d01b2396",
361 rx: "6951f3b50aafbc63e21707dd53623b7f42badd633a0567ef1b37f6e42a4237ad",
362 ry: "9c930796a49110122fbfdedc36418af726197ed950b783a2d29058f8c02130de",
363 }, {
364 name: "known good result 2",
365 k: "6461e6df0fe7dfd05329f41bf771b86578143d4dd1f7866fb4ca7e97c5fa945d",
366 x: "659214ac1a1790023f53c4cf55a0a63b9e20c1151efa971215b395a558aa151",
367 y: "b126363aa4243d2759320a356230569a4eea355d9dabd94ed7f4590701e5364d",
368 rx: "4ffad856833396ef753c0bd4ea40319295f107c476793df0adac2caea53b3df4",
369 ry: "586fa6b1e9a3ff7df8a2b9b3698badcf40aa06af5600fefc56dd8ae4db5451c5",
370 }, {
371 name: "known good result 3",
372 k: "376a3a2cdcd12581efff13ee4ad44c4044b8a0524c42422a7e1e181e4deeccec",
373 x: "3f0e80e574456d8f8fa64e044b2eb72ea22eb53fe1efe3a443933aca7f8cb0e3",
374 y: "cb66d7d7296cbc91e90b9c08485d01b39501253aa65b53a4cb0289e2ea5f404f",
375 rx: "35ae6480b18e48070709d9276ed97a50c6ee1fc05ac44386c85826533233d28f",
376 ry: "f88abee3efabd95e80ce8c664bbc3d4d12b24e1a0f4d2b98ba6542789c6715fd",
377 }, {
378 name: "known good result 4",
379 k: "1b22644a7be026548810c378d0b2994eefa6d2b9881803cb02ceff865287d1b9",
380 x: "d7924d4f7d43ea965a465ae3095ff41131e5946f3c85f79e44adbcf8e27e080e",
381 y: "581e2872a86c72a683842ec228cc6defea40af2bd896d3a5c504dc9ff6a26b58",
382 rx: "cca7f9a4b0d379c31c438050e163a8945f2f910498bd3b545be20ed862bd6cd9",
383 ry: "cfc7bbf37bef62da6e5753ed419168fa1376a3fe949c139a8dd0f5303f4ae947",
384 }, {
385 name: "known good result 5",
386 k: "7f5b2cb4b43840c75e4afad83d792e1965d8c21c1109505f45c7d46df422d73e",
387 x: "bce74de6d5f98dc027740c2bbff05b6aafe5fd8d103f827e48894a2bd3460117",
388 y: "5bea1fa17a41b115525a3e7dbf0d8d5a4f7ce5c6fc73a6f4f216512417c9f6b4",
389 rx: "3d96b9290fe6c4f2d62fe2175f4333907d0c3637fada1010b45c7d80690e16de",
390 ry: "d59c0e8192d7fbd4846172d6479630b751cd03d0d9be0dca2759c6212b70575d",
391 }, {
392 // From btcd issue #709.
393 name: "early implementation regression point",
394 k: "a2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba219b51835b55cc30ebfe2f6599bc56f58",
395 x: "000000000000000000000000000000000000000000000000000000000000002c",
396 y: "420e7a99bba18a9d3952597510fd2b6728cfeafc21a4e73951091d4d8ddbe94e",
397 rx: "a2112dcdfbcd10ae1133a358de7b82db68e0a3eb4b492cc8268d1e7118c98788",
398 ry: "27fc7463b7bb3c5f98ecf2c84a6272bb1681ed553d92c69f2dfe25a9f9fd3836",
399 },
400 }
401 curve := S256()
402 for _, test := range tests {
403 // Parse the test data.
404 k := fromHex(test.k)
405 x, y := fromHex(test.x), fromHex(test.y)
406 xWant, yWant := fromHex(test.rx), fromHex(test.ry)
407 // Ensure the test data is using points that are actually on the curve
408 // (or the point at infinity).
409 if !isValidAffinePoint(x, y) {
410 t.Errorf("%s: point is not on curve", test.name)
411 continue
412 }
413 if !isValidAffinePoint(xWant, yWant) {
414 t.Errorf("%s: expected point is not on curve", test.name)
415 continue
416 }
417 // Perform scalar point multiplication ensure the result matches
418 // expected.
419 rx, ry := curve.ScalarMult(x, y, k.Bytes())
420 if rx.Cmp(xWant) != 0 || ry.Cmp(yWant) != 0 {
421 t.Errorf(
422 "%s: wrong result\ngot: (%x, %x)\nwant: (%x, %x)",
423 test.name, rx, ry, xWant, yWant,
424 )
425 }
426 }
427 }
428