/* -*-c-*-
*
- * $Id: ec-info.c,v 1.1 2004/03/27 17:54:11 mdw Exp $
+ * $Id$
*
* Elliptic curve information management
*
* MA 02111-1307, USA.
*/
-/*----- Revision history --------------------------------------------------*
- *
- * $Log: ec-info.c,v $
- * Revision 1.1 2004/03/27 17:54:11 mdw
- * Standard curves and curve checking.
- *
- */
-
/*----- Header files ------------------------------------------------------*/
#include "ec.h"
#include "gf.h"
#include "pgen.h"
#include "mprand.h"
+#include "mpint.h"
#include "rabin.h"
/*----- Main code ---------------------------------------------------------*/
default:
goto fail;
}
+ if (!c) {
+ qd->e = "bad curve parameters";
+ goto fail;
+ }
if (a) MP_DROP(a);
if (b) MP_DROP(b);
return (c);
return (0);
}
+/* --- @ec_infofromdata@ --- *
+ *
+ * Arguments: @ec_info *ei@ = where to write the information
+ * @ecdata *ed@ = raw data
+ *
+ * Returns: ---
+ *
+ * Use: Loads elliptic curve information about one of the standard
+ * curves.
+ */
+
+void ec_infofromdata(ec_info *ei, ecdata *ed)
+{
+ field *f;
+
+ switch (ed->ftag) {
+ case FTAG_PRIME:
+ f = field_prime(&ed->p);
+ ei->c = ec_primeproj(f, &ed->a, &ed->b);
+ break;
+ case FTAG_NICEPRIME:
+ f = field_niceprime(&ed->p);
+ ei->c = ec_primeproj(f, &ed->a, &ed->b);
+ break;
+ case FTAG_BINPOLY:
+ f = field_binpoly(&ed->p);
+ ei->c = ec_binproj(f, &ed->a, &ed->b);
+ break;
+ case FTAG_BINNORM:
+ f = field_binnorm(&ed->p, &ed->beta);
+ ei->c = ec_binproj(f, &ed->a, &ed->b);
+ break;
+ default:
+ abort();
+ }
+
+ assert(f); assert(ei->c);
+ EC_CREATE(&ei->g); ei->g.x = &ed->gx; ei->g.y = &ed->gy; ei->g.z = 0;
+ ei->r = &ed->r; ei->h = &ed->h;
+}
+
/* --- @ec_infoparse@ --- *
*
* Arguments: @qd_parse *qd@ = parser context
* Returns: Zero on success, nonzero on failure.
*
* Use: Parses an elliptic curve information string, and stores the
- * information in @ei@. This has the form
+ * information in @ei@. This is either the name of a standard
+ * curve, or it has the form
*
* * elliptic curve description
* * optional `/'
ec_curve *c = 0;
field *f;
ec g = EC_INIT;
+ const ecentry *ee;
mp *r = MP_NEW, *h = MP_NEW;
+ for (ee = ectab; ee->name; ee++) {
+ if (qd_enum(qd, ee->name) >= 0) {
+ ec_infofromdata(ei, ee->data);
+ goto found;
+ }
+ }
+
if ((c = ec_curveparse(qd)) == 0) goto fail;
qd_delim(qd, '/'); if (!ec_ptparse(qd, &g)) goto fail;
qd_delim(qd, ':'); if ((r = qd_getmp(qd)) == 0) goto fail;
qd_delim(qd, '*'); if ((h = qd_getmp(qd)) == 0) goto fail;
-
ei->c = c; ei->g = g; ei->r = r; ei->h = h;
+
+found:
return (0);
fail:
return (-1);
}
-/* --- @getinfo@ --- *
- *
- * Arguments: @ec_info *ei@ = where to write the information
- * @const ecdata *ed@ = raw data
- *
- * Returns: ---
- *
- * Use: Loads elliptic curve information about one of the standard
- * curves.
- */
-
-static mp *getmp(const mpw *v, size_t n)
-{
- mp *x = mp_new(n, 0);
- memcpy(x->v, v, MPWS(n));
- return (x);
-}
-
-static void getinfo(ec_info *ei, const ecdata *ed)
-{
- field *f;
- mp *p = 0, *a = 0, *b = 0;
-
- switch (ed->ftag) {
- case FTAG_PRIME:
- p = getmp(ed->p, ed->psz);
- f = field_prime(p);
- a = getmp(ed->a, ed->asz); b = getmp(ed->b, ed->bsz);
- ei->c = ec_primeproj(f, a, b);
- break;
- case FTAG_NICEPRIME:
- p = getmp(ed->p, ed->psz);
- f = field_niceprime(p);
- a = getmp(ed->a, ed->asz); b = getmp(ed->b, ed->bsz);
- ei->c = ec_primeproj(f, a, b);
- break;
- case FTAG_BINPOLY:
- p = getmp(ed->p, ed->psz);
- f = field_binpoly(p);
- a = getmp(ed->a, ed->asz); b = getmp(ed->b, ed->bsz);
- ei->c = ec_binproj(f, a, b);
- break;
- default:
- abort();
- }
-
- EC_CREATE(&ei->g);
- ei->g.x = getmp(ed->gx, ed->gxsz);
- ei->g.y = getmp(ed->gy, ed->gysz);
- ei->g.z = 0;
- ei->r = getmp(ed->r, ed->rsz);
- ei->h = getmp(ed->h, ed->hsz);
-
- MP_DROP(p);
- MP_DROP(a);
- MP_DROP(b);
-}
-
/* --- @ec_getinfo@ --- *
*
* Arguments: @ec_info *ei@ = where to write the information
const char *ec_getinfo(ec_info *ei, const char *p)
{
qd_parse qd;
- const ecentry *ee;
qd.p = p;
qd.e = 0;
- for (ee = ectab; ee->name; ee++) {
- if (qd_enum(&qd, ee->name) >= 0) {
- getinfo(ei, ee->data);
- goto found;
- }
- }
if (ec_infoparse(&qd, ei))
return (qd.e);
-found:
if (!qd_eofp(&qd)) {
ec_freeinfo(ei);
return ("junk found at end of string");
return (0);
}
+/* --- @ec_sameinfop@ --- *
+ *
+ * Arguments: @ec_info *ei, *ej@ = two elliptic curve parameter sets
+ *
+ * Returns: Nonzero if the curves are identical (not just isomorphic).
+ *
+ * Use: Checks for sameness of curve parameters.
+ */
+
+int ec_sameinfop(ec_info *ei, ec_info *ej)
+{
+ return (ec_samep(ei->c, ej->c) &&
+ MP_EQ(ei->r, ej->r) && MP_EQ(ei->h, ej->h) &&
+ EC_EQ(&ei->g, &ej->g));
+}
+
/* --- @ec_freeinfo@ --- *
*
* Arguments: @ec_info *ei@ = elliptic curve information block to free
* Use: Checks an elliptic curve according to the rules in SEC1.
*/
-static int primep(mp *p, grand *gr)
-{
- int i = rabin_iters(mp_bits(p));
- rabin r;
- mp *x = MP_NEW;
-
- switch (pfilt_smallfactor(p)) {
- case PGEN_DONE: return (1);
- case PGEN_FAIL: return (0);
- }
- rabin_create(&r, p);
- while (i) {
- x = mprand_range(x, p, gr, 0);
- if (rabin_rtest(&r, x) == PGEN_FAIL)
- break;
- i--;
- }
- MP_DROP(x);
- rabin_destroy(&r);
- return (!i);
-}
-
static int primeeltp(mp *x, field *f)
{
- return (!MP_ISNEG(x) && MP_CMP(x, <, f->m));
+ return (!MP_NEGP(x) && MP_CMP(x, <, f->m));
}
static const char *primecheck(const ec_info *ei, grand *gr)
/* --- Check %$p$% is an odd prime --- */
- if (!primep(f->m, gr)) return ("p not prime");
+ if (!pgen_primep(f->m, gr)) return ("p not prime");
/* --- Check %$a$%, %$b$%, %$G_x$% and %$G_y$% are in %$[0, p)$% --- */
/* --- Check %$r$% is prime --- */
- if (!primep(ei->r, gr)) return ("generator order not prime");
-
- /* --- Check %$0 < h \le 4$% --- */
-
- if (MP_CMP(ei->h, <, MP_ONE) || MP_CMP(ei->h, >, MP_FOUR))
- return ("cofactor out of range");
+ if (!pgen_primep(ei->r, gr)) return ("generator order not prime");
/* --- Check %$h = \lfloor (\sqrt{p} + 1)^2/r \rlfoor$% --- *
*
MP_DROP(x);
if (i) return ("curve is weak");
+ /* --- Check %$0 < h \le 4$% --- */
+
+ if (MP_CMP(ei->h, <, MP_ONE) || MP_CMP(ei->h, >, MP_FOUR))
+ return ("cofactor out of range");
+
/* --- Done --- */
return (0);
ec p;
int rc;
+ /* --- Check that %$m$% is prime --- */
+
+ x = mp_fromuint(MP_NEW, f->nbits);
+ rc = pfilt_smallfactor(x);
+ mp_drop(x);
+ if (rc != PGEN_DONE) return ("degree not prime");
+
/* --- Check that %$p$% is irreducible --- */
if (!gf_irreduciblep(f->m)) return ("p not irreducible");
/* --- Check %$r$% is prime --- */
- if (!primep(ei->r, gr)) return ("generator order not prime");
-
- /* --- Check %$0 < h \le 4$% --- */
-
- if (MP_CMP(ei->h, <, MP_ONE) || MP_CMP(ei->h, >, MP_FOUR))
- return ("cofactor out of range");
+ if (!pgen_primep(ei->r, gr)) return ("generator order not prime");
/* --- Check %$h = \lfloor (\sqrt{2^m} + 1)^2/r \rlfoor$% --- *
*
MP_DROP(x);
if (i) return ("curve is weak");
+ /* --- Check %$0 < h \le 4$% --- */
+
+ if (MP_CMP(ei->h, <, MP_ONE) || MP_CMP(ei->h, >, MP_FOUR))
+ return ("cofactor out of range");
+
/* --- Done --- */
return (0);
#include "fibrand.h"
-int main(void)
+int main(int argc, char *argv[])
{
const ecentry *ee;
const char *e;
int ok = 1;
+ int i;
grand *gr;
gr = fibrand_create(0);
- fputs("checking standard curves: ", stdout);
- for (ee = ectab; ee->name; ee++) {
- ec_info ei;
- getinfo(&ei, ee->data);
- e = ec_checkinfo(&ei, gr);
- ec_freeinfo(&ei);
- if (e) {
- fprintf(stderr, "\n*** curve %s fails: %s\n", ee->name, e);
- ok = 0;
+ if (argc > 1) {
+ for (i = 1; i < argc; i++) {
+ ec_info ei;
+ if ((e = ec_getinfo(&ei, argv[i])) != 0)
+ fprintf(stderr, "bad curve spec `%s': %s", argv[i], e);
+ else {
+ e = ec_checkinfo(&ei, gr);
+ ec_freeinfo(&ei);
+ if (!e)
+ printf("OK %s\n", argv[i]);
+ else {
+ printf("BAD %s: %s\n", argv[i], e);
+ ok = 0;
+ }
+ }
}
- putchar('.');
+ } else {
+ fputs("checking standard curves:", stdout);
fflush(stdout);
+ for (ee = ectab; ee->name; ee++) {
+ ec_info ei;
+ ec_infofromdata(&ei, ee->data);
+ e = ec_checkinfo(&ei, gr);
+ ec_freeinfo(&ei);
+ if (e) {
+ printf(" [%s fails: %s]", ee->name, e);
+ ok = 0;
+ } else
+ printf(" %s", ee->name);
+ fflush(stdout);
+ }
+ fputs(ok ? " ok\n" : " failed\n", stdout);
}
gr->ops->destroy(gr);
- fputs(ok ? " ok\n" : " failed\n", stdout);
return (!ok);
}