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

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