Diffstat (limited to 'pwmanager/libcrypt/mpi/mpi-pow.c') (more/less context) (ignore whitespace changes)
-rw-r--r-- | pwmanager/libcrypt/mpi/mpi-pow.c | 302 |
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 | */ | ||
39 | void | ||
40 | gcry_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 | |||