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