29
29
#include <stdlib.h>
30
30
#include <string.h>
31
32
#include "mpi-internal.h"
32
33
#include "longlong.h"
37
37
* RES = BASE ^ EXPO mod MOD
40
gcry_mpi_powm( gcry_mpi_t res, gcry_mpi_t base, gcry_mpi_t expo, gcry_mpi_t mod)
40
gcry_mpi_powm (gcry_mpi_t res,
41
gcry_mpi_t base, gcry_mpi_t expo, gcry_mpi_t mod)
42
mpi_ptr_t rp, ep, mp, bp;
43
mpi_size_t esize, msize, bsize, rsize;
44
int msign, bsign, rsign;
45
int esec, msec, bsec, rsec;
49
mpi_ptr_t mp_marker=NULL, bp_marker=NULL, ep_marker=NULL;
50
mpi_ptr_t xp_marker=NULL;
51
unsigned int mp_nlimbs = 0, bp_nlimbs = 0, ep_nlimbs = 0;
52
unsigned int xp_nlimbs = 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*/
63
esec = mpi_is_secure(expo);
64
msec = mpi_is_secure(mod);
65
bsec = mpi_is_secure(base);
66
rsec = mpi_is_secure(res);
72
msize = 1 / msize; /* provoke a signal */
75
/* Exponent is zero, result is 1 mod MOD, i.e., 1 or 0
76
* depending on if MOD equals 1. */
78
res->nlimbs = (msize == 1 && mod->d[0] == 1) ? 0 : 1;
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_nlimbs = msec? msize:0;
88
mp = mp_marker = mpi_alloc_limb_space(msize, msec);
89
count_leading_zeros( mod_shift_cnt, mod->d[msize-1] );
91
_gcry_mpih_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_nlimbs = bsec ? (bsize + 1):0;
101
bp = bp_marker = mpi_alloc_limb_space( bsize + 1, bsec );
102
MPN_COPY( bp, base->d, bsize );
103
/* We don't care about the quotient, store it above the remainder,
105
_gcry_mpih_divrem( bp + msize, 0, bp, bsize, mp, msize );
107
/* Canonicalize the base, since we are going to multiply with it
108
* quite a few times. */
109
MPN_NORMALIZE( bp, bsize );
120
if( res->alloced < size ) {
121
/* We have to allocate more space for RES. If any of the input
122
* parameters are identical to RES, defer deallocation of the old
124
if( rp == ep || rp == mp || rp == bp ) {
125
rp = mpi_alloc_limb_space( size, rsec );
129
mpi_resize( res, size );
133
else { /* Make BASE, EXPO and MOD not overlap with RES. */
135
/* RES and BASE are identical. Allocate temp. space for BASE. */
136
assert( !bp_marker );
137
bp_nlimbs = bsec? bsize:0;
138
bp = bp_marker = mpi_alloc_limb_space( bsize, bsec );
139
MPN_COPY(bp, rp, bsize);
142
/* RES and EXPO are identical. Allocate temp. space for EXPO. */
143
ep_nlimbs = esec? esize:0;
144
ep = ep_marker = mpi_alloc_limb_space( esize, esec );
145
MPN_COPY(ep, rp, esize);
148
/* RES and MOD are identical. Allocate temporary space for MOD.*/
149
assert( !mp_marker );
150
mp_nlimbs = msec?msize:0;
151
mp = mp_marker = mpi_alloc_limb_space( msize, msec );
152
MPN_COPY(mp, rp, msize);
156
MPN_COPY( rp, bp, bsize );
165
mpi_limb_t carry_limb;
166
struct karatsuba_ctx karactx;
168
xp_nlimbs = msec? (2 * (msize + 1)):0;
169
xp = xp_marker = mpi_alloc_limb_space( 2 * (msize + 1), msec );
171
memset( &karactx, 0, sizeof karactx );
172
negative_result = (ep[0] & 1) && base->sign;
176
count_leading_zeros (c, e);
177
e = (e << c) << 1; /* shift the expo bits to the left, lose msb */
178
c = BITS_PER_MPI_LIMB - 1 - c;
182
* Make the result be pointed to alternately by XP and RP. This
183
* helps us avoid block copying, which would otherwise be necessary
184
* with the overlap restrictions of _gcry_mpih_divmod. With 50% probability
185
* the result after this loop will be in the area originally pointed
186
* by RP (==RES->d), and with 50% probability in the area originally
195
/*mpih_mul_n(xp, rp, rp, rsize);*/
196
if( rsize < KARATSUBA_THRESHOLD )
197
_gcry_mpih_sqr_n_basecase( xp, rp, rsize );
201
tspace = mpi_alloc_limb_space( tsize, 0 );
203
else if( tsize < (2*rsize) ) {
204
_gcry_mpi_free_limb_space (tspace, 0);
206
tspace = mpi_alloc_limb_space( tsize, 0 );
208
_gcry_mpih_sqr_n( xp, rp, rsize, tspace );
212
if( xsize > msize ) {
213
_gcry_mpih_divrem(xp + msize, 0, xp, xsize, mp, msize);
217
tp = rp; rp = xp; xp = tp;
220
if( (mpi_limb_signed_t)e < 0 ) {
221
/*mpih_mul( xp, rp, rsize, bp, bsize );*/
222
if( bsize < KARATSUBA_THRESHOLD ) {
223
_gcry_mpih_mul( xp, rp, rsize, bp, bsize );
226
_gcry_mpih_mul_karatsuba_case(
227
xp, rp, rsize, bp, bsize, &karactx );
230
xsize = rsize + bsize;
231
if( xsize > msize ) {
232
_gcry_mpih_divrem(xp + msize, 0, xp, xsize, mp, msize);
236
tp = rp; rp = xp; xp = tp;
247
c = BITS_PER_MPI_LIMB;
250
/* We shifted MOD, the modulo reduction argument, left MOD_SHIFT_CNT
251
* steps. Adjust the result by reducing it with the original MOD.
253
* Also make sure the result is put in RES->d (where it already
254
* might be, see above).
256
if( mod_shift_cnt ) {
257
carry_limb = _gcry_mpih_lshift( res->d, rp, rsize, mod_shift_cnt);
260
rp[rsize] = carry_limb;
265
MPN_COPY( res->d, rp, rsize);
269
if( rsize >= msize ) {
270
_gcry_mpih_divrem(rp + msize, 0, rp, rsize, mp, msize);
274
/* Remove any leading zero words from the result. */
276
_gcry_mpih_rshift( rp, rp, rsize, mod_shift_cnt);
277
MPN_NORMALIZE (rp, rsize);
279
_gcry_mpih_release_karatsuba_ctx( &karactx );
282
if( negative_result && rsize ) {
284
_gcry_mpih_rshift( mp, mp, msize, mod_shift_cnt);
285
_gcry_mpih_sub( rp, mp, msize, rp, rsize);
288
MPN_NORMALIZE(rp, rsize);
294
if( assign_rp ) _gcry_mpi_assign_limb_space( res, rp, size );
295
if( mp_marker ) _gcry_mpi_free_limb_space( mp_marker, mp_nlimbs );
296
if( bp_marker ) _gcry_mpi_free_limb_space( bp_marker, bp_nlimbs );
297
if( ep_marker ) _gcry_mpi_free_limb_space( ep_marker, ep_nlimbs );
298
if( xp_marker ) _gcry_mpi_free_limb_space( xp_marker, xp_nlimbs );
299
if( tspace ) _gcry_mpi_free_limb_space( tspace, 0 );
43
/* Pointer to the limbs of the arguments, their size and signs. */
44
mpi_ptr_t rp, ep, mp, bp;
45
mpi_size_t esize, msize, bsize, rsize;
46
int msign, bsign, rsign;
47
/* Flags telling the secure allocation status of the arguments. */
48
int esec, msec, bsec, rsec;
49
/* Size of the result including space for temporary values. */
54
mpi_ptr_t mp_marker = NULL;
55
mpi_ptr_t bp_marker = NULL;
56
mpi_ptr_t ep_marker = NULL;
57
mpi_ptr_t xp_marker = NULL;
58
unsigned int mp_nlimbs = 0;
59
unsigned int bp_nlimbs = 0;
60
unsigned int ep_nlimbs = 0;
61
unsigned int xp_nlimbs = 0;
62
mpi_ptr_t tspace = NULL;
71
esec = mpi_is_secure(expo);
72
msec = mpi_is_secure(mod);
73
bsec = mpi_is_secure(base);
74
rsec = mpi_is_secure(res);
80
msize = 1 / msize; /* Provoke a signal. */
84
/* Exponent is zero, result is 1 mod MOD, i.e., 1 or 0 depending
85
on if MOD equals 1. */
87
res->nlimbs = (msize == 1 && mod->d[0] == 1) ? 0 : 1;
92
/* Normalize MOD (i.e. make its most significant bit set) as
93
required by mpn_divrem. This will make the intermediate values
94
in the calculation slightly larger, but the correct result is
95
obtained after a final reduction using the original MOD value. */
96
mp_nlimbs = msec? msize:0;
97
mp = mp_marker = mpi_alloc_limb_space(msize, msec);
98
count_leading_zeros (mod_shift_cnt, mod->d[msize-1]);
100
_gcry_mpih_lshift (mp, mod->d, msize, mod_shift_cnt);
102
MPN_COPY( mp, mod->d, msize );
104
bsize = base->nlimbs;
108
/* The base is larger than the module. Reduce it.
110
Allocate (BSIZE + 1) with space for remainder and quotient.
111
(The quotient is (bsize - msize + 1) limbs.) */
112
bp_nlimbs = bsec ? (bsize + 1):0;
113
bp = bp_marker = mpi_alloc_limb_space( bsize + 1, bsec );
114
MPN_COPY ( bp, base->d, bsize );
115
/* We don't care about the quotient, store it above the
116
* remainder, at BP + MSIZE. */
117
_gcry_mpih_divrem( bp + msize, 0, bp, bsize, mp, msize );
119
/* Canonicalize the base, since we are going to multiply with it
120
quite a few times. */
121
MPN_NORMALIZE( bp, bsize );
134
/* Make BASE, EXPO and MOD not overlap with RES. */
137
/* RES and BASE are identical. Allocate temp. space for BASE. */
138
gcry_assert (!bp_marker);
139
bp_nlimbs = bsec? bsize:0;
140
bp = bp_marker = mpi_alloc_limb_space( bsize, bsec );
141
MPN_COPY(bp, rp, bsize);
145
/* RES and EXPO are identical. Allocate temp. space for EXPO. */
146
ep_nlimbs = esec? esize:0;
147
ep = ep_marker = mpi_alloc_limb_space( esize, esec );
148
MPN_COPY(ep, rp, esize);
152
/* RES and MOD are identical. Allocate temporary space for MOD.*/
153
gcry_assert (!mp_marker);
154
mp_nlimbs = msec?msize:0;
155
mp = mp_marker = mpi_alloc_limb_space( msize, msec );
156
MPN_COPY(mp, rp, msize);
159
/* Copy base to the result. */
160
if (res->alloced < size)
162
mpi_resize (res, size);
165
MPN_COPY ( rp, bp, bsize );
169
/* Main processing. */
175
mpi_limb_t carry_limb;
176
struct karatsuba_ctx karactx;
178
xp_nlimbs = msec? (2 * (msize + 1)):0;
179
xp = xp_marker = mpi_alloc_limb_space( 2 * (msize + 1), msec );
181
memset( &karactx, 0, sizeof karactx );
182
negative_result = (ep[0] & 1) && base->sign;
186
count_leading_zeros (c, e);
187
e = (e << c) << 1; /* Shift the expo bits to the left, lose msb. */
188
c = BITS_PER_MPI_LIMB - 1 - c;
192
Make the result be pointed to alternately by XP and RP. This
193
helps us avoid block copying, which would otherwise be
194
necessary with the overlap restrictions of
195
_gcry_mpih_divmod. With 50% probability the result after this
196
loop will be in the area originally pointed by RP (==RES->d),
197
and with 50% probability in the area originally pointed to by XP. */
205
/*mpih_mul_n(xp, rp, rp, rsize);*/
206
if ( rsize < KARATSUBA_THRESHOLD )
207
_gcry_mpih_sqr_n_basecase( xp, rp, rsize );
213
tspace = mpi_alloc_limb_space( tsize, 0 );
215
else if ( tsize < (2*rsize) )
217
_gcry_mpi_free_limb_space (tspace, 0);
219
tspace = mpi_alloc_limb_space (tsize, 0 );
221
_gcry_mpih_sqr_n (xp, rp, rsize, tspace);
227
_gcry_mpih_divrem(xp + msize, 0, xp, xsize, mp, msize);
231
tp = rp; rp = xp; xp = tp;
234
if ( (mpi_limb_signed_t)e < 0 )
236
/*mpih_mul( xp, rp, rsize, bp, bsize );*/
237
if( bsize < KARATSUBA_THRESHOLD )
238
_gcry_mpih_mul ( xp, rp, rsize, bp, bsize );
240
_gcry_mpih_mul_karatsuba_case (xp, rp, rsize, bp, bsize,
243
xsize = rsize + bsize;
246
_gcry_mpih_divrem(xp + msize, 0, xp, xsize, mp, msize);
250
tp = rp; rp = xp; xp = tp;
261
c = BITS_PER_MPI_LIMB;
264
/* We shifted MOD, the modulo reduction argument, left
265
MOD_SHIFT_CNT steps. Adjust the result by reducing it with the
268
Also make sure the result is put in RES->d (where it already
269
might be, see above). */
272
carry_limb = _gcry_mpih_lshift( res->d, rp, rsize, mod_shift_cnt);
276
rp[rsize] = carry_limb;
280
else if (res->d != rp)
282
MPN_COPY (res->d, rp, rsize);
286
if ( rsize >= msize )
288
_gcry_mpih_divrem(rp + msize, 0, rp, rsize, mp, msize);
292
/* Remove any leading zero words from the result. */
294
_gcry_mpih_rshift( rp, rp, rsize, mod_shift_cnt);
295
MPN_NORMALIZE (rp, rsize);
297
_gcry_mpih_release_karatsuba_ctx (&karactx );
300
/* Fixup for negative results. */
301
if ( negative_result && rsize )
304
_gcry_mpih_rshift( mp, mp, msize, mod_shift_cnt);
305
_gcry_mpih_sub( rp, mp, msize, rp, rsize);
308
MPN_NORMALIZE(rp, rsize);
310
gcry_assert (res->d == rp);
316
_gcry_mpi_free_limb_space( mp_marker, mp_nlimbs );
318
_gcry_mpi_free_limb_space( bp_marker, bp_nlimbs );
320
_gcry_mpi_free_limb_space( ep_marker, ep_nlimbs );
322
_gcry_mpi_free_limb_space( xp_marker, xp_nlimbs );
324
_gcry_mpi_free_limb_space( tspace, 0 );