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

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