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

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