]>
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 | ||
1d9ddde1 | 29 | #include <linux/sched.h> |
cdec9cb5 DK |
30 | #include <linux/string.h> |
31 | #include "mpi-internal.h" | |
32 | #include "longlong.h" | |
33 | ||
34 | /**************** | |
35 | * RES = BASE ^ EXP mod MOD | |
36 | */ | |
37 | int mpi_powm(MPI res, MPI base, MPI exp, MPI mod) | |
38 | { | |
39 | mpi_ptr_t mp_marker = NULL, bp_marker = NULL, ep_marker = NULL; | |
cad14c8c | 40 | struct karatsuba_ctx karactx = {}; |
cdec9cb5 DK |
41 | mpi_ptr_t xp_marker = NULL; |
42 | mpi_ptr_t tspace = NULL; | |
43 | mpi_ptr_t rp, ep, mp, bp; | |
44 | mpi_size_t esize, msize, bsize, rsize; | |
45 | int esign, msign, bsign, rsign; | |
46 | mpi_size_t size; | |
47 | int mod_shift_cnt; | |
48 | int negative_result; | |
49 | int assign_rp = 0; | |
50 | mpi_size_t tsize = 0; /* to avoid compiler warning */ | |
51 | /* fixme: we should check that the warning is void */ | |
52 | int rc = -ENOMEM; | |
53 | ||
54 | esize = exp->nlimbs; | |
55 | msize = mod->nlimbs; | |
56 | size = 2 * msize; | |
57 | esign = exp->sign; | |
58 | msign = mod->sign; | |
59 | ||
60 | rp = res->d; | |
61 | ep = exp->d; | |
62 | ||
63 | if (!msize) | |
e87c5e35 | 64 | return -EINVAL; |
cdec9cb5 DK |
65 | |
66 | if (!esize) { | |
67 | /* Exponent is zero, result is 1 mod MOD, i.e., 1 or 0 | |
68 | * depending on if MOD equals 1. */ | |
cdec9cb5 | 69 | res->nlimbs = (msize == 1 && mod->d[0] == 1) ? 0 : 1; |
f5527fff AR |
70 | if (res->nlimbs) { |
71 | if (mpi_resize(res, 1) < 0) | |
72 | goto enomem; | |
73 | rp = res->d; | |
74 | rp[0] = 1; | |
75 | } | |
cdec9cb5 DK |
76 | res->sign = 0; |
77 | goto leave; | |
78 | } | |
79 | ||
80 | /* Normalize MOD (i.e. make its most significant bit set) as required by | |
81 | * mpn_divrem. This will make the intermediate values in the calculation | |
82 | * slightly larger, but the correct result is obtained after a final | |
83 | * reduction using the original MOD value. */ | |
84 | mp = mp_marker = mpi_alloc_limb_space(msize); | |
85 | if (!mp) | |
86 | goto enomem; | |
aacf29bf | 87 | mod_shift_cnt = count_leading_zeros(mod->d[msize - 1]); |
cdec9cb5 DK |
88 | if (mod_shift_cnt) |
89 | mpihelp_lshift(mp, mod->d, msize, mod_shift_cnt); | |
90 | else | |
91 | MPN_COPY(mp, mod->d, msize); | |
92 | ||
93 | bsize = base->nlimbs; | |
94 | bsign = base->sign; | |
95 | if (bsize > msize) { /* The base is larger than the module. Reduce it. */ | |
96 | /* Allocate (BSIZE + 1) with space for remainder and quotient. | |
97 | * (The quotient is (bsize - msize + 1) limbs.) */ | |
98 | bp = bp_marker = mpi_alloc_limb_space(bsize + 1); | |
99 | if (!bp) | |
100 | goto enomem; | |
101 | MPN_COPY(bp, base->d, bsize); | |
102 | /* We don't care about the quotient, store it above the remainder, | |
103 | * at BP + MSIZE. */ | |
104 | mpihelp_divrem(bp + msize, 0, bp, bsize, mp, msize); | |
105 | bsize = msize; | |
106 | /* Canonicalize the base, since we are going to multiply with it | |
107 | * quite a few times. */ | |
108 | MPN_NORMALIZE(bp, bsize); | |
109 | } else | |
110 | bp = base->d; | |
111 | ||
112 | if (!bsize) { | |
113 | res->nlimbs = 0; | |
114 | res->sign = 0; | |
115 | goto leave; | |
116 | } | |
117 | ||
118 | if (res->alloced < size) { | |
119 | /* We have to allocate more space for RES. If any of the input | |
120 | * parameters are identical to RES, defer deallocation of the old | |
121 | * space. */ | |
122 | if (rp == ep || rp == mp || rp == bp) { | |
123 | rp = mpi_alloc_limb_space(size); | |
124 | if (!rp) | |
125 | goto enomem; | |
126 | assign_rp = 1; | |
127 | } else { | |
128 | if (mpi_resize(res, size) < 0) | |
129 | goto enomem; | |
130 | rp = res->d; | |
131 | } | |
132 | } else { /* Make BASE, EXP and MOD not overlap with RES. */ | |
133 | if (rp == bp) { | |
134 | /* RES and BASE are identical. Allocate temp. space for BASE. */ | |
135 | BUG_ON(bp_marker); | |
136 | bp = bp_marker = mpi_alloc_limb_space(bsize); | |
137 | if (!bp) | |
138 | goto enomem; | |
139 | MPN_COPY(bp, rp, bsize); | |
140 | } | |
141 | if (rp == ep) { | |
142 | /* RES and EXP are identical. Allocate temp. space for EXP. */ | |
143 | ep = ep_marker = mpi_alloc_limb_space(esize); | |
144 | if (!ep) | |
145 | goto enomem; | |
146 | MPN_COPY(ep, rp, esize); | |
147 | } | |
148 | if (rp == mp) { | |
149 | /* RES and MOD are identical. Allocate temporary space for MOD. */ | |
150 | BUG_ON(mp_marker); | |
151 | mp = mp_marker = mpi_alloc_limb_space(msize); | |
152 | if (!mp) | |
153 | goto enomem; | |
154 | MPN_COPY(mp, rp, msize); | |
155 | } | |
156 | } | |
157 | ||
158 | MPN_COPY(rp, bp, bsize); | |
159 | rsize = bsize; | |
160 | rsign = bsign; | |
161 | ||
162 | { | |
163 | mpi_size_t i; | |
164 | mpi_ptr_t xp; | |
165 | int c; | |
166 | mpi_limb_t e; | |
167 | mpi_limb_t carry_limb; | |
cdec9cb5 DK |
168 | |
169 | xp = xp_marker = mpi_alloc_limb_space(2 * (msize + 1)); | |
170 | if (!xp) | |
171 | goto enomem; | |
172 | ||
cdec9cb5 DK |
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--; | |
1d9ddde1 | 259 | cond_resched(); |
cdec9cb5 DK |
260 | } |
261 | ||
262 | i--; | |
263 | if (i < 0) | |
264 | break; | |
265 | e = ep[i]; | |
266 | c = BITS_PER_MPI_LIMB; | |
267 | } | |
268 | ||
269 | /* We shifted MOD, the modulo reduction argument, left MOD_SHIFT_CNT | |
270 | * steps. Adjust the result by reducing it with the original MOD. | |
271 | * | |
272 | * Also make sure the result is put in RES->d (where it already | |
273 | * might be, see above). | |
274 | */ | |
275 | if (mod_shift_cnt) { | |
276 | carry_limb = | |
277 | mpihelp_lshift(res->d, rp, rsize, mod_shift_cnt); | |
278 | rp = res->d; | |
279 | if (carry_limb) { | |
280 | rp[rsize] = carry_limb; | |
281 | rsize++; | |
282 | } | |
283 | } else { | |
284 | MPN_COPY(res->d, rp, rsize); | |
285 | rp = res->d; | |
286 | } | |
287 | ||
288 | if (rsize >= msize) { | |
289 | mpihelp_divrem(rp + msize, 0, rp, rsize, mp, msize); | |
290 | rsize = msize; | |
291 | } | |
292 | ||
293 | /* Remove any leading zero words from the result. */ | |
294 | if (mod_shift_cnt) | |
295 | mpihelp_rshift(rp, rp, rsize, mod_shift_cnt); | |
296 | MPN_NORMALIZE(rp, rsize); | |
cdec9cb5 DK |
297 | } |
298 | ||
299 | if (negative_result && rsize) { | |
300 | if (mod_shift_cnt) | |
301 | mpihelp_rshift(mp, mp, msize, mod_shift_cnt); | |
302 | mpihelp_sub(rp, mp, msize, rp, rsize); | |
303 | rsize = msize; | |
304 | rsign = msign; | |
305 | MPN_NORMALIZE(rp, rsize); | |
306 | } | |
307 | res->nlimbs = rsize; | |
308 | res->sign = rsign; | |
309 | ||
310 | leave: | |
311 | rc = 0; | |
312 | enomem: | |
cad14c8c | 313 | mpihelp_release_karatsuba_ctx(&karactx); |
cdec9cb5 DK |
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); |