mpi-pow.c (7878B)
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 */ 24int 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_ptr_t tp; 180 mpi_size_t xsize; 181 182 /*if (mpihelp_mul_n(xp, rp, rp, rsize) < 0) goto enomem */ 183 if (rsize < KARATSUBA_THRESHOLD) 184 mpih_sqr_n_basecase(xp, rp, rsize); 185 else { 186 if (!tspace) { 187 tsize = 2 * rsize; 188 tspace = 189 mpi_alloc_limb_space(tsize); 190 if (!tspace) 191 goto enomem; 192 } else if (tsize < (2 * rsize)) { 193 mpi_free_limb_space(tspace); 194 tsize = 2 * rsize; 195 tspace = 196 mpi_alloc_limb_space(tsize); 197 if (!tspace) 198 goto enomem; 199 } 200 mpih_sqr_n(xp, rp, rsize, tspace); 201 } 202 203 xsize = 2 * rsize; 204 if (xsize > msize) { 205 mpihelp_divrem(xp + msize, 0, xp, xsize, 206 mp, msize); 207 xsize = msize; 208 } 209 210 tp = rp; 211 rp = xp; 212 xp = tp; 213 rsize = xsize; 214 215 if ((mpi_limb_signed_t) e < 0) { 216 /*mpihelp_mul( xp, rp, rsize, bp, bsize ); */ 217 if (bsize < KARATSUBA_THRESHOLD) { 218 mpi_limb_t tmp; 219 if (mpihelp_mul 220 (xp, rp, rsize, bp, bsize, 221 &tmp) < 0) 222 goto enomem; 223 } else { 224 if (mpihelp_mul_karatsuba_case 225 (xp, rp, rsize, bp, bsize, 226 &karactx) < 0) 227 goto enomem; 228 } 229 230 xsize = rsize + bsize; 231 if (xsize > msize) { 232 mpihelp_divrem(xp + msize, 0, 233 xp, xsize, mp, 234 msize); 235 xsize = msize; 236 } 237 238 tp = rp; 239 rp = xp; 240 xp = tp; 241 rsize = xsize; 242 } 243 e <<= 1; 244 c--; 245 cond_resched(); 246 } 247 248 i--; 249 if (i < 0) 250 break; 251 e = ep[i]; 252 c = BITS_PER_MPI_LIMB; 253 } 254 255 /* We shifted MOD, the modulo reduction argument, left MOD_SHIFT_CNT 256 * steps. Adjust the result by reducing it with the original MOD. 257 * 258 * Also make sure the result is put in RES->d (where it already 259 * might be, see above). 260 */ 261 if (mod_shift_cnt) { 262 carry_limb = 263 mpihelp_lshift(res->d, rp, rsize, mod_shift_cnt); 264 rp = res->d; 265 if (carry_limb) { 266 rp[rsize] = carry_limb; 267 rsize++; 268 } 269 } else { 270 MPN_COPY(res->d, rp, rsize); 271 rp = res->d; 272 } 273 274 if (rsize >= msize) { 275 mpihelp_divrem(rp + msize, 0, rp, rsize, mp, msize); 276 rsize = msize; 277 } 278 279 /* Remove any leading zero words from the result. */ 280 if (mod_shift_cnt) 281 mpihelp_rshift(rp, rp, rsize, mod_shift_cnt); 282 MPN_NORMALIZE(rp, rsize); 283 } 284 285 if (negative_result && rsize) { 286 if (mod_shift_cnt) 287 mpihelp_rshift(mp, mp, msize, mod_shift_cnt); 288 mpihelp_sub(rp, mp, msize, rp, rsize); 289 rsize = msize; 290 rsign = msign; 291 MPN_NORMALIZE(rp, rsize); 292 } 293 res->nlimbs = rsize; 294 res->sign = rsign; 295 296leave: 297 rc = 0; 298enomem: 299 mpihelp_release_karatsuba_ctx(&karactx); 300 if (assign_rp) 301 mpi_assign_limb_space(res, rp, size); 302 if (mp_marker) 303 mpi_free_limb_space(mp_marker); 304 if (bp_marker) 305 mpi_free_limb_space(bp_marker); 306 if (ep_marker) 307 mpi_free_limb_space(ep_marker); 308 if (xp_marker) 309 mpi_free_limb_space(xp_marker); 310 if (tspace) 311 mpi_free_limb_space(tspace); 312 return rc; 313} 314EXPORT_SYMBOL_GPL(mpi_powm);