source: grub-pc/trunk/fuentes/grub-core/lib/libgcrypt/mpi/mpi-pow.c @ 22

Last change on this file since 22 was 22, checked in by mabarracus, 4 years ago

updated version and apply net.ifnames=0 into debian/rules

File size: 10.0 KB
Line 
1/* mpi-pow.c  -  MPI functions for exponentiation
2 * Copyright (C) 1994, 1996, 1998, 2000, 2002
3 *               2003  Free Software Foundation, Inc.
4 *               2013  g10 Code GmbH
5 *
6 * This file is part of Libgcrypt.
7 *
8 * Libgcrypt is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU Lesser General Public License as
10 * published by the Free Software Foundation; either version 2.1 of
11 * the License, or (at your option) any later version.
12 *
13 * Libgcrypt is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16 * GNU Lesser General Public License for more details.
17 *
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with this program; if not, see <http://www.gnu.org/licenses/>.
20 *
21 * Note: This code is heavily based on the GNU MP Library.
22 *       Actually it's the same code with only minor changes in the
23 *       way the data is stored; this is to support the abstraction
24 *       of an optional secure memory allocation which may be used
25 *       to avoid revealing of sensitive data due to paging etc.
26 */
27
28#include <config.h>
29#include <stdio.h>
30#include <stdlib.h>
31#include <string.h>
32
33#include "mpi-internal.h"
34#include "longlong.h"
35
36
37/****************
38 * RES = BASE ^ EXPO mod MOD
39 */
40void
41gcry_mpi_powm (gcry_mpi_t res,
42               gcry_mpi_t base, gcry_mpi_t expo, gcry_mpi_t mod)
43{
44  /* Pointer to the limbs of the arguments, their size and signs. */
45  mpi_ptr_t  rp, ep, mp, bp;
46  mpi_size_t esize, msize, bsize, rsize;
47  int               msign, bsign, rsign;
48  /* Flags telling the secure allocation status of the arguments.  */
49  int        esec,  msec,  bsec;
50  /* Size of the result including space for temporary values.  */
51  mpi_size_t size;
52  /* Helper.  */
53  int mod_shift_cnt;
54  int negative_result;
55  mpi_ptr_t mp_marker = NULL;
56  mpi_ptr_t bp_marker = NULL;
57  mpi_ptr_t ep_marker = NULL;
58  mpi_ptr_t xp_marker = NULL;
59  unsigned int mp_nlimbs = 0;
60  unsigned int bp_nlimbs = 0;
61  unsigned int ep_nlimbs = 0;
62  unsigned int xp_nlimbs = 0;
63  mpi_ptr_t tspace = NULL;
64  mpi_size_t tsize = 0;
65
66
67  esize = expo->nlimbs;
68  msize = mod->nlimbs;
69  size = 2 * msize;
70  msign = mod->sign;
71
72  esec = mpi_is_secure(expo);
73  msec = mpi_is_secure(mod);
74  bsec = mpi_is_secure(base);
75
76  rp = res->d;
77  ep = expo->d;
78
79  if (!msize)
80    grub_fatal ("mpi division by zero");
81
82  if (!esize)
83    {
84      /* Exponent is zero, result is 1 mod MOD, i.e., 1 or 0 depending
85         on if MOD equals 1.  */
86      res->nlimbs = (msize == 1 && mod->d[0] == 1) ? 0 : 1;
87      if (res->nlimbs)
88        {
89          RESIZE_IF_NEEDED (res, 1);
90          rp = res->d;
91          rp[0] = 1;
92        }
93      res->sign = 0;
94      goto leave;
95    }
96
97  /* Normalize MOD (i.e. make its most significant bit set) as
98     required by mpn_divrem.  This will make the intermediate values
99     in the calculation slightly larger, but the correct result is
100     obtained after a final reduction using the original MOD value. */
101  mp_nlimbs = msec? msize:0;
102  mp = mp_marker = mpi_alloc_limb_space(msize, msec);
103  count_leading_zeros (mod_shift_cnt, mod->d[msize-1]);
104  if (mod_shift_cnt)
105    _gcry_mpih_lshift (mp, mod->d, msize, mod_shift_cnt);
106  else
107    MPN_COPY( mp, mod->d, msize );
108
109  bsize = base->nlimbs;
110  bsign = base->sign;
111  if (bsize > msize)
112    {
113      /* The base is larger than the module.  Reduce it.
114
115         Allocate (BSIZE + 1) with space for remainder and quotient.
116         (The quotient is (bsize - msize + 1) limbs.)  */
117      bp_nlimbs = bsec ? (bsize + 1):0;
118      bp = bp_marker = mpi_alloc_limb_space( bsize + 1, bsec );
119      MPN_COPY ( bp, base->d, bsize );
120      /* We don't care about the quotient, store it above the
121       * remainder, at BP + MSIZE.  */
122      _gcry_mpih_divrem( bp + msize, 0, bp, bsize, mp, msize );
123      bsize = msize;
124      /* Canonicalize the base, since we are going to multiply with it
125         quite a few times.  */
126      MPN_NORMALIZE( bp, bsize );
127    }
128  else
129    bp = base->d;
130
131  if (!bsize)
132    {
133      res->nlimbs = 0;
134      res->sign = 0;
135      goto leave;
136    }
137
138
139  /* Make BASE, EXPO and MOD not overlap with RES.  */
140  if ( rp == bp )
141    {
142      /* RES and BASE are identical.  Allocate temp. space for BASE.  */
143      gcry_assert (!bp_marker);
144      bp_nlimbs = bsec? bsize:0;
145      bp = bp_marker = mpi_alloc_limb_space( bsize, bsec );
146      MPN_COPY(bp, rp, bsize);
147    }
148  if ( rp == ep )
149    {
150      /* RES and EXPO are identical.  Allocate temp. space for EXPO.  */
151      ep_nlimbs = esec? esize:0;
152      ep = ep_marker = mpi_alloc_limb_space( esize, esec );
153      MPN_COPY(ep, rp, esize);
154    }
155  if ( rp == mp )
156    {
157      /* RES and MOD are identical.  Allocate temporary space for MOD.*/
158      gcry_assert (!mp_marker);
159      mp_nlimbs = msec?msize:0;
160      mp = mp_marker = mpi_alloc_limb_space( msize, msec );
161      MPN_COPY(mp, rp, msize);
162    }
163
164  /* Copy base to the result.  */
165  if (res->alloced < size)
166    {
167      mpi_resize (res, size);
168      rp = res->d;
169    }
170  MPN_COPY ( rp, bp, bsize );
171  rsize = bsize;
172  rsign = bsign;
173
174  /* Main processing.  */
175  {
176    mpi_size_t i;
177    mpi_ptr_t xp;
178    int c;
179    mpi_limb_t e;
180    mpi_limb_t carry_limb;
181    struct karatsuba_ctx karactx;
182
183    xp_nlimbs = msec? (2 * (msize + 1)):0;
184    xp = xp_marker = mpi_alloc_limb_space( 2 * (msize + 1), msec );
185
186    memset( &karactx, 0, sizeof karactx );
187    negative_result = (ep[0] & 1) && base->sign;
188
189    i = esize - 1;
190    e = ep[i];
191    count_leading_zeros (c, e);
192    e = (e << c) << 1;     /* Shift the expo bits to the left, lose msb.  */
193    c = BITS_PER_MPI_LIMB - 1 - c;
194
195    /* Main loop.
196
197       Make the result be pointed to alternately by XP and RP.  This
198       helps us avoid block copying, which would otherwise be
199       necessary with the overlap restrictions of
200       _gcry_mpih_divmod. With 50% probability the result after this
201       loop will be in the area originally pointed by RP (==RES->d),
202       and with 50% probability in the area originally pointed to by XP. */
203    for (;;)
204      {
205        while (c)
206          {
207            mpi_ptr_t tp;
208            mpi_size_t xsize;
209
210            /*mpih_mul_n(xp, rp, rp, rsize);*/
211            if ( rsize < KARATSUBA_THRESHOLD )
212              _gcry_mpih_sqr_n_basecase( xp, rp, rsize );
213            else
214              {
215                if ( !tspace )
216                  {
217                    tsize = 2 * rsize;
218                    tspace = mpi_alloc_limb_space( tsize, 0 );
219                  }
220                else if ( tsize < (2*rsize) )
221                  {
222                    _gcry_mpi_free_limb_space (tspace, 0);
223                    tsize = 2 * rsize;
224                    tspace = mpi_alloc_limb_space (tsize, 0 );
225                  }
226                _gcry_mpih_sqr_n (xp, rp, rsize, tspace);
227              }
228
229            xsize = 2 * rsize;
230            if ( xsize > msize )
231              {
232                _gcry_mpih_divrem(xp + msize, 0, xp, xsize, mp, msize);
233                xsize = msize;
234              }
235
236            tp = rp; rp = xp; xp = tp;
237            rsize = xsize;
238
239            /* To mitigate the Yarom/Falkner flush+reload cache
240             * side-channel attack on the RSA secret exponent, we do
241             * the multiplication regardless of the value of the
242             * high-bit of E.  But to avoid this performance penalty
243             * we do it only if the exponent has been stored in secure
244             * memory and we can thus assume it is a secret exponent.  */
245            if (esec || (mpi_limb_signed_t)e < 0)
246              {
247                /*mpih_mul( xp, rp, rsize, bp, bsize );*/
248                if( bsize < KARATSUBA_THRESHOLD )
249                  _gcry_mpih_mul ( xp, rp, rsize, bp, bsize );
250                else
251                  _gcry_mpih_mul_karatsuba_case (xp, rp, rsize, bp, bsize,
252                                                 &karactx);
253
254                xsize = rsize + bsize;
255                if ( xsize > msize )
256                  {
257                    _gcry_mpih_divrem(xp + msize, 0, xp, xsize, mp, msize);
258                    xsize = msize;
259                  }
260              }
261            if ( (mpi_limb_signed_t)e < 0 )
262              {
263                tp = rp; rp = xp; xp = tp;
264                rsize = xsize;
265              }
266            e <<= 1;
267            c--;
268          }
269
270        i--;
271        if ( i < 0 )
272          break;
273        e = ep[i];
274        c = BITS_PER_MPI_LIMB;
275      }
276
277    /* We shifted MOD, the modulo reduction argument, left
278       MOD_SHIFT_CNT steps.  Adjust the result by reducing it with the
279       original MOD.
280
281       Also make sure the result is put in RES->d (where it already
282       might be, see above).  */
283    if ( mod_shift_cnt )
284      {
285        carry_limb = _gcry_mpih_lshift( res->d, rp, rsize, mod_shift_cnt);
286        rp = res->d;
287        if ( carry_limb )
288          {
289            rp[rsize] = carry_limb;
290            rsize++;
291          }
292      }
293    else if (res->d != rp)
294      {
295        MPN_COPY (res->d, rp, rsize);
296        rp = res->d;
297      }
298
299    if ( rsize >= msize )
300      {
301        _gcry_mpih_divrem(rp + msize, 0, rp, rsize, mp, msize);
302        rsize = msize;
303      }
304
305    /* Remove any leading zero words from the result.  */
306    if ( mod_shift_cnt )
307      _gcry_mpih_rshift( rp, rp, rsize, mod_shift_cnt);
308    MPN_NORMALIZE (rp, rsize);
309
310    _gcry_mpih_release_karatsuba_ctx (&karactx );
311  }
312
313  /* Fixup for negative results.  */
314  if ( negative_result && rsize )
315    {
316      if ( mod_shift_cnt )
317        _gcry_mpih_rshift( mp, mp, msize, mod_shift_cnt);
318      _gcry_mpih_sub( rp, mp, msize, rp, rsize);
319      rsize = msize;
320      rsign = msign;
321      MPN_NORMALIZE(rp, rsize);
322    }
323  gcry_assert (res->d == rp);
324  res->nlimbs = rsize;
325  res->sign = rsign;
326
327 leave:
328  if (mp_marker)
329    _gcry_mpi_free_limb_space( mp_marker, mp_nlimbs );
330  if (bp_marker)
331    _gcry_mpi_free_limb_space( bp_marker, bp_nlimbs );
332  if (ep_marker)
333    _gcry_mpi_free_limb_space( ep_marker, ep_nlimbs );
334  if (xp_marker)
335    _gcry_mpi_free_limb_space( xp_marker, xp_nlimbs );
336  if (tspace)
337    _gcry_mpi_free_limb_space( tspace, 0 );
338}
Note: See TracBrowser for help on using the repository browser.