edwards25519_test.go

Documentation: crypto/ed25519/internal/edwards25519

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