Commit | Line | Data |
---|---|---|
432c4e18 | 1 | /* -*-c-*- |
432c4e18 | 2 | * |
3 | * Elliptic curve information management | |
4 | * | |
5 | * (c) 2004 Straylight/Edgeware | |
6 | */ | |
7 | ||
45c0fd36 | 8 | /*----- Licensing notice --------------------------------------------------* |
432c4e18 | 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. | |
45c0fd36 | 16 | * |
432c4e18 | 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. | |
45c0fd36 | 21 | * |
432c4e18 | 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 | ||
432c4e18 | 28 | /*----- Header files ------------------------------------------------------*/ |
29 | ||
61a0271a MW |
30 | #include <mLib/darray.h> |
31 | ||
432c4e18 | 32 | #include "ec.h" |
33 | #include "ectab.h" | |
34 | #include "gf.h" | |
61a0271a MW |
35 | #include "keysz.h" |
36 | #include "mpbarrett.h" | |
432c4e18 | 37 | #include "pgen.h" |
61a0271a | 38 | #include "primeiter.h" |
432c4e18 | 39 | #include "mprand.h" |
389d8222 | 40 | #include "mpint.h" |
432c4e18 | 41 | #include "rabin.h" |
42 | ||
61a0271a MW |
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 | |
b14f3203 | 93 | * %$p^d \not\equiv 1 \pmod{r}$%. |
61a0271a MW |
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; | |
b14f3203 | 115 | * http://eprint.iacr.org/2006/415 |
61a0271a MW |
116 | * |
117 | * [P1363] IEEE 1363-2000: Standard Specifications for Public Key | |
b14f3203 | 118 | * Cryptography; http://grouper.ieee.org/groups/1363/P1363/index.html |
61a0271a MW |
119 | * |
120 | * [SEC1] SEC 1: Elliptic Curve Cryptography; | |
b14f3203 | 121 | * http://www.secg.org/download/aid-385/sec1_final.pdf |
61a0271a MW |
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 | ||
432c4e18 | 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 | |
20095408 | 259 | * * an optional `;' |
432c4e18 | 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; | |
20095408 | 274 | qd_delim(qd, ';'); |
432c4e18 | 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 | } | |
02d7884d | 323 | if (!c) { |
324 | qd->e = "bad curve parameters"; | |
325 | goto fail; | |
326 | } | |
432c4e18 | 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 | ||
20ca05f0 | 375 | /* --- @ec_infofromdata@ --- * |
34e4f738 | 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 | ||
20ca05f0 | 386 | void ec_infofromdata(ec_info *ei, ecdata *ed) |
34e4f738 | 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; | |
4edc47b8 | 403 | case FTAG_BINNORM: |
404 | f = field_binnorm(&ed->p, &ed->beta); | |
405 | ei->c = ec_binproj(f, &ed->a, &ed->b); | |
406 | break; | |
34e4f738 | 407 | default: |
408 | abort(); | |
409 | } | |
410 | ||
02d7884d | 411 | assert(f); assert(ei->c); |
34e4f738 | 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 | ||
432c4e18 | 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 | |
34e4f738 | 425 | * information in @ei@. This is either the name of a standard |
426 | * curve, or it has the form | |
432c4e18 | 427 | * |
428 | * * elliptic curve description | |
20095408 | 429 | * * optional `;' |
432c4e18 | 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; | |
34e4f738 | 442 | const ecentry *ee; |
432c4e18 | 443 | mp *r = MP_NEW, *h = MP_NEW; |
444 | ||
20ca05f0 | 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 | } | |
45c0fd36 | 450 | } |
02d7884d | 451 | |
432c4e18 | 452 | if ((c = ec_curveparse(qd)) == 0) goto fail; |
20095408 | 453 | qd_delim(qd, ';'); if (!ec_ptparse(qd, &g)) goto fail; |
432c4e18 | 454 | qd_delim(qd, ':'); if ((r = qd_getmp(qd)) == 0) goto fail; |
455 | qd_delim(qd, '*'); if ((h = qd_getmp(qd)) == 0) goto fail; | |
432c4e18 | 456 | ei->c = c; ei->g = g; ei->r = r; ei->h = h; |
34e4f738 | 457 | |
458 | found: | |
432c4e18 | 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 | ||
432c4e18 | 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; | |
432c4e18 | 483 | |
484 | qd.p = p; | |
485 | qd.e = 0; | |
432c4e18 | 486 | if (ec_infoparse(&qd, ei)) |
487 | return (qd.e); | |
432c4e18 | 488 | if (!qd_eofp(&qd)) { |
489 | ec_freeinfo(ei); | |
490 | return ("junk found at end of string"); | |
491 | } | |
492 | return (0); | |
493 | } | |
494 | ||
34e4f738 | 495 | /* --- @ec_sameinfop@ --- * |
496 | * | |
497 | * Arguments: @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(ec_info *ei, 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 | ||
432c4e18 | 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 | ||
61a0271a | 539 | static const char *gencheck(const ec_info *ei, grand *gr, mp *q, mp *ch) |
432c4e18 | 540 | { |
541 | ec_curve *c = ei->c; | |
61a0271a | 542 | unsigned long qmbits, rbits, cbits, B; |
30ac115b MW |
543 | mp *qq; |
544 | mp *nn; | |
432c4e18 | 545 | mp *x, *y; |
546 | ec p; | |
547 | int rc; | |
548 | ||
61a0271a MW |
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 \}$% --- */ | |
432c4e18 | 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 | ||
34e4f738 | 560 | if (!pgen_primep(ei->r, gr)) return ("generator order not prime"); |
432c4e18 | 561 | |
30ac115b MW |
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); | |
432c4e18 | 581 | * |
30ac115b MW |
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). | |
432c4e18 | 586 | */ |
587 | ||
30ac115b MW |
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 | ||
432c4e18 | 605 | MP_DROP(x); |
606 | MP_DROP(y); | |
30ac115b MW |
607 | MP_DROP(nn); |
608 | MP_DROP(qq); | |
609 | if (!rc) return ("incorrect or ambiguous cofactor"); | |
432c4e18 | 610 | |
61a0271a | 611 | /* --- Check %$n G = 0$% --- */ |
432c4e18 | 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 | ||
61a0271a | 619 | /* --- Check the embedding degree --- */ |
432c4e18 | 620 | |
61a0271a MW |
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"); | |
5c3f75ec | 627 | |
432c4e18 | 628 | /* --- Done --- */ |
629 | ||
630 | return (0); | |
631 | } | |
632 | ||
30ac115b MW |
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) | |
432c4e18 | 637 | { |
638 | ec_curve *c = ei->c; | |
639 | field *f = c->f; | |
432c4e18 | 640 | mp *x, *y; |
432c4e18 | 641 | int rc; |
30ac115b MW |
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 | ||
61a0271a | 672 | err = gencheck(ei, gr, f->m, f->m); |
30ac115b MW |
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; | |
432c4e18 | 683 | |
389d8222 | 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 | ||
432c4e18 | 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 | ||
30ac115b | 706 | /* --- Now do the general checks --- */ |
432c4e18 | 707 | |
708 | x = mp_lsl(MP_NEW, MP_ONE, f->nbits); | |
61a0271a | 709 | err = gencheck(ei, gr, x, MP_TWO); |
30ac115b MW |
710 | mp_drop(x); |
711 | return (err); | |
432c4e18 | 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 | ||
53cbeae3 | 729 | int main(int argc, char *argv[]) |
432c4e18 | 730 | { |
731 | const ecentry *ee; | |
732 | const char *e; | |
733 | int ok = 1; | |
53cbeae3 | 734 | int i; |
432c4e18 | 735 | grand *gr; |
736 | ||
737 | gr = fibrand_create(0); | |
53cbeae3 | 738 | if (argc > 1) { |
739 | for (i = 1; i < argc; i++) { | |
740 | ec_info ei; | |
741 | if ((e = ec_getinfo(&ei, argv[i])) != 0) | |
3cf91080 | 742 | fprintf(stderr, "bad curve spec `%s': %s\n", argv[i], e); |
53cbeae3 | 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 | } | |
30ac115b | 753 | assert(mparena_count(MPARENA_GLOBAL) == 0); |
53cbeae3 | 754 | } |
755 | } else { | |
20ca05f0 | 756 | fputs("checking standard curves:", stdout); |
757 | fflush(stdout); | |
53cbeae3 | 758 | for (ee = ectab; ee->name; ee++) { |
759 | ec_info ei; | |
20ca05f0 | 760 | ec_infofromdata(&ei, ee->data); |
53cbeae3 | 761 | e = ec_checkinfo(&ei, gr); |
762 | ec_freeinfo(&ei); | |
763 | if (e) { | |
106b481c | 764 | printf(" [%s fails: %s]", ee->name, e); |
53cbeae3 | 765 | ok = 0; |
f94b972d | 766 | } else |
20ca05f0 | 767 | printf(" %s", ee->name); |
53cbeae3 | 768 | fflush(stdout); |
30ac115b | 769 | assert(mparena_count(MPARENA_GLOBAL) == 0); |
432c4e18 | 770 | } |
20ca05f0 | 771 | fputs(ok ? " ok\n" : " failed\n", stdout); |
432c4e18 | 772 | } |
773 | gr->ops->destroy(gr); | |
432c4e18 | 774 | return (!ok); |
775 | } | |
776 | ||
777 | #endif | |
778 | ||
779 | /*----- That's all, folks -------------------------------------------------*/ |