Root/
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) |
62 | return -EINVAL; |
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. */ |
67 | rp[0] = 1; |
68 | res->nlimbs = (msize == 1 && mod->d[0] == 1) ? 0 : 1; |
69 | res->sign = 0; |
70 | goto leave; |
71 | } |
72 | |
73 | /* Normalize MOD (i.e. make its most significant bit set) as required by |
74 | * mpn_divrem. This will make the intermediate values in the calculation |
75 | * slightly larger, but the correct result is obtained after a final |
76 | * reduction using the original MOD value. */ |
77 | mp = mp_marker = mpi_alloc_limb_space(msize); |
78 | if (!mp) |
79 | goto enomem; |
80 | mod_shift_cnt = count_leading_zeros(mod->d[msize - 1]); |
81 | if (mod_shift_cnt) |
82 | mpihelp_lshift(mp, mod->d, msize, mod_shift_cnt); |
83 | else |
84 | MPN_COPY(mp, mod->d, msize); |
85 | |
86 | bsize = base->nlimbs; |
87 | bsign = base->sign; |
88 | if (bsize > msize) { /* The base is larger than the module. Reduce it. */ |
89 | /* Allocate (BSIZE + 1) with space for remainder and quotient. |
90 | * (The quotient is (bsize - msize + 1) limbs.) */ |
91 | bp = bp_marker = mpi_alloc_limb_space(bsize + 1); |
92 | if (!bp) |
93 | goto enomem; |
94 | MPN_COPY(bp, base->d, bsize); |
95 | /* We don't care about the quotient, store it above the remainder, |
96 | * at BP + MSIZE. */ |
97 | mpihelp_divrem(bp + msize, 0, bp, bsize, mp, msize); |
98 | bsize = msize; |
99 | /* Canonicalize the base, since we are going to multiply with it |
100 | * quite a few times. */ |
101 | MPN_NORMALIZE(bp, bsize); |
102 | } else |
103 | bp = base->d; |
104 | |
105 | if (!bsize) { |
106 | res->nlimbs = 0; |
107 | res->sign = 0; |
108 | goto leave; |
109 | } |
110 | |
111 | if (res->alloced < size) { |
112 | /* We have to allocate more space for RES. If any of the input |
113 | * parameters are identical to RES, defer deallocation of the old |
114 | * space. */ |
115 | if (rp == ep || rp == mp || rp == bp) { |
116 | rp = mpi_alloc_limb_space(size); |
117 | if (!rp) |
118 | goto enomem; |
119 | assign_rp = 1; |
120 | } else { |
121 | if (mpi_resize(res, size) < 0) |
122 | goto enomem; |
123 | rp = res->d; |
124 | } |
125 | } else { /* Make BASE, EXP and MOD not overlap with RES. */ |
126 | if (rp == bp) { |
127 | /* RES and BASE are identical. Allocate temp. space for BASE. */ |
128 | BUG_ON(bp_marker); |
129 | bp = bp_marker = mpi_alloc_limb_space(bsize); |
130 | if (!bp) |
131 | goto enomem; |
132 | MPN_COPY(bp, rp, bsize); |
133 | } |
134 | if (rp == ep) { |
135 | /* RES and EXP are identical. Allocate temp. space for EXP. */ |
136 | ep = ep_marker = mpi_alloc_limb_space(esize); |
137 | if (!ep) |
138 | goto enomem; |
139 | MPN_COPY(ep, rp, esize); |
140 | } |
141 | if (rp == mp) { |
142 | /* RES and MOD are identical. Allocate temporary space for MOD. */ |
143 | BUG_ON(mp_marker); |
144 | mp = mp_marker = mpi_alloc_limb_space(msize); |
145 | if (!mp) |
146 | goto enomem; |
147 | MPN_COPY(mp, rp, msize); |
148 | } |
149 | } |
150 | |
151 | MPN_COPY(rp, bp, bsize); |
152 | rsize = bsize; |
153 | rsign = bsign; |
154 | |
155 | { |
156 | mpi_size_t i; |
157 | mpi_ptr_t xp; |
158 | int c; |
159 | mpi_limb_t e; |
160 | mpi_limb_t carry_limb; |
161 | struct karatsuba_ctx karactx; |
162 | |
163 | xp = xp_marker = mpi_alloc_limb_space(2 * (msize + 1)); |
164 | if (!xp) |
165 | goto enomem; |
166 | |
167 | memset(&karactx, 0, sizeof karactx); |
168 | negative_result = (ep[0] & 1) && base->sign; |
169 | |
170 | i = esize - 1; |
171 | e = ep[i]; |
172 | c = count_leading_zeros(e); |
173 | e = (e << c) << 1; /* shift the exp bits to the left, lose msb */ |
174 | c = BITS_PER_MPI_LIMB - 1 - c; |
175 | |
176 | /* Main loop. |
177 | * |
178 | * Make the result be pointed to alternately by XP and RP. This |
179 | * helps us avoid block copying, which would otherwise be necessary |
180 | * with the overlap restrictions of mpihelp_divmod. With 50% probability |
181 | * the result after this loop will be in the area originally pointed |
182 | * by RP (==RES->d), and with 50% probability in the area originally |
183 | * pointed to by XP. |
184 | */ |
185 | |
186 | for (;;) { |
187 | while (c) { |
188 | mpi_ptr_t tp; |
189 | mpi_size_t xsize; |
190 | |
191 | /*if (mpihelp_mul_n(xp, rp, rp, rsize) < 0) goto enomem */ |
192 | if (rsize < KARATSUBA_THRESHOLD) |
193 | mpih_sqr_n_basecase(xp, rp, rsize); |
194 | else { |
195 | if (!tspace) { |
196 | tsize = 2 * rsize; |
197 | tspace = |
198 | mpi_alloc_limb_space(tsize); |
199 | if (!tspace) |
200 | goto enomem; |
201 | } else if (tsize < (2 * rsize)) { |
202 | mpi_free_limb_space(tspace); |
203 | tsize = 2 * rsize; |
204 | tspace = |
205 | mpi_alloc_limb_space(tsize); |
206 | if (!tspace) |
207 | goto enomem; |
208 | } |
209 | mpih_sqr_n(xp, rp, rsize, tspace); |
210 | } |
211 | |
212 | xsize = 2 * rsize; |
213 | if (xsize > msize) { |
214 | mpihelp_divrem(xp + msize, 0, xp, xsize, |
215 | mp, msize); |
216 | xsize = msize; |
217 | } |
218 | |
219 | tp = rp; |
220 | rp = xp; |
221 | xp = tp; |
222 | rsize = xsize; |
223 | |
224 | if ((mpi_limb_signed_t) e < 0) { |
225 | /*mpihelp_mul( xp, rp, rsize, bp, bsize ); */ |
226 | if (bsize < KARATSUBA_THRESHOLD) { |
227 | mpi_limb_t tmp; |
228 | if (mpihelp_mul |
229 | (xp, rp, rsize, bp, bsize, |
230 | &tmp) < 0) |
231 | goto enomem; |
232 | } else { |
233 | if (mpihelp_mul_karatsuba_case |
234 | (xp, rp, rsize, bp, bsize, |
235 | &karactx) < 0) |
236 | goto enomem; |
237 | } |
238 | |
239 | xsize = rsize + bsize; |
240 | if (xsize > msize) { |
241 | mpihelp_divrem(xp + msize, 0, |
242 | xp, xsize, mp, |
243 | msize); |
244 | xsize = msize; |
245 | } |
246 | |
247 | tp = rp; |
248 | rp = xp; |
249 | xp = tp; |
250 | rsize = xsize; |
251 | } |
252 | e <<= 1; |
253 | c--; |
254 | } |
255 | |
256 | i--; |
257 | if (i < 0) |
258 | break; |
259 | e = ep[i]; |
260 | c = BITS_PER_MPI_LIMB; |
261 | } |
262 | |
263 | /* We shifted MOD, the modulo reduction argument, left MOD_SHIFT_CNT |
264 | * steps. Adjust the result by reducing it with the original MOD. |
265 | * |
266 | * Also make sure the result is put in RES->d (where it already |
267 | * might be, see above). |
268 | */ |
269 | if (mod_shift_cnt) { |
270 | carry_limb = |
271 | mpihelp_lshift(res->d, rp, rsize, mod_shift_cnt); |
272 | rp = res->d; |
273 | if (carry_limb) { |
274 | rp[rsize] = carry_limb; |
275 | rsize++; |
276 | } |
277 | } else { |
278 | MPN_COPY(res->d, rp, rsize); |
279 | rp = res->d; |
280 | } |
281 | |
282 | if (rsize >= msize) { |
283 | mpihelp_divrem(rp + msize, 0, rp, rsize, mp, msize); |
284 | rsize = msize; |
285 | } |
286 | |
287 | /* Remove any leading zero words from the result. */ |
288 | if (mod_shift_cnt) |
289 | mpihelp_rshift(rp, rp, rsize, mod_shift_cnt); |
290 | MPN_NORMALIZE(rp, rsize); |
291 | |
292 | mpihelp_release_karatsuba_ctx(&karactx); |
293 | } |
294 | |
295 | if (negative_result && rsize) { |
296 | if (mod_shift_cnt) |
297 | mpihelp_rshift(mp, mp, msize, mod_shift_cnt); |
298 | mpihelp_sub(rp, mp, msize, rp, rsize); |
299 | rsize = msize; |
300 | rsign = msign; |
301 | MPN_NORMALIZE(rp, rsize); |
302 | } |
303 | res->nlimbs = rsize; |
304 | res->sign = rsign; |
305 | |
306 | leave: |
307 | rc = 0; |
308 | enomem: |
309 | if (assign_rp) |
310 | mpi_assign_limb_space(res, rp, size); |
311 | if (mp_marker) |
312 | mpi_free_limb_space(mp_marker); |
313 | if (bp_marker) |
314 | mpi_free_limb_space(bp_marker); |
315 | if (ep_marker) |
316 | mpi_free_limb_space(ep_marker); |
317 | if (xp_marker) |
318 | mpi_free_limb_space(xp_marker); |
319 | if (tspace) |
320 | mpi_free_limb_space(tspace); |
321 | return rc; |
322 | } |
323 | EXPORT_SYMBOL_GPL(mpi_powm); |
324 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9