scalar_test.go

     1  // Copyright (c) 2019 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package edwards25519
     6  
     7  import (
     8  	"bytes"
     9  	"encoding/hex"
    10  	"math/big"
    11  	mathrand "math/rand"
    12  	"reflect"
    13  	"testing"
    14  	"testing/quick"
    15  )
    16  
    17  // quickCheckConfig returns a quick.Config that scales the max count by the
    18  // given factor if the -short flag is not set.
    19  func quickCheckConfig(slowScale int) *quick.Config {
    20  	cfg := new(quick.Config)
    21  	if !testing.Short() {
    22  		cfg.MaxCountScale = float64(slowScale)
    23  	}
    24  	return cfg
    25  }
    26  
    27  var scOneBytes = [32]byte{1}
    28  var scOne, _ = new(Scalar).SetCanonicalBytes(scOneBytes[:])
    29  var scMinusOne = new(Scalar).Subtract(new(Scalar), scOne)
    30  
    31  // Generate returns a valid (reduced modulo l) Scalar with a distribution
    32  // weighted towards high, low, and edge values.
    33  func (Scalar) Generate(rand *mathrand.Rand, size int) reflect.Value {
    34  	var s [32]byte
    35  	diceRoll := rand.Intn(100)
    36  	switch {
    37  	case diceRoll == 0:
    38  	case diceRoll == 1:
    39  		s = scOneBytes
    40  	case diceRoll == 2:
    41  		s = [32]byte(scMinusOne.Bytes())
    42  	case diceRoll < 5:
    43  		// Generate a low scalar in [0, 2^125).
    44  		rand.Read(s[:16])
    45  		s[15] &= (1 << 5) - 1
    46  	case diceRoll < 10:
    47  		// Generate a high scalar in [2^252, 2^252 + 2^124).
    48  		s[31] = 1 << 4
    49  		rand.Read(s[:16])
    50  		s[15] &= (1 << 4) - 1
    51  	default:
    52  		// Generate a valid scalar in [0, l) by returning [0, 2^252) which has a
    53  		// negligibly different distribution (the former has a 2^-127.6 chance
    54  		// of being out of the latter range).
    55  		rand.Read(s[:])
    56  		s[31] &= (1 << 4) - 1
    57  	}
    58  
    59  	val := Scalar{}
    60  	fiatScalarFromBytes((*[4]uint64)(&val.s), &s)
    61  	fiatScalarToMontgomery(&val.s, (*fiatScalarNonMontgomeryDomainFieldElement)(&val.s))
    62  
    63  	return reflect.ValueOf(val)
    64  }
    65  
    66  func TestScalarGenerate(t *testing.T) {
    67  	f := func(sc Scalar) bool {
    68  		return isReduced(sc.Bytes())
    69  	}
    70  	if err := quick.Check(f, quickCheckConfig(1024)); err != nil {
    71  		t.Errorf("generated unreduced scalar: %v", err)
    72  	}
    73  }
    74  
    75  func TestScalarSetCanonicalBytes(t *testing.T) {
    76  	f1 := func(in [32]byte, sc Scalar) bool {
    77  		// Mask out top 4 bits to guarantee value falls in [0, l).
    78  		in[len(in)-1] &= (1 << 4) - 1
    79  		if _, err := sc.SetCanonicalBytes(in[:]); err != nil {
    80  			return false
    81  		}
    82  		repr := sc.Bytes()
    83  		return bytes.Equal(in[:], repr) && isReduced(repr)
    84  	}
    85  	if err := quick.Check(f1, quickCheckConfig(1024)); err != nil {
    86  		t.Errorf("failed bytes->scalar->bytes round-trip: %v", err)
    87  	}
    88  
    89  	f2 := func(sc1, sc2 Scalar) bool {
    90  		if _, err := sc2.SetCanonicalBytes(sc1.Bytes()); err != nil {
    91  			return false
    92  		}
    93  		return sc1 == sc2
    94  	}
    95  	if err := quick.Check(f2, quickCheckConfig(1024)); err != nil {
    96  		t.Errorf("failed scalar->bytes->scalar round-trip: %v", err)
    97  	}
    98  
    99  	expectReject := func(b []byte) {
   100  		t.Helper()
   101  		s := scOne
   102  		if out, err := s.SetCanonicalBytes(b[:]); err == nil {
   103  			t.Errorf("SetCanonicalBytes worked on a non-canonical value")
   104  		} else if s != scOne {
   105  			t.Errorf("SetCanonicalBytes modified its receiver")
   106  		} else if out != nil {
   107  			t.Errorf("SetCanonicalBytes did not return nil with an error")
   108  		}
   109  	}
   110  
   111  	b := scMinusOne.Bytes()
   112  	b[0] += 1
   113  	expectReject(b)
   114  
   115  	b = scMinusOne.Bytes()
   116  	b[31] += 1
   117  	expectReject(b)
   118  
   119  	b = scMinusOne.Bytes()
   120  	b[31] |= 0b1000_0000
   121  	expectReject(b)
   122  }
   123  
   124  func TestScalarSetUniformBytes(t *testing.T) {
   125  	mod, _ := new(big.Int).SetString("27742317777372353535851937790883648493", 10)
   126  	mod.Add(mod, new(big.Int).Lsh(big.NewInt(1), 252))
   127  	f := func(in [64]byte, sc Scalar) bool {
   128  		sc.SetUniformBytes(in[:])
   129  		repr := sc.Bytes()
   130  		if !isReduced(repr) {
   131  			return false
   132  		}
   133  		scBig := bigIntFromLittleEndianBytes(repr[:])
   134  		inBig := bigIntFromLittleEndianBytes(in[:])
   135  		return inBig.Mod(inBig, mod).Cmp(scBig) == 0
   136  	}
   137  	if err := quick.Check(f, quickCheckConfig(1024)); err != nil {
   138  		t.Error(err)
   139  	}
   140  }
   141  
   142  func TestScalarSetBytesWithClamping(t *testing.T) {
   143  	// Generated with libsodium.js 1.0.18 crypto_scalarmult_ed25519_base.
   144  
   145  	random := "633d368491364dc9cd4c1bf891b1d59460face1644813240a313e61f2c88216e"
   146  	s, _ := new(Scalar).SetBytesWithClamping(decodeHex(random))
   147  	p := new(Point).ScalarBaseMult(s)
   148  	want := "1d87a9026fd0126a5736fe1628c95dd419172b5b618457e041c9c861b2494a94"
   149  	if got := hex.EncodeToString(p.Bytes()); got != want {
   150  		t.Errorf("random: got %q, want %q", got, want)
   151  	}
   152  
   153  	zero := "0000000000000000000000000000000000000000000000000000000000000000"
   154  	s, _ = new(Scalar).SetBytesWithClamping(decodeHex(zero))
   155  	p = new(Point).ScalarBaseMult(s)
   156  	want = "693e47972caf527c7883ad1b39822f026f47db2ab0e1919955b8993aa04411d1"
   157  	if got := hex.EncodeToString(p.Bytes()); got != want {
   158  		t.Errorf("zero: got %q, want %q", got, want)
   159  	}
   160  
   161  	one := "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
   162  	s, _ = new(Scalar).SetBytesWithClamping(decodeHex(one))
   163  	p = new(Point).ScalarBaseMult(s)
   164  	want = "12e9a68b73fd5aacdbcaf3e88c46fea6ebedb1aa84eed1842f07f8edab65e3a7"
   165  	if got := hex.EncodeToString(p.Bytes()); got != want {
   166  		t.Errorf("one: got %q, want %q", got, want)
   167  	}
   168  }
   169  
   170  func bigIntFromLittleEndianBytes(b []byte) *big.Int {
   171  	bb := make([]byte, len(b))
   172  	for i := range b {
   173  		bb[i] = b[len(b)-i-1]
   174  	}
   175  	return new(big.Int).SetBytes(bb)
   176  }
   177  
   178  func TestScalarMultiplyDistributesOverAdd(t *testing.T) {
   179  	multiplyDistributesOverAdd := func(x, y, z Scalar) bool {
   180  		// Compute t1 = (x+y)*z
   181  		var t1 Scalar
   182  		t1.Add(&x, &y)
   183  		t1.Multiply(&t1, &z)
   184  
   185  		// Compute t2 = x*z + y*z
   186  		var t2 Scalar
   187  		var t3 Scalar
   188  		t2.Multiply(&x, &z)
   189  		t3.Multiply(&y, &z)
   190  		t2.Add(&t2, &t3)
   191  
   192  		reprT1, reprT2 := t1.Bytes(), t2.Bytes()
   193  
   194  		return t1 == t2 && isReduced(reprT1) && isReduced(reprT2)
   195  	}
   196  
   197  	if err := quick.Check(multiplyDistributesOverAdd, quickCheckConfig(1024)); err != nil {
   198  		t.Error(err)
   199  	}
   200  }
   201  
   202  func TestScalarAddLikeSubNeg(t *testing.T) {
   203  	addLikeSubNeg := func(x, y Scalar) bool {
   204  		// Compute t1 = x - y
   205  		var t1 Scalar
   206  		t1.Subtract(&x, &y)
   207  
   208  		// Compute t2 = -y + x
   209  		var t2 Scalar
   210  		t2.Negate(&y)
   211  		t2.Add(&t2, &x)
   212  
   213  		return t1 == t2 && isReduced(t1.Bytes())
   214  	}
   215  
   216  	if err := quick.Check(addLikeSubNeg, quickCheckConfig(1024)); err != nil {
   217  		t.Error(err)
   218  	}
   219  }
   220  
   221  func TestScalarNonAdjacentForm(t *testing.T) {
   222  	s, _ := (&Scalar{}).SetCanonicalBytes([]byte{
   223  		0x1a, 0x0e, 0x97, 0x8a, 0x90, 0xf6, 0x62, 0x2d,
   224  		0x37, 0x47, 0x02, 0x3f, 0x8a, 0xd8, 0x26, 0x4d,
   225  		0xa7, 0x58, 0xaa, 0x1b, 0x88, 0xe0, 0x40, 0xd1,
   226  		0x58, 0x9e, 0x7b, 0x7f, 0x23, 0x76, 0xef, 0x09,
   227  	})
   228  
   229  	expectedNaf := [256]int8{
   230  		0, 13, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, -9, 0, 0, 0, 0, -11, 0, 0, 0, 0, 3, 0, 0, 0, 0, 1,
   231  		0, 0, 0, 0, 9, 0, 0, 0, 0, -5, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 11, 0, 0, 0, 0, 11, 0, 0, 0, 0, 0,
   232  		-9, 0, 0, 0, 0, 0, -3, 0, 0, 0, 0, 9, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 9, 0,
   233  		0, 0, 0, -15, 0, 0, 0, 0, -7, 0, 0, 0, 0, -9, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 13, 0, 0, 0, 0, 0, -3, 0,
   234  		0, 0, 0, -11, 0, 0, 0, 0, -7, 0, 0, 0, 0, -13, 0, 0, 0, 0, 11, 0, 0, 0, 0, -9, 0, 0, 0, 0, 0, 1, 0, 0,
   235  		0, 0, 0, -15, 0, 0, 0, 0, 1, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 13, 0, 0, 0,
   236  		0, 0, 0, 11, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0, -9, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 7,
   237  		0, 0, 0, 0, 0, -15, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 15, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0,
   238  	}
   239  
   240  	sNaf := s.nonAdjacentForm(5)
   241  
   242  	for i := 0; i < 256; i++ {
   243  		if expectedNaf[i] != sNaf[i] {
   244  			t.Errorf("Wrong digit at position %d, got %d, expected %d", i, sNaf[i], expectedNaf[i])
   245  		}
   246  	}
   247  }
   248  
   249  type notZeroScalar Scalar
   250  
   251  func (notZeroScalar) Generate(rand *mathrand.Rand, size int) reflect.Value {
   252  	var s Scalar
   253  	var isNonZero uint64
   254  	for isNonZero == 0 {
   255  		s = Scalar{}.Generate(rand, size).Interface().(Scalar)
   256  		fiatScalarNonzero(&isNonZero, (*[4]uint64)(&s.s))
   257  	}
   258  	return reflect.ValueOf(notZeroScalar(s))
   259  }
   260  
   261  func TestScalarEqual(t *testing.T) {
   262  	if scOne.Equal(scMinusOne) == 1 {
   263  		t.Errorf("scOne.Equal(&scMinusOne) is true")
   264  	}
   265  	if scMinusOne.Equal(scMinusOne) == 0 {
   266  		t.Errorf("scMinusOne.Equal(&scMinusOne) is false")
   267  	}
   268  }
   269
View as plain text