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