]>
Commit | Line | Data |
---|---|---|
cdec9cb5 DK |
1 | /* mpi-pow.c - MPI functions |
2 | * Copyright (C) 1994, 1996, 1998, 2000 Free Software Foundation, Inc. | |
3 | * | |
4 | * This file is part of GnuPG. | |
5 | * | |
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. | |
10 | * | |
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. | |
15 | * | |
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 | |
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 | * The GNU MP Library itself is published under the LGPL; | |
26 | * however I decided to publish this code under the plain GPL. | |
27 | */ | |
28 | ||
29 | #include <linux/string.h> | |
30 | #include "mpi-internal.h" | |
31 | #include "longlong.h" | |
32 | ||
33 | /**************** | |
34 | * RES = BASE ^ EXP mod MOD | |
35 | */ | |
36 | int mpi_powm(MPI res, MPI base, MPI exp, MPI mod) | |
37 | { | |
38 | mpi_ptr_t mp_marker = NULL, bp_marker = NULL, ep_marker = NULL; | |
39 | mpi_ptr_t xp_marker = NULL; | |
40 | mpi_ptr_t tspace = NULL; | |
41 | mpi_ptr_t rp, ep, mp, bp; | |
42 | mpi_size_t esize, msize, bsize, rsize; | |
43 | int esign, msign, bsign, rsign; | |
44 | mpi_size_t size; | |
45 | int mod_shift_cnt; | |
46 | int negative_result; | |
47 | int assign_rp = 0; | |
48 | mpi_size_t tsize = 0; /* to avoid compiler warning */ | |
49 | /* fixme: we should check that the warning is void */ | |
50 | int rc = -ENOMEM; | |
51 | ||
52 | esize = exp->nlimbs; | |
53 | msize = mod->nlimbs; | |
54 | size = 2 * msize; | |
55 | esign = exp->sign; | |
56 | msign = mod->sign; | |
57 | ||
58 | rp = res->d; | |
59 | ep = exp->d; | |
60 | ||
61 | if (!msize) | |
e87c5e35 | 62 | return -EINVAL; |
cdec9cb5 DK |
63 | |
64 | if (!esize) { | |
65 | /* Exponent is zero, result is 1 mod MOD, i.e., 1 or 0 | |
66 | * depending on if MOD equals 1. */ | |
cdec9cb5 | 67 | res->nlimbs = (msize == 1 && mod->d[0] == 1) ? 0 : 1; |
f5527fff AR |
68 | if (res->nlimbs) { |
69 | if (mpi_resize(res, 1) < 0) | |
70 | goto enomem; | |
71 | rp = res->d; | |
72 | rp[0] = 1; | |
73 | } | |
cdec9cb5 DK |
74 | res->sign = 0; |
75 | goto leave; | |
76 | } | |
77 | ||
78 | /* Normalize MOD (i.e. make its most significant bit set) as required by | |
79 | * mpn_divrem. This will make the intermediate values in the calculation | |
80 | * slightly larger, but the correct result is obtained after a final | |
81 | * reduction using the original MOD value. */ | |
82 | mp = mp_marker = mpi_alloc_limb_space(msize); | |
83 | if (!mp) | |
84 | goto enomem; | |
aacf29bf | 85 | mod_shift_cnt = count_leading_zeros(mod->d[msize - 1]); |
cdec9cb5 DK |
86 | if (mod_shift_cnt) |
87 | mpihelp_lshift(mp, mod->d, msize, mod_shift_cnt); | |
88 | else | |
89 | MPN_COPY(mp, mod->d, msize); | |
90 | ||
91 | bsize = base->nlimbs; | |
92 | bsign = base->sign; | |
93 | if (bsize > msize) { /* The base is larger than the module. Reduce it. */ | |
94 | /* Allocate (BSIZE + 1) with space for remainder and quotient. | |
95 | * (The quotient is (bsize - msize + 1) limbs.) */ | |
96 | bp = bp_marker = mpi_alloc_limb_space(bsize + 1); | |
97 | if (!bp) | |
98 | goto enomem; | |
99 | MPN_COPY(bp, base->d, bsize); | |
100 | /* We don't care about the quotient, store it above the remainder, | |
101 | * at BP + MSIZE. */ | |
102 | mpihelp_divrem(bp + msize, 0, bp, bsize, mp, msize); | |
103 | bsize = msize; | |
104 | /* Canonicalize the base, since we are going to multiply with it | |
105 | * quite a few times. */ | |
106 | MPN_NORMALIZE(bp, bsize); | |
107 | } else | |
108 | bp = base->d; | |
109 | ||
110 | if (!bsize) { | |
111 | res->nlimbs = 0; | |
112 | res->sign = 0; | |
113 | goto leave; | |
114 | } | |
115 | ||
116 | if (res->alloced < size) { | |
117 | /* We have to allocate more space for RES. If any of the input | |
118 | * parameters are identical to RES, defer deallocation of the old | |
119 | * space. */ | |
120 | if (rp == ep || rp == mp || rp == bp) { | |
121 | rp = mpi_alloc_limb_space(size); | |
122 | if (!rp) | |
123 | goto enomem; | |
124 | assign_rp = 1; | |
125 | } else { | |
126 | if (mpi_resize(res, size) < 0) | |
127 | goto enomem; | |
128 | rp = res->d; | |
129 | } | |
130 | } else { /* Make BASE, EXP and MOD not overlap with RES. */ | |
131 | if (rp == bp) { | |
132 | /* RES and BASE are identical. Allocate temp. space for BASE. */ | |
133 | BUG_ON(bp_marker); | |
134 | bp = bp_marker = mpi_alloc_limb_space(bsize); | |
135 | if (!bp) | |
136 | goto enomem; | |
137 | MPN_COPY(bp, rp, bsize); | |
138 | } | |
139 | if (rp == ep) { | |
140 | /* RES and EXP are identical. Allocate temp. space for EXP. */ | |
141 | ep = ep_marker = mpi_alloc_limb_space(esize); | |
142 | if (!ep) | |
143 | goto enomem; | |
144 | MPN_COPY(ep, rp, esize); | |
145 | } | |
146 | if (rp == mp) { | |
147 | /* RES and MOD are identical. Allocate temporary space for MOD. */ | |
148 | BUG_ON(mp_marker); | |
149 | mp = mp_marker = mpi_alloc_limb_space(msize); | |
150 | if (!mp) | |
151 | goto enomem; | |
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 = xp_marker = mpi_alloc_limb_space(2 * (msize + 1)); | |
169 | if (!xp) | |
170 | goto enomem; | |
171 | ||
172 | memset(&karactx, 0, sizeof karactx); | |
173 | negative_result = (ep[0] & 1) && base->sign; | |
174 | ||
175 | i = esize - 1; | |
176 | e = ep[i]; | |
aacf29bf | 177 | c = count_leading_zeros(e); |
cdec9cb5 DK |
178 | e = (e << c) << 1; /* shift the exp 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 mpihelp_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 | /*if (mpihelp_mul_n(xp, rp, rp, rsize) < 0) goto enomem */ | |
197 | if (rsize < KARATSUBA_THRESHOLD) | |
198 | mpih_sqr_n_basecase(xp, rp, rsize); | |
199 | else { | |
200 | if (!tspace) { | |
201 | tsize = 2 * rsize; | |
202 | tspace = | |
203 | mpi_alloc_limb_space(tsize); | |
204 | if (!tspace) | |
205 | goto enomem; | |
206 | } else if (tsize < (2 * rsize)) { | |
207 | mpi_free_limb_space(tspace); | |
208 | tsize = 2 * rsize; | |
209 | tspace = | |
210 | mpi_alloc_limb_space(tsize); | |
211 | if (!tspace) | |
212 | goto enomem; | |
213 | } | |
214 | mpih_sqr_n(xp, rp, rsize, tspace); | |
215 | } | |
216 | ||
217 | xsize = 2 * rsize; | |
218 | if (xsize > msize) { | |
219 | mpihelp_divrem(xp + msize, 0, xp, xsize, | |
220 | mp, msize); | |
221 | xsize = msize; | |
222 | } | |
223 | ||
224 | tp = rp; | |
225 | rp = xp; | |
226 | xp = tp; | |
227 | rsize = xsize; | |
228 | ||
229 | if ((mpi_limb_signed_t) e < 0) { | |
230 | /*mpihelp_mul( xp, rp, rsize, bp, bsize ); */ | |
231 | if (bsize < KARATSUBA_THRESHOLD) { | |
232 | mpi_limb_t tmp; | |
233 | if (mpihelp_mul | |
234 | (xp, rp, rsize, bp, bsize, | |
235 | &tmp) < 0) | |
236 | goto enomem; | |
237 | } else { | |
238 | if (mpihelp_mul_karatsuba_case | |
239 | (xp, rp, rsize, bp, bsize, | |
240 | &karactx) < 0) | |
241 | goto enomem; | |
242 | } | |
243 | ||
244 | xsize = rsize + bsize; | |
245 | if (xsize > msize) { | |
246 | mpihelp_divrem(xp + msize, 0, | |
247 | xp, xsize, mp, | |
248 | msize); | |
249 | xsize = msize; | |
250 | } | |
251 | ||
252 | tp = rp; | |
253 | rp = xp; | |
254 | xp = tp; | |
255 | rsize = xsize; | |
256 | } | |
257 | e <<= 1; | |
258 | c--; | |
259 | } | |
260 | ||
261 | i--; | |
262 | if (i < 0) | |
263 | break; | |
264 | e = ep[i]; | |
265 | c = BITS_PER_MPI_LIMB; | |
266 | } | |
267 | ||
268 | /* We shifted MOD, the modulo reduction argument, left MOD_SHIFT_CNT | |
269 | * steps. Adjust the result by reducing it with the original MOD. | |
270 | * | |
271 | * Also make sure the result is put in RES->d (where it already | |
272 | * might be, see above). | |
273 | */ | |
274 | if (mod_shift_cnt) { | |
275 | carry_limb = | |
276 | mpihelp_lshift(res->d, rp, rsize, mod_shift_cnt); | |
277 | rp = res->d; | |
278 | if (carry_limb) { | |
279 | rp[rsize] = carry_limb; | |
280 | rsize++; | |
281 | } | |
282 | } else { | |
283 | MPN_COPY(res->d, rp, rsize); | |
284 | rp = res->d; | |
285 | } | |
286 | ||
287 | if (rsize >= msize) { | |
288 | mpihelp_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 | mpihelp_rshift(rp, rp, rsize, mod_shift_cnt); | |
295 | MPN_NORMALIZE(rp, rsize); | |
296 | ||
297 | mpihelp_release_karatsuba_ctx(&karactx); | |
298 | } | |
299 | ||
300 | if (negative_result && rsize) { | |
301 | if (mod_shift_cnt) | |
302 | mpihelp_rshift(mp, mp, msize, mod_shift_cnt); | |
303 | mpihelp_sub(rp, mp, msize, rp, rsize); | |
304 | rsize = msize; | |
305 | rsign = msign; | |
306 | MPN_NORMALIZE(rp, rsize); | |
307 | } | |
308 | res->nlimbs = rsize; | |
309 | res->sign = rsign; | |
310 | ||
311 | leave: | |
312 | rc = 0; | |
313 | enomem: | |
314 | if (assign_rp) | |
315 | mpi_assign_limb_space(res, rp, size); | |
316 | if (mp_marker) | |
317 | mpi_free_limb_space(mp_marker); | |
318 | if (bp_marker) | |
319 | mpi_free_limb_space(bp_marker); | |
320 | if (ep_marker) | |
321 | mpi_free_limb_space(ep_marker); | |
322 | if (xp_marker) | |
323 | mpi_free_limb_space(xp_marker); | |
324 | if (tspace) | |
325 | mpi_free_limb_space(tspace); | |
326 | return rc; | |
327 | } | |
328 | EXPORT_SYMBOL_GPL(mpi_powm); |