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