contrib/gmp/mpn/generic/powm_sec.c

   1 /* mpn_powm_sec -- Compute R = U^E mod M.  Safe variant, not leaking time info.
   2
   3 Copyright 2007, 2008, 2009 Free Software Foundation, Inc.
   4
   5 This file is part of the GNU MP Library.
   6
   7 The GNU MP Library is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU Lesser General Public License as published by
   9 the Free Software Foundation; either version 3 of the License, or (at your
  10 option) any later version.
  11
  12 The GNU MP Library is distributed in the hope that it will be useful, but
  13 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  14 or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  15 License for more details.
  16
  17 You should have received a copy of the GNU Lesser General Public License
  18 along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
  19
  20
  21 /*
  22   BASIC ALGORITHM, Compute b^e mod n, where n is odd.
  23
  24   1. w <- b
  25
  26   2. While w^2 < n (and there are more bits in e)
  27        w <- power left-to-right base-2 without reduction
  28
  29   3. t <- (B^n * b) / n                Convert to REDC form
  30
  31   4. Compute power table of e-dependent size
  32
  33   5. While there are more bits in e
  34        w <- power left-to-right base-k with reduction
  35
  36
  37   TODO:
  38
  39    * Make getbits a macro, thereby allowing it to update the index operand.
  40      That will simplify the code using getbits.  (Perhaps make getbits' sibling
  41      getbit then have similar form, for symmetry.)
  42
  43    * Write an itch function.
  44
  45    * Choose window size without looping.  (Superoptimize or think(tm).)
  46
  47    * Make it sub-quadratic.
  48
  49    * Call new division functions, not mpn_tdiv_qr.
  50
  51    * Is redc obsolete with improved SB division?
  52
  53    * Consider special code for one-limb M.
  54
  55    * Handle even M (in mpz_powm_sec) with two modexps and CRT.
  56 */
  57
  58 #include "gmp.h"
  59 #include "gmp-impl.h"
  60 #include "longlong.h"
  61
  62 #define WANT_CACHE_SECURITY 1
  63
  64
  65 #define getbit(p,bi) \
  66   ((p[(bi - 1) / GMP_LIMB_BITS] >> (bi - 1) % GMP_LIMB_BITS) & 1)
  67
  68 static inline mp_limb_t
  69 getbits (const mp_limb_t *p, unsigned long bi, int nbits)
  70 {
  71   int nbits_in_r;
  72   mp_limb_t r;
  73   mp_size_t i;
  74
  75   if (bi < nbits)
  76     {
  77       return p[0] & (((mp_limb_t) 1 << bi) - 1);
  78     }
  79   else
  80     {
  81       bi -= nbits;                      /* bit index of low bit to extract */
  82       i = bi / GMP_LIMB_BITS;           /* word index of low bit to extract */
  83       bi %= GMP_LIMB_BITS;              /* bit index in low word */
  84       r = p[i] >> bi;                   /* extract (low) bits */
  85       nbits_in_r = GMP_LIMB_BITS - bi;  /* number of bits now in r */
  86       if (nbits_in_r < nbits)           /* did we get enough bits? */
  87         r += p[i + 1] << nbits_in_r;    /* prepend bits from higher word */
  88       return r & (((mp_limb_t ) 1 << nbits) - 1);
  89     }
  90 }
  91
  92 #undef HAVE_NATIVE_mpn_addmul_2
  93
  94 #ifndef HAVE_NATIVE_mpn_addmul_2
  95 #define REDC_2_THRESHOLD                MP_SIZE_T_MAX
  96 #endif
  97
  98 #ifndef REDC_2_THRESHOLD
  99 #define REDC_2_THRESHOLD                4
 100 #endif
 101
 102 static void mpn_redc_n () {ASSERT_ALWAYS(0);}
 103
 104 static inline int
 105 win_size (unsigned long eb)
 106 {
 107   int k;
 108   static unsigned long x[] = {1,4,27,100,325,1026,2905,7848,20457,51670,~0ul};
 109   for (k = 0; eb > x[k]; k++)
 110     ;
 111   return k;
 112 }
 113
 114 #define MPN_REDC_X(rp, tp, mp, n, mip)                                  \
 115   do {                                                                  \
 116     if (redc_x == 1)                                                    \
 117       mpn_redc_1 (rp, tp, mp, n, mip[0]);                               \
 118     else if (redc_x == 2)                                               \
 119       mpn_redc_2 (rp, tp, mp, n, mip);                                  \
 120     else                                                                \
 121       mpn_redc_n (rp, tp, mp, n, mip);                                  \
 122   } while (0)
 123
 124   /* Convert U to REDC form, U_r = B^n * U mod M */
 125 static void
 126 redcify (mp_ptr rp, mp_srcptr up, mp_size_t un, mp_srcptr mp, mp_size_t n)
 127 {
 128   mp_ptr tp, qp;
 129   TMP_DECL;
 130   TMP_MARK;
 131
 132   tp = TMP_ALLOC_LIMBS (un + n);
 133   qp = TMP_ALLOC_LIMBS (un + 1);        /* FIXME: Put at tp+? */
 134
 135   MPN_ZERO (tp, n);
 136   MPN_COPY (tp + n, up, un);
 137   mpn_tdiv_qr (qp, rp, 0L, tp, un + n, mp, n);
 138   TMP_FREE;
 139 }
 140
 141 /* rp[n-1..0] = bp[bn-1..0] ^ ep[en-1..0] mod mp[n-1..0]
 142    Requires that mp[n-1..0] is odd.
 143    Requires that ep[en-1..0] is > 1.
 144    Uses scratch space tp[3n..0], i.e., 3n+1 words.  */
 145 void
 146 mpn_powm_sec (mp_ptr rp, mp_srcptr bp, mp_size_t bn,
 147               mp_srcptr ep, mp_size_t en,
 148               mp_srcptr mp, mp_size_t n, mp_ptr tp)
 149 {
 150   mp_limb_t mip[2];
 151   int cnt;
 152   long ebi;
 153   int windowsize, this_windowsize;
 154   mp_limb_t expbits;
 155   mp_ptr pp, this_pp, last_pp;
 156   long i;
 157   int redc_x;
 158   TMP_DECL;
 159
 160   ASSERT (en > 1 || (en == 1 && ep[0] > 1));
 161   ASSERT (n >= 1 && ((mp[0] & 1) != 0));
 162
 163   TMP_MARK;
 164
 165   count_leading_zeros (cnt, ep[en - 1]);
 166   ebi = en * GMP_LIMB_BITS - cnt;
 167
 168   windowsize = win_size (ebi);
 169
 170   if (BELOW_THRESHOLD (n, REDC_2_THRESHOLD))
 171     {
 172       binvert_limb (mip[0], mp[0]);
 173       mip[0] = -mip[0];
 174       redc_x = 1;
 175     }
 176 #if defined (HAVE_NATIVE_mpn_addmul_2)
 177   else
 178     {
 179       mpn_binvert (mip, mp, 2, tp);
 180       mip[0] = -mip[0]; mip[1] = ~mip[1];
 181       redc_x = 2;
 182     }
 183 #endif
 184 #if 0
 185   mpn_binvert (mip, mp, n, tp);
 186   redc_x = 0;
 187 #endif
 188
 189   pp = TMP_ALLOC_LIMBS (n << windowsize);
 190
 191   this_pp = pp;
 192   this_pp[n] = 1;
 193   redcify (this_pp, this_pp + n, 1, mp, n);
 194   this_pp += n;
 195   redcify (this_pp, bp, bn, mp, n);
 196
 197   /* Precompute powers of b and put them in the temporary area at pp.  */
 198   for (i = (1 << windowsize) - 2; i > 0; i--)
 199     {
 200       last_pp = this_pp;
 201       this_pp += n;
 202       mpn_mul_n (tp, last_pp, pp + n, n);
 203       MPN_REDC_X (this_pp, tp, mp, n, mip);
 204     }
 205
 206   expbits = getbits (ep, ebi, windowsize);
 207   ebi -= windowsize;
 208   if (ebi < 0)
 209     ebi = 0;
 210
 211   MPN_COPY (rp, pp + n * expbits, n);
 212
 213   while (ebi != 0)
 214     {
 215       expbits = getbits (ep, ebi, windowsize);
 216       ebi -= windowsize;
 217       this_windowsize = windowsize;
 218       if (ebi < 0)
 219         {
 220           this_windowsize += ebi;
 221           ebi = 0;
 222         }
 223
 224       do
 225         {
 226           mpn_sqr_n (tp, rp, n);
 227           MPN_REDC_X (rp, tp, mp, n, mip);
 228           this_windowsize--;
 229         }
 230       while (this_windowsize != 0);
 231
 232 #if WANT_CACHE_SECURITY
 233       mpn_tabselect (tp + 2*n, pp, n, 1 << windowsize, expbits);
 234       mpn_mul_n (tp, rp, tp + 2*n, n);
 235 #else
 236       mpn_mul_n (tp, rp, pp + n * expbits, n);
 237 #endif
 238       MPN_REDC_X (rp, tp, mp, n, mip);
 239     }
 240
 241   MPN_COPY (tp, rp, n);
 242   MPN_ZERO (tp + n, n);
 243   MPN_REDC_X (rp, tp, mp, n, mip);
 244   if (mpn_cmp (rp, mp, n) >= 0)
 245     mpn_sub_n (rp, rp, mp, n);
 246   TMP_FREE;
 247 }
 248
 249 #if ! HAVE_NATIVE_mpn_tabselect
 250 /* Select entry `which' from table `tab', which has nents entries, each `n'
 251    limbs.  Store the selected entry at rp.  Reads entire table to avoid
 252    sideband information leaks.  O(n*nents).  */
 253
 254 void
 255 mpn_tabselect (volatile mp_limb_t *rp, volatile mp_limb_t *tab, mp_size_t n,
 256                mp_size_t nents, mp_size_t which)
 257 {
 258   mp_size_t k, i;
 259   mp_limb_t mask;
 260   volatile mp_limb_t *tp;
 261
 262   for (k = 0; k < nents; k++)
 263     {
 264       mask = -(mp_limb_t) (which == k);
 265       tp = tab + n * k;
 266       for (i = 0; i < n; i++)
 267         {
 268           rp[i] = (rp[i] & ~mask) | (tp[i] & mask);
 269         }
 270     }
 271 }
 272 #endif