summaryrefslogtreecommitdiffabout
path: root/pwmanager/libcrypt/mpi/mpi-pow.c
Unidiff
Diffstat (limited to 'pwmanager/libcrypt/mpi/mpi-pow.c') (more/less context) (ignore whitespace changes)
-rw-r--r--pwmanager/libcrypt/mpi/mpi-pow.c302
1 files changed, 302 insertions, 0 deletions
diff --git a/pwmanager/libcrypt/mpi/mpi-pow.c b/pwmanager/libcrypt/mpi/mpi-pow.c
new file mode 100644
index 0000000..61a115f
--- a/dev/null
+++ b/pwmanager/libcrypt/mpi/mpi-pow.c
@@ -0,0 +1,302 @@
1/* mpi-pow.c - MPI functions
2 * Copyright (C) 1994, 1996, 1998, 2000, 2002, 2003 Free Software Foundation, Inc.
3 *
4 * This file is part of Libgcrypt.
5 *
6 * Libgcrypt is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU Lesser General Public License as
8 * published by the Free Software Foundation; either version 2.1 of
9 * the License, or (at your option) any later version.
10 *
11 * Libgcrypt 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 Lesser General Public License for more details.
15 *
16 * 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
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 */
26
27#include <config.h>
28#include <stdio.h>
29#include <stdlib.h>
30#include <string.h>
31#include "mpi-internal.h"
32#include "longlong.h"
33#include <assert.h>
34
35
36/****************
37 * RES = BASE ^ EXPO mod MOD
38 */
39void
40gcry_mpi_powm( gcry_mpi_t res, gcry_mpi_t base, gcry_mpi_t expo, gcry_mpi_t mod)
41{
42 mpi_ptr_t rp, ep, mp, bp;
43 mpi_size_t esize, msize, bsize, rsize;
44 int esign, 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 esign = expo->sign;
62 msign = mod->sign;
63
64 esec = mpi_is_secure(expo);
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 = expo->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_nlimbs = msec? msize:0;
89 mp = mp_marker = mpi_alloc_limb_space(msize, msec);
90 count_leading_zeros( mod_shift_cnt, mod->d[msize-1] );
91 if( mod_shift_cnt )
92 _gcry_mpih_lshift( mp, mod->d, msize, mod_shift_cnt );
93 else
94 MPN_COPY( mp, mod->d, msize );
95
96 bsize = base->nlimbs;
97 bsign = base->sign;
98 if( bsize > msize ) { /* The base is larger than the module. Reduce it. */
99 /* Allocate (BSIZE + 1) with space for remainder and quotient.
100 * (The quotient is (bsize - msize + 1) limbs.) */
101 bp_nlimbs = bsec ? (bsize + 1):0;
102 bp = bp_marker = mpi_alloc_limb_space( bsize + 1, bsec );
103 MPN_COPY( bp, base->d, bsize );
104 /* We don't care about the quotient, store it above the remainder,
105 * at BP + MSIZE. */
106 _gcry_mpih_divrem( bp + msize, 0, bp, bsize, mp, msize );
107 bsize = msize;
108 /* Canonicalize the base, since we are going to multiply with it
109 * quite a few times. */
110 MPN_NORMALIZE( bp, bsize );
111 }
112 else
113 bp = base->d;
114
115 if( !bsize ) {
116 res->nlimbs = 0;
117 res->sign = 0;
118 goto leave;
119 }
120
121 if( res->alloced < size ) {
122 /* We have to allocate more space for RES. If any of the input
123 * parameters are identical to RES, defer deallocation of the old
124 * space. */
125 if( rp == ep || rp == mp || rp == bp ) {
126 rp = mpi_alloc_limb_space( size, rsec );
127 assign_rp = 1;
128 }
129 else {
130 mpi_resize( res, size );
131 rp = res->d;
132 }
133 }
134 else { /* Make BASE, EXPO and MOD not overlap with RES. */
135 if( rp == bp ) {
136 /* RES and BASE are identical. Allocate temp. space for BASE. */
137 assert( !bp_marker );
138 bp_nlimbs = bsec? bsize:0;
139 bp = bp_marker = mpi_alloc_limb_space( bsize, bsec );
140 MPN_COPY(bp, rp, bsize);
141 }
142 if( rp == ep ) {
143 /* RES and EXPO are identical. Allocate temp. space for EXPO. */
144 ep_nlimbs = esec? esize:0;
145 ep = ep_marker = mpi_alloc_limb_space( esize, esec );
146 MPN_COPY(ep, rp, esize);
147 }
148 if( rp == mp ) {
149 /* RES and MOD are identical. Allocate temporary space for MOD.*/
150 assert( !mp_marker );
151 mp_nlimbs = msec?msize:0;
152 mp = mp_marker = mpi_alloc_limb_space( msize, msec );
153 MPN_COPY(mp, rp, msize);
154 }
155 }
156
157 MPN_COPY( rp, bp, bsize );
158 rsize = bsize;
159 rsign = bsign;
160
161 {
162 mpi_size_t i;
163 mpi_ptr_t xp;
164 int c;
165 mpi_limb_t e;
166 mpi_limb_t carry_limb;
167 struct karatsuba_ctx karactx;
168
169 xp_nlimbs = msec? (2 * (msize + 1)):0;
170 xp = xp_marker = mpi_alloc_limb_space( 2 * (msize + 1), msec );
171
172 memset( &karactx, 0, sizeof karactx );
173 negative_result = (ep[0] & 1) && base->sign;
174
175 i = esize - 1;
176 e = ep[i];
177 count_leading_zeros (c, e);
178 e = (e << c) << 1; /* shift the expo bits to the left, lose msb */
179 c = BITS_PER_MPI_LIMB - 1 - c;
180
181 /* Main loop.
182 *
183 * Make the result be pointed to alternately by XP and RP. This
184 * helps us avoid block copying, which would otherwise be necessary
185 * with the overlap restrictions of _gcry_mpih_divmod. With 50% probability
186 * the result after this loop will be in the area originally pointed
187 * by RP (==RES->d), and with 50% probability in the area originally
188 * pointed to by XP.
189 */
190
191 for(;;) {
192 while( c ) {
193 mpi_ptr_t tp;
194 mpi_size_t xsize;
195
196 /*mpih_mul_n(xp, rp, rp, rsize);*/
197 if( rsize < KARATSUBA_THRESHOLD )
198 _gcry_mpih_sqr_n_basecase( xp, rp, rsize );
199 else {
200 if( !tspace ) {
201 tsize = 2 * rsize;
202 tspace = mpi_alloc_limb_space( tsize, 0 );
203 }
204 else if( tsize < (2*rsize) ) {
205 _gcry_mpi_free_limb_space (tspace, 0);
206 tsize = 2 * rsize;
207 tspace = mpi_alloc_limb_space( tsize, 0 );
208 }
209 _gcry_mpih_sqr_n( xp, rp, rsize, tspace );
210 }
211
212 xsize = 2 * rsize;
213 if( xsize > msize ) {
214 _gcry_mpih_divrem(xp + msize, 0, xp, xsize, mp, msize);
215 xsize = msize;
216 }
217
218 tp = rp; rp = xp; xp = tp;
219 rsize = xsize;
220
221 if( (mpi_limb_signed_t)e < 0 ) {
222 /*mpih_mul( xp, rp, rsize, bp, bsize );*/
223 if( bsize < KARATSUBA_THRESHOLD ) {
224 _gcry_mpih_mul( xp, rp, rsize, bp, bsize );
225 }
226 else {
227 _gcry_mpih_mul_karatsuba_case(
228 xp, rp, rsize, bp, bsize, &karactx );
229 }
230
231 xsize = rsize + bsize;
232 if( xsize > msize ) {
233 _gcry_mpih_divrem(xp + msize, 0, xp, xsize, mp, msize);
234 xsize = msize;
235 }
236
237 tp = rp; rp = xp; xp = tp;
238 rsize = xsize;
239 }
240 e <<= 1;
241 c--;
242 }
243
244 i--;
245 if( i < 0 )
246 break;
247 e = ep[i];
248 c = BITS_PER_MPI_LIMB;
249 }
250
251 /* We shifted MOD, the modulo reduction argument, left MOD_SHIFT_CNT
252 * steps. Adjust the result by reducing it with the original MOD.
253 *
254 * Also make sure the result is put in RES->d (where it already
255 * might be, see above).
256 */
257 if( mod_shift_cnt ) {
258 carry_limb = _gcry_mpih_lshift( res->d, rp, rsize, mod_shift_cnt);
259 rp = res->d;
260 if( carry_limb ) {
261 rp[rsize] = carry_limb;
262 rsize++;
263 }
264 }
265 else {
266 MPN_COPY( res->d, rp, rsize);
267 rp = res->d;
268 }
269
270 if( rsize >= msize ) {
271 _gcry_mpih_divrem(rp + msize, 0, rp, rsize, mp, msize);
272 rsize = msize;
273 }
274
275 /* Remove any leading zero words from the result. */
276 if( mod_shift_cnt )
277 _gcry_mpih_rshift( rp, rp, rsize, mod_shift_cnt);
278 MPN_NORMALIZE (rp, rsize);
279
280 _gcry_mpih_release_karatsuba_ctx( &karactx );
281 }
282
283 if( negative_result && rsize ) {
284 if( mod_shift_cnt )
285 _gcry_mpih_rshift( mp, mp, msize, mod_shift_cnt);
286 _gcry_mpih_sub( rp, mp, msize, rp, rsize);
287 rsize = msize;
288 rsign = msign;
289 MPN_NORMALIZE(rp, rsize);
290 }
291 res->nlimbs = rsize;
292 res->sign = rsign;
293
294 leave:
295 if( assign_rp ) _gcry_mpi_assign_limb_space( res, rp, size );
296 if( mp_marker ) _gcry_mpi_free_limb_space( mp_marker, mp_nlimbs );
297 if( bp_marker ) _gcry_mpi_free_limb_space( bp_marker, bp_nlimbs );
298 if( ep_marker ) _gcry_mpi_free_limb_space( ep_marker, ep_nlimbs );
299 if( xp_marker ) _gcry_mpi_free_limb_space( xp_marker, xp_nlimbs );
300 if( tspace ) _gcry_mpi_free_limb_space( tspace, 0 );
301}
302