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

   1 /* -*-c-*-
   2  *
   3  * $Id$
   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 /*----- Header files ------------------------------------------------------*/
  31
  32 #include "ec.h"
  33 #include "ec-exp.h"
  34
  35 /*----- Main code ---------------------------------------------------------*/
  36
  37 /* --- @ec_imul@, @ec_mul@ --- *
  38  *
  39  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
  40  *              @ec *d@ = pointer to the destination point
  41  *              @const ec *p@ = pointer to the generator point
  42  *              @mp *n@ = integer multiplier
  43  *
  44  * Returns:     The destination @d@.
  45  *
  46  * Use:         Multiplies a point by a scalar, returning %$n p$%.  The
  47  *              @imul@ variant uses internal representations for argument
  48  *              and result.
  49  */
  50
  51 ec *ec_imul(ec_curve *c, ec *d, const ec *p, mp *n)
  52 {
  53   ec t = EC_INIT;
  54
  55   EC_COPY(&t, p);
  56   if (t.x && (n->f & MP_BURN))
  57     t.x->f |= MP_BURN;
  58   MP_SHRINK(n);
  59   EC_SETINF(d);
  60   if (MP_ZEROP(n))
  61     ;
  62   else {
  63     if (MP_NEGP(n))
  64       EC_NEG(c, &t, &t);
  65     if (MP_LEN(n) < EXP_THRESH)
  66       EXP_SIMPLE(*d, t, n);
  67     else
  68       EXP_WINDOW(*d, t, n);
  69   }
  70   EC_DESTROY(&t);
  71   return (d);
  72 }
  73
  74 ec *ec_mul(ec_curve *c, ec *d, const ec *p, mp *n)
  75 {
  76   EC_IN(c, d, p);
  77   ec_imul(c, d, d, n);
  78   return (EC_OUT(c, d, d));
  79 }
  80
  81 /* --- @ec_mmul@, @ec_immul@ --- *
  82  *
  83  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
  84  *              @ec *d@ = pointer to the destination point
  85  *              @const ec_mulfactor *f@ = pointer to vector of factors
  86  *              @size_t n@ = number of factors
  87  *
  88  * Returns:     The destination @d@.
  89  *
  90  * Use:         Does simultaneous point multiplication.  The @immul@ variant
  91  *              uses internal representations for arguments and result.
  92  */
  93
  94 #undef EXP_WINSZ
  95 #define EXP_WINSZ 3
  96
  97 static ec *immul(ec_curve *c, ec *d, ec_mulfactor *f, size_t n)
  98 {
  99   size_t i;
 100
 101   for (i = 0; i < n; i++) {
 102     MP_SHRINK(f[i].exp);
 103     if (MP_NEGP(f[i].exp))
 104       EC_NEG(c, &f[i].base, &f[i].base);
 105     if (f[i].base.x && f[i].exp->f & MP_BURN)
 106       f[i].base.x->f |= MP_BURN;
 107   }
 108   EC_SETINF(d);
 109   EXP_SIMUL(*d, f, n);
 110   for (i = 0; i < n; i++)
 111     EC_DESTROY(&f[i].base);
 112   xfree(f);
 113   return (d);
 114 }
 115
 116 ec *ec_immul(ec_curve *c, ec *d, const ec_mulfactor *f, size_t n)
 117 {
 118   ec_mulfactor *ff = xmalloc(n * sizeof(ec_mulfactor));
 119   size_t i;
 120
 121   for (i = 0; i < n; i++) {
 122     EC_CREATE(&ff[i].base);
 123     EC_COPY(&ff[i].base, &f[i].base);
 124     ff[i].exp = f[i].exp;
 125   }
 126   return (immul(c, d, ff, n));
 127 }
 128
 129 ec *ec_mmul(ec_curve *c, ec *d, const ec_mulfactor *f, size_t n)
 130 {
 131   ec_mulfactor *ff = xmalloc(n * sizeof(ec_mulfactor));
 132   size_t i;
 133
 134   for (i = 0; i < n; i++) {
 135     EC_CREATE(&ff[i].base);
 136     EC_IN(c, &ff[i].base, &f[i].base);
 137     ff[i].exp = f[i].exp;
 138   }
 139   immul(c, d, ff, n);
 140   return (EC_OUT(c, d, d));
 141 }
 142
 143 /*----- That's all, folks -------------------------------------------------*/