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