« back to all changes in this revision
Viewing changes to mpi/mpi-pow.c
- browse files at revision 18
- compare with another revision
- download diff
- download tarball
- view history from revision 18
- Committer: Bazaar Package Importer
- Author(s): Bhavani Shankar
- Date: 2009-05-16 20:13:32 UTC
- mfrom: (1.1.6 upstream) (2.1.3 squeeze)
- Revision ID: james.westby@ubuntu.com-20090516201332-czkobpu32w318i16
Tags: 1.4.4-2ubuntu1
* Merge from Debian unstable (LP: #364535), remaining changes:
- Add libgcrypt11-udeb for use by cryptsetup-udeb.
- Add clean-la.mk, and add a symlink for the .la
- Install to /lib.
- Add libgcrypt11-udeb for use by cryptsetup-udeb.
- Add clean-la.mk, and add a symlink for the .la
- Install to /lib.
- files added:
- cipher/hash-common.c
- random
- files removed:
- BUGS
- files modified:
- AUTHORS
added
removed
mpi/mpi-pow.c
1
/* mpi-pow.c - MPI functions
2
* Copyright (C) 1994, 1996, 1998, 2000, 2002, 2003 Free Software Foundation, Inc.
1
/* mpi-pow.c - MPI functions for exponentiation
2
* Copyright (C) 1994, 1996, 1998, 2000, 2002
3
* 2003 Free Software Foundation, Inc.
3
4
*
4
5
* This file is part of Libgcrypt.
5
6
*
14
15
* GNU Lesser General Public License for more details.
15
16
*
16
17
* You should have received a copy of the GNU Lesser General Public
17
* License along with this program; if not, write to the Free Software
18
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
18
* License along with this program; if not, see <http://www.gnu.org/licenses/>.
19
19
*
20
20
* Note: This code is heavily based on the GNU MP Library.
21
21
* Actually it's the same code with only minor changes in the
28
28
#include <stdio.h>
29
29
#include <stdlib.h>
30
30
#include <string.h>
31
31
32
#include "mpi-internal.h"
32
33
#include "longlong.h"
33
#include <assert.h>
34
34
35
35
36
36
/****************
37
37
* RES = BASE ^ EXPO mod MOD
38
38
*/
39
39
void
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)
41
42
{
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;
46
mpi_size_t size;
47
int mod_shift_cnt;
48
int negative_result;
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;
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 = expo->nlimbs;
59
msize = mod->nlimbs;
60
size = 2 * msize;
61
msign = mod->sign;
62
63
esec = mpi_is_secure(expo);
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 = expo->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_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] );
90
if( mod_shift_cnt )
91
_gcry_mpih_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_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,
104
* at BP + MSIZE. */
105
_gcry_mpih_divrem( bp + msize, 0, bp, bsize, mp, msize );
106
bsize = msize;
107
/* Canonicalize the base, since we are going to multiply with it
108
* quite a few times. */
109
MPN_NORMALIZE( bp, bsize );
110
}
111
else
112
bp = base->d;
113
114
if( !bsize ) {
115
res->nlimbs = 0;
116
res->sign = 0;
117
goto leave;
118
}
119
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
123
* space. */
124
if( rp == ep || rp == mp || rp == bp ) {
125
rp = mpi_alloc_limb_space( size, rsec );
126
assign_rp = 1;
127
}
128
else {
129
mpi_resize( res, size );
130
rp = res->d;
131
}
132
}
133
else { /* Make BASE, EXPO and MOD not overlap with RES. */
134
if( rp == bp ) {
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);
140
}
141
if( rp == ep ) {
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);
146
}
147
if( rp == mp ) {
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);
153
}
154
}
155
156
MPN_COPY( rp, bp, bsize );
157
rsize = bsize;
158
rsign = bsign;
159
160
{
161
mpi_size_t i;
162
mpi_ptr_t xp;
163
int c;
164
mpi_limb_t e;
165
mpi_limb_t carry_limb;
166
struct karatsuba_ctx karactx;
167
168
xp_nlimbs = msec? (2 * (msize + 1)):0;
169
xp = xp_marker = mpi_alloc_limb_space( 2 * (msize + 1), msec );
170
171
memset( &karactx, 0, sizeof karactx );
172
negative_result = (ep[0] & 1) && base->sign;
173
174
i = esize - 1;
175
e = ep[i];
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;
179
180
/* Main loop.
181
*
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
187
* pointed to by XP.
188
*/
189
190
for(;;) {
191
while( c ) {
192
mpi_ptr_t tp;
193
mpi_size_t xsize;
194
195
/*mpih_mul_n(xp, rp, rp, rsize);*/
196
if( rsize < KARATSUBA_THRESHOLD )
197
_gcry_mpih_sqr_n_basecase( xp, rp, rsize );
198
else {
199
if( !tspace ) {
200
tsize = 2 * rsize;
201
tspace = mpi_alloc_limb_space( tsize, 0 );
202
}
203
else if( tsize < (2*rsize) ) {
204
_gcry_mpi_free_limb_space (tspace, 0);
205
tsize = 2 * rsize;
206
tspace = mpi_alloc_limb_space( tsize, 0 );
207
}
208
_gcry_mpih_sqr_n( xp, rp, rsize, tspace );
209
}
210
211
xsize = 2 * rsize;
212
if( xsize > msize ) {
213
_gcry_mpih_divrem(xp + msize, 0, xp, xsize, mp, msize);
214
xsize = msize;
215
}
216
217
tp = rp; rp = xp; xp = tp;
218
rsize = xsize;
219
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 );
224
}
225
else {
226
_gcry_mpih_mul_karatsuba_case(
227
xp, rp, rsize, bp, bsize, &karactx );
228
}
229
230
xsize = rsize + bsize;
231
if( xsize > msize ) {
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
e <<= 1;
240
c--;
241
}
242
243
i--;
244
if( i < 0 )
245
break;
246
e = ep[i];
247
c = BITS_PER_MPI_LIMB;
248
}
249
250
/* We shifted MOD, the modulo reduction argument, left MOD_SHIFT_CNT
251
* steps. Adjust the result by reducing it with the original MOD.
252
*
253
* Also make sure the result is put in RES->d (where it already
254
* might be, see above).
255
*/
256
if( mod_shift_cnt ) {
257
carry_limb = _gcry_mpih_lshift( res->d, rp, rsize, mod_shift_cnt);
258
rp = res->d;
259
if( carry_limb ) {
260
rp[rsize] = carry_limb;
261
rsize++;
262
}
263
}
264
else {
265
MPN_COPY( res->d, rp, rsize);
266
rp = res->d;
267
}
268
269
if( rsize >= msize ) {
270
_gcry_mpih_divrem(rp + msize, 0, rp, rsize, mp, msize);
271
rsize = msize;
272
}
273
274
/* Remove any leading zero words from the result. */
275
if( mod_shift_cnt )
276
_gcry_mpih_rshift( rp, rp, rsize, mod_shift_cnt);
277
MPN_NORMALIZE (rp, rsize);
278
279
_gcry_mpih_release_karatsuba_ctx( &karactx );
280
}
281
282
if( negative_result && rsize ) {
283
if( mod_shift_cnt )
284
_gcry_mpih_rshift( mp, mp, msize, mod_shift_cnt);
285
_gcry_mpih_sub( rp, mp, msize, rp, rsize);
286
rsize = msize;
287
rsign = msign;
288
MPN_NORMALIZE(rp, rsize);
289
}
290
res->nlimbs = rsize;
291
res->sign = rsign;
292
293
leave:
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. */
50
mpi_size_t size;
51
/* Helper. */
52
int mod_shift_cnt;
53
int negative_result;
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;
63
mpi_size_t tsize = 0;
64
65
66
esize = expo->nlimbs;
67
msize = mod->nlimbs;
68
size = 2 * msize;
69
msign = mod->sign;
70
71
esec = mpi_is_secure(expo);
72
msec = mpi_is_secure(mod);
73
bsec = mpi_is_secure(base);
74
rsec = mpi_is_secure(res);
75
76
rp = res->d;
77
ep = expo->d;
78
79
if (!msize)
80
msize = 1 / msize; /* Provoke a signal. */
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
rp[0] = 1;
87
res->nlimbs = (msize == 1 && mod->d[0] == 1) ? 0 : 1;
88
res->sign = 0;
89
goto leave;
90
}
91
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]);
99
if (mod_shift_cnt)
100
_gcry_mpih_lshift (mp, mod->d, msize, mod_shift_cnt);
101
else
102
MPN_COPY( mp, mod->d, msize );
103
104
bsize = base->nlimbs;
105
bsign = base->sign;
106
if (bsize > msize)
107
{
108
/* The base is larger than the module. Reduce it.
109
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 );
118
bsize = msize;
119
/* Canonicalize the base, since we are going to multiply with it
120
quite a few times. */
121
MPN_NORMALIZE( bp, bsize );
122
}
123
else
124
bp = base->d;
125
126
if (!bsize)
127
{
128
res->nlimbs = 0;
129
res->sign = 0;
130
goto leave;
131
}
132
133
134
/* Make BASE, EXPO and MOD not overlap with RES. */
135
if ( rp == bp )
136
{
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);
142
}
143
if ( rp == ep )
144
{
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);
149
}
150
if ( rp == mp )
151
{
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);
157
}
158
159
/* Copy base to the result. */
160
if (res->alloced < size)
161
{
162
mpi_resize (res, size);
163
rp = res->d;
164
}
165
MPN_COPY ( rp, bp, bsize );
166
rsize = bsize;
167
rsign = bsign;
168
169
/* Main processing. */
170
{
171
mpi_size_t i;
172
mpi_ptr_t xp;
173
int c;
174
mpi_limb_t e;
175
mpi_limb_t carry_limb;
176
struct karatsuba_ctx karactx;
177
178
xp_nlimbs = msec? (2 * (msize + 1)):0;
179
xp = xp_marker = mpi_alloc_limb_space( 2 * (msize + 1), msec );
180
181
memset( &karactx, 0, sizeof karactx );
182
negative_result = (ep[0] & 1) && base->sign;
183
184
i = esize - 1;
185
e = ep[i];
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;
189
190
/* Main loop.
191
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. */
198
for (;;)
199
{
200
while (c)
201
{
202
mpi_ptr_t tp;
203
mpi_size_t xsize;
204
205
/*mpih_mul_n(xp, rp, rp, rsize);*/
206
if ( rsize < KARATSUBA_THRESHOLD )
207
_gcry_mpih_sqr_n_basecase( xp, rp, rsize );
208
else
209
{
210
if ( !tspace )
211
{
212
tsize = 2 * rsize;
213
tspace = mpi_alloc_limb_space( tsize, 0 );
214
}
215
else if ( tsize < (2*rsize) )
216
{
217
_gcry_mpi_free_limb_space (tspace, 0);
218
tsize = 2 * rsize;
219
tspace = mpi_alloc_limb_space (tsize, 0 );
220
}
221
_gcry_mpih_sqr_n (xp, rp, rsize, tspace);
222
}
223
224
xsize = 2 * rsize;
225
if ( xsize > msize )
226
{
227
_gcry_mpih_divrem(xp + msize, 0, xp, xsize, mp, msize);
228
xsize = msize;
229
}
230
231
tp = rp; rp = xp; xp = tp;
232
rsize = xsize;
233
234
if ( (mpi_limb_signed_t)e < 0 )
235
{
236
/*mpih_mul( xp, rp, rsize, bp, bsize );*/
237
if( bsize < KARATSUBA_THRESHOLD )
238
_gcry_mpih_mul ( xp, rp, rsize, bp, bsize );
239
else
240
_gcry_mpih_mul_karatsuba_case (xp, rp, rsize, bp, bsize,
241
&karactx);
242
243
xsize = rsize + bsize;
244
if ( xsize > msize )
245
{
246
_gcry_mpih_divrem(xp + msize, 0, xp, xsize, mp, msize);
247
xsize = msize;
248
}
249
250
tp = rp; rp = xp; xp = tp;
251
rsize = xsize;
252
}
253
e <<= 1;
254
c--;
255
}
256
257
i--;
258
if ( i < 0 )
259
break;
260
e = ep[i];
261
c = BITS_PER_MPI_LIMB;
262
}
263
264
/* We shifted MOD, the modulo reduction argument, left
265
MOD_SHIFT_CNT steps. Adjust the result by reducing it with the
266
original MOD.
267
268
Also make sure the result is put in RES->d (where it already
269
might be, see above). */
270
if ( mod_shift_cnt )
271
{
272
carry_limb = _gcry_mpih_lshift( res->d, rp, rsize, mod_shift_cnt);
273
rp = res->d;
274
if ( carry_limb )
275
{
276
rp[rsize] = carry_limb;
277
rsize++;
278
}
279
}
280
else if (res->d != rp)
281
{
282
MPN_COPY (res->d, rp, rsize);
283
rp = res->d;
284
}
285
286
if ( rsize >= msize )
287
{
288
_gcry_mpih_divrem(rp + msize, 0, rp, rsize, mp, msize);
289
rsize = msize;
290
}
291
292
/* Remove any leading zero words from the result. */
293
if ( mod_shift_cnt )
294
_gcry_mpih_rshift( rp, rp, rsize, mod_shift_cnt);
295
MPN_NORMALIZE (rp, rsize);
296
297
_gcry_mpih_release_karatsuba_ctx (&karactx );
298
}
299
300
/* Fixup for negative results. */
301
if ( negative_result && rsize )
302
{
303
if ( mod_shift_cnt )
304
_gcry_mpih_rshift( mp, mp, msize, mod_shift_cnt);
305
_gcry_mpih_sub( rp, mp, msize, rp, rsize);
306
rsize = msize;
307
rsign = msign;
308
MPN_NORMALIZE(rp, rsize);
309
}
310
gcry_assert (res->d == rp);
311
res->nlimbs = rsize;
312
res->sign = rsign;
313
314
leave:
315
if (mp_marker)
316
_gcry_mpi_free_limb_space( mp_marker, mp_nlimbs );
317
if (bp_marker)
318
_gcry_mpi_free_limb_space( bp_marker, bp_nlimbs );
319
if (ep_marker)
320
_gcry_mpi_free_limb_space( ep_marker, ep_nlimbs );
321
if (xp_marker)
322
_gcry_mpi_free_limb_space( xp_marker, xp_nlimbs );
323
if (tspace)
324
_gcry_mpi_free_limb_space( tspace, 0 );
300
325
}
301
326
Loggerhead is a web-based interface for Breezy
Version: 2.0.1