git.distorted.org.uk Git - u/mdw/catacomb/blob - ec-exp.c

   1 /* -*-c-*-
   2  *
   3  * $Id: ec-exp.c,v 1.1 2004/04/01 12:50:09 mdw Exp $
   4  *
   5  * Point multiplication for elliptic curves
   6  *
   7  * (c) 2004 Straylight/Edgeware
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  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.
  18  *
  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.
  23  *
  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
  30 /*----- Revision history --------------------------------------------------*
  31  *
  32  * $Log: ec-exp.c,v $
  33  * Revision 1.1  2004/04/01 12:50:09  mdw
  34  * Add cyclic group abstraction, with test code.  Separate off exponentation
  35  * functions for better static linking.  Fix a buttload of bugs on the way.
  36  * Generally ensure that negative exponents do inversion correctly.  Add
  37  * table of standard prime-field subgroups.  (Binary field subgroups are
  38  * currently unimplemented but easy to add if anyone ever finds a good one.)
  39  *
  40  */
  41
  42 /*----- Header files ------------------------------------------------------*/
  43
  44 #include "ec.h"
  45 #include "ec-exp.h"
  46
  47 /*----- Main code ---------------------------------------------------------*/
  48
  49 /* --- @ec_imul@, @ec_mul@ --- *
  50  *
  51  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
  52  *              @ec *d@ = pointer to the destination point
  53  *              @const ec *p@ = pointer to the generator point
  54  *              @mp *n@ = integer multiplier
  55  *
  56  * Returns:     The destination @d@.
  57  *
  58  * Use:         Multiplies a point by a scalar, returning %$n p$%.  The
  59  *              @imul@ variant uses internal representations for argument
  60  *              and result.
  61  */
  62
  63 ec *ec_imul(ec_curve *c, ec *d, const ec *p, mp *n)
  64 {
  65   ec t = EC_INIT;
  66
  67   EC_COPY(&t, p);
  68   if (t.x && (n->f & MP_BURN))
  69     t.x->f |= MP_BURN;
  70   MP_SHRINK(n);
  71   EC_SETINF(d);
  72   if (MP_LEN(n) == 0)
  73     ;
  74   else {
  75     if (n->f & MP_NEG)
  76       EC_NEG(c, &t, &t);
  77     if (MP_LEN(n) < EXP_THRESH)
  78       EXP_SIMPLE(*d, t, n);
  79     else
  80       EXP_WINDOW(*d, t, n);
  81   }
  82   EC_DESTROY(&t);
  83   return (d);
  84 }
  85
  86 ec *ec_mul(ec_curve *c, ec *d, const ec *p, mp *n)
  87 {
  88   EC_IN(c, d, p);
  89   ec_imul(c, d, d, n);
  90   return (EC_OUT(c, d, d));
  91 }
  92
  93 /* --- @ec_mmul@, @ec_immul@ --- *
  94  *
  95  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
  96  *              @ec *d@ = pointer to the destination point
  97  *              @const ec_mulfactor *f@ = pointer to vector of factors
  98  *              @size_t n@ = number of factors
  99  *
 100  * Returns:     The destination @d@.
 101  *
 102  * Use:         Does simultaneous point multiplication.  The @immul@ variant
 103  *              uses internal representations for arguments and result.
 104  */
 105
 106 #undef EXP_WINSZ
 107 #define EXP_WINSZ 3
 108
 109 static ec *immul(ec_curve *c, ec *d, ec_mulfactor *f, size_t n)
 110 {
 111   size_t i;
 112
 113   for (i = 0; i < n; i++) {
 114     MP_SHRINK(f[i].exp);
 115     if (f[i].exp->f & MP_NEG)
 116       EC_NEG(c, &f[i].base, &f[i].base);
 117     if (f[i].base.x && f[i].exp->f & MP_BURN)
 118       f[i].base.x->f |= MP_BURN;
 119   }
 120   EC_SETINF(d);
 121   EXP_SIMUL(*d, f, n);
 122   for (i = 0; i < n; i++)
 123     EC_DESTROY(&f[i].base);
 124   xfree(f);
 125   return (d);
 126 }
 127
 128 ec *ec_immul(ec_curve *c, ec *d, const ec_mulfactor *f, size_t n)
 129 {
 130   ec_mulfactor *ff = xmalloc(n * sizeof(ec_mulfactor));
 131   size_t i;
 132
 133   for (i = 0; i < n; i++) {
 134     EC_CREATE(&ff[i].base);
 135     EC_COPY(&ff[i].base, &f[i].base);
 136     ff[i].exp = f[i].exp;
 137   }
 138   return (immul(c, d, ff, n));
 139 }
 140
 141 ec *ec_mmul(ec_curve *c, ec *d, const ec_mulfactor *f, size_t n)
 142 {
 143   ec_mulfactor *ff = xmalloc(n * sizeof(ec_mulfactor));
 144   size_t i;
 145
 146   for (i = 0; i < n; i++) {
 147     EC_CREATE(&ff[i].base);
 148     EC_IN(c, &ff[i].base, &f[i].base);
 149     ff[i].exp = f[i].exp;
 150   }
 151   immul(c, d, ff, n);
 152   return (EC_OUT(c, d, d));
 153 }
 154
 155 /*----- That's all, folks -------------------------------------------------*/