scalarmult_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  	"testing"
     9  	"testing/quick"
    10  )
    11  
    12  var (
    13  	// quickCheckConfig32 will make each quickcheck test run (32 * -quickchecks)
    14  	// times. The default value of -quickchecks is 100.
    15  	quickCheckConfig32 = &quick.Config{MaxCountScale: 1 << 5}
    16  
    17  	// a random scalar generated using dalek.
    18  	dalekScalar = Scalar{[32]byte{219, 106, 114, 9, 174, 249, 155, 89, 69, 203, 201, 93, 92, 116, 234, 187, 78, 115, 103, 172, 182, 98, 62, 103, 187, 136, 13, 100, 248, 110, 12, 4}}
    19  	// the above, times the edwards25519 basepoint.
    20  	dalekScalarBasepoint, _ = new(Point).SetBytes([]byte{0xf4, 0xef, 0x7c, 0xa, 0x34, 0x55, 0x7b, 0x9f, 0x72, 0x3b, 0xb6, 0x1e, 0xf9, 0x46, 0x9, 0x91, 0x1c, 0xb9, 0xc0, 0x6c, 0x17, 0x28, 0x2d, 0x8b, 0x43, 0x2b, 0x5, 0x18, 0x6a, 0x54, 0x3e, 0x48})
    21  )
    22  
    23  func TestScalarMultSmallScalars(t *testing.T) {
    24  	var z Scalar
    25  	var p Point
    26  	p.ScalarMult(&z, B)
    27  	if I.Equal(&p) != 1 {
    28  		t.Error("0*B != 0")
    29  	}
    30  	checkOnCurve(t, &p)
    31  
    32  	z = Scalar{[32]byte{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}}
    33  	p.ScalarMult(&z, B)
    34  	if B.Equal(&p) != 1 {
    35  		t.Error("1*B != 1")
    36  	}
    37  	checkOnCurve(t, &p)
    38  }
    39  
    40  func TestScalarMultVsDalek(t *testing.T) {
    41  	var p Point
    42  	p.ScalarMult(&dalekScalar, B)
    43  	if dalekScalarBasepoint.Equal(&p) != 1 {
    44  		t.Error("Scalar mul does not match dalek")
    45  	}
    46  	checkOnCurve(t, &p)
    47  }
    48  
    49  func TestBaseMultVsDalek(t *testing.T) {
    50  	var p Point
    51  	p.ScalarBaseMult(&dalekScalar)
    52  	if dalekScalarBasepoint.Equal(&p) != 1 {
    53  		t.Error("Scalar mul does not match dalek")
    54  	}
    55  	checkOnCurve(t, &p)
    56  }
    57  
    58  func TestVarTimeDoubleBaseMultVsDalek(t *testing.T) {
    59  	var p Point
    60  	var z Scalar
    61  	p.VarTimeDoubleScalarBaseMult(&dalekScalar, B, &z)
    62  	if dalekScalarBasepoint.Equal(&p) != 1 {
    63  		t.Error("VarTimeDoubleScalarBaseMult fails with b=0")
    64  	}
    65  	checkOnCurve(t, &p)
    66  	p.VarTimeDoubleScalarBaseMult(&z, B, &dalekScalar)
    67  	if dalekScalarBasepoint.Equal(&p) != 1 {
    68  		t.Error("VarTimeDoubleScalarBaseMult fails with a=0")
    69  	}
    70  	checkOnCurve(t, &p)
    71  }
    72  
    73  func TestScalarMultDistributesOverAdd(t *testing.T) {
    74  	scalarMultDistributesOverAdd := func(x, y Scalar) bool {
    75  		var z Scalar
    76  		z.Add(&x, &y)
    77  		var p, q, r, check Point
    78  		p.ScalarMult(&x, B)
    79  		q.ScalarMult(&y, B)
    80  		r.ScalarMult(&z, B)
    81  		check.Add(&p, &q)
    82  		checkOnCurve(t, &p, &q, &r, &check)
    83  		return check.Equal(&r) == 1
    84  	}
    85  
    86  	if err := quick.Check(scalarMultDistributesOverAdd, quickCheckConfig32); err != nil {
    87  		t.Error(err)
    88  	}
    89  }
    90  
    91  func TestScalarMultNonIdentityPoint(t *testing.T) {
    92  	// Check whether p.ScalarMult and q.ScalaBaseMult give the same,
    93  	// when p and q are originally set to the base point.
    94  
    95  	scalarMultNonIdentityPoint := func(x Scalar) bool {
    96  		var p, q Point
    97  		p.Set(B)
    98  		q.Set(B)
    99  
   100  		p.ScalarMult(&x, B)
   101  		q.ScalarBaseMult(&x)
   102  
   103  		checkOnCurve(t, &p, &q)
   104  
   105  		return p.Equal(&q) == 1
   106  	}
   107  
   108  	if err := quick.Check(scalarMultNonIdentityPoint, quickCheckConfig32); err != nil {
   109  		t.Error(err)
   110  	}
   111  }
   112  
   113  func TestBasepointTableGeneration(t *testing.T) {
   114  	// The basepoint table is 32 affineLookupTables,
   115  	// corresponding to (16^2i)*B for table i.
   116  	basepointTable := basepointTable()
   117  
   118  	tmp1 := &projP1xP1{}
   119  	tmp2 := &projP2{}
   120  	tmp3 := &Point{}
   121  	tmp3.Set(B)
   122  	table := make([]affineLookupTable, 32)
   123  	for i := 0; i < 32; i++ {
   124  		// Build the table
   125  		table[i].FromP3(tmp3)
   126  		// Assert equality with the hardcoded one
   127  		if table[i] != basepointTable[i] {
   128  			t.Errorf("Basepoint table %d does not match", i)
   129  		}
   130  
   131  		// Set p = (16^2)*p = 256*p = 2^8*p
   132  		tmp2.FromP3(tmp3)
   133  		for j := 0; j < 7; j++ {
   134  			tmp1.Double(tmp2)
   135  			tmp2.FromP1xP1(tmp1)
   136  		}
   137  		tmp1.Double(tmp2)
   138  		tmp3.fromP1xP1(tmp1)
   139  		checkOnCurve(t, tmp3)
   140  	}
   141  }
   142  
   143  func TestScalarMultMatchesBaseMult(t *testing.T) {
   144  	scalarMultMatchesBaseMult := func(x Scalar) bool {
   145  		var p, q Point
   146  		p.ScalarMult(&x, B)
   147  		q.ScalarBaseMult(&x)
   148  		checkOnCurve(t, &p, &q)
   149  		return p.Equal(&q) == 1
   150  	}
   151  
   152  	if err := quick.Check(scalarMultMatchesBaseMult, quickCheckConfig32); err != nil {
   153  		t.Error(err)
   154  	}
   155  }
   156  
   157  func TestBasepointNafTableGeneration(t *testing.T) {
   158  	var table nafLookupTable8
   159  	table.FromP3(B)
   160  
   161  	if table != *basepointNafTable() {
   162  		t.Error("BasepointNafTable does not match")
   163  	}
   164  }
   165  
   166  func TestVarTimeDoubleBaseMultMatchesBaseMult(t *testing.T) {
   167  	varTimeDoubleBaseMultMatchesBaseMult := func(x, y Scalar) bool {
   168  		var p, q1, q2, check Point
   169  
   170  		p.VarTimeDoubleScalarBaseMult(&x, B, &y)
   171  
   172  		q1.ScalarBaseMult(&x)
   173  		q2.ScalarBaseMult(&y)
   174  		check.Add(&q1, &q2)
   175  
   176  		checkOnCurve(t, &p, &check, &q1, &q2)
   177  		return p.Equal(&check) == 1
   178  	}
   179  
   180  	if err := quick.Check(varTimeDoubleBaseMultMatchesBaseMult, quickCheckConfig32); err != nil {
   181  		t.Error(err)
   182  	}
   183  }
   184  
   185  // Benchmarks.
   186  
   187  func BenchmarkScalarBaseMult(t *testing.B) {
   188  	var p Point
   189  
   190  	for i := 0; i < t.N; i++ {
   191  		p.ScalarBaseMult(&dalekScalar)
   192  	}
   193  }
   194  
   195  func BenchmarkScalarMult(t *testing.B) {
   196  	var p Point
   197  
   198  	for i := 0; i < t.N; i++ {
   199  		p.ScalarMult(&dalekScalar, B)
   200  	}
   201  }
   202  
   203  func BenchmarkVarTimeDoubleScalarBaseMult(t *testing.B) {
   204  	var p Point
   205  
   206  	for i := 0; i < t.N; i++ {
   207  		p.VarTimeDoubleScalarBaseMult(&dalekScalar, B, &dalekScalar)
   208  	}
   209  }
   210
View as plain text