Commit | Line | Data |
---|---|---|
432c4e18 | 1 | /* -*-c-*- |
2 | * | |
a69a3efd | 3 | * $Id$ |
432c4e18 | 4 | * |
5 | * Elliptic curve information management | |
6 | * | |
7 | * (c) 2004 Straylight/Edgeware | |
8 | */ | |
9 | ||
45c0fd36 | 10 | /*----- Licensing notice --------------------------------------------------* |
432c4e18 | 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. | |
45c0fd36 | 18 | * |
432c4e18 | 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. | |
45c0fd36 | 23 | * |
432c4e18 | 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 | ||
432c4e18 | 30 | /*----- Header files ------------------------------------------------------*/ |
31 | ||
61a0271a MW |
32 | #include <mLib/darray.h> |
33 | ||
432c4e18 | 34 | #include "ec.h" |
35 | #include "ectab.h" | |
36 | #include "gf.h" | |
61a0271a MW |
37 | #include "keysz.h" |
38 | #include "mpbarrett.h" | |
432c4e18 | 39 | #include "pgen.h" |
61a0271a | 40 | #include "primeiter.h" |
432c4e18 | 41 | #include "mprand.h" |
389d8222 | 42 | #include "mpint.h" |
432c4e18 | 43 | #include "rabin.h" |
44 | ||
61a0271a MW |
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 | ||
432c4e18 | 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 | |
20095408 | 261 | * * an optional `;' |
432c4e18 | 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; | |
20095408 | 276 | qd_delim(qd, ';'); |
432c4e18 | 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 | } | |
02d7884d | 325 | if (!c) { |
326 | qd->e = "bad curve parameters"; | |
327 | goto fail; | |
328 | } | |
432c4e18 | 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 | ||
20ca05f0 | 377 | /* --- @ec_infofromdata@ --- * |
34e4f738 | 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 | ||
20ca05f0 | 388 | void ec_infofromdata(ec_info *ei, ecdata *ed) |
34e4f738 | 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; | |
4edc47b8 | 405 | case FTAG_BINNORM: |
406 | f = field_binnorm(&ed->p, &ed->beta); | |
407 | ei->c = ec_binproj(f, &ed->a, &ed->b); | |
408 | break; | |
34e4f738 | 409 | default: |
410 | abort(); | |
411 | } | |
412 | ||
02d7884d | 413 | assert(f); assert(ei->c); |
34e4f738 | 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 | ||
432c4e18 | 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 | |
34e4f738 | 427 | * information in @ei@. This is either the name of a standard |
428 | * curve, or it has the form | |
432c4e18 | 429 | * |
430 | * * elliptic curve description | |
20095408 | 431 | * * optional `;' |
432c4e18 | 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; | |
34e4f738 | 444 | const ecentry *ee; |
432c4e18 | 445 | mp *r = MP_NEW, *h = MP_NEW; |
446 | ||
20ca05f0 | 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 | } | |
45c0fd36 | 452 | } |
02d7884d | 453 | |
432c4e18 | 454 | if ((c = ec_curveparse(qd)) == 0) goto fail; |
20095408 | 455 | qd_delim(qd, ';'); if (!ec_ptparse(qd, &g)) goto fail; |
432c4e18 | 456 | qd_delim(qd, ':'); if ((r = qd_getmp(qd)) == 0) goto fail; |
457 | qd_delim(qd, '*'); if ((h = qd_getmp(qd)) == 0) goto fail; | |
432c4e18 | 458 | ei->c = c; ei->g = g; ei->r = r; ei->h = h; |
34e4f738 | 459 | |
460 | found: | |
432c4e18 | 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 | ||
432c4e18 | 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; | |
432c4e18 | 485 | |
486 | qd.p = p; | |
487 | qd.e = 0; | |
432c4e18 | 488 | if (ec_infoparse(&qd, ei)) |
489 | return (qd.e); | |
432c4e18 | 490 | if (!qd_eofp(&qd)) { |
491 | ec_freeinfo(ei); | |
492 | return ("junk found at end of string"); | |
493 | } | |
494 | return (0); | |
495 | } | |
496 | ||
34e4f738 | 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 | ||
432c4e18 | 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 | ||
61a0271a | 541 | static const char *gencheck(const ec_info *ei, grand *gr, mp *q, mp *ch) |
432c4e18 | 542 | { |
543 | ec_curve *c = ei->c; | |
61a0271a | 544 | unsigned long qmbits, rbits, cbits, B; |
30ac115b MW |
545 | mp *qq; |
546 | mp *nn; | |
432c4e18 | 547 | mp *x, *y; |
548 | ec p; | |
549 | int rc; | |
550 | ||
61a0271a MW |
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 \}$% --- */ | |
432c4e18 | 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 | ||
34e4f738 | 562 | if (!pgen_primep(ei->r, gr)) return ("generator order not prime"); |
432c4e18 | 563 | |
30ac115b MW |
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); | |
432c4e18 | 583 | * |
30ac115b MW |
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). | |
432c4e18 | 588 | */ |
589 | ||
30ac115b MW |
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 | ||
432c4e18 | 607 | MP_DROP(x); |
608 | MP_DROP(y); | |
30ac115b MW |
609 | MP_DROP(nn); |
610 | MP_DROP(qq); | |
611 | if (!rc) return ("incorrect or ambiguous cofactor"); | |
432c4e18 | 612 | |
61a0271a | 613 | /* --- Check %$n G = 0$% --- */ |
432c4e18 | 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 | ||
61a0271a | 621 | /* --- Check the embedding degree --- */ |
432c4e18 | 622 | |
61a0271a MW |
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"); | |
5c3f75ec | 629 | |
432c4e18 | 630 | /* --- Done --- */ |
631 | ||
632 | return (0); | |
633 | } | |
634 | ||
30ac115b MW |
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) | |
432c4e18 | 639 | { |
640 | ec_curve *c = ei->c; | |
641 | field *f = c->f; | |
432c4e18 | 642 | mp *x, *y; |
432c4e18 | 643 | int rc; |
30ac115b MW |
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 | ||
61a0271a | 674 | err = gencheck(ei, gr, f->m, f->m); |
30ac115b MW |
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; | |
432c4e18 | 685 | |
389d8222 | 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 | ||
432c4e18 | 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 | ||
30ac115b | 708 | /* --- Now do the general checks --- */ |
432c4e18 | 709 | |
710 | x = mp_lsl(MP_NEW, MP_ONE, f->nbits); | |
61a0271a | 711 | err = gencheck(ei, gr, x, MP_TWO); |
30ac115b MW |
712 | mp_drop(x); |
713 | return (err); | |
432c4e18 | 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 | ||
53cbeae3 | 731 | int main(int argc, char *argv[]) |
432c4e18 | 732 | { |
733 | const ecentry *ee; | |
734 | const char *e; | |
735 | int ok = 1; | |
53cbeae3 | 736 | int i; |
432c4e18 | 737 | grand *gr; |
738 | ||
739 | gr = fibrand_create(0); | |
53cbeae3 | 740 | if (argc > 1) { |
741 | for (i = 1; i < argc; i++) { | |
742 | ec_info ei; | |
743 | if ((e = ec_getinfo(&ei, argv[i])) != 0) | |
3cf91080 | 744 | fprintf(stderr, "bad curve spec `%s': %s\n", argv[i], e); |
53cbeae3 | 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 | } | |
30ac115b | 755 | assert(mparena_count(MPARENA_GLOBAL) == 0); |
53cbeae3 | 756 | } |
757 | } else { | |
20ca05f0 | 758 | fputs("checking standard curves:", stdout); |
759 | fflush(stdout); | |
53cbeae3 | 760 | for (ee = ectab; ee->name; ee++) { |
761 | ec_info ei; | |
20ca05f0 | 762 | ec_infofromdata(&ei, ee->data); |
53cbeae3 | 763 | e = ec_checkinfo(&ei, gr); |
764 | ec_freeinfo(&ei); | |
765 | if (e) { | |
106b481c | 766 | printf(" [%s fails: %s]", ee->name, e); |
53cbeae3 | 767 | ok = 0; |
f94b972d | 768 | } else |
20ca05f0 | 769 | printf(" %s", ee->name); |
53cbeae3 | 770 | fflush(stdout); |
30ac115b | 771 | assert(mparena_count(MPARENA_GLOBAL) == 0); |
432c4e18 | 772 | } |
20ca05f0 | 773 | fputs(ok ? " ok\n" : " failed\n", stdout); |
432c4e18 | 774 | } |
775 | gr->ops->destroy(gr); | |
432c4e18 | 776 | return (!ok); |
777 | } | |
778 | ||
779 | #endif | |
780 | ||
781 | /*----- That's all, folks -------------------------------------------------*/ |