chiark - git - mdw - catacomb/blob - math/ec-exp.c

   1 /* -*-c-*-
   2  *
   3  * Point multiplication for elliptic curves
   4  *
   5  * (c) 2004 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of Catacomb.
  11  *
  12  * Catacomb is free software; you can redistribute it and/or modify
  13  * it under the terms of the GNU Library General Public License as
  14  * published by the Free Software Foundation; either version 2 of the
  15  * License, or (at your option) any later version.
  16  *
  17  * Catacomb is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20  * GNU Library General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU Library General Public
  23  * License along with Catacomb; if not, write to the Free
  24  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  25  * MA 02111-1307, USA.
  26  */
  27
  28 /*----- Header files ------------------------------------------------------*/
  29
  30 #include "ec.h"
  31 #include "ec-exp.h"
  32
  33 /*----- Main code ---------------------------------------------------------*/
  34
  35 /* --- @ec_imul@, @ec_mul@ --- *
  36  *
  37  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
  38  *              @ec *d@ = pointer to the destination point
  39  *              @const ec *p@ = pointer to the generator point
  40  *              @mp *n@ = integer multiplier
  41  *
  42  * Returns:     The destination @d@.
  43  *
  44  * Use:         Multiplies a point by a scalar, returning %$n p$%.  The
  45  *              @imul@ variant uses internal representations for argument
  46  *              and result.
  47  */
  48
  49 ec *ec_imul(ec_curve *c, ec *d, const ec *p, mp *n)
  50 {
  51   ec t = EC_INIT;
  52
  53   EC_COPY(&t, p);
  54   if (t.x && (n->f & MP_BURN))
  55     t.x->f |= MP_BURN;
  56   MP_SHRINK(n);
  57   EC_SETINF(d);
  58   if (MP_ZEROP(n))
  59     ;
  60   else {
  61     if (MP_NEGP(n))
  62       EC_NEG(c, &t, &t);
  63     if (MP_LEN(n) < EXP_THRESH)
  64       EXP_SIMPLE(*d, t, n);
  65     else
  66       EXP_WINDOW(*d, t, n);
  67   }
  68   EC_DESTROY(&t);
  69   return (d);
  70 }
  71
  72 ec *ec_mul(ec_curve *c, ec *d, const ec *p, mp *n)
  73 {
  74   EC_IN(c, d, p);
  75   ec_imul(c, d, d, n);
  76   return (EC_OUT(c, d, d));
  77 }
  78
  79 /* --- @ec_mmul@, @ec_immul@ --- *
  80  *
  81  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
  82  *              @ec *d@ = pointer to the destination point
  83  *              @const ec_mulfactor *f@ = pointer to vector of factors
  84  *              @size_t n@ = number of factors
  85  *
  86  * Returns:     The destination @d@.
  87  *
  88  * Use:         Does simultaneous point multiplication.  The @immul@ variant
  89  *              uses internal representations for arguments and result.
  90  */
  91
  92 #undef EXP_WINSZ
  93 #define EXP_WINSZ 3
  94
  95 static ec *immul(ec_curve *c, ec *d, ec_mulfactor *f, size_t n)
  96 {
  97   size_t i;
  98
  99   for (i = 0; i < n; i++) {
 100     MP_SHRINK(f[i].exp);
 101     if (MP_NEGP(f[i].exp))
 102       EC_NEG(c, &f[i].base, &f[i].base);
 103     if (f[i].base.x && f[i].exp->f & MP_BURN)
 104       f[i].base.x->f |= MP_BURN;
 105   }
 106   EC_SETINF(d);
 107   EXP_SIMUL(*d, f, n);
 108   for (i = 0; i < n; i++)
 109     EC_DESTROY(&f[i].base);
 110   xfree(f);
 111   return (d);
 112 }
 113
 114 ec *ec_immul(ec_curve *c, ec *d, const ec_mulfactor *f, size_t n)
 115 {
 116   ec_mulfactor *ff = xmalloc(n * sizeof(ec_mulfactor));
 117   size_t i;
 118
 119   for (i = 0; i < n; i++) {
 120     EC_CREATE(&ff[i].base);
 121     EC_COPY(&ff[i].base, &f[i].base);
 122     ff[i].exp = f[i].exp;
 123   }
 124   return (immul(c, d, ff, n));
 125 }
 126
 127 ec *ec_mmul(ec_curve *c, ec *d, const ec_mulfactor *f, size_t n)
 128 {
 129   ec_mulfactor *ff = xmalloc(n * sizeof(ec_mulfactor));
 130   size_t i;
 131
 132   for (i = 0; i < n; i++) {
 133     EC_CREATE(&ff[i].base);
 134     EC_IN(c, &ff[i].base, &f[i].base);
 135     ff[i].exp = f[i].exp;
 136   }
 137   immul(c, d, ff, n);
 138   return (EC_OUT(c, d, d));
 139 }
 140
 141 /*----- That's all, folks -------------------------------------------------*/