projects / u / mdw / catacomb / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Add cyclic group abstraction, with test code. Separate off exponentation
[u/mdw/catacomb] / group-test.c
1 /* -*-c-*-
2 *
3 * $Id: group-test.c,v 1.1 2004/04/01 12:50:09 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.1 2004/04/01 12:50:09 mdw
34 * Add cyclic group abstraction, with test code. Separate off exponentation
35 * functions for better static linking. Fix a buttload of bugs on the way.
36 * Generally ensure that negative exponents do inversion correctly. Add
37 * table of standard prime-field subgroups. (Binary field subgroups are
38 * currently unimplemented but easy to add if anyone ever finds a good one.)
39 *
40 */
41
42 /*----- Header files ------------------------------------------------------*/
43
44 #include <stdarg.h>
45
46 #include <mLib/testrig.h>
47
48 #include "group.h"
49 #include "fibrand.h"
50 #include "ec.h"
51 #include "ec-test.h"
52
53 /*----- Main code ---------------------------------------------------------*/
54
55 static group *getgroup(const char *p) {
56 group *g; qd_parse qd;
57 qd.p = p; qd.e = 0; g = group_parse(&qd);
58 if (g && !qd_eofp(&qd)) { G_DESTROYGROUP(g); g = 0; qd.e = "junk at eof"; }
59 if (!g) { fprintf(stderr, "bad group string `%.*s|%s': %s\n", qd.p - p,
60 p, qd.p, qd.e); exit(1); }
61 return (g);
62 }
63
64 static ge *getge(group *g, const char *p) {
65 ge *x = G_CREATE(g);
66 if (group_readstring(g, x, p, 0)) {
67 fprintf(stderr, "bad group element `%s'\n", p);
68 exit(1);
69 }
70 return (x);
71 }
72
73 static void show(group *g, const char *p, ge *x) {
74 fprintf(stderr, "*** %s = ", p); group_writefile(g, x, stderr);
75 putc('\n', stderr);
76 }
77
78 static void showec(const char *p, ec *q) {
79 fprintf(stderr, "*** %s = ", p);
80 if (EC_ATINF(q)) fprintf(stderr, "inf\n");
81 else {
82 mp_writefile(q->x, stderr, 16); fputs(", ", stderr);
83 mp_writefile(q->x, stderr, 16); putchar('\n');
84 }
85 }
86
87 static void showmp(const char *p, mp *x, int r) {
88 fprintf(stderr, "*** %s = ", p); mp_writefile(x, stderr, r);
89 putc('\n', stderr);
90 }
91
92 static int check(const char *op, const char *gd, group *g,
93 ge *r, ge *c, ...) {
94 va_list ap;
95
96 if (G_EQ(g, r, c)) return (1);
97 fprintf(stderr, "\n*** %s failed\n", op);
98 fprintf(stderr, "*** group: %s\n", gd);
99 va_start(ap, c);
100 for (;;) {
101 const char *p; ge *x;
102 p = va_arg(ap, const char *); if (!p) break;
103 x = va_arg(ap, ge *); show(g, p, x);
104 }
105 show(g, "expected", r);
106 show(g, "computed", c);
107 return (0);
108 }
109
110 /*----- Actual tests ------------------------------------------------------*/
111
112 static int vcheck(dstr *v)
113 {
114 group *g = getgroup(v[0].buf);
115 grand *gr = fibrand_create(0);
116 const char *e = G_CHECK(g, gr);
117 int ok = 1;
118 gr->ops->destroy(gr);
119 if (!e) e = "ok";
120 G_DESTROYGROUP(g);
121 if (strcmp(e, v[1].buf)) {
122 ok = 0;
123 fprintf(stderr, "*** check failed\n");
124 fprintf(stderr, "*** group: %s\n", v[0].buf);
125 fprintf(stderr, "*** expected: %s\n", v[1].buf);
126 fprintf(stderr, "*** returned: %s\n", e);
127 }
128 assert(mparena_count(MPARENA_GLOBAL) == 0);
129 return (ok);
130 }
131
132 static int vcheckelt(dstr *v)
133 {
134 group *g = getgroup(v[0].buf);
135 ge *x = getge(g, v[1].buf);
136 int ir = *(int *)v[2].buf;
137 int ic = group_check(g, x);
138 int ok = 1;
139 if (ir != ic) {
140 ok = 0;
141 fprintf(stderr, "*** check failed\n");
142 fprintf(stderr, "*** group: %s\n", v[0].buf);
143 show(g, "x", x);
144 fprintf(stderr, "*** expected %s\n", ir ? "failure" : "success");
145 }
146 G_DESTROY(g, x);
147 G_DESTROYGROUP(g);
148 assert(mparena_count(MPARENA_GLOBAL) == 0);
149 return (ok);
150 }
151
152 static int vmul(dstr *v)
153 {
154 group *g = getgroup(v[0].buf);
155 ge *x = getge(g, v[1].buf);
156 ge *y = getge(g, v[2].buf);
157 ge *r = getge(g, v[3].buf);
158 ge *c = G_CREATE(g);
159 int ok = 1;
160 G_MUL(g, c, x, y);
161 ok &= check("mul", v[0].buf, g, r, c, "x", x, "y", y, (char *)0);
162 G_DESTROY(g, x); G_DESTROY(g, y); G_DESTROY(g, r); G_DESTROY(g, c);
163 G_DESTROYGROUP(g);
164 assert(mparena_count(MPARENA_GLOBAL) == 0);
165 return (ok);
166 }
167
168 static int vsqr(dstr *v)
169 {
170 group *g = getgroup(v[0].buf);
171 ge *x = getge(g, v[1].buf);
172 ge *r = getge(g, v[2].buf);
173 ge *c = G_CREATE(g);
174 int ok = 1;
175 G_SQR(g, c, x);
176 ok &= check("sqr", v[0].buf, g, r, c, "x", x, (char *)0);
177 G_DESTROY(g, x); G_DESTROY(g, r); G_DESTROY(g, c);
178 G_DESTROYGROUP(g);
179 assert(mparena_count(MPARENA_GLOBAL) == 0);
180 return (ok);
181 }
182
183 static int vinv(dstr *v)
184 {
185 group *g = getgroup(v[0].buf);
186 ge *x = getge(g, v[1].buf);
187 ge *r = getge(g, v[2].buf);
188 ge *c = G_CREATE(g);
189 int ok = 1;
190 G_INV(g, c, x);
191 ok &= check("inv", v[0].buf, g, r, c, "x", x, (char *)0);
192 G_DESTROY(g, x); G_DESTROY(g, r); G_DESTROY(g, c);
193 G_DESTROYGROUP(g);
194 assert(mparena_count(MPARENA_GLOBAL) == 0);
195 return (ok);
196 }
197
198 static int vdiv(dstr *v)
199 {
200 group *g = getgroup(v[0].buf);
201 ge *x = getge(g, v[1].buf);
202 ge *y = getge(g, v[2].buf);
203 ge *r = getge(g, v[3].buf);
204 ge *c = G_CREATE(g);
205 int ok = 1;
206 G_DIV(g, c, x, y);
207 ok &= check("div", v[0].buf, g, r, c, "x", x, "y", y, (char *)0);
208 group_stddiv(g, c, x, y);
209 ok &= check("stddiv", v[0].buf, g, r, c, "x", x, "y", y, (char *)0);
210 G_DESTROY(g, x); G_DESTROY(g, y); G_DESTROY(g, r); G_DESTROY(g, c);
211 G_DESTROYGROUP(g);
212 assert(mparena_count(MPARENA_GLOBAL) == 0);
213 return (ok);
214 }
215
216 static int vexp(dstr *v)
217 {
218 group *g = getgroup(v[0].buf);
219 ge *x = getge(g, v[1].buf);
220 mp *n = *(mp **)v[2].buf;
221 ge *r = getge(g, v[3].buf);
222 ge *c = G_CREATE(g);
223 int ok = 1;
224 G_EXP(g, c, x, n);
225 if (!G_EQ(g, r, c)) {
226 ok = 0;
227 fprintf(stderr, "\n*** exp failed\n");
228 fprintf(stderr, "*** group: %s\n", v[0].buf);
229 show(g, "x", x); showmp("n", n, 10);
230 show(g, "expected", r); show(g, "computed", c);
231 }
232 group_stdexp(g, c, x, n);
233 if (!G_EQ(g, r, c)) {
234 ok = 0;
235 fprintf(stderr, "\n*** stdexp failed\n");
236 fprintf(stderr, "*** group: %s\n", v[0].buf);
237 show(g, "x", x); showmp("n", n, 10);
238 show(g, "expected", r); show(g, "computed", c);
239 }
240 G_DESTROY(g, x); MP_DROP(n); G_DESTROY(g, r); G_DESTROY(g, c);
241 G_DESTROYGROUP(g);
242 assert(mparena_count(MPARENA_GLOBAL) == 0);
243 return (ok);
244 }
245
246 static int vmexp(size_t n, dstr *v)
247 {
248 group *g = getgroup(v[0].buf);
249 ge *c, *r;
250 group_expfactor *f = xmalloc(n * sizeof(group_expfactor));
251 int ok = 1;
252 size_t i;
253 for (i = 0; i < n; i++) {
254 f[i].base = getge(g, v[1 + 2 * i].buf);
255 f[i].exp = *(mp **)v[2 + 2 * i].buf;
256 }
257 r = getge(g, v[1 + 2 * n].buf);
258 c = G_CREATE(g);
259 G_MEXP(g, c, f, n);
260 if (!G_EQ(g, r, c)) {
261 ok = 0;
262 fprintf(stderr, "\n*** mexp failed\n");
263 fprintf(stderr, "*** group: %s\n", v[0].buf);
264 for (i = 0; i < n; i++) {
265 show(g, "base", f[i].base);
266 showmp("exp", f[i].exp, 10);
267 }
268 show(g, "expected", r); show(g, "computed", c);
269 }
270 group_stdmexp(g, c, f, n);
271 if (!G_EQ(g, r, c)) {
272 ok = 0;
273 fprintf(stderr, "\n*** stdmexp failed\n");
274 fprintf(stderr, "*** group: %s\n", v[0].buf);
275 for (i = 0; i < n; i++) {
276 show(g, "base", f[i].base);
277 showmp("exp", f[i].exp, 10);
278 }
279 show(g, "expected", r); show(g, "computed", c);
280 }
281 for (i = 0; i < n; i++) { G_DESTROY(g, f[i].base); MP_DROP(f[i].exp); }
282 G_DESTROY(g, r); G_DESTROY(g, c);
283 G_DESTROYGROUP(g);
284 assert(mparena_count(MPARENA_GLOBAL) == 0);
285 return (ok);
286 }
287
288 static int vmexp1(dstr *v) { return vmexp(1, v); }
289 static int vmexp2(dstr *v) { return vmexp(2, v); }
290 static int vmexp3(dstr *v) { return vmexp(3, v); }
291 static int vmexp4(dstr *v) { return vmexp(4, v); }
292
293 static int vtoint(dstr *v)
294 {
295 group *g = getgroup(v[0].buf);
296 ge *x = getge(g, v[1].buf);
297 int ir = *(int *)v[2].buf;
298 mp *r = *(mp **)v[3].buf;
299 mp *c;
300 int ic;
301 int ok = 1;
302 c = G_TOINT(g, MP_NEW, x);
303 ic = c ? 0 : -1;
304 if (ir != ic || (!ic && !MP_EQ(r, c))) {
305 ok = 0;
306 fprintf(stderr, "\n*** toint failed\n");
307 fprintf(stderr, "*** group: %s\n", v[0].buf);
308 if (ir) fprintf(stderr, "*** expected failure\n");
309 else { show(g, "x", x); showmp("expected", r, 16);
310 showmp("computed", c, 16); }
311 }
312 G_DESTROY(g, x); mp_drop(r); mp_drop(c);
313 G_DESTROYGROUP(g);
314 assert(mparena_count(MPARENA_GLOBAL) == 0);
315 return (ok);
316 }
317
318 static int vfromint(dstr *v)
319 {
320 group *g = getgroup(v[0].buf);
321 mp *x = *(mp **)v[1].buf;
322 int ir = *(int *)v[2].buf;
323 ge *r = getge(g, v[3].buf);
324 int ic;
325 ge *c = G_CREATE(g);
326 int ok = 1;
327 ic = G_FROMINT(g, c, x);
328 if (ir != ic || (!ic && !G_EQ(g, r, c))) {
329 ok = 0;
330 fprintf(stderr, "\n*** fromint failed\n");
331 fprintf(stderr, "*** group: %s\n", v[0].buf);
332 showmp("x", x, 16); if (ir) fprintf(stderr, "*** should have failed\n");
333 else { show(g, "expected", r); show(g, "computed", c); }
334 }
335 MP_DROP(x); G_DESTROY(g, r); G_DESTROY(g, c);
336 G_DESTROYGROUP(g);
337 assert(mparena_count(MPARENA_GLOBAL) == 0);
338 return (ok);
339 }
340
341 static int vtoec(dstr *v)
342 {
343 group *g = getgroup(v[0].buf);
344 ge *x = getge(g, v[1].buf);
345 int ir = *(int *)v[2].buf;
346 ec *r = (ec *)v[3].buf;
347 int ic;
348 ec c = EC_INIT;
349 int ok = 1;
350 ic = G_TOEC(g, &c, x);
351 if (ir != ic || (!ic && !EC_EQ(r, &c))) {
352 ok = 0;
353 fprintf(stderr, "\n*** toec failed\n");
354 fprintf(stderr, "*** group: %s\n", v[0].buf);
355 show(g, "x", x);
356 if (ir) fprintf(stderr, "*** should have failed\n");
357 else { showec("expected", r); showec("computed", &c); }
358 }
359 G_DESTROY(g, x); EC_DESTROY(&c); EC_DESTROY(r);
360 G_DESTROYGROUP(g);
361 assert(mparena_count(MPARENA_GLOBAL) == 0);
362 return (ok);
363 }
364
365 static int vfromec(dstr *v)
366 {
367 group *g = getgroup(v[0].buf);
368 ec *p = (ec *)v[1].buf;
369 int ir = *(int *)v[2].buf;
370 ge *r = getge(g, v[3].buf);
371 int ic;
372 ge *c = G_CREATE(g);
373 int ok = 1;
374 ic = G_FROMEC(g, c, p);
375 if (ir != ic || (!ic && !G_EQ(g, r, c))) {
376 ok = 0;
377 fprintf(stderr, "\n*** fromec failed\n");
378 fprintf(stderr, "*** group: %s\n", v[0].buf);
379 showec("p", p); if (ir) fprintf(stderr, "*** should have failed\n");
380 else { show(g, "expected", r); show(g, "computed", c); }
381 }
382 EC_DESTROY(p); G_DESTROY(g, r); G_DESTROY(g, c);
383 G_DESTROYGROUP(g);
384 assert(mparena_count(MPARENA_GLOBAL) == 0);
385 return (ok);
386 }
387
388 static int vtobuf(dstr *v)
389 {
390 group *g = getgroup(v[0].buf);
391 ge *x = getge(g, v[1].buf);
392 int ir = *(int *)v[2].buf;
393 dstr c = DSTR_INIT;
394 int ic;
395 buf b;
396 int ok = 1;
397
398 dstr_ensure(&c, v[3].len);
399 buf_init(&b, c.buf, v[3].len);
400 ic = G_TOBUF(g, &b, x);
401 c.len = BLEN(&b);
402 if (ic != ir || (!ic && (c.len != v[3].len ||
403 memcmp(c.buf, v[3].buf, c.len)))) {
404 ok = 0;
405 fprintf(stderr, "*** tobuf failed\n");
406 fprintf(stderr, "*** group: %s\n", v[0].buf);
407 show(g, "x", x);
408 if (ir) fprintf(stderr, "*** expected failure\n");
409 else {
410 fprintf(stderr, "*** expected: "); type_hex.dump(&v[3], stderr);
411 fprintf(stderr, "\n*** computed: "); type_hex.dump(&c, stderr);
412 fputc('\n', stderr);
413 }
414 }
415 G_DESTROY(g, x); dstr_destroy(&c);
416 G_DESTROYGROUP(g);
417 assert(mparena_count(MPARENA_GLOBAL) == 0);
418 return (ok);
419 }
420
421 static int vfrombuf(dstr *v)
422 {
423 group *g = getgroup(v[0].buf);
424 int ir = *(int *)v[2].buf;
425 ge *r = getge(g, v[3].buf);
426 int ic;
427 ge *c = G_CREATE(g);
428 buf b;
429 int ok = 1;
430
431 buf_init(&b, v[1].buf, v[1].len);
432 ic = G_FROMBUF(g, &b, c);
433 if ((ic < 0) != (ir < 0) || (ir >= 0 &&
434 (ir != BLEN(&b) || !G_EQ(g, r, c)))) {
435 ok = 0;
436 fprintf(stderr, "*** frombuf failed\n");
437 fprintf(stderr, "*** group: %s\n", v[0].buf);
438 fprintf(stderr, "*** input string: "); type_hex.dump(&v[1], stderr);
439 fputc('\n', stderr);
440 if (ir < 0) fprintf(stderr, "*** expected failure\n");
441 else {
442 show(g, "expected", r); show(g, "computed", c);
443 fprintf(stderr, "*** expected used = %d\n", ir);
444 fprintf(stderr, "*** computed used = %lu\n", (unsigned long)BLEN(&b));
445 }
446 }
447 G_DESTROY(g, r); G_DESTROY(g, c);
448 G_DESTROYGROUP(g);
449 assert(mparena_count(MPARENA_GLOBAL) == 0);
450 return (ok);
451 }
452
453 static const test_chunk tests[] = {
454 { "check", vcheck, { &type_string, &type_string } },
455 { "checkelt", vcheckelt, { &type_string, &type_string, &type_int } },
456 { "mul", vmul, { &type_string, &type_string,
457 &type_string, &type_string } },
458 { "sqr", vsqr, { &type_string, &type_string,
459 &type_string } },
460 { "inv", vinv, { &type_string, &type_string,
461 &type_string } },
462 { "div", vdiv, { &type_string, &type_string,
463 &type_string, &type_string } },
464 { "exp", vexp, { &type_string, &type_string,
465 &type_mp, &type_string } },
466 { "mexp-1", vmexp1, { &type_string,
467 &type_string, &type_mp,
468 &type_string } },
469 { "mexp-2", vmexp2, { &type_string,
470 &type_string, &type_mp,
471 &type_string, &type_mp,
472 &type_string } },
473 { "mexp-3", vmexp3, { &type_string,
474 &type_string, &type_mp,
475 &type_string, &type_mp,
476 &type_string, &type_mp,
477 &type_string } },
478 { "mexp-4", vmexp4, { &type_string,
479 &type_string, &type_mp,
480 &type_string, &type_mp,
481 &type_string, &type_mp,
482 &type_string, &type_mp,
483 &type_string } },
484 { "toint", vtoint, { &type_string, &type_string,
485 &type_int, &type_mp } },
486 { "fromint", vfromint, { &type_string, &type_mp,
487 &type_int, &type_string } },
488 { "toec", vtoec, { &type_string, &type_string,
489 &type_int, &type_ec } },
490 { "fromec", vfromec, { &type_string, &type_ec,
491 &type_int, &type_string } },
492 { "tobuf", vtobuf, { &type_string, &type_string,
493 &type_int, &type_hex } },
494 { "frombuf", vfrombuf, { &type_string, &type_hex,
495 &type_int, &type_string } },
496 { 0 }
497 };
498
499 int main(int argc, char *argv[])
500 {
501 sub_init();
502 test_run(argc, argv, tests, SRCDIR "/tests/group");
503 return (0);
504 }
505
506 /*----- That's all, folks -------------------------------------------------*/
Catacomb cryptographic library (downstream of http://git.distorted.org.uk/~mdw/catacomb/)