1 package fp448
2
3 import (
4 "crypto/rand"
5 "fmt"
6 "math/big"
7 "testing"
8
9 "github.com/cloudflare/circl/internal/conv"
10 "github.com/cloudflare/circl/internal/test"
11 )
12
13 func testCmov(t *testing.T, f func(x, y *Elt, n uint)) {
14 const numTests = 1 << 9
15 var x, y Elt
16 for i := 0; i < numTests; i++ {
17 _, _ = rand.Read(x[:])
18 _, _ = rand.Read(y[:])
19 b := uint(y[0] & 0x1)
20 want := conv.BytesLe2BigInt(x[:])
21 if b != 0 {
22 want = conv.BytesLe2BigInt(y[:])
23 }
24
25 f(&x, &y, b)
26 got := conv.BytesLe2BigInt(x[:])
27
28 if got.Cmp(want) != 0 {
29 test.ReportError(t, got, want, x, y, b)
30 }
31 }
32 }
33
34 func testCswap(t *testing.T, f func(x, y *Elt, n uint)) {
35 const numTests = 1 << 9
36 var x, y Elt
37 for i := 0; i < numTests; i++ {
38 _, _ = rand.Read(x[:])
39 _, _ = rand.Read(y[:])
40 b := uint(y[0] & 0x1)
41 want0 := conv.BytesLe2BigInt(x[:])
42 want1 := conv.BytesLe2BigInt(y[:])
43 if b != 0 {
44 want0 = conv.BytesLe2BigInt(y[:])
45 want1 = conv.BytesLe2BigInt(x[:])
46 }
47
48 f(&x, &y, b)
49 got0 := conv.BytesLe2BigInt(x[:])
50 got1 := conv.BytesLe2BigInt(y[:])
51
52 if got0.Cmp(want0) != 0 {
53 test.ReportError(t, got0, want0, x, y, b)
54 }
55 if got1.Cmp(want1) != 0 {
56 test.ReportError(t, got1, want1, x, y, b)
57 }
58 }
59 }
60
61 func testAdd(t *testing.T, f func(z, x, y *Elt)) {
62 const numTests = 1 << 9
63 var x, y, z Elt
64 prime := P()
65 p := conv.BytesLe2BigInt(prime[:])
66 for i := 0; i < numTests; i++ {
67 _, _ = rand.Read(x[:])
68 _, _ = rand.Read(y[:])
69 f(&z, &x, &y)
70 Modp(&z)
71 got := conv.BytesLe2BigInt(z[:])
72
73 xx, yy := conv.BytesLe2BigInt(x[:]), conv.BytesLe2BigInt(y[:])
74 want := xx.Add(xx, yy).Mod(xx, p)
75
76 if got.Cmp(want) != 0 {
77 test.ReportError(t, got, want, x, y)
78 }
79 }
80 }
81
82 func testSub(t *testing.T, f func(z, x, y *Elt)) {
83 const numTests = 1 << 9
84 var x, y, z Elt
85 prime := P()
86 p := conv.BytesLe2BigInt(prime[:])
87 for i := 0; i < numTests; i++ {
88 _, _ = rand.Read(x[:])
89 _, _ = rand.Read(y[:])
90 f(&z, &x, &y)
91 Modp(&z)
92 got := conv.BytesLe2BigInt(z[:])
93
94 xx, yy := conv.BytesLe2BigInt(x[:]), conv.BytesLe2BigInt(y[:])
95 want := xx.Sub(xx, yy).Mod(xx, p)
96
97 if got.Cmp(want) != 0 {
98 test.ReportError(t, got, want, x, y)
99 }
100 }
101 }
102
103 func testAddSub(t *testing.T, f func(x, y *Elt)) {
104 const numTests = 1 << 9
105 var x, y Elt
106 prime := P()
107 p := conv.BytesLe2BigInt(prime[:])
108 want0, want1 := big.NewInt(0), big.NewInt(0)
109 for i := 0; i < numTests; i++ {
110 _, _ = rand.Read(x[:])
111 _, _ = rand.Read(y[:])
112 xx, yy := conv.BytesLe2BigInt(x[:]), conv.BytesLe2BigInt(y[:])
113 want0.Add(xx, yy).Mod(want0, p)
114 want1.Sub(xx, yy).Mod(want1, p)
115
116 f(&x, &y)
117 Modp(&x)
118 Modp(&y)
119 got0 := conv.BytesLe2BigInt(x[:])
120 got1 := conv.BytesLe2BigInt(y[:])
121
122 if got0.Cmp(want0) != 0 {
123 test.ReportError(t, got0, want0, x, y)
124 }
125 if got1.Cmp(want1) != 0 {
126 test.ReportError(t, got1, want1, x, y)
127 }
128 }
129 }
130
131 func testMul(t *testing.T, f func(z, x, y *Elt)) {
132 const numTests = 1 << 9
133 var x, y, z Elt
134 prime := P()
135 p := conv.BytesLe2BigInt(prime[:])
136 for i := 0; i < numTests; i++ {
137 _, _ = rand.Read(x[:])
138 _, _ = rand.Read(y[:])
139 f(&z, &x, &y)
140 Modp(&z)
141 got := conv.BytesLe2BigInt(z[:])
142
143 xx, yy := conv.BytesLe2BigInt(x[:]), conv.BytesLe2BigInt(y[:])
144 want := xx.Mul(xx, yy).Mod(xx, p)
145
146 if got.Cmp(want) != 0 {
147 test.ReportError(t, got, want, x, y)
148 }
149 }
150 }
151
152 func testSqr(t *testing.T, f func(z, x *Elt)) {
153 const numTests = 1 << 9
154 var x, z Elt
155 prime := P()
156 p := conv.BytesLe2BigInt(prime[:])
157 for i := 0; i < numTests; i++ {
158 _, _ = rand.Read(x[:])
159 f(&z, &x)
160 Modp(&z)
161 got := conv.BytesLe2BigInt(z[:])
162
163 xx := conv.BytesLe2BigInt(x[:])
164 want := xx.Mul(xx, xx).Mod(xx, p)
165
166 if got.Cmp(want) != 0 {
167 test.ReportError(t, got, want, x)
168 }
169 }
170 }
171
172 func TestModp(t *testing.T) {
173 const numTests = 1 << 9
174 var x Elt
175 prime := P()
176 p := conv.BytesLe2BigInt(prime[:])
177 two256 := big.NewInt(1)
178 two256.Lsh(two256, 256)
179 want := new(big.Int)
180 for i := 0; i < numTests; i++ {
181 bigX, _ := rand.Int(rand.Reader, two256)
182 bigX.Add(bigX, p).Mod(bigX, two256)
183 conv.BigInt2BytesLe(x[:], bigX)
184
185 Modp(&x)
186 got := conv.BytesLe2BigInt(x[:])
187
188 want.Mod(bigX, p)
189
190 if got.Cmp(want) != 0 {
191 test.ReportError(t, got, want, bigX)
192 }
193 }
194 }
195
196 func TestIsZero(t *testing.T) {
197 var x Elt
198 got := IsZero(&x)
199 want := true
200 if got != want {
201 test.ReportError(t, got, want, x)
202 }
203
204 SetOne(&x)
205 got = IsZero(&x)
206 want = false
207 if got != want {
208 test.ReportError(t, got, want, x)
209 }
210
211 x = P()
212 got = IsZero(&x)
213 want = true
214 if got != want {
215 test.ReportError(t, got, want, x)
216 }
217 }
218
219 func TestToBytes(t *testing.T) {
220 const numTests = 1 << 9
221 var x Elt
222 var got, want [Size]byte
223 for i := 0; i < numTests; i++ {
224 _, _ = rand.Read(x[:])
225 err := ToBytes(got[:], &x)
226 conv.BigInt2BytesLe(want[:], conv.BytesLe2BigInt(x[:]))
227
228 if err != nil || got != want {
229 test.ReportError(t, got, want, x)
230 }
231 }
232 var largeSlice [Size + 1]byte
233 err := ToBytes(largeSlice[:], &x)
234 if err == nil {
235 test.ReportError(t, got, want, largeSlice)
236 }
237 }
238
239 func TestString(t *testing.T) {
240 const numTests = 1 << 9
241 var x Elt
242 var bigX big.Int
243 for i := 0; i < numTests; i++ {
244 _, _ = rand.Read(x[:])
245 got, _ := bigX.SetString(fmt.Sprint(x), 0)
246 want := conv.BytesLe2BigInt(x[:])
247
248 if got.Cmp(want) != 0 {
249 test.ReportError(t, got, want, x)
250 }
251 }
252 }
253
254 func TestNeg(t *testing.T) {
255 const numTests = 1 << 9
256 var x, z Elt
257 prime := P()
258 p := conv.BytesLe2BigInt(prime[:])
259 for i := 0; i < numTests; i++ {
260 _, _ = rand.Read(x[:])
261 Neg(&z, &x)
262 Modp(&z)
263 got := conv.BytesLe2BigInt(z[:])
264
265 bigX := conv.BytesLe2BigInt(x[:])
266 want := bigX.Neg(bigX).Mod(bigX, p)
267
268 if got.Cmp(want) != 0 {
269 test.ReportError(t, got, want, bigX)
270 }
271 }
272 }
273
274 func TestInv(t *testing.T) {
275 const numTests = 1 << 9
276 var x, z Elt
277 prime := P()
278 p := conv.BytesLe2BigInt(prime[:])
279 for i := 0; i < numTests; i++ {
280 _, _ = rand.Read(x[:])
281 Inv(&z, &x)
282 Modp(&z)
283 got := conv.BytesLe2BigInt(z[:])
284
285 xx := conv.BytesLe2BigInt(x[:])
286 want := xx.ModInverse(xx, p)
287
288 if got.Cmp(want) != 0 {
289 test.ReportError(t, got, want, x)
290 }
291 }
292 }
293
294 func TestInvSqrt(t *testing.T) {
295 const numTests = 1 << 9
296 var x, y, z Elt
297 prime := P()
298 p := conv.BytesLe2BigInt(prime[:])
299 exp := big.NewInt(1)
300 exp.Add(p, exp).Rsh(exp, 2)
301 var frac, root, sqRoot big.Int
302 var wantQR bool
303 var want *big.Int
304 for i := 0; i < numTests; i++ {
305 _, _ = rand.Read(x[:])
306 _, _ = rand.Read(y[:])
307
308 gotQR := InvSqrt(&z, &x, &y)
309 Modp(&z)
310 got := conv.BytesLe2BigInt(z[:])
311
312 xx := conv.BytesLe2BigInt(x[:])
313 yy := conv.BytesLe2BigInt(y[:])
314 frac.ModInverse(yy, p).Mul(&frac, xx).Mod(&frac, p)
315 root.Exp(&frac, exp, p)
316 sqRoot.Mul(&root, &root).Mod(&sqRoot, p)
317
318 if sqRoot.Cmp(&frac) == 0 {
319 want = &root
320 wantQR = true
321 } else {
322 want = big.NewInt(0)
323 wantQR = false
324 }
325
326 if wantQR {
327 if gotQR != wantQR || got.Cmp(want) != 0 {
328 test.ReportError(t, got, want, x, y)
329 }
330 } else {
331 if gotQR != wantQR {
332 test.ReportError(t, gotQR, wantQR, x, y)
333 }
334 }
335 }
336 }
337
338 func TestGeneric(t *testing.T) {
339 t.Run("Cmov", func(t *testing.T) { testCmov(t, cmovGeneric) })
340 t.Run("Cswap", func(t *testing.T) { testCswap(t, cswapGeneric) })
341 t.Run("Add", func(t *testing.T) { testAdd(t, addGeneric) })
342 t.Run("Sub", func(t *testing.T) { testSub(t, subGeneric) })
343 t.Run("AddSub", func(t *testing.T) { testAddSub(t, addsubGeneric) })
344 t.Run("Mul", func(t *testing.T) { testMul(t, mulGeneric) })
345 t.Run("Sqr", func(t *testing.T) { testSqr(t, sqrGeneric) })
346 }
347
348 func TestNative(t *testing.T) {
349 t.Run("Cmov", func(t *testing.T) { testCmov(t, Cmov) })
350 t.Run("Cswap", func(t *testing.T) { testCswap(t, Cswap) })
351 t.Run("Add", func(t *testing.T) { testAdd(t, Add) })
352 t.Run("Sub", func(t *testing.T) { testSub(t, Sub) })
353 t.Run("AddSub", func(t *testing.T) { testAddSub(t, AddSub) })
354 t.Run("Mul", func(t *testing.T) { testMul(t, Mul) })
355 t.Run("Sqr", func(t *testing.T) { testSqr(t, Sqr) })
356 }
357
358 func BenchmarkFp(b *testing.B) {
359 var x, y, z Elt
360 _, _ = rand.Read(x[:])
361 _, _ = rand.Read(y[:])
362 _, _ = rand.Read(z[:])
363 b.Run("Add", func(b *testing.B) {
364 for i := 0; i < b.N; i++ {
365 Add(&x, &y, &z)
366 }
367 })
368 b.Run("Sub", func(b *testing.B) {
369 for i := 0; i < b.N; i++ {
370 Sub(&x, &y, &z)
371 }
372 })
373 b.Run("Mul", func(b *testing.B) {
374 for i := 0; i < b.N; i++ {
375 Mul(&x, &y, &z)
376 }
377 })
378 b.Run("Sqr", func(b *testing.B) {
379 for i := 0; i < b.N; i++ {
380 Sqr(&x, &y)
381 }
382 })
383 b.Run("Inv", func(b *testing.B) {
384 for i := 0; i < b.N; i++ {
385 Inv(&x, &y)
386 }
387 })
388 b.Run("InvSqrt", func(b *testing.B) {
389 for i := 0; i < b.N; i++ {
390 _ = InvSqrt(&z, &x, &y)
391 }
392 })
393 }
394
View as plain text