chiark - git - mdw - catacomb/blob - ec-info.c

   1 /* -*-c-*-
   2  *
   3  * $Id: ec-info.c,v 1.2 2004/04/01 12:50:09 mdw Exp $
   4  *
   5  * Elliptic curve information management
   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-info.c,v $
  33  * Revision 1.2  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.1  2004/03/27 17:54:11  mdw
  41  * Standard curves and curve checking.
  42  *
  43  */
  44
  45 /*----- Header files ------------------------------------------------------*/
  46
  47 #include "ec.h"
  48 #include "ectab.h"
  49 #include "gf.h"
  50 #include "pgen.h"
  51 #include "mprand.h"
  52 #include "rabin.h"
  53
  54 /*----- Main code ---------------------------------------------------------*/
  55
  56 /* --- @ec_curveparse@ --- *
  57  *
  58  * Arguments:   @qd_parse *qd@ = parser context
  59  *
  60  * Returns:     Elliptic curve pointer if OK, or null.
  61  *
  62  * Use:         Parses an elliptic curve description, which has the form
  63  *
  64  *                * a field description
  65  *                * an optional `/'
  66  *                * `prime', `primeproj', `bin', or `binproj'
  67  *                * an optional `:'
  68  *                * the %$a$% parameter
  69  *                * an optional `,'
  70  *                * the %$b$% parameter
  71  */
  72
  73 ec_curve *ec_curveparse(qd_parse *qd)
  74 {
  75   mp *a = MP_NEW, *b = MP_NEW;
  76   ec_curve *c;
  77   field *f;
  78
  79   if ((f = field_parse(qd)) == 0) goto fail;
  80   qd_delim(qd, '/');
  81   switch (qd_enum(qd, "prime,primeproj,bin,binproj")) {
  82     case 0:
  83       if (F_TYPE(f) != FTY_PRIME) {
  84         qd->e = "field not prime";
  85         goto fail;
  86       }
  87       qd_delim(qd, ':');
  88       if ((a = qd_getmp(qd)) == 0) goto fail;
  89       qd_delim(qd, ',');
  90       if ((b = qd_getmp(qd)) == 0) goto fail;
  91       c = ec_prime(f, a, b);
  92       break;
  93     case 1:
  94       if (F_TYPE(f) != FTY_PRIME) {
  95         qd->e = "field not prime";
  96         goto fail;
  97       }
  98       qd_delim(qd, ':');
  99       if ((a = qd_getmp(qd)) == 0) goto fail;
 100       qd_delim(qd, ',');
 101       if ((b = qd_getmp(qd)) == 0) goto fail;
 102       c = ec_primeproj(f, a, b);
 103       break;
 104     case 2:
 105       if (F_TYPE(f) != FTY_BINARY) {
 106         qd->e = "field not binary";
 107         goto fail;
 108       }
 109       qd_delim(qd, ':');
 110       if ((a = qd_getmp(qd)) == 0) goto fail;
 111       qd_delim(qd, ',');
 112       if ((b = qd_getmp(qd)) == 0) goto fail;
 113       c = ec_bin(f, a, b);
 114       break;
 115     case 3:
 116       if (F_TYPE(f) != FTY_BINARY) {
 117         qd->e = "field not binary";
 118         goto fail;
 119       }
 120       qd_delim(qd, ':');
 121       if ((a = qd_getmp(qd)) == 0) goto fail;
 122       qd_delim(qd, ',');
 123       if ((b = qd_getmp(qd)) == 0) goto fail;
 124       c = ec_binproj(f, a, b);
 125       break;
 126     default:
 127       goto fail;
 128   }
 129   if (a) MP_DROP(a);
 130   if (b) MP_DROP(b);
 131   return (c);
 132
 133 fail:
 134   if (f) F_DESTROY(f);
 135   if (a) MP_DROP(a);
 136   if (b) MP_DROP(b);
 137   return (0);
 138 }
 139
 140 /* --- @ec_ptparse@ --- *
 141  *
 142  * Arguments:   @qd_parse *qd@ = parser context
 143  *              @ec *p@ = where to put the point
 144  *
 145  * Returns:     The point address, or null.
 146  *
 147  * Use:         Parses an elliptic curve point.  This has the form
 148  *
 149  *                * %$x$%-coordinate
 150  *                * optional `,'
 151  *                * %$y$%-coordinate
 152  */
 153
 154 ec *ec_ptparse(qd_parse *qd, ec *p)
 155 {
 156   mp *x = MP_NEW, *y = MP_NEW;
 157
 158   if (qd_enum(qd, "inf") >= 0) {
 159     EC_SETINF(p);
 160     return (p);
 161   }
 162   if ((x = qd_getmp(qd)) == 0) goto fail;
 163   qd_delim(qd, ',');
 164   if ((y = qd_getmp(qd)) == 0) goto fail;
 165   EC_DESTROY(p);
 166   p->x = x;
 167   p->y = y;
 168   p->z = 0;
 169   return (p);
 170
 171 fail:
 172   if (x) MP_DROP(x);
 173   if (y) MP_DROP(y);
 174   return (0);
 175 }
 176
 177 /* --- @getinfo@ --- *
 178  *
 179  * Arguments:   @ec_info *ei@ = where to write the information
 180  *              @ecdata *ed@ = raw data
 181  *
 182  * Returns:     ---
 183  *
 184  * Use:         Loads elliptic curve information about one of the standard
 185  *              curves.
 186  */
 187
 188 static void getinfo(ec_info *ei, ecdata *ed)
 189 {
 190   field *f;
 191
 192   switch (ed->ftag) {
 193     case FTAG_PRIME:
 194       f = field_prime(&ed->p);
 195       ei->c = ec_primeproj(f, &ed->a, &ed->b);
 196       break;
 197     case FTAG_NICEPRIME:
 198       f = field_niceprime(&ed->p);
 199       ei->c = ec_primeproj(f, &ed->a, &ed->b);
 200       break;
 201     case FTAG_BINPOLY:
 202       f = field_binpoly(&ed->p);
 203       ei->c = ec_binproj(f, &ed->a, &ed->b);
 204       break;
 205     default:
 206       abort();
 207   }
 208
 209   EC_CREATE(&ei->g); ei->g.x = &ed->gx; ei->g.y = &ed->gy; ei->g.z = 0;
 210   ei->r = &ed->r; ei->h = &ed->h;
 211 }
 212
 213 /* --- @ec_infoparse@ --- *
 214  *
 215  * Arguments:   @qd_parse *qd@ = parser context
 216  *              @ec_info *ei@ = curve information block, currently
 217  *                      uninitialized
 218  *
 219  * Returns:     Zero on success, nonzero on failure.
 220  *
 221  * Use:         Parses an elliptic curve information string, and stores the
 222  *              information in @ei@.  This is either the name of a standard
 223  *              curve, or it has the form
 224  *
 225  *                * elliptic curve description
 226  *                * optional `/'
 227  *                * common point
 228  *                * optional `:'
 229  *                * group order
 230  *                * optional `*'
 231  *                * cofactor
 232  */
 233
 234 int ec_infoparse(qd_parse *qd, ec_info *ei)
 235 {
 236   ec_curve *c = 0;
 237   field *f;
 238   ec g = EC_INIT;
 239   const ecentry *ee;
 240   mp *r = MP_NEW, *h = MP_NEW;
 241
 242   for (ee = ectab; ee->name; ee++) {
 243     if (qd_enum(qd, ee->name) >= 0) {
 244       getinfo(ei, ee->data);
 245       goto found;
 246     }
 247   }
 248   if ((c = ec_curveparse(qd)) == 0) goto fail;
 249   qd_delim(qd, '/'); if (!ec_ptparse(qd, &g)) goto fail;
 250   qd_delim(qd, ':'); if ((r = qd_getmp(qd)) == 0) goto fail;
 251   qd_delim(qd, '*'); if ((h = qd_getmp(qd)) == 0) goto fail;
 252   ei->c = c; ei->g = g; ei->r = r; ei->h = h;
 253
 254 found:
 255   return (0);
 256
 257 fail:
 258   EC_DESTROY(&g);
 259   if (r) MP_DROP(r);
 260   if (h) MP_DROP(h);
 261   if (c) { f = c->f; ec_destroycurve(c); F_DESTROY(f); }
 262   return (-1);
 263 }
 264
 265 /* --- @ec_getinfo@ --- *
 266  *
 267  * Arguments:   @ec_info *ei@ = where to write the information
 268  *              @const char *p@ = string describing a curve
 269  *
 270  * Returns:     Null on success, or a pointer to an error message.
 271  *
 272  * Use:         Parses out information about a curve.  The string is either a
 273  *              standard curve name, or a curve info string.
 274  */
 275
 276 const char *ec_getinfo(ec_info *ei, const char *p)
 277 {
 278   qd_parse qd;
 279
 280   qd.p = p;
 281   qd.e = 0;
 282   if (ec_infoparse(&qd, ei))
 283     return (qd.e);
 284   if (!qd_eofp(&qd)) {
 285     ec_freeinfo(ei);
 286     return ("junk found at end of string");
 287   }
 288   return (0);
 289 }
 290
 291 /* --- @ec_sameinfop@ --- *
 292  *
 293  * Arguments:   @ec_info *ei, *ej@ = two elliptic curve parameter sets
 294  *
 295  * Returns:     Nonzero if the curves are identical (not just isomorphic).
 296  *
 297  * Use:         Checks for sameness of curve parameters.
 298  */
 299
 300 int ec_sameinfop(ec_info *ei, ec_info *ej)
 301 {
 302   return (ec_samep(ei->c, ej->c) &&
 303           MP_EQ(ei->r, ej->r) && MP_EQ(ei->h, ej->h) &&
 304           EC_EQ(&ei->g, &ej->g));
 305 }
 306
 307 /* --- @ec_freeinfo@ --- *
 308  *
 309  * Arguments:   @ec_info *ei@ = elliptic curve information block to free
 310  *
 311  * Returns:     ---
 312  *
 313  * Use:         Frees the information block.
 314  */
 315
 316 void ec_freeinfo(ec_info *ei)
 317 {
 318   field *f;
 319
 320   EC_DESTROY(&ei->g);
 321   MP_DROP(ei->r);
 322   MP_DROP(ei->h);
 323   f = ei->c->f; ec_destroycurve(ei->c); F_DESTROY(f);
 324 }
 325
 326 /* --- @ec_checkinfo@ --- *
 327  *
 328  * Arguments:   @const ec_info *ei@ = elliptic curve information block
 329  *
 330  * Returns:     Null if OK, or pointer to error message.
 331  *
 332  * Use:         Checks an elliptic curve according to the rules in SEC1.
 333  */
 334
 335 static int primeeltp(mp *x, field *f)
 336 {
 337   return (!MP_ISNEG(x) && MP_CMP(x, <, f->m));
 338 }
 339
 340 static const char *primecheck(const ec_info *ei, grand *gr)
 341 {
 342   ec_curve *c = ei->c;
 343   field *f = c->f;
 344   int i;
 345   mp *x, *y;
 346   ec p;
 347   int rc;
 348
 349   /* --- Check %$p$% is an odd prime --- */
 350
 351   if (!pgen_primep(f->m, gr)) return ("p not prime");
 352
 353   /* --- Check %$a$%, %$b$%, %$G_x$% and %$G_y$% are in %$[0, p)$% --- */
 354
 355   if (!primeeltp(c->a, f)) return ("a out of range");
 356   if (!primeeltp(c->b, f)) return ("b out of range");
 357   if (!primeeltp(ei->g.x, f)) return ("G_x out of range");
 358   if (!primeeltp(ei->g.x, f)) return ("G_y out of range");
 359
 360   /* --- Check %$4 a^3 + 27 b^2 \not\equiv 0 \pmod{p}$% --- */
 361
 362   x = F_SQR(f, MP_NEW, c->a);
 363   x = F_MUL(f, x, x, c->a);
 364   x = F_QDL(f, x, x);
 365   y = F_SQR(f, MP_NEW, c->b);
 366   y = F_TPL(f, y, y);
 367   y = F_TPL(f, y, y);
 368   y = F_TPL(f, y, y);
 369   x = F_ADD(f, x, x, y);
 370   rc = F_ZEROP(f, x);
 371   MP_DROP(x);
 372   MP_DROP(y);
 373   if (rc) return ("not an elliptic curve");
 374
 375   /* --- Check %$G \in E$% --- */
 376
 377   if (EC_ATINF(&ei->g)) return ("generator at infinity");
 378   if (ec_check(c, &ei->g)) return ("generator not on curve");
 379
 380   /* --- Check %$r$% is prime --- */
 381
 382   if (!pgen_primep(ei->r, gr)) return ("generator order not prime");
 383
 384   /* --- Check %$0 < h \le 4$% --- */
 385
 386   if (MP_CMP(ei->h, <, MP_ONE) || MP_CMP(ei->h, >, MP_FOUR))
 387     return ("cofactor out of range");
 388
 389   /* --- Check %$h = \lfloor (\sqrt{p} + 1)^2/r \rlfoor$% --- *
 390    *
 391    * This seems to work with the approximate-sqrt in the library, but might
 392    * not be so good in some cases.  Throw in some extra significate figures
 393    * for good measure.
 394    */
 395
 396   x = mp_lsl(MP_NEW, f->m, 128);
 397   x = mp_sqrt(x, x);
 398   y = mp_lsl(MP_NEW, MP_ONE, 64);
 399   x = mp_add(x, x, y);
 400   x = mp_sqr(x, x);
 401   mp_div(&x, 0, x, ei->r);
 402   x = mp_lsr(x, x, 128);
 403   rc = MP_EQ(x, ei->h);
 404   MP_DROP(x);
 405   MP_DROP(y);
 406   if (!rc) return ("incorrect cofactor");
 407
 408   /* --- Check %$n G = O$% --- */
 409
 410   EC_CREATE(&p);
 411   ec_mul(c, &p, &ei->g, ei->r);
 412   rc = EC_ATINF(&p);
 413   EC_DESTROY(&p);
 414   if (!rc) return ("incorrect group order");
 415
 416   /* --- Check that %$p^B \not\equiv 1 \pmod{r}$% for %$1 \le B < 20$% --- *
 417    *
 418    * The spec says %$q$%, not %$p$%, but I think that's a misprint.
 419    */
 420
 421   x = MP_NEW;
 422   mp_div(0, &x, f->m, ei->r);
 423   i = 20;
 424   while (i) {
 425     if (MP_EQ(x, MP_ONE)) break;
 426     x = mp_mul(x, x, f->m);
 427     mp_div(0, &x, x, ei->r);
 428     i--;
 429   }
 430   MP_DROP(x);
 431   if (i) return ("curve is weak");
 432
 433   /* --- Done --- */
 434
 435   return (0);
 436 }
 437
 438 static const char *bincheck(const ec_info *ei, grand *gr)
 439 {
 440   ec_curve *c = ei->c;
 441   field *f = c->f;
 442   int i;
 443   mp *x, *y;
 444   ec p;
 445   int rc;
 446
 447   /* --- Check that %$p$% is irreducible --- */
 448
 449   if (!gf_irreduciblep(f->m)) return ("p not irreducible");
 450
 451   /* --- Check that %$a, b, G_x, G_y$% have degree less than %$p$% --- */
 452
 453   if (mp_bits(c->a) > f->nbits) return ("a out of range");
 454   if (mp_bits(c->b) > f->nbits) return ("a out of range");
 455   if (mp_bits(ei->g.x) > f->nbits) return ("G_x out of range");
 456   if (mp_bits(ei->g.y) > f->nbits) return ("G_y out of range");
 457
 458   /* --- Check that %$b \ne 0$% --- */
 459
 460   if (F_ZEROP(f, c->b)) return ("b is zero");
 461
 462   /* --- Check that %$G \in E$% --- */
 463
 464   if (EC_ATINF(&ei->g)) return ("generator at infinity");
 465   if (ec_check(c, &ei->g)) return ("generator not on curve");
 466
 467   /* --- Check %$r$% is prime --- */
 468
 469   if (!pgen_primep(ei->r, gr)) return ("generator order not prime");
 470
 471   /* --- Check %$0 < h \le 4$% --- */
 472
 473   if (MP_CMP(ei->h, <, MP_ONE) || MP_CMP(ei->h, >, MP_FOUR))
 474     return ("cofactor out of range");
 475
 476   /* --- Check %$h = \lfloor (\sqrt{2^m} + 1)^2/r \rlfoor$% --- *
 477    *
 478    * This seems to work with the approximate-sqrt in the library, but might
 479    * not be so good in some cases.  Throw in some extra significate figures
 480    * for good measure.
 481    */
 482
 483   x = mp_lsl(MP_NEW, MP_ONE, f->nbits + 128);
 484   x = mp_sqrt(x, x);
 485   y = mp_lsl(MP_NEW, MP_ONE, 64);
 486   x = mp_add(x, x, y);
 487   x = mp_sqr(x, x);
 488   mp_div(&x, 0, x, ei->r);
 489   x = mp_lsr(x, x, 128);
 490   rc = MP_EQ(x, ei->h);
 491   MP_DROP(x);
 492   MP_DROP(y);
 493   if (!rc) return ("incorrect cofactor");
 494
 495   /* --- Check %$n G = O$% --- */
 496
 497   EC_CREATE(&p);
 498   ec_mul(c, &p, &ei->g, ei->r);
 499   rc = EC_ATINF(&p);
 500   EC_DESTROY(&p);
 501   if (!rc) return ("incorrect group order");
 502
 503   /* --- Check %$2^{m B} \not\equiv 1 \pmod{r}$% for %$1 \le B < 20$% --- */
 504
 505   x = mp_lsl(MP_NEW, MP_ONE, f->nbits);
 506   mp_div(0, &x, x, ei->r);
 507   i = 20;
 508   while (i) {
 509     if (MP_EQ(x, MP_ONE)) break;
 510     x = mp_mul(x, x, f->m);
 511     mp_div(0, &x, x, ei->r);
 512     i--;
 513   }
 514   MP_DROP(x);
 515   if (i) return ("curve is weak");
 516
 517   /* --- Done --- */
 518
 519   return (0);
 520 }
 521
 522 const char *ec_checkinfo(const ec_info *ei, grand *gr)
 523 {
 524   switch (F_TYPE(ei->c->f)) {
 525     case FTY_PRIME: return (primecheck(ei, gr)); break;
 526     case FTY_BINARY: return (bincheck(ei, gr)); break;
 527   }
 528   return ("unknown curve type");
 529 }
 530
 531 /*----- Test rig ----------------------------------------------------------*/
 532
 533 #ifdef TEST_RIG
 534
 535 #include "fibrand.h"
 536
 537 int main(void)
 538 {
 539   const ecentry *ee;
 540   const char *e;
 541   int ok = 1;
 542   grand *gr;
 543
 544   gr = fibrand_create(0);
 545   fputs("checking standard curves: ", stdout);
 546   for (ee = ectab; ee->name; ee++) {
 547     ec_info ei;
 548     getinfo(&ei, ee->data);
 549     e = ec_checkinfo(&ei, gr);
 550     ec_freeinfo(&ei);
 551     if (e) {
 552       fprintf(stderr, "\n*** curve %s fails: %s\n", ee->name, e);
 553       ok = 0;
 554     }
 555     putchar('.');
 556     fflush(stdout);
 557   }
 558   gr->ops->destroy(gr);
 559   fputs(ok ? " ok\n" : " failed\n", stdout);
 560   return (!ok);
 561 }
 562
 563 #endif
 564
 565 /*----- That's all, folks -------------------------------------------------*/