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 273