123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308 |
- // 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
- }
|