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