The Tor Browser / file comparison

comparison: security/nss/lib/freebl/ecl/tests/ecp_fpt.c

security/nss/lib/freebl/ecl/tests/ecp_fpt.c

branch
TOR_BUG_9701
changeset 15
b8a032363ba2
equal deleted inserted replaced
-1:000000000000 0:f10333783813
1 /* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
4
5 #include "ecp_fp.h"
6 #include "mpprime.h"
7
8 #include <stdio.h>
9 #include <time.h>
10 #include <sys/time.h>
11 #include <sys/resource.h>
12
13 /* Time k repetitions of operation op. */
14 #define M_TimeOperation(op, k) { \
15 double dStart, dNow, dUserTime; \
16 struct rusage ru; \
17 int i; \
18 getrusage(RUSAGE_SELF, &ru); \
19 dStart = (double)ru.ru_utime.tv_sec+(double)ru.ru_utime.tv_usec*0.000001; \
20 for (i = 0; i < k; i++) { \
21 { op; } \
22 }; \
23 getrusage(RUSAGE_SELF, &ru); \
24 dNow = (double)ru.ru_utime.tv_sec+(double)ru.ru_utime.tv_usec*0.000001; \
25 dUserTime = dNow-dStart; \
26 if (dUserTime) printf(" %-45s\n k: %6i, t: %6.2f sec, k/t: %6.2f ops/sec\n", #op, k, dUserTime, k/dUserTime); \
27 }
28
29 /* Test curve using specific floating point field arithmetic. */
30 #define M_TestCurve(name_c, name) { \
31 printf("Testing %s using specific floating point implementation...\n", name_c); \
32 ECGroup_free(ecgroup); \
33 ecgroup = ECGroup_fromName(name); \
34 if (ecgroup == NULL) { \
35 printf(" Warning: could not construct group.\n"); \
36 printf("%s failed.\n", name_c); \
37 res = MP_NO; \
38 goto CLEANUP; \
39 } else { \
40 MP_CHECKOK( testCurve(ecgroup)); \
41 printf("%s passed.\n", name_c); \
42 } \
43 }
44
45 /* Outputs a floating point double (currently not used) */
46 void
47 d_output(const double *u, int len, char *name, const EC_group_fp * group)
48 {
49 int i;
50
51 printf("%s: ", name);
52 for (i = 0; i < len; i++) {
53 printf("+ %.2f * 2^%i ", u[i] / ecfp_exp[i],
54 group->doubleBitSize * i);
55 }
56 printf("\n");
57 }
58
59 /* Tests a point p in Jacobian coordinates, comparing against the
60 * expected affine result (x, y). */
61 mp_err
62 testJacPoint(ecfp_jac_pt * p, mp_int *x, mp_int *y, ECGroup *ecgroup)
63 {
64 char s[1000];
65 mp_int rx, ry, rz;
66 mp_err res = MP_OKAY;
67
68 MP_DIGITS(&rx) = 0;
69 MP_DIGITS(&ry) = 0;
70 MP_DIGITS(&rz) = 0;
71
72 MP_CHECKOK(mp_init(&rx));
73 MP_CHECKOK(mp_init(&ry));
74 MP_CHECKOK(mp_init(&rz));
75
76 ecfp_fp2i(&rx, p->x, ecgroup);
77 ecfp_fp2i(&ry, p->y, ecgroup);
78 ecfp_fp2i(&rz, p->z, ecgroup);
79
80 /* convert result R to affine coordinates */
81 ec_GFp_pt_jac2aff(&rx, &ry, &rz, &rx, &ry, ecgroup);
82
83 /* Compare to expected result */
84 if ((mp_cmp(&rx, x) != 0) || (mp_cmp(&ry, y) != 0)) {
85 printf(" Error: Jacobian Floating Point Incorrect.\n");
86 MP_CHECKOK(mp_toradix(&rx, s, 16));
87 printf("floating point result\nrx %s\n", s);
88 MP_CHECKOK(mp_toradix(&ry, s, 16));
89 printf("ry %s\n", s);
90 MP_CHECKOK(mp_toradix(x, s, 16));
91 printf("integer result\nx %s\n", s);
92 MP_CHECKOK(mp_toradix(y, s, 16));
93 printf("y %s\n", s);
94 res = MP_NO;
95 goto CLEANUP;
96 }
97
98 CLEANUP:
99 mp_clear(&rx);
100 mp_clear(&ry);
101 mp_clear(&rz);
102
103 return res;
104 }
105
106 /* Tests a point p in Chudnovsky Jacobian coordinates, comparing against
107 * the expected affine result (x, y). */
108 mp_err
109 testChudPoint(ecfp_chud_pt * p, mp_int *x, mp_int *y, ECGroup *ecgroup)
110 {
111
112 char s[1000];
113 mp_int rx, ry, rz, rz2, rz3, test;
114 mp_err res = MP_OKAY;
115
116 /* Initialization */
117 MP_DIGITS(&rx) = 0;
118 MP_DIGITS(&ry) = 0;
119 MP_DIGITS(&rz) = 0;
120 MP_DIGITS(&rz2) = 0;
121 MP_DIGITS(&rz3) = 0;
122 MP_DIGITS(&test) = 0;
123
124 MP_CHECKOK(mp_init(&rx));
125 MP_CHECKOK(mp_init(&ry));
126 MP_CHECKOK(mp_init(&rz));
127 MP_CHECKOK(mp_init(&rz2));
128 MP_CHECKOK(mp_init(&rz3));
129 MP_CHECKOK(mp_init(&test));
130
131 /* Convert to integers */
132 ecfp_fp2i(&rx, p->x, ecgroup);
133 ecfp_fp2i(&ry, p->y, ecgroup);
134 ecfp_fp2i(&rz, p->z, ecgroup);
135 ecfp_fp2i(&rz2, p->z2, ecgroup);
136 ecfp_fp2i(&rz3, p->z3, ecgroup);
137
138 /* Verify z2, z3 are valid */
139 mp_sqrmod(&rz, &ecgroup->meth->irr, &test);
140 if (mp_cmp(&test, &rz2) != 0) {
141 printf(" Error: rzp2 not valid\n");
142 res = MP_NO;
143 goto CLEANUP;
144 }
145 mp_mulmod(&test, &rz, &ecgroup->meth->irr, &test);
146 if (mp_cmp(&test, &rz3) != 0) {
147 printf(" Error: rzp2 not valid\n");
148 res = MP_NO;
149 goto CLEANUP;
150 }
151
152 /* convert result R to affine coordinates */
153 ec_GFp_pt_jac2aff(&rx, &ry, &rz, &rx, &ry, ecgroup);
154
155 /* Compare against expected result */
156 if ((mp_cmp(&rx, x) != 0) || (mp_cmp(&ry, y) != 0)) {
157 printf(" Error: Chudnovsky Floating Point Incorrect.\n");
158 MP_CHECKOK(mp_toradix(&rx, s, 16));
159 printf("floating point result\nrx %s\n", s);
160 MP_CHECKOK(mp_toradix(&ry, s, 16));
161 printf("ry %s\n", s);
162 MP_CHECKOK(mp_toradix(x, s, 16));
163 printf("integer result\nx %s\n", s);
164 MP_CHECKOK(mp_toradix(y, s, 16));
165 printf("y %s\n", s);
166 res = MP_NO;
167 goto CLEANUP;
168 }
169
170 CLEANUP:
171 mp_clear(&rx);
172 mp_clear(&ry);
173 mp_clear(&rz);
174 mp_clear(&rz2);
175 mp_clear(&rz3);
176 mp_clear(&test);
177
178 return res;
179 }
180
181 /* Tests a point p in Modified Jacobian coordinates, comparing against the
182 * expected affine result (x, y). */
183 mp_err
184 testJmPoint(ecfp_jm_pt * r, mp_int *x, mp_int *y, ECGroup *ecgroup)
185 {
186
187 char s[1000];
188 mp_int rx, ry, rz, raz4, test;
189 mp_err res = MP_OKAY;
190
191 /* Initialization */
192 MP_DIGITS(&rx) = 0;
193 MP_DIGITS(&ry) = 0;
194 MP_DIGITS(&rz) = 0;
195 MP_DIGITS(&raz4) = 0;
196 MP_DIGITS(&test) = 0;
197
198 MP_CHECKOK(mp_init(&rx));
199 MP_CHECKOK(mp_init(&ry));
200 MP_CHECKOK(mp_init(&rz));
201 MP_CHECKOK(mp_init(&raz4));
202 MP_CHECKOK(mp_init(&test));
203
204 /* Convert to integer */
205 ecfp_fp2i(&rx, r->x, ecgroup);
206 ecfp_fp2i(&ry, r->y, ecgroup);
207 ecfp_fp2i(&rz, r->z, ecgroup);
208 ecfp_fp2i(&raz4, r->az4, ecgroup);
209
210 /* Verify raz4 = rz^4 * a */
211 mp_sqrmod(&rz, &ecgroup->meth->irr, &test);
212 mp_sqrmod(&test, &ecgroup->meth->irr, &test);
213 mp_mulmod(&test, &ecgroup->curvea, &ecgroup->meth->irr, &test);
214 if (mp_cmp(&test, &raz4) != 0) {
215 printf(" Error: a*z^4 not valid\n");
216 MP_CHECKOK(mp_toradix(&ecgroup->curvea, s, 16));
217 printf("a %s\n", s);
218 MP_CHECKOK(mp_toradix(&rz, s, 16));
219 printf("rz %s\n", s);
220 MP_CHECKOK(mp_toradix(&raz4, s, 16));
221 printf("raz4 %s\n", s);
222 res = MP_NO;
223 goto CLEANUP;
224 }
225
226 /* convert result R to affine coordinates */
227 ec_GFp_pt_jac2aff(&rx, &ry, &rz, &rx, &ry, ecgroup);
228
229 /* Compare against expected result */
230 if ((mp_cmp(&rx, x) != 0) || (mp_cmp(&ry, y) != 0)) {
231 printf(" Error: Modified Jacobian Floating Point Incorrect.\n");
232 MP_CHECKOK(mp_toradix(&rx, s, 16));
233 printf("floating point result\nrx %s\n", s);
234 MP_CHECKOK(mp_toradix(&ry, s, 16));
235 printf("ry %s\n", s);
236 MP_CHECKOK(mp_toradix(x, s, 16));
237 printf("integer result\nx %s\n", s);
238 MP_CHECKOK(mp_toradix(y, s, 16));
239 printf("y %s\n", s);
240 res = MP_NO;
241 goto CLEANUP;
242 }
243 CLEANUP:
244 mp_clear(&rx);
245 mp_clear(&ry);
246 mp_clear(&rz);
247 mp_clear(&raz4);
248 mp_clear(&test);
249
250 return res;
251 }
252
253 /* Tests point addition of Jacobian + Affine -> Jacobian */
254 mp_err
255 testPointAddJacAff(ECGroup *ecgroup)
256 {
257 mp_err res;
258 mp_int pz, rx2, ry2, rz2;
259 ecfp_jac_pt p, r;
260 ecfp_aff_pt q;
261 EC_group_fp *group = (EC_group_fp *) ecgroup->extra1;
262
263 /* Init */
264 MP_DIGITS(&pz) = 0;
265 MP_DIGITS(&rx2) = 0;
266 MP_DIGITS(&ry2) = 0;
267 MP_DIGITS(&rz2) = 0;
268 MP_CHECKOK(mp_init(&pz));
269 MP_CHECKOK(mp_init(&rx2));
270 MP_CHECKOK(mp_init(&ry2));
271 MP_CHECKOK(mp_init(&rz2));
272
273 MP_CHECKOK(mp_set_int(&pz, 5));
274
275 /* Set p */
276 ecfp_i2fp(p.x, &ecgroup->genx, ecgroup);
277 ecfp_i2fp(p.y, &ecgroup->geny, ecgroup);
278 ecfp_i2fp(p.z, &pz, ecgroup);
279 /* Set q */
280 ecfp_i2fp(q.x, &ecgroup->geny, ecgroup);
281 ecfp_i2fp(q.y, &ecgroup->genx, ecgroup);
282
283 /* Do calculations */
284 group->pt_add_jac_aff(&p, &q, &r, group);
285
286 /* Do calculation in integer to compare against */
287 MP_CHECKOK(ec_GFp_pt_add_jac_aff
288 (&ecgroup->genx, &ecgroup->geny, &pz, &ecgroup->geny,
289 &ecgroup->genx, &rx2, &ry2, &rz2, ecgroup));
290 /* convert result R to affine coordinates */
291 ec_GFp_pt_jac2aff(&rx2, &ry2, &rz2, &rx2, &ry2, ecgroup);
292
293 MP_CHECKOK(testJacPoint(&r, &rx2, &ry2, ecgroup));
294
295 CLEANUP:
296 if (res == MP_OKAY)
297 printf(" Test Passed - Point Addition - Jacobian & Affine\n");
298 else
299 printf("TEST FAILED - Point Addition - Jacobian & Affine\n");
300
301 mp_clear(&pz);
302 mp_clear(&rx2);
303 mp_clear(&ry2);
304 mp_clear(&rz2);
305
306 return res;
307 }
308
309 /* Tests point addition in Jacobian coordinates */
310 mp_err
311 testPointAddJac(ECGroup *ecgroup)
312 {
313 mp_err res;
314 mp_int pz, qz, qx, qy, rx2, ry2, rz2;
315 ecfp_jac_pt p, q, r;
316 EC_group_fp *group = (EC_group_fp *) ecgroup->extra1;
317
318 /* Init */
319 MP_DIGITS(&pz) = 0;
320 MP_DIGITS(&qx) = 0;
321 MP_DIGITS(&qy) = 0;
322 MP_DIGITS(&qz) = 0;
323 MP_DIGITS(&rx2) = 0;
324 MP_DIGITS(&ry2) = 0;
325 MP_DIGITS(&rz2) = 0;
326 MP_CHECKOK(mp_init(&pz));
327 MP_CHECKOK(mp_init(&qx));
328 MP_CHECKOK(mp_init(&qy));
329 MP_CHECKOK(mp_init(&qz));
330 MP_CHECKOK(mp_init(&rx2));
331 MP_CHECKOK(mp_init(&ry2));
332 MP_CHECKOK(mp_init(&rz2));
333
334 MP_CHECKOK(mp_set_int(&pz, 5));
335 MP_CHECKOK(mp_set_int(&qz, 105));
336
337 /* Set p */
338 ecfp_i2fp(p.x, &ecgroup->genx, ecgroup);
339 ecfp_i2fp(p.y, &ecgroup->geny, ecgroup);
340 ecfp_i2fp(p.z, &pz, ecgroup);
341 /* Set q */
342 ecfp_i2fp(q.x, &ecgroup->geny, ecgroup);
343 ecfp_i2fp(q.y, &ecgroup->genx, ecgroup);
344 ecfp_i2fp(q.z, &qz, ecgroup);
345
346 /* Do calculations */
347 group->pt_add_jac(&p, &q, &r, group);
348
349 /* Do calculation in integer to compare against */
350 ec_GFp_pt_jac2aff(&ecgroup->geny, &ecgroup->genx, &qz, &qx, &qy,
351 ecgroup);
352 MP_CHECKOK(ec_GFp_pt_add_jac_aff
353 (&ecgroup->genx, &ecgroup->geny, &pz, &qx, &qy, &rx2, &ry2,
354 &rz2, ecgroup));
355 /* convert result R to affine coordinates */
356 ec_GFp_pt_jac2aff(&rx2, &ry2, &rz2, &rx2, &ry2, ecgroup);
357
358 MP_CHECKOK(testJacPoint(&r, &rx2, &ry2, ecgroup));
359
360 CLEANUP:
361 if (res == MP_OKAY)
362 printf(" Test Passed - Point Addition - Jacobian\n");
363 else
364 printf("TEST FAILED - Point Addition - Jacobian\n");
365
366 mp_clear(&pz);
367 mp_clear(&qx);
368 mp_clear(&qy);
369 mp_clear(&qz);
370 mp_clear(&rx2);
371 mp_clear(&ry2);
372 mp_clear(&rz2);
373
374 return res;
375 }
376
377 /* Tests point addition in Chudnovsky Jacobian Coordinates */
378 mp_err
379 testPointAddChud(ECGroup *ecgroup)
380 {
381 mp_err res;
382 mp_int rx2, ry2, ix, iy, iz, test, pz, qx, qy, qz;
383 ecfp_chud_pt p, q, r;
384 EC_group_fp *group = (EC_group_fp *) ecgroup->extra1;
385
386 MP_DIGITS(&qx) = 0;
387 MP_DIGITS(&qy) = 0;
388 MP_DIGITS(&qz) = 0;
389 MP_DIGITS(&pz) = 0;
390 MP_DIGITS(&rx2) = 0;
391 MP_DIGITS(&ry2) = 0;
392 MP_DIGITS(&ix) = 0;
393 MP_DIGITS(&iy) = 0;
394 MP_DIGITS(&iz) = 0;
395 MP_DIGITS(&test) = 0;
396
397 MP_CHECKOK(mp_init(&qx));
398 MP_CHECKOK(mp_init(&qy));
399 MP_CHECKOK(mp_init(&qz));
400 MP_CHECKOK(mp_init(&pz));
401 MP_CHECKOK(mp_init(&rx2));
402 MP_CHECKOK(mp_init(&ry2));
403 MP_CHECKOK(mp_init(&ix));
404 MP_CHECKOK(mp_init(&iy));
405 MP_CHECKOK(mp_init(&iz));
406 MP_CHECKOK(mp_init(&test));
407
408 /* Test Chudnovsky form addition */
409 /* Set p */
410 MP_CHECKOK(mp_set_int(&pz, 5));
411 ecfp_i2fp(p.x, &ecgroup->genx, ecgroup);
412 ecfp_i2fp(p.y, &ecgroup->geny, ecgroup);
413 ecfp_i2fp(p.z, &pz, ecgroup);
414 mp_sqrmod(&pz, &ecgroup->meth->irr, &test);
415 ecfp_i2fp(p.z2, &test, ecgroup);
416 mp_mulmod(&test, &pz, &ecgroup->meth->irr, &test);
417 ecfp_i2fp(p.z3, &test, ecgroup);
418
419 /* Set q */
420 MP_CHECKOK(mp_set_int(&qz, 105));
421 ecfp_i2fp(q.x, &ecgroup->geny, ecgroup);
422 ecfp_i2fp(q.y, &ecgroup->genx, ecgroup);
423 ecfp_i2fp(q.z, &qz, ecgroup);
424 mp_sqrmod(&qz, &ecgroup->meth->irr, &test);
425 ecfp_i2fp(q.z2, &test, ecgroup);
426 mp_mulmod(&test, &qz, &ecgroup->meth->irr, &test);
427 ecfp_i2fp(q.z3, &test, ecgroup);
428
429 group->pt_add_chud(&p, &q, &r, group);
430
431 /* Calculate addition to compare against */
432 ec_GFp_pt_jac2aff(&ecgroup->geny, &ecgroup->genx, &qz, &qx, &qy,
433 ecgroup);
434 ec_GFp_pt_add_jac_aff(&ecgroup->genx, &ecgroup->geny, &pz, &qx, &qy,
435 &ix, &iy, &iz, ecgroup);
436 ec_GFp_pt_jac2aff(&ix, &iy, &iz, &rx2, &ry2, ecgroup);
437
438 MP_CHECKOK(testChudPoint(&r, &rx2, &ry2, ecgroup));
439
440 CLEANUP:
441 if (res == MP_OKAY)
442 printf(" Test Passed - Point Addition - Chudnovsky Jacobian\n");
443 else
444 printf("TEST FAILED - Point Addition - Chudnovsky Jacobian\n");
445
446 mp_clear(&qx);
447 mp_clear(&qy);
448 mp_clear(&qz);
449 mp_clear(&pz);
450 mp_clear(&rx2);
451 mp_clear(&ry2);
452 mp_clear(&ix);
453 mp_clear(&iy);
454 mp_clear(&iz);
455 mp_clear(&test);
456
457 return res;
458 }
459
460 /* Tests point addition in Modified Jacobian + Chudnovsky Jacobian ->
461 * Modified Jacobian coordinates. */
462 mp_err
463 testPointAddJmChud(ECGroup *ecgroup)
464 {
465 mp_err res;
466 mp_int rx2, ry2, ix, iy, iz, test, pz, paz4, qx, qy, qz;
467 ecfp_chud_pt q;
468 ecfp_jm_pt p, r;
469 EC_group_fp *group = (EC_group_fp *) ecgroup->extra1;
470
471 MP_DIGITS(&qx) = 0;
472 MP_DIGITS(&qy) = 0;
473 MP_DIGITS(&qz) = 0;
474 MP_DIGITS(&pz) = 0;
475 MP_DIGITS(&paz4) = 0;
476 MP_DIGITS(&iz) = 0;
477 MP_DIGITS(&rx2) = 0;
478 MP_DIGITS(&ry2) = 0;
479 MP_DIGITS(&ix) = 0;
480 MP_DIGITS(&iy) = 0;
481 MP_DIGITS(&iz) = 0;
482 MP_DIGITS(&test) = 0;
483
484 MP_CHECKOK(mp_init(&qx));
485 MP_CHECKOK(mp_init(&qy));
486 MP_CHECKOK(mp_init(&qz));
487 MP_CHECKOK(mp_init(&pz));
488 MP_CHECKOK(mp_init(&paz4));
489 MP_CHECKOK(mp_init(&rx2));
490 MP_CHECKOK(mp_init(&ry2));
491 MP_CHECKOK(mp_init(&ix));
492 MP_CHECKOK(mp_init(&iy));
493 MP_CHECKOK(mp_init(&iz));
494 MP_CHECKOK(mp_init(&test));
495
496 /* Test Modified Jacobian form addition */
497 /* Set p */
498 ecfp_i2fp(p.x, &ecgroup->genx, ecgroup);
499 ecfp_i2fp(p.y, &ecgroup->geny, ecgroup);
500 ecfp_i2fp(group->curvea, &ecgroup->curvea, ecgroup);
501 /* paz4 = az^4 */
502 MP_CHECKOK(mp_set_int(&pz, 5));
503 mp_sqrmod(&pz, &ecgroup->meth->irr, &paz4);
504 mp_sqrmod(&paz4, &ecgroup->meth->irr, &paz4);
505 mp_mulmod(&paz4, &ecgroup->curvea, &ecgroup->meth->irr, &paz4);
506 ecfp_i2fp(p.z, &pz, ecgroup);
507 ecfp_i2fp(p.az4, &paz4, ecgroup);
508
509 /* Set q */
510 MP_CHECKOK(mp_set_int(&qz, 105));
511 ecfp_i2fp(q.x, &ecgroup->geny, ecgroup);
512 ecfp_i2fp(q.y, &ecgroup->genx, ecgroup);
513 ecfp_i2fp(q.z, &qz, ecgroup);
514 mp_sqrmod(&qz, &ecgroup->meth->irr, &test);
515 ecfp_i2fp(q.z2, &test, ecgroup);
516 mp_mulmod(&test, &qz, &ecgroup->meth->irr, &test);
517 ecfp_i2fp(q.z3, &test, ecgroup);
518
519 /* Do calculation */
520 group->pt_add_jm_chud(&p, &q, &r, group);
521
522 /* Calculate addition to compare against */
523 ec_GFp_pt_jac2aff(&ecgroup->geny, &ecgroup->genx, &qz, &qx, &qy,
524 ecgroup);
525 ec_GFp_pt_add_jac_aff(&ecgroup->genx, &ecgroup->geny, &pz, &qx, &qy,
526 &ix, &iy, &iz, ecgroup);
527 ec_GFp_pt_jac2aff(&ix, &iy, &iz, &rx2, &ry2, ecgroup);
528
529 MP_CHECKOK(testJmPoint(&r, &rx2, &ry2, ecgroup));
530
531 CLEANUP:
532 if (res == MP_OKAY)
533 printf
534 (" Test Passed - Point Addition - Modified & Chudnovsky Jacobian\n");
535 else
536 printf
537 ("TEST FAILED - Point Addition - Modified & Chudnovsky Jacobian\n");
538
539 mp_clear(&qx);
540 mp_clear(&qy);
541 mp_clear(&qz);
542 mp_clear(&pz);
543 mp_clear(&paz4);
544 mp_clear(&rx2);
545 mp_clear(&ry2);
546 mp_clear(&ix);
547 mp_clear(&iy);
548 mp_clear(&iz);
549 mp_clear(&test);
550
551 return res;
552 }
553
554 /* Tests point doubling in Modified Jacobian coordinates */
555 mp_err
556 testPointDoubleJm(ECGroup *ecgroup)
557 {
558 mp_err res;
559 mp_int pz, paz4, rx2, ry2, rz2, raz4;
560 ecfp_jm_pt p, r;
561 EC_group_fp *group = (EC_group_fp *) ecgroup->extra1;
562
563 MP_DIGITS(&pz) = 0;
564 MP_DIGITS(&paz4) = 0;
565 MP_DIGITS(&rx2) = 0;
566 MP_DIGITS(&ry2) = 0;
567 MP_DIGITS(&rz2) = 0;
568 MP_DIGITS(&raz4) = 0;
569
570 MP_CHECKOK(mp_init(&pz));
571 MP_CHECKOK(mp_init(&paz4));
572 MP_CHECKOK(mp_init(&rx2));
573 MP_CHECKOK(mp_init(&ry2));
574 MP_CHECKOK(mp_init(&rz2));
575 MP_CHECKOK(mp_init(&raz4));
576
577 /* Set p */
578 ecfp_i2fp(p.x, &ecgroup->genx, ecgroup);
579 ecfp_i2fp(p.y, &ecgroup->geny, ecgroup);
580 ecfp_i2fp(group->curvea, &ecgroup->curvea, ecgroup);
581
582 /* paz4 = az^4 */
583 MP_CHECKOK(mp_set_int(&pz, 5));
584 mp_sqrmod(&pz, &ecgroup->meth->irr, &paz4);
585 mp_sqrmod(&paz4, &ecgroup->meth->irr, &paz4);
586 mp_mulmod(&paz4, &ecgroup->curvea, &ecgroup->meth->irr, &paz4);
587
588 ecfp_i2fp(p.z, &pz, ecgroup);
589 ecfp_i2fp(p.az4, &paz4, ecgroup);
590
591 group->pt_dbl_jm(&p, &r, group);
592
593 M_TimeOperation(group->pt_dbl_jm(&p, &r, group), 100000);
594
595 /* Calculate doubling to compare against */
596 ec_GFp_pt_dbl_jac(&ecgroup->genx, &ecgroup->geny, &pz, &rx2, &ry2,
597 &rz2, ecgroup);
598 ec_GFp_pt_jac2aff(&rx2, &ry2, &rz2, &rx2, &ry2, ecgroup);
599
600 /* Do comparison and check az^4 */
601 MP_CHECKOK(testJmPoint(&r, &rx2, &ry2, ecgroup));
602
603 CLEANUP:
604 if (res == MP_OKAY)
605 printf(" Test Passed - Point Doubling - Modified Jacobian\n");
606 else
607 printf("TEST FAILED - Point Doubling - Modified Jacobian\n");
608 mp_clear(&pz);
609 mp_clear(&paz4);
610 mp_clear(&rx2);
611 mp_clear(&ry2);
612 mp_clear(&rz2);
613 mp_clear(&raz4);
614
615 return res;
616
617 }
618
619 /* Tests point doubling in Chudnovsky Jacobian coordinates */
620 mp_err
621 testPointDoubleChud(ECGroup *ecgroup)
622 {
623 mp_err res;
624 mp_int px, py, pz, rx2, ry2, rz2;
625 ecfp_aff_pt p;
626 ecfp_chud_pt p2;
627 EC_group_fp *group = (EC_group_fp *) ecgroup->extra1;
628
629 MP_DIGITS(&rx2) = 0;
630 MP_DIGITS(&ry2) = 0;
631 MP_DIGITS(&rz2) = 0;
632 MP_DIGITS(&px) = 0;
633 MP_DIGITS(&py) = 0;
634 MP_DIGITS(&pz) = 0;
635
636 MP_CHECKOK(mp_init(&rx2));
637 MP_CHECKOK(mp_init(&ry2));
638 MP_CHECKOK(mp_init(&rz2));
639 MP_CHECKOK(mp_init(&px));
640 MP_CHECKOK(mp_init(&py));
641 MP_CHECKOK(mp_init(&pz));
642
643 /* Set p2 = 2P */
644 ecfp_i2fp(p.x, &ecgroup->genx, ecgroup);
645 ecfp_i2fp(p.y, &ecgroup->geny, ecgroup);
646 ecfp_i2fp(group->curvea, &ecgroup->curvea, ecgroup);
647
648 group->pt_dbl_aff2chud(&p, &p2, group);
649
650 /* Calculate doubling to compare against */
651 MP_CHECKOK(mp_set_int(&pz, 1));
652 ec_GFp_pt_dbl_jac(&ecgroup->genx, &ecgroup->geny, &pz, &rx2, &ry2,
653 &rz2, ecgroup);
654 ec_GFp_pt_jac2aff(&rx2, &ry2, &rz2, &rx2, &ry2, ecgroup);
655
656 /* Do comparison and check az^4 */
657 MP_CHECKOK(testChudPoint(&p2, &rx2, &ry2, ecgroup));
658
659 CLEANUP:
660 if (res == MP_OKAY)
661 printf(" Test Passed - Point Doubling - Chudnovsky Jacobian\n");
662 else
663 printf("TEST FAILED - Point Doubling - Chudnovsky Jacobian\n");
664
665 mp_clear(&rx2);
666 mp_clear(&ry2);
667 mp_clear(&rz2);
668 mp_clear(&px);
669 mp_clear(&py);
670 mp_clear(&pz);
671
672 return res;
673 }
674
675 /* Test point doubling in Jacobian coordinates */
676 mp_err
677 testPointDoubleJac(ECGroup *ecgroup)
678 {
679 mp_err res;
680 mp_int pz, rx, ry, rz, rx2, ry2, rz2;
681 ecfp_jac_pt p, p2;
682 EC_group_fp *group = (EC_group_fp *) ecgroup->extra1;
683
684 MP_DIGITS(&pz) = 0;
685 MP_DIGITS(&rx) = 0;
686 MP_DIGITS(&ry) = 0;
687 MP_DIGITS(&rz) = 0;
688 MP_DIGITS(&rx2) = 0;
689 MP_DIGITS(&ry2) = 0;
690 MP_DIGITS(&rz2) = 0;
691
692 MP_CHECKOK(mp_init(&pz));
693 MP_CHECKOK(mp_init(&rx));
694 MP_CHECKOK(mp_init(&ry));
695 MP_CHECKOK(mp_init(&rz));
696 MP_CHECKOK(mp_init(&rx2));
697 MP_CHECKOK(mp_init(&ry2));
698 MP_CHECKOK(mp_init(&rz2));
699
700 MP_CHECKOK(mp_set_int(&pz, 5));
701
702 /* Set p2 = 2P */
703 ecfp_i2fp(p.x, &ecgroup->genx, ecgroup);
704 ecfp_i2fp(p.y, &ecgroup->geny, ecgroup);
705 ecfp_i2fp(p.z, &pz, ecgroup);
706 ecfp_i2fp(group->curvea, &ecgroup->curvea, ecgroup);
707
708 group->pt_dbl_jac(&p, &p2, group);
709 M_TimeOperation(group->pt_dbl_jac(&p, &p2, group), 100000);
710
711 /* Calculate doubling to compare against */
712 ec_GFp_pt_dbl_jac(&ecgroup->genx, &ecgroup->geny, &pz, &rx2, &ry2,
713 &rz2, ecgroup);
714 ec_GFp_pt_jac2aff(&rx2, &ry2, &rz2, &rx2, &ry2, ecgroup);
715
716 /* Do comparison */
717 MP_CHECKOK(testJacPoint(&p2, &rx2, &ry2, ecgroup));
718
719 CLEANUP:
720 if (res == MP_OKAY)
721 printf(" Test Passed - Point Doubling - Jacobian\n");
722 else
723 printf("TEST FAILED - Point Doubling - Jacobian\n");
724
725 mp_clear(&pz);
726 mp_clear(&rx);
727 mp_clear(&ry);
728 mp_clear(&rz);
729 mp_clear(&rx2);
730 mp_clear(&ry2);
731 mp_clear(&rz2);
732
733 return res;
734 }
735
736 /* Tests a point multiplication (various algorithms) */
737 mp_err
738 testPointMul(ECGroup *ecgroup)
739 {
740 mp_err res;
741 char s[1000];
742 mp_int rx, ry, order_1;
743
744 /* Init */
745 MP_DIGITS(&rx) = 0;
746 MP_DIGITS(&ry) = 0;
747 MP_DIGITS(&order_1) = 0;
748
749 MP_CHECKOK(mp_init(&rx));
750 MP_CHECKOK(mp_init(&ry));
751 MP_CHECKOK(mp_init(&order_1));
752
753 MP_CHECKOK(mp_set_int(&order_1, 1));
754 MP_CHECKOK(mp_sub(&ecgroup->order, &order_1, &order_1));
755
756 /* Test Algorithm 1: Jacobian-Affine Double & Add */
757 ec_GFp_pt_mul_jac_fp(&order_1, &ecgroup->genx, &ecgroup->geny, &rx,
758 &ry, ecgroup);
759 MP_CHECKOK(ecgroup->meth->field_neg(&ry, &ry, ecgroup->meth));
760 if ((mp_cmp(&rx, &ecgroup->genx) != 0)
761 || (mp_cmp(&ry, &ecgroup->geny) != 0)) {
762 printf
763 (" Error: ec_GFp_pt_mul_jac_fp invalid result (expected (- base point)).\n");
764 MP_CHECKOK(mp_toradix(&rx, s, 16));
765 printf("rx %s\n", s);
766 MP_CHECKOK(mp_toradix(&ry, s, 16));
767 printf("ry %s\n", s);
768 res = MP_NO;
769 goto CLEANUP;
770 }
771
772 ec_GFp_pt_mul_jac_fp(&ecgroup->order, &ecgroup->genx, &ecgroup->geny,
773 &rx, &ry, ecgroup);
774 if (ec_GFp_pt_is_inf_aff(&rx, &ry) != MP_YES) {
775 printf
776 (" Error: ec_GFp_pt_mul_jac_fp invalid result (expected point at infinity.\n");
777 MP_CHECKOK(mp_toradix(&rx, s, 16));
778 printf("rx %s\n", s);
779 MP_CHECKOK(mp_toradix(&ry, s, 16));
780 printf("ry %s\n", s);
781 res = MP_NO;
782 goto CLEANUP;
783 }
784
785 /* Test Algorithm 2: 4-bit Window in Jacobian */
786 ec_GFp_point_mul_jac_4w_fp(&order_1, &ecgroup->genx, &ecgroup->geny,
787 &rx, &ry, ecgroup);
788 MP_CHECKOK(ecgroup->meth->field_neg(&ry, &ry, ecgroup->meth));
789 if ((mp_cmp(&rx, &ecgroup->genx) != 0)
790 || (mp_cmp(&ry, &ecgroup->geny) != 0)) {
791 printf
792 (" Error: ec_GFp_point_mul_jac_4w_fp invalid result (expected (- base point)).\n");
793 MP_CHECKOK(mp_toradix(&rx, s, 16));
794 printf("rx %s\n", s);
795 MP_CHECKOK(mp_toradix(&ry, s, 16));
796 printf("ry %s\n", s);
797 res = MP_NO;
798 goto CLEANUP;
799 }
800
801 ec_GFp_point_mul_jac_4w_fp(&ecgroup->order, &ecgroup->genx,
802 &ecgroup->geny, &rx, &ry, ecgroup);
803 if (ec_GFp_pt_is_inf_aff(&rx, &ry) != MP_YES) {
804 printf
805 (" Error: ec_GFp_point_mul_jac_4w_fp invalid result (expected point at infinity.\n");
806 MP_CHECKOK(mp_toradix(&rx, s, 16));
807 printf("rx %s\n", s);
808 MP_CHECKOK(mp_toradix(&ry, s, 16));
809 printf("ry %s\n", s);
810 res = MP_NO;
811 goto CLEANUP;
812 }
813
814 /* Test Algorithm 3: wNAF with modified Jacobian coordinates */
815 ec_GFp_point_mul_wNAF_fp(&order_1, &ecgroup->genx, &ecgroup->geny, &rx,
816 &ry, ecgroup);
817 MP_CHECKOK(ecgroup->meth->field_neg(&ry, &ry, ecgroup->meth));
818 if ((mp_cmp(&rx, &ecgroup->genx) != 0)
819 || (mp_cmp(&ry, &ecgroup->geny) != 0)) {
820 printf
821 (" Error: ec_GFp_pt_mul_wNAF_fp invalid result (expected (- base point)).\n");
822 MP_CHECKOK(mp_toradix(&rx, s, 16));
823 printf("rx %s\n", s);
824 MP_CHECKOK(mp_toradix(&ry, s, 16));
825 printf("ry %s\n", s);
826 res = MP_NO;
827 goto CLEANUP;
828 }
829
830 ec_GFp_point_mul_wNAF_fp(&ecgroup->order, &ecgroup->genx,
831 &ecgroup->geny, &rx, &ry, ecgroup);
832 if (ec_GFp_pt_is_inf_aff(&rx, &ry) != MP_YES) {
833 printf
834 (" Error: ec_GFp_pt_mul_wNAF_fp invalid result (expected point at infinity.\n");
835 MP_CHECKOK(mp_toradix(&rx, s, 16));
836 printf("rx %s\n", s);
837 MP_CHECKOK(mp_toradix(&ry, s, 16));
838 printf("ry %s\n", s);
839 res = MP_NO;
840 goto CLEANUP;
841 }
842
843 CLEANUP:
844 if (res == MP_OKAY)
845 printf(" Test Passed - Point Multiplication\n");
846 else
847 printf("TEST FAILED - Point Multiplication\n");
848 mp_clear(&rx);
849 mp_clear(&ry);
850 mp_clear(&order_1);
851
852 return res;
853 }
854
855 /* Tests point multiplication with a random scalar repeatedly, comparing
856 * for consistency within different algorithms. */
857 mp_err
858 testPointMulRandom(ECGroup *ecgroup)
859 {
860 mp_err res;
861 mp_int rx, ry, rx2, ry2, n;
862 int i, size;
863 EC_group_fp *group = (EC_group_fp *) ecgroup->extra1;
864
865 MP_DIGITS(&rx) = 0;
866 MP_DIGITS(&ry) = 0;
867 MP_DIGITS(&rx2) = 0;
868 MP_DIGITS(&ry2) = 0;
869 MP_DIGITS(&n) = 0;
870
871 MP_CHECKOK(mp_init(&rx));
872 MP_CHECKOK(mp_init(&ry));
873 MP_CHECKOK(mp_init(&rx2));
874 MP_CHECKOK(mp_init(&ry2));
875 MP_CHECKOK(mp_init(&n));
876
877 for (i = 0; i < 100; i++) {
878 /* compute random scalar */
879 size = mpl_significant_bits(&ecgroup->meth->irr);
880 if (size < MP_OKAY) {
881 res = MP_NO;
882 goto CLEANUP;
883 }
884 MP_CHECKOK(mpp_random_size(&n, group->orderBitSize));
885 MP_CHECKOK(mp_mod(&n, &ecgroup->order, &n));
886
887 ec_GFp_pt_mul_jac(&n, &ecgroup->genx, &ecgroup->geny, &rx, &ry,
888 ecgroup);
889 ec_GFp_pt_mul_jac_fp(&n, &ecgroup->genx, &ecgroup->geny, &rx2,
890 &ry2, ecgroup);
891
892 if ((mp_cmp(&rx, &rx2) != 0) || (mp_cmp(&ry, &ry2) != 0)) {
893 printf
894 (" Error: different results for Point Multiplication - Double & Add.\n");
895 res = MP_NO;
896 goto CLEANUP;
897 }
898
899 ec_GFp_point_mul_wNAF_fp(&n, &ecgroup->genx, &ecgroup->geny, &rx,
900 &ry, ecgroup);
901 if ((mp_cmp(&rx, &rx2) != 0) || (mp_cmp(&ry, &ry2) != 0)) {
902 printf
903 (" Error: different results for Point Multiplication - wNAF.\n");
904 res = MP_NO;
905 goto CLEANUP;
906 }
907
908 ec_GFp_point_mul_jac_4w_fp(&n, &ecgroup->genx, &ecgroup->geny, &rx,
909 &ry, ecgroup);
910 if ((mp_cmp(&rx, &rx2) != 0) || (mp_cmp(&ry, &ry2) != 0)) {
911 printf
912 (" Error: different results for Point Multiplication - 4 bit window.\n");
913 res = MP_NO;
914 goto CLEANUP;
915 }
916
917 }
918
919 CLEANUP:
920 if (res == MP_OKAY)
921 printf(" Test Passed - Point Random Multiplication\n");
922 else
923 printf("TEST FAILED - Point Random Multiplication\n");
924 mp_clear(&rx);
925 mp_clear(&ry);
926 mp_clear(&rx2);
927 mp_clear(&ry2);
928 mp_clear(&n);
929
930 return res;
931 }
932
933 /* Tests the time required for a point multiplication */
934 mp_err
935 testPointMulTime(ECGroup *ecgroup)
936 {
937 mp_err res = MP_OKAY;
938 mp_int rx, ry, n;
939 int size;
940
941 MP_DIGITS(&rx) = 0;
942 MP_DIGITS(&ry) = 0;
943 MP_DIGITS(&n) = 0;
944
945 MP_CHECKOK(mp_init(&rx));
946 MP_CHECKOK(mp_init(&ry));
947 MP_CHECKOK(mp_init(&n));
948
949 /* compute random scalar */
950 size = mpl_significant_bits(&ecgroup->meth->irr);
951 if (size < MP_OKAY) {
952 res = MP_NO;
953 goto CLEANUP;
954 }
955
956 MP_CHECKOK(mpp_random_size(&n, (size + ECL_BITS - 1) / ECL_BITS));
957 MP_CHECKOK(ecgroup->meth->field_mod(&n, &n, ecgroup->meth));
958
959 M_TimeOperation(ec_GFp_pt_mul_jac_fp
960 (&n, &ecgroup->genx, &ecgroup->geny, &rx, &ry,
961 ecgroup), 1000);
962
963 M_TimeOperation(ec_GFp_point_mul_jac_4w_fp
964 (&n, &ecgroup->genx, &ecgroup->geny, &rx, &ry,
965 ecgroup), 1000);
966
967 M_TimeOperation(ec_GFp_point_mul_wNAF_fp
968 (&n, &ecgroup->genx, &ecgroup->geny, &rx, &ry,
969 ecgroup), 1000);
970
971 M_TimeOperation(ec_GFp_pt_mul_jac
972 (&n, &ecgroup->genx, &ecgroup->geny, &rx, &ry,
973 ecgroup), 100);
974
975 CLEANUP:
976 if (res == MP_OKAY)
977 printf(" Test Passed - Point Multiplication Timing\n");
978 else
979 printf("TEST FAILED - Point Multiplication Timing\n");
980 mp_clear(&rx);
981 mp_clear(&ry);
982 mp_clear(&n);
983
984 return res;
985 }
986
987 /* Tests pre computation of Chudnovsky Jacobian points used in wNAF form */
988 mp_err
989 testPreCompute(ECGroup *ecgroup)
990 {
991 ecfp_chud_pt precomp[16];
992 ecfp_aff_pt p;
993 EC_group_fp *group = (EC_group_fp *) ecgroup->extra1;
994 int i;
995 mp_err res;
996
997 mp_int x, y, ny, x2, y2;
998
999 MP_DIGITS(&x) = 0;
1000 MP_DIGITS(&y) = 0;
1001 MP_DIGITS(&ny) = 0;
1002 MP_DIGITS(&x2) = 0;
1003 MP_DIGITS(&y2) = 0;
1004
1005 MP_CHECKOK(mp_init(&x));
1006 MP_CHECKOK(mp_init(&y));
1007 MP_CHECKOK(mp_init(&ny));
1008 MP_CHECKOK(mp_init(&x2));
1009 MP_CHECKOK(mp_init(&y2));
1010
1011 ecfp_i2fp(p.x, &ecgroup->genx, ecgroup);
1012 ecfp_i2fp(p.y, &ecgroup->geny, ecgroup);
1013 ecfp_i2fp(group->curvea, &(ecgroup->curvea), ecgroup);
1014
1015 /* Perform precomputation */
1016 group->precompute_chud(precomp, &p, group);
1017
1018 M_TimeOperation(group->precompute_chud(precomp, &p, group), 10000);
1019
1020 /* Calculate addition to compare against */
1021 MP_CHECKOK(mp_copy(&ecgroup->genx, &x));
1022 MP_CHECKOK(mp_copy(&ecgroup->geny, &y));
1023 MP_CHECKOK(ecgroup->meth->field_neg(&y, &ny, ecgroup->meth));
1024
1025 ec_GFp_pt_dbl_aff(&x, &y, &x2, &y2, ecgroup);
1026
1027 for (i = 0; i < 8; i++) {
1028 MP_CHECKOK(testChudPoint(&precomp[8 + i], &x, &y, ecgroup));
1029 MP_CHECKOK(testChudPoint(&precomp[7 - i], &x, &ny, ecgroup));
1030 ec_GFp_pt_add_aff(&x, &y, &x2, &y2, &x, &y, ecgroup);
1031 MP_CHECKOK(ecgroup->meth->field_neg(&y, &ny, ecgroup->meth));
1032 }
1033
1034 CLEANUP:
1035 if (res == MP_OKAY)
1036 printf(" Test Passed - Precomputation\n");
1037 else
1038 printf("TEST FAILED - Precomputation\n");
1039
1040 mp_clear(&x);
1041 mp_clear(&y);
1042 mp_clear(&ny);
1043 mp_clear(&x2);
1044 mp_clear(&y2);
1045 return res;
1046 }
1047
1048 /* Given a curve using floating point arithmetic, test it. This method
1049 * specifies which of the above tests to run. */
1050 mp_err
1051 testCurve(ECGroup *ecgroup)
1052 {
1053 int res = MP_OKAY;
1054
1055 MP_CHECKOK(testPointAddJacAff(ecgroup));
1056 MP_CHECKOK(testPointAddJac(ecgroup));
1057 MP_CHECKOK(testPointAddChud(ecgroup));
1058 MP_CHECKOK(testPointAddJmChud(ecgroup));
1059 MP_CHECKOK(testPointDoubleJac(ecgroup));
1060 MP_CHECKOK(testPointDoubleChud(ecgroup));
1061 MP_CHECKOK(testPointDoubleJm(ecgroup));
1062 MP_CHECKOK(testPreCompute(ecgroup));
1063 MP_CHECKOK(testPointMul(ecgroup));
1064 MP_CHECKOK(testPointMulRandom(ecgroup));
1065 MP_CHECKOK(testPointMulTime(ecgroup));
1066 CLEANUP:
1067 return res;
1068 }
1069
1070 /* Tests a number of curves optimized using floating point arithmetic */
1071 int
1072 main(void)
1073 {
1074 mp_err res = MP_OKAY;
1075 ECGroup *ecgroup = NULL;
1076
1077 /* specific arithmetic tests */
1078 M_TestCurve("SECG-160R1", ECCurve_SECG_PRIME_160R1);
1079 M_TestCurve("SECG-192R1", ECCurve_SECG_PRIME_192R1);
1080 M_TestCurve("SEGC-224R1", ECCurve_SECG_PRIME_224R1);
1081
1082 CLEANUP:
1083 ECGroup_free(ecgroup);
1084 if (res != MP_OKAY) {
1085 printf("Error: exiting with error value %i\n", res);
1086 }
1087 return res;
1088 }

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial