Switched to GPLv3.
[gnupg.git] / mpi / mpi-pow.c
1 /* mpi-pow.c  -  MPI functions
2  *      Copyright (C) 1994, 1996, 1998, 2000 Free Software Foundation, Inc.
3  *
4  * This file is part of GnuPG.
5  *
6  * GnuPG is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License as published by
8  * the Free Software Foundation; either version 3 of the License, or
9  * (at your option) any later version.
10  *
11  * GnuPG is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, see <http://www.gnu.org/licenses/>.
18  *
19  * Note: This code is heavily based on the GNU MP Library.
20  *       Actually it's the same code with only minor changes in the
21  *       way the data is stored; this is to support the abstraction
22  *       of an optional secure memory allocation which may be used
23  *       to avoid revealing of sensitive data due to paging etc.
24  *       The GNU MP Library itself is published under the LGPL;
25  *       however I decided to publish this code under the plain GPL.
26  */
27
28 #include <config.h>
29 #include <stdio.h>
30 #include <stdlib.h>
31 #include <string.h>
32 #include "mpi-internal.h"
33 #include "longlong.h"
34 #include <assert.h>
35
36
37 /****************
38  * RES = BASE ^ EXP mod MOD
39  */
40 void
41 mpi_powm( MPI res, MPI base, MPI exponent, MPI mod)
42 {
43     mpi_ptr_t  rp, ep, mp, bp;
44     mpi_size_t esize, msize, bsize, rsize;
45     int        esign, msign, bsign, rsign;
46     int        esec,  msec,  bsec,  rsec;
47     mpi_size_t size;
48     int mod_shift_cnt;
49     int negative_result;
50     mpi_ptr_t mp_marker=NULL, bp_marker=NULL, ep_marker=NULL;
51     mpi_ptr_t xp_marker=NULL;
52     int assign_rp=0;
53     mpi_ptr_t tspace = NULL;
54     mpi_size_t tsize=0;   /* to avoid compiler warning */
55                           /* fixme: we should check that the warning is void*/
56
57     esize = exponent->nlimbs;
58     msize = mod->nlimbs;
59     size = 2 * msize;
60     esign = exponent->sign;
61     msign = mod->sign;
62
63     esec = mpi_is_secure(exponent);
64     msec = mpi_is_secure(mod);
65     bsec = mpi_is_secure(base);
66     rsec = mpi_is_secure(res);
67
68     rp = res->d;
69     ep = exponent->d;
70
71     if( !msize )
72         msize = 1 / msize;          /* provoke a signal */
73
74     if( !esize ) {
75         /* Exponent is zero, result is 1 mod MOD, i.e., 1 or 0
76          * depending on if MOD equals 1.  */
77         rp[0] = 1;
78         res->nlimbs = (msize == 1 && mod->d[0] == 1) ? 0 : 1;
79         res->sign = 0;
80         goto leave;
81     }
82
83     /* Normalize MOD (i.e. make its most significant bit set) as required by
84      * mpn_divrem.  This will make the intermediate values in the calculation
85      * slightly larger, but the correct result is obtained after a final
86      * reduction using the original MOD value.  */
87     mp = mp_marker = mpi_alloc_limb_space(msize, msec);
88     count_leading_zeros( mod_shift_cnt, mod->d[msize-1] );
89     if( mod_shift_cnt )
90         mpihelp_lshift( mp, mod->d, msize, mod_shift_cnt );
91     else
92         MPN_COPY( mp, mod->d, msize );
93
94     bsize = base->nlimbs;
95     bsign = base->sign;
96     if( bsize > msize ) { /* The base is larger than the module. Reduce it. */
97         /* Allocate (BSIZE + 1) with space for remainder and quotient.
98          * (The quotient is (bsize - msize + 1) limbs.)  */
99         bp = bp_marker = mpi_alloc_limb_space( bsize + 1, bsec );
100         MPN_COPY( bp, base->d, bsize );
101         /* We don't care about the quotient, store it above the remainder,
102          * at BP + MSIZE.  */
103         mpihelp_divrem( bp + msize, 0, bp, bsize, mp, msize );
104         bsize = msize;
105         /* Canonicalize the base, since we are going to multiply with it
106          * quite a few times.  */
107         MPN_NORMALIZE( bp, bsize );
108     }
109     else
110         bp = base->d;
111
112     if( !bsize ) {
113         res->nlimbs = 0;
114         res->sign = 0;
115         goto leave;
116     }
117
118     if( res->alloced < size ) {
119         /* We have to allocate more space for RES.  If any of the input
120          * parameters are identical to RES, defer deallocation of the old
121          * space.  */
122         if( rp == ep || rp == mp || rp == bp ) {
123             rp = mpi_alloc_limb_space( size, rsec );
124             assign_rp = 1;
125         }
126         else {
127             mpi_resize( res, size );
128             rp = res->d;
129         }
130     }
131     else { /* Make BASE, EXPONENT and MOD not overlap with RES.  */
132         if( rp == bp ) {
133             /* RES and BASE are identical.  Allocate temp. space for BASE.  */
134             assert( !bp_marker );
135             bp = bp_marker = mpi_alloc_limb_space( bsize, bsec );
136             MPN_COPY(bp, rp, bsize);
137         }
138         if( rp == ep ) {
139             /* RES and EXPONENT are identical.  
140                Allocate temp. space for EXPONENT.  */
141             ep = ep_marker = mpi_alloc_limb_space( esize, esec );
142             MPN_COPY(ep, rp, esize);
143         }
144         if( rp == mp ) {
145             /* RES and MOD are identical.  Allocate temporary space for MOD.*/
146             assert( !mp_marker );
147             mp = mp_marker = mpi_alloc_limb_space( msize, msec );
148             MPN_COPY(mp, rp, msize);
149         }
150     }
151
152     MPN_COPY( rp, bp, bsize );
153     rsize = bsize;
154     rsign = bsign;
155
156     {
157         mpi_size_t i;
158         mpi_ptr_t xp = xp_marker = mpi_alloc_limb_space( 2 * (msize + 1), msec );
159         int c;
160         mpi_limb_t e;
161         mpi_limb_t carry_limb;
162         struct karatsuba_ctx karactx;
163
164         memset( &karactx, 0, sizeof karactx );
165         negative_result = (ep[0] & 1) && base->sign;
166
167         i = esize - 1;
168         e = ep[i];
169         count_leading_zeros (c, e);
170         e = (e << c) << 1;     /* shift the exp bits to the left, lose msb */
171         c = BITS_PER_MPI_LIMB - 1 - c;
172
173         /* Main loop.
174          *
175          * Make the result be pointed to alternately by XP and RP.  This
176          * helps us avoid block copying, which would otherwise be necessary
177          * with the overlap restrictions of mpihelp_divmod. With 50% probability
178          * the result after this loop will be in the area originally pointed
179          * by RP (==RES->d), and with 50% probability in the area originally
180          * pointed to by XP.
181          */
182
183         for(;;) {
184             while( c ) {
185                 mpi_ptr_t tp;
186                 mpi_size_t xsize;
187
188                 /*mpihelp_mul_n(xp, rp, rp, rsize);*/
189                 if( rsize < KARATSUBA_THRESHOLD )
190                     mpih_sqr_n_basecase( xp, rp, rsize );
191                 else {
192                     if( !tspace ) {
193                         tsize = 2 * rsize;
194                         tspace = mpi_alloc_limb_space( tsize, 0 );
195                     }
196                     else if( tsize < (2*rsize) ) {
197                         mpi_free_limb_space( tspace );
198                         tsize = 2 * rsize;
199                         tspace = mpi_alloc_limb_space( tsize, 0 );
200                     }
201                     mpih_sqr_n( xp, rp, rsize, tspace );
202                 }
203
204                 xsize = 2 * rsize;
205                 if( xsize > msize ) {
206                     mpihelp_divrem(xp + msize, 0, xp, xsize, mp, msize);
207                     xsize = msize;
208                 }
209
210                 tp = rp; rp = xp; xp = tp;
211                 rsize = xsize;
212
213                 if( (mpi_limb_signed_t)e < 0 ) {
214                     /*mpihelp_mul( xp, rp, rsize, bp, bsize );*/
215                     if( bsize < KARATSUBA_THRESHOLD ) {
216                         mpihelp_mul( xp, rp, rsize, bp, bsize );
217                     }
218                     else {
219                         mpihelp_mul_karatsuba_case(
220                                      xp, rp, rsize, bp, bsize, &karactx );
221                     }
222
223                     xsize = rsize + bsize;
224                     if( xsize > msize ) {
225                         mpihelp_divrem(xp + msize, 0, xp, xsize, mp, msize);
226                         xsize = msize;
227                     }
228
229                     tp = rp; rp = xp; xp = tp;
230                     rsize = xsize;
231                 }
232                 e <<= 1;
233                 c--;
234             }
235
236             i--;
237             if( i < 0 )
238                 break;
239             e = ep[i];
240             c = BITS_PER_MPI_LIMB;
241         }
242
243         /* We shifted MOD, the modulo reduction argument, left MOD_SHIFT_CNT
244          * steps.  Adjust the result by reducing it with the original MOD.
245          *
246          * Also make sure the result is put in RES->d (where it already
247          * might be, see above).
248          */
249         if( mod_shift_cnt ) {
250             carry_limb = mpihelp_lshift( res->d, rp, rsize, mod_shift_cnt);
251             rp = res->d;
252             if( carry_limb ) {
253                 rp[rsize] = carry_limb;
254                 rsize++;
255             }
256         }
257         else {
258             MPN_COPY( res->d, rp, rsize);
259             rp = res->d;
260         }
261
262         if( rsize >= msize ) {
263             mpihelp_divrem(rp + msize, 0, rp, rsize, mp, msize);
264             rsize = msize;
265         }
266
267         /* Remove any leading zero words from the result.  */
268         if( mod_shift_cnt )
269             mpihelp_rshift( rp, rp, rsize, mod_shift_cnt);
270         MPN_NORMALIZE (rp, rsize);
271
272         mpihelp_release_karatsuba_ctx( &karactx );
273     }
274
275     if( negative_result && rsize ) {
276         if( mod_shift_cnt )
277             mpihelp_rshift( mp, mp, msize, mod_shift_cnt);
278         mpihelp_sub( rp, mp, msize, rp, rsize);
279         rsize = msize;
280         rsign = msign;
281         MPN_NORMALIZE(rp, rsize);
282     }
283     res->nlimbs = rsize;
284     res->sign = rsign;
285
286   leave:
287     if( assign_rp ) mpi_assign_limb_space( res, rp, size );
288     if( mp_marker ) mpi_free_limb_space( mp_marker );
289     if( bp_marker ) mpi_free_limb_space( bp_marker );
290     if( ep_marker ) mpi_free_limb_space( ep_marker );
291     if( xp_marker ) mpi_free_limb_space( xp_marker );
292     if( tspace )    mpi_free_limb_space( tspace );
293 }
294