7c1936b5a46874b273a124ba7d1ade72bc812045
[u/mdw/catacomb] / group-test.c
1 /* -*-c-*-
2 *
3 * $Id: group-test.c,v 1.2 2004/04/04 19:04:11 mdw Exp $
4 *
5 * Testing group operations
6 *
7 * (c) 2004 Straylight/Edgeware
8 */
9
10 /*----- Licensing notice --------------------------------------------------*
11 *
12 * This file is part of Catacomb.
13 *
14 * Catacomb is free software; you can redistribute it and/or modify
15 * it under the terms of the GNU Library General Public License as
16 * published by the Free Software Foundation; either version 2 of the
17 * License, or (at your option) any later version.
18 *
19 * Catacomb is distributed in the hope that it will be useful,
20 * but WITHOUT ANY WARRANTY; without even the implied warranty of
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 * GNU Library General Public License for more details.
23 *
24 * You should have received a copy of the GNU Library General Public
25 * License along with Catacomb; if not, write to the Free
26 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
27 * MA 02111-1307, USA.
28 */
29
30 /*----- Revision history --------------------------------------------------*
31 *
32 * $Log: group-test.c,v $
33 * Revision 1.2 2004/04/04 19:04:11 mdw
34 * Raw I/O of elliptic curve points and group elements.
35 *
36 * Revision 1.1 2004/04/01 12:50:09 mdw
37 * Add cyclic group abstraction, with test code. Separate off exponentation
38 * functions for better static linking. Fix a buttload of bugs on the way.
39 * Generally ensure that negative exponents do inversion correctly. Add
40 * table of standard prime-field subgroups. (Binary field subgroups are
41 * currently unimplemented but easy to add if anyone ever finds a good one.)
42 *
43 */
44
45 /*----- Header files ------------------------------------------------------*/
46
47 #include <stdarg.h>
48
49 #include <mLib/testrig.h>
50
51 #include "group.h"
52 #include "fibrand.h"
53 #include "ec.h"
54 #include "ec-test.h"
55
56 /*----- Main code ---------------------------------------------------------*/
57
58 static group *getgroup(const char *p) {
59 group *g; qd_parse qd;
60 qd.p = p; qd.e = 0; g = group_parse(&qd);
61 if (g && !qd_eofp(&qd)) { G_DESTROYGROUP(g); g = 0; qd.e = "junk at eof"; }
62 if (!g) { fprintf(stderr, "bad group string `%.*s|%s': %s\n", qd.p - p,
63 p, qd.p, qd.e); exit(1); }
64 return (g);
65 }
66
67 static ge *getge(group *g, const char *p) {
68 ge *x = G_CREATE(g);
69 if (group_readstring(g, x, p, 0)) {
70 fprintf(stderr, "bad group element `%s'\n", p);
71 exit(1);
72 }
73 return (x);
74 }
75
76 static void show(group *g, const char *p, ge *x) {
77 fprintf(stderr, "*** %s = ", p); group_writefile(g, x, stderr);
78 putc('\n', stderr);
79 }
80
81 static void showec(const char *p, ec *q) {
82 fprintf(stderr, "*** %s = ", p);
83 if (EC_ATINF(q)) fprintf(stderr, "inf\n");
84 else {
85 mp_writefile(q->x, stderr, 16); fputs(", ", stderr);
86 mp_writefile(q->x, stderr, 16); putchar('\n');
87 }
88 }
89
90 static void showmp(const char *p, mp *x, int r) {
91 fprintf(stderr, "*** %s = ", p); mp_writefile(x, stderr, r);
92 putc('\n', stderr);
93 }
94
95 static int check(const char *op, const char *gd, group *g,
96 ge *r, ge *c, ...) {
97 va_list ap;
98
99 if (G_EQ(g, r, c)) return (1);
100 fprintf(stderr, "\n*** %s failed\n", op);
101 fprintf(stderr, "*** group: %s\n", gd);
102 va_start(ap, c);
103 for (;;) {
104 const char *p; ge *x;
105 p = va_arg(ap, const char *); if (!p) break;
106 x = va_arg(ap, ge *); show(g, p, x);
107 }
108 show(g, "expected", r);
109 show(g, "computed", c);
110 return (0);
111 }
112
113 /*----- Actual tests ------------------------------------------------------*/
114
115 static int vcheck(dstr *v)
116 {
117 group *g = getgroup(v[0].buf);
118 grand *gr = fibrand_create(0);
119 const char *e = G_CHECK(g, gr);
120 int ok = 1;
121 gr->ops->destroy(gr);
122 if (!e) e = "ok";
123 G_DESTROYGROUP(g);
124 if (strcmp(e, v[1].buf)) {
125 ok = 0;
126 fprintf(stderr, "*** check failed\n");
127 fprintf(stderr, "*** group: %s\n", v[0].buf);
128 fprintf(stderr, "*** expected: %s\n", v[1].buf);
129 fprintf(stderr, "*** returned: %s\n", e);
130 }
131 assert(mparena_count(MPARENA_GLOBAL) == 0);
132 return (ok);
133 }
134
135 static int vcheckelt(dstr *v)
136 {
137 group *g = getgroup(v[0].buf);
138 ge *x = getge(g, v[1].buf);
139 int ir = *(int *)v[2].buf;
140 int ic = group_check(g, x);
141 int ok = 1;
142 if (ir != ic) {
143 ok = 0;
144 fprintf(stderr, "*** check failed\n");
145 fprintf(stderr, "*** group: %s\n", v[0].buf);
146 show(g, "x", x);
147 fprintf(stderr, "*** expected %s\n", ir ? "failure" : "success");
148 }
149 G_DESTROY(g, x);
150 G_DESTROYGROUP(g);
151 assert(mparena_count(MPARENA_GLOBAL) == 0);
152 return (ok);
153 }
154
155 static int vmul(dstr *v)
156 {
157 group *g = getgroup(v[0].buf);
158 ge *x = getge(g, v[1].buf);
159 ge *y = getge(g, v[2].buf);
160 ge *r = getge(g, v[3].buf);
161 ge *c = G_CREATE(g);
162 int ok = 1;
163 G_MUL(g, c, x, y);
164 ok &= check("mul", v[0].buf, g, r, c, "x", x, "y", y, (char *)0);
165 G_DESTROY(g, x); G_DESTROY(g, y); G_DESTROY(g, r); G_DESTROY(g, c);
166 G_DESTROYGROUP(g);
167 assert(mparena_count(MPARENA_GLOBAL) == 0);
168 return (ok);
169 }
170
171 static int vsqr(dstr *v)
172 {
173 group *g = getgroup(v[0].buf);
174 ge *x = getge(g, v[1].buf);
175 ge *r = getge(g, v[2].buf);
176 ge *c = G_CREATE(g);
177 int ok = 1;
178 G_SQR(g, c, x);
179 ok &= check("sqr", v[0].buf, g, r, c, "x", x, (char *)0);
180 G_DESTROY(g, x); G_DESTROY(g, r); G_DESTROY(g, c);
181 G_DESTROYGROUP(g);
182 assert(mparena_count(MPARENA_GLOBAL) == 0);
183 return (ok);
184 }
185
186 static int vinv(dstr *v)
187 {
188 group *g = getgroup(v[0].buf);
189 ge *x = getge(g, v[1].buf);
190 ge *r = getge(g, v[2].buf);
191 ge *c = G_CREATE(g);
192 int ok = 1;
193 G_INV(g, c, x);
194 ok &= check("inv", v[0].buf, g, r, c, "x", x, (char *)0);
195 G_DESTROY(g, x); G_DESTROY(g, r); G_DESTROY(g, c);
196 G_DESTROYGROUP(g);
197 assert(mparena_count(MPARENA_GLOBAL) == 0);
198 return (ok);
199 }
200
201 static int vdiv(dstr *v)
202 {
203 group *g = getgroup(v[0].buf);
204 ge *x = getge(g, v[1].buf);
205 ge *y = getge(g, v[2].buf);
206 ge *r = getge(g, v[3].buf);
207 ge *c = G_CREATE(g);
208 int ok = 1;
209 G_DIV(g, c, x, y);
210 ok &= check("div", v[0].buf, g, r, c, "x", x, "y", y, (char *)0);
211 group_stddiv(g, c, x, y);
212 ok &= check("stddiv", v[0].buf, g, r, c, "x", x, "y", y, (char *)0);
213 G_DESTROY(g, x); G_DESTROY(g, y); G_DESTROY(g, r); G_DESTROY(g, c);
214 G_DESTROYGROUP(g);
215 assert(mparena_count(MPARENA_GLOBAL) == 0);
216 return (ok);
217 }
218
219 static int vexp(dstr *v)
220 {
221 group *g = getgroup(v[0].buf);
222 ge *x = getge(g, v[1].buf);
223 mp *n = *(mp **)v[2].buf;
224 ge *r = getge(g, v[3].buf);
225 ge *c = G_CREATE(g);
226 int ok = 1;
227 G_EXP(g, c, x, n);
228 if (!G_EQ(g, r, c)) {
229 ok = 0;
230 fprintf(stderr, "\n*** exp failed\n");
231 fprintf(stderr, "*** group: %s\n", v[0].buf);
232 show(g, "x", x); showmp("n", n, 10);
233 show(g, "expected", r); show(g, "computed", c);
234 }
235 group_stdexp(g, c, x, n);
236 if (!G_EQ(g, r, c)) {
237 ok = 0;
238 fprintf(stderr, "\n*** stdexp failed\n");
239 fprintf(stderr, "*** group: %s\n", v[0].buf);
240 show(g, "x", x); showmp("n", n, 10);
241 show(g, "expected", r); show(g, "computed", c);
242 }
243 G_DESTROY(g, x); MP_DROP(n); G_DESTROY(g, r); G_DESTROY(g, c);
244 G_DESTROYGROUP(g);
245 assert(mparena_count(MPARENA_GLOBAL) == 0);
246 return (ok);
247 }
248
249 static int vmexp(size_t n, dstr *v)
250 {
251 group *g = getgroup(v[0].buf);
252 ge *c, *r;
253 group_expfactor *f = xmalloc(n * sizeof(group_expfactor));
254 int ok = 1;
255 size_t i;
256 for (i = 0; i < n; i++) {
257 f[i].base = getge(g, v[1 + 2 * i].buf);
258 f[i].exp = *(mp **)v[2 + 2 * i].buf;
259 }
260 r = getge(g, v[1 + 2 * n].buf);
261 c = G_CREATE(g);
262 G_MEXP(g, c, f, n);
263 if (!G_EQ(g, r, c)) {
264 ok = 0;
265 fprintf(stderr, "\n*** mexp failed\n");
266 fprintf(stderr, "*** group: %s\n", v[0].buf);
267 for (i = 0; i < n; i++) {
268 show(g, "base", f[i].base);
269 showmp("exp", f[i].exp, 10);
270 }
271 show(g, "expected", r); show(g, "computed", c);
272 }
273 group_stdmexp(g, c, f, n);
274 if (!G_EQ(g, r, c)) {
275 ok = 0;
276 fprintf(stderr, "\n*** stdmexp failed\n");
277 fprintf(stderr, "*** group: %s\n", v[0].buf);
278 for (i = 0; i < n; i++) {
279 show(g, "base", f[i].base);
280 showmp("exp", f[i].exp, 10);
281 }
282 show(g, "expected", r); show(g, "computed", c);
283 }
284 for (i = 0; i < n; i++) { G_DESTROY(g, f[i].base); MP_DROP(f[i].exp); }
285 G_DESTROY(g, r); G_DESTROY(g, c);
286 G_DESTROYGROUP(g);
287 assert(mparena_count(MPARENA_GLOBAL) == 0);
288 return (ok);
289 }
290
291 static int vmexp1(dstr *v) { return vmexp(1, v); }
292 static int vmexp2(dstr *v) { return vmexp(2, v); }
293 static int vmexp3(dstr *v) { return vmexp(3, v); }
294 static int vmexp4(dstr *v) { return vmexp(4, v); }
295
296 static int vtoint(dstr *v)
297 {
298 group *g = getgroup(v[0].buf);
299 ge *x = getge(g, v[1].buf);
300 int ir = *(int *)v[2].buf;
301 mp *r = *(mp **)v[3].buf;
302 mp *c;
303 int ic;
304 int ok = 1;
305 c = G_TOINT(g, MP_NEW, x);
306 ic = c ? 0 : -1;
307 if (ir != ic || (!ic && !MP_EQ(r, c))) {
308 ok = 0;
309 fprintf(stderr, "\n*** toint failed\n");
310 fprintf(stderr, "*** group: %s\n", v[0].buf);
311 if (ir) fprintf(stderr, "*** expected failure\n");
312 else { show(g, "x", x); showmp("expected", r, 16);
313 showmp("computed", c, 16); }
314 }
315 G_DESTROY(g, x); mp_drop(r); mp_drop(c);
316 G_DESTROYGROUP(g);
317 assert(mparena_count(MPARENA_GLOBAL) == 0);
318 return (ok);
319 }
320
321 static int vfromint(dstr *v)
322 {
323 group *g = getgroup(v[0].buf);
324 mp *x = *(mp **)v[1].buf;
325 int ir = *(int *)v[2].buf;
326 ge *r = getge(g, v[3].buf);
327 int ic;
328 ge *c = G_CREATE(g);
329 int ok = 1;
330 ic = G_FROMINT(g, c, x);
331 if (ir != ic || (!ic && !G_EQ(g, r, c))) {
332 ok = 0;
333 fprintf(stderr, "\n*** fromint failed\n");
334 fprintf(stderr, "*** group: %s\n", v[0].buf);
335 showmp("x", x, 16); if (ir) fprintf(stderr, "*** should have failed\n");
336 else { show(g, "expected", r); show(g, "computed", c); }
337 }
338 MP_DROP(x); G_DESTROY(g, r); G_DESTROY(g, c);
339 G_DESTROYGROUP(g);
340 assert(mparena_count(MPARENA_GLOBAL) == 0);
341 return (ok);
342 }
343
344 static int vtoec(dstr *v)
345 {
346 group *g = getgroup(v[0].buf);
347 ge *x = getge(g, v[1].buf);
348 int ir = *(int *)v[2].buf;
349 ec *r = (ec *)v[3].buf;
350 int ic;
351 ec c = EC_INIT;
352 int ok = 1;
353 ic = G_TOEC(g, &c, x);
354 if (ir != ic || (!ic && !EC_EQ(r, &c))) {
355 ok = 0;
356 fprintf(stderr, "\n*** toec failed\n");
357 fprintf(stderr, "*** group: %s\n", v[0].buf);
358 show(g, "x", x);
359 if (ir) fprintf(stderr, "*** should have failed\n");
360 else { showec("expected", r); showec("computed", &c); }
361 }
362 G_DESTROY(g, x); EC_DESTROY(&c); EC_DESTROY(r);
363 G_DESTROYGROUP(g);
364 assert(mparena_count(MPARENA_GLOBAL) == 0);
365 return (ok);
366 }
367
368 static int vfromec(dstr *v)
369 {
370 group *g = getgroup(v[0].buf);
371 ec *p = (ec *)v[1].buf;
372 int ir = *(int *)v[2].buf;
373 ge *r = getge(g, v[3].buf);
374 int ic;
375 ge *c = G_CREATE(g);
376 int ok = 1;
377 ic = G_FROMEC(g, c, p);
378 if (ir != ic || (!ic && !G_EQ(g, r, c))) {
379 ok = 0;
380 fprintf(stderr, "\n*** fromec failed\n");
381 fprintf(stderr, "*** group: %s\n", v[0].buf);
382 showec("p", p); if (ir) fprintf(stderr, "*** should have failed\n");
383 else { show(g, "expected", r); show(g, "computed", c); }
384 }
385 EC_DESTROY(p); G_DESTROY(g, r); G_DESTROY(g, c);
386 G_DESTROYGROUP(g);
387 assert(mparena_count(MPARENA_GLOBAL) == 0);
388 return (ok);
389 }
390
391 static int vtobuf(dstr *v)
392 {
393 group *g = getgroup(v[0].buf);
394 ge *x = getge(g, v[1].buf);
395 int ir = *(int *)v[2].buf;
396 dstr c = DSTR_INIT;
397 int ic;
398 buf b;
399 int ok = 1;
400
401 dstr_ensure(&c, v[3].len);
402 buf_init(&b, c.buf, v[3].len);
403 ic = G_TOBUF(g, &b, x);
404 c.len = BLEN(&b);
405 if (ic != ir || (!ic && (c.len != v[3].len ||
406 memcmp(c.buf, v[3].buf, c.len)))) {
407 ok = 0;
408 fprintf(stderr, "*** tobuf failed\n");
409 fprintf(stderr, "*** group: %s\n", v[0].buf);
410 show(g, "x", x);
411 if (ir) fprintf(stderr, "*** expected failure\n");
412 else {
413 fprintf(stderr, "*** expected: "); type_hex.dump(&v[3], stderr);
414 fprintf(stderr, "\n*** computed: "); type_hex.dump(&c, stderr);
415 fputc('\n', stderr);
416 }
417 }
418 G_DESTROY(g, x); dstr_destroy(&c);
419 G_DESTROYGROUP(g);
420 assert(mparena_count(MPARENA_GLOBAL) == 0);
421 return (ok);
422 }
423
424 static int vfrombuf(dstr *v)
425 {
426 group *g = getgroup(v[0].buf);
427 int ir = *(int *)v[2].buf;
428 ge *r = getge(g, v[3].buf);
429 int ic;
430 ge *c = G_CREATE(g);
431 buf b;
432 int ok = 1;
433
434 buf_init(&b, v[1].buf, v[1].len);
435 ic = G_FROMBUF(g, &b, c);
436 if ((ic < 0) != (ir < 0) || (ir >= 0 &&
437 (ir != BLEN(&b) || !G_EQ(g, r, c)))) {
438 ok = 0;
439 fprintf(stderr, "*** frombuf failed\n");
440 fprintf(stderr, "*** group: %s\n", v[0].buf);
441 fprintf(stderr, "*** input string: "); type_hex.dump(&v[1], stderr);
442 fputc('\n', stderr);
443 if (ir < 0) fprintf(stderr, "*** expected failure\n");
444 else {
445 show(g, "expected", r); show(g, "computed", c);
446 fprintf(stderr, "*** expected used = %d\n", ir);
447 fprintf(stderr, "*** computed used = %lu\n", (unsigned long)BLEN(&b));
448 }
449 }
450 G_DESTROY(g, r); G_DESTROY(g, c);
451 G_DESTROYGROUP(g);
452 assert(mparena_count(MPARENA_GLOBAL) == 0);
453 return (ok);
454 }
455
456 static int vtoraw(dstr *v)
457 {
458 group *g = getgroup(v[0].buf);
459 ge *x = getge(g, v[1].buf);
460 int ir = *(int *)v[2].buf;
461 dstr c = DSTR_INIT;
462 int ic;
463 buf b;
464 int ok = 1;
465
466 dstr_ensure(&c, v[3].len);
467 buf_init(&b, c.buf, v[3].len);
468 ic = G_TORAW(g, &b, x);
469 c.len = BLEN(&b);
470 if (ic != ir || (!ic && (c.len != v[3].len ||
471 memcmp(c.buf, v[3].buf, c.len)))) {
472 ok = 0;
473 fprintf(stderr, "*** toraw failed\n");
474 fprintf(stderr, "*** group: %s\n", v[0].buf);
475 show(g, "x", x);
476 if (ir) fprintf(stderr, "*** expected failure\n");
477 else {
478 fprintf(stderr, "*** expected: "); type_hex.dump(&v[3], stderr);
479 fprintf(stderr, "\n*** computed: "); type_hex.dump(&c, stderr);
480 fputc('\n', stderr);
481 }
482 }
483 G_DESTROY(g, x); dstr_destroy(&c);
484 G_DESTROYGROUP(g);
485 assert(mparena_count(MPARENA_GLOBAL) == 0);
486 return (ok);
487 }
488
489 static int vfromraw(dstr *v)
490 {
491 group *g = getgroup(v[0].buf);
492 int ir = *(int *)v[2].buf;
493 ge *r = getge(g, v[3].buf);
494 int ic;
495 ge *c = G_CREATE(g);
496 buf b;
497 int ok = 1;
498
499 buf_init(&b, v[1].buf, v[1].len);
500 ic = G_FROMRAW(g, &b, c);
501 if ((ic < 0) != (ir < 0) || (ir >= 0 &&
502 (ir != BLEN(&b) || !G_EQ(g, r, c)))) {
503 ok = 0;
504 fprintf(stderr, "*** fromraw failed\n");
505 fprintf(stderr, "*** group: %s\n", v[0].buf);
506 fprintf(stderr, "*** input string: "); type_hex.dump(&v[1], stderr);
507 fputc('\n', stderr);
508 if (ir < 0) fprintf(stderr, "*** expected failure\n");
509 else {
510 show(g, "expected", r); show(g, "computed", c);
511 fprintf(stderr, "*** expected used = %d\n", ir);
512 fprintf(stderr, "*** computed used = %lu\n", (unsigned long)BLEN(&b));
513 }
514 }
515 G_DESTROY(g, r); G_DESTROY(g, c);
516 G_DESTROYGROUP(g);
517 assert(mparena_count(MPARENA_GLOBAL) == 0);
518 return (ok);
519 }
520
521 static const test_chunk tests[] = {
522 { "check", vcheck, { &type_string, &type_string } },
523 { "checkelt", vcheckelt, { &type_string, &type_string, &type_int } },
524 { "mul", vmul, { &type_string, &type_string,
525 &type_string, &type_string } },
526 { "sqr", vsqr, { &type_string, &type_string,
527 &type_string } },
528 { "inv", vinv, { &type_string, &type_string,
529 &type_string } },
530 { "div", vdiv, { &type_string, &type_string,
531 &type_string, &type_string } },
532 { "exp", vexp, { &type_string, &type_string,
533 &type_mp, &type_string } },
534 { "mexp-1", vmexp1, { &type_string,
535 &type_string, &type_mp,
536 &type_string } },
537 { "mexp-2", vmexp2, { &type_string,
538 &type_string, &type_mp,
539 &type_string, &type_mp,
540 &type_string } },
541 { "mexp-3", vmexp3, { &type_string,
542 &type_string, &type_mp,
543 &type_string, &type_mp,
544 &type_string, &type_mp,
545 &type_string } },
546 { "mexp-4", vmexp4, { &type_string,
547 &type_string, &type_mp,
548 &type_string, &type_mp,
549 &type_string, &type_mp,
550 &type_string, &type_mp,
551 &type_string } },
552 { "toint", vtoint, { &type_string, &type_string,
553 &type_int, &type_mp } },
554 { "fromint", vfromint, { &type_string, &type_mp,
555 &type_int, &type_string } },
556 { "toec", vtoec, { &type_string, &type_string,
557 &type_int, &type_ec } },
558 { "fromec", vfromec, { &type_string, &type_ec,
559 &type_int, &type_string } },
560 { "tobuf", vtobuf, { &type_string, &type_string,
561 &type_int, &type_hex } },
562 { "frombuf", vfrombuf, { &type_string, &type_hex,
563 &type_int, &type_string } },
564 { "toraw", vtoraw, { &type_string, &type_string,
565 &type_int, &type_hex } },
566 { "fromraw", vfromraw, { &type_string, &type_hex,
567 &type_int, &type_string } },
568 { 0 }
569 };
570
571 int main(int argc, char *argv[])
572 {
573 sub_init();
574 test_run(argc, argv, tests, SRCDIR "/tests/group");
575 return (0);
576 }
577
578 /*----- That's all, folks -------------------------------------------------*/