From: mdw Date: Tue, 26 Oct 2004 23:56:36 +0000 (+0000) Subject: Field exponentiation. Add field size to field structure. Make check X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/commitdiff_plain/1d7857e79cfb9d5b41fe13935b0a0bf68f6049f5 Field exponentiation. Add field size to field structure. Make check failure nonfatal in point decompression utility. --- diff --git a/f-binpoly.c b/f-binpoly.c index 23d9984..2d2221c 100644 --- a/f-binpoly.c +++ b/f-binpoly.c @@ -41,7 +41,7 @@ static void fdestroy(field *ff) { fctx_binpoly *f = (fctx_binpoly *)ff; - gfreduce_destroy(&f->r); + gfreduce_destroy(&f->r); MP_DROP(f->f.q); DESTROY(f); } @@ -114,6 +114,7 @@ field *field_binpoly(mp *p) f->f.noctets = (f->f.nbits + 7) >> 3; gfreduce_create(&f->r, p); f->f.m = f->r.p; + f->f.q = mp_lsl(MP_NEW, MP_ONE, f->f.nbits); return (&f->f); } @@ -123,7 +124,7 @@ field *field_binpoly(mp *p) static void fndestroy(field *ff) { fctx_binnorm *f = (fctx_binnorm *)ff; gfreduce_destroy(&f->f.r); - gfn_destroy(&f->ntop); gfn_destroy(&f->pton); + gfn_destroy(&f->ntop); gfn_destroy(&f->pton); MP_DROP(f->f.f.q); DESTROY(f); } @@ -175,6 +176,7 @@ field *field_binnorm(mp *p, mp *beta) f->f.f.noctets = (f->f.f.nbits + 7) >> 3; gfreduce_create(&f->f.r, p); f->f.f.m = f->f.r.p; + f->f.f.q = mp_lsl(MP_NEW, MP_ONE, f->f.f.nbits); gfn_create(p, beta, &f->ntop, &f->pton); return (&f->f.f); } diff --git a/f-prime.c b/f-prime.c index 9b1ceb6..b1c4367 100644 --- a/f-prime.c +++ b/f-prime.c @@ -170,6 +170,7 @@ field *field_prime(mp *p) f->f.m = f->mm.m; f->f.nbits = mp_bits(p); f->f.noctets = (f->f.nbits + 7) >> 3; + f->f.q = f->mm.m; return (&f->f); } diff --git a/field-exp.c b/field-exp.c new file mode 100644 index 0000000..fe3e8ce --- /dev/null +++ b/field-exp.c @@ -0,0 +1,73 @@ +/* -*-c-*- + * + * $Id$ + * + * Exponentiation in finite fields + * + * (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. + */ + +/*----- Header files ------------------------------------------------------*/ + +#include "field.h" +#include "field-exp.h" + +/*----- Main code ---------------------------------------------------------*/ + +/* --- @field_exp@ --- * + * + * Arguments: @field *f@ = pointer to field + * @mp *d@ = fake destination + * @mp *a@ = base + * @mp *e@ = exponent + * + * Returns: Result, %$a^e$%. + * + * Use: Exponentiation in a finite field. Note that all quantities + * are in internal format. + */ + +mp *field_exp(field *f, mp *d, mp *a, mp *e) +{ + mp *x = MP_COPY(f->one); + mp *spare = (e->f & MP_BURN) ? MP_NEWSEC : MP_NEW; + + MP_COPY(a); + MP_SHRINK(e); + if (MP_ZEROP(e)) + ; + else { + if (MP_NEGP(e)) + a = F_INV(f, a, a); + if (MP_LEN(e) < EXP_THRESH) + EXP_SIMPLE(x, a, e); + else + EXP_WINDOW(x, a, e); + } + mp_drop(d); + mp_drop(spare); + mp_drop(a); + return (x); +} + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/field-exp.h b/field-exp.h new file mode 100644 index 0000000..5a32356 --- /dev/null +++ b/field-exp.h @@ -0,0 +1,59 @@ +/* -*-c-*- + * + * $Id$ + * + * Exponentiation in finite fields + * + * (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. + */ + +#ifndef CATACOMB_FIELD_EXP_H +#define CATACOMB_FIELD_EXP_H + +#ifdef __cplusplus + extern "C" { +#endif + +/*----- Exponentiation definitions ----------------------------------------*/ + +#define EXP_TYPE mp * + +#define EXP_COPY(d, x) d = MP_COPY(x) +#define EXP_DROP(x) MP_DROP(x) + +#define EXP_MUL(a, x) a = F_MUL(f, a, a, x) +#define EXP_SQR(a) a = F_SQR(f, a, a) +#define EXP_FIX(x) + +#define EXP_SETMUL(d, x, y) d = F_MUL(f, MP_NEW, x, y) +#define EXP_SETSQR(d, x) d = F_SQR(f, MP_NEW, x) + +#include "exp.h" + +/*----- That's all, folks -------------------------------------------------*/ + +#ifdef __cplusplus + } +#endif + +#endif diff --git a/field.h b/field.h index 5790284..4164bce 100644 --- a/field.h +++ b/field.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: field.h,v 1.11 2004/04/08 01:36:15 mdw Exp $ + * $Id$ * * Definitions for field arithmetic * @@ -56,6 +56,7 @@ typedef struct field { mp *m; /* Modulus (prime and binary) */ unsigned long nbits; /* Length of field element in bits */ size_t noctets; /* Length of element in octets */ + mp *q; /* Number of elements in field */ } field; enum { @@ -170,6 +171,25 @@ extern int field_samep(field */*f*/, field */*g*/); extern int field_stdsamep(field */*f*/, field */*g*/); +/*----- Arithmetic --------------------------------------------------------*/ + +/* --- @field_exp@ --- * + * + * Arguments: @field *f@ = pointer to field + * @mp *d@ = fake destination + * @mp *a@ = base + * @mp *e@ = exponent + * + * Returns: Result, %$a^e$%. + * + * Use: Exponentiation in a finite field. Note that all quantities + * are in internal format. This is a generic implementation + * suitable for use with all fields and is not intended to be + * optimal. + */ + +extern mp *field_exp(field */*f*/, mp */*d*/, mp */*a*/, mp */*e*/); + /*----- Creating fields ---------------------------------------------------*/ /* --- @field_prime@ --- * diff --git a/utils/ecptdecompress.c b/utils/ecptdecompress.c index 09e1f88..e438696 100644 --- a/utils/ecptdecompress.c +++ b/utils/ecptdecompress.c @@ -126,10 +126,8 @@ int main(int argc, char *argv[]) mp_drop(y); mp_drop(yy); } - if ((err = ec_checkinfo(&ei, &rand_global)) != 0) { + if ((err = ec_checkinfo(&ei, &rand_global)) != 0) fprintf(stderr, "bad curve: %s\n", err); - exit(0); - } puthex("p", ei.c->f->m, 0); if (strcmp(F_NAME(ei.c->f), "binnorm") == 0) { fctx_binnorm *fc = (fctx_binnorm *)ei.c->f;