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

   1 /* -*-c-*-
   2  *
   3  * Elliptic curve information management
   4  *
   5  * (c) 2004 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of Catacomb.
  11  *
  12  * Catacomb is free software; you can redistribute it and/or modify
  13  * it under the terms of the GNU Library General Public License as
  14  * published by the Free Software Foundation; either version 2 of the
  15  * License, or (at your option) any later version.
  16  *
  17  * Catacomb is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20  * GNU Library General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU Library General Public
  23  * License along with Catacomb; if not, write to the Free
  24  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  25  * MA 02111-1307, USA.
  26  */
  27
  28 /*----- Header files ------------------------------------------------------*/
  29
  30 #include <mLib/darray.h>
  31
  32 #include "ec.h"
  33 #include "ectab.h"
  34 #include "gf.h"
  35 #include "keysz.h"
  36 #include "mpbarrett.h"
  37 #include "pgen.h"
  38 #include "primeiter.h"
  39 #include "mprand.h"
  40 #include "mpint.h"
  41 #include "rabin.h"
  42
  43 /*----- Embedding degree checking -----------------------------------------*
  44  *
  45  * Let %$q = p^m$% be a prime power, and let %$E$% be an elliptic curve over
  46  * %$\gf{q}$% with %$n = \#E(\gf{q}) = r h$% where %$r$% is prime.  Then the
  47  * Weil and Tate pairings can be used to map %$r$%-torsion points on
  48  * %$E(\gf{q})$% onto the %$r$%-th roots of unity (i.e., the order-%$r$%
  49  * subgroup) in an extension field %$\gf{p^k}$% of %$\gf{p}$% (%%\emph{not}%%
  50  * of %$\gf{q}$% -- see [Hitt]).  We call the smallest such %$k$% the
  51  * %%\emph{embedding degree}%% of the curve %$E$%.  The
  52  * Menezes-Okamoto-Vanstone (MOV) attack solves the discrete log problem in
  53  * %$E(\gf{q})$% by using the pairing and then applying index calculus to
  54  * extract a discrete log in %$\gf{p^k}$%; obviously this only works if %$k$%
  55  * is small enough.
  56  *
  57  * The usual check, suggested in, e.g., [P1363] or [SEC1], only covers
  58  * extension fields %$\gf{q^\ell}$% of %$\gf{q}$%, which is fine when %$q$%
  59  * is prime, but when we're dealing with binary fields it works less well.
  60  * Indeed, as [Hitt] demonstrates, the embedding field can actually be
  61  * %%\emph{smaller}%% than %$\gf{q}$%, and choosing %$m$% prime doesn't help
  62  * (even though I previously thought it did).
  63  *
  64  * Define the %%\emph{embedding degree bound}%% %$B$% to be the smallest
  65  * %$i$% such that discrete logs in %$\gf{p^i}$% are about as hard as in
  66  * %$E(\gf{q})$%.
  67  *
  68  * The embedding group is a subgroup of the multiplicative group
  69  * %$\gf{p^k}^*$% which contains %$p^k - 1$% elements; therefore we must have
  70  * %$r \mid p^k - 1$%, or, equivalently, %$p^k \equiv 1 \pmod{r}$%.
  71  *
  72  * The recommended checking procedure, e.g., in [P1363], is just to check
  73  * %$q^i \not\equiv 1 \pmod{r}$% for each %$0 < i < B$%.  This is fast when
  74  * you only consider extension fields of %$\gf{q}$%, since %$B$% is at most
  75  * about 27.  However, as noted above, this is inadequate when %$q$% is a
  76  * prime power, and we must check all the extension fields of %$p$%.  Now
  77  * %$B$% can be about 15000, which is rather scarier -- we need a better
  78  * algorithm.
  79  *
  80  * As noted, we must have %$p^k \equiv 1 \pmod{r}$%; but by minimality of
  81  * %$k$%, we must have %$p^i \not\equiv 1 \pmod{r}$% for %$0 < i < k$%.
  82  * Therefore %$p$% generates an order-%$k$% subgroup in %$\gf{r}^*$%, so we
  83  * must have %$k \mid r - 1$%.
  84  *
  85  * Of course, factoring %$r - 1$% is a mug's game; but we're not interested
  86  * in the complete factorization -- just the %$B$%-smooth portion.  An
  87  * algorithm suggests itself:
  88  *
  89  *   1. Extract the factors of %$r - 1$% which are less than %$B$%.
  90  *
  91  *   2. For each divisor %$d$% of %$r - 1$% less than %$B$% (which we can
  92  *      construct using this factorization), make sure that
  93  *      %$p^d \not\equiv 1 \pmod{r}$%.
  94  *
  95  * This takes a little while but not ever-so long.
  96  *
  97  * This is enough for cryptosystems based on the computational Diffie-
  98  * Hellman problem to be secure.  However, it's %%\emph{not}%% enough for the
  99  * %%\emph{decisional}%% Diffie-Hellman problem to be hard; it appears we
 100  * also need to hope that there aren't any suitable distortion maps with
 101  * which one can solve the DDH problem.  I don't know how to check for those
 102  * at the moment.
 103  *
 104  * We'll take the subgroup order as indicative of the security level actually
 105  * wanted.  Then, to ensure security against the MOV attack, we must ensure
 106  * that the embedding degree is sufficiently large that discrete logs in
 107  * %$\gf{q^m}$% are at least as hard as discrete logs over the curve.
 108  *
 109  * We actually allow a small amount of slop in the conversions, in order to
 110  * let people pick nice round numbers for their key lengths.
 111  *
 112  * References:
 113  *
 114  * [Hitt]  L. Hitt, On an improved definition of embedding degree;
 115  *         http://eprint.iacr.org/2006/415
 116  *
 117  * [P1363] IEEE 1363-2000: Standard Specifications for Public Key
 118  *         Cryptography; http://grouper.ieee.org/groups/1363/P1363/index.html
 119  *
 120  * [SEC1]  SEC 1: Elliptic Curve Cryptography;
 121  *         http://www.secg.org/download/aid-385/sec1_final.pdf
 122  */
 123
 124 /* --- @movcheck@ --- *
 125  *
 126  * Arguments:   @mp *r@ = curve subgroup order
 127  *              @mp *p@ = field characteristic
 128  *              @unsigned long B@ = embedding degree bound
 129  *
 130  * Returns:     Zero if OK, nonzero if an embedding was found.
 131  *
 132  * Use:         Checks a curve for embeddings with degree less than the
 133  *              stated bound %$B$%.  See above for explanation and a
 134  *              description of the algorithm.
 135  */
 136
 137 static int movcheck(mp *r, mp *p, unsigned long B)
 138 {
 139   mpmont mm;
 140   mp *r1, *pp = MP_NEW, *t = MP_NEW, *u = MP_NEW, *v = MP_NEW, *tt;
 141   struct factor {
 142     unsigned long f;
 143     unsigned c, e;
 144   };
 145   DA_DECL(factor_v, struct factor);
 146   factor_v fv = DA_INIT;
 147   size_t nf;
 148   struct factor *ff;
 149   primeiter pi;
 150   mp *BB;
 151   unsigned long d, f;
 152   unsigned i, j;
 153   int rc = 0;
 154
 155   /* --- Special case --- *
 156    *
 157    * If %$r = 2$% then (a) Montgomery reduction won't work, and (b) we have
 158    * no security worth checking anyway.  Otherwise we're guaranteed that
 159    * %$r$% is a prime, so it must be odd.
 160    */
 161
 162   if (MP_EQ(r, MP_TWO))
 163     return (0);
 164
 165   /* --- First factor the %$B%-smooth portion of %$r - 1$% --- *
 166    *
 167    * We can generate prime numbers up to %$B$% efficiently, so trial division
 168    * it is.
 169    */
 170
 171   BB = mp_fromulong(MP_NEW, B);
 172   r1 = mp_sub(MP_NEW, r, MP_ONE);
 173   primeiter_create(&pi, 0);
 174   for (;;) {
 175     pp = primeiter_next(&pi, pp);
 176     if (MP_CMP(pp, >, BB))
 177       break;
 178     mp_div(&u, &v, r1, pp);
 179     if (!MP_ZEROP(v))
 180       continue;
 181     i = 0;
 182     do {
 183       tt = r1; r1 = u; u = tt; i++;
 184       mp_div(&u, &v, r1, pp);
 185     } while (MP_ZEROP(v));
 186     DA_ENSURE(&fv, 1);
 187     DA_UNSAFE_EXTEND(&fv, 1);
 188     DA_LAST(&fv).f = mp_toulong(pp);
 189     DA_LAST(&fv).e = i;
 190     DA_LAST(&fv).c = 0;
 191   }
 192   MP_DROP(BB); MP_DROP(pp); primeiter_destroy(&pi);
 193   nf = DA_LEN(&fv); ff = DA(&fv);
 194
 195   /* --- Now generate divisors of %$r - 1$% less than %$B$% --- *
 196    *
 197    * For each divisor %$d$%, check whether %$p^d \equiv 1 \pmod{r}$%.
 198    */
 199
 200   mpmont_create(&mm, r);
 201   u = mpmont_mul(&mm, u, p, mm.r2);
 202   for (;;) {
 203
 204     /* --- Construct the divisor --- */
 205
 206     d = 1;
 207     for (i = 0; i < nf; i++) {
 208       f = ff[i].f; j = ff[i].c; if (!j) continue;
 209       for (;;) {
 210         if (f >= (B + d - 1)/d) goto toobig;
 211         if (j & 1) d *= f;
 212         j >>= 1; if (!j) break;
 213         f *= f;
 214       }
 215     }
 216     v = mp_fromulong(v, d);
 217
 218     /* --- Compute %$p^k \bmod r$% and check --- */
 219
 220     t = mpmont_expr(&mm, t, u, v);
 221     if (MP_EQ(t, mm.r)) {
 222       rc = -1;
 223       break;
 224     }
 225
 226     /* --- Step the divisors along --- */
 227
 228   toobig:
 229     for (i = 0; i < nf; i++) {
 230       if (ff[i].c < ff[i].e) {
 231         ff[i].c++;
 232         goto more;
 233       }
 234       ff[i].c = 0;
 235     }
 236     break;
 237   more:;
 238   }
 239
 240   /* --- Clear away the debris --- */
 241
 242   mpmont_destroy(&mm);
 243   MP_DROP(t); MP_DROP(u); MP_DROP(v); MP_DROP(r1);
 244   DA_DESTROY(&fv);
 245   return (rc);
 246 }
 247
 248 /*----- Main code ---------------------------------------------------------*/
 249
 250 /* --- @ec_curveparse@ --- *
 251  *
 252  * Arguments:   @qd_parse *qd@ = parser context
 253  *
 254  * Returns:     Elliptic curve pointer if OK, or null.
 255  *
 256  * Use:         Parses an elliptic curve description, which has the form
 257  *
 258  *                * a field description
 259  *                * an optional `;'
 260  *                * `prime', `primeproj', `bin', or `binproj'
 261  *                * an optional `:'
 262  *                * the %$a$% parameter
 263  *                * an optional `,'
 264  *                * the %$b$% parameter
 265  */
 266
 267 ec_curve *ec_curveparse(qd_parse *qd)
 268 {
 269   mp *a = MP_NEW, *b = MP_NEW;
 270   ec_curve *c;
 271   field *f;
 272
 273   if ((f = field_parse(qd)) == 0) goto fail;
 274   qd_delim(qd, ';');
 275   switch (qd_enum(qd, "prime,primeproj,bin,binproj")) {
 276     case 0:
 277       if (F_TYPE(f) != FTY_PRIME) {
 278         qd->e = "field not prime";
 279         goto fail;
 280       }
 281       qd_delim(qd, ':');
 282       if ((a = qd_getmp(qd)) == 0) goto fail;
 283       qd_delim(qd, ',');
 284       if ((b = qd_getmp(qd)) == 0) goto fail;
 285       c = ec_prime(f, a, b);
 286       break;
 287     case 1:
 288       if (F_TYPE(f) != FTY_PRIME) {
 289         qd->e = "field not prime";
 290         goto fail;
 291       }
 292       qd_delim(qd, ':');
 293       if ((a = qd_getmp(qd)) == 0) goto fail;
 294       qd_delim(qd, ',');
 295       if ((b = qd_getmp(qd)) == 0) goto fail;
 296       c = ec_primeproj(f, a, b);
 297       break;
 298     case 2:
 299       if (F_TYPE(f) != FTY_BINARY) {
 300         qd->e = "field not binary";
 301         goto fail;
 302       }
 303       qd_delim(qd, ':');
 304       if ((a = qd_getmp(qd)) == 0) goto fail;
 305       qd_delim(qd, ',');
 306       if ((b = qd_getmp(qd)) == 0) goto fail;
 307       c = ec_bin(f, a, b);
 308       break;
 309     case 3:
 310       if (F_TYPE(f) != FTY_BINARY) {
 311         qd->e = "field not binary";
 312         goto fail;
 313       }
 314       qd_delim(qd, ':');
 315       if ((a = qd_getmp(qd)) == 0) goto fail;
 316       qd_delim(qd, ',');
 317       if ((b = qd_getmp(qd)) == 0) goto fail;
 318       c = ec_binproj(f, a, b);
 319       break;
 320     default:
 321       goto fail;
 322   }
 323   if (!c) {
 324     qd->e = "bad curve parameters";
 325     goto fail;
 326   }
 327   if (a) MP_DROP(a);
 328   if (b) MP_DROP(b);
 329   return (c);
 330
 331 fail:
 332   if (f) F_DESTROY(f);
 333   if (a) MP_DROP(a);
 334   if (b) MP_DROP(b);
 335   return (0);
 336 }
 337
 338 /* --- @ec_ptparse@ --- *
 339  *
 340  * Arguments:   @qd_parse *qd@ = parser context
 341  *              @ec *p@ = where to put the point
 342  *
 343  * Returns:     The point address, or null.
 344  *
 345  * Use:         Parses an elliptic curve point.  This has the form
 346  *
 347  *                * %$x$%-coordinate
 348  *                * optional `,'
 349  *                * %$y$%-coordinate
 350  */
 351
 352 ec *ec_ptparse(qd_parse *qd, ec *p)
 353 {
 354   mp *x = MP_NEW, *y = MP_NEW;
 355
 356   if (qd_enum(qd, "inf") >= 0) {
 357     EC_SETINF(p);
 358     return (p);
 359   }
 360   if ((x = qd_getmp(qd)) == 0) goto fail;
 361   qd_delim(qd, ',');
 362   if ((y = qd_getmp(qd)) == 0) goto fail;
 363   EC_DESTROY(p);
 364   p->x = x;
 365   p->y = y;
 366   p->z = 0;
 367   return (p);
 368
 369 fail:
 370   if (x) MP_DROP(x);
 371   if (y) MP_DROP(y);
 372   return (0);
 373 }
 374
 375 /* --- @ec_infofromdata@ --- *
 376  *
 377  * Arguments:   @ec_info *ei@ = where to write the information
 378  *              @ecdata *ed@ = raw data
 379  *
 380  * Returns:     ---
 381  *
 382  * Use:         Loads elliptic curve information about one of the standard
 383  *              curves.
 384  */
 385
 386 void ec_infofromdata(ec_info *ei, ecdata *ed)
 387 {
 388   field *f;
 389
 390   switch (ed->ftag) {
 391     case FTAG_PRIME:
 392       f = field_prime(&ed->p);
 393       ei->c = ec_primeproj(f, &ed->a, &ed->b);
 394       break;
 395     case FTAG_NICEPRIME:
 396       f = field_niceprime(&ed->p);
 397       ei->c = ec_primeproj(f, &ed->a, &ed->b);
 398       break;
 399     case FTAG_BINPOLY:
 400       f = field_binpoly(&ed->p);
 401       ei->c = ec_binproj(f, &ed->a, &ed->b);
 402       break;
 403     case FTAG_BINNORM:
 404       f = field_binnorm(&ed->p, &ed->beta);
 405       ei->c = ec_binproj(f, &ed->a, &ed->b);
 406       break;
 407     default:
 408       abort();
 409   }
 410
 411   assert(f); assert(ei->c);
 412   EC_CREATE(&ei->g); ei->g.x = &ed->gx; ei->g.y = &ed->gy; ei->g.z = 0;
 413   ei->r = &ed->r; ei->h = &ed->h;
 414 }
 415
 416 /* --- @ec_infoparse@ --- *
 417  *
 418  * Arguments:   @qd_parse *qd@ = parser context
 419  *              @ec_info *ei@ = curve information block, currently
 420  *                      uninitialized
 421  *
 422  * Returns:     Zero on success, nonzero on failure.
 423  *
 424  * Use:         Parses an elliptic curve information string, and stores the
 425  *              information in @ei@.  This is either the name of a standard
 426  *              curve, or it has the form
 427  *
 428  *                * elliptic curve description
 429  *                * optional `;'
 430  *                * common point
 431  *                * optional `:'
 432  *                * group order
 433  *                * optional `*'
 434  *                * cofactor
 435  */
 436
 437 int ec_infoparse(qd_parse *qd, ec_info *ei)
 438 {
 439   ec_curve *c = 0;
 440   field *f;
 441   ec g = EC_INIT;
 442   const ecentry *ee;
 443   mp *r = MP_NEW, *h = MP_NEW;
 444
 445   for (ee = ectab; ee->name; ee++) {
 446     if (qd_enum(qd, ee->name) >= 0) {
 447       ec_infofromdata(ei, ee->data);
 448       goto found;
 449     }
 450   }
 451
 452   if ((c = ec_curveparse(qd)) == 0) goto fail;
 453   qd_delim(qd, ';'); if (!ec_ptparse(qd, &g)) goto fail;
 454   qd_delim(qd, ':'); if ((r = qd_getmp(qd)) == 0) goto fail;
 455   qd_delim(qd, '*'); if ((h = qd_getmp(qd)) == 0) goto fail;
 456   ei->c = c; ei->g = g; ei->r = r; ei->h = h;
 457
 458 found:
 459   return (0);
 460
 461 fail:
 462   EC_DESTROY(&g);
 463   if (r) MP_DROP(r);
 464   if (h) MP_DROP(h);
 465   if (c) { f = c->f; ec_destroycurve(c); F_DESTROY(f); }
 466   return (-1);
 467 }
 468
 469 /* --- @ec_getinfo@ --- *
 470  *
 471  * Arguments:   @ec_info *ei@ = where to write the information
 472  *              @const char *p@ = string describing a curve
 473  *
 474  * Returns:     Null on success, or a pointer to an error message.
 475  *
 476  * Use:         Parses out information about a curve.  The string is either a
 477  *              standard curve name, or a curve info string.
 478  */
 479
 480 const char *ec_getinfo(ec_info *ei, const char *p)
 481 {
 482   qd_parse qd;
 483
 484   qd.p = p;
 485   qd.e = 0;
 486   if (ec_infoparse(&qd, ei))
 487     return (qd.e);
 488   if (!qd_eofp(&qd)) {
 489     ec_freeinfo(ei);
 490     return ("junk found at end of string");
 491   }
 492   return (0);
 493 }
 494
 495 /* --- @ec_sameinfop@ --- *
 496  *
 497  * Arguments:   @const ec_info *ei, *ej@ = two elliptic curve parameter sets
 498  *
 499  * Returns:     Nonzero if the curves are identical (not just isomorphic).
 500  *
 501  * Use:         Checks for sameness of curve parameters.
 502  */
 503
 504 int ec_sameinfop(const ec_info *ei, const ec_info *ej)
 505 {
 506   return (ec_samep(ei->c, ej->c) &&
 507           MP_EQ(ei->r, ej->r) && MP_EQ(ei->h, ej->h) &&
 508           EC_EQ(&ei->g, &ej->g));
 509 }
 510
 511 /* --- @ec_freeinfo@ --- *
 512  *
 513  * Arguments:   @ec_info *ei@ = elliptic curve information block to free
 514  *
 515  * Returns:     ---
 516  *
 517  * Use:         Frees the information block.
 518  */
 519
 520 void ec_freeinfo(ec_info *ei)
 521 {
 522   field *f;
 523
 524   EC_DESTROY(&ei->g);
 525   MP_DROP(ei->r);
 526   MP_DROP(ei->h);
 527   f = ei->c->f; ec_destroycurve(ei->c); F_DESTROY(f);
 528 }
 529
 530 /* --- @ec_checkinfo@ --- *
 531  *
 532  * Arguments:   @const ec_info *ei@ = elliptic curve information block
 533  *
 534  * Returns:     Null if OK, or pointer to error message.
 535  *
 536  * Use:         Checks an elliptic curve according to the rules in SEC1.
 537  */
 538
 539 static const char *gencheck(const ec_info *ei, grand *gr, mp *q, mp *ch)
 540 {
 541   ec_curve *c = ei->c;
 542   unsigned long qmbits, rbits, cbits, B;
 543   mp *qq;
 544   mp *nn;
 545   mp *x, *y;
 546   ec p;
 547   int rc;
 548
 549   /* --- Check curve isn't anomalous --- */
 550
 551   if (MP_EQ(ei->r, q)) return ("curve is anomalous");
 552
 553   /* --- Check %$G \in E \setminus \{ 0 \}$% --- */
 554
 555   if (EC_ATINF(&ei->g)) return ("generator at infinity");
 556   if (ec_check(c, &ei->g)) return ("generator not on curve");
 557
 558   /* --- Check %$r$% is prime --- */
 559
 560   if (!pgen_primep(ei->r, gr)) return ("generator order not prime");
 561
 562   /* --- Check that the cofactor is correct --- *
 563    *
 564    * Let %$q$% be the size of the field, and let %$n = h r = \#E(\gf{q})$% be
 565    * the number of %$\gf{q}$%-rational points on our curve.  Hasse's theorem
 566    * tells us that
 567    *
 568    *   %$|q + 1 - n| \le 2\sqrt{q}$%
 569    *
 570    * or, if we square both sides,
 571    *
 572    *   %$(q + 1 - n)^2 \le 4 q$%.
 573    *
 574    * We'd like the cofactor to be uniquely determined by this equation, which
 575    * is possible as long as it's not too big.  (If it is, we have to mess
 576    * about with Weil pairings, which is no fun.)  For this, we need the
 577    * following inequalities:
 578    *
 579    *   * %$A = (q + 1 - n)^2 \le 4 q$% (both lower and upper bounds from
 580    *     Hasse's theorem);
 581    *
 582    *   * %$B = (q + 1 - n - r)^2 > 4 q$% (check %$h - 1$% isn't possible);
 583    *     and
 584    *
 585    *   * %$C = (q + 1 - n + r)^2 > 4 q$% (check %$h + 1$% isn't possible).
 586    */
 587
 588   rc = 1;
 589   qq = mp_add(MP_NEW, q, MP_ONE);
 590   nn = mp_mul(MP_NEW, ei->r, ei->h);
 591   nn = mp_sub(nn, qq, nn);
 592   qq = mp_lsl(qq, q, 2);
 593
 594   y = mp_sqr(MP_NEW, nn);
 595   if (MP_CMP(y, >, qq)) rc = 0;
 596
 597   x = mp_sub(MP_NEW, nn, ei->r);
 598   y = mp_sqr(y, x);
 599   if (MP_CMP(y, <=, qq)) rc = 0;
 600
 601   x = mp_add(x, nn, ei->r);
 602   y = mp_sqr(y, x);
 603   if (MP_CMP(y, <=, qq)) rc = 0;
 604
 605   MP_DROP(x);
 606   MP_DROP(y);
 607   MP_DROP(nn);
 608   MP_DROP(qq);
 609   if (!rc) return ("incorrect or ambiguous cofactor");
 610
 611   /* --- Check %$n G = 0$% --- */
 612
 613   EC_CREATE(&p);
 614   ec_mul(c, &p, &ei->g, ei->r);
 615   rc = EC_ATINF(&p);
 616   EC_DESTROY(&p);
 617   if (!rc) return ("incorrect group order");
 618
 619   /* --- Check the embedding degree --- */
 620
 621   rbits = mp_bits(ei->r);
 622   cbits = mp_bits(ch);
 623   qmbits = keysz_todl(keysz_fromec(rbits * 7/8));
 624   B = (qmbits + cbits - 1)/cbits;
 625   if (movcheck(ei->r, ch, B))
 626     return("curve embedding degree too low");
 627
 628   /* --- Done --- */
 629
 630   return (0);
 631 }
 632
 633 static int primeeltp(mp *x, field *f)
 634   { return (!MP_NEGP(x) && MP_CMP(x, <, f->m)); }
 635
 636 static const char *primecheck(const ec_info *ei, grand *gr)
 637 {
 638   ec_curve *c = ei->c;
 639   field *f = c->f;
 640   mp *x, *y;
 641   int rc;
 642   const char *err;
 643
 644   /* --- Check %$p$% is an odd prime --- */
 645
 646   if (!pgen_primep(f->m, gr)) return ("p not prime");
 647
 648   /* --- Check %$a$%, %$b$%, %$G_x$% and %$G_y$% are in %$[0, p)$% --- */
 649
 650   if (!primeeltp(c->a, f)) return ("a out of range");
 651   if (!primeeltp(c->b, f)) return ("b out of range");
 652   if (!primeeltp(ei->g.x, f)) return ("G_x out of range");
 653   if (!primeeltp(ei->g.x, f)) return ("G_y out of range");
 654
 655   /* --- Check %$4 a^3 + 27 b^2 \not\equiv 0 \pmod{p}$% --- */
 656
 657   x = F_SQR(f, MP_NEW, c->a);
 658   x = F_MUL(f, x, x, c->a);
 659   x = F_QDL(f, x, x);
 660   y = F_SQR(f, MP_NEW, c->b);
 661   y = F_TPL(f, y, y);
 662   y = F_TPL(f, y, y);
 663   y = F_TPL(f, y, y);
 664   x = F_ADD(f, x, x, y);
 665   rc = F_ZEROP(f, x);
 666   MP_DROP(x);
 667   MP_DROP(y);
 668   if (rc) return ("not an elliptic curve");
 669
 670   /* --- Now do the general checks --- */
 671
 672   err = gencheck(ei, gr, f->m, f->m);
 673   return (err);
 674 }
 675
 676 static const char *bincheck(const ec_info *ei, grand *gr)
 677 {
 678   ec_curve *c = ei->c;
 679   field *f = c->f;
 680   mp *x;
 681   int rc;
 682   const char *err;
 683
 684   /* --- Check that %$m$% is prime --- */
 685
 686   x = mp_fromuint(MP_NEW, f->nbits);
 687   rc = pfilt_smallfactor(x);
 688   mp_drop(x);
 689   if (rc != PGEN_DONE) return ("degree not prime");
 690
 691   /* --- Check that %$p$% is irreducible --- */
 692
 693   if (!gf_irreduciblep(f->m)) return ("p not irreducible");
 694
 695   /* --- Check that %$a, b, G_x, G_y$% have degree less than %$p$% --- */
 696
 697   if (mp_bits(c->a) > f->nbits) return ("a out of range");
 698   if (mp_bits(c->b) > f->nbits) return ("a out of range");
 699   if (mp_bits(ei->g.x) > f->nbits) return ("G_x out of range");
 700   if (mp_bits(ei->g.y) > f->nbits) return ("G_y out of range");
 701
 702   /* --- Check that %$b \ne 0$% --- */
 703
 704   if (F_ZEROP(f, c->b)) return ("b is zero");
 705
 706   /* --- Now do the general checks --- */
 707
 708   x = mp_lsl(MP_NEW, MP_ONE, f->nbits);
 709   err = gencheck(ei, gr, x, MP_TWO);
 710   mp_drop(x);
 711   return (err);
 712 }
 713
 714 const char *ec_checkinfo(const ec_info *ei, grand *gr)
 715 {
 716   switch (F_TYPE(ei->c->f)) {
 717     case FTY_PRIME: return (primecheck(ei, gr)); break;
 718     case FTY_BINARY: return (bincheck(ei, gr)); break;
 719   }
 720   return ("unknown curve type");
 721 }
 722
 723 /*----- Test rig ----------------------------------------------------------*/
 724
 725 #ifdef TEST_RIG
 726
 727 #include "fibrand.h"
 728
 729 int main(int argc, char *argv[])
 730 {
 731   const ecentry *ee;
 732   const char *e;
 733   int ok = 1;
 734   int i;
 735   grand *gr;
 736
 737   gr = fibrand_create(0);
 738   if (argc > 1) {
 739     for (i = 1; i < argc; i++) {
 740       ec_info ei;
 741       if ((e = ec_getinfo(&ei, argv[i])) != 0)
 742         fprintf(stderr, "bad curve spec `%s': %s\n", argv[i], e);
 743       else {
 744         e = ec_checkinfo(&ei, gr);
 745         ec_freeinfo(&ei);
 746         if (!e)
 747           printf("OK %s\n", argv[i]);
 748         else {
 749           printf("BAD %s: %s\n", argv[i], e);
 750           ok = 0;
 751         }
 752       }
 753       assert(mparena_count(MPARENA_GLOBAL) == 0);
 754     }
 755   } else {
 756     fputs("checking standard curves:", stdout);
 757     fflush(stdout);
 758     for (ee = ectab; ee->name; ee++) {
 759       ec_info ei;
 760       ec_infofromdata(&ei, ee->data);
 761       e = ec_checkinfo(&ei, gr);
 762       ec_freeinfo(&ei);
 763       if (e) {
 764         printf(" [%s fails: %s]", ee->name, e);
 765         ok = 0;
 766       } else
 767         printf(" %s", ee->name);
 768       fflush(stdout);
 769       assert(mparena_count(MPARENA_GLOBAL) == 0);
 770     }
 771     fputs(ok ? " ok\n" : " failed\n", stdout);
 772   }
 773   gr->ops->destroy(gr);
 774   return (!ok);
 775 }
 776
 777 #endif
 778
 779 /*----- That's all, folks -------------------------------------------------*/