modnscalar_test.go raw
1 // Copyright (c) 2020-2023 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 "fmt"
9 "math/big"
10 "math/rand"
11 "reflect"
12 "testing"
13 "time"
14
15 "next.orly.dev/pkg/nostr/encoders/hex"
16 "next.orly.dev/pkg/nostr/utils"
17 "next.orly.dev/pkg/lol/chk"
18 )
19
20 // SetHex interprets the provided hex string as a 256-bit big-endian unsigned
21 // integer (meaning it is truncated to the first 32 bytes), reduces it modulo
22 // the group order and sets the scalar to the result.
23 //
24 // This is NOT constant time.
25 //
26 // The scalar is returned to support chaining. This enables syntax like:
27 // s := new(ModNScalar).SetHex("0abc").Add(1) so that s = 0x0abc + 1
28 func (s *ModNScalar) SetHex(hexString string) *ModNScalar {
29 if len(hexString)%2 != 0 {
30 hexString = "0" + hexString
31 }
32 bytes, _ := hex.Dec(hexString)
33 s.SetByteSlice(bytes)
34 return s
35 }
36
37 // randModNScalar returns a mod N scalar created from a random value generated
38 // by the passed rng.
39 func randModNScalar(t *testing.T, rng *rand.Rand) *ModNScalar {
40 t.Helper()
41 var buf [32]byte
42 if _, err := rng.Read(buf[:]); chk.T(err) {
43 t.Fatalf("failed to read random: %v", err)
44 }
45 // Create and return a mod N scalar.
46 var modNVal ModNScalar
47 modNVal.SetBytes(&buf)
48 return &modNVal
49 }
50
51 // randIntAndModNScalar returns a big integer and mod N scalar both created from
52 // the same random value generated by the passed rng.
53 func randIntAndModNScalar(t *testing.T, rng *rand.Rand) (
54 *big.Int,
55 *ModNScalar,
56 ) {
57 t.Helper()
58 var buf [32]byte
59 if _, err := rng.Read(buf[:]); chk.T(err) {
60 t.Fatalf("failed to read random: %v", err)
61 }
62 // Create and return both a big integer and a mod N scalar.
63 bigIntVal := new(big.Int).SetBytes(buf[:])
64 bigIntVal.Mod(bigIntVal, curveParams.N)
65 var modNVal ModNScalar
66 modNVal.SetBytes(&buf)
67 return bigIntVal, &modNVal
68 }
69
70 // TestModNScalarZero ensures that zeroing a scalar modulo the group order works
71 // as expected.
72 func TestModNScalarZero(t *testing.T) {
73 var s ModNScalar
74 s.SetHex("a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5")
75 s.Zero()
76 for idx, rawInt := range s.n {
77 if rawInt != 0 {
78 t.Errorf(
79 "internal integer at index #%d is not zero - got %d", idx,
80 rawInt,
81 )
82 }
83 }
84 }
85
86 // TestModNScalarIsZero ensures that checking if a scalar is zero via IsZero and
87 // IsZeroBit works as expected.
88 func TestModNScalarIsZero(t *testing.T) {
89 var s ModNScalar
90 if !s.IsZero() {
91 t.Errorf("new scalar is not zero - got %v (rawints %x)", s, s.n)
92 }
93 if s.IsZeroBit() != 1 {
94 t.Errorf("new scalar is not zero - got %v (rawints %x)", s, s.n)
95 }
96 s.SetInt(1)
97 if s.IsZero() {
98 t.Errorf("claims zero for nonzero scalar - got %v (rawints %x)", s, s.n)
99 }
100 if s.IsZeroBit() == 1 {
101 t.Errorf("claims zero for nonzero scalar - got %v (rawints %x)", s, s.n)
102 }
103
104 s.SetInt(0)
105 if !s.IsZero() {
106 t.Errorf("claims nonzero for zero scalar - got %v (rawints %x)", s, s.n)
107 }
108 if s.IsZeroBit() != 1 {
109 t.Errorf("claims nonzero for zero scalar - got %v (rawints %x)", s, s.n)
110 }
111 s.SetInt(1)
112 s.Zero()
113 if !s.IsZero() {
114 t.Errorf("claims nonzero for zero scalar - got %v (rawints %x)", s, s.n)
115 }
116 if s.IsZeroBit() != 1 {
117 t.Errorf("claims nonzero for zero scalar - got %v (rawints %x)", s, s.n)
118 }
119 }
120
121 // TestModNScalarSetInt ensures that setting a scalar to various native integers
122 // works as expected.
123 func TestModNScalarSetInt(t *testing.T) {
124 tests := []struct {
125 name string // test description
126 in uint32 // test value
127 expected [8]uint32 // expected raw ints
128 }{
129 {
130 name: "five",
131 in: 5,
132 expected: [8]uint32{5, 0, 0, 0, 0, 0, 0, 0},
133 }, {
134 name: "group order word zero",
135 in: orderWordZero,
136 expected: [8]uint32{orderWordZero, 0, 0, 0, 0, 0, 0, 0},
137 }, {
138 name: "group order word zero + 1",
139 in: orderWordZero + 1,
140 expected: [8]uint32{orderWordZero + 1, 0, 0, 0, 0, 0, 0, 0},
141 }, {
142 name: "2^32 - 1",
143 in: 4294967295,
144 expected: [8]uint32{4294967295, 0, 0, 0, 0, 0, 0, 0},
145 },
146 }
147 for _, test := range tests {
148 s := new(ModNScalar).SetInt(test.in)
149 if !reflect.DeepEqual(s.n, test.expected) {
150 t.Errorf(
151 "%s: wrong result\ngot: %v\nwant: %v", test.name, s.n,
152 test.expected,
153 )
154 continue
155 }
156 }
157 }
158
159 // TestModNScalarSetBytes ensures that setting a scalar to a 256-bit big-endian
160 // unsigned integer via both the slice and array methods works as expected for
161 // edge cases. Random cases are tested via the various other tests.
162 func TestModNScalarSetBytes(t *testing.T) {
163 tests := []struct {
164 name string // test description
165 in string // hex encoded test value
166 expected [8]uint32 // expected raw ints
167 overflow bool // expected overflow result
168 }{
169 {
170 name: "zero",
171 in: "00",
172 expected: [8]uint32{0, 0, 0, 0, 0, 0, 0, 0},
173 overflow: false,
174 }, {
175 name: "group order (aka 0)",
176 in: "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141",
177 expected: [8]uint32{0, 0, 0, 0, 0, 0, 0, 0},
178 overflow: true,
179 }, {
180 name: "group order - 1",
181 in: "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140",
182 expected: [8]uint32{
183 0xd0364140, 0xbfd25e8c, 0xaf48a03b, 0xbaaedce6,
184 0xfffffffe, 0xffffffff, 0xffffffff, 0xffffffff,
185 },
186 overflow: false,
187 }, {
188 name: "group order + 1 (aka 1, overflow in word zero)",
189 in: "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364142",
190 expected: [8]uint32{1, 0, 0, 0, 0, 0, 0, 0},
191 overflow: true,
192 }, {
193 name: "group order word zero",
194 in: "d0364141",
195 expected: [8]uint32{0xd0364141, 0, 0, 0, 0, 0, 0, 0},
196 overflow: false,
197 }, {
198 name: "group order word zero and one",
199 in: "bfd25e8cd0364141",
200 expected: [8]uint32{0xd0364141, 0xbfd25e8c, 0, 0, 0, 0, 0, 0},
201 overflow: false,
202 }, {
203 name: "group order words zero, one, and two",
204 in: "af48a03bbfd25e8cd0364141",
205 expected: [8]uint32{
206 0xd0364141, 0xbfd25e8c, 0xaf48a03b, 0, 0, 0, 0, 0,
207 },
208 overflow: false,
209 }, {
210 name: "overflow in word one",
211 in: "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8dd0364141",
212 expected: [8]uint32{0, 1, 0, 0, 0, 0, 0, 0},
213 overflow: true,
214 }, {
215 name: "overflow in word two",
216 in: "fffffffffffffffffffffffffffffffebaaedce6af48a03cbfd25e8cd0364141",
217 expected: [8]uint32{0, 0, 1, 0, 0, 0, 0, 0},
218 overflow: true,
219 }, {
220 name: "overflow in word three",
221 in: "fffffffffffffffffffffffffffffffebaaedce7af48a03bbfd25e8cd0364141",
222 expected: [8]uint32{0, 0, 0, 1, 0, 0, 0, 0},
223 overflow: true,
224 }, {
225 name: "overflow in word four",
226 in: "ffffffffffffffffffffffffffffffffbaaedce6af48a03bbfd25e8cd0364141",
227 expected: [8]uint32{0, 0, 0, 0, 1, 0, 0, 0},
228 overflow: true,
229 }, {
230 name: "(group order - 1) * 2 NOT mod N, truncated >32 bytes",
231 in: "01fffffffffffffffffffffffffffffffd755db9cd5e9140777fa4bd19a06c8284",
232 expected: [8]uint32{
233 0x19a06c82, 0x777fa4bd, 0xcd5e9140, 0xfd755db9,
234 0xffffffff, 0xffffffff, 0xffffffff, 0x01ffffff,
235 },
236 overflow: false,
237 }, {
238 name: "alternating bits",
239 in: "a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5",
240 expected: [8]uint32{
241 0xa5a5a5a5, 0xa5a5a5a5, 0xa5a5a5a5, 0xa5a5a5a5,
242 0xa5a5a5a5, 0xa5a5a5a5, 0xa5a5a5a5, 0xa5a5a5a5,
243 },
244 overflow: false,
245 }, {
246 name: "alternating bits 2",
247 in: "5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a",
248 expected: [8]uint32{
249 0x5a5a5a5a, 0x5a5a5a5a, 0x5a5a5a5a, 0x5a5a5a5a,
250 0x5a5a5a5a, 0x5a5a5a5a, 0x5a5a5a5a, 0x5a5a5a5a,
251 },
252 overflow: false,
253 },
254 }
255 for _, test := range tests {
256 inBytes := hexToBytes(test.in)
257
258 // Ensure setting the bytes via the slice method works as expected.
259 var s ModNScalar
260 overflow := s.SetByteSlice(inBytes)
261 if !reflect.DeepEqual(s.n, test.expected) {
262 t.Errorf(
263 "%s: unexpected result\ngot: %x\nwant: %x", test.name, s.n,
264 test.expected,
265 )
266 continue
267 }
268 // Ensure the setting the bytes via the slice method produces the
269 // expected overflow result.
270 if overflow != test.overflow {
271 t.Errorf(
272 "%s: unexpected overflow -- got: %v, want: %v", test.name,
273 overflow, test.overflow,
274 )
275 continue
276 }
277 // Ensure setting the bytes via the array method works as expected.
278 var s2 ModNScalar
279 var b32 [32]byte
280 truncatedInBytes := inBytes
281 if len(truncatedInBytes) > 32 {
282 truncatedInBytes = truncatedInBytes[:32]
283 }
284 copy(b32[32-len(truncatedInBytes):], truncatedInBytes)
285 overflow = s2.SetBytes(&b32) != 0
286 if !reflect.DeepEqual(s2.n, test.expected) {
287 t.Errorf(
288 "%s: unexpected result\ngot: %x\nwant: %x", test.name,
289 s2.n, test.expected,
290 )
291 continue
292 }
293 // Ensure the setting the bytes via the array method produces the
294 // expected overflow result.
295 if overflow != test.overflow {
296 t.Errorf(
297 "%s: unexpected overflow -- got: %v, want: %v", test.name,
298 overflow, test.overflow,
299 )
300 continue
301 }
302 }
303 }
304
305 // TestModNScalarBytes ensures that retrieving the bytes for a 256-bit
306 // big-endian unsigned integer via the various methods works as expected for
307 // edge cases. Random cases are tested via the various other tests.
308 func TestModNScalarBytes(t *testing.T) {
309 tests := []struct {
310 name string // test description
311 in string // hex encoded test value
312 expected string // expected hex encoded bytes
313 overflow bool // expected overflow result
314 }{
315 {
316 name: "zero",
317 in: "0",
318 expected: "0000000000000000000000000000000000000000000000000000000000000000",
319 }, {
320 name: "group order (aka 0)",
321 in: "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141",
322 expected: "0000000000000000000000000000000000000000000000000000000000000000",
323 }, {
324 name: "group order - 1",
325 in: "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140",
326 expected: "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140",
327 }, {
328 name: "group order + 1 (aka 1, overflow in word zero)",
329 in: "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364142",
330 expected: "0000000000000000000000000000000000000000000000000000000000000001",
331 }, {
332 name: "group order word zero",
333 in: "d0364141",
334 expected: "00000000000000000000000000000000000000000000000000000000d0364141",
335 }, {
336 name: "group order word zero and one",
337 in: "bfd25e8cd0364141",
338 expected: "000000000000000000000000000000000000000000000000bfd25e8cd0364141",
339 }, {
340 name: "group order words zero, one, and two",
341 in: "af48a03bbfd25e8cd0364141",
342 expected: "0000000000000000000000000000000000000000af48a03bbfd25e8cd0364141",
343 }, {
344 name: "overflow in word one",
345 in: "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8dd0364141",
346 expected: "0000000000000000000000000000000000000000000000000000000100000000",
347 }, {
348 name: "overflow in word two",
349 in: "fffffffffffffffffffffffffffffffebaaedce6af48a03cbfd25e8cd0364141",
350 expected: "0000000000000000000000000000000000000000000000010000000000000000",
351 }, {
352 name: "overflow in word three",
353 in: "fffffffffffffffffffffffffffffffebaaedce7af48a03bbfd25e8cd0364141",
354 expected: "0000000000000000000000000000000000000001000000000000000000000000",
355 }, {
356 name: "overflow in word four",
357 in: "ffffffffffffffffffffffffffffffffbaaedce6af48a03bbfd25e8cd0364141",
358 expected: "0000000000000000000000000000000100000000000000000000000000000000",
359 }, {
360 name: "alternating bits",
361 in: "a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5",
362 expected: "a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5",
363 }, {
364 name: "alternating bits 2",
365 in: "5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a",
366 expected: "5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a",
367 },
368 }
369 for _, test := range tests {
370 s := new(ModNScalar).SetHex(test.in)
371 expected := hexToBytes(test.expected)
372 // Ensure getting the bytes works as expected.
373 gotBytes := s.Bytes()
374 if !utils.FastEqual(gotBytes[:], expected) {
375 t.Errorf(
376 "%s: unexpected result\ngot: %x\nwant: %x", test.name,
377 gotBytes, expected,
378 )
379 continue
380 }
381 // Ensure getting the bytes directly into an array works as expected.
382 var b32 [32]byte
383 s.PutBytes(&b32)
384 if !utils.FastEqual(b32[:], expected) {
385 t.Errorf(
386 "%s: unexpected result\ngot: %x\nwant: %x", test.name,
387 b32, expected,
388 )
389 continue
390 }
391 // Ensure getting the bytes directly into a slice works as expected.
392 var buffer [64]byte
393 s.PutBytesUnchecked(buffer[:])
394 if !utils.FastEqual(buffer[:32], expected) {
395 t.Errorf(
396 "%s: unexpected result\ngot: %x\nwant: %x", test.name,
397 buffer[:32], expected,
398 )
399 continue
400 }
401 }
402 }
403
404 // TestModNScalarIsOdd ensures that checking if a scalar is odd works as
405 // expected.
406 func TestModNScalarIsOdd(t *testing.T) {
407 tests := []struct {
408 name string // test description
409 in string // hex encoded value
410 expected bool // expected oddness
411 }{
412 {
413 name: "zero",
414 in: "0",
415 expected: false,
416 }, {
417 name: "one",
418 in: "1",
419 expected: true,
420 }, {
421 name: "two",
422 in: "2",
423 expected: false,
424 }, {
425 name: "2^32 - 1",
426 in: "ffffffff",
427 expected: true,
428 }, {
429 name: "2^64 - 2",
430 in: "fffffffffffffffe",
431 expected: false,
432 }, {
433 name: "group order (aka 0)",
434 in: "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141",
435 expected: false,
436 }, {
437 name: "group order + 1 (aka 1)",
438 in: "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364142",
439 expected: true,
440 },
441 }
442 for _, test := range tests {
443 result := new(ModNScalar).SetHex(test.in).IsOdd()
444 if result != test.expected {
445 t.Errorf(
446 "%s: wrong result -- got: %v, want: %v", test.name,
447 result, test.expected,
448 )
449 continue
450 }
451 }
452 }
453
454 // TestModNScalarEquals ensures that checking two scalars for equality works as
455 // expected for edge cases.
456 func TestModNScalarEquals(t *testing.T) {
457 tests := []struct {
458 name string // test description
459 in1 string // hex encoded value
460 in2 string // hex encoded value
461 expected bool // expected equality
462 }{
463 {
464 name: "0 == 0?",
465 in1: "0",
466 in2: "0",
467 expected: true,
468 }, {
469 name: "0 == 1?",
470 in1: "0",
471 in2: "1",
472 expected: false,
473 }, {
474 name: "1 == 0?",
475 in1: "1",
476 in2: "0",
477 expected: false,
478 }, {
479 name: "2^32 - 1 == 2^32 - 1?",
480 in1: "ffffffff",
481 in2: "ffffffff",
482 expected: true,
483 }, {
484 name: "2^64 - 1 == 2^64 - 2?",
485 in1: "ffffffffffffffff",
486 in2: "fffffffffffffffe",
487 expected: false,
488 }, {
489 name: "0 == group order?",
490 in1: "0",
491 in2: "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141",
492 expected: true,
493 }, {
494 name: "1 == group order + 1?",
495 in1: "1",
496 in2: "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364142",
497 expected: true,
498 },
499 }
500 for _, test := range tests {
501 s1 := new(ModNScalar).SetHex(test.in1)
502 s2 := new(ModNScalar).SetHex(test.in2)
503 result := s1.Equals(s2)
504 if result != test.expected {
505 t.Errorf(
506 "%s: wrong result -- got: %v, want: %v", test.name, result,
507 test.expected,
508 )
509 continue
510 }
511 }
512 }
513
514 // TestModNScalarEqualsRandom ensures that scalars for random values works as
515 // expected.
516 func TestModNScalarEqualsRandom(t *testing.T) {
517 // Use a unique random seed each test instance and log it if the tests fail.
518 seed := time.Now().Unix()
519 rng := rand.New(rand.NewSource(seed))
520 defer func(t *testing.T, seed int64) {
521 if t.Failed() {
522 t.Logf("random seed: %d", seed)
523 }
524 }(t, seed)
525 for i := 0; i < 100; i++ {
526 // Ensure a randomly-generated scalar equals itself.
527 s := randModNScalar(t, rng)
528 if !s.Equals(s) {
529 t.Fatalf("failed equality check\nscalar in: %v", s)
530 }
531 // Flip a random bit in a random word and ensure it's no longer equal.
532 randomWord := rng.Int31n(int32(len(s.n)))
533 randomBit := uint32(1 << uint32(rng.Int31n(32)))
534 s2 := new(ModNScalar).Set(s)
535 s2.n[randomWord] ^= randomBit
536 if s2.Equals(s) {
537 t.Fatalf("failed inequality check\nscalar in: %v", s2)
538 }
539 }
540 }
541
542 // TestModNScalarAdd ensures that adding two scalars works as expected for edge
543 // cases.
544 func TestModNScalarAdd(t *testing.T) {
545 tests := []struct {
546 name string // test description
547 in1 string // first hex encoded test value
548 in2 string // second hex encoded test value
549 expected string // expected hex encoded bytes
550 }{
551 {
552 name: "zero + one",
553 in1: "0",
554 in2: "1",
555 expected: "1",
556 }, {
557 name: "one + zero",
558 in1: "1",
559 in2: "0",
560 expected: "1",
561 }, {
562 name: "group order (aka 0) + 1 (gets reduced, no overflow)",
563 in1: "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141",
564 in2: "1",
565 expected: "1",
566 }, {
567 name: "group order - 1 + 1 (aka 0, overflow to prime)",
568 in1: "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140",
569 in2: "1",
570 expected: "0",
571 }, {
572 name: "group order - 1 + 2 (aka 1, overflow in word zero)",
573 in1: "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140",
574 in2: "2",
575 expected: "1",
576 }, {
577 name: "overflow in word one",
578 in1: "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8bd0364141",
579 in2: "100000001",
580 expected: "1",
581 }, {
582 name: "overflow in word two",
583 in1: "fffffffffffffffffffffffffffffffebaaedce6af48a03abfd25e8cd0364141",
584 in2: "10000000000000001",
585 expected: "1",
586 }, {
587 name: "overflow in word three",
588 in1: "fffffffffffffffffffffffffffffffebaaedce5af48a03bbfd25e8cd0364141",
589 in2: "1000000000000000000000001",
590 expected: "1",
591 }, {
592 name: "overflow in word four",
593 in1: "fffffffffffffffffffffffffffffffdbaaedce6af48a03bbfd25e8cd0364141",
594 in2: "100000000000000000000000000000001",
595 expected: "1",
596 }, {
597 name: "overflow in word five",
598 in1: "fffffffffffffffffffffffefffffffebaaedce6af48a03bbfd25e8cd0364141",
599 in2: "10000000000000000000000000000000000000001",
600 expected: "1",
601 }, {
602 name: "overflow in word six",
603 in1: "fffffffffffffffefffffffffffffffebaaedce6af48a03bbfd25e8cd0364141",
604 in2: "1000000000000000000000000000000000000000000000001",
605 expected: "1",
606 }, {
607 name: "overflow in word seven",
608 in1: "fffffffefffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141",
609 in2: "100000000000000000000000000000000000000000000000000000001",
610 expected: "1",
611 }, {
612 name: "alternating bits",
613 in1: "a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5",
614 in2: "5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a",
615 expected: "14551231950b75fc4402da1732fc9bebe",
616 }, {
617 name: "alternating bits 2",
618 in1: "5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a",
619 in2: "a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5",
620 expected: "14551231950b75fc4402da1732fc9bebe",
621 },
622 }
623 for _, test := range tests {
624 // Parse test hex.
625 s1 := new(ModNScalar).SetHex(test.in1)
626 s2 := new(ModNScalar).SetHex(test.in2)
627 expected := new(ModNScalar).SetHex(test.expected)
628
629 // Ensure the result has the expected value.
630 s1.Add(s2)
631 if !s1.Equals(expected) {
632 t.Errorf(
633 "%s: unexpected result\ngot: %x\nwant: %x", test.name,
634 s1, expected,
635 )
636 continue
637 }
638 }
639 }
640
641 // TestModNScalarAddRandom ensures that adding two scalars together for random
642 // values works as expected by also performing the same operation with big ints
643 // and comparing the results.
644 func TestModNScalarAddRandom(t *testing.T) {
645 // Use a unique random seed each test instance and log it if the tests fail.
646 seed := time.Now().Unix()
647 rng := rand.New(rand.NewSource(seed))
648 defer func(t *testing.T, seed int64) {
649 if t.Failed() {
650 t.Logf("random seed: %d", seed)
651 }
652 }(t, seed)
653 for i := 0; i < 100; i++ {
654 // Generate two big integer and mod n scalar pairs.
655 bigIntVal1, modNVal1 := randIntAndModNScalar(t, rng)
656 bigIntVal2, modNVal2 := randIntAndModNScalar(t, rng)
657
658 // Calculate the sum of the values using big ints.
659 bigIntResult := new(big.Int).Add(bigIntVal1, bigIntVal2)
660 bigIntResult.Mod(bigIntResult, curveParams.N)
661 // Calculate the sum of the values using mod n scalars.
662 modNValResult := new(ModNScalar).Add2(modNVal1, modNVal2)
663 // Ensure they match.
664 bigIntResultHex := fmt.Sprintf("%064x", bigIntResult)
665 modNResultHex := fmt.Sprintf("%v", modNValResult)
666 if bigIntResultHex != modNResultHex {
667 t.Fatalf(
668 "mismatched add\nbig int in 1: %x\nbig int in 2: %x\n"+
669 "scalar in 1: %v\nscalar in 2: %v\nbig int result: %x\nscalar "+
670 "result %v", bigIntVal1, bigIntVal2, modNVal1, modNVal2,
671 bigIntResult, modNValResult,
672 )
673 }
674 }
675 }
676
677 // TestAccumulator96Add ensures that the internal 96-bit accumulator used by
678 // multiplication works as expected for overflow edge cases including overflow.
679 func TestAccumulator96Add(t *testing.T) {
680 tests := []struct {
681 name string // test description
682 start accumulator96 // starting value of accumulator
683 in uint64 // value to add to accumulator
684 expected accumulator96 // expected value of accumulator after addition
685 }{
686 {
687 name: "0 + 0 = 0",
688 start: accumulator96{[3]uint32{0, 0, 0}},
689 in: 0,
690 expected: accumulator96{[3]uint32{0, 0, 0}},
691 }, {
692 name: "overflow in word zero",
693 start: accumulator96{[3]uint32{0xffffffff, 0, 0}},
694 in: 1,
695 expected: accumulator96{[3]uint32{0, 1, 0}},
696 }, {
697 name: "overflow in word one",
698 start: accumulator96{[3]uint32{0, 0xffffffff, 0}},
699 in: 0x100000000,
700 expected: accumulator96{[3]uint32{0, 0, 1}},
701 }, {
702 name: "overflow in words one and two",
703 start: accumulator96{[3]uint32{0xffffffff, 0xffffffff, 0}},
704 in: 1,
705 expected: accumulator96{[3]uint32{0, 0, 1}},
706 }, {
707 // Start accumulator at 129127208455837319175 which is the result of
708 // 4294967295 * 4294967295 accumulated seven times.
709 name: "max result from eight adds of max uint32 multiplications",
710 start: accumulator96{[3]uint32{7, 4294967282, 6}},
711 in: 18446744065119617025,
712 expected: accumulator96{[3]uint32{8, 4294967280, 7}},
713 },
714 }
715 for _, test := range tests {
716 acc := test.start
717 acc.Add(test.in)
718 if acc.n != test.expected.n {
719 t.Errorf(
720 "%s: wrong result\ngot: %v\nwant: %v", test.name, acc.n,
721 test.expected.n,
722 )
723 }
724 }
725 }
726
727 // TestModNScalarMul ensures that multiplying two scalars together works as
728 // expected for edge cases.
729 func TestModNScalarMul(t *testing.T) {
730 tests := []struct {
731 name string // test description
732 in1 string // first hex encoded value
733 in2 string // second hex encoded value to multiply with
734 expected string // expected hex encoded value
735 }{
736 {
737 name: "zero * zero",
738 in1: "0",
739 in2: "0",
740 expected: "0",
741 }, {
742 name: "one * zero",
743 in1: "1",
744 in2: "0",
745 expected: "0",
746 }, {
747 name: "one * one",
748 in1: "1",
749 in2: "1",
750 expected: "1",
751 }, {
752 name: "(group order-1) * 2",
753 in1: "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140",
754 in2: "2",
755 expected: "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd036413f",
756 }, {
757 name: "(group order-1) * (group order-1)",
758 in1: "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140",
759 in2: "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140",
760 expected: "1",
761 }, {
762 name: "slightly over group order",
763 in1: "7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1",
764 in2: "2",
765 expected: "1",
766 }, {
767 name: "group order (aka 0) * 3",
768 in1: "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141",
769 in2: "3",
770 expected: "0",
771 }, {
772 name: "overflow in word eight",
773 in1: "100000000000000000000000000000000",
774 in2: "100000000000000000000000000000000",
775 expected: "14551231950b75fc4402da1732fc9bebf",
776 }, {
777 name: "overflow in word nine",
778 in1: "1000000000000000000000000000000000000",
779 in2: "1000000000000000000000000000000000000",
780 expected: "14551231950b75fc4402da1732fc9bebf00000000",
781 }, {
782 name: "overflow in word ten",
783 in1: "10000000000000000000000000000000000000000",
784 in2: "10000000000000000000000000000000000000000",
785 expected: "14551231950b75fc4402da1732fc9bebf0000000000000000",
786 }, {
787 name: "overflow in word eleven",
788 in1: "100000000000000000000000000000000000000000000",
789 in2: "100000000000000000000000000000000000000000000",
790 expected: "14551231950b75fc4402da1732fc9bebf000000000000000000000000",
791 }, {
792 name: "overflow in word twelve",
793 in1: "1000000000000000000000000000000000000000000000000",
794 in2: "1000000000000000000000000000000000000000000000000",
795 expected: "4551231950b75fc4402da1732fc9bec04551231950b75fc4402da1732fc9bebf",
796 }, {
797 name: "overflow in word thirteen",
798 in1: "10000000000000000000000000000000000000000000000000000",
799 in2: "10000000000000000000000000000000000000000000000000000",
800 expected: "50b75fc4402da1732fc9bec09d671cd51b343a1b66926b57d2a4c1c61536bda7",
801 }, {
802 name: "overflow in word fourteen",
803 in1: "100000000000000000000000000000000000000000000000000000000",
804 in2: "100000000000000000000000000000000000000000000000000000000",
805 expected: "402da1732fc9bec09d671cd581c69bc59509b0b074ec0aea8f564d667ec7eb3c",
806 }, {
807 name: "overflow in word fifteen",
808 in1: "1000000000000000000000000000000000000000000000000000000000000",
809 in2: "1000000000000000000000000000000000000000000000000000000000000",
810 expected: "2fc9bec09d671cd581c69bc5e697f5e41f12c33a0a7b6f4e3302b92ea029cecd",
811 }, {
812 name: "double overflow in internal accumulator",
813 in1: "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140",
814 in2: "55555555555555555555555555555554e8e4f44ce51835693ff0ca2ef01215c2",
815 expected: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa9d1c9e899ca306ad27fe1945de0242b7f",
816 }, {
817 name: "alternating bits",
818 in1: "a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5",
819 in2: "5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a",
820 expected: "88edea3d29272800e7988455cfdf19b039dbfbb1c93b5b44a48c2ba462316838",
821 }, {
822 name: "alternating bits 2",
823 in1: "5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a",
824 in2: "a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5",
825 expected: "88edea3d29272800e7988455cfdf19b039dbfbb1c93b5b44a48c2ba462316838",
826 },
827 }
828 for _, test := range tests {
829 v1 := new(ModNScalar).SetHex(test.in1)
830 v2 := new(ModNScalar).SetHex(test.in2)
831 expected := new(ModNScalar).SetHex(test.expected)
832 // Ensure multiplying two other values produces the expected result.
833 result := new(ModNScalar).Mul2(v1, v2)
834 if !result.Equals(expected) {
835 t.Errorf(
836 "%s: wrong result\ngot: %v\nwant: %v", test.name, result,
837 expected,
838 )
839 continue
840 }
841 // Ensure self multiplying with another value also produces the expected
842 // result.
843 result2 := new(ModNScalar).Set(v1).Mul(v2)
844 if !result2.Equals(expected) {
845 t.Errorf(
846 "%s: wrong result\ngot: %v\nwant: %v", test.name, result2,
847 expected,
848 )
849 continue
850 }
851 }
852 }
853
854 // TestModNScalarMulRandom ensures that multiplying two scalars together for
855 // random values works as expected by also performing the same operation with
856 // big ints and comparing the results.
857 func TestModNScalarMulRandom(t *testing.T) {
858 // Use a unique random seed each test instance and log it if the tests fail.
859 seed := time.Now().Unix()
860 rng := rand.New(rand.NewSource(seed))
861 defer func(t *testing.T, seed int64) {
862 if t.Failed() {
863 t.Logf("random seed: %d", seed)
864 }
865 }(t, seed)
866 for i := 0; i < 100; i++ {
867 // Generate two big integer and mod n scalar pairs.
868 bigIntVal1, modNVal1 := randIntAndModNScalar(t, rng)
869 bigIntVal2, modNVal2 := randIntAndModNScalar(t, rng)
870 // Calculate the square of the value using big ints.
871 bigIntResult := new(big.Int).Mul(bigIntVal1, bigIntVal2)
872 bigIntResult.Mod(bigIntResult, curveParams.N)
873 // Calculate the square of the value using mod n scalar.
874 modNValResult := new(ModNScalar).Mul2(modNVal1, modNVal2)
875 // Ensure they match.
876 bigIntResultHex := fmt.Sprintf("%064x", bigIntResult)
877 modNResultHex := fmt.Sprintf("%v", modNValResult)
878 if bigIntResultHex != modNResultHex {
879 t.Fatalf(
880 "mismatched mul\nbig int in 1: %x\nbig int in 2: %x\n"+
881 "scalar in 1: %v\nscalar in 2: %v\nbig int result: %x\nscalar "+
882 "result %v", bigIntVal1, bigIntVal2, modNVal1, modNVal2,
883 bigIntResult, modNValResult,
884 )
885 }
886 }
887 }
888
889 // TestModNScalarSquare ensures that squaring scalars works as expected for edge
890 // cases.
891 func TestModNScalarSquare(t *testing.T) {
892 tests := []struct {
893 name string // test description
894 in string // hex encoded test value
895 expected string // expected hex encoded value
896 }{
897 {
898 name: "zero",
899 in: "0",
900 expected: "0",
901 }, {
902 name: "one",
903 in: "1",
904 expected: "1",
905 }, {
906 name: "over group order",
907 in: "0000000000000000000000000000000100000000000000000000000000000000",
908 expected: "000000000000000000000000000000014551231950b75fc4402da1732fc9bebf",
909 }, {
910 name: "group order - 1",
911 in: "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140",
912 expected: "0000000000000000000000000000000000000000000000000000000000000001",
913 }, {
914 name: "overflow in word eight",
915 in: "100000000000000000000000000000000",
916 expected: "14551231950b75fc4402da1732fc9bebf",
917 }, {
918 name: "overflow in word nine",
919 in: "1000000000000000000000000000000000000",
920 expected: "14551231950b75fc4402da1732fc9bebf00000000",
921 }, {
922 name: "overflow in word ten",
923 in: "10000000000000000000000000000000000000000",
924 expected: "14551231950b75fc4402da1732fc9bebf0000000000000000",
925 }, {
926 name: "overflow in word eleven",
927 in: "100000000000000000000000000000000000000000000",
928 expected: "14551231950b75fc4402da1732fc9bebf000000000000000000000000",
929 }, {
930 name: "overflow in word twelve",
931 in: "1000000000000000000000000000000000000000000000000",
932 expected: "4551231950b75fc4402da1732fc9bec04551231950b75fc4402da1732fc9bebf",
933 }, {
934 name: "overflow in word thirteen",
935 in: "10000000000000000000000000000000000000000000000000000",
936 expected: "50b75fc4402da1732fc9bec09d671cd51b343a1b66926b57d2a4c1c61536bda7",
937 }, {
938 name: "overflow in word fourteen",
939 in: "100000000000000000000000000000000000000000000000000000000",
940 expected: "402da1732fc9bec09d671cd581c69bc59509b0b074ec0aea8f564d667ec7eb3c",
941 }, {
942 name: "overflow in word fifteen",
943 in: "1000000000000000000000000000000000000000000000000000000000000",
944 expected: "2fc9bec09d671cd581c69bc5e697f5e41f12c33a0a7b6f4e3302b92ea029cecd",
945 }, {
946 name: "alternating bits",
947 in: "a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5",
948 expected: "fb0982c5761d1eac534247f2a7c3af186a134d709b977ca88300faad5eafe9bc",
949 }, {
950 name: "alternating bits 2",
951 in: "5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a",
952 expected: "9081c595b95b2d17c424a546144b25488104c5889d914635bc9d1a51859e1c19",
953 },
954 }
955 for _, test := range tests {
956 v := new(ModNScalar).SetHex(test.in)
957 expected := new(ModNScalar).SetHex(test.expected)
958 // Ensure squaring another value produces the expected result.
959 result := new(ModNScalar).SquareVal(v)
960 if !result.Equals(expected) {
961 t.Errorf(
962 "%s: wrong result\ngot: %v\nwant: %v", test.name, result,
963 expected,
964 )
965 continue
966 }
967 // Ensure self squaring also produces the expected result.
968 result2 := new(ModNScalar).Set(v).Square()
969 if !result2.Equals(expected) {
970 t.Errorf(
971 "%s: wrong result\ngot: %v\nwant: %v", test.name, result2,
972 expected,
973 )
974 continue
975 }
976 }
977 }
978
979 // TestModNScalarSquareRandom ensures that squaring scalars for random values
980 // works as expected by also performing the same operation with big ints and
981 // comparing the results.
982 func TestModNScalarSquareRandom(t *testing.T) {
983 // Use a unique random seed each test instance and log it if the tests fail.
984 seed := time.Now().Unix()
985 rng := rand.New(rand.NewSource(seed))
986 defer func(t *testing.T, seed int64) {
987 if t.Failed() {
988 t.Logf("random seed: %d", seed)
989 }
990 }(t, seed)
991 for i := 0; i < 100; i++ {
992 // Generate big integer and mod n scalar with the same random value.
993 bigIntVal, modNVal := randIntAndModNScalar(t, rng)
994 // Calculate the square of the value using big ints.
995 bigIntResult := new(big.Int).Mul(bigIntVal, bigIntVal)
996 bigIntResult.Mod(bigIntResult, curveParams.N)
997 // Calculate the square of the value using mod n scalar.
998 modNValResult := new(ModNScalar).SquareVal(modNVal)
999 // Ensure they match.
1000 bigIntResultHex := fmt.Sprintf("%064x", bigIntResult)
1001 modNResultHex := fmt.Sprintf("%v", modNValResult)
1002 if bigIntResultHex != modNResultHex {
1003 t.Fatalf(
1004 "mismatched square\nbig int in: %x\nscalar in: %v\n"+
1005 "big int result: %x\nscalar result %v", bigIntVal, modNVal,
1006 bigIntResult, modNValResult,
1007 )
1008 }
1009 }
1010 }
1011
1012 // TestModNScalarNegate ensures that negating scalars works as expected for edge
1013 // cases.
1014 func TestModNScalarNegate(t *testing.T) {
1015 tests := []struct {
1016 name string // test description
1017 in string // hex encoded test value
1018 expected string // hex encoded expected result
1019 }{
1020 {
1021 name: "zero",
1022 in: "0",
1023 expected: "0",
1024 }, {
1025 name: "one",
1026 in: "1",
1027 expected: "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140",
1028 }, {
1029 name: "negation in word one",
1030 in: "0000000000000000000000000000000000000000000000000000000100000000",
1031 expected: "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8bd0364141",
1032 }, {
1033 name: "negation in word two",
1034 in: "0000000000000000000000000000000000000000000000010000000000000000",
1035 expected: "fffffffffffffffffffffffffffffffebaaedce6af48a03abfd25e8cd0364141",
1036 }, {
1037 name: "negation in word three",
1038 in: "0000000000000000000000000000000000000001000000000000000000000000",
1039 expected: "fffffffffffffffffffffffffffffffebaaedce5af48a03bbfd25e8cd0364141",
1040 }, {
1041 name: "negation in word four",
1042 in: "0000000000000000000000000000000100000000000000000000000000000000",
1043 expected: "fffffffffffffffffffffffffffffffdbaaedce6af48a03bbfd25e8cd0364141",
1044 }, {
1045 name: "negation in word five",
1046 in: "0000000000000000000000010000000000000000000000000000000000000000",
1047 expected: "fffffffffffffffffffffffefffffffebaaedce6af48a03bbfd25e8cd0364141",
1048 }, {
1049 name: "negation in word six",
1050 in: "0000000000000001000000000000000000000000000000000000000000000000",
1051 expected: "fffffffffffffffefffffffffffffffebaaedce6af48a03bbfd25e8cd0364141",
1052 }, {
1053 name: "negation in word seven",
1054 in: "0000000100000000000000000000000000000000000000000000000000000000",
1055 expected: "fffffffefffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141",
1056 }, {
1057 name: "alternating bits",
1058 in: "a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5",
1059 expected: "5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a591509374109a2fa961a2cb8e72a909b9c",
1060 }, {
1061 name: "alternating bits 2",
1062 in: "5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a",
1063 expected: "a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a46054828c54ee45e16578043275dbe6e7",
1064 },
1065 }
1066 for _, test := range tests {
1067 s := new(ModNScalar).SetHex(test.in)
1068 expected := new(ModNScalar).SetHex(test.expected)
1069 // Ensure negating another value produces the expected result.
1070 result := new(ModNScalar).NegateVal(s)
1071 if !result.Equals(expected) {
1072 t.Errorf(
1073 "%s: unexpected result -- got: %v, want: %v", test.name,
1074 result, expected,
1075 )
1076 continue
1077 }
1078 // Ensure self negating also produces the expected result.
1079 result2 := new(ModNScalar).Set(s).Negate()
1080 if !result2.Equals(expected) {
1081 t.Errorf(
1082 "%s: unexpected result -- got: %v, want: %v", test.name,
1083 result2, expected,
1084 )
1085 continue
1086 }
1087 }
1088 }
1089
1090 // TestModNScalarNegateRandom ensures that negating scalars for random values
1091 // works as expected by also performing the same operation with big ints and
1092 // comparing the results.
1093 func TestModNScalarNegateRandom(t *testing.T) {
1094 // Use a unique random seed each test instance and log it if the tests fail.
1095 seed := time.Now().Unix()
1096 rng := rand.New(rand.NewSource(seed))
1097 defer func(t *testing.T, seed int64) {
1098 if t.Failed() {
1099 t.Logf("random seed: %d", seed)
1100 }
1101 }(t, seed)
1102 for i := 0; i < 100; i++ {
1103 // Generate big integer and mod n scalar with the same random value.
1104 bigIntVal, modNVal := randIntAndModNScalar(t, rng)
1105 // Calculate the negation of the value using big ints.
1106 bigIntResult := new(big.Int).Neg(bigIntVal)
1107 bigIntResult.Mod(bigIntResult, curveParams.N)
1108 // Calculate the negation of the value using mod n scalar.
1109 modNValResult := new(ModNScalar).NegateVal(modNVal)
1110 // Ensure they match.
1111 bigIntResultHex := fmt.Sprintf("%064x", bigIntResult)
1112 modNResultHex := fmt.Sprintf("%v", modNValResult)
1113 if bigIntResultHex != modNResultHex {
1114 t.Fatalf(
1115 "mismatched negate\nbig int in: %x\nscalar in: %v\n"+
1116 "big int result: %x\nscalar result %v", bigIntVal, modNVal,
1117 bigIntResult, modNValResult,
1118 )
1119 }
1120 }
1121 }
1122
1123 // TestModNScalarInverseNonConst ensures that calculating the multiplicative
1124 // inverse of scalars in *non-constant* time works as expected for edge cases.
1125 func TestModNScalarInverseNonConst(t *testing.T) {
1126 tests := []struct {
1127 name string // test description
1128 in string // hex encoded test value
1129 expected string // hex encoded expected result
1130 }{
1131 {
1132 name: "zero",
1133 in: "0",
1134 expected: "0",
1135 }, {
1136 name: "one",
1137 in: "1",
1138 expected: "1",
1139 }, {
1140 name: "inverse carry in word one",
1141 in: "0000000000000000000000000000000000000000000000000000000100000000",
1142 expected: "5588b13effffffffffffffffffffffff934e5b00ca8417bf50177f7ba415411a",
1143 }, {
1144 name: "inverse carry in word two",
1145 in: "0000000000000000000000000000000000000000000000010000000000000000",
1146 expected: "4b0dff665588b13effffffffffffffffa09f710af01555259d4ad302583de6dc",
1147 }, {
1148 name: "inverse carry in word three",
1149 in: "0000000000000000000000000000000000000001000000000000000000000000",
1150 expected: "34b9ec244b0dff665588b13effffffffbcff4127932a971a78274c9d74176b38",
1151 }, {
1152 name: "inverse carry in word four",
1153 in: "0000000000000000000000000000000100000000000000000000000000000000",
1154 expected: "50a51ac834b9ec244b0dff665588b13e9984d5b3cf80ef0fd6a23766a3ee9f22",
1155 }, {
1156 name: "inverse carry in word five",
1157 in: "0000000000000000000000010000000000000000000000000000000000000000",
1158 expected: "27cfab5e50a51ac834b9ec244b0dff6622f16e85b683d5a059bcd5a3b29d9dff",
1159 }, {
1160 name: "inverse carry in word six",
1161 in: "0000000000000001000000000000000000000000000000000000000000000000",
1162 expected: "897f30c127cfab5e50a51ac834b9ec239c53f268b4700c14f19b9499ac58d8ad",
1163 }, {
1164 name: "inverse carry in word seven",
1165 in: "0000000100000000000000000000000000000000000000000000000000000000",
1166 expected: "6494ef93897f30c127cfab5e50a51ac7b4e8f713e0cddd182234e907286ae6b3",
1167 }, {
1168 name: "alternating bits",
1169 in: "a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5",
1170 expected: "cb6086e560b8597a85c934e46f5b6e8a445bf3f0a88e4160d7fa8d83fd10338d",
1171 }, {
1172 name: "alternating bits 2",
1173 in: "5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a",
1174 expected: "9f864ca486a74eb5f546364d76d24aa93716dc78f84847aa6c1c09fca2707d77",
1175 },
1176 }
1177 for _, test := range tests {
1178 s := new(ModNScalar).SetHex(test.in)
1179 expected := new(ModNScalar).SetHex(test.expected)
1180 // Ensure calculating the multiplicative inverse of another value
1181 // produces the expected result.
1182 result := new(ModNScalar).InverseValNonConst(s)
1183 if !result.Equals(expected) {
1184 t.Errorf(
1185 "%s: unexpected result -- got: %v, want: %v", test.name,
1186 result, expected,
1187 )
1188 continue
1189 }
1190 // Ensure calculating the multiplicative inverse in place also produces
1191 // the expected result.
1192 result2 := new(ModNScalar).Set(s).InverseNonConst()
1193 if !result2.Equals(expected) {
1194 t.Errorf(
1195 "%s: unexpected result -- got: %v, want: %v", test.name,
1196 result2, expected,
1197 )
1198 continue
1199 }
1200 }
1201 }
1202
1203 // TestModNScalarInverseNonConstRandom ensures that calculating the
1204 // multiplicative inverse of scalars in *non-constant* time for random values
1205 // works as expected by also performing the same operation with big ints and
1206 // comparing the results.
1207 func TestModNScalarInverseNonConstRandom(t *testing.T) {
1208 // Use a unique random seed each test instance and log it if the tests fail.
1209 seed := time.Now().Unix()
1210 rng := rand.New(rand.NewSource(seed))
1211 defer func(t *testing.T, seed int64) {
1212 if t.Failed() {
1213 t.Logf("random seed: %d", seed)
1214 }
1215 }(t, seed)
1216 for i := 0; i < 100; i++ {
1217 // Generate big integer and mod n scalar with the same random value.
1218 bigIntVal, modNVal := randIntAndModNScalar(t, rng)
1219 // Calculate the inverse of the value using big ints.
1220 bigIntResult := new(big.Int).ModInverse(bigIntVal, curveParams.N)
1221 // Calculate the inverse of the value using a mod n scalar.
1222 modNValResult := new(ModNScalar).InverseValNonConst(modNVal)
1223 // Ensure they match.
1224 bigIntResultHex := fmt.Sprintf("%064x", bigIntResult)
1225 modNResultHex := fmt.Sprintf("%v", modNValResult)
1226 if bigIntResultHex != modNResultHex {
1227 t.Fatalf(
1228 "mismatched inverse\nbig int in: %x\nscalar in: %v\n"+
1229 "big int result: %x\nscalar result %v", bigIntVal, modNVal,
1230 bigIntResult, modNValResult,
1231 )
1232 }
1233 }
1234 }
1235
1236 // TestModNScalarIsOverHalfOrder ensures that scalars report whether or not they
1237 // exceeed the half order works as expected for edge cases.
1238 func TestModNScalarIsOverHalfOrder(t *testing.T) {
1239 tests := []struct {
1240 name string // test description
1241 in string // hex encoded test value
1242 expected bool // expected result
1243 }{
1244 {
1245 name: "zero",
1246 in: "0",
1247 expected: false,
1248 }, {
1249 name: "one",
1250 in: "1",
1251 expected: false,
1252 }, {
1253 name: "group half order - 1",
1254 in: "7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b209f",
1255 expected: false,
1256 }, {
1257 name: "group half order",
1258 in: "7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0",
1259 expected: false,
1260 }, {
1261 name: "group half order + 1",
1262 in: "7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1",
1263 expected: true,
1264 }, {
1265 name: "over half order word one",
1266 in: "7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f47681b20a0",
1267 expected: true,
1268 }, {
1269 name: "over half order word two",
1270 in: "7fffffffffffffffffffffffffffffff5d576e7357a4501edfe92f46681b20a0",
1271 expected: true,
1272 }, {
1273 name: "over half order word three",
1274 in: "7fffffffffffffffffffffffffffffff5d576e7457a4501ddfe92f46681b20a0",
1275 expected: true,
1276 }, {
1277 name: "over half order word seven",
1278 in: "8fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0",
1279 expected: true,
1280 },
1281 }
1282 for _, test := range tests {
1283 result := new(ModNScalar).SetHex(test.in).IsOverHalfOrder()
1284 if result != test.expected {
1285 t.Errorf(
1286 "%s: unexpected result -- got: %v, want: %v", test.name,
1287 result, test.expected,
1288 )
1289 continue
1290 }
1291 }
1292 }
1293
1294 // TestModNScalarIsOverHalfOrderRandom ensures that scalars report whether or
1295 // not they exceeed the half order for random values works as expected by also
1296 // performing the same operation with big ints and comparing the results.
1297 func TestModNScalarIsOverHalfOrderRandom(t *testing.T) {
1298 // Use a unique random seed each test instance and log it if the tests fail.
1299 seed := time.Now().Unix()
1300 rng := rand.New(rand.NewSource(seed))
1301 defer func(t *testing.T, seed int64) {
1302 if t.Failed() {
1303 t.Logf("random seed: %d", seed)
1304 }
1305 }(t, seed)
1306 bigHalfOrder := new(big.Int).Rsh(curveParams.N, 1)
1307 for i := 0; i < 100; i++ {
1308 // Generate big integer and mod n scalar with the same random value.
1309 bigIntVal, modNVal := randIntAndModNScalar(t, rng)
1310 // Determine the value exceeds the half order using big ints.
1311 bigIntResult := bigIntVal.Cmp(bigHalfOrder) > 0
1312 // Determine the value exceeds the half order using a mod n scalar.
1313 modNValResult := modNVal.IsOverHalfOrder()
1314 // Ensure they match.
1315 if bigIntResult != modNValResult {
1316 t.Fatalf(
1317 "mismatched is over half order\nbig int in: %x\nscalar "+
1318 "in: %v\nbig int result: %v\nscalar result %v", bigIntVal,
1319 modNVal, bigIntResult, modNValResult,
1320 )
1321 }
1322 }
1323 }
1324