Source file src/github.com/decred/dcrd/dcrec/secp256k1/v4/modnscalar_test.go

Documentation: github.com/decred/dcrd/dcrec/secp256k1/v4

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

View as plain text