blob: 7b01920135a8b2962f68a403b5e5c6c27a85f16b [file] [log] [blame]
// Copyright (c) 2019 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 edwards25519
import (
"crypto/ed25519/internal/edwards25519/field"
"encoding/hex"
"os"
"reflect"
"runtime"
"strings"
"testing"
)
var B = NewGeneratorPoint()
var I = NewIdentityPoint()
func checkOnCurve(t *testing.T, points ...*Point) {
t.Helper()
for i, p := range points {
var XX, YY, ZZ, ZZZZ field.Element
XX.Square(&p.x)
YY.Square(&p.y)
ZZ.Square(&p.z)
ZZZZ.Square(&ZZ)
// -x² + y² = 1 + dx²y²
// -(X/Z)² + (Y/Z)² = 1 + d(X/Z)²(Y/Z)²
// (-X² + Y²)/Z² = 1 + (dX²Y²)/Z⁴
// (-X² + Y²)*Z² = Z⁴ + dX²Y²
var lhs, rhs field.Element
lhs.Subtract(&YY, &XX).Multiply(&lhs, &ZZ)
rhs.Multiply(d, &XX).Multiply(&rhs, &YY).Add(&rhs, &ZZZZ)
if lhs.Equal(&rhs) != 1 {
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)
}
// xy = T/Z
lhs.Multiply(&p.x, &p.y)
rhs.Multiply(&p.z, &p.t)
if lhs.Equal(&rhs) != 1 {
t.Errorf("point %d is not valid\nX = %v\nY = %v\nZ = %v", i, p.x, p.y, p.z)
}
}
}
func TestGenerator(t *testing.T) {
// These are the coordinates of B from RFC 8032, Section 5.1, converted to
// little endian hex.
x := "1ad5258f602d56c9b2a7259560c72c695cdcd6fd31e2a4c0fe536ecdd3366921"
y := "5866666666666666666666666666666666666666666666666666666666666666"
if got := hex.EncodeToString(B.x.Bytes()); got != x {
t.Errorf("wrong B.x: got %s, expected %s", got, x)
}
if got := hex.EncodeToString(B.y.Bytes()); got != y {
t.Errorf("wrong B.y: got %s, expected %s", got, y)
}
if B.z.Equal(feOne) != 1 {
t.Errorf("wrong B.z: got %v, expected 1", B.z)
}
// Check that t is correct.
checkOnCurve(t, B)
}
func TestAddSubNegOnBasePoint(t *testing.T) {
checkLhs, checkRhs := &Point{}, &Point{}
checkLhs.Add(B, B)
tmpP2 := new(projP2).FromP3(B)
tmpP1xP1 := new(projP1xP1).Double(tmpP2)
checkRhs.fromP1xP1(tmpP1xP1)
if checkLhs.Equal(checkRhs) != 1 {
t.Error("B + B != [2]B")
}
checkOnCurve(t, checkLhs, checkRhs)
checkLhs.Subtract(B, B)
Bneg := new(Point).Negate(B)
checkRhs.Add(B, Bneg)
if checkLhs.Equal(checkRhs) != 1 {
t.Error("B - B != B + (-B)")
}
if I.Equal(checkLhs) != 1 {
t.Error("B - B != 0")
}
if I.Equal(checkRhs) != 1 {
t.Error("B + (-B) != 0")
}
checkOnCurve(t, checkLhs, checkRhs, Bneg)
}
func TestComparable(t *testing.T) {
if reflect.TypeOf(Point{}).Comparable() {
t.Error("Point is unexpectedly comparable")
}
}
func TestInvalidEncodings(t *testing.T) {
// An invalid point, that also happens to have y > p.
invalid := "efffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f"
p := NewGeneratorPoint()
if out, err := p.SetBytes(decodeHex(invalid)); err == nil {
t.Error("expected error for invalid point")
} else if out != nil {
t.Error("SetBytes did not return nil on an invalid encoding")
} else if p.Equal(B) != 1 {
t.Error("the Point was modified while decoding an invalid encoding")
}
checkOnCurve(t, p)
}
func TestNonCanonicalPoints(t *testing.T) {
type test struct {
name string
encoding, canonical string
}
tests := []test{
// Points with x = 0 and the sign bit set. With x = 0 the curve equation
// gives y² = 1, so y = ±1. 1 has two valid encodings.
{
"y=1,sign-",
"0100000000000000000000000000000000000000000000000000000000000080",
"0100000000000000000000000000000000000000000000000000000000000000",
},
{
"y=p+1,sign-",
"eeffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
"0100000000000000000000000000000000000000000000000000000000000000",
},
{
"y=p-1,sign-",
"ecffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
"ecffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
},
// Non-canonical y encodings with values 2²⁵⁵-19 (p) to 2²⁵⁵-1 (p+18).
{
"y=p,sign+",
"edffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
"0000000000000000000000000000000000000000000000000000000000000000",
},
{
"y=p,sign-",
"edffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
"0000000000000000000000000000000000000000000000000000000000000080",
},
{
"y=p+1,sign+",
"eeffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
"0100000000000000000000000000000000000000000000000000000000000000",
},
// "y=p+1,sign-" is already tested above.
// p+2 is not a valid y-coordinate.
{
"y=p+3,sign+",
"f0ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
"0300000000000000000000000000000000000000000000000000000000000000",
},
{
"y=p+3,sign-",
"f0ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
"0300000000000000000000000000000000000000000000000000000000000080",
},
{
"y=p+4,sign+",
"f1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
"0400000000000000000000000000000000000000000000000000000000000000",
},
{
"y=p+4,sign-",
"f1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
"0400000000000000000000000000000000000000000000000000000000000080",
},
{
"y=p+5,sign+",
"f2ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
"0500000000000000000000000000000000000000000000000000000000000000",
},
{
"y=p+5,sign-",
"f2ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
"0500000000000000000000000000000000000000000000000000000000000080",
},
{
"y=p+6,sign+",
"f3ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
"0600000000000000000000000000000000000000000000000000000000000000",
},
{
"y=p+6,sign-",
"f3ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
"0600000000000000000000000000000000000000000000000000000000000080",
},
// p+7 is not a valid y-coordinate.
// p+8 is not a valid y-coordinate.
{
"y=p+9,sign+",
"f6ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
"0900000000000000000000000000000000000000000000000000000000000000",
},
{
"y=p+9,sign-",
"f6ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
"0900000000000000000000000000000000000000000000000000000000000080",
},
{
"y=p+10,sign+",
"f7ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
"0a00000000000000000000000000000000000000000000000000000000000000",
},
{
"y=p+10,sign-",
"f7ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
"0a00000000000000000000000000000000000000000000000000000000000080",
},
// p+11 is not a valid y-coordinate.
// p+12 is not a valid y-coordinate.
// p+13 is not a valid y-coordinate.
{
"y=p+14,sign+",
"fbffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
"0e00000000000000000000000000000000000000000000000000000000000000",
},
{
"y=p+14,sign-",
"fbffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
"0e00000000000000000000000000000000000000000000000000000000000080",
},
{
"y=p+15,sign+",
"fcffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
"0f00000000000000000000000000000000000000000000000000000000000000",
},
{
"y=p+15,sign-",
"fcffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
"0f00000000000000000000000000000000000000000000000000000000000080",
},
{
"y=p+16,sign+",
"fdffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
"1000000000000000000000000000000000000000000000000000000000000000",
},
{
"y=p+16,sign-",
"fdffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
"1000000000000000000000000000000000000000000000000000000000000080",
},
// p+17 is not a valid y-coordinate.
{
"y=p+18,sign+",
"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f",
"1200000000000000000000000000000000000000000000000000000000000000",
},
{
"y=p+18,sign-",
"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
"1200000000000000000000000000000000000000000000000000000000000080",
},
}
for _, tt := range tests {
t.Run(tt.name, func(t *testing.T) {
p1, err := new(Point).SetBytes(decodeHex(tt.encoding))
if err != nil {
t.Fatalf("error decoding non-canonical point: %v", err)
}
p2, err := new(Point).SetBytes(decodeHex(tt.canonical))
if err != nil {
t.Fatalf("error decoding canonical point: %v", err)
}
if p1.Equal(p2) != 1 {
t.Errorf("equivalent points are not equal: %v, %v", p1, p2)
}
if encoding := hex.EncodeToString(p1.Bytes()); encoding != tt.canonical {
t.Errorf("re-encoding does not match canonical; got %q, expected %q", encoding, tt.canonical)
}
checkOnCurve(t, p1, p2)
})
}
}
var testAllocationsSink byte
func TestAllocations(t *testing.T) {
if runtime.Compiler == "gccgo" {
t.Skip("gofronted escape analysis not good enough")
}
if strings.HasSuffix(os.Getenv("GO_BUILDER_NAME"), "-noopt") {
t.Skip("skipping allocations test without relevant optimizations")
}
if allocs := testing.AllocsPerRun(100, func() {
p := NewIdentityPoint()
p.Add(p, NewGeneratorPoint())
s := NewScalar()
testAllocationsSink ^= s.Bytes()[0]
testAllocationsSink ^= p.Bytes()[0]
}); allocs > 0 {
t.Errorf("expected zero allocations, got %0.1v", allocs)
}
}
func decodeHex(s string) []byte {
b, err := hex.DecodeString(s)
if err != nil {
panic(err)
}
return b
}