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