Debian Codegraph @

libgo/go/crypto/ed25519/internal/edwards25519/scalar_test.go

raw
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 }