85d6fd8fbb0fd67ffbc533f8395356b0119c23e3
[libgcrypt.git] / mpi / mpi-pow.c
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  */
40 void
41 gcry_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     _gcry_divide_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 }