1 package csidh
2
3 import (
4 "crypto/rand"
5 "math/big"
6 "testing"
7
8 "github.com/cloudflare/circl/internal/test"
9 )
10
11 func testFp512Mul3Nominal(t *testing.T, f func(*fp, *fp, uint64)) {
12 var mod, two64 big.Int
13
14
15 mod.SetUint64(1).Lsh(&mod, 512)
16 two64.SetUint64(1).Lsh(&two64, 64)
17
18 for i := 0; i < numIter; i++ {
19 multiplier64, _ := rand.Int(rand.Reader, &two64)
20 mul64 := multiplier64.Uint64()
21
22 fV := randomFp()
23 exp, _ := new(big.Int).SetString(fp2S(fV), 16)
24 exp.Mul(exp, multiplier64)
25
26 exp.Mod(exp, &mod)
27
28 f(&fV, &fV, mul64)
29 res, _ := new(big.Int).SetString(fp2S(fV), 16)
30
31 if exp.Cmp(res) != 0 {
32 test.ReportError(t, exp, res, fV)
33 }
34 }
35 }
36
37
38
39 func TestFp512Mul3_Nominal(t *testing.T) {
40 testFp512Mul3Nominal(t, mul512)
41 testFp512Mul3Nominal(t, mul512Generic)
42 }
43
44 func TestAddRdcRandom(t *testing.T) {
45 for i := 0; i < numIter; i++ {
46 a := randomFp()
47 bigA, _ := new(big.Int).SetString(fp2S(a), 16)
48 bigA.Mod(bigA, modulus)
49 copy(a[:], intGetU64(bigA))
50
51 b := randomFp()
52 bigB, _ := new(big.Int).SetString(fp2S(b), 16)
53 bigB.Mod(bigB, modulus)
54 copy(b[:], intGetU64(bigB))
55
56 addRdc(&a, &a, &b)
57 bigRet, _ := new(big.Int).SetString(fp2S(a), 16)
58
59 bigA.Add(bigA, bigB)
60 bigA.Mod(bigA, modulus)
61
62 if bigRet.Cmp(bigA) != 0 {
63 test.ReportError(t, bigRet, bigA, a, b)
64 }
65 }
66 }
67
68 func TestAddRdcNominal(t *testing.T) {
69 var res fp
70
71 tmp := oneFp512
72 addRdc(&res, &tmp, &p)
73 if !eqFp(&res, &tmp) {
74 t.Errorf("Wrong value\n%X", res)
75 }
76
77 tmp = zeroFp512
78 addRdc(&res, &p, &p)
79 if !eqFp(&res, &p) {
80 t.Errorf("Wrong value\n%X", res)
81 }
82
83 tmp = fp{1, 1, 1, 1, 1, 1, 1, 1}
84 addRdc(&res, &p, &tmp)
85 if !eqFp(&res, &tmp) {
86 t.Errorf("Wrong value\n%X", res)
87 }
88
89 tmp = fp{1, 1, 1, 1, 1, 1, 1, 1}
90 exp := fp{2, 2, 2, 2, 2, 2, 2, 2}
91 addRdc(&res, &tmp, &tmp)
92 if !eqFp(&res, &exp) {
93 t.Errorf("Wrong value\n%X", res)
94 }
95 }
96
97 func TestFp512Sub3_Nominal(t *testing.T) {
98 var ret fp
99 var mod big.Int
100
101 mod.SetUint64(1).Lsh(&mod, 512)
102
103 for i := 0; i < numIter; i++ {
104 a := randomFp()
105 bigA, _ := new(big.Int).SetString(fp2S(a), 16)
106 b := randomFp()
107 bigB, _ := new(big.Int).SetString(fp2S(b), 16)
108
109 sub512(&ret, &a, &b)
110 bigRet, _ := new(big.Int).SetString(fp2S(ret), 16)
111 bigA.Sub(bigA, bigB)
112
113 bigA.Mod(bigA, &mod)
114
115 if bigRet.Cmp(bigA) != 0 {
116 test.ReportError(t, bigRet, bigA, a, b)
117 }
118 }
119 }
120
121 func TestFp512Sub3_DoesntReturnCarry(t *testing.T) {
122 a := fp{}
123 b := fp{
124 0xFFFFFFFFFFFFFFFF, 1,
125 0, 0,
126 0, 0,
127 0, 0,
128 }
129 c := fp{
130 0xFFFFFFFFFFFFFFFF, 2,
131 0, 0,
132 0, 0,
133 0, 0,
134 }
135
136 if sub512(&a, &b, &c) != 1 {
137 t.Error("Carry not returned")
138 }
139 }
140
141 func TestFp512Sub3_ReturnsCarry(t *testing.T) {
142 a := fp{}
143 b := fp{
144 0xFFFFFFFFFFFFFFFF, 2,
145 0, 0,
146 0, 0,
147 0, 0,
148 }
149 c := fp{
150 0xFFFFFFFFFFFFFFFF, 1,
151 0, 0,
152 0, 0,
153 0, 0,
154 }
155
156 if sub512(&a, &b, &c) != 0 {
157 t.Error("Carry not returned")
158 }
159 }
160
161 func testCswap(t *testing.T, f func(*fp, *fp, uint8)) {
162 arg1 := randomFp()
163 arg2 := randomFp()
164
165 arg1cpy := arg1
166 f(&arg1, &arg2, 0)
167 if !eqFp(&arg1, &arg1cpy) {
168 t.Error("cswap swapped")
169 }
170
171 arg1cpy = arg1
172 f(&arg1, &arg2, 1)
173 if eqFp(&arg1, &arg1cpy) {
174 t.Error("cswap didn't swapped")
175 }
176
177 arg1cpy = arg1
178 f(&arg1, &arg2, 0xF2)
179 if eqFp(&arg1, &arg1cpy) {
180 t.Error("cswap didn't swapped")
181 }
182 }
183
184 func TestCswap(t *testing.T) {
185 testCswap(t, cswap512Generic)
186 testCswap(t, cswap512)
187 }
188
189 func TestSubRdc(t *testing.T) {
190 var res fp
191
192
193 tmp := oneFp512
194 subRdc(&res, &tmp, &tmp)
195 if !eqFp(&res, &zeroFp512) {
196 t.Errorf("Wrong value\n%X", res)
197 }
198 zero(&res)
199
200
201 exp := p
202 exp[0]--
203
204 subRdc(&res, &zeroFp512, &oneFp512)
205 if !eqFp(&res, &exp) {
206 t.Errorf("Wrong value\n%X\n%X", res, exp)
207 }
208 zero(&res)
209
210
211 pMinusOne := p
212 pMinusOne[0]--
213 subRdc(&res, &p, &pMinusOne)
214 if !eqFp(&res, &oneFp512) {
215 t.Errorf("Wrong value\n[%X != %X]", res, oneFp512)
216 }
217 zero(&res)
218
219 subRdc(&res, &p, &oneFp512)
220 if !eqFp(&res, &pMinusOne) {
221 t.Errorf("Wrong value\n[%X != %X]", res, pMinusOne)
222 }
223 }
224
225 func testMulRdc(t *testing.T, f func(*fp, *fp, *fp)) {
226 var res fp
227 m1 := fp{
228 0x85E2579C786882D0, 0x4E3433657E18DA95,
229 0x850AE5507965A0B3, 0xA15BC4E676475964,
230 }
231 m2 := fp{
232 0x85E2579C786882CF, 0x4E3433657E18DA95,
233 0x850AE5507965A0B3, 0xA15BC4E676475964,
234 }
235
236
237 m1m1 := fp{
238 0xAEBF46E92C88A4B4, 0xCFE857977B946347,
239 0xD3B264FF08493901, 0x6EEB3D23746B6C7C,
240 0xC0CA874A349D64B4, 0x7AD4A38B406F8504,
241 0x38B6B6CEB82472FB, 0x1587015FD7DDFC7D,
242 }
243 m1m2 := fp{
244 0x51534771258C4624, 0x2BFEDE86504E2160,
245 0xE8127D5E9329670B, 0x0C84DBD584491D75,
246 0x656C73C68B16E38C, 0x01C0DA470B30B8DE,
247 0x2532E3903EAA950B, 0x3F2C28EA97FE6FEC,
248 }
249
250
251 tmp := zeroFp512
252 f(&res, &tmp, &tmp)
253 if !eqFp(&res, &tmp) {
254 t.Errorf("Wrong value\n%X", res)
255 }
256
257
258 zero(&res)
259 f(&res, &m1, &one)
260 if !eqFp(&res, &m1) {
261 t.Errorf("Wrong value\n%X", res)
262 }
263
264
265 zero(&res)
266 f(&res, &m1, &m2)
267 if !eqFp(&res, &m1m2) {
268 t.Errorf("Wrong value\n%X", res)
269 }
270
271
272 zero(&res)
273 f(&res, &m1, &m1)
274 if !eqFp(&res, &m1m1) {
275 t.Errorf("Wrong value\n%X", res)
276 }
277 }
278
279 func TestMulRdc(t *testing.T) {
280 testMulRdc(t, mulRdcGeneric)
281 testMulRdc(t, mulRdc)
282 }
283
284 func TestModExp(t *testing.T) {
285 var resExp, base, exp big.Int
286 var baseFp, expFp, resFp, resFpExp fp
287
288 for i := 0; i < numIter; i++ {
289
290
291 base.SetString(fp2S(randomFp()), 16)
292 exp.SetString(fp2S(randomFp()), 16)
293 resExp.Exp(&base, &exp, modulus)
294 toMont(&base, true)
295 toMont(&resExp, true)
296
297
298 copy(baseFp[:], intGetU64(&base))
299 copy(expFp[:], intGetU64(&exp))
300 copy(resFpExp[:], intGetU64(&resExp))
301
302
303 modExpRdc512(&resFp, &baseFp, &expFp)
304
305 if !eqFp(&resFp, &resFpExp) {
306 test.ReportError(t, resFp, intGetU64(&resExp), base, exp)
307 }
308 }
309 }
310
311
312 func TestIsNonQuadRes(t *testing.T) {
313 var n, nMont big.Int
314 var pm1o2, rawP big.Int
315 var nMontFp fp
316
317
318 pm1o2.SetString("0x32da4747ba07c4dffe455868af1f26255a16841d76e446212d7dfe63499164e6d3d56362b3f9aa83a8b398660f85a792e1390dfa2bd6541a8dc0dc8299e3643d", 0)
319
320 rawP.SetString("0x65b48e8f740f89bffc8ab0d15e3e4c4ab42d083aedc88c425afbfcc69322c9cda7aac6c567f35507516730cc1f0b4f25c2721bf457aca8351b81b90533c6c87b", 0)
321
322
323 for i := uint64(1); i < uint64(numIter); i++ {
324 n.SetUint64(i)
325 n.Exp(&n, &pm1o2, &rawP)
326
327 exp := n.Cmp(big.NewInt(1))
328 if exp < 0 {
329 panic("Should never happen")
330 }
331
332 nMont.SetUint64(i)
333 toMont(&nMont, true)
334 copy(nMontFp[:], intGetU64(&nMont))
335 ret := nMontFp.isNonQuadRes()
336
337 if ret != exp {
338 toMont(&nMont, false)
339 t.Errorf("Test failed for value %s", nMont.Text(10))
340 }
341 }
342 }
343
344 func TestCheckSmaller(t *testing.T) {
345
346 pMin1 := p
347 pMin1[0]--
348
349
350 if !isLess(&pMin1, &p) {
351 t.Error("pMin1>p")
352 }
353
354
355 if isLess(&p, &pMin1) {
356 t.Error("p>pMin1")
357 }
358
359
360 if isLess(&p, &p) {
361 t.Error("p==p")
362 }
363 }
364
365 func BenchmarkFp(b *testing.B) {
366 var res, arg1 fp
367 var two64 big.Int
368 two64.SetUint64(1).Lsh(&two64, 64)
369 n, _ := rand.Int(rand.Reader, &two64)
370 u64 := n.Uint64()
371 arg2, arg3 := randomFp(), randomFp()
372 b.Run("sub512", func(b *testing.B) {
373 for n := 0; n < b.N; n++ {
374 sub512(&arg1, &arg2, &arg3)
375 }
376 })
377 b.Run("mul", func(b *testing.B) {
378 for n := 0; n < b.N; n++ {
379 mul512(&arg2, &arg3, u64)
380 }
381 })
382 b.Run("cswap", func(b *testing.B) {
383 for n := 0; n < b.N; n++ {
384 cswap512(&arg1, &arg2, uint8(n%2))
385 }
386 })
387 b.Run("add", func(b *testing.B) {
388 for n := 0; n < b.N; n++ {
389 addRdc(&res, &arg1, &arg2)
390 }
391 })
392 b.Run("sub", func(b *testing.B) {
393 for n := 0; n < b.N; n++ {
394 subRdc(&res, &arg1, &arg2)
395 }
396 })
397 b.Run("mul", func(b *testing.B) {
398 for n := 0; n < b.N; n++ {
399 mulRdc(&res, &arg1, &arg2)
400 }
401 })
402 b.Run("exp", func(b *testing.B) {
403 for n := 0; n < b.N; n++ {
404 modExpRdc512(&res, &arg1, &arg2)
405 }
406 })
407 }
408
View as plain text