| 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 |
"bytes" |
| 9 |
"encoding/hex" |
| 10 |
"math/big" |
| 11 |
mathrand "math/rand" |
| 12 |
"reflect" |
| 13 |
"testing" |
| 14 |
"testing/quick" |
| 15 |
) |
| 16 |
|
| 17 |
// Generate returns a valid (reduced modulo l) Scalar with a distribution |
| 18 |
// weighted towards high, low, and edge values. |
| 19 |
func (Scalar) Generate(rand *mathrand.Rand, size int) reflect.Value { |
| 20 |
s := scZero |
| 21 |
diceRoll := rand.Intn(100) |
| 22 |
switch { |
| 23 |
case diceRoll == 0: |
| 24 |
case diceRoll == 1: |
| 25 |
s = scOne |
| 26 |
case diceRoll == 2: |
| 27 |
s = scMinusOne |
| 28 |
case diceRoll < 5: |
| 29 |
// Generate a low scalar in [0, 2^125). |
| 30 |
rand.Read(s.s[:16]) |
| 31 |
s.s[15] &= (1 << 5) - 1 |
| 32 |
case diceRoll < 10: |
| 33 |
// Generate a high scalar in [2^252, 2^252 + 2^124). |
| 34 |
s.s[31] = 1 << 4 |
| 35 |
rand.Read(s.s[:16]) |
| 36 |
s.s[15] &= (1 << 4) - 1 |
| 37 |
default: |
| 38 |
// Generate a valid scalar in [0, l) by returning [0, 2^252) which has a |
| 39 |
// negligibly different distribution (the former has a 2^-127.6 chance |
| 40 |
// of being out of the latter range). |
| 41 |
rand.Read(s.s[:]) |
| 42 |
s.s[31] &= (1 << 4) - 1 |
| 43 |
} |
| 44 |
return reflect.ValueOf(s) |
| 45 |
} |
| 46 |
|
| 47 |
// quickCheckConfig1024 will make each quickcheck test run (1024 * -quickchecks) |
| 48 |
// times. The default value of -quickchecks is 100. |
| 49 |
var quickCheckConfig1024 = &quick.Config{MaxCountScale: 1 << 10} |
| 50 |
|
| 51 |
func TestScalarGenerate(t *testing.T) { |
| 52 |
f := func(sc Scalar) bool { |
| 53 |
return isReduced(&sc) |
| 54 |
} |
| 55 |
if err := quick.Check(f, quickCheckConfig1024); err != nil { |
| 56 |
t.Errorf("generated unreduced scalar: %v", err) |
| 57 |
} |
| 58 |
} |
| 59 |
|
| 60 |
func TestScalarSetCanonicalBytes(t *testing.T) { |
| 61 |
f1 := func(in [32]byte, sc Scalar) bool { |
| 62 |
// Mask out top 4 bits to guarantee value falls in [0, l). |
| 63 |
in[len(in)-1] &= (1 << 4) - 1 |
| 64 |
if _, err := sc.SetCanonicalBytes(in[:]); err != nil { |
| 65 |
return false |
| 66 |
} |
| 67 |
return bytes.Equal(in[:], sc.Bytes()) && isReduced(&sc) |
| 68 |
} |
| 69 |
if err := quick.Check(f1, quickCheckConfig1024); err != nil { |
| 70 |
t.Errorf("failed bytes->scalar->bytes round-trip: %v", err) |
| 71 |
} |
| 72 |
|
| 73 |
f2 := func(sc1, sc2 Scalar) bool { |
| 74 |
if _, err := sc2.SetCanonicalBytes(sc1.Bytes()); err != nil { |
| 75 |
return false |
| 76 |
} |
| 77 |
return sc1 == sc2 |
| 78 |
} |
| 79 |
if err := quick.Check(f2, quickCheckConfig1024); err != nil { |
| 80 |
t.Errorf("failed scalar->bytes->scalar round-trip: %v", err) |
| 81 |
} |
| 82 |
|
| 83 |
b := scMinusOne.s |
| 84 |
b[31] += 1 |
| 85 |
s := scOne |
| 86 |
if out, err := s.SetCanonicalBytes(b[:]); err == nil { |
| 87 |
t.Errorf("SetCanonicalBytes worked on a non-canonical value") |
| 88 |
} else if s != scOne { |
| 89 |
t.Errorf("SetCanonicalBytes modified its receiver") |
| 90 |
} else if out != nil { |
| 91 |
t.Errorf("SetCanonicalBytes did not return nil with an error") |
| 92 |
} |
| 93 |
} |
| 94 |
|
| 95 |
func TestScalarSetUniformBytes(t *testing.T) { |
| 96 |
mod, _ := new(big.Int).SetString("27742317777372353535851937790883648493", 10) |
| 97 |
mod.Add(mod, new(big.Int).Lsh(big.NewInt(1), 252)) |
| 98 |
f := func(in [64]byte, sc Scalar) bool { |
| 99 |
sc.SetUniformBytes(in[:]) |
| 100 |
if !isReduced(&sc) { |
| 101 |
return false |
| 102 |
} |
| 103 |
scBig := bigIntFromLittleEndianBytes(sc.s[:]) |
| 104 |
inBig := bigIntFromLittleEndianBytes(in[:]) |
| 105 |
return inBig.Mod(inBig, mod).Cmp(scBig) == 0 |
| 106 |
} |
| 107 |
if err := quick.Check(f, quickCheckConfig1024); err != nil { |
| 108 |
t.Error(err) |
| 109 |
} |
| 110 |
} |
| 111 |
|
| 112 |
func TestScalarSetBytesWithClamping(t *testing.T) { |
| 113 |
// Generated with libsodium.js 1.0.18 crypto_scalarmult_ed25519_base. |
| 114 |
|
| 115 |
random := "633d368491364dc9cd4c1bf891b1d59460face1644813240a313e61f2c88216e" |
| 116 |
s := new(Scalar).SetBytesWithClamping(decodeHex(random)) |
| 117 |
p := new(Point).ScalarBaseMult(s) |
| 118 |
want := "1d87a9026fd0126a5736fe1628c95dd419172b5b618457e041c9c861b2494a94" |
| 119 |
if got := hex.EncodeToString(p.Bytes()); got != want { |
| 120 |
t.Errorf("random: got %q, want %q", got, want) |
| 121 |
} |
| 122 |
|
| 123 |
zero := "0000000000000000000000000000000000000000000000000000000000000000" |
| 124 |
s = new(Scalar).SetBytesWithClamping(decodeHex(zero)) |
| 125 |
p = new(Point).ScalarBaseMult(s) |
| 126 |
want = "693e47972caf527c7883ad1b39822f026f47db2ab0e1919955b8993aa04411d1" |
| 127 |
if got := hex.EncodeToString(p.Bytes()); got != want { |
| 128 |
t.Errorf("zero: got %q, want %q", got, want) |
| 129 |
} |
| 130 |
|
| 131 |
one := "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff" |
| 132 |
s = new(Scalar).SetBytesWithClamping(decodeHex(one)) |
| 133 |
p = new(Point).ScalarBaseMult(s) |
| 134 |
want = "12e9a68b73fd5aacdbcaf3e88c46fea6ebedb1aa84eed1842f07f8edab65e3a7" |
| 135 |
if got := hex.EncodeToString(p.Bytes()); got != want { |
| 136 |
t.Errorf("one: got %q, want %q", got, want) |
| 137 |
} |
| 138 |
} |
| 139 |
|
| 140 |
func bigIntFromLittleEndianBytes(b []byte) *big.Int { |
| 141 |
bb := make([]byte, len(b)) |
| 142 |
for i := range b { |
| 143 |
bb[i] = b[len(b)-i-1] |
| 144 |
} |
| 145 |
return new(big.Int).SetBytes(bb) |
| 146 |
} |
| 147 |
|
| 148 |
func TestScalarMultiplyDistributesOverAdd(t *testing.T) { |
| 149 |
multiplyDistributesOverAdd := func(x, y, z Scalar) bool { |
| 150 |
// Compute t1 = (x+y)*z |
| 151 |
var t1 Scalar |
| 152 |
t1.Add(&x, &y) |
| 153 |
t1.Multiply(&t1, &z) |
| 154 |
|
| 155 |
// Compute t2 = x*z + y*z |
| 156 |
var t2 Scalar |
| 157 |
var t3 Scalar |
| 158 |
t2.Multiply(&x, &z) |
| 159 |
t3.Multiply(&y, &z) |
| 160 |
t2.Add(&t2, &t3) |
| 161 |
|
| 162 |
return t1 == t2 && isReduced(&t1) && isReduced(&t3) |
| 163 |
} |
| 164 |
|
| 165 |
if err := quick.Check(multiplyDistributesOverAdd, quickCheckConfig1024); err != nil { |
| 166 |
t.Error(err) |
| 167 |
} |
| 168 |
} |
| 169 |
|
| 170 |
func TestScalarAddLikeSubNeg(t *testing.T) { |
| 171 |
addLikeSubNeg := func(x, y Scalar) bool { |
| 172 |
// Compute t1 = x - y |
| 173 |
var t1 Scalar |
| 174 |
t1.Subtract(&x, &y) |
| 175 |
|
| 176 |
// Compute t2 = -y + x |
| 177 |
var t2 Scalar |
| 178 |
t2.Negate(&y) |
| 179 |
t2.Add(&t2, &x) |
| 180 |
|
| 181 |
return t1 == t2 && isReduced(&t1) |
| 182 |
} |
| 183 |
|
| 184 |
if err := quick.Check(addLikeSubNeg, quickCheckConfig1024); err != nil { |
| 185 |
t.Error(err) |
| 186 |
} |
| 187 |
} |
| 188 |
|
| 189 |
func TestScalarNonAdjacentForm(t *testing.T) { |
| 190 |
s := Scalar{[32]byte{ |
| 191 |
0x1a, 0x0e, 0x97, 0x8a, 0x90, 0xf6, 0x62, 0x2d, |
| 192 |
0x37, 0x47, 0x02, 0x3f, 0x8a, 0xd8, 0x26, 0x4d, |
| 193 |
0xa7, 0x58, 0xaa, 0x1b, 0x88, 0xe0, 0x40, 0xd1, |
| 194 |
0x58, 0x9e, 0x7b, 0x7f, 0x23, 0x76, 0xef, 0x09, |
| 195 |
}} |
| 196 |
expectedNaf := [256]int8{ |
| 197 |
0, 13, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, -9, 0, 0, 0, 0, -11, 0, 0, 0, 0, 3, 0, 0, 0, 0, 1, |
| 198 |
0, 0, 0, 0, 9, 0, 0, 0, 0, -5, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 11, 0, 0, 0, 0, 11, 0, 0, 0, 0, 0, |
| 199 |
-9, 0, 0, 0, 0, 0, -3, 0, 0, 0, 0, 9, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 9, 0, |
| 200 |
0, 0, 0, -15, 0, 0, 0, 0, -7, 0, 0, 0, 0, -9, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 13, 0, 0, 0, 0, 0, -3, 0, |
| 201 |
0, 0, 0, -11, 0, 0, 0, 0, -7, 0, 0, 0, 0, -13, 0, 0, 0, 0, 11, 0, 0, 0, 0, -9, 0, 0, 0, 0, 0, 1, 0, 0, |
| 202 |
0, 0, 0, -15, 0, 0, 0, 0, 1, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 13, 0, 0, 0, |
| 203 |
0, 0, 0, 11, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0, -9, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 7, |
| 204 |
0, 0, 0, 0, 0, -15, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 15, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, |
| 205 |
} |
| 206 |
|
| 207 |
sNaf := s.nonAdjacentForm(5) |
| 208 |
|
| 209 |
for i := 0; i < 256; i++ { |
| 210 |
if expectedNaf[i] != sNaf[i] { |
| 211 |
t.Errorf("Wrong digit at position %d, got %d, expected %d", i, sNaf[i], expectedNaf[i]) |
| 212 |
} |
| 213 |
} |
| 214 |
} |
| 215 |
|
| 216 |
type notZeroScalar Scalar |
| 217 |
|
| 218 |
func (notZeroScalar) Generate(rand *mathrand.Rand, size int) reflect.Value { |
| 219 |
var s Scalar |
| 220 |
for s == scZero { |
| 221 |
s = Scalar{}.Generate(rand, size).Interface().(Scalar) |
| 222 |
} |
| 223 |
return reflect.ValueOf(notZeroScalar(s)) |
| 224 |
} |
| 225 |
|
| 226 |
func TestScalarEqual(t *testing.T) { |
| 227 |
if scOne.Equal(&scMinusOne) == 1 { |
| 228 |
t.Errorf("scOne.Equal(&scMinusOne) is true") |
| 229 |
} |
| 230 |
if scMinusOne.Equal(&scMinusOne) == 0 { |
| 231 |
t.Errorf("scMinusOne.Equal(&scMinusOne) is false") |
| 232 |
} |
| 233 |
} |