1/* mpi-pow.c - MPI functions 2 * Copyright (C) 1994, 1996, 1998, 2000 Free Software Foundation, Inc. 3 * 4 * This file is part of GnuPG. 5 * 6 * GnuPG is free software; you can redistribute it and/or modify 7 * it under the terms of the GNU General Public License as published by 8 * the Free Software Foundation; either version 2 of the License, or 9 * (at your option) any later version. 10 * 11 * GnuPG is distributed in the hope that it will be useful, 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 * GNU General Public License for more details. 15 * 16 * You should have received a copy of the GNU General Public License 17 * along with this program; if not, write to the Free Software 18 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA 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 * The GNU MP Library itself is published under the LGPL; 26 * however I decided to publish this code under the plain GPL. 27 */ 28 29#include <linux/string.h> 30#include "mpi-internal.h" 31#include "longlong.h" 32 33/**************** 34 * RES = BASE ^ EXP mod MOD 35 */ 36int mpi_powm(MPI res, MPI base, MPI exp, MPI mod) 37{ 38 mpi_ptr_t mp_marker = NULL, bp_marker = NULL, ep_marker = NULL; 39 mpi_ptr_t xp_marker = NULL; 40 mpi_ptr_t tspace = NULL; 41 mpi_ptr_t rp, ep, mp, bp; 42 mpi_size_t esize, msize, bsize, rsize; 43 int esign, msign, bsign, rsign; 44 mpi_size_t size; 45 int mod_shift_cnt; 46 int negative_result; 47 int assign_rp = 0; 48 mpi_size_t tsize = 0; /* to avoid compiler warning */ 49 /* fixme: we should check that the warning is void */ 50 int rc = -ENOMEM; 51 52 esize = exp->nlimbs; 53 msize = mod->nlimbs; 54 size = 2 * msize; 55 esign = exp->sign; 56 msign = mod->sign; 57 58 rp = res->d; 59 ep = exp->d; 60 61 if (!msize) 62 return -EINVAL; 63 64 if (!esize) { 65 /* Exponent is zero, result is 1 mod MOD, i.e., 1 or 0 66 * depending on if MOD equals 1. */ 67 rp[0] = 1; 68 res->nlimbs = (msize == 1 && mod->d[0] == 1) ? 0 : 1; 69 res->sign = 0; 70 goto leave; 71 } 72 73 /* Normalize MOD (i.e. make its most significant bit set) as required by 74 * mpn_divrem. This will make the intermediate values in the calculation 75 * slightly larger, but the correct result is obtained after a final 76 * reduction using the original MOD value. */ 77 mp = mp_marker = mpi_alloc_limb_space(msize); 78 if (!mp) 79 goto enomem; 80 mod_shift_cnt = count_leading_zeros(mod->d[msize - 1]); 81 if (mod_shift_cnt) 82 mpihelp_lshift(mp, mod->d, msize, mod_shift_cnt); 83 else 84 MPN_COPY(mp, mod->d, msize); 85 86 bsize = base->nlimbs; 87 bsign = base->sign; 88 if (bsize > msize) { /* The base is larger than the module. Reduce it. */ 89 /* Allocate (BSIZE + 1) with space for remainder and quotient. 90 * (The quotient is (bsize - msize + 1) limbs.) */ 91 bp = bp_marker = mpi_alloc_limb_space(bsize + 1); 92 if (!bp) 93 goto enomem; 94 MPN_COPY(bp, base->d, bsize); 95 /* We don't care about the quotient, store it above the remainder, 96 * at BP + MSIZE. */ 97 mpihelp_divrem(bp + msize, 0, bp, bsize, mp, msize); 98 bsize = msize; 99 /* Canonicalize the base, since we are going to multiply with it 100 * quite a few times. */ 101 MPN_NORMALIZE(bp, bsize); 102 } else 103 bp = base->d; 104 105 if (!bsize) { 106 res->nlimbs = 0; 107 res->sign = 0; 108 goto leave; 109 } 110 111 if (res->alloced < size) { 112 /* We have to allocate more space for RES. If any of the input 113 * parameters are identical to RES, defer deallocation of the old 114 * space. */ 115 if (rp == ep || rp == mp || rp == bp) { 116 rp = mpi_alloc_limb_space(size); 117 if (!rp) 118 goto enomem; 119 assign_rp = 1; 120 } else { 121 if (mpi_resize(res, size) < 0) 122 goto enomem; 123 rp = res->d; 124 } 125 } else { /* Make BASE, EXP and MOD not overlap with RES. */ 126 if (rp == bp) { 127 /* RES and BASE are identical. Allocate temp. space for BASE. */ 128 BUG_ON(bp_marker); 129 bp = bp_marker = mpi_alloc_limb_space(bsize); 130 if (!bp) 131 goto enomem; 132 MPN_COPY(bp, rp, bsize); 133 } 134 if (rp == ep) { 135 /* RES and EXP are identical. Allocate temp. space for EXP. */ 136 ep = ep_marker = mpi_alloc_limb_space(esize); 137 if (!ep) 138 goto enomem; 139 MPN_COPY(ep, rp, esize); 140 } 141 if (rp == mp) { 142 /* RES and MOD are identical. Allocate temporary space for MOD. */ 143 BUG_ON(mp_marker); 144 mp = mp_marker = mpi_alloc_limb_space(msize); 145 if (!mp) 146 goto enomem; 147 MPN_COPY(mp, rp, msize); 148 } 149 } 150 151 MPN_COPY(rp, bp, bsize); 152 rsize = bsize; 153 rsign = bsign; 154 155 { 156 mpi_size_t i; 157 mpi_ptr_t xp; 158 int c; 159 mpi_limb_t e; 160 mpi_limb_t carry_limb; 161 struct karatsuba_ctx karactx; 162 163 xp = xp_marker = mpi_alloc_limb_space(2 * (msize + 1)); 164 if (!xp) 165 goto enomem; 166 167 memset(&karactx, 0, sizeof karactx); 168 negative_result = (ep[0] & 1) && base->sign; 169 170 i = esize - 1; 171 e = ep[i]; 172 c = count_leading_zeros(e); 173 e = (e << c) << 1; /* shift the exp bits to the left, lose msb */ 174 c = BITS_PER_MPI_LIMB - 1 - c; 175 176 /* Main loop. 177 * 178 * Make the result be pointed to alternately by XP and RP. This 179 * helps us avoid block copying, which would otherwise be necessary 180 * with the overlap restrictions of mpihelp_divmod. With 50% probability 181 * the result after this loop will be in the area originally pointed 182 * by RP (==RES->d), and with 50% probability in the area originally 183 * pointed to by XP. 184 */ 185 186 for (;;) { 187 while (c) { 188 mpi_ptr_t tp; 189 mpi_size_t xsize; 190 191 /*if (mpihelp_mul_n(xp, rp, rp, rsize) < 0) goto enomem */ 192 if (rsize < KARATSUBA_THRESHOLD) 193 mpih_sqr_n_basecase(xp, rp, rsize); 194 else { 195 if (!tspace) { 196 tsize = 2 * rsize; 197 tspace = 198 mpi_alloc_limb_space(tsize); 199 if (!tspace) 200 goto enomem; 201 } else if (tsize < (2 * rsize)) { 202 mpi_free_limb_space(tspace); 203 tsize = 2 * rsize; 204 tspace = 205 mpi_alloc_limb_space(tsize); 206 if (!tspace) 207 goto enomem; 208 } 209 mpih_sqr_n(xp, rp, rsize, tspace); 210 } 211 212 xsize = 2 * rsize; 213 if (xsize > msize) { 214 mpihelp_divrem(xp + msize, 0, xp, xsize, 215 mp, msize); 216 xsize = msize; 217 } 218 219 tp = rp; 220 rp = xp; 221 xp = tp; 222 rsize = xsize; 223 224 if ((mpi_limb_signed_t) e < 0) { 225 /*mpihelp_mul( xp, rp, rsize, bp, bsize ); */ 226 if (bsize < KARATSUBA_THRESHOLD) { 227 mpi_limb_t tmp; 228 if (mpihelp_mul 229 (xp, rp, rsize, bp, bsize, 230 &tmp) < 0) 231 goto enomem; 232 } else { 233 if (mpihelp_mul_karatsuba_case 234 (xp, rp, rsize, bp, bsize, 235 &karactx) < 0) 236 goto enomem; 237 } 238 239 xsize = rsize + bsize; 240 if (xsize > msize) { 241 mpihelp_divrem(xp + msize, 0, 242 xp, xsize, mp, 243 msize); 244 xsize = msize; 245 } 246 247 tp = rp; 248 rp = xp; 249 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 MOD_SHIFT_CNT 264 * steps. Adjust the result by reducing it with the original MOD. 265 * 266 * Also make sure the result is put in RES->d (where it already 267 * might be, see above). 268 */ 269 if (mod_shift_cnt) { 270 carry_limb = 271 mpihelp_lshift(res->d, rp, rsize, mod_shift_cnt); 272 rp = res->d; 273 if (carry_limb) { 274 rp[rsize] = carry_limb; 275 rsize++; 276 } 277 } else { 278 MPN_COPY(res->d, rp, rsize); 279 rp = res->d; 280 } 281 282 if (rsize >= msize) { 283 mpihelp_divrem(rp + msize, 0, rp, rsize, mp, msize); 284 rsize = msize; 285 } 286 287 /* Remove any leading zero words from the result. */ 288 if (mod_shift_cnt) 289 mpihelp_rshift(rp, rp, rsize, mod_shift_cnt); 290 MPN_NORMALIZE(rp, rsize); 291 292 mpihelp_release_karatsuba_ctx(&karactx); 293 } 294 295 if (negative_result && rsize) { 296 if (mod_shift_cnt) 297 mpihelp_rshift(mp, mp, msize, mod_shift_cnt); 298 mpihelp_sub(rp, mp, msize, rp, rsize); 299 rsize = msize; 300 rsign = msign; 301 MPN_NORMALIZE(rp, rsize); 302 } 303 res->nlimbs = rsize; 304 res->sign = rsign; 305 306leave: 307 rc = 0; 308enomem: 309 if (assign_rp) 310 mpi_assign_limb_space(res, rp, size); 311 if (mp_marker) 312 mpi_free_limb_space(mp_marker); 313 if (bp_marker) 314 mpi_free_limb_space(bp_marker); 315 if (ep_marker) 316 mpi_free_limb_space(ep_marker); 317 if (xp_marker) 318 mpi_free_limb_space(xp_marker); 319 if (tspace) 320 mpi_free_limb_space(tspace); 321 return rc; 322} 323EXPORT_SYMBOL_GPL(mpi_powm); 324