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

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