lib/mpi/mpi-pow.c

0001 // SPDX-License-Identifier: GPL-2.0-or-later
0002 /* mpi-pow.c  -  MPI functions
0003  *  Copyright (C) 1994, 1996, 1998, 2000 Free Software Foundation, Inc.
0004  *
0005  * This file is part of GnuPG.
0006  *
0007  * Note: This code is heavily based on the GNU MP Library.
0008  *   Actually it's the same code with only minor changes in the
0009  *   way the data is stored; this is to support the abstraction
0010  *   of an optional secure memory allocation which may be used
0011  *   to avoid revealing of sensitive data due to paging etc.
0012  *   The GNU MP Library itself is published under the LGPL;
0013  *   however I decided to publish this code under the plain GPL.
0014  */
0015
0016 #include <linux/sched.h>
0017 #include <linux/string.h>
0018 #include "mpi-internal.h"
0019 #include "longlong.h"
0020
0021 /****************
0022  * RES = BASE ^ EXP mod MOD
0023  */
0024 int mpi_powm(MPI res, MPI base, MPI exp, MPI mod)
0025 {
0026     mpi_ptr_t mp_marker = NULL, bp_marker = NULL, ep_marker = NULL;
0027     struct karatsuba_ctx karactx = {};
0028     mpi_ptr_t xp_marker = NULL;
0029     mpi_ptr_t tspace = NULL;
0030     mpi_ptr_t rp, ep, mp, bp;
0031     mpi_size_t esize, msize, bsize, rsize;
0032     int msign, bsign, rsign;
0033     mpi_size_t size;
0034     int mod_shift_cnt;
0035     int negative_result;
0036     int assign_rp = 0;
0037     mpi_size_t tsize = 0;   /* to avoid compiler warning */
0038     /* fixme: we should check that the warning is void */
0039     int rc = -ENOMEM;
0040
0041     esize = exp->nlimbs;
0042     msize = mod->nlimbs;
0043     size = 2 * msize;
0044     msign = mod->sign;
0045
0046     rp = res->d;
0047     ep = exp->d;
0048
0049     if (!msize)
0050         return -EINVAL;
0051
0052     if (!esize) {
0053         /* Exponent is zero, result is 1 mod MOD, i.e., 1 or 0
0054          * depending on if MOD equals 1.  */
0055         res->nlimbs = (msize == 1 && mod->d[0] == 1) ? 0 : 1;
0056         if (res->nlimbs) {
0057             if (mpi_resize(res, 1) < 0)
0058                 goto enomem;
0059             rp = res->d;
0060             rp[0] = 1;
0061         }
0062         res->sign = 0;
0063         goto leave;
0064     }
0065
0066     /* Normalize MOD (i.e. make its most significant bit set) as required by
0067      * mpn_divrem.  This will make the intermediate values in the calculation
0068      * slightly larger, but the correct result is obtained after a final
0069      * reduction using the original MOD value.  */
0070     mp = mp_marker = mpi_alloc_limb_space(msize);
0071     if (!mp)
0072         goto enomem;
0073     mod_shift_cnt = count_leading_zeros(mod->d[msize - 1]);
0074     if (mod_shift_cnt)
0075         mpihelp_lshift(mp, mod->d, msize, mod_shift_cnt);
0076     else
0077         MPN_COPY(mp, mod->d, msize);
0078
0079     bsize = base->nlimbs;
0080     bsign = base->sign;
0081     if (bsize > msize) {    /* The base is larger than the module. Reduce it. */
0082         /* Allocate (BSIZE + 1) with space for remainder and quotient.
0083          * (The quotient is (bsize - msize + 1) limbs.)  */
0084         bp = bp_marker = mpi_alloc_limb_space(bsize + 1);
0085         if (!bp)
0086             goto enomem;
0087         MPN_COPY(bp, base->d, bsize);
0088         /* We don't care about the quotient, store it above the remainder,
0089          * at BP + MSIZE.  */
0090         mpihelp_divrem(bp + msize, 0, bp, bsize, mp, msize);
0091         bsize = msize;
0092         /* Canonicalize the base, since we are going to multiply with it
0093          * quite a few times.  */
0094         MPN_NORMALIZE(bp, bsize);
0095     } else
0096         bp = base->d;
0097
0098     if (!bsize) {
0099         res->nlimbs = 0;
0100         res->sign = 0;
0101         goto leave;
0102     }
0103
0104     if (res->alloced < size) {
0105         /* We have to allocate more space for RES.  If any of the input
0106          * parameters are identical to RES, defer deallocation of the old
0107          * space.  */
0108         if (rp == ep || rp == mp || rp == bp) {
0109             rp = mpi_alloc_limb_space(size);
0110             if (!rp)
0111                 goto enomem;
0112             assign_rp = 1;
0113         } else {
0114             if (mpi_resize(res, size) < 0)
0115                 goto enomem;
0116             rp = res->d;
0117         }
0118     } else {        /* Make BASE, EXP and MOD not overlap with RES.  */
0119         if (rp == bp) {
0120             /* RES and BASE are identical.  Allocate temp. space for BASE.  */
0121             BUG_ON(bp_marker);
0122             bp = bp_marker = mpi_alloc_limb_space(bsize);
0123             if (!bp)
0124                 goto enomem;
0125             MPN_COPY(bp, rp, bsize);
0126         }
0127         if (rp == ep) {
0128             /* RES and EXP are identical.  Allocate temp. space for EXP.  */
0129             ep = ep_marker = mpi_alloc_limb_space(esize);
0130             if (!ep)
0131                 goto enomem;
0132             MPN_COPY(ep, rp, esize);
0133         }
0134         if (rp == mp) {
0135             /* RES and MOD are identical.  Allocate temporary space for MOD. */
0136             BUG_ON(mp_marker);
0137             mp = mp_marker = mpi_alloc_limb_space(msize);
0138             if (!mp)
0139                 goto enomem;
0140             MPN_COPY(mp, rp, msize);
0141         }
0142     }
0143
0144     MPN_COPY(rp, bp, bsize);
0145     rsize = bsize;
0146     rsign = bsign;
0147
0148     {
0149         mpi_size_t i;
0150         mpi_ptr_t xp;
0151         int c;
0152         mpi_limb_t e;
0153         mpi_limb_t carry_limb;
0154
0155         xp = xp_marker = mpi_alloc_limb_space(2 * (msize + 1));
0156         if (!xp)
0157             goto enomem;
0158
0159         negative_result = (ep[0] & 1) && base->sign;
0160
0161         i = esize - 1;
0162         e = ep[i];
0163         c = count_leading_zeros(e);
0164         e = (e << c) << 1;  /* shift the exp bits to the left, lose msb */
0165         c = BITS_PER_MPI_LIMB - 1 - c;
0166
0167         /* Main loop.
0168          *
0169          * Make the result be pointed to alternately by XP and RP.  This
0170          * helps us avoid block copying, which would otherwise be necessary
0171          * with the overlap restrictions of mpihelp_divmod. With 50% probability
0172          * the result after this loop will be in the area originally pointed
0173          * by RP (==RES->d), and with 50% probability in the area originally
0174          * pointed to by XP.
0175          */
0176
0177         for (;;) {
0178             while (c) {
0179                 mpi_ptr_t tp;
0180                 mpi_size_t xsize;
0181
0182                 /*if (mpihelp_mul_n(xp, rp, rp, rsize) < 0) goto enomem */
0183                 if (rsize < KARATSUBA_THRESHOLD)
0184                     mpih_sqr_n_basecase(xp, rp, rsize);
0185                 else {
0186                     if (!tspace) {
0187                         tsize = 2 * rsize;
0188                         tspace =
0189                             mpi_alloc_limb_space(tsize);
0190                         if (!tspace)
0191                             goto enomem;
0192                     } else if (tsize < (2 * rsize)) {
0193                         mpi_free_limb_space(tspace);
0194                         tsize = 2 * rsize;
0195                         tspace =
0196                             mpi_alloc_limb_space(tsize);
0197                         if (!tspace)
0198                             goto enomem;
0199                     }
0200                     mpih_sqr_n(xp, rp, rsize, tspace);
0201                 }
0202
0203                 xsize = 2 * rsize;
0204                 if (xsize > msize) {
0205                     mpihelp_divrem(xp + msize, 0, xp, xsize,
0206                                mp, msize);
0207                     xsize = msize;
0208                 }
0209
0210                 tp = rp;
0211                 rp = xp;
0212                 xp = tp;
0213                 rsize = xsize;
0214
0215                 if ((mpi_limb_signed_t) e < 0) {
0216                     /*mpihelp_mul( xp, rp, rsize, bp, bsize ); */
0217                     if (bsize < KARATSUBA_THRESHOLD) {
0218                         mpi_limb_t tmp;
0219                         if (mpihelp_mul
0220                             (xp, rp, rsize, bp, bsize,
0221                              &tmp) < 0)
0222                             goto enomem;
0223                     } else {
0224                         if (mpihelp_mul_karatsuba_case
0225                             (xp, rp, rsize, bp, bsize,
0226                              &karactx) < 0)
0227                             goto enomem;
0228                     }
0229
0230                     xsize = rsize + bsize;
0231                     if (xsize > msize) {
0232                         mpihelp_divrem(xp + msize, 0,
0233                                    xp, xsize, mp,
0234                                    msize);
0235                         xsize = msize;
0236                     }
0237
0238                     tp = rp;
0239                     rp = xp;
0240                     xp = tp;
0241                     rsize = xsize;
0242                 }
0243                 e <<= 1;
0244                 c--;
0245                 cond_resched();
0246             }
0247
0248             i--;
0249             if (i < 0)
0250                 break;
0251             e = ep[i];
0252             c = BITS_PER_MPI_LIMB;
0253         }
0254
0255         /* We shifted MOD, the modulo reduction argument, left MOD_SHIFT_CNT
0256          * steps.  Adjust the result by reducing it with the original MOD.
0257          *
0258          * Also make sure the result is put in RES->d (where it already
0259          * might be, see above).
0260          */
0261         if (mod_shift_cnt) {
0262             carry_limb =
0263                 mpihelp_lshift(res->d, rp, rsize, mod_shift_cnt);
0264             rp = res->d;
0265             if (carry_limb) {
0266                 rp[rsize] = carry_limb;
0267                 rsize++;
0268             }
0269         } else {
0270             MPN_COPY(res->d, rp, rsize);
0271             rp = res->d;
0272         }
0273
0274         if (rsize >= msize) {
0275             mpihelp_divrem(rp + msize, 0, rp, rsize, mp, msize);
0276             rsize = msize;
0277         }
0278
0279         /* Remove any leading zero words from the result.  */
0280         if (mod_shift_cnt)
0281             mpihelp_rshift(rp, rp, rsize, mod_shift_cnt);
0282         MPN_NORMALIZE(rp, rsize);
0283     }
0284
0285     if (negative_result && rsize) {
0286         if (mod_shift_cnt)
0287             mpihelp_rshift(mp, mp, msize, mod_shift_cnt);
0288         mpihelp_sub(rp, mp, msize, rp, rsize);
0289         rsize = msize;
0290         rsign = msign;
0291         MPN_NORMALIZE(rp, rsize);
0292     }
0293     res->nlimbs = rsize;
0294     res->sign = rsign;
0295
0296 leave:
0297     rc = 0;
0298 enomem:
0299     mpihelp_release_karatsuba_ctx(&karactx);
0300     if (assign_rp)
0301         mpi_assign_limb_space(res, rp, size);
0302     if (mp_marker)
0303         mpi_free_limb_space(mp_marker);
0304     if (bp_marker)
0305         mpi_free_limb_space(bp_marker);
0306     if (ep_marker)
0307         mpi_free_limb_space(ep_marker);
0308     if (xp_marker)
0309         mpi_free_limb_space(xp_marker);
0310     if (tspace)
0311         mpi_free_limb_space(tspace);
0312     return rc;
0313 }
0314 EXPORT_SYMBOL_GPL(mpi_powm);