src/crypto/elliptic/elliptic_test.go - go - Git at Google

 // Copyright 2010 The Go Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.

 package elliptic

 import (
 	"bytes"
 	"crypto/rand"
 	"encoding/hex"
 	"math/big"
 	"testing"
 )

 // genericParamsForCurve returns the dereferenced CurveParams for
 // the specified curve. This is used to avoid the logic for
 // upgrading a curve to its specific implementation, forcing
 // usage of the generic implementation.
 func genericParamsForCurve(c Curve) *CurveParams {
 	d := *(c.Params())
 	return &d
 }

 func testAllCurves(t *testing.T, f func(*testing.T, Curve)) {
 	tests := []struct {
 		name  string
 		curve Curve
 	}{
 		{"P256", P256()},
 		{"P256/Params", genericParamsForCurve(P256())},
 		{"P224", P224()},
 		{"P224/Params", genericParamsForCurve(P224())},
 		{"P384", P384()},
 		{"P384/Params", genericParamsForCurve(P384())},
 		{"P521", P521()},
 		{"P521/Params", genericParamsForCurve(P521())},
 	}
 	if testing.Short() {
 		tests = tests[:1]
 	}
 	for _, test := range tests {
 		curve := test.curve
 		t.Run(test.name, func(t *testing.T) {
 			t.Parallel()
 			f(t, curve)
 		})
 	}
 }

 func TestOnCurve(t *testing.T) {
 	testAllCurves(t, func(t *testing.T, curve Curve) {
 		if !curve.IsOnCurve(curve.Params().Gx, curve.Params().Gy) {
 			t.Error("basepoint is not on the curve")
 		}
 	})
 }

 func TestOffCurve(t *testing.T) {
 	testAllCurves(t, func(t *testing.T, curve Curve) {
 		x, y := new(big.Int).SetInt64(1), new(big.Int).SetInt64(1)
 		if curve.IsOnCurve(x, y) {
 			t.Errorf("point off curve is claimed to be on the curve")
 		}
 		b := Marshal(curve, x, y)
 		x1, y1 := Unmarshal(curve, b)
 		if x1 != nil || y1 != nil {
 			t.Errorf("unmarshaling a point not on the curve succeeded")
 		}
 	})
 }

 func TestInfinity(t *testing.T) {
 	testAllCurves(t, testInfinity)
 }

 func testInfinity(t *testing.T, curve Curve) {
 	_, x, y, _ := GenerateKey(curve, rand.Reader)
 	x, y = curve.ScalarMult(x, y, curve.Params().N.Bytes())
 	if x.Sign() != 0 || y.Sign() != 0 {
 		t.Errorf("x^q != ∞")
 	}

 	x, y = curve.ScalarBaseMult([]byte{0})
 	if x.Sign() != 0 || y.Sign() != 0 {
 		t.Errorf("b^0 != ∞")
 		x.SetInt64(0)
 		y.SetInt64(0)
 	}

 	x2, y2 := curve.Double(x, y)
 	if x2.Sign() != 0 || y2.Sign() != 0 {
 		t.Errorf("2∞ != ∞")
 	}

 	baseX := curve.Params().Gx
 	baseY := curve.Params().Gy

 	x3, y3 := curve.Add(baseX, baseY, x, y)
 	if x3.Cmp(baseX) != 0 || y3.Cmp(baseY) != 0 {
 		t.Errorf("x+∞ != x")
 	}

 	x4, y4 := curve.Add(x, y, baseX, baseY)
 	if x4.Cmp(baseX) != 0 || y4.Cmp(baseY) != 0 {
 		t.Errorf("∞+x != x")
 	}

 	if curve.IsOnCurve(x, y) {
 		t.Errorf("IsOnCurve(∞) == true")
 	}

 	if xx, yy := Unmarshal(curve, Marshal(curve, x, y)); xx != nil || yy != nil {
 		t.Errorf("Unmarshal(Marshal(∞)) did not return an error")
 	}
 	// We don't test UnmarshalCompressed(MarshalCompressed(∞)) because there are
 	// two valid points with x = 0.
 	if xx, yy := Unmarshal(curve, []byte{0x00}); xx != nil || yy != nil {
 		t.Errorf("Unmarshal(∞) did not return an error")
 	}
 }

 func TestMarshal(t *testing.T) {
 	testAllCurves(t, func(t *testing.T, curve Curve) {
 		_, x, y, err := GenerateKey(curve, rand.Reader)
 		if err != nil {
 			t.Fatal(err)
 		}
 		serialized := Marshal(curve, x, y)
 		xx, yy := Unmarshal(curve, serialized)
 		if xx == nil {
 			t.Fatal("failed to unmarshal")
 		}
 		if xx.Cmp(x) != 0 || yy.Cmp(y) != 0 {
 			t.Fatal("unmarshal returned different values")
 		}
 	})
 }

 func TestUnmarshalToLargeCoordinates(t *testing.T) {
 	// See https://golang.org/issues/20482.
 	testAllCurves(t, testUnmarshalToLargeCoordinates)
 }

 func testUnmarshalToLargeCoordinates(t *testing.T, curve Curve) {
 	p := curve.Params().P
 	byteLen := (p.BitLen() + 7) / 8

 	// Set x to be greater than curve's parameter P – specifically, to P+5.
 	// Set y to mod_sqrt(x^3 - 3x + B)) so that (x mod P = 5 , y) is on the
 	// curve.
 	x := new(big.Int).Add(p, big.NewInt(5))
 	y := curve.Params().polynomial(x)
 	y.ModSqrt(y, p)

 	invalid := make([]byte, byteLen*2+1)
 	invalid[0] = 4 // uncompressed encoding
 	x.FillBytes(invalid[1 : 1+byteLen])
 	y.FillBytes(invalid[1+byteLen:])

 	if X, Y := Unmarshal(curve, invalid); X != nil || Y != nil {
 		t.Errorf("Unmarshal accepts invalid X coordinate")
 	}

 	if curve == p256 {
 		// This is a point on the curve with a small y value, small enough that
 		// we can add p and still be within 32 bytes.
 		x, _ = new(big.Int).SetString("31931927535157963707678568152204072984517581467226068221761862915403492091210", 10)
 		y, _ = new(big.Int).SetString("5208467867388784005506817585327037698770365050895731383201516607147", 10)
 		y.Add(y, p)

 		if p.Cmp(y) > 0 || y.BitLen() != 256 {
 			t.Fatal("y not within expected range")
 		}

 		// marshal
 		x.FillBytes(invalid[1 : 1+byteLen])
 		y.FillBytes(invalid[1+byteLen:])

 		if X, Y := Unmarshal(curve, invalid); X != nil || Y != nil {
 			t.Errorf("Unmarshal accepts invalid Y coordinate")
 		}
 	}
 }

 func TestMarshalCompressed(t *testing.T) {
 	t.Run("P-256/03", func(t *testing.T) {
 		data, _ := hex.DecodeString("031e3987d9f9ea9d7dd7155a56a86b2009e1e0ab332f962d10d8beb6406ab1ad79")
 		x, _ := new(big.Int).SetString("13671033352574878777044637384712060483119675368076128232297328793087057702265", 10)
 		y, _ := new(big.Int).SetString("66200849279091436748794323380043701364391950689352563629885086590854940586447", 10)
 		testMarshalCompressed(t, P256(), x, y, data)
 	})
 	t.Run("P-256/02", func(t *testing.T) {
 		data, _ := hex.DecodeString("021e3987d9f9ea9d7dd7155a56a86b2009e1e0ab332f962d10d8beb6406ab1ad79")
 		x, _ := new(big.Int).SetString("13671033352574878777044637384712060483119675368076128232297328793087057702265", 10)
 		y, _ := new(big.Int).SetString("49591239931264812013903123569363872165694192725937750565648544718012157267504", 10)
 		testMarshalCompressed(t, P256(), x, y, data)
 	})

 	t.Run("Invalid", func(t *testing.T) {
 		data, _ := hex.DecodeString("02fd4bf61763b46581fd9174d623516cf3c81edd40e29ffa2777fb6cb0ae3ce535")
 		X, Y := UnmarshalCompressed(P256(), data)
 		if X != nil || Y != nil {
 			t.Error("expected an error for invalid encoding")
 		}
 	})

 	if testing.Short() {
 		t.Skip("skipping other curves on short test")
 	}

 	testAllCurves(t, func(t *testing.T, curve Curve) {
 		_, x, y, err := GenerateKey(curve, rand.Reader)
 		if err != nil {
 			t.Fatal(err)
 		}
 		testMarshalCompressed(t, curve, x, y, nil)
 	})

 }

 func testMarshalCompressed(t *testing.T, curve Curve, x, y *big.Int, want []byte) {
 	if !curve.IsOnCurve(x, y) {
 		t.Fatal("invalid test point")
 	}
 	got := MarshalCompressed(curve, x, y)
 	if want != nil && !bytes.Equal(got, want) {
 		t.Errorf("got unexpected MarshalCompressed result: got %x, want %x", got, want)
 	}

 	X, Y := UnmarshalCompressed(curve, got)
 	if X == nil || Y == nil {
 		t.Fatalf("UnmarshalCompressed failed unexpectedly")
 	}

 	if !curve.IsOnCurve(X, Y) {
 		t.Error("UnmarshalCompressed returned a point not on the curve")
 	}
 	if X.Cmp(x) != 0 || Y.Cmp(y) != 0 {
 		t.Errorf("point did not round-trip correctly: got (%v, %v), want (%v, %v)", X, Y, x, y)
 	}
 }

 func TestLargeIsOnCurve(t *testing.T) {
 	testAllCurves(t, func(t *testing.T, curve Curve) {
 		large := big.NewInt(1)
 		large.Lsh(large, 1000)
 		if curve.IsOnCurve(large, large) {
 			t.Errorf("(2^1000, 2^1000) is reported on the curve")
 		}
 	})
 }

 func benchmarkAllCurves(t *testing.B, f func(*testing.B, Curve)) {
 	tests := []struct {
 		name  string
 		curve Curve
 	}{
 		{"P256", P256()},
 		{"P224", P224()},
 		{"P384", P384()},
 		{"P521", P521()},
 	}
 	for _, test := range tests {
 		curve := test.curve
 		t.Run(test.name, func(t *testing.B) {
 			f(t, curve)
 		})
 	}
 }

 func BenchmarkScalarBaseMult(b *testing.B) {
 	benchmarkAllCurves(b, func(b *testing.B, curve Curve) {
 		priv, _, _, _ := GenerateKey(curve, rand.Reader)
 		b.ReportAllocs()
 		b.ResetTimer()
 		for i := 0; i < b.N; i++ {
 			x, _ := curve.ScalarBaseMult(priv)
 			// Prevent the compiler from optimizing out the operation.
 			priv[0] ^= byte(x.Bits()[0])
 		}
 	})
 }

 func BenchmarkScalarMult(b *testing.B) {
 	benchmarkAllCurves(b, func(b *testing.B, curve Curve) {
 		_, x, y, _ := GenerateKey(curve, rand.Reader)
 		priv, _, _, _ := GenerateKey(curve, rand.Reader)
 		b.ReportAllocs()
 		b.ResetTimer()
 		for i := 0; i < b.N; i++ {
 			x, y = curve.ScalarMult(x, y, priv)
 		}
 	})
 }

 func BenchmarkMarshalUnmarshal(b *testing.B) {
 	benchmarkAllCurves(b, func(b *testing.B, curve Curve) {
 		_, x, y, _ := GenerateKey(curve, rand.Reader)
 		b.Run("Uncompressed", func(b *testing.B) {
 			b.ReportAllocs()
 			for i := 0; i < b.N; i++ {
 				buf := Marshal(curve, x, y)
 				xx, yy := Unmarshal(curve, buf)
 				if xx.Cmp(x) != 0 || yy.Cmp(y) != 0 {
 					b.Error("Unmarshal output different from Marshal input")
 				}
 			}
 		})
 		b.Run("Compressed", func(b *testing.B) {
 			b.ReportAllocs()
 			for i := 0; i < b.N; i++ {
 				buf := Marshal(curve, x, y)
 				xx, yy := Unmarshal(curve, buf)
 				if xx.Cmp(x) != 0 || yy.Cmp(y) != 0 {
 					b.Error("Unmarshal output different from Marshal input")
 				}
 			}
 		})
 	})
 }
	// Copyright 2010 The Go Authors. All rights reserved.
	// Use of this source code is governed by a BSD-style
	// license that can be found in the LICENSE file.

	package elliptic

	import (
	"bytes"
	"crypto/rand"
	"encoding/hex"
	"math/big"
	"testing"
	)

	// genericParamsForCurve returns the dereferenced CurveParams for
	// the specified curve. This is used to avoid the logic for
	// upgrading a curve to its specific implementation, forcing
	// usage of the generic implementation.
	func genericParamsForCurve(c Curve) *CurveParams {
	d := *(c.Params())
	return &d
	}

	func testAllCurves(t testing.T, f func(testing.T, Curve)) {
	tests := []struct {
	name string
	curve Curve
	}{
	{"P256", P256()},
	{"P256/Params", genericParamsForCurve(P256())},
	{"P224", P224()},
	{"P224/Params", genericParamsForCurve(P224())},
	{"P384", P384()},
	{"P384/Params", genericParamsForCurve(P384())},
	{"P521", P521()},
	{"P521/Params", genericParamsForCurve(P521())},
	}
	if testing.Short() {
	tests = tests[:1]
	}
	for _, test := range tests {
	curve := test.curve
	t.Run(test.name, func(t *testing.T) {
	t.Parallel()
	f(t, curve)
	})
	}
	}

	func TestOnCurve(t *testing.T) {
	testAllCurves(t, func(t *testing.T, curve Curve) {
	if !curve.IsOnCurve(curve.Params().Gx, curve.Params().Gy) {
	t.Error("basepoint is not on the curve")
	}
	})
	}

	func TestOffCurve(t *testing.T) {
	testAllCurves(t, func(t *testing.T, curve Curve) {
	x, y := new(big.Int).SetInt64(1), new(big.Int).SetInt64(1)
	if curve.IsOnCurve(x, y) {
	t.Errorf("point off curve is claimed to be on the curve")
	}
	b := Marshal(curve, x, y)
	x1, y1 := Unmarshal(curve, b)
	if x1 != nil \|\| y1 != nil {
	t.Errorf("unmarshaling a point not on the curve succeeded")
	}
	})
	}

	func TestInfinity(t *testing.T) {
	testAllCurves(t, testInfinity)
	}

	func testInfinity(t *testing.T, curve Curve) {
	_, x, y, _ := GenerateKey(curve, rand.Reader)
	x, y = curve.ScalarMult(x, y, curve.Params().N.Bytes())
	if x.Sign() != 0 \|\| y.Sign() != 0 {
	t.Errorf("x^q != ∞")
	}

	x, y = curve.ScalarBaseMult([]byte{0})
	if x.Sign() != 0 \|\| y.Sign() != 0 {
	t.Errorf("b^0 != ∞")
	x.SetInt64(0)
	y.SetInt64(0)
	}

	x2, y2 := curve.Double(x, y)
	if x2.Sign() != 0 \|\| y2.Sign() != 0 {
	t.Errorf("2∞ != ∞")
	}

	baseX := curve.Params().Gx
	baseY := curve.Params().Gy

	x3, y3 := curve.Add(baseX, baseY, x, y)
	if x3.Cmp(baseX) != 0 \|\| y3.Cmp(baseY) != 0 {
	t.Errorf("x+∞ != x")
	}

	x4, y4 := curve.Add(x, y, baseX, baseY)
	if x4.Cmp(baseX) != 0 \|\| y4.Cmp(baseY) != 0 {
	t.Errorf("∞+x != x")
	}

	if curve.IsOnCurve(x, y) {
	t.Errorf("IsOnCurve(∞) == true")
	}

	if xx, yy := Unmarshal(curve, Marshal(curve, x, y)); xx != nil \|\| yy != nil {
	t.Errorf("Unmarshal(Marshal(∞)) did not return an error")
	}
	// We don't test UnmarshalCompressed(MarshalCompressed(∞)) because there are
	// two valid points with x = 0.
	if xx, yy := Unmarshal(curve, []byte{0x00}); xx != nil \|\| yy != nil {
	t.Errorf("Unmarshal(∞) did not return an error")
	}
	}

	func TestMarshal(t *testing.T) {
	testAllCurves(t, func(t *testing.T, curve Curve) {
	_, x, y, err := GenerateKey(curve, rand.Reader)
	if err != nil {
	t.Fatal(err)
	}
	serialized := Marshal(curve, x, y)
	xx, yy := Unmarshal(curve, serialized)
	if xx == nil {
	t.Fatal("failed to unmarshal")
	}
	if xx.Cmp(x) != 0 \|\| yy.Cmp(y) != 0 {
	t.Fatal("unmarshal returned different values")
	}
	})
	}

	func TestUnmarshalToLargeCoordinates(t *testing.T) {
	// See https://golang.org/issues/20482.
	testAllCurves(t, testUnmarshalToLargeCoordinates)
	}

	func testUnmarshalToLargeCoordinates(t *testing.T, curve Curve) {
	p := curve.Params().P
	byteLen := (p.BitLen() + 7) / 8

	// Set x to be greater than curve's parameter P – specifically, to P+5.
	// Set y to mod_sqrt(x^3 - 3x + B)) so that (x mod P = 5 , y) is on the
	// curve.
	x := new(big.Int).Add(p, big.NewInt(5))
	y := curve.Params().polynomial(x)
	y.ModSqrt(y, p)

	invalid := make([]byte, byteLen*2+1)
	invalid[0] = 4 // uncompressed encoding
	x.FillBytes(invalid[1 : 1+byteLen])
	y.FillBytes(invalid[1+byteLen:])

	if X, Y := Unmarshal(curve, invalid); X != nil \|\| Y != nil {
	t.Errorf("Unmarshal accepts invalid X coordinate")
	}

	if curve == p256 {
	// This is a point on the curve with a small y value, small enough that
	// we can add p and still be within 32 bytes.
	x, _ = new(big.Int).SetString("31931927535157963707678568152204072984517581467226068221761862915403492091210", 10)
	y, _ = new(big.Int).SetString("5208467867388784005506817585327037698770365050895731383201516607147", 10)
	y.Add(y, p)

	if p.Cmp(y) > 0 \|\| y.BitLen() != 256 {
	t.Fatal("y not within expected range")
	}

	// marshal
	x.FillBytes(invalid[1 : 1+byteLen])
	y.FillBytes(invalid[1+byteLen:])

	if X, Y := Unmarshal(curve, invalid); X != nil \|\| Y != nil {
	t.Errorf("Unmarshal accepts invalid Y coordinate")
	}
	}
	}

	func TestMarshalCompressed(t *testing.T) {
	t.Run("P-256/03", func(t *testing.T) {
	data, _ := hex.DecodeString("031e3987d9f9ea9d7dd7155a56a86b2009e1e0ab332f962d10d8beb6406ab1ad79")
	x, _ := new(big.Int).SetString("13671033352574878777044637384712060483119675368076128232297328793087057702265", 10)
	y, _ := new(big.Int).SetString("66200849279091436748794323380043701364391950689352563629885086590854940586447", 10)
	testMarshalCompressed(t, P256(), x, y, data)
	})
	t.Run("P-256/02", func(t *testing.T) {
	data, _ := hex.DecodeString("021e3987d9f9ea9d7dd7155a56a86b2009e1e0ab332f962d10d8beb6406ab1ad79")
	x, _ := new(big.Int).SetString("13671033352574878777044637384712060483119675368076128232297328793087057702265", 10)
	y, _ := new(big.Int).SetString("49591239931264812013903123569363872165694192725937750565648544718012157267504", 10)
	testMarshalCompressed(t, P256(), x, y, data)
	})

	t.Run("Invalid", func(t *testing.T) {
	data, _ := hex.DecodeString("02fd4bf61763b46581fd9174d623516cf3c81edd40e29ffa2777fb6cb0ae3ce535")
	X, Y := UnmarshalCompressed(P256(), data)
	if X != nil \|\| Y != nil {
	t.Error("expected an error for invalid encoding")
	}
	})

	if testing.Short() {
	t.Skip("skipping other curves on short test")
	}

	testAllCurves(t, func(t *testing.T, curve Curve) {
	_, x, y, err := GenerateKey(curve, rand.Reader)
	if err != nil {
	t.Fatal(err)
	}
	testMarshalCompressed(t, curve, x, y, nil)
	})

	}

	func testMarshalCompressed(t testing.T, curve Curve, x, y big.Int, want []byte) {
	if !curve.IsOnCurve(x, y) {
	t.Fatal("invalid test point")
	}
	got := MarshalCompressed(curve, x, y)
	if want != nil && !bytes.Equal(got, want) {
	t.Errorf("got unexpected MarshalCompressed result: got %x, want %x", got, want)
	}

	X, Y := UnmarshalCompressed(curve, got)
	if X == nil \|\| Y == nil {
	t.Fatalf("UnmarshalCompressed failed unexpectedly")
	}

	if !curve.IsOnCurve(X, Y) {
	t.Error("UnmarshalCompressed returned a point not on the curve")
	}
	if X.Cmp(x) != 0 \|\| Y.Cmp(y) != 0 {
	t.Errorf("point did not round-trip correctly: got (%v, %v), want (%v, %v)", X, Y, x, y)
	}
	}

	func TestLargeIsOnCurve(t *testing.T) {
	testAllCurves(t, func(t *testing.T, curve Curve) {
	large := big.NewInt(1)
	large.Lsh(large, 1000)
	if curve.IsOnCurve(large, large) {
	t.Errorf("(2^1000, 2^1000) is reported on the curve")
	}
	})
	}

	func benchmarkAllCurves(t testing.B, f func(testing.B, Curve)) {
	tests := []struct {
	name string
	curve Curve
	}{
	{"P256", P256()},
	{"P224", P224()},
	{"P384", P384()},
	{"P521", P521()},
	}
	for _, test := range tests {
	curve := test.curve
	t.Run(test.name, func(t *testing.B) {
	f(t, curve)
	})
	}
	}

	func BenchmarkScalarBaseMult(b *testing.B) {
	benchmarkAllCurves(b, func(b *testing.B, curve Curve) {
	priv, _, _, _ := GenerateKey(curve, rand.Reader)
	b.ReportAllocs()
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
	x, _ := curve.ScalarBaseMult(priv)
	// Prevent the compiler from optimizing out the operation.
	priv[0] ^= byte(x.Bits()[0])
	}
	})
	}

	func BenchmarkScalarMult(b *testing.B) {
	benchmarkAllCurves(b, func(b *testing.B, curve Curve) {
	_, x, y, _ := GenerateKey(curve, rand.Reader)
	priv, _, _, _ := GenerateKey(curve, rand.Reader)
	b.ReportAllocs()
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
	x, y = curve.ScalarMult(x, y, priv)
	}
	})
	}

	func BenchmarkMarshalUnmarshal(b *testing.B) {
	benchmarkAllCurves(b, func(b *testing.B, curve Curve) {
	_, x, y, _ := GenerateKey(curve, rand.Reader)
	b.Run("Uncompressed", func(b *testing.B) {
	b.ReportAllocs()
	for i := 0; i < b.N; i++ {
	buf := Marshal(curve, x, y)
	xx, yy := Unmarshal(curve, buf)
	if xx.Cmp(x) != 0 \|\| yy.Cmp(y) != 0 {
	b.Error("Unmarshal output different from Marshal input")
	}
	}
	})
	b.Run("Compressed", func(b *testing.B) {
	b.ReportAllocs()
	for i := 0; i < b.N; i++ {
	buf := Marshal(curve, x, y)
	xx, yy := Unmarshal(curve, buf)
	if xx.Cmp(x) != 0 \|\| yy.Cmp(y) != 0 {
	b.Error("Unmarshal output different from Marshal input")
	}
	}
	})
	})
	}