--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: ec-info.c,v 1.1 2004/03/27 17:54:11 mdw Exp $
+ *
+ * Elliptic curve information management
+ *
+ * (c) 2004 Straylight/Edgeware
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * This file is part of Catacomb.
+ *
+ * Catacomb is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Library General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ * Catacomb is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public
+ * License along with Catacomb; if not, write to the Free
+ * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
+ * 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 "ectab.h"
+#include "gf.h"
+#include "pgen.h"
+#include "mprand.h"
+#include "rabin.h"
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- @ec_curveparse@ --- *
+ *
+ * Arguments: @qd_parse *qd@ = parser context
+ *
+ * Returns: Elliptic curve pointer if OK, or null.
+ *
+ * Use: Parses an elliptic curve description, which has the form
+ *
+ * * a field description
+ * * an optional `/'
+ * * `prime', `primeproj', `bin', or `binproj'
+ * * an optional `:'
+ * * the %$a$% parameter
+ * * an optional `,'
+ * * the %$b$% parameter
+ */
+
+ec_curve *ec_curveparse(qd_parse *qd)
+{
+ mp *a = MP_NEW, *b = MP_NEW;
+ ec_curve *c;
+ field *f;
+
+ if ((f = field_parse(qd)) == 0) goto fail;
+ qd_delim(qd, '/');
+ switch (qd_enum(qd, "prime,primeproj,bin,binproj")) {
+ case 0:
+ if (F_TYPE(f) != FTY_PRIME) {
+ qd->e = "field not prime";
+ goto fail;
+ }
+ qd_delim(qd, ':');
+ if ((a = qd_getmp(qd)) == 0) goto fail;
+ qd_delim(qd, ',');
+ if ((b = qd_getmp(qd)) == 0) goto fail;
+ c = ec_prime(f, a, b);
+ break;
+ case 1:
+ if (F_TYPE(f) != FTY_PRIME) {
+ qd->e = "field not prime";
+ goto fail;
+ }
+ qd_delim(qd, ':');
+ if ((a = qd_getmp(qd)) == 0) goto fail;
+ qd_delim(qd, ',');
+ if ((b = qd_getmp(qd)) == 0) goto fail;
+ c = ec_primeproj(f, a, b);
+ break;
+ case 2:
+ if (F_TYPE(f) != FTY_BINARY) {
+ qd->e = "field not binary";
+ goto fail;
+ }
+ qd_delim(qd, ':');
+ if ((a = qd_getmp(qd)) == 0) goto fail;
+ qd_delim(qd, ',');
+ if ((b = qd_getmp(qd)) == 0) goto fail;
+ c = ec_bin(f, a, b);
+ break;
+ case 3:
+ if (F_TYPE(f) != FTY_BINARY) {
+ qd->e = "field not binary";
+ goto fail;
+ }
+ qd_delim(qd, ':');
+ if ((a = qd_getmp(qd)) == 0) goto fail;
+ qd_delim(qd, ',');
+ if ((b = qd_getmp(qd)) == 0) goto fail;
+ c = ec_binproj(f, a, b);
+ break;
+ default:
+ goto fail;
+ }
+ if (a) MP_DROP(a);
+ if (b) MP_DROP(b);
+ return (c);
+
+fail:
+ if (f) F_DESTROY(f);
+ if (a) MP_DROP(a);
+ if (b) MP_DROP(b);
+ return (0);
+}
+
+/* --- @ec_ptparse@ --- *
+ *
+ * Arguments: @qd_parse *qd@ = parser context
+ * @ec *p@ = where to put the point
+ *
+ * Returns: The point address, or null.
+ *
+ * Use: Parses an elliptic curve point. This has the form
+ *
+ * * %$x$%-coordinate
+ * * optional `,'
+ * * %$y$%-coordinate
+ */
+
+ec *ec_ptparse(qd_parse *qd, ec *p)
+{
+ mp *x = MP_NEW, *y = MP_NEW;
+
+ if (qd_enum(qd, "inf") >= 0) {
+ EC_SETINF(p);
+ return (p);
+ }
+ if ((x = qd_getmp(qd)) == 0) goto fail;
+ qd_delim(qd, ',');
+ if ((y = qd_getmp(qd)) == 0) goto fail;
+ EC_DESTROY(p);
+ p->x = x;
+ p->y = y;
+ p->z = 0;
+ return (p);
+
+fail:
+ if (x) MP_DROP(x);
+ if (y) MP_DROP(y);
+ return (0);
+}
+
+/* --- @ec_infoparse@ --- *
+ *
+ * Arguments: @qd_parse *qd@ = parser context
+ * @ec_info *ei@ = curve information block, currently
+ * uninitialized
+ *
+ * Returns: Zero on success, nonzero on failure.
+ *
+ * Use: Parses an elliptic curve information string, and stores the
+ * information in @ei@. This has the form
+ *
+ * * elliptic curve description
+ * * optional `/'
+ * * common point
+ * * optional `:'
+ * * group order
+ * * optional `*'
+ * * cofactor
+ */
+
+int ec_infoparse(qd_parse *qd, ec_info *ei)
+{
+ ec_curve *c = 0;
+ field *f;
+ ec g = EC_INIT;
+ mp *r = MP_NEW, *h = MP_NEW;
+
+ 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;
+ return (0);
+
+fail:
+ EC_DESTROY(&g);
+ if (r) MP_DROP(r);
+ if (h) MP_DROP(h);
+ if (c) { f = c->f; ec_destroycurve(c); F_DESTROY(f); }
+ 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 *p@ = string describing a curve
+ *
+ * Returns: Null on success, or a pointer to an error message.
+ *
+ * Use: Parses out information about a curve. The string is either a
+ * standard curve name, or a curve info string.
+ */
+
+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_freeinfo@ --- *
+ *
+ * Arguments: @ec_info *ei@ = elliptic curve information block to free
+ *
+ * Returns: ---
+ *
+ * Use: Frees the information block.
+ */
+
+void ec_freeinfo(ec_info *ei)
+{
+ field *f;
+
+ EC_DESTROY(&ei->g);
+ MP_DROP(ei->r);
+ MP_DROP(ei->h);
+ f = ei->c->f; ec_destroycurve(ei->c); F_DESTROY(f);
+}
+
+/* --- @ec_checkinfo@ --- *
+ *
+ * Arguments: @const ec_info *ei@ = elliptic curve information block
+ *
+ * Returns: Null if OK, or pointer to error message.
+ *
+ * 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));
+}
+
+static const char *primecheck(const ec_info *ei, grand *gr)
+{
+ ec_curve *c = ei->c;
+ field *f = c->f;
+ int i;
+ mp *x, *y;
+ ec p;
+ int rc;
+
+ /* --- Check %$p$% is an odd prime --- */
+
+ if (!primep(f->m, gr)) return ("p not prime");
+
+ /* --- Check %$a$%, %$b$%, %$G_x$% and %$G_y$% are in %$[0, p)$% --- */
+
+ if (!primeeltp(c->a, f)) return ("a out of range");
+ if (!primeeltp(c->b, f)) return ("b out of range");
+ if (!primeeltp(ei->g.x, f)) return ("G_x out of range");
+ if (!primeeltp(ei->g.x, f)) return ("G_y out of range");
+
+ /* --- Check %$4 a^3 + 27 b^2 \not\equiv 0 \pmod{p}$% --- */
+
+ x = F_SQR(f, MP_NEW, c->a);
+ x = F_MUL(f, x, x, c->a);
+ x = F_QDL(f, x, x);
+ y = F_SQR(f, MP_NEW, c->b);
+ y = F_TPL(f, y, y);
+ y = F_TPL(f, y, y);
+ y = F_TPL(f, y, y);
+ x = F_ADD(f, x, x, y);
+ rc = F_ZEROP(f, x);
+ MP_DROP(x);
+ MP_DROP(y);
+ if (rc) return ("not an elliptic curve");
+
+ /* --- Check %$G \in E$% --- */
+
+ if (EC_ATINF(&ei->g)) return ("generator at infinity");
+ if (ec_check(c, &ei->g)) return ("generator not on curve");
+
+ /* --- 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");
+
+ /* --- Check %$h = \lfloor (\sqrt{p} + 1)^2/r \rlfoor$% --- *
+ *
+ * This seems to work with the approximate-sqrt in the library, but might
+ * not be so good in some cases. Throw in some extra significate figures
+ * for good measure.
+ */
+
+ x = mp_lsl(MP_NEW, f->m, 128);
+ x = mp_sqrt(x, x);
+ y = mp_lsl(MP_NEW, MP_ONE, 64);
+ x = mp_add(x, x, y);
+ x = mp_sqr(x, x);
+ mp_div(&x, 0, x, ei->r);
+ x = mp_lsr(x, x, 128);
+ rc = MP_EQ(x, ei->h);
+ MP_DROP(x);
+ MP_DROP(y);
+ if (!rc) return ("incorrect cofactor");
+
+ /* --- Check %$n G = O$% --- */
+
+ EC_CREATE(&p);
+ ec_mul(c, &p, &ei->g, ei->r);
+ rc = EC_ATINF(&p);
+ EC_DESTROY(&p);
+ if (!rc) return ("incorrect group order");
+
+ /* --- Check that %$p^B \not\equiv 1 \pmod{r}$% for %$1 \le B < 20$% --- *
+ *
+ * The spec says %$q$%, not %$p$%, but I think that's a misprint.
+ */
+
+ x = MP_NEW;
+ mp_div(0, &x, f->m, ei->r);
+ i = 20;
+ while (i) {
+ if (MP_EQ(x, MP_ONE)) break;
+ x = mp_mul(x, x, f->m);
+ mp_div(0, &x, x, ei->r);
+ i--;
+ }
+ MP_DROP(x);
+ if (i) return ("curve is weak");
+
+ /* --- Done --- */
+
+ return (0);
+}
+
+static const char *bincheck(const ec_info *ei, grand *gr)
+{
+ ec_curve *c = ei->c;
+ field *f = c->f;
+ int i;
+ mp *x, *y;
+ ec p;
+ int rc;
+
+ /* --- Check that %$p$% is irreducible --- */
+
+ if (!gf_irreduciblep(f->m)) return ("p not irreducible");
+
+ /* --- Check that %$a, b, G_x, G_y$% have degree less than %$p$% --- */
+
+ if (mp_bits(c->a) > f->nbits) return ("a out of range");
+ if (mp_bits(c->b) > f->nbits) return ("a out of range");
+ if (mp_bits(ei->g.x) > f->nbits) return ("G_x out of range");
+ if (mp_bits(ei->g.y) > f->nbits) return ("G_y out of range");
+
+ /* --- Check that %$b \ne 0$% --- */
+
+ if (F_ZEROP(f, c->b)) return ("b is zero");
+
+ /* --- Check that %$G \in E$% --- */
+
+ if (EC_ATINF(&ei->g)) return ("generator at infinity");
+ if (ec_check(c, &ei->g)) return ("generator not on curve");
+
+ /* --- 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");
+
+ /* --- Check %$h = \lfloor (\sqrt{2^m} + 1)^2/r \rlfoor$% --- *
+ *
+ * This seems to work with the approximate-sqrt in the library, but might
+ * not be so good in some cases. Throw in some extra significate figures
+ * for good measure.
+ */
+
+ x = mp_lsl(MP_NEW, MP_ONE, f->nbits + 128);
+ x = mp_sqrt(x, x);
+ y = mp_lsl(MP_NEW, MP_ONE, 64);
+ x = mp_add(x, x, y);
+ x = mp_sqr(x, x);
+ mp_div(&x, 0, x, ei->r);
+ x = mp_lsr(x, x, 128);
+ rc = MP_EQ(x, ei->h);
+ MP_DROP(x);
+ MP_DROP(y);
+ if (!rc) return ("incorrect cofactor");
+
+ /* --- Check %$n G = O$% --- */
+
+ EC_CREATE(&p);
+ ec_mul(c, &p, &ei->g, ei->r);
+ rc = EC_ATINF(&p);
+ EC_DESTROY(&p);
+ if (!rc) return ("incorrect group order");
+
+ /* --- Check %$2^{m B} \not\equiv 1 \pmod{r}$% for %$1 \le B < 20$% --- */
+
+ x = mp_lsl(MP_NEW, MP_ONE, f->nbits);
+ mp_div(0, &x, x, ei->r);
+ i = 20;
+ while (i) {
+ if (MP_EQ(x, MP_ONE)) break;
+ x = mp_mul(x, x, f->m);
+ mp_div(0, &x, x, ei->r);
+ i--;
+ }
+ MP_DROP(x);
+ if (i) return ("curve is weak");
+
+ /* --- Done --- */
+
+ return (0);
+}
+
+const char *ec_checkinfo(const ec_info *ei, grand *gr)
+{
+ switch (F_TYPE(ei->c->f)) {
+ case FTY_PRIME: return (primecheck(ei, gr)); break;
+ case FTY_BINARY: return (bincheck(ei, gr)); break;
+ }
+ return ("unknown curve type");
+}
+
+/*----- Test rig ----------------------------------------------------------*/
+
+#ifdef TEST_RIG
+
+#include "fibrand.h"
+
+int main(void)
+{
+ const ecentry *ee;
+ const char *e;
+ int ok = 1;
+ 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;
+ }
+ putchar('.');
+ fflush(stdout);
+ }
+ gr->ops->destroy(gr);
+ fputs(ok ? " ok\n" : " failed\n", stdout);
+ return (!ok);
+}
+
+#endif
+
+/*----- That's all, folks -------------------------------------------------*/
projects / u / mdw / catacomb / blobdiff