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