git.distorted.org.uk Git - u/mdw/catacomb/blob - mpmont-mexp.c

   1 /* -*-c-*-
   2  *
   3  * $Id: mpmont-mexp.c,v 1.8 2004/04/01 12:50:09 mdw Exp $
   4  *
   5  * Multiple simultaneous exponentiations
   6  *
   7  * (c) 1999 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: mpmont-mexp.c,v $
  33  * Revision 1.8  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  * Revision 1.7  2002/01/13 13:49:14  mdw
  41  * Make @const@-correct.
  42  *
  43  * Revision 1.6  2001/06/16 13:00:20  mdw
  44  * Use the generic exponentiation functions.
  45  *
  46  * Revision 1.5  2000/10/08 12:11:22  mdw
  47  * Use @MP_EQ@ instead of @MP_CMP@.
  48  *
  49  * Revision 1.4  2000/06/17 11:45:09  mdw
  50  * Major memory management overhaul.  Added arena support.  Use the secure
  51  * arena for secret integers.  Replace and improve the MP management macros
  52  * (e.g., replace MP_MODIFY by MP_DEST).
  53  *
  54  * Revision 1.3  1999/12/10 23:18:39  mdw
  55  * Change interface for suggested destinations.
  56  *
  57  * Revision 1.2  1999/11/21 11:35:10  mdw
  58  * Performance improvement: use @mp_sqr@ and @mpmont_reduce@ instead of
  59  * @mpmont_mul@ for squaring in exponentiation.
  60  *
  61  * Revision 1.1  1999/11/19 13:19:29  mdw
  62  * Simultaneous exponentiation support.
  63  *
  64  */
  65
  66 /*----- Header files ------------------------------------------------------*/
  67
  68 #include "mp.h"
  69 #include "mpmont.h"
  70
  71 #define EXP_WINSZ 3
  72 #include "mpmont-exp.h"
  73
  74 /*----- Main code ---------------------------------------------------------*/
  75
  76 /* --- @mpmont_mexpr@ --- *
  77  *
  78  * Arguments:   @mpmont *mm@ = pointer to Montgomery reduction context
  79  *              @mp *d@ = fake destination
  80  *              @const mp_expfactor *f@ = pointer to array of factors
  81  *              @size_t n@ = number of factors supplied
  82  *
  83  * Returns:     If the bases are %$g_0, g_1, \ldots, g_{n-1}$% and the
  84  *              exponents are %$e_0, e_1, \ldots, e_{n-1}$% then the result
  85  *              is:
  86  *
  87  *              %$g_0^{e_0} g_1^{e_1} \ldots g_{n-1}^{e_{n-1}} \bmod m$%
  88  *
  89  *              except that the %$g_i$% and result are in Montgomery form.
  90  */
  91
  92 static mp *mexpr(mpmont *mm, mp *d, mp_expfactor *f, size_t n)
  93 {
  94   mp *a = MP_COPY(mm->r);
  95   mp *spare = MP_NEW;
  96   mp *g = MP_NEW;
  97   size_t i;
  98
  99   for (i = 0; i < n; i++) {
 100     mp *t;
 101     if (f[i].exp->f & MP_BURN)
 102       spare = MP_NEWSEC;
 103     if (f[i].exp->f & MP_NEG) {
 104       t = mpmont_reduce(mm, f[i].base, f[i].base);
 105       mp_gcd(&g, 0, &t, mm->m, t);
 106       assert(MP_EQ(g, MP_ONE));
 107       f[i].base = mpmont_mul(mm, t, t, mm->r2);
 108     }
 109   }
 110   mp_drop(g);
 111   EXP_SIMUL(a, f, n);
 112   mp_drop(d);
 113   mp_drop(spare);
 114   for (i = 0; i < n; i++)
 115     MP_DROP(f[i].base);
 116   xfree(f);
 117   return (a);
 118 }
 119
 120 mp *mpmont_mexpr(mpmont *mm, mp *d, const mp_expfactor *f, size_t n)
 121 {
 122   mp_expfactor *ff = xmalloc(n * sizeof(mp_expfactor));
 123   size_t i;
 124
 125   for (i = 0; i < n; i++) {
 126     ff[i].base = MP_COPY(f[i].base);
 127     ff[i].exp = f[i].exp;
 128   }
 129   return (mexpr(mm, d, ff, n));
 130 }
 131
 132 /* --- @mpmont_mexp@ --- *
 133  *
 134  * Arguments:   @mpmont *mm@ = pointer to Montgomery reduction context
 135  *              @mp *d@ = fake destination
 136  *              @const mp_expfactor *f@ = pointer to array of factors
 137  *              @size_t n@ = number of factors supplied
 138  *
 139  * Returns:     Product of bases raised to exponents, all mod @m@.
 140  *
 141  * Use:         Convenient interface over @mpmont_mexpr@.
 142  */
 143
 144 mp *mpmont_mexp(mpmont *mm, mp *d, const mp_expfactor *f, size_t n)
 145 {
 146   mp_expfactor *ff = xmalloc(n * sizeof(mp_expfactor));
 147   size_t i;
 148
 149   for (i = 0; i < n; i++) {
 150     ff[i].base = mpmont_mul(mm, MP_NEW, f[i].base, mm->r2);
 151     ff[i].exp = f[i].exp;
 152   }
 153   d = mexpr(mm, d, ff, n);
 154   return (mpmont_reduce(mm, d, d));
 155 }
 156
 157 /*----- Test rig ----------------------------------------------------------*/
 158
 159 #ifdef TEST_RIG
 160
 161 #include <mLib/testrig.h>
 162
 163 static int verify(size_t n, dstr *v)
 164 {
 165   mp *m = *(mp **)v[0].buf;
 166   mp_expfactor *f = xmalloc(n * sizeof(*f));
 167   mp *r, *rr;
 168   size_t i, j;
 169   mpmont mm;
 170   int ok = 1;
 171
 172   j = 1;
 173   for (i = 0; i < n; i++) {
 174     f[i].base = *(mp **)v[j++].buf;
 175     f[i].exp = *(mp **)v[j++].buf;
 176   }
 177
 178   rr = *(mp **)v[j].buf;
 179   mpmont_create(&mm, m);
 180   r = mpmont_mexp(&mm, MP_NEW, f, n);
 181   if (!MP_EQ(r, rr)) {
 182     fputs("\n*** mexp failed\n", stderr);
 183     fputs("m = ", stderr); mp_writefile(m, stderr, 10);
 184     for (i = 0; i < n; i++) {
 185       fprintf(stderr, "\ng_%u = ", i);
 186       mp_writefile(f[i].base, stderr, 10);
 187       fprintf(stderr, "\ne_%u = ", i);
 188       mp_writefile(f[i].exp, stderr, 10);
 189     }
 190     fputs("\nr = ", stderr); mp_writefile(r, stderr, 10);
 191     fputs("\nR = ", stderr); mp_writefile(rr, stderr, 10);
 192     fputc('\n', stderr);
 193     ok = 0;
 194   }
 195
 196   for (i = 0; i < n; i++) {
 197     MP_DROP(f[i].base);
 198     MP_DROP(f[i].exp);
 199   }
 200   MP_DROP(m);
 201   MP_DROP(r);
 202   MP_DROP(rr);
 203   mpmont_destroy(&mm);
 204   assert(mparena_count(MPARENA_GLOBAL) == 0);
 205   return (ok);
 206 }
 207
 208 static int t1(dstr *v) { return verify(1, v); }
 209 static int t2(dstr *v) { return verify(2, v); }
 210 static int t3(dstr *v) { return verify(3, v); }
 211 static int t4(dstr *v) { return verify(4, v); }
 212 static int t5(dstr *v) { return verify(5, v); }
 213
 214 static test_chunk tests[] = {
 215   { "mexp-1", t1, { &type_mp,
 216                     &type_mp, &type_mp,
 217                     &type_mp, 0 } },
 218   { "mexp-2", t2, { &type_mp,
 219                     &type_mp, &type_mp,
 220                     &type_mp, &type_mp,
 221                     &type_mp, 0 } },
 222   { "mexp-3", t3, { &type_mp,
 223                     &type_mp, &type_mp,
 224                     &type_mp, &type_mp,
 225                     &type_mp, &type_mp,
 226                     &type_mp, 0 } },
 227   { "mexp-4", t4, { &type_mp,
 228                     &type_mp, &type_mp,
 229                     &type_mp, &type_mp,
 230                     &type_mp, &type_mp,
 231                     &type_mp, &type_mp,
 232                     &type_mp, 0 } },
 233   { "mexp-5", t5, { &type_mp,
 234                     &type_mp, &type_mp,
 235                     &type_mp, &type_mp,
 236                     &type_mp, &type_mp,
 237                     &type_mp, &type_mp,
 238                     &type_mp, &type_mp,
 239                     &type_mp, 0 } },
 240   { 0, 0, { 0 } }
 241 };
 242
 243 int main(int argc, char *argv[])
 244 {
 245   sub_init();
 246   test_run(argc, argv, tests, SRCDIR "/tests/mpmont");
 247   return (0);
 248 }
 249
 250 #endif
 251
 252 /*----- That's all, folks -------------------------------------------------*/