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  */
mpi_powm(MPI res,MPI base,MPI exp,MPI mod)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(res, 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(msize);
71 	if (!mp)
72 		goto enomem;
73 	mod_shift_cnt = count_leading_zeros(mod->d[msize - 1]);
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;
154 
155 		xp = xp_marker = mpi_alloc_limb_space(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(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(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--;
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(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);
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:
299 	mpihelp_release_karatsuba_ctx(&karactx);
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);
315