projects / u / mdw / catacomb / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Test elliptic curves more thoroughly.
[u/mdw/catacomb] / ec-test.c
1 /* -*-c-*-
2 *
3 * $Id: ec-test.c,v 1.1 2004/03/23 15:19:32 mdw Exp $
4 *
5 * Code for testing elliptic-curve stuff
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: ec-test.c,v $
33 * Revision 1.1 2004/03/23 15:19:32 mdw
34 * Test elliptic curves more thoroughly.
35 *
36 */
37
38 /*----- Header files ------------------------------------------------------*/
39
40 #include <assert.h>
41 #include <ctype.h>
42 #include <stdio.h>
43 #include <stdlib.h>
44 #include <string.h>
45
46 #include <mLib/alloc.h>
47 #include <mLib/testrig.h>
48 #include <mLib/sub.h>
49
50 #include "ec.h"
51 #include "ec-test.h"
52
53 /*----- Cardboard cut-out elliptic curve ----------------------------------*/
54
55 typedef struct ecctx {
56 ec_curve c;
57 unsigned long magic;
58 char *name;
59 ec_curve *real;
60 } ecctx;
61
62 #define MAGIC 0x3a1f0b07
63
64 static void ecDESTROY(ec_curve *cc)
65 {
66 ecctx *c = (ecctx *)cc;
67 xfree(c->name);
68 ec_destroycurve(c->real);
69 DESTROY(c);
70 }
71
72 #define UNOP(OP) \
73 static ec *ec##OP(ec_curve *cc, ec *d, const ec *p) { \
74 ecctx *c = (ecctx *)cc; \
75 return (EC_##OP(c->real, d, p)); \
76 }
77
78 #define BINOP(OP) \
79 static ec *ec##OP(ec_curve *cc, ec *d, const ec *p, const ec *q) { \
80 ecctx *c = (ecctx *)cc; \
81 return (EC_##OP(c->real, d, p, q)); \
82 }
83
84 UNOP(IN)
85 UNOP(OUT)
86 UNOP(FIX)
87 UNOP(NEG)
88 UNOP(DBL)
89 BINOP(ADD)
90 BINOP(SUB)
91
92 #undef UNOP
93 #undef BINOP
94
95 static ec *ecFIND(ec_curve *cc, ec *d, mp *x)
96 {
97 ecctx *c = (ecctx *)cc;
98 return (EC_FIND(c->real, d, x));
99 }
100
101 static int ecCHECK(ec_curve *cc, const ec *p)
102 {
103 ecctx *c = (ecctx *)cc;
104 return (EC_CHECK(c->real, p));
105 }
106
107 static ec_ops ecops = {
108 ecDESTROY, ecIN, ecOUT, ecFIX,
109 ecFIND, ecNEG, ecADD, ecSUB, ecDBL, ecCHECK
110 };
111
112 static ec_curve *ec_cutout(ec_curve *real, const char *name)
113 {
114 ecctx *c = CREATE(ecctx);
115 c->c.f = real->f;
116 c->c.ops = &ecops;
117 c->magic = MAGIC;
118 c->name = xstrdup(name);
119 c->real = real;
120 return (&c->c);
121 }
122
123 static const char *ec_name(ec_curve *cc)
124 {
125 ecctx *c = (ecctx *)cc;
126 assert(c->magic == MAGIC);
127 return (c->name);
128 }
129
130 /*----- Test field types --------------------------------------------------*
131 *
132 * Really lazy parser. Sorry.
133 */
134
135 static void skipws(const char **p)
136 {
137 while (isspace((unsigned char)**p)) (*p)++;
138 }
139
140 static void ckchar(const char **p, int ch)
141 { skipws(p); if (**p == ch) (*p)++; }
142
143 static void ckend(const char **p)
144 {
145 skipws(p);
146 if (**p) {
147 fprintf(stderr, "syntax error: junk at end of line\n");
148 abort();
149 }
150 }
151
152 static int ckstring(const char **p, const char **s)
153 {
154 int i;
155 size_t n;
156
157 skipws(p);
158 for (i = 0; s[i]; i++) {
159 n = strlen(s[i]);
160 if (strncmp(*p, s[i], n) == 0 && !isalnum((unsigned char)(*p)[n])) {
161 *p += n;
162 return (i);
163 }
164 }
165 fprintf(stderr, "syntax error: couldn't recognize keyword\n");
166 abort();
167 }
168
169 static mp *getmp(const char **p)
170 {
171 char *q;
172 mp *m;
173 skipws(p);
174 m = mp_readstring(MP_NEW, *p, &q, 0);
175 if (!m || isalnum((unsigned char)*q)) {
176 fprintf(stderr, "syntax error: bad number\n");
177 abort();
178 }
179 *p = q;
180 return (m);
181 }
182
183 static void ecvcvt(const char *buf, dstr *d)
184 {
185 field *f;
186 ec_curve *v;
187 mp *m, *n;
188 const char *p = buf;
189 int i;
190
191 static const char *fnames[] = {
192 "prime", "binpoly", 0
193 };
194 static const char *ecnames[] = {
195 "prime", "primeproj", "bin", "binproj", 0
196 };
197
198 switch (i = ckstring(&p, fnames), ckchar(&p, ':'), i) {
199 case 0: m = getmp(&p); f = field_prime(m); mp_drop(m); break;
200 case 1: m = getmp(&p); f = field_binpoly(m); mp_drop(m); break;
201 default: abort();
202 }
203 ckchar(&p, '/');
204
205 switch (i = ckstring(&p, ecnames), ckchar(&p, ':'), i) {
206 case 0: m = getmp(&p); ckchar(&p, ','); n = getmp(&p);
207 v = ec_prime(f, m, n); mp_drop(m); mp_drop(n); break;
208 case 1: m = getmp(&p); ckchar(&p, ','); n = getmp(&p);
209 v = ec_primeproj(f, m, n); mp_drop(m); mp_drop(n); break;
210 case 2: m = getmp(&p); ckchar(&p, ','); n = getmp(&p);
211 v = ec_bin(f, m, n); mp_drop(m); mp_drop(n); break;
212 case 3: m = getmp(&p); ckchar(&p, ','); n = getmp(&p);
213 v = ec_binproj(f, m, n); mp_drop(m); mp_drop(n); break;
214 default: abort();
215 }
216 ckend(&p);
217
218 dstr_ensure(d, sizeof(v));
219 *(ec_curve **)d->buf = ec_cutout(v, buf);
220 d->len += sizeof(v);
221 }
222
223 static void ecvdump(dstr *d, FILE *fp)
224 {
225 ec_curve *v = *(ec_curve **)d->buf;
226 fprintf(fp, "%s", ec_name(v));
227 }
228
229 test_type type_ecurve = { ecvcvt, ecvdump };
230
231 static void eccvt(const char *p, dstr *d)
232 {
233 ec *a;
234
235 dstr_ensure(d, sizeof(ec));
236 a = (ec *)d->buf;
237 d->len += sizeof(ec);
238 ec_create(a);
239 skipws(&p);
240 if (strcmp(p, "inf") == 0)
241 EC_SETINF(a);
242 else
243 { a->x = getmp(&p); ckchar(&p, ','); a->y = getmp(&p); ckend(&p); }
244 }
245
246 static void ecdodump(ec *a, FILE *fp)
247 {
248 if (EC_ATINF(a))
249 fputs("inf", fp);
250 else {
251 fputs("0x", fp);
252 mp_writefile(a->x, fp, 16);
253 fputs(", 0x", fp);
254 mp_writefile(a->y, fp, 16);
255 }
256 }
257
258 static void ecdump(dstr *d, FILE *fp)
259 {
260 ec *a = (ec *)d->buf;
261 ecdodump(a, fp);
262 }
263
264 test_type type_ec = { eccvt, ecdump };
265
266 /*----- Testing elliptic curve functionality ------------------------------*/
267
268 #ifdef TEST_RIG
269
270 static void ecdestroy(ec_curve *c)
271 {
272 field *f = c->f;
273 ec_destroycurve(c);
274 F_DESTROY(f);
275 }
276
277 #define UNOP(op) \
278 static int v##op(dstr v[]) \
279 { \
280 ec_curve *e = *(ec_curve **)v[0].buf; \
281 ec *a = (ec *)v[1].buf; \
282 ec *r = (ec *)v[2].buf; \
283 ec c = EC_INIT; \
284 int ok = 1; \
285 ec_##op(e, &c, a); \
286 if (!EC_EQ(r, &c)) { \
287 fprintf(stderr, #op "failed"); \
288 fprintf(stderr, "\ncurve = "); type_ecurve.dump(v, stderr); \
289 fprintf(stderr, "\n a = "); ecdodump(a, stderr); \
290 fprintf(stderr, "\n r = "); ecdodump(r, stderr); \
291 fprintf(stderr, "\n c = "); ecdodump(&c, stderr); \
292 fprintf(stderr, "\n"); \
293 ok = 0; \
294 } \
295 EC_DESTROY(a); EC_DESTROY(r); EC_DESTROY(&c); \
296 ecdestroy(e); \
297 return (ok); \
298 }
299
300 #define BINOP(op) \
301 static int v##op(dstr v[]) \
302 { \
303 ec_curve *e = *(ec_curve **)v[0].buf; \
304 ec *a = (ec *)v[1].buf; \
305 ec *b = (ec *)v[2].buf; \
306 ec *r = (ec *)v[3].buf; \
307 ec c = EC_INIT; \
308 int ok = 1; \
309 ec_##op(e, &c, a, b); \
310 if (!EC_EQ(r, &c)) { \
311 fprintf(stderr, #op "failed"); \
312 fprintf(stderr, "\ncurve = "); type_ecurve.dump(v, stderr); \
313 fprintf(stderr, "\n a = "); ecdodump(a, stderr); \
314 fprintf(stderr, "\n b = "); ecdodump(b, stderr); \
315 fprintf(stderr, "\n r = "); ecdodump(r, stderr); \
316 fprintf(stderr, "\n c = "); ecdodump(&c, stderr); \
317 fprintf(stderr, "\n"); \
318 ok = 0; \
319 } \
320 EC_DESTROY(a); EC_DESTROY(b); EC_DESTROY(r); EC_DESTROY(&c); \
321 ecdestroy(e); \
322 return (ok); \
323 }
324
325 UNOP(neg)
326 UNOP(dbl)
327 BINOP(add)
328 BINOP(sub)
329
330 static int vcheck(dstr v[])
331 {
332 ec_curve *e = *(ec_curve **)v[0].buf;
333 ec *a = (ec *)v[1].buf;
334 int r = *(int *)v[2].buf;
335 int c;
336 int ok = 1;
337 c = ec_check(e, a);
338 if (r != c) {
339 fprintf(stderr, "check failed");
340 fprintf(stderr, "\ncurve = "); type_ecurve.dump(v, stderr);
341 fprintf(stderr, "\n a = "); ecdodump(a, stderr);
342 fprintf(stderr, "\n r = %d", r);
343 fprintf(stderr, "\n c = %d", c);
344 fprintf(stderr, "\n");
345 ok = 0;
346 }
347 EC_DESTROY(a);
348 ecdestroy(e);
349 return (ok);
350 }
351
352 static int vmul(dstr v[])
353 {
354 ec_curve *e = *(ec_curve **)v[0].buf;
355 ec *a = (ec *)v[1].buf;
356 mp *n = *(mp **)v[2].buf;
357 ec *r = (ec *)v[3].buf;
358 ec c = EC_INIT;
359 int ok = 1;
360 ec_mul(e, &c, a, n);
361 if (!EC_EQ(r, &c)) {
362 fprintf(stderr, "mul failed");
363 fprintf(stderr, "\ncurve = "); type_ecurve.dump(v, stderr);
364 fprintf(stderr, "\n a = "); ecdodump(a, stderr);
365 fprintf(stderr, "\n n = "); mp_writefile(n, stderr, 10);
366 fprintf(stderr, "\n r = "); ecdodump(r, stderr);
367 fprintf(stderr, "\n c = "); ecdodump(&c, stderr);
368 fprintf(stderr, "\n");
369 ok = 0;
370 }
371 EC_DESTROY(a); EC_DESTROY(r); EC_DESTROY(&c); MP_DROP(n);
372 ecdestroy(e);
373 return (ok);
374 }
375
376 static int vfind(dstr v[])
377 {
378 ec_curve *e = *(ec_curve **)v[0].buf;
379 mp *x = *(mp **)v[1].buf;
380 ec *r = (ec *)v[2].buf;
381 ec c = EC_INIT;
382 int ok = 1;
383 if (!ec_find(e, &c, x)) EC_SETINF(&c);
384 if (!EC_EQ(r, &c)) {
385 fprintf(stderr, "find failed");
386 fprintf(stderr, "\ncurve = "); type_ecurve.dump(v, stderr);
387 fprintf(stderr, "\n x = "); mp_writefile(x, stderr, 16);
388 fprintf(stderr, "\n r = "); ecdodump(r, stderr);
389 fprintf(stderr, "\n c = "); ecdodump(&c, stderr);
390 fprintf(stderr, "\n");
391 ok = 0;
392 }
393 MP_DROP(x); EC_DESTROY(r); EC_DESTROY(&c);
394 ecdestroy(e);
395 return (ok);
396 }
397
398 static test_chunk tests[] = {
399 { "neg", vneg, { &type_ecurve, &type_ec, &type_ec } },
400 { "dbl", vdbl, { &type_ecurve, &type_ec, &type_ec } },
401 { "add", vadd, { &type_ecurve, &type_ec, &type_ec, &type_ec } },
402 { "sub", vsub, { &type_ecurve, &type_ec, &type_ec, &type_ec } },
403 { "mul", vmul, { &type_ecurve, &type_ec, &type_mp, &type_ec } },
404 { "check", vcheck, { &type_ecurve, &type_ec, &type_int } },
405 { "find", vfind, { &type_ecurve, &type_mp, &type_ec } },
406 { 0, 0, { 0 } }
407 };
408
409 int main(int argc, char *argv[])
410 {
411 sub_init();
412 test_run(argc, argv, tests, SRCDIR "/tests/ec");
413 return (0);
414 }
415
416 #endif
417
418 /*----- That's all, folks -------------------------------------------------*/
Catacomb cryptographic library (downstream of http://git.distorted.org.uk/~mdw/catacomb/)