From: mdw Date: Sat, 16 Oct 2004 22:33:47 +0000 (+0000) Subject: Add utility for computing conversion factors for ONBs. Fix up elliptic curve X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/commitdiff_plain/389d822217b802003674d2085b3b902cbe13cf25 Add utility for computing conversion factors for ONBs. Fix up elliptic curve entry programs to accept binnorm fields. Add some ONB curves from X9.62 to the list. Also, for binary fields, ensure that the degree is prime in ec_checkinfo: otherwise the GHS attack is applicable. --- diff --git a/ec-info.c b/ec-info.c index 6b5e08e..bf9607c 100644 --- a/ec-info.c +++ b/ec-info.c @@ -34,6 +34,7 @@ #include "gf.h" #include "pgen.h" #include "mprand.h" +#include "mpint.h" #include "rabin.h" /*----- Main code ---------------------------------------------------------*/ @@ -435,6 +436,13 @@ static const char *bincheck(const ec_info *ei, grand *gr) 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"); diff --git a/ectab.in b/ectab.in index cfe3e00..de594e1 100644 --- a/ectab.in +++ b/ectab.in @@ -330,8 +330,16 @@ curve ansi-c2tnb191v2 binpoly h 4 gx 0x3809b2b7cc1b28cc5a87926aad83fd28789e81e2c9e3bf10 gy 0x17434386626d14f3dbf01760d9213a3e1cf37aec437d668a -# ansi-c2tnb191v3 has an unacceptable cofactor -# ansi-c2onb191v{4,5} don't include conversion factors +# ansi-c2tnb191v3 and ansi-c2onb191v2 have unacceptable cofactor +curve ansi-c2onb191v1 binnorm + p 0x800000000000000000000000000000000000000000000201 + beta 0x19c409a7f85383bf0ef72b097a5c7398013a2dba6269292d + a 0x65903e04e1e4924253e26a3c9ac28c758bd8184a3fb680e8 + b 0x54678621b190cfce282ade219d5b3a065e3f4b3ffdebb29b + r 0x4000000000000000000000009cf2d6e3901dac4c32eec65d + h 2 + gx 0x5a2c69a32e8638e51ccefaad05350a978457cb5fb6df994a + gy 0x0f32fe0fa0e902f19b17d363c269f4f5cfe8087618569954 # ansi-c2pnb208v1 has an unacceptable cofactor; and 208 isn't prime anyway @@ -343,8 +351,16 @@ curve ansi-c2tnb239v1 binpoly h 4 gx 0x57927098fa932e7c0a96d3fd5b706ef7e5f5c156e16b7e7c86038552e91d gy 0x61d8ee5077c33fecf6f1a16b268de469c3c7744ea9a971649fc7a9616305 -# ansi-c2tnb239v{2,3} have unacceptable cofactors -# ansi-c2onb239v{4,5} don't include conversion factors +# ansi-c2tnb239v{2,3} and ansi-c2onb239v2 have unacceptable cofactors +curve ansi-c2onb239v1 binnorm + p 0x800000000000000000000000000000000000000000000000001000000001 + beta 0x3b5ce9846911b248f9347018a7ac8cce3662cee952ba45becd02d4b903ec + a 0x182dd45f5d470239b8983fea47b8b292641c57f9bf84baecde8bb3adce30 + b 0x147a9c1d4c2ce9be5d34ec02797f76667ebad5a3f93fa2a524bfde91ef28 + r 0x200000000000000000000000000000474f7e69f42fe430931d0b455aae8b + h 4 + gx 0x4912ad657f1d1c6b32edb9942c95e226b06fb012cd40fdea0d72197c8104 + gy 0x01f1fbc3d21168fd3f66c441c2b5c6cfdcd9ed3e13646b7a4db9a3b0c286 # ansi-c2pnb272w1 has an unacceptable cofactor; and 272 isn't prime anyway @@ -434,18 +450,10 @@ alias ansip521r1 secp521r1 #----- Curves from RFC2414 (Oakley) ----------------------------------------- # -# oakley155 has too large a cofactor -# oakley185's group has composite order; we double the generator to -# produce a group of composite order - -curve oakley185 binpoly - p 0x020000000000000000000000000000200000000000000001 - a 0 - b 0x1ee9 - r 0x007ffffffffffffffffffffff6fcbe226dcf92105d7e53af - h 4 - gx 0x1bd555555555555555555555555554e8000000000000158 - gy 0x14e999999999999999999999999998d7000000000001fe6 +# The Oakley curves are not good: +# oakley155 has too large a cofactor +# oakley185's field has composite degree +# Hence, we include neither here. #----- NIST curves from FIPS186-2 ------------------------------------------- # diff --git a/utils/ecentry-prettify.pl b/utils/ecentry-prettify.pl index 3b72053..ab9b3ed 100644 --- a/utils/ecentry-prettify.pl +++ b/utils/ecentry-prettify.pl @@ -23,6 +23,7 @@ my $name = shift; my $kind = shift; my $p = gather("p"); +my $beta = ($kind eq "binnorm") ? "0x".gather("beta") : ""; my $a = gather("a"); my $b = gather("b"); my $r = gather("r"); @@ -31,4 +32,6 @@ my $g = gather("g"); print "curve $name $kind\n"; $p = "0x".$p if $kind =~ /bin/; -system "./ecptd", "$kind $p $CTYPE{$kind} 0x$a 0x$b", "0x$r", $h, $g; +my @l = ("./ecptd", "$kind $p $beta $CTYPE{$kind} 0x$a 0x$b", "0x$r", $h, $g); +# print join(" ", @l), "\n"; +system @l; diff --git a/utils/ecptdecompress.c b/utils/ecptdecompress.c index dcfdcbd..09e1f88 100644 --- a/utils/ecptdecompress.c +++ b/utils/ecptdecompress.c @@ -9,6 +9,7 @@ #include "ec.h" #include "mp.h" #include "rand.h" +#include "field-guts.h" static void puthex(const char *name, mp *x, size_t n) { @@ -42,6 +43,7 @@ int main(int argc, char *argv[]) size_t n; octet *p; mp *x, *y = 0, *yy = 0; + mp *t = MP_NEW; const char *err; qd.p = argv[1]; @@ -77,7 +79,7 @@ int main(int argc, char *argv[]) y = mp_loadb(MP_NEW, p + n + 1, n); } if (p[0] & 0x02) { - if (!EC_FIND(c, &pt, x)) { + if (!ec_find(c, &pt, x)) { fprintf(stderr, "no matching y\n"); exit(1); } @@ -85,26 +87,30 @@ int main(int argc, char *argv[]) ec_destroy(&pt); switch (F_TYPE(c->f)) { case FTY_PRIME: - if (!MP_ISODD(yy) != !(p[0] & 1)) + if (!MP_ODDP(yy) != !(p[0] & 1)) yy = mp_sub(yy, c->f->m, yy); break; case FTY_BINARY: - if (MP_ISZERO(x)) + if (MP_ZEROP(x)) yy = F_SQRT(c->f, MP_NEW, c->b); else { - mp *xx = F_SQR(c->f, MP_NEW, x); + mp *xin = F_IN(c->f, MP_NEW, x); + mp *xx = F_SQR(c->f, MP_NEW, xin); mp *b = F_MUL(c->f, MP_NEW, xx, c->a); - mp *xxx = F_MUL(c->f, MP_NEW, xx, x); + mp *xxx = F_MUL(c->f, MP_NEW, xx, xin); b = F_ADD(c->f, b, b, xxx); b = F_ADD(c->f, b, b, c->b); xx = F_INV(c->f, xx, xx); b = F_MUL(c->f, b, b, xx); mp_drop(xxx); - mp_drop(xx); yy = F_QUADSOLVE(c->f, MP_NEW, b); - if (!MP_ISODD(yy) != !(p[0] & 1)) - yy = mp_add(yy, yy, MP_ONE); - yy = F_MUL(c->f, yy, yy, x); + xx = F_OUT(c->f, xx, yy); + if (!MP_ODDP(xx) != !(p[0] & 1)) + yy = gf_add(yy, yy, MP_ONE); + yy = F_MUL(c->f, yy, yy, xin); + yy = F_OUT(c->f, yy, yy); + mp_drop(xin); + mp_drop(xx); } break; default: @@ -125,13 +131,18 @@ int main(int argc, char *argv[]) exit(0); } puthex("p", ei.c->f->m, 0); - puthex("a", ei.c->a, c->f->noctets); - puthex("b", ei.c->b, c->f->noctets); + if (strcmp(F_NAME(ei.c->f), "binnorm") == 0) { + fctx_binnorm *fc = (fctx_binnorm *)ei.c->f; + puthex("beta", fc->ntop.r[fc->ntop.n - 1], c->f->noctets); + } + t = F_OUT(ei.c->f, t, ei.c->a); puthex("a", t, c->f->noctets); + t = F_OUT(ei.c->f, t, ei.c->b); puthex("b", t, c->f->noctets); puthex("r", ei.r, c->f->noctets); printf(" h "); mp_writefile(ei.h, stdout, 10); putchar('\n'); puthex("gx", ei.g.x, c->f->noctets); puthex("gy", ei.g.y, c->f->noctets); ec_freeinfo(&ei); + mp_drop(t); dstr_destroy(&d); return (0); } diff --git a/utils/fnb.c b/utils/fnb.c new file mode 100644 index 0000000..8b7c1ab --- /dev/null +++ b/utils/fnb.c @@ -0,0 +1,482 @@ +#include +#include + +#include + +#include "field.h" +#include "gf.h" +#include "mptext.h" +#include "fibrand.h" +#include "mprand.h" +#include "gfn.h" + +/*----- Polynomials over finite fields ------------------------------------*/ + +typedef struct poly { + unsigned sz, len; + mp **v; +} poly; + +#define POLY_INIT { 0, 0, 0 } + +#define POLY_ZEROP(p) (!(p)->len) +#define POLY_CONSTANTP(p) ((p)->len == 1) +#define POLY_DEGREE(p) ((p)->len - 1) + +void poly_free(poly *p) +{ + unsigned i; + + for (i = 0; i < p->sz; i++) + MP_DROP(p->v[i]); + xfree(p->v); p->v = 0; + p->sz = p->len = 0; +} + +void poly_ensure(field *f, poly *p, unsigned sz) +{ + mp **x; + unsigned i; + unsigned n; + + if (p->sz >= sz) + return; + n = p->sz; if (!n) n = 2; do n <<= 1; while (n < sz); + x = xmalloc(n * sizeof(mp *)); + for (i = 0; i < p->sz; i++) + x[i] = p->v[i]; + for (; i < n; i++) + x[i] = MP_COPY(f->zero); + xfree(p->v); + p->v = x; + p->sz = n; +} + +void poly_fix(field *f, poly *p, unsigned n) +{ + while (n && F_ZEROP(f, p->v[n - 1])) + n--; + p->len = n; +} + +#define MAX(a, b) ((a) > (b) ? (a) : (b)) + +static void putmphex(field *f, const char *name, mp *x) +{ + mp *z; + + printf("%s = 0x", name); + z = F_OUT(f, MP_NEW, x); + mp_writefile(z, stdout, 16); + MP_DROP(z); + printf("\n"); +} + +void poly_dump(field *f, const char *name, poly *p) +{ + unsigned i; + mp *z = MP_NEW; + + printf("%s = (", name); + for (i = p->len; i--; ) { + printf("0x"); + z = F_OUT(f, z, p->v[i]); + mp_writefile(z, stdout, 16); + if (i) printf(", "); + } + mp_drop(z); + printf(")\n"); +} + +void poly_add(field *f, poly *d, poly *x, poly *y) +{ + unsigned i; + unsigned n = MAX(x->len, y->len); + +/* poly_dump(f, "add x", x); */ +/* poly_dump(f, "add y", y); */ + poly_ensure(f, d, n); + for (i = 0; i < n; i++) { + mp *a = (i < x->len) ? x->v[i] : f->zero; + mp *b = (i < y->len) ? y->v[i] : f->zero; + d->v[i] = F_ADD(f, d->v[i], a, b); + } + poly_fix(f, d, n); +/* poly_dump(f, "add d", d); */ +} + +void poly_sub(field *f, poly *d, poly *x, poly *y) +{ + unsigned i; + unsigned n = MAX(x->len, y->len); + +/* poly_dump(f, "sub x", x); */ +/* poly_dump(f, "sub y", y); */ + poly_ensure(f, d, n); + for (i = 0; i < n; i++) { + mp *a = (i < x->len) ? x->v[i] : f->zero; + mp *b = (i < y->len) ? y->v[i] : f->zero; + d->v[i] = F_SUB(f, d->v[i], a, b); + } + poly_fix(f, d, n); +/* poly_dump(f, "sub d", d); */ +} + +static void omuladd(field *f, poly *x, poly *y, mp *z, unsigned o) +{ + unsigned i; + unsigned n = MAX(x->len, y->len + o); + mp *t = MP_NEW; + +/* poly_dump(f, "omuladd x", x); */ +/* poly_dump(f, "omuladd y", y); */ +/* putmphex(f, "omuladd z", z); */ +/* printf("omuladd o = %u\n", o); */ + poly_ensure(f, x, n); + for (i = o; i < n; i++) { + if (i < y->len + o) { + mp *a = (i < x->len) ? x->v[i] : f->zero; + t = F_MUL(f, t, y->v[i - o], z); + x->v[i] = F_ADD(f, x->v[i], a, t); + } + } + mp_drop(t); + poly_fix(f, x, n); +/* poly_dump(f, "omuladd d", x); */ +} + +static void omulsub(field *f, poly *x, poly *y, mp *z, unsigned o) +{ + unsigned i; + unsigned n = MAX(x->len, y->len + o); + mp *t = MP_NEW; + +/* poly_dump(f, "omulsub x", x); */ +/* poly_dump(f, "omulsub y", y); */ +/* putmphex(f, "omulsub z", z); */ +/* printf("omulsub o = %u\n", o); */ + poly_ensure(f, x, n); + for (i = o; i < n; i++) { + if (i < y->len + o) { + mp *a = (i < x->len) ? x->v[i] : f->zero; + t = F_MUL(f, t, y->v[i - o], z); + x->v[i] = F_SUB(f, x->v[i], a, t); + } + } + mp_drop(t); + poly_fix(f, x, n); +/* poly_dump(f, "omulsub d", x); */ +} + +void poly_mul(field *f, poly *d, poly *x, poly *y) +{ + poly dd = POLY_INIT; + unsigned i; + +/* poly_dump(f, "mul x", x); */ +/* poly_dump(f, "mul y", y); */ + poly_ensure(f, &dd, x->len + y->len); + for (i = 0; i < y->len; i++) { + if (!F_ZEROP(f, y->v[i])) + omuladd(f, &dd, x, y->v[i], i); + } + poly_free(d); + *d = dd; +/* poly_dump(f, "mul d", d); */ +} + +void poly_copy(field *f, poly *d, poly *p) +{ + unsigned i; + + poly_ensure(f, d, p->len); + for (i = 0; i < p->len; i++) { + MP_DROP(d->v[i]); + d->v[i] = MP_COPY(p->v[i]); + } + d->len = p->len; +} + +void poly_div(field *f, poly *q, poly *r, poly *x, poly *y) +{ + poly qq = POLY_INIT, rr = POLY_INIT; + mp *i = MP_NEW; + mp *z = MP_NEW; + unsigned j; + unsigned o, oo = 0; + +/* poly_dump(f, "div x", x); */ +/* poly_dump(f, "div y", y); */ + assert(y->len); + i = F_INV(f, MP_NEW, y->v[y->len - 1]); + poly_copy(f, &rr, x); + if (rr.len >= y->len) { + o = oo = rr.len - y->len + 1; + j = rr.len; + if (q) poly_ensure(f, &qq, o); + while (o) { + o--; j--; + if (!F_ZEROP(f, rr.v[j])) { + z = F_MUL(f, z, rr.v[j], i); + if (q) qq.v[o] = MP_COPY(z); + omulsub(f, &rr, y, z, o); + } + } + } + if (q) { + poly_fix(f, &qq, oo); + poly_free(q); + *q = qq; +/* poly_dump(f, "div q", q); */ + } +/* poly_dump(f, "div r", &rr); */ + if (!r) + poly_free(&rr); + else { + poly_free(r); + *r = rr; + } + mp_drop(i); + mp_drop(z); +} + +void poly_monic(field *f, poly *d, poly *p) +{ + mp *z; + unsigned i, n; + + assert(p->len); + n = p->len; +/* poly_dump(f, "monic p", p); */ + poly_ensure(f, d, n); + z = F_INV(f, MP_NEW, p->v[n - 1]); + for (i = 0; i < n; i++) + d->v[i] = F_MUL(f, d->v[i], p->v[i], z); + poly_fix(f, d, n); +/* poly_dump(f, "monic d", d); */ + mp_drop(z); +} + +void poly_gcd(field *f, poly *g, poly *x, poly *y) +{ + poly uu = POLY_INIT, vv = POLY_INIT, rr = POLY_INIT; + poly *u = &uu, *v = &vv, *r = &rr; + poly *t; + +/* poly_dump(f, "gcd x", x); */ +/* poly_dump(f, "gcd y", y); */ + poly_copy(f, u, x); poly_copy(f, v, y); + if (u->len < v->len) { t = u; u = v; v = t; } + while (!POLY_ZEROP(v)) { + poly_div(f, 0, r, u, v); + t = u; u = v; v = r; r = t; + } + poly_monic(f, g, u); + poly_free(u); + poly_free(v); + poly_free(r); +/* poly_dump(f, "gcd g", g); */ +} + +mp *poly_solve(field *f, mp *d, mp *p, grand *r) +{ + poly g = POLY_INIT; + poly ut = POLY_INIT; + poly c = POLY_INIT; + poly h = POLY_INIT; + mp *z; + unsigned m = f->nbits; + unsigned i; + + poly_ensure(f, &g, m + 1); + for (i = 0; i <= m; i++) + g.v[i] = mp_testbit(p, i) ? MP_COPY(f->one) : MP_COPY(f->zero); + poly_fix(f, &g, m + 1); + poly_ensure(f, &ut, 2); + while (POLY_DEGREE(&g) > 1) { + ut.v[1] = mprand(ut.v[1], m, r, 0); + poly_fix(f, &ut, 2); + poly_copy(f, &c, &ut); +/* poly_dump(f, "c-in", &c); */ + + for (i = 1; i < m; i++) { + poly_mul(f, &c, &c, &c); + poly_add(f, &c, &c, &ut); + poly_div(f, 0, &c, &c, &g); +/* putchar('.'); fflush(stdout); */ + } +/* poly_dump(f, "c-out", &c); */ + poly_gcd(f, &h, &c, &g); +/* poly_dump(f, "h", &h); */ + if (POLY_CONSTANTP(&h) || POLY_DEGREE(&h) == POLY_DEGREE(&g)) + continue; + if (2 * POLY_DEGREE(&h) > POLY_DEGREE(&g)) + poly_div(f, &g, 0, &g, &h); + else + poly_copy(f, &g, &h); + } + z = MP_COPY(g.v[0]); + poly_free(&g); + poly_free(&ut); + poly_free(&c); + poly_free(&h); + mp_drop(d); + return (z); +} + +/*----- Other stuff -------------------------------------------------------*/ + +static int primep(unsigned x) +{ + unsigned i; + + for (i = 2; i*i < x; i++) { + if (x%i == 0) + return (0); + } + return (1); +} + +static unsigned gcd(unsigned u, unsigned v) +{ + unsigned r; + + if (u < v) { r = u; u = v; v = r; } + for (;;) { + r = u%v; + if (!r) return (v); + u = v; v = r; + } +} + +static int onbtype(unsigned m) +{ + unsigned t; + unsigned p, h; + unsigned k, x, d; + + if (m%8 == 0) + return (0); + for (t = 1; t <= 2; t++) { + p = t*m + 1; + if (!primep(p)) + continue; + for (x = 2, k = 1; x != 1; x = (2*x)%p, k++); + h = t*m/k; + d = gcd(h, m); + if (d == 1) + return (t); + } + return (0); +} + +static mp *fieldpoly(unsigned m, int t) +{ + mp *p, *q, *r, *z; + unsigned i; + + switch (t) { + case 1: + p = MP_ZERO; + for (i = 0; i <= m; i++) + p = mp_setbit(p, p, i); + break; + case 2: + q = MP_ONE; + p = MP_THREE; + r = MP_NEW; + for (i = 1; i < m; i++) { + r = mp_lsl(r, p, 1); + r = mp_xor(r, r, q); + z = r; r = q; q = p; p = z; + } + mp_drop(q); + mp_drop(r); + break; + default: + abort(); + } + return (p); +} + +static int dofip(unsigned m, mp **p, unsigned n, unsigned x) +{ + unsigned i; + + for (i = n + 1; i < x; i++) { + *p = mp_setbit(*p, *p, i); + if (n ? dofip(m, p, n - 1, i) : gf_irreduciblep(*p)) + return (1); + *p = mp_clearbit(*p, *p, i); + } + return (0); +} + +static mp *fip(unsigned m) +{ + mp *p = MP_ONE; + unsigned n; + + p = mp_setbit(p, p, m); + n = 0; + while (!dofip(m, &p, n, m)) + n += 2; + return (p); +} + +static mp *fnb(mp *p) +{ + unsigned t; + field *f; + grand *r = fibrand_create(0); + mp *q, *x; + unsigned m = mp_bits(p) - 1; + + if ((t = onbtype(m)) == 0) + return (0); + f = field_binpoly(p); + q = fieldpoly(m, t); + x = poly_solve(f, MP_NEW, q, r); + MP_DROP(q); + F_DESTROY(f); + return (x); +} + +int main(int argc, char *argv[]) +{ + int m = atoi(argv[1]); + int i; + mp *p; + mp *beta; + + if (!argv[2]) + p = fip(m); + else { + p = MP_ONE; + p = mp_setbit(p, p, m); + for (i = 2; i < argc; i++) + p = mp_setbit(p, p, atoi(argv[i])); + } + if (!gf_irreduciblep(p)) { + printf("not irreducible\n"); + return (1); + } + + MP_PRINTX("p", p); + for (i = m + 1; i--; ) { + if (mp_testbit(p, i)) + printf("%u ", i); + } + putchar('\n'); + + beta = fnb(p); + if (!beta) + printf("no onb\n"); + else + MP_PRINTX("beta", beta); + + mp_drop(p); + mp_drop(beta); + assert(mparena_count(MPARENA_GLOBAL) == 0); + return (0); +}