310 lines · c
1// SPDX-License-Identifier: GPL-2.0-or-later2/* mpi-pow.c - MPI functions3 * 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 the9 * way the data is stored; this is to support the abstraction10 * of an optional secure memory allocation which may be used11 * 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 MOD23 */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 054 * 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 by67 * mpn_divrem. This will make the intermediate values in the calculation68 * slightly larger, but the correct result is obtained after a final69 * 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 else77 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 it93 * quite a few times. */94 MPN_NORMALIZE(bp, bsize);95 } else96 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 input106 * parameters are identical to RES, defer deallocation of the old107 * 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. This170 * helps us avoid block copying, which would otherwise be necessary171 * with the overlap restrictions of mpihelp_divmod. With 50% probability172 * the result after this loop will be in the area originally pointed173 * by RP (==RES->d), and with 50% probability in the area originally174 * 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_mul217 (xp, rp, rsize, bp, bsize,218 &tmp) < 0)219 goto enomem;220 } else {221 if (mpihelp_mul_karatsuba_case222 (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_CNT251 * 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 already254 * 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 291leave:292 rc = 0;293enomem: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}309EXPORT_SYMBOL_GPL(mpi_powm);310