~mdw / catacomb / blob
? search:


d9cda6ff6217e384e837e33f5bcab0c0b9565ec5
[catacomb] / math / ec-test.c
1 /* -*-c-*-
2 *
3 * Code for testing elliptic-curve stuff
4 *
5 * (c) 2004 Straylight/Edgeware
6 */
7
8 /*----- Licensing notice --------------------------------------------------*
9 *
10 * This file is part of Catacomb.
11 *
12 * Catacomb is free software; you can redistribute it and/or modify
13 * it under the terms of the GNU Library General Public License as
14 * published by the Free Software Foundation; either version 2 of the
15 * License, or (at your option) any later version.
16 *
17 * Catacomb is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU Library General Public License for more details.
21 *
22 * You should have received a copy of the GNU Library General Public
23 * License along with Catacomb; if not, write to the Free
24 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
25 * MA 02111-1307, USA.
26 */
27
28 /*----- Header files ------------------------------------------------------*/
29
30 #include <assert.h>
31 #include <ctype.h>
32 #include <stdio.h>
33 #include <stdlib.h>
34 #include <string.h>
35
36 #include <mLib/alloc.h>
37 #include <mLib/testrig.h>
38 #include <mLib/sub.h>
39
40 #include "ec.h"
41 #include "ectab.h"
42 #include "ec-raw.h"
43 #include "ec-test.h"
44
45 /*----- Cardboard cut-out elliptic curve ----------------------------------*/
46
47 typedef struct ecctx {
48 ec_curve c;
49 unsigned long magic;
50 char *name;
51 ec_curve *real;
52 } ecctx;
53
54 #define MAGIC 0x3a1f0b07
55
56 static void ecDESTROY(ec_curve *cc)
57 {
58 ecctx *c = (ecctx *)cc;
59 xfree(c->name);
60 ec_destroycurve(c->real);
61 DESTROY(c);
62 }
63
64 #define UNOP(OP) \
65 static ec *ec##OP(ec_curve *cc, ec *d, const ec *p) { \
66 ecctx *c = (ecctx *)cc; \
67 return (EC_##OP(c->real, d, p)); \
68 }
69
70 #define BINOP(OP) \
71 static ec *ec##OP(ec_curve *cc, ec *d, const ec *p, const ec *q) { \
72 ecctx *c = (ecctx *)cc; \
73 return (EC_##OP(c->real, d, p, q)); \
74 }
75
76 UNOP(IN)
77 UNOP(OUT)
78 UNOP(FIX)
79 UNOP(NEG)
80 UNOP(DBL)
81 BINOP(ADD)
82 BINOP(SUB)
83
84 #undef UNOP
85 #undef BINOP
86
87 static ec *ecFIND(ec_curve *cc, ec *d, mp *x)
88 {
89 ecctx *c = (ecctx *)cc;
90 return (EC_FIND(c->real, d, x));
91 }
92
93 static int ecCOMPR(ec_curve *cc, const ec *p)
94 {
95 ecctx *c = (ecctx *)cc;
96 return (EC_COMPR(c->real, p));
97 }
98
99 static int ecCHECK(ec_curve *cc, const ec *p)
100 {
101 ecctx *c = (ecctx *)cc;
102 return (EC_CHECK(c->real, p));
103 }
104
105 static int ecSAMEP(ec_curve *cc, ec_curve *dd)
106 {
107 ecctx *c = (ecctx *)cc, *d = (ecctx *)dd;
108 return (ec_samep(c->real, d->real));
109 }
110
111 static const ec_ops ecops = {
112 "cardboard",
113 ecDESTROY, ecSAMEP, ecIN, ecOUT, ecFIX,
114 ecFIND, ecNEG, ecADD, ecSUB, ecDBL, ecCHECK, ecCOMPR
115 };
116
117 static ec_curve *ec_cutout(ec_curve *real, const char *name)
118 {
119 ecctx *c = CREATE(ecctx);
120 c->c.f = real->f;
121 c->c.ops = &ecops;
122 c->c.a = real->a;
123 c->c.b = real->b;
124 c->magic = MAGIC;
125 c->name = xstrdup(name);
126 c->real = real;
127 return (&c->c);
128 }
129
130 static const char *ec_name(ec_curve *cc)
131 {
132 ecctx *c = (ecctx *)cc;
133 assert(c->magic == MAGIC);
134 return (c->name);
135 }
136
137 /*----- Test field types --------------------------------------------------*/
138
139 static void ecvcvt(const char *buf, dstr *d)
140 {
141 ec_curve *v;
142 qd_parse qd;
143 const ecentry *ee;
144 ec_info ei;
145
146 qd.p = buf;
147 qd.e = 0;
148 for (ee = ectab; ee->name; ee++) {
149 if (qd_enum(&qd, ee->name) >= 0) {
150 ec_infofromdata(&ei, ee->data);
151 v = ei.c;
152 MP_DROP(ei.r); MP_DROP(ei.h);
153 EC_DESTROY(&ei.g);
154 goto found;
155 }
156 }
157 if ((v = ec_curveparse(&qd)) == 0) {
158 fprintf(stderr, "bad curve `%.*s|%s': %s\n",
159 (int)(qd.p - buf), buf, qd.p, qd.e);
160 exit(1);
161 }
162 found:
163 dstr_ensure(d, sizeof(v));
164 *(ec_curve **)d->buf = ec_cutout(v, buf);
165 d->len += sizeof(v);
166 }
167
168 static void ecvdump(dstr *d, FILE *fp)
169 {
170 ec_curve *v = *(ec_curve **)d->buf;
171 fprintf(fp, "%s", ec_name(v));
172 }
173
174 const test_type type_ecurve = { ecvcvt, ecvdump };
175
176 static void eccvt(const char *p, dstr *d)
177 {
178 ec *a;
179 qd_parse qd;
180
181 qd.p = p;
182 qd.e = 0;
183 dstr_ensure(d, sizeof(ec));
184 a = (ec *)d->buf;
185 d->len += sizeof(ec);
186 ec_create(a);
187 if (!ec_ptparse(&qd, a)) {
188 fprintf(stderr, "bad point `%.*s|%s': %s\n",
189 (int)(qd.p - p), p, qd.p, qd.e);
190 exit(1);
191 }
192 }
193
194 static void ecdodump(ec *a, FILE *fp)
195 {
196 if (EC_ATINF(a))
197 fputs("inf", fp);
198 else {
199 fputs("0x", fp);
200 mp_writefile(a->x, fp, 16);
201 fputs(", 0x", fp);
202 mp_writefile(a->y, fp, 16);
203 }
204 }
205
206 static void ecdump(dstr *d, FILE *fp)
207 {
208 ec *a = (ec *)d->buf;
209 ecdodump(a, fp);
210 }
211
212 const test_type type_ec = { eccvt, ecdump };
213
214 /*----- Testing elliptic curve functionality ------------------------------*/
215
216 #ifdef TEST_RIG
217
218 static void ecdestroy(ec_curve *c)
219 {
220 field *f = c->f;
221 ec_destroycurve(c);
222 F_DESTROY(f);
223 }
224
225 #define UNOP(op) \
226 static int v##op(dstr v[]) \
227 { \
228 ec_curve *e = *(ec_curve **)v[0].buf; \
229 ec *a = (ec *)v[1].buf; \
230 ec *r = (ec *)v[2].buf; \
231 ec c = EC_INIT; \
232 int ok = 1; \
233 ec_##op(e, &c, a); \
234 if (!EC_EQ(r, &c)) { \
235 fprintf(stderr, #op " failed"); \
236 fprintf(stderr, "\ncurve = "); type_ecurve.dump(v, stderr); \
237 fprintf(stderr, "\n a = "); ecdodump(a, stderr); \
238 fprintf(stderr, "\n r = "); ecdodump(r, stderr); \
239 fprintf(stderr, "\n c = "); ecdodump(&c, stderr); \
240 fprintf(stderr, "\n"); \
241 ok = 0; \
242 } \
243 EC_DESTROY(a); EC_DESTROY(r); EC_DESTROY(&c); \
244 ecdestroy(e); \
245 return (ok); \
246 }
247
248 #define BINOP(op) \
249 static int v##op(dstr v[]) \
250 { \
251 ec_curve *e = *(ec_curve **)v[0].buf; \
252 ec *a = (ec *)v[1].buf; \
253 ec *b = (ec *)v[2].buf; \
254 ec *r = (ec *)v[3].buf; \
255 ec c = EC_INIT; \
256 int ok = 1; \
257 ec_##op(e, &c, a, b); \
258 if (!EC_EQ(r, &c)) { \
259 fprintf(stderr, #op " failed"); \
260 fprintf(stderr, "\ncurve = "); type_ecurve.dump(v, stderr); \
261 fprintf(stderr, "\n a = "); ecdodump(a, stderr); \
262 fprintf(stderr, "\n b = "); ecdodump(b, stderr); \
263 fprintf(stderr, "\n r = "); ecdodump(r, stderr); \
264 fprintf(stderr, "\n c = "); ecdodump(&c, stderr); \
265 fprintf(stderr, "\n"); \
266 ok = 0; \
267 } \
268 EC_DESTROY(a); EC_DESTROY(b); EC_DESTROY(r); EC_DESTROY(&c); \
269 ecdestroy(e); \
270 return (ok); \
271 }
272
273 UNOP(neg)
274 UNOP(dbl)
275 BINOP(add)
276 BINOP(sub)
277
278 static int vcheck(dstr v[])
279 {
280 ec_curve *e = *(ec_curve **)v[0].buf;
281 ec *a = (ec *)v[1].buf;
282 int r = *(int *)v[2].buf;
283 int c;
284 int ok = 1;
285 c = ec_check(e, a);
286 if (r != c) {
287 fprintf(stderr, "check failed");
288 fprintf(stderr, "\ncurve = "); type_ecurve.dump(v, stderr);
289 fprintf(stderr, "\n a = "); ecdodump(a, stderr);
290 fprintf(stderr, "\n r = %d", r);
291 fprintf(stderr, "\n c = %d", c);
292 fprintf(stderr, "\n");
293 ok = 0;
294 }
295 EC_DESTROY(a);
296 ecdestroy(e);
297 return (ok);
298 }
299
300 static int vmul(dstr v[])
301 {
302 ec_curve *e = *(ec_curve **)v[0].buf;
303 ec *a = (ec *)v[1].buf;
304 mp *n = *(mp **)v[2].buf;
305 ec *r = (ec *)v[3].buf;
306 ec c = EC_INIT;
307 int ok = 1;
308 ec_mul(e, &c, a, n);
309 if (!EC_EQ(r, &c)) {
310 fprintf(stderr, "mul failed");
311 fprintf(stderr, "\ncurve = "); type_ecurve.dump(v, stderr);
312 fprintf(stderr, "\n a = "); ecdodump(a, stderr);
313 fprintf(stderr, "\n n = "); mp_writefile(n, stderr, 10);
314 fprintf(stderr, "\n r = "); ecdodump(r, stderr);
315 fprintf(stderr, "\n c = "); ecdodump(&c, stderr);
316 fprintf(stderr, "\n");
317 ok = 0;
318 }
319 EC_DESTROY(a); EC_DESTROY(r); EC_DESTROY(&c); MP_DROP(n);
320 ecdestroy(e);
321 return (ok);
322 }
323
324 static int vfind(dstr v[])
325 {
326 ec_curve *e = *(ec_curve **)v[0].buf;
327 mp *x = *(mp **)v[1].buf;
328 ec *r = (ec *)v[2].buf;
329 ec c = EC_INIT;
330 int ok = 1;
331 if (!ec_find(e, &c, x)) EC_SETINF(&c);
332 if (!EC_EQ(r, &c)) {
333 fprintf(stderr, "find failed");
334 fprintf(stderr, "\ncurve = "); type_ecurve.dump(v, stderr);
335 fprintf(stderr, "\n x = "); mp_writefile(x, stderr, 16);
336 fprintf(stderr, "\n r = "); ecdodump(r, stderr);
337 fprintf(stderr, "\n c = "); ecdodump(&c, stderr);
338 fprintf(stderr, "\n");
339 ok = 0;
340 }
341 MP_DROP(x); EC_DESTROY(r); EC_DESTROY(&c);
342 ecdestroy(e);
343 return (ok);
344 }
345
346 static int vec2osp(dstr v[])
347 {
348 ec_curve *e = *(ec_curve **)v[0].buf;
349 unsigned f = *(int *)v[1].buf;
350 ec *p = (ec *)v[2].buf;
351 size_t n = 1 + 2*e->f->noctets;
352 dstr d = DSTR_INIT, dd = DSTR_INIT;
353 buf b;
354 int ok = 1;
355 int win, wantwin;
356
357 if (strcmp(v[3].buf, "FAIL") == 0) wantwin = 0;
358 else { wantwin = 1; type_hex.cvt(v[3].buf, &d); }
359
360 dstr_ensure(&dd, n); buf_init(&b, dd.buf, n);
361
362 win = !ec_ec2osp(e, f, &b, p);
363 if (!win != !wantwin ||
364 (win && (BLEN(&b) != d.len ||
365 memcmp(BBASE(&b), d.buf, BLEN(&b)) != 0))) {
366 ok = 0;
367 fprintf(stderr, "ec2osp failed");
368 fprintf(stderr, "\ncurve = "); type_ecurve.dump(v, stderr);
369 fprintf(stderr, "\n fmt = 0x%02x", f);
370 fprintf(stderr, "\n p = "); ecdodump(p, stderr);
371 fprintf(stderr, "\n want = ");
372 if (wantwin) type_hex.dump(&d, stderr);
373 else fprintf(stderr, "FAIL");
374 fprintf(stderr, "\nfound = ");
375 if (win) { dd.len = BLEN(&b); type_hex.dump(&dd, stderr); }
376 else fprintf(stderr, "FAIL");
377 fprintf(stderr, "\n");
378 }
379
380 dstr_destroy(&d); dstr_destroy(&dd);
381 EC_DESTROY(p); ecdestroy(e);
382 return (ok);
383 }
384
385 static int vos2ecp(dstr v[])
386 {
387 ec_curve *e = *(ec_curve **)v[0].buf;
388 unsigned f = *(int *)v[1].buf;
389 int remain = *(int *)v[4].buf;
390 dstr d = DSTR_INIT;
391 ec *p, q = EC_INIT;
392 buf b;
393 int ok = 1;
394 int win;
395
396 if (strcmp(v[3].buf, "FAIL") == 0) p = 0;
397 else { type_ec.cvt(v[3].buf, &d); p = (ec *)d.buf; }
398
399 buf_init(&b, v[2].buf, v[2].len);
400 win = !ec_os2ecp(e, f, &b, &q);
401
402 if (!win != !p || (win && (!EC_EQ(p, &q) || BLEFT(&b) != remain))) {
403 ok = 0;
404 fprintf(stderr, "os2ecp failed");
405 fprintf(stderr, "\ncurve = "); type_ecurve.dump(v, stderr);
406 fprintf(stderr, "\n fmt = 0x%02x", f);
407 fprintf(stderr, "\ninput = "); type_hex.dump(&v[2], stderr);
408 fprintf(stderr, "\n want = ");
409 if (p) ecdodump(p, stderr); else fprintf(stderr, "FAIL");
410 fprintf(stderr, "\nfound = ");
411 if (win) ecdodump(&q, stderr); else fprintf(stderr, "FAIL");
412 fprintf(stderr, "\nremain= %d", remain);
413 fprintf(stderr, "\nleft = %d", (int)BLEFT(&b));
414 fprintf(stderr, "\n");
415 }
416
417 if (p) EC_DESTROY(p); EC_DESTROY(&q); ecdestroy(e);
418 dstr_destroy(&d);
419 return (ok);
420 }
421
422 static test_chunk tests[] = {
423 { "neg", vneg, { &type_ecurve, &type_ec, &type_ec } },
424 { "dbl", vdbl, { &type_ecurve, &type_ec, &type_ec } },
425 { "add", vadd, { &type_ecurve, &type_ec, &type_ec, &type_ec } },
426 { "sub", vsub, { &type_ecurve, &type_ec, &type_ec, &type_ec } },
427 { "mul", vmul, { &type_ecurve, &type_ec, &type_mp, &type_ec } },
428 { "check", vcheck, { &type_ecurve, &type_ec, &type_int } },
429 { "find", vfind, { &type_ecurve, &type_mp, &type_ec } },
430 { "ec2osp", vec2osp, { &type_ecurve, &type_int, &type_ec, &type_string } },
431 { "os2ecp", vos2ecp,
432 { &type_ecurve, &type_int, &type_hex, &type_string, &type_int } },
433 { 0, 0, { 0 } }
434 };
435
436 int main(int argc, char *argv[])
437 {
438 sub_init();
439 test_run(argc, argv, tests, SRCDIR "/t/ec");
440 return (0);
441 }
442
443 #endif
444
445 /*----- That's all, folks -------------------------------------------------*/
Catacomb cryptographic library