edwards25519_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  	"crypto/internal/edwards25519/field"
     9  	"encoding/hex"
    10  	"internal/testenv"
    11  	"reflect"
    12  	"testing"
    13  )
    14  
    15  var B = NewGeneratorPoint()
    16  var I = NewIdentityPoint()
    17  
    18  func checkOnCurve(t *testing.T, points ...*Point) {
    19  	t.Helper()
    20  	for i, p := range points {
    21  		var XX, YY, ZZ, ZZZZ field.Element
    22  		XX.Square(&p.x)
    23  		YY.Square(&p.y)
    24  		ZZ.Square(&p.z)
    25  		ZZZZ.Square(&ZZ)
    26  		// -x² + y² = 1 + dx²y²
    27  		// -(X/Z)² + (Y/Z)² = 1 + d(X/Z)²(Y/Z)²
    28  		// (-X² + Y²)/Z² = 1 + (dX²Y²)/Z⁴
    29  		// (-X² + Y²)*Z² = Z⁴ + dX²Y²
    30  		var lhs, rhs field.Element
    31  		lhs.Subtract(&YY, &XX).Multiply(&lhs, &ZZ)
    32  		rhs.Multiply(d, &XX).Multiply(&rhs, &YY).Add(&rhs, &ZZZZ)
    33  		if lhs.Equal(&rhs) != 1 {
    34  			t.Errorf("X, Y, and Z do not specify a point on the curve\nX = %v\nY = %v\nZ = %v", p.x, p.y, p.z)
    35  		}
    36  		// xy = T/Z
    37  		lhs.Multiply(&p.x, &p.y)
    38  		rhs.Multiply(&p.z, &p.t)
    39  		if lhs.Equal(&rhs) != 1 {
    40  			t.Errorf("point %d is not valid\nX = %v\nY = %v\nZ = %v", i, p.x, p.y, p.z)
    41  		}
    42  	}
    43  }
    44  
    45  func TestGenerator(t *testing.T) {
    46  	// These are the coordinates of B from RFC 8032, Section 5.1, converted to
    47  	// little endian hex.
    48  	x := "1ad5258f602d56c9b2a7259560c72c695cdcd6fd31e2a4c0fe536ecdd3366921"
    49  	y := "5866666666666666666666666666666666666666666666666666666666666666"
    50  	if got := hex.EncodeToString(B.x.Bytes()); got != x {
    51  		t.Errorf("wrong B.x: got %s, expected %s", got, x)
    52  	}
    53  	if got := hex.EncodeToString(B.y.Bytes()); got != y {
    54  		t.Errorf("wrong B.y: got %s, expected %s", got, y)
    55  	}
    56  	if B.z.Equal(feOne) != 1 {
    57  		t.Errorf("wrong B.z: got %v, expected 1", B.z)
    58  	}
    59  	// Check that t is correct.
    60  	checkOnCurve(t, B)
    61  }
    62  
    63  func TestAddSubNegOnBasePoint(t *testing.T) {
    64  	checkLhs, checkRhs := &Point{}, &Point{}
    65  
    66  	checkLhs.Add(B, B)
    67  	tmpP2 := new(projP2).FromP3(B)
    68  	tmpP1xP1 := new(projP1xP1).Double(tmpP2)
    69  	checkRhs.fromP1xP1(tmpP1xP1)
    70  	if checkLhs.Equal(checkRhs) != 1 {
    71  		t.Error("B + B != [2]B")
    72  	}
    73  	checkOnCurve(t, checkLhs, checkRhs)
    74  
    75  	checkLhs.Subtract(B, B)
    76  	Bneg := new(Point).Negate(B)
    77  	checkRhs.Add(B, Bneg)
    78  	if checkLhs.Equal(checkRhs) != 1 {
    79  		t.Error("B - B != B + (-B)")
    80  	}
    81  	if I.Equal(checkLhs) != 1 {
    82  		t.Error("B - B != 0")
    83  	}
    84  	if I.Equal(checkRhs) != 1 {
    85  		t.Error("B + (-B) != 0")
    86  	}
    87  	checkOnCurve(t, checkLhs, checkRhs, Bneg)
    88  }
    89  
    90  func TestComparable(t *testing.T) {
    91  	if reflect.TypeOf(Point{}).Comparable() {
    92  		t.Error("Point is unexpectedly comparable")
    93  	}
    94  }
    95  
    96  func TestInvalidEncodings(t *testing.T) {
    97  	// An invalid point, that also happens to have y > p.
    98  	invalid := "efffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f"
    99  	p := NewGeneratorPoint()
   100  	if out, err := p.SetBytes(decodeHex(invalid)); err == nil {
   101  		t.Error("expected error for invalid point")
   102  	} else if out != nil {
   103  		t.Error("SetBytes did not return nil on an invalid encoding")
   104  	} else if p.Equal(B) != 1 {
   105  		t.Error("the Point was modified while decoding an invalid encoding")
   106  	}
   107  	checkOnCurve(t, p)
   108  }
   109  
   110  func TestNonCanonicalPoints(t *testing.T) {
   111  	type test struct {
   112  		name                string
   113  		encoding, canonical string
   114  	}
   115  	tests := []test{
   116  		// Points with x = 0 and the sign bit set. With x = 0 the curve equation
   117  		// gives y² = 1, so y = ±1. 1 has two valid encodings.
   118  		{
   119  			"y=1,sign-",
   120  			"0100000000000000000000000000000000000000000000000000000000000080",
   121  			"0100000000000000000000000000000000000000000000000000000000000000",
   122  		},
   123  		{
   124  			"y=p+1,sign-",
   125  			"eeffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
   126  			"0100000000000000000000000000000000000000000000000000000000000000",
   127  		},
   128  		{
   129  			"y=p-1,sign-",
   130  			"ecffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
   131  			"ecffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
   132  		},
   133  
   134  		// Non-canonical y encodings with values 2²⁵⁵-19 (p) to 2²⁵⁵-1 (p+18).
   135  		{
   136  			"y=p,sign+",
   137  			"edffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
   138  			"0000000000000000000000000000000000000000000000000000000000000000",
   139  		},
   140  		{
   141  			"y=p,sign-",
   142  			"edffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
   143  			"0000000000000000000000000000000000000000000000000000000000000080",
   144  		},
   145  		{
   146  			"y=p+1,sign+",
   147  			"eeffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
   148  			"0100000000000000000000000000000000000000000000000000000000000000",
   149  		},
   150  		// "y=p+1,sign-" is already tested above.
   151  		// p+2 is not a valid y-coordinate.
   152  		{
   153  			"y=p+3,sign+",
   154  			"f0ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
   155  			"0300000000000000000000000000000000000000000000000000000000000000",
   156  		},
   157  		{
   158  			"y=p+3,sign-",
   159  			"f0ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
   160  			"0300000000000000000000000000000000000000000000000000000000000080",
   161  		},
   162  		{
   163  			"y=p+4,sign+",
   164  			"f1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
   165  			"0400000000000000000000000000000000000000000000000000000000000000",
   166  		},
   167  		{
   168  			"y=p+4,sign-",
   169  			"f1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
   170  			"0400000000000000000000000000000000000000000000000000000000000080",
   171  		},
   172  		{
   173  			"y=p+5,sign+",
   174  			"f2ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
   175  			"0500000000000000000000000000000000000000000000000000000000000000",
   176  		},
   177  		{
   178  			"y=p+5,sign-",
   179  			"f2ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
   180  			"0500000000000000000000000000000000000000000000000000000000000080",
   181  		},
   182  		{
   183  			"y=p+6,sign+",
   184  			"f3ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
   185  			"0600000000000000000000000000000000000000000000000000000000000000",
   186  		},
   187  		{
   188  			"y=p+6,sign-",
   189  			"f3ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
   190  			"0600000000000000000000000000000000000000000000000000000000000080",
   191  		},
   192  		// p+7 is not a valid y-coordinate.
   193  		// p+8 is not a valid y-coordinate.
   194  		{
   195  			"y=p+9,sign+",
   196  			"f6ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
   197  			"0900000000000000000000000000000000000000000000000000000000000000",
   198  		},
   199  		{
   200  			"y=p+9,sign-",
   201  			"f6ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
   202  			"0900000000000000000000000000000000000000000000000000000000000080",
   203  		},
   204  		{
   205  			"y=p+10,sign+",
   206  			"f7ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
   207  			"0a00000000000000000000000000000000000000000000000000000000000000",
   208  		},
   209  		{
   210  			"y=p+10,sign-",
   211  			"f7ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
   212  			"0a00000000000000000000000000000000000000000000000000000000000080",
   213  		},
   214  		// p+11 is not a valid y-coordinate.
   215  		// p+12 is not a valid y-coordinate.
   216  		// p+13 is not a valid y-coordinate.
   217  		{
   218  			"y=p+14,sign+",
   219  			"fbffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
   220  			"0e00000000000000000000000000000000000000000000000000000000000000",
   221  		},
   222  		{
   223  			"y=p+14,sign-",
   224  			"fbffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
   225  			"0e00000000000000000000000000000000000000000000000000000000000080",
   226  		},
   227  		{
   228  			"y=p+15,sign+",
   229  			"fcffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
   230  			"0f00000000000000000000000000000000000000000000000000000000000000",
   231  		},
   232  		{
   233  			"y=p+15,sign-",
   234  			"fcffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
   235  			"0f00000000000000000000000000000000000000000000000000000000000080",
   236  		},
   237  		{
   238  			"y=p+16,sign+",
   239  			"fdffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
   240  			"1000000000000000000000000000000000000000000000000000000000000000",
   241  		},
   242  		{
   243  			"y=p+16,sign-",
   244  			"fdffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
   245  			"1000000000000000000000000000000000000000000000000000000000000080",
   246  		},
   247  		// p+17 is not a valid y-coordinate.
   248  		{
   249  			"y=p+18,sign+",
   250  			"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
   251  			"1200000000000000000000000000000000000000000000000000000000000000",
   252  		},
   253  		{
   254  			"y=p+18,sign-",
   255  			"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
   256  			"1200000000000000000000000000000000000000000000000000000000000080",
   257  		},
   258  	}
   259  	for _, tt := range tests {
   260  		t.Run(tt.name, func(t *testing.T) {
   261  			p1, err := new(Point).SetBytes(decodeHex(tt.encoding))
   262  			if err != nil {
   263  				t.Fatalf("error decoding non-canonical point: %v", err)
   264  			}
   265  			p2, err := new(Point).SetBytes(decodeHex(tt.canonical))
   266  			if err != nil {
   267  				t.Fatalf("error decoding canonical point: %v", err)
   268  			}
   269  			if p1.Equal(p2) != 1 {
   270  				t.Errorf("equivalent points are not equal: %v, %v", p1, p2)
   271  			}
   272  			if encoding := hex.EncodeToString(p1.Bytes()); encoding != tt.canonical {
   273  				t.Errorf("re-encoding does not match canonical; got %q, expected %q", encoding, tt.canonical)
   274  			}
   275  			checkOnCurve(t, p1, p2)
   276  		})
   277  	}
   278  }
   279  
   280  var testAllocationsSink byte
   281  
   282  func TestAllocations(t *testing.T) {
   283  	testenv.SkipIfOptimizationOff(t)
   284  
   285  	if allocs := testing.AllocsPerRun(100, func() {
   286  		p := NewIdentityPoint()
   287  		p.Add(p, NewGeneratorPoint())
   288  		s := NewScalar()
   289  		testAllocationsSink ^= s.Bytes()[0]
   290  		testAllocationsSink ^= p.Bytes()[0]
   291  	}); allocs > 0 {
   292  		t.Errorf("expected zero allocations, got %0.1v", allocs)
   293  	}
   294  }
   295  
   296  func decodeHex(s string) []byte {
   297  	b, err := hex.DecodeString(s)
   298  	if err != nil {
   299  		panic(err)
   300  	}
   301  	return b
   302  }
   303  
   304  func BenchmarkEncodingDecoding(b *testing.B) {
   305  	p := new(Point).Set(dalekScalarBasepoint)
   306  	for i := 0; i < b.N; i++ {
   307  		buf := p.Bytes()
   308  		_, err := p.SetBytes(buf)
   309  		if err != nil {
   310  			b.Fatal(err)
   311  		}
   312  	}
   313  }
   314
View as plain text