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