1 | // SPDX-License-Identifier: GPL-2.0-or-later |
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 | * |
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 | |
16 | #include <linux/sched.h> |
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; |
27 | struct karatsuba_ctx karactx = {}; |
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; |
32 | int msign, bsign, rsign; |
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; |
44 | msign = mod->sign; |
45 | |
46 | rp = res->d; |
47 | ep = exp->d; |
48 | |
49 | if (!msize) |
50 | return -EINVAL; |
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. */ |
55 | res->nlimbs = (msize == 1 && mod->d[0] == 1) ? 0 : 1; |
56 | if (res->nlimbs) { |
57 | if (mpi_resize(a: res, nlimbs: 1) < 0) |
58 | goto enomem; |
59 | rp = res->d; |
60 | rp[0] = 1; |
61 | } |
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(nlimbs: msize); |
71 | if (!mp) |
72 | goto enomem; |
73 | mod_shift_cnt = count_leading_zeros(x: mod->d[msize - 1]); |
74 | if (mod_shift_cnt) |
75 | mpihelp_lshift(wp: mp, up: mod->d, usize: msize, cnt: 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(nlimbs: 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(qp: bp + msize, qextra_limbs: 0, np: bp, nsize: bsize, dp: mp, dsize: 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(nlimbs: size); |
110 | if (!rp) |
111 | goto enomem; |
112 | assign_rp = 1; |
113 | } else { |
114 | if (mpi_resize(a: res, nlimbs: 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(nlimbs: 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(nlimbs: 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(nlimbs: 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; |
154 | |
155 | xp = xp_marker = mpi_alloc_limb_space(nlimbs: 2 * (msize + 1)); |
156 | if (!xp) |
157 | goto enomem; |
158 | |
159 | negative_result = (ep[0] & 1) && base->sign; |
160 | |
161 | i = esize - 1; |
162 | e = ep[i]; |
163 | c = count_leading_zeros(x: e); |
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(prodp: xp, up: rp, size: rsize); |
185 | else { |
186 | if (!tspace) { |
187 | tsize = 2 * rsize; |
188 | tspace = |
189 | mpi_alloc_limb_space(nlimbs: tsize); |
190 | if (!tspace) |
191 | goto enomem; |
192 | } else if (tsize < (2 * rsize)) { |
193 | mpi_free_limb_space(a: tspace); |
194 | tsize = 2 * rsize; |
195 | tspace = |
196 | mpi_alloc_limb_space(nlimbs: tsize); |
197 | if (!tspace) |
198 | goto enomem; |
199 | } |
200 | mpih_sqr_n(prodp: xp, up: rp, size: rsize, tspace); |
201 | } |
202 | |
203 | xsize = 2 * rsize; |
204 | if (xsize > msize) { |
205 | mpihelp_divrem(qp: xp + msize, qextra_limbs: 0, np: xp, nsize: xsize, |
206 | dp: mp, dsize: 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 | (prodp: xp, up: rp, usize: rsize, vp: bp, vsize: bsize, |
221 | result: &tmp) < 0) |
222 | goto enomem; |
223 | } else { |
224 | if (mpihelp_mul_karatsuba_case |
225 | (prodp: xp, up: rp, usize: rsize, vp: bp, vsize: bsize, |
226 | ctx: &karactx) < 0) |
227 | goto enomem; |
228 | } |
229 | |
230 | xsize = rsize + bsize; |
231 | if (xsize > msize) { |
232 | mpihelp_divrem(qp: xp + msize, qextra_limbs: 0, |
233 | np: xp, nsize: xsize, dp: mp, |
234 | dsize: msize); |
235 | xsize = msize; |
236 | } |
237 | |
238 | tp = rp; |
239 | rp = xp; |
240 | xp = tp; |
241 | rsize = xsize; |
242 | } |
243 | e <<= 1; |
244 | c--; |
245 | cond_resched(); |
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(wp: res->d, up: rp, usize: rsize, cnt: 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(qp: rp + msize, qextra_limbs: 0, np: rp, nsize: rsize, dp: mp, dsize: msize); |
276 | rsize = msize; |
277 | } |
278 | |
279 | /* Remove any leading zero words from the result. */ |
280 | if (mod_shift_cnt) |
281 | mpihelp_rshift(wp: rp, up: rp, usize: rsize, cnt: mod_shift_cnt); |
282 | MPN_NORMALIZE(rp, rsize); |
283 | } |
284 | |
285 | if (negative_result && rsize) { |
286 | if (mod_shift_cnt) |
287 | mpihelp_rshift(wp: mp, up: mp, usize: msize, cnt: mod_shift_cnt); |
288 | mpihelp_sub(res_ptr: rp, s1_ptr: mp, s1_size: msize, s2_ptr: rp, s2_size: 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: |
299 | mpihelp_release_karatsuba_ctx(ctx: &karactx); |
300 | if (assign_rp) |
301 | mpi_assign_limb_space(a: res, ap: rp, nlimbs: size); |
302 | if (mp_marker) |
303 | mpi_free_limb_space(a: mp_marker); |
304 | if (bp_marker) |
305 | mpi_free_limb_space(a: bp_marker); |
306 | if (ep_marker) |
307 | mpi_free_limb_space(a: ep_marker); |
308 | if (xp_marker) |
309 | mpi_free_limb_space(a: xp_marker); |
310 | if (tspace) |
311 | mpi_free_limb_space(a: tspace); |
312 | return rc; |
313 | } |
314 | EXPORT_SYMBOL_GPL(mpi_powm); |
315 | |