blob: f5b36f75ca0439a28d90c8cd2c75557252089c53 [file] [log] [blame]
// 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")
}
}
})
})
}