git.distorted.org.uk Git - u/mdw/catacomb/blob - ec-test.c

   1 /* -*-c-*-
   2  *
   3  * $Id: ec-test.c,v 1.4 2004/04/01 12:50:09 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.4  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  * Revision 1.3  2004/03/27 17:54:11  mdw
  41  * Standard curves and curve checking.
  42  *
  43  * Revision 1.2  2004/03/27 00:04:46  mdw
  44  * Implement efficient reduction for pleasant-looking primes.
  45  *
  46  * Revision 1.1  2004/03/23 15:19:32  mdw
  47  * Test elliptic curves more thoroughly.
  48  *
  49  */
  50
  51 /*----- Header files ------------------------------------------------------*/
  52
  53 #include <assert.h>
  54 #include <ctype.h>
  55 #include <stdio.h>
  56 #include <stdlib.h>
  57 #include <string.h>
  58
  59 #include <mLib/alloc.h>
  60 #include <mLib/testrig.h>
  61 #include <mLib/sub.h>
  62
  63 #include "ec.h"
  64 #include "ec-test.h"
  65
  66 /*----- Cardboard cut-out elliptic curve ----------------------------------*/
  67
  68 typedef struct ecctx {
  69   ec_curve c;
  70   unsigned long magic;
  71   char *name;
  72   ec_curve *real;
  73 } ecctx;
  74
  75 #define MAGIC 0x3a1f0b07
  76
  77 static void ecDESTROY(ec_curve *cc)
  78 {
  79   ecctx *c = (ecctx *)cc;
  80   xfree(c->name);
  81   ec_destroycurve(c->real);
  82   DESTROY(c);
  83 }
  84
  85 #define UNOP(OP)                                                        \
  86   static ec *ec##OP(ec_curve *cc, ec *d, const ec *p) {                 \
  87     ecctx *c = (ecctx *)cc;                                             \
  88     return (EC_##OP(c->real, d, p));                                    \
  89   }
  90
  91 #define BINOP(OP)                                                       \
  92   static ec *ec##OP(ec_curve *cc, ec *d, const ec *p, const ec *q) {    \
  93     ecctx *c = (ecctx *)cc;                                             \
  94     return (EC_##OP(c->real, d, p, q));                                 \
  95   }
  96
  97 UNOP(IN)
  98 UNOP(OUT)
  99 UNOP(FIX)
 100 UNOP(NEG)
 101 UNOP(DBL)
 102 BINOP(ADD)
 103 BINOP(SUB)
 104
 105 #undef UNOP
 106 #undef BINOP
 107
 108 static ec *ecFIND(ec_curve *cc, ec *d, mp *x)
 109 {
 110   ecctx *c = (ecctx *)cc;
 111   return (EC_FIND(c->real, d, x));
 112 }
 113
 114 static int ecCHECK(ec_curve *cc, const ec *p)
 115 {
 116   ecctx *c = (ecctx *)cc;
 117   return (EC_CHECK(c->real, p));
 118 }
 119
 120 static int ecSAMEP(ec_curve *cc, ec_curve *dd)
 121 {
 122   ecctx *c = (ecctx *)cc, *d = (ecctx *)dd;
 123   return (ec_samep(c->real, d->real));
 124 }
 125
 126 static ec_ops ecops = {
 127   ecDESTROY, ecSAMEP, ecIN, ecOUT, ecFIX,
 128   ecFIND, ecNEG, ecADD, ecSUB, ecDBL, ecCHECK
 129 };
 130
 131 static ec_curve *ec_cutout(ec_curve *real, const char *name)
 132 {
 133   ecctx *c = CREATE(ecctx);
 134   c->c.f = real->f;
 135   c->c.ops = &ecops;
 136   c->c.a = real->a;
 137   c->c.b = real->b;
 138   c->magic = MAGIC;
 139   c->name = xstrdup(name);
 140   c->real = real;
 141   return (&c->c);
 142 }
 143
 144 static const char *ec_name(ec_curve *cc)
 145 {
 146   ecctx *c = (ecctx *)cc;
 147   assert(c->magic == MAGIC);
 148   return (c->name);
 149 }
 150
 151 /*----- Test field types --------------------------------------------------*/
 152
 153 static void ecvcvt(const char *buf, dstr *d)
 154 {
 155   ec_curve *v;
 156   qd_parse qd;
 157
 158   qd.p = buf;
 159   qd.e = 0;
 160   if ((v = ec_curveparse(&qd)) == 0) {
 161     fprintf(stderr, "bad curve `%.*s|%s': %s\n",
 162             qd.p - buf, buf, qd.p, qd.e);
 163     exit(1);
 164   }
 165   dstr_ensure(d, sizeof(v));
 166   *(ec_curve **)d->buf = ec_cutout(v, buf);
 167   d->len += sizeof(v);
 168 }
 169
 170 static void ecvdump(dstr *d, FILE *fp)
 171 {
 172   ec_curve *v = *(ec_curve **)d->buf;
 173   fprintf(fp, "%s", ec_name(v));
 174 }
 175
 176 test_type type_ecurve = { ecvcvt, ecvdump };
 177
 178 static void eccvt(const char *p, dstr *d)
 179 {
 180   ec *a;
 181   qd_parse qd;
 182
 183   qd.p = p;
 184   qd.e = 0;
 185   dstr_ensure(d, sizeof(ec));
 186   a = (ec *)d->buf;
 187   d->len += sizeof(ec);
 188   ec_create(a);
 189   if (!ec_ptparse(&qd, a)) {
 190     fprintf(stderr, "bad point `%.*s|%s': %s\n", qd.p - p, p, qd.p, qd.e);
 191     exit(1);
 192   }
 193 }
 194
 195 static void ecdodump(ec *a, FILE *fp)
 196 {
 197   if (EC_ATINF(a))
 198     fputs("inf", fp);
 199   else {
 200     fputs("0x", fp);
 201     mp_writefile(a->x, fp, 16);
 202     fputs(", 0x", fp);
 203     mp_writefile(a->y, fp, 16);
 204   }
 205 }
 206
 207 static void ecdump(dstr *d, FILE *fp)
 208 {
 209   ec *a = (ec *)d->buf;
 210   ecdodump(a, fp);
 211 }
 212
 213 test_type type_ec = { eccvt, ecdump };
 214
 215 /*----- Testing elliptic curve functionality ------------------------------*/
 216
 217 #ifdef TEST_RIG
 218
 219 static void ecdestroy(ec_curve *c)
 220 {
 221   field *f = c->f;
 222   ec_destroycurve(c);
 223   F_DESTROY(f);
 224 }
 225
 226 #define UNOP(op)                                                        \
 227   static int v##op(dstr v[])                                            \
 228   {                                                                     \
 229     ec_curve *e = *(ec_curve **)v[0].buf;                               \
 230     ec *a = (ec *)v[1].buf;                                             \
 231     ec *r = (ec *)v[2].buf;                                             \
 232     ec c = EC_INIT;                                                     \
 233     int ok = 1;                                                         \
 234     ec_##op(e, &c, a);                                                  \
 235     if (!EC_EQ(r, &c)) {                                                \
 236       fprintf(stderr, #op "failed");                                    \
 237       fprintf(stderr, "\ncurve = "); type_ecurve.dump(v, stderr);       \
 238       fprintf(stderr, "\n    a = "); ecdodump(a, stderr);               \
 239       fprintf(stderr, "\n    r = "); ecdodump(r, stderr);               \
 240       fprintf(stderr, "\n    c = "); ecdodump(&c, stderr);              \
 241       fprintf(stderr, "\n");                                            \
 242       ok = 0;                                                           \
 243     }                                                                   \
 244     EC_DESTROY(a); EC_DESTROY(r); EC_DESTROY(&c);                       \
 245     ecdestroy(e);                                                       \
 246     return (ok);                                                        \
 247   }
 248
 249 #define BINOP(op)                                                       \
 250   static int v##op(dstr v[])                                            \
 251   {                                                                     \
 252     ec_curve *e = *(ec_curve **)v[0].buf;                               \
 253     ec *a = (ec *)v[1].buf;                                             \
 254     ec *b = (ec *)v[2].buf;                                             \
 255     ec *r = (ec *)v[3].buf;                                             \
 256     ec c = EC_INIT;                                                     \
 257     int ok = 1;                                                         \
 258     ec_##op(e, &c, a, b);                                               \
 259     if (!EC_EQ(r, &c)) {                                                \
 260       fprintf(stderr, #op "failed");                                    \
 261       fprintf(stderr, "\ncurve = "); type_ecurve.dump(v, stderr);       \
 262       fprintf(stderr, "\n    a = "); ecdodump(a, stderr);               \
 263       fprintf(stderr, "\n    b = "); ecdodump(b, stderr);               \
 264       fprintf(stderr, "\n    r = "); ecdodump(r, stderr);               \
 265       fprintf(stderr, "\n    c = "); ecdodump(&c, stderr);              \
 266       fprintf(stderr, "\n");                                            \
 267       ok = 0;                                                           \
 268     }                                                                   \
 269     EC_DESTROY(a); EC_DESTROY(b); EC_DESTROY(r); EC_DESTROY(&c);        \
 270     ecdestroy(e);                                                       \
 271     return (ok);                                                        \
 272   }
 273
 274 UNOP(neg)
 275 UNOP(dbl)
 276 BINOP(add)
 277 BINOP(sub)
 278
 279 static int vcheck(dstr v[])
 280 {
 281   ec_curve *e = *(ec_curve **)v[0].buf;
 282   ec *a = (ec *)v[1].buf;
 283   int r = *(int *)v[2].buf;
 284   int c;
 285   int ok = 1;
 286   c = ec_check(e, a);
 287   if (r != c) {
 288     fprintf(stderr, "check failed");
 289     fprintf(stderr, "\ncurve = "); type_ecurve.dump(v, stderr);
 290     fprintf(stderr, "\n    a = "); ecdodump(a, stderr);
 291     fprintf(stderr, "\n    r = %d", r);
 292     fprintf(stderr, "\n    c = %d", c);
 293     fprintf(stderr, "\n");
 294     ok = 0;
 295   }
 296   EC_DESTROY(a);
 297   ecdestroy(e);
 298   return (ok);
 299 }
 300
 301 static int vmul(dstr v[])
 302 {
 303   ec_curve *e = *(ec_curve **)v[0].buf;
 304   ec *a = (ec *)v[1].buf;
 305   mp *n = *(mp **)v[2].buf;
 306   ec *r = (ec *)v[3].buf;
 307   ec c = EC_INIT;
 308   int ok = 1;
 309   ec_mul(e, &c, a, n);
 310   if (!EC_EQ(r, &c)) {
 311     fprintf(stderr, "mul failed");
 312     fprintf(stderr, "\ncurve = "); type_ecurve.dump(v, stderr);
 313     fprintf(stderr, "\n    a = "); ecdodump(a, stderr);
 314     fprintf(stderr, "\n    n = "); mp_writefile(n, stderr, 10);
 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(r); EC_DESTROY(&c); MP_DROP(n);
 321   ecdestroy(e);
 322   return (ok);
 323 }
 324
 325 static int vfind(dstr v[])
 326 {
 327   ec_curve *e = *(ec_curve **)v[0].buf;
 328   mp *x = *(mp **)v[1].buf;
 329   ec *r = (ec *)v[2].buf;
 330   ec c = EC_INIT;
 331   int ok = 1;
 332   if (!ec_find(e, &c, x)) EC_SETINF(&c);
 333   if (!EC_EQ(r, &c)) {
 334     fprintf(stderr, "find failed");
 335     fprintf(stderr, "\ncurve = "); type_ecurve.dump(v, stderr);
 336     fprintf(stderr, "\n    x = "); mp_writefile(x, stderr, 16);
 337     fprintf(stderr, "\n    r = "); ecdodump(r, stderr);
 338     fprintf(stderr, "\n    c = "); ecdodump(&c, stderr);
 339     fprintf(stderr, "\n");
 340     ok = 0;
 341   }
 342   MP_DROP(x); EC_DESTROY(r); EC_DESTROY(&c);
 343   ecdestroy(e);
 344   return (ok);
 345 }
 346
 347 static test_chunk tests[] = {
 348   { "neg", vneg, { &type_ecurve, &type_ec, &type_ec } },
 349   { "dbl", vdbl, { &type_ecurve, &type_ec, &type_ec } },
 350   { "add", vadd, { &type_ecurve, &type_ec, &type_ec, &type_ec } },
 351   { "sub", vsub, { &type_ecurve, &type_ec, &type_ec, &type_ec } },
 352   { "mul", vmul, { &type_ecurve, &type_ec, &type_mp, &type_ec } },
 353   { "check", vcheck, { &type_ecurve, &type_ec, &type_int } },
 354   { "find", vfind, { &type_ecurve, &type_mp, &type_ec } },
 355   { 0, 0, { 0 } }
 356 };
 357
 358 int main(int argc, char *argv[])
 359 {
 360   sub_init();
 361   test_run(argc, argv, tests, SRCDIR "/tests/ec");
 362   return (0);
 363 }
 364
 365 #endif
 366
 367 /*----- That's all, folks -------------------------------------------------*/