]>
Commit | Line | Data |
---|---|---|
465ae836 | 1 | // SPDX-License-Identifier: GPL-2.0-or-later |
cdec9cb5 DK |
2 | /* mpi-pow.c - MPI functions |
3 | * Copyright (C) 1994, 1996, 1998, 2000 Free Software Foundation, Inc. | |
4 | * | |
5 | * This file is part of GnuPG. | |
6 | * | |
cdec9cb5 DK |
7 | * Note: This code is heavily based on the GNU MP Library. |
8 | * Actually it's the same code with only minor changes in the | |
9 | * way the data is stored; this is to support the abstraction | |
10 | * of an optional secure memory allocation which may be used | |
11 | * to avoid revealing of sensitive data due to paging etc. | |
12 | * The GNU MP Library itself is published under the LGPL; | |
13 | * however I decided to publish this code under the plain GPL. | |
14 | */ | |
15 | ||
1d9ddde1 | 16 | #include <linux/sched.h> |
cdec9cb5 DK |
17 | #include <linux/string.h> |
18 | #include "mpi-internal.h" | |
19 | #include "longlong.h" | |
20 | ||
21 | /**************** | |
22 | * RES = BASE ^ EXP mod MOD | |
23 | */ | |
24 | int mpi_powm(MPI res, MPI base, MPI exp, MPI mod) | |
25 | { | |
26 | mpi_ptr_t mp_marker = NULL, bp_marker = NULL, ep_marker = NULL; | |
c8ea9fce | 27 | struct karatsuba_ctx karactx = {}; |
cdec9cb5 DK |
28 | mpi_ptr_t xp_marker = NULL; |
29 | mpi_ptr_t tspace = NULL; | |
30 | mpi_ptr_t rp, ep, mp, bp; | |
31 | mpi_size_t esize, msize, bsize, rsize; | |
6122bbbd | 32 | int msign, bsign, rsign; |
cdec9cb5 DK |
33 | mpi_size_t size; |
34 | int mod_shift_cnt; | |
35 | int negative_result; | |
36 | int assign_rp = 0; | |
37 | mpi_size_t tsize = 0; /* to avoid compiler warning */ | |
38 | /* fixme: we should check that the warning is void */ | |
39 | int rc = -ENOMEM; | |
40 | ||
41 | esize = exp->nlimbs; | |
42 | msize = mod->nlimbs; | |
43 | size = 2 * msize; | |
cdec9cb5 DK |
44 | msign = mod->sign; |
45 | ||
46 | rp = res->d; | |
47 | ep = exp->d; | |
48 | ||
49 | if (!msize) | |
e87c5e35 | 50 | return -EINVAL; |
cdec9cb5 DK |
51 | |
52 | if (!esize) { | |
53 | /* Exponent is zero, result is 1 mod MOD, i.e., 1 or 0 | |
54 | * depending on if MOD equals 1. */ | |
cdec9cb5 | 55 | res->nlimbs = (msize == 1 && mod->d[0] == 1) ? 0 : 1; |
f5527fff AR |
56 | if (res->nlimbs) { |
57 | if (mpi_resize(res, 1) < 0) | |
58 | goto enomem; | |
59 | rp = res->d; | |
60 | rp[0] = 1; | |
61 | } | |
cdec9cb5 DK |
62 | res->sign = 0; |
63 | goto leave; | |
64 | } | |
65 | ||
66 | /* Normalize MOD (i.e. make its most significant bit set) as required by | |
67 | * mpn_divrem. This will make the intermediate values in the calculation | |
68 | * slightly larger, but the correct result is obtained after a final | |
69 | * reduction using the original MOD value. */ | |
70 | mp = mp_marker = mpi_alloc_limb_space(msize); | |
71 | if (!mp) | |
72 | goto enomem; | |
aacf29bf | 73 | mod_shift_cnt = count_leading_zeros(mod->d[msize - 1]); |
cdec9cb5 DK |
74 | if (mod_shift_cnt) |
75 | mpihelp_lshift(mp, mod->d, msize, mod_shift_cnt); | |
76 | else | |
77 | MPN_COPY(mp, mod->d, msize); | |
78 | ||
79 | bsize = base->nlimbs; | |
80 | bsign = base->sign; | |
81 | if (bsize > msize) { /* The base is larger than the module. Reduce it. */ | |
82 | /* Allocate (BSIZE + 1) with space for remainder and quotient. | |
83 | * (The quotient is (bsize - msize + 1) limbs.) */ | |
84 | bp = bp_marker = mpi_alloc_limb_space(bsize + 1); | |
85 | if (!bp) | |
86 | goto enomem; | |
87 | MPN_COPY(bp, base->d, bsize); | |
88 | /* We don't care about the quotient, store it above the remainder, | |
89 | * at BP + MSIZE. */ | |
90 | mpihelp_divrem(bp + msize, 0, bp, bsize, mp, msize); | |
91 | bsize = msize; | |
92 | /* Canonicalize the base, since we are going to multiply with it | |
93 | * quite a few times. */ | |
94 | MPN_NORMALIZE(bp, bsize); | |
95 | } else | |
96 | bp = base->d; | |
97 | ||
98 | if (!bsize) { | |
99 | res->nlimbs = 0; | |
100 | res->sign = 0; | |
101 | goto leave; | |
102 | } | |
103 | ||
104 | if (res->alloced < size) { | |
105 | /* We have to allocate more space for RES. If any of the input | |
106 | * parameters are identical to RES, defer deallocation of the old | |
107 | * space. */ | |
108 | if (rp == ep || rp == mp || rp == bp) { | |
109 | rp = mpi_alloc_limb_space(size); | |
110 | if (!rp) | |
111 | goto enomem; | |
112 | assign_rp = 1; | |
113 | } else { | |
114 | if (mpi_resize(res, size) < 0) | |
115 | goto enomem; | |
116 | rp = res->d; | |
117 | } | |
118 | } else { /* Make BASE, EXP and MOD not overlap with RES. */ | |
119 | if (rp == bp) { | |
120 | /* RES and BASE are identical. Allocate temp. space for BASE. */ | |
121 | BUG_ON(bp_marker); | |
122 | bp = bp_marker = mpi_alloc_limb_space(bsize); | |
123 | if (!bp) | |
124 | goto enomem; | |
125 | MPN_COPY(bp, rp, bsize); | |
126 | } | |
127 | if (rp == ep) { | |
128 | /* RES and EXP are identical. Allocate temp. space for EXP. */ | |
129 | ep = ep_marker = mpi_alloc_limb_space(esize); | |
130 | if (!ep) | |
131 | goto enomem; | |
132 | MPN_COPY(ep, rp, esize); | |
133 | } | |
134 | if (rp == mp) { | |
135 | /* RES and MOD are identical. Allocate temporary space for MOD. */ | |
136 | BUG_ON(mp_marker); | |
137 | mp = mp_marker = mpi_alloc_limb_space(msize); | |
138 | if (!mp) | |
139 | goto enomem; | |
140 | MPN_COPY(mp, rp, msize); | |
141 | } | |
142 | } | |
143 | ||
144 | MPN_COPY(rp, bp, bsize); | |
145 | rsize = bsize; | |
146 | rsign = bsign; | |
147 | ||
148 | { | |
149 | mpi_size_t i; | |
150 | mpi_ptr_t xp; | |
151 | int c; | |
152 | mpi_limb_t e; | |
153 | mpi_limb_t carry_limb; | |
cdec9cb5 DK |
154 | |
155 | xp = xp_marker = mpi_alloc_limb_space(2 * (msize + 1)); | |
156 | if (!xp) | |
157 | goto enomem; | |
158 | ||
cdec9cb5 DK |
159 | negative_result = (ep[0] & 1) && base->sign; |
160 | ||
161 | i = esize - 1; | |
162 | e = ep[i]; | |
aacf29bf | 163 | c = count_leading_zeros(e); |
cdec9cb5 DK |
164 | e = (e << c) << 1; /* shift the exp bits to the left, lose msb */ |
165 | c = BITS_PER_MPI_LIMB - 1 - c; | |
166 | ||
167 | /* Main loop. | |
168 | * | |
169 | * Make the result be pointed to alternately by XP and RP. This | |
170 | * helps us avoid block copying, which would otherwise be necessary | |
171 | * with the overlap restrictions of mpihelp_divmod. With 50% probability | |
172 | * the result after this loop will be in the area originally pointed | |
173 | * by RP (==RES->d), and with 50% probability in the area originally | |
174 | * pointed to by XP. | |
175 | */ | |
176 | ||
177 | for (;;) { | |
178 | while (c) { | |
179 | mpi_ptr_t tp; | |
180 | mpi_size_t xsize; | |
181 | ||
182 | /*if (mpihelp_mul_n(xp, rp, rp, rsize) < 0) goto enomem */ | |
183 | if (rsize < KARATSUBA_THRESHOLD) | |
184 | mpih_sqr_n_basecase(xp, rp, rsize); | |
185 | else { | |
186 | if (!tspace) { | |
187 | tsize = 2 * rsize; | |
188 | tspace = | |
189 | mpi_alloc_limb_space(tsize); | |
190 | if (!tspace) | |
191 | goto enomem; | |
192 | } else if (tsize < (2 * rsize)) { | |
193 | mpi_free_limb_space(tspace); | |
194 | tsize = 2 * rsize; | |
195 | tspace = | |
196 | mpi_alloc_limb_space(tsize); | |
197 | if (!tspace) | |
198 | goto enomem; | |
199 | } | |
200 | mpih_sqr_n(xp, rp, rsize, tspace); | |
201 | } | |
202 | ||
203 | xsize = 2 * rsize; | |
204 | if (xsize > msize) { | |
205 | mpihelp_divrem(xp + msize, 0, xp, xsize, | |
206 | mp, msize); | |
207 | xsize = msize; | |
208 | } | |
209 | ||
210 | tp = rp; | |
211 | rp = xp; | |
212 | xp = tp; | |
213 | rsize = xsize; | |
214 | ||
215 | if ((mpi_limb_signed_t) e < 0) { | |
216 | /*mpihelp_mul( xp, rp, rsize, bp, bsize ); */ | |
217 | if (bsize < KARATSUBA_THRESHOLD) { | |
218 | mpi_limb_t tmp; | |
219 | if (mpihelp_mul | |
220 | (xp, rp, rsize, bp, bsize, | |
221 | &tmp) < 0) | |
222 | goto enomem; | |
223 | } else { | |
224 | if (mpihelp_mul_karatsuba_case | |
225 | (xp, rp, rsize, bp, bsize, | |
226 | &karactx) < 0) | |
227 | goto enomem; | |
228 | } | |
229 | ||
230 | xsize = rsize + bsize; | |
231 | if (xsize > msize) { | |
232 | mpihelp_divrem(xp + msize, 0, | |
233 | xp, xsize, mp, | |
234 | msize); | |
235 | xsize = msize; | |
236 | } | |
237 | ||
238 | tp = rp; | |
239 | rp = xp; | |
240 | xp = tp; | |
241 | rsize = xsize; | |
242 | } | |
243 | e <<= 1; | |
244 | c--; | |
1d9ddde1 | 245 | cond_resched(); |
cdec9cb5 DK |
246 | } |
247 | ||
248 | i--; | |
249 | if (i < 0) | |
250 | break; | |
251 | e = ep[i]; | |
252 | c = BITS_PER_MPI_LIMB; | |
253 | } | |
254 | ||
255 | /* We shifted MOD, the modulo reduction argument, left MOD_SHIFT_CNT | |
256 | * steps. Adjust the result by reducing it with the original MOD. | |
257 | * | |
258 | * Also make sure the result is put in RES->d (where it already | |
259 | * might be, see above). | |
260 | */ | |
261 | if (mod_shift_cnt) { | |
262 | carry_limb = | |
263 | mpihelp_lshift(res->d, rp, rsize, mod_shift_cnt); | |
264 | rp = res->d; | |
265 | if (carry_limb) { | |
266 | rp[rsize] = carry_limb; | |
267 | rsize++; | |
268 | } | |
269 | } else { | |
270 | MPN_COPY(res->d, rp, rsize); | |
271 | rp = res->d; | |
272 | } | |
273 | ||
274 | if (rsize >= msize) { | |
275 | mpihelp_divrem(rp + msize, 0, rp, rsize, mp, msize); | |
276 | rsize = msize; | |
277 | } | |
278 | ||
279 | /* Remove any leading zero words from the result. */ | |
280 | if (mod_shift_cnt) | |
281 | mpihelp_rshift(rp, rp, rsize, mod_shift_cnt); | |
282 | MPN_NORMALIZE(rp, rsize); | |
cdec9cb5 DK |
283 | } |
284 | ||
285 | if (negative_result && rsize) { | |
286 | if (mod_shift_cnt) | |
287 | mpihelp_rshift(mp, mp, msize, mod_shift_cnt); | |
288 | mpihelp_sub(rp, mp, msize, rp, rsize); | |
289 | rsize = msize; | |
290 | rsign = msign; | |
291 | MPN_NORMALIZE(rp, rsize); | |
292 | } | |
293 | res->nlimbs = rsize; | |
294 | res->sign = rsign; | |
295 | ||
296 | leave: | |
297 | rc = 0; | |
298 | enomem: | |
c8ea9fce | 299 | mpihelp_release_karatsuba_ctx(&karactx); |
cdec9cb5 DK |
300 | if (assign_rp) |
301 | mpi_assign_limb_space(res, rp, size); | |
302 | if (mp_marker) | |
303 | mpi_free_limb_space(mp_marker); | |
304 | if (bp_marker) | |
305 | mpi_free_limb_space(bp_marker); | |
306 | if (ep_marker) | |
307 | mpi_free_limb_space(ep_marker); | |
308 | if (xp_marker) | |
309 | mpi_free_limb_space(xp_marker); | |
310 | if (tspace) | |
311 | mpi_free_limb_space(tspace); | |
312 | return rc; | |
313 | } | |
314 | EXPORT_SYMBOL_GPL(mpi_powm); |