LCOV - code coverage report
Current view: top level - lib/mpi - mpi-pow.c (source / functions) Hit Total Coverage
Test: combined.info Lines: 106 175 60.6 %
Date: 2022-04-01 14:58:12 Functions: 1 1 100.0 %
Branches: 46 126 36.5 %

           Branch data     Line data    Source code
       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                 :          3 : int mpi_powm(MPI res, MPI base, MPI exp, MPI mod)
      25                 :            : {
      26                 :          3 :         mpi_ptr_t mp_marker = NULL, bp_marker = NULL, ep_marker = NULL;
      27                 :          3 :         struct karatsuba_ctx karactx = {};
      28                 :          3 :         mpi_ptr_t xp_marker = NULL;
      29                 :          3 :         mpi_ptr_t tspace = NULL;
      30                 :          3 :         mpi_ptr_t rp, ep, mp, bp;
      31                 :          3 :         mpi_size_t esize, msize, bsize, rsize;
      32                 :          3 :         int msign, bsign, rsign;
      33                 :          3 :         mpi_size_t size;
      34                 :          3 :         int mod_shift_cnt;
      35                 :          3 :         int negative_result;
      36                 :          3 :         int assign_rp = 0;
      37                 :          3 :         mpi_size_t tsize = 0;   /* to avoid compiler warning */
      38                 :            :         /* fixme: we should check that the warning is void */
      39                 :          3 :         int rc = -ENOMEM;
      40                 :            : 
      41                 :          3 :         esize = exp->nlimbs;
      42                 :          3 :         msize = mod->nlimbs;
      43                 :          3 :         size = 2 * msize;
      44                 :          3 :         msign = mod->sign;
      45                 :            : 
      46                 :          3 :         rp = res->d;
      47                 :          3 :         ep = exp->d;
      48                 :            : 
      49         [ +  - ]:          3 :         if (!msize)
      50                 :            :                 return -EINVAL;
      51                 :            : 
      52         [ -  + ]:          3 :         if (!esize) {
      53                 :            :                 /* Exponent is zero, result is 1 mod MOD, i.e., 1 or 0
      54                 :            :                  * depending on if MOD equals 1.  */
      55   [ #  #  #  # ]:          0 :                 res->nlimbs = (msize == 1 && mod->d[0] == 1) ? 0 : 1;
      56         [ #  # ]:          0 :                 if (res->nlimbs) {
      57         [ #  # ]:          0 :                         if (mpi_resize(res, 1) < 0)
      58                 :          0 :                                 goto enomem;
      59                 :          0 :                         rp = res->d;
      60                 :          0 :                         rp[0] = 1;
      61                 :            :                 }
      62                 :          0 :                 res->sign = 0;
      63                 :          0 :                 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                 :          3 :         mp = mp_marker = mpi_alloc_limb_space(msize);
      71         [ -  + ]:          3 :         if (!mp)
      72                 :          0 :                 goto enomem;
      73         [ -  + ]:          3 :         mod_shift_cnt = count_leading_zeros(mod->d[msize - 1]);
      74         [ -  + ]:          3 :         if (mod_shift_cnt)
      75                 :          0 :                 mpihelp_lshift(mp, mod->d, msize, mod_shift_cnt);
      76                 :            :         else
      77         [ +  + ]:         99 :                 MPN_COPY(mp, mod->d, msize);
      78                 :            : 
      79                 :          3 :         bsize = base->nlimbs;
      80                 :          3 :         bsign = base->sign;
      81         [ -  + ]:          3 :         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                 :          0 :                 bp = bp_marker = mpi_alloc_limb_space(bsize + 1);
      85         [ #  # ]:          0 :                 if (!bp)
      86                 :          0 :                         goto enomem;
      87         [ #  # ]:          0 :                 MPN_COPY(bp, base->d, bsize);
      88                 :            :                 /* We don't care about the quotient, store it above the remainder,
      89                 :            :                  * at BP + MSIZE.  */
      90                 :          0 :                 mpihelp_divrem(bp + msize, 0, bp, bsize, mp, msize);
      91                 :          0 :                 bsize = msize;
      92                 :            :                 /* Canonicalize the base, since we are going to multiply with it
      93                 :            :                  * quite a few times.  */
      94   [ #  #  #  # ]:          0 :                 MPN_NORMALIZE(bp, bsize);
      95                 :            :         } else
      96                 :          3 :                 bp = base->d;
      97                 :            : 
      98         [ -  + ]:          3 :         if (!bsize) {
      99                 :          0 :                 res->nlimbs = 0;
     100                 :          0 :                 res->sign = 0;
     101                 :          0 :                 goto leave;
     102                 :            :         }
     103                 :            : 
     104         [ +  - ]:          3 :         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   [ +  -  -  + ]:          3 :                 if (rp == ep || rp == mp || rp == bp) {
     109                 :          0 :                         rp = mpi_alloc_limb_space(size);
     110         [ #  # ]:          0 :                         if (!rp)
     111                 :          0 :                                 goto enomem;
     112                 :            :                         assign_rp = 1;
     113                 :            :                 } else {
     114         [ -  + ]:          3 :                         if (mpi_resize(res, size) < 0)
     115                 :          0 :                                 goto enomem;
     116                 :          3 :                         rp = res->d;
     117                 :            :                 }
     118                 :            :         } else {                /* Make BASE, EXP and MOD not overlap with RES.  */
     119         [ #  # ]:          0 :                 if (rp == bp) {
     120                 :            :                         /* RES and BASE are identical.  Allocate temp. space for BASE.  */
     121         [ #  # ]:          0 :                         BUG_ON(bp_marker);
     122                 :          0 :                         bp = bp_marker = mpi_alloc_limb_space(bsize);
     123         [ #  # ]:          0 :                         if (!bp)
     124                 :          0 :                                 goto enomem;
     125         [ #  # ]:          0 :                         MPN_COPY(bp, rp, bsize);
     126                 :            :                 }
     127         [ #  # ]:          0 :                 if (rp == ep) {
     128                 :            :                         /* RES and EXP are identical.  Allocate temp. space for EXP.  */
     129                 :          0 :                         ep = ep_marker = mpi_alloc_limb_space(esize);
     130         [ #  # ]:          0 :                         if (!ep)
     131                 :          0 :                                 goto enomem;
     132         [ #  # ]:          0 :                         MPN_COPY(ep, rp, esize);
     133                 :            :                 }
     134         [ #  # ]:          0 :                 if (rp == mp) {
     135                 :            :                         /* RES and MOD are identical.  Allocate temporary space for MOD. */
     136                 :          0 :                         BUG_ON(mp_marker);
     137                 :            :                         mp = mp_marker = mpi_alloc_limb_space(msize);
     138                 :            :                         if (!mp)
     139                 :            :                                 goto enomem;
     140                 :          3 :                         MPN_COPY(mp, rp, msize);
     141                 :            :                 }
     142                 :            :         }
     143                 :            : 
     144         [ +  + ]:         99 :         MPN_COPY(rp, bp, bsize);
     145                 :          3 :         rsize = bsize;
     146                 :          3 :         rsign = bsign;
     147                 :            : 
     148                 :            :         {
     149                 :          3 :                 mpi_size_t i;
     150                 :          3 :                 mpi_ptr_t xp;
     151                 :          3 :                 int c;
     152                 :          3 :                 mpi_limb_t e;
     153                 :          3 :                 mpi_limb_t carry_limb;
     154                 :            : 
     155                 :          3 :                 xp = xp_marker = mpi_alloc_limb_space(2 * (msize + 1));
     156         [ -  + ]:          3 :                 if (!xp)
     157                 :          0 :                         goto enomem;
     158                 :            : 
     159   [ +  -  +  - ]:          3 :                 negative_result = (ep[0] & 1) && base->sign;
     160                 :            : 
     161                 :          3 :                 i = esize - 1;
     162                 :          3 :                 e = ep[i];
     163                 :          3 :                 c = count_leading_zeros(e);
     164                 :          3 :                 e = (e << c) << 1;  /* shift the exp bits to the left, lose msb */
     165                 :          3 :                 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                 :          0 :                 for (;;) {
     178         [ +  + ]:         51 :                         while (c) {
     179                 :         48 :                                 mpi_ptr_t tp;
     180                 :         48 :                                 mpi_size_t xsize;
     181                 :            : 
     182                 :            :                                 /*if (mpihelp_mul_n(xp, rp, rp, rsize) < 0) goto enomem */
     183         [ -  + ]:         48 :                                 if (rsize < KARATSUBA_THRESHOLD)
     184                 :          0 :                                         mpih_sqr_n_basecase(xp, rp, rsize);
     185                 :            :                                 else {
     186         [ +  + ]:         48 :                                         if (!tspace) {
     187                 :          3 :                                                 tsize = 2 * rsize;
     188                 :          3 :                                                 tspace =
     189                 :          3 :                                                     mpi_alloc_limb_space(tsize);
     190         [ -  + ]:          3 :                                                 if (!tspace)
     191                 :          0 :                                                         goto enomem;
     192         [ -  + ]:         45 :                                         } else if (tsize < (2 * rsize)) {
     193                 :          0 :                                                 mpi_free_limb_space(tspace);
     194                 :          0 :                                                 tsize = 2 * rsize;
     195                 :          0 :                                                 tspace =
     196                 :          0 :                                                     mpi_alloc_limb_space(tsize);
     197         [ #  # ]:          0 :                                                 if (!tspace)
     198                 :          0 :                                                         goto enomem;
     199                 :            :                                         }
     200                 :         48 :                                         mpih_sqr_n(xp, rp, rsize, tspace);
     201                 :            :                                 }
     202                 :            : 
     203                 :         48 :                                 xsize = 2 * rsize;
     204         [ +  - ]:         48 :                                 if (xsize > msize) {
     205                 :         48 :                                         mpihelp_divrem(xp + msize, 0, xp, xsize,
     206                 :            :                                                        mp, msize);
     207                 :         48 :                                         xsize = msize;
     208                 :            :                                 }
     209                 :            : 
     210                 :         48 :                                 tp = rp;
     211                 :         48 :                                 rp = xp;
     212                 :         48 :                                 xp = tp;
     213                 :         48 :                                 rsize = xsize;
     214                 :            : 
     215         [ +  + ]:         48 :                                 if ((mpi_limb_signed_t) e < 0) {
     216                 :            :                                         /*mpihelp_mul( xp, rp, rsize, bp, bsize ); */
     217         [ -  + ]:          3 :                                         if (bsize < KARATSUBA_THRESHOLD) {
     218                 :          0 :                                                 mpi_limb_t tmp;
     219         [ #  # ]:          0 :                                                 if (mpihelp_mul
     220                 :            :                                                     (xp, rp, rsize, bp, bsize,
     221                 :            :                                                      &tmp) < 0)
     222                 :          0 :                                                         goto enomem;
     223                 :            :                                         } else {
     224         [ -  + ]:          3 :                                                 if (mpihelp_mul_karatsuba_case
     225                 :            :                                                     (xp, rp, rsize, bp, bsize,
     226                 :            :                                                      &karactx) < 0)
     227                 :          0 :                                                         goto enomem;
     228                 :            :                                         }
     229                 :            : 
     230                 :          3 :                                         xsize = rsize + bsize;
     231         [ +  - ]:          3 :                                         if (xsize > msize) {
     232                 :          3 :                                                 mpihelp_divrem(xp + msize, 0,
     233                 :            :                                                                xp, xsize, mp,
     234                 :            :                                                                msize);
     235                 :          3 :                                                 xsize = msize;
     236                 :            :                                         }
     237                 :            : 
     238                 :            :                                         tp = rp;
     239                 :            :                                         rp = xp;
     240                 :            :                                         xp = tp;
     241                 :            :                                         rsize = xsize;
     242                 :            :                                 }
     243                 :         48 :                                 e <<= 1;
     244                 :         48 :                                 c--;
     245                 :         48 :                                 cond_resched();
     246                 :            :                         }
     247                 :            : 
     248                 :          3 :                         i--;
     249         [ -  + ]:          3 :                         if (i < 0)
     250                 :            :                                 break;
     251                 :          0 :                         e = ep[i];
     252                 :          0 :                         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         [ -  + ]:          3 :                 if (mod_shift_cnt) {
     262                 :          0 :                         carry_limb =
     263                 :          0 :                             mpihelp_lshift(res->d, rp, rsize, mod_shift_cnt);
     264                 :          0 :                         rp = res->d;
     265         [ #  # ]:          0 :                         if (carry_limb) {
     266                 :          0 :                                 rp[rsize] = carry_limb;
     267                 :          0 :                                 rsize++;
     268                 :            :                         }
     269                 :            :                 } else {
     270         [ +  + ]:         99 :                         MPN_COPY(res->d, rp, rsize);
     271                 :          3 :                         rp = res->d;
     272                 :            :                 }
     273                 :            : 
     274         [ +  - ]:          3 :                 if (rsize >= msize) {
     275                 :          3 :                         mpihelp_divrem(rp + msize, 0, rp, rsize, mp, msize);
     276                 :          3 :                         rsize = msize;
     277                 :            :                 }
     278                 :            : 
     279                 :            :                 /* Remove any leading zero words from the result.  */
     280         [ -  + ]:          3 :                 if (mod_shift_cnt)
     281                 :          0 :                         mpihelp_rshift(rp, rp, rsize, mod_shift_cnt);
     282   [ -  +  +  - ]:          3 :                 MPN_NORMALIZE(rp, rsize);
     283                 :            :         }
     284                 :            : 
     285         [ -  + ]:          3 :         if (negative_result && rsize) {
     286         [ #  # ]:          0 :                 if (mod_shift_cnt)
     287                 :          0 :                         mpihelp_rshift(mp, mp, msize, mod_shift_cnt);
     288                 :          0 :                 mpihelp_sub(rp, mp, msize, rp, rsize);
     289                 :          0 :                 rsize = msize;
     290                 :          0 :                 rsign = msign;
     291   [ #  #  #  # ]:          0 :                 MPN_NORMALIZE(rp, rsize);
     292                 :            :         }
     293                 :          3 :         res->nlimbs = rsize;
     294                 :          3 :         res->sign = rsign;
     295                 :            : 
     296                 :            : leave:
     297                 :            :         rc = 0;
     298                 :          3 : enomem:
     299                 :          3 :         mpihelp_release_karatsuba_ctx(&karactx);
     300         [ -  + ]:          3 :         if (assign_rp)
     301                 :          0 :                 mpi_assign_limb_space(res, rp, size);
     302         [ +  - ]:          3 :         if (mp_marker)
     303                 :          3 :                 mpi_free_limb_space(mp_marker);
     304         [ -  + ]:          3 :         if (bp_marker)
     305                 :          0 :                 mpi_free_limb_space(bp_marker);
     306         [ -  + ]:          3 :         if (ep_marker)
     307                 :          0 :                 mpi_free_limb_space(ep_marker);
     308         [ +  - ]:          3 :         if (xp_marker)
     309                 :          3 :                 mpi_free_limb_space(xp_marker);
     310         [ +  - ]:          3 :         if (tspace)
     311                 :          3 :                 mpi_free_limb_space(tspace);
     312                 :            :         return rc;
     313                 :            : }
     314                 :            : EXPORT_SYMBOL_GPL(mpi_powm);

Generated by: LCOV version 1.14