1
/* mpi-pow.c - MPI functions
2
* Copyright (C) 1994, 1996, 1998, 2000 Free Software Foundation, Inc.
4
* This file is part of GnuPG.
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.
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.
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
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.
33
#include "mpi-internal.h"
39
* RES = BASE ^ EXP mod MOD
42
mpi_powm( MPI res, MPI base, MPI exp, MPI mod)
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;
51
mpi_ptr_t mp_marker=NULL, bp_marker=NULL, ep_marker=NULL;
52
mpi_ptr_t xp_marker=NULL;
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*/
64
esec = mpi_is_secure(exp);
65
msec = mpi_is_secure(mod);
66
bsec = mpi_is_secure(base);
67
rsec = mpi_is_secure(res);
73
msize = 1 / msize; /* provoke a signal */
76
/* Exponent is zero, result is 1 mod MOD, i.e., 1 or 0
77
* depending on if MOD equals 1. */
79
res->nlimbs = (msize == 1 && mod->d[0] == 1) ? 0 : 1;
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] );
91
mpihelp_lshift( mp, mod->d, msize, mod_shift_cnt );
93
MPN_COPY( mp, mod->d, msize );
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,
104
mpihelp_divrem( bp + msize, 0, bp, bsize, mp, msize );
106
/* Canonicalize the base, since we are going to multiply with it
107
* quite a few times. */
108
MPN_NORMALIZE( bp, bsize );
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
123
if( rp == ep || rp == mp || rp == bp ) {
124
rp = mpi_alloc_limb_space( size, rsec );
128
mpi_resize( res, size );
132
else { /* Make BASE, EXP and MOD not overlap with RES. */
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);
140
/* RES and EXP are identical. Allocate temp. space for EXP. */
141
ep = ep_marker = mpi_alloc_limb_space( esize, esec );
142
MPN_COPY(ep, rp, esize);
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);
152
MPN_COPY( rp, bp, bsize );
158
mpi_ptr_t xp = xp_marker = mpi_alloc_limb_space( 2 * (msize + 1), msec );
161
mpi_limb_t carry_limb;
162
struct karatsuba_ctx karactx;
164
memset( &karactx, 0, sizeof karactx );
165
negative_result = (ep[0] & 1) && base->sign;
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;
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
188
/*mpihelp_mul_n(xp, rp, rp, rsize);*/
189
if( rsize < KARATSUBA_THRESHOLD )
190
mpih_sqr_n_basecase( xp, rp, rsize );
194
tspace = mpi_alloc_limb_space( tsize, 0 );
196
else if( tsize < (2*rsize) ) {
197
mpi_free_limb_space( tspace );
199
tspace = mpi_alloc_limb_space( tsize, 0 );
201
mpih_sqr_n( xp, rp, rsize, tspace );
205
if( xsize > msize ) {
206
mpihelp_divrem(xp + msize, 0, xp, xsize, mp, msize);
210
tp = rp; rp = xp; xp = tp;
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 );
219
mpihelp_mul_karatsuba_case(
220
xp, rp, rsize, bp, bsize, &karactx );
223
xsize = rsize + bsize;
224
if( xsize > msize ) {
225
mpihelp_divrem(xp + msize, 0, xp, xsize, mp, msize);
229
tp = rp; rp = xp; xp = tp;
240
c = BITS_PER_MPI_LIMB;
243
/* We shifted MOD, the modulo reduction argument, left MOD_SHIFT_CNT
244
* steps. Adjust the result by reducing it with the original MOD.
246
* Also make sure the result is put in RES->d (where it already
247
* might be, see above).
249
if( mod_shift_cnt ) {
250
carry_limb = mpihelp_lshift( res->d, rp, rsize, mod_shift_cnt);
253
rp[rsize] = carry_limb;
258
MPN_COPY( res->d, rp, rsize);
262
if( rsize >= msize ) {
263
mpihelp_divrem(rp + msize, 0, rp, rsize, mp, msize);
267
/* Remove any leading zero words from the result. */
269
mpihelp_rshift( rp, rp, rsize, mod_shift_cnt);
270
MPN_NORMALIZE (rp, rsize);
272
mpihelp_release_karatsuba_ctx( &karactx );
275
if( negative_result && rsize ) {
277
mpihelp_rshift( mp, mp, msize, mod_shift_cnt);
278
mpihelp_sub( rp, mp, msize, rp, rsize);
281
MPN_NORMALIZE(rp, rsize);
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 );
added
removed
mpi/mpi-pow.c
