1/* mpi-pow.c - MPI functions for exponentiation 2 * Copyright (C) 1994, 1996, 1998, 2000, 2002 3 * 2003 Free Software Foundation, Inc. 4 * 5 * This file is part of Libgcrypt. 6 * 7 * Libgcrypt is free software; you can redistribute it and/or modify 8 * it under the terms of the GNU Lesser General Public License as 9 * published by the Free Software Foundation; either version 2.1 of 10 * the License, or (at your option) any later version. 11 * 12 * Libgcrypt is distributed in the hope that it will be useful, 13 * but WITHOUT ANY WARRANTY; without even the implied warranty of 14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 * GNU Lesser General Public License for more details. 16 * 17 * You should have received a copy of the GNU Lesser General Public 18 * License along with this program; if not, see <http://www.gnu.org/licenses/>. 19 * 20 * Note: This code is heavily based on the GNU MP Library. 21 * Actually it's the same code with only minor changes in the 22 * way the data is stored; this is to support the abstraction 23 * of an optional secure memory allocation which may be used 24 * to avoid revealing of sensitive data due to paging etc. 25 */ 26 27#include <config.h> 28#include <stdio.h> 29#include <stdlib.h> 30#include <string.h> 31 32#include "mpi-internal.h" 33#include "longlong.h" 34 35 36/**************** 37 * RES = BASE ^ EXPO mod MOD 38 */ 39void 40gcry_mpi_powm (gcry_mpi_t res, 41 gcry_mpi_t base, gcry_mpi_t expo, gcry_mpi_t mod) 42{ 43 /* Pointer to the limbs of the arguments, their size and signs. */ 44 mpi_ptr_t rp, ep, mp, bp; 45 mpi_size_t esize, msize, bsize, rsize; 46 int msign, bsign, rsign; 47 /* Flags telling the secure allocation status of the arguments. */ 48 int esec, msec, bsec; 49 /* Size of the result including space for temporary values. */ 50 mpi_size_t size; 51 /* Helper. */ 52 int mod_shift_cnt; 53 int negative_result; 54 mpi_ptr_t mp_marker = NULL; 55 mpi_ptr_t bp_marker = NULL; 56 mpi_ptr_t ep_marker = NULL; 57 mpi_ptr_t xp_marker = NULL; 58 unsigned int mp_nlimbs = 0; 59 unsigned int bp_nlimbs = 0; 60 unsigned int ep_nlimbs = 0; 61 unsigned int xp_nlimbs = 0; 62 mpi_ptr_t tspace = NULL; 63 mpi_size_t tsize = 0; 64 65 66 esize = expo->nlimbs; 67 msize = mod->nlimbs; 68 size = 2 * msize; 69 msign = mod->sign; 70 71 esec = mpi_is_secure(expo); 72 msec = mpi_is_secure(mod); 73 bsec = mpi_is_secure(base); 74 75 rp = res->d; 76 ep = expo->d; 77 78 if (!msize) 79 msize = 1 / msize; /* Provoke a signal. */ 80 81 if (!esize) 82 { 83 /* Exponent is zero, result is 1 mod MOD, i.e., 1 or 0 depending 84 on if MOD equals 1. */ 85 rp[0] = 1; 86 res->nlimbs = (msize == 1 && mod->d[0] == 1) ? 0 : 1; 87 res->sign = 0; 88 goto leave; 89 } 90 91 /* Normalize MOD (i.e. make its most significant bit set) as 92 required by mpn_divrem. This will make the intermediate values 93 in the calculation slightly larger, but the correct result is 94 obtained after a final reduction using the original MOD value. */ 95 mp_nlimbs = msec? msize:0; 96 mp = mp_marker = mpi_alloc_limb_space(msize, msec); 97 count_leading_zeros (mod_shift_cnt, mod->d[msize-1]); 98 if (mod_shift_cnt) 99 _gcry_mpih_lshift (mp, mod->d, msize, mod_shift_cnt); 100 else 101 MPN_COPY( mp, mod->d, msize ); 102 103 bsize = base->nlimbs; 104 bsign = base->sign; 105 if (bsize > msize) 106 { 107 /* The base is larger than the module. Reduce it. 108 109 Allocate (BSIZE + 1) with space for remainder and quotient. 110 (The quotient is (bsize - msize + 1) limbs.) */ 111 bp_nlimbs = bsec ? (bsize + 1):0; 112 bp = bp_marker = mpi_alloc_limb_space( bsize + 1, bsec ); 113 MPN_COPY ( bp, base->d, bsize ); 114 /* We don't care about the quotient, store it above the 115 * remainder, at BP + MSIZE. */ 116 _gcry_mpih_divrem( bp + msize, 0, bp, bsize, mp, msize ); 117 bsize = msize; 118 /* Canonicalize the base, since we are going to multiply with it 119 quite a few times. */ 120 MPN_NORMALIZE( bp, bsize ); 121 } 122 else 123 bp = base->d; 124 125 if (!bsize) 126 { 127 res->nlimbs = 0; 128 res->sign = 0; 129 goto leave; 130 } 131 132 133 /* Make BASE, EXPO and MOD not overlap with RES. */ 134 if ( rp == bp ) 135 { 136 /* RES and BASE are identical. Allocate temp. space for BASE. */ 137 gcry_assert (!bp_marker); 138 bp_nlimbs = bsec? bsize:0; 139 bp = bp_marker = mpi_alloc_limb_space( bsize, bsec ); 140 MPN_COPY(bp, rp, bsize); 141 } 142 if ( rp == ep ) 143 { 144 /* RES and EXPO are identical. Allocate temp. space for EXPO. */ 145 ep_nlimbs = esec? esize:0; 146 ep = ep_marker = mpi_alloc_limb_space( esize, esec ); 147 MPN_COPY(ep, rp, esize); 148 } 149 if ( rp == mp ) 150 { 151 /* RES and MOD are identical. Allocate temporary space for MOD.*/ 152 gcry_assert (!mp_marker); 153 mp_nlimbs = msec?msize:0; 154 mp = mp_marker = mpi_alloc_limb_space( msize, msec ); 155 MPN_COPY(mp, rp, msize); 156 } 157 158 /* Copy base to the result. */ 159 if (res->alloced < size) 160 { 161 mpi_resize (res, size); 162 rp = res->d; 163 } 164 MPN_COPY ( rp, bp, bsize ); 165 rsize = bsize; 166 rsign = bsign; 167 168 /* Main processing. */ 169 { 170 mpi_size_t i; 171 mpi_ptr_t xp; 172 int c; 173 mpi_limb_t e; 174 mpi_limb_t carry_limb; 175 struct karatsuba_ctx karactx; 176 177 xp_nlimbs = msec? (2 * (msize + 1)):0; 178 xp = xp_marker = mpi_alloc_limb_space( 2 * (msize + 1), msec ); 179 180 memset( &karactx, 0, sizeof karactx ); 181 negative_result = (ep[0] & 1) && base->sign; 182 183 i = esize - 1; 184 e = ep[i]; 185 count_leading_zeros (c, e); 186 e = (e << c) << 1; /* Shift the expo bits to the left, lose msb. */ 187 c = BITS_PER_MPI_LIMB - 1 - c; 188 189 /* Main loop. 190 191 Make the result be pointed to alternately by XP and RP. This 192 helps us avoid block copying, which would otherwise be 193 necessary with the overlap restrictions of 194 _gcry_mpih_divmod. With 50% probability the result after this 195 loop will be in the area originally pointed by RP (==RES->d), 196 and with 50% probability in the area originally pointed to by XP. */ 197 for (;;) 198 { 199 while (c) 200 { 201 mpi_ptr_t tp; 202 mpi_size_t xsize; 203 204 /*mpih_mul_n(xp, rp, rp, rsize);*/ 205 if ( rsize < KARATSUBA_THRESHOLD ) 206 _gcry_mpih_sqr_n_basecase( xp, rp, rsize ); 207 else 208 { 209 if ( !tspace ) 210 { 211 tsize = 2 * rsize; 212 tspace = mpi_alloc_limb_space( tsize, 0 ); 213 } 214 else if ( tsize < (2*rsize) ) 215 { 216 _gcry_mpi_free_limb_space (tspace, 0); 217 tsize = 2 * rsize; 218 tspace = mpi_alloc_limb_space (tsize, 0 ); 219 } 220 _gcry_mpih_sqr_n (xp, rp, rsize, tspace); 221 } 222 223 xsize = 2 * rsize; 224 if ( xsize > msize ) 225 { 226 _gcry_mpih_divrem(xp + msize, 0, xp, xsize, mp, msize); 227 xsize = msize; 228 } 229 230 tp = rp; rp = xp; xp = tp; 231 rsize = xsize; 232 233 if ( (mpi_limb_signed_t)e < 0 ) 234 { 235 /*mpih_mul( xp, rp, rsize, bp, bsize );*/ 236 if( bsize < KARATSUBA_THRESHOLD ) 237 _gcry_mpih_mul ( xp, rp, rsize, bp, bsize ); 238 else 239 _gcry_mpih_mul_karatsuba_case (xp, rp, rsize, bp, bsize, 240 &karactx); 241 242 xsize = rsize + bsize; 243 if ( xsize > msize ) 244 { 245 _gcry_mpih_divrem(xp + msize, 0, xp, xsize, mp, msize); 246 xsize = msize; 247 } 248 249 tp = rp; rp = xp; xp = tp; 250 rsize = xsize; 251 } 252 e <<= 1; 253 c--; 254 } 255 256 i--; 257 if ( i < 0 ) 258 break; 259 e = ep[i]; 260 c = BITS_PER_MPI_LIMB; 261 } 262 263 /* We shifted MOD, the modulo reduction argument, left 264 MOD_SHIFT_CNT steps. Adjust the result by reducing it with the 265 original MOD. 266 267 Also make sure the result is put in RES->d (where it already 268 might be, see above). */ 269 if ( mod_shift_cnt ) 270 { 271 carry_limb = _gcry_mpih_lshift( res->d, rp, rsize, mod_shift_cnt); 272 rp = res->d; 273 if ( carry_limb ) 274 { 275 rp[rsize] = carry_limb; 276 rsize++; 277 } 278 } 279 else if (res->d != rp) 280 { 281 MPN_COPY (res->d, rp, rsize); 282 rp = res->d; 283 } 284 285 if ( rsize >= msize ) 286 { 287 _gcry_mpih_divrem(rp + msize, 0, rp, rsize, mp, msize); 288 rsize = msize; 289 } 290 291 /* Remove any leading zero words from the result. */ 292 if ( mod_shift_cnt ) 293 _gcry_mpih_rshift( rp, rp, rsize, mod_shift_cnt); 294 MPN_NORMALIZE (rp, rsize); 295 296 _gcry_mpih_release_karatsuba_ctx (&karactx ); 297 } 298 299 /* Fixup for negative results. */ 300 if ( negative_result && rsize ) 301 { 302 if ( mod_shift_cnt ) 303 _gcry_mpih_rshift( mp, mp, msize, mod_shift_cnt); 304 _gcry_mpih_sub( rp, mp, msize, rp, rsize); 305 rsize = msize; 306 rsign = msign; 307 MPN_NORMALIZE(rp, rsize); 308 } 309 gcry_assert (res->d == rp); 310 res->nlimbs = rsize; 311 res->sign = rsign; 312 313 leave: 314 if (mp_marker) 315 _gcry_mpi_free_limb_space( mp_marker, mp_nlimbs ); 316 if (bp_marker) 317 _gcry_mpi_free_limb_space( bp_marker, bp_nlimbs ); 318 if (ep_marker) 319 _gcry_mpi_free_limb_space( ep_marker, ep_nlimbs ); 320 if (xp_marker) 321 _gcry_mpi_free_limb_space( xp_marker, xp_nlimbs ); 322 if (tspace) 323 _gcry_mpi_free_limb_space( tspace, 0 ); 324} 325