chiark - git - mdw - catacomb/blob - 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 #include <mLib/macros.h>
 219
 220 static void ecdestroy(ec_curve *c)
 221 {
 222   field *f = c->f;
 223   ec_destroycurve(c);
 224   F_DESTROY(f);
 225 }
 226
 227 #define UNOP(op)                                                        \
 228   static int v##op(dstr v[])                                            \
 229   {                                                                     \
 230     ec_curve *e = *(ec_curve **)v[0].buf;                               \
 231     ec *a = (ec *)v[1].buf;                                             \
 232     ec *r = (ec *)v[2].buf;                                             \
 233     ec c = EC_INIT;                                                     \
 234     int ok = 1;                                                         \
 235     ec_##op(e, &c, a);                                                  \
 236     if (!EC_EQ(r, &c)) {                                                \
 237       fprintf(stderr, #op " failed");                                   \
 238       fprintf(stderr, "\ncurve = "); type_ecurve.dump(v, stderr);       \
 239       fprintf(stderr, "\n    a = "); ecdodump(a, stderr);               \
 240       fprintf(stderr, "\n    r = "); ecdodump(r, stderr);               \
 241       fprintf(stderr, "\n    c = "); ecdodump(&c, stderr);              \
 242       fprintf(stderr, "\n");                                            \
 243       ok = 0;                                                           \
 244     }                                                                   \
 245     EC_DESTROY(a); EC_DESTROY(r); EC_DESTROY(&c);                       \
 246     ecdestroy(e);                                                       \
 247     return (ok);                                                        \
 248   }
 249
 250 #define BINOP(op)                                                       \
 251   static int v##op(dstr v[])                                            \
 252   {                                                                     \
 253     ec_curve *e = *(ec_curve **)v[0].buf;                               \
 254     ec *a = (ec *)v[1].buf;                                             \
 255     ec *b = (ec *)v[2].buf;                                             \
 256     ec *r = (ec *)v[3].buf;                                             \
 257     ec c = EC_INIT;                                                     \
 258     int ok = 1;                                                         \
 259     ec_##op(e, &c, a, b);                                               \
 260     if (!EC_EQ(r, &c)) {                                                \
 261       fprintf(stderr, #op " failed");                                   \
 262       fprintf(stderr, "\ncurve = "); type_ecurve.dump(v, stderr);       \
 263       fprintf(stderr, "\n    a = "); ecdodump(a, stderr);               \
 264       fprintf(stderr, "\n    b = "); ecdodump(b, stderr);               \
 265       fprintf(stderr, "\n    r = "); ecdodump(r, stderr);               \
 266       fprintf(stderr, "\n    c = "); ecdodump(&c, stderr);              \
 267       fprintf(stderr, "\n");                                            \
 268       ok = 0;                                                           \
 269     }                                                                   \
 270     EC_DESTROY(a); EC_DESTROY(b); EC_DESTROY(r); EC_DESTROY(&c);        \
 271     ecdestroy(e);                                                       \
 272     return (ok);                                                        \
 273   }
 274
 275 UNOP(neg)
 276 UNOP(dbl)
 277 BINOP(add)
 278 BINOP(sub)
 279
 280 static int vcheck(dstr v[])
 281 {
 282   ec_curve *e = *(ec_curve **)v[0].buf;
 283   ec *a = (ec *)v[1].buf;
 284   int r = *(int *)v[2].buf;
 285   int c;
 286   int ok = 1;
 287   c = ec_check(e, a);
 288   if (r != c) {
 289     fprintf(stderr, "check failed");
 290     fprintf(stderr, "\ncurve = "); type_ecurve.dump(v, stderr);
 291     fprintf(stderr, "\n    a = "); ecdodump(a, stderr);
 292     fprintf(stderr, "\n    r = %d", r);
 293     fprintf(stderr, "\n    c = %d", c);
 294     fprintf(stderr, "\n");
 295     ok = 0;
 296   }
 297   EC_DESTROY(a);
 298   ecdestroy(e);
 299   return (ok);
 300 }
 301
 302 static int vmul(dstr v[])
 303 {
 304   ec_curve *e = *(ec_curve **)v[0].buf;
 305   ec *a = (ec *)v[1].buf;
 306   mp *n = *(mp **)v[2].buf;
 307   ec *r = (ec *)v[3].buf;
 308   ec c = EC_INIT;
 309   int ok = 1;
 310   ec_mul(e, &c, a, n);
 311   if (!EC_EQ(r, &c)) {
 312     fprintf(stderr, "mul failed");
 313     fprintf(stderr, "\ncurve = "); type_ecurve.dump(v, stderr);
 314     fprintf(stderr, "\n    a = "); ecdodump(a, stderr);
 315     fprintf(stderr, "\n    n = "); mp_writefile(n, stderr, 10);
 316     fprintf(stderr, "\n    r = "); ecdodump(r, stderr);
 317     fprintf(stderr, "\n    c = "); ecdodump(&c, stderr);
 318     fprintf(stderr, "\n");
 319     ok = 0;
 320   }
 321   EC_DESTROY(a); EC_DESTROY(r); EC_DESTROY(&c); MP_DROP(n);
 322   ecdestroy(e);
 323   return (ok);
 324 }
 325
 326 static int vfind(dstr v[])
 327 {
 328   ec_curve *e = *(ec_curve **)v[0].buf;
 329   mp *x = *(mp **)v[1].buf;
 330   ec *r = (ec *)v[2].buf;
 331   ec c = EC_INIT;
 332   int ok = 1;
 333   if (!ec_find(e, &c, x)) EC_SETINF(&c);
 334   if (!EC_EQ(r, &c)) {
 335     fprintf(stderr, "find failed");
 336     fprintf(stderr, "\ncurve = "); type_ecurve.dump(v, stderr);
 337     fprintf(stderr, "\n    x = "); mp_writefile(x, stderr, 16);
 338     fprintf(stderr, "\n    r = "); ecdodump(r, stderr);
 339     fprintf(stderr, "\n    c = "); ecdodump(&c, stderr);
 340     fprintf(stderr, "\n");
 341     ok = 0;
 342   }
 343   MP_DROP(x); EC_DESTROY(r); EC_DESTROY(&c);
 344   ecdestroy(e);
 345   return (ok);
 346 }
 347
 348 static int vec2osp(dstr v[])
 349 {
 350   ec_curve *e = *(ec_curve **)v[0].buf;
 351   unsigned f = *(int *)v[1].buf;
 352   ec *p = (ec *)v[2].buf;
 353   size_t n = 1 + 2*e->f->noctets;
 354   dstr d = DSTR_INIT, dd = DSTR_INIT;
 355   buf b;
 356   int ok = 1;
 357   int win, wantwin;
 358
 359   if (STRCMP(v[3].buf, ==, "FAIL")) wantwin = 0;
 360   else { wantwin = 1; type_hex.cvt(v[3].buf, &d); }
 361
 362   dstr_ensure(&dd, n); buf_init(&b, dd.buf, n);
 363
 364   win = !ec_ec2osp(e, f, &b, p);
 365   if (!win != !wantwin ||
 366       (win && (BLEN(&b) != d.len ||
 367                MEMCMP(BBASE(&b), !=, d.buf, BLEN(&b))))) {
 368     ok = 0;
 369     fprintf(stderr, "ec2osp failed");
 370     fprintf(stderr, "\ncurve = "); type_ecurve.dump(v, stderr);
 371     fprintf(stderr, "\n  fmt = 0x%02x", f);
 372     fprintf(stderr, "\n    p = "); ecdodump(p, stderr);
 373     fprintf(stderr, "\n want = ");
 374     if (wantwin) type_hex.dump(&d, stderr);
 375     else fprintf(stderr, "FAIL");
 376     fprintf(stderr, "\nfound = ");
 377     if (win) { dd.len = BLEN(&b); type_hex.dump(&dd, stderr); }
 378     else fprintf(stderr, "FAIL");
 379     fprintf(stderr, "\n");
 380   }
 381
 382   dstr_destroy(&d); dstr_destroy(&dd);
 383   EC_DESTROY(p); ecdestroy(e);
 384   return (ok);
 385 }
 386
 387 static int vos2ecp(dstr v[])
 388 {
 389   ec_curve *e = *(ec_curve **)v[0].buf;
 390   unsigned f = *(int *)v[1].buf;
 391   int remain = *(int *)v[4].buf;
 392   dstr d = DSTR_INIT;
 393   ec *p, q = EC_INIT;
 394   buf b;
 395   int ok = 1;
 396   int win;
 397
 398   if (STRCMP(v[3].buf, ==, "FAIL")) p = 0;
 399   else { type_ec.cvt(v[3].buf, &d); p = (ec *)d.buf; }
 400
 401   buf_init(&b, v[2].buf, v[2].len);
 402   win = !ec_os2ecp(e, f, &b, &q);
 403
 404   if (!win != !p || (win && (!EC_EQ(p, &q) || BLEFT(&b) != remain))) {
 405     ok = 0;
 406     fprintf(stderr, "os2ecp failed");
 407     fprintf(stderr, "\ncurve = "); type_ecurve.dump(v, stderr);
 408     fprintf(stderr, "\n  fmt = 0x%02x", f);
 409     fprintf(stderr, "\ninput = "); type_hex.dump(&v[2], stderr);
 410     fprintf(stderr, "\n want = ");
 411     if (p) ecdodump(p, stderr); else fprintf(stderr, "FAIL");
 412     fprintf(stderr, "\nfound = ");
 413     if (win) ecdodump(&q, stderr); else fprintf(stderr, "FAIL");
 414     fprintf(stderr, "\nremain= %d", remain);
 415     fprintf(stderr, "\nleft  = %d", (int)BLEFT(&b));
 416     fprintf(stderr, "\n");
 417   }
 418
 419   if (p) EC_DESTROY(p); EC_DESTROY(&q); ecdestroy(e);
 420   dstr_destroy(&d);
 421   return (ok);
 422 }
 423
 424 static test_chunk tests[] = {
 425   { "neg", vneg, { &type_ecurve, &type_ec, &type_ec } },
 426   { "dbl", vdbl, { &type_ecurve, &type_ec, &type_ec } },
 427   { "add", vadd, { &type_ecurve, &type_ec, &type_ec, &type_ec } },
 428   { "sub", vsub, { &type_ecurve, &type_ec, &type_ec, &type_ec } },
 429   { "mul", vmul, { &type_ecurve, &type_ec, &type_mp, &type_ec } },
 430   { "check", vcheck, { &type_ecurve, &type_ec, &type_int } },
 431   { "find", vfind, { &type_ecurve, &type_mp, &type_ec } },
 432   { "ec2osp", vec2osp, { &type_ecurve, &type_int, &type_ec, &type_string } },
 433   { "os2ecp", vos2ecp,
 434     { &type_ecurve, &type_int, &type_hex, &type_string, &type_int } },
 435   { 0, 0, { 0 } }
 436 };
 437
 438 int main(int argc, char *argv[])
 439 {
 440   sub_init();
 441   test_run(argc, argv, tests, SRCDIR "/t/ec");
 442   return (0);
 443 }
 444
 445 #endif
 446
 447 /*----- That's all, folks -------------------------------------------------*/