1 /* mpiutil.ac  -  Utility functions for MPI
2  * Copyright (C) 1998, 1999 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 
21 #include "mpi-internal.h"
22 
23 /* Constants allocated right away at startup.  */
24 static MPI constants[MPI_NUMBER_OF_CONSTANTS];
25 
26 /* Initialize the MPI subsystem.  This is called early and allows to
27  * do some initialization without taking care of threading issues.
28  */
mpi_init(void)29 static int __init mpi_init(void)
30 {
31 	int idx;
32 	unsigned long value;
33 
34 	for (idx = 0; idx < MPI_NUMBER_OF_CONSTANTS; idx++) {
35 		switch (idx) {
36 		case MPI_C_ZERO:
37 			value = 0;
38 			break;
39 		case MPI_C_ONE:
40 			value = 1;
41 			break;
42 		case MPI_C_TWO:
43 			value = 2;
44 			break;
45 		case MPI_C_THREE:
46 			value = 3;
47 			break;
48 		case MPI_C_FOUR:
49 			value = 4;
50 			break;
51 		case MPI_C_EIGHT:
52 			value = 8;
53 			break;
54 		default:
55 			pr_err("MPI: invalid mpi_const selector %d\n", idx);
56 			return -EFAULT;
57 		}
58 		constants[idx] = mpi_alloc_set_ui(value);
59 		constants[idx]->flags = (16|32);
60 	}
61 
62 	return 0;
63 }
64 postcore_initcall(mpi_init);
65 
66 /* Return a constant MPI descripbed by NO which is one of the
67  * MPI_C_xxx macros.  There is no need to copy this returned value; it
68  * may be used directly.
69  */
mpi_const(enum gcry_mpi_constants no)70 MPI mpi_const(enum gcry_mpi_constants no)
71 {
72 	if ((int)no < 0 || no > MPI_NUMBER_OF_CONSTANTS)
73 		pr_err("MPI: invalid mpi_const selector %d\n", no);
74 	if (!constants[no])
75 		pr_err("MPI: MPI subsystem not initialized\n");
76 	return constants[no];
77 }
78 EXPORT_SYMBOL_GPL(mpi_const);
79 
80 /****************
81  * Note:  It was a bad idea to use the number of limbs to allocate
82  *	  because on a alpha the limbs are large but we normally need
83  *	  integers of n bits - So we should change this to bits (or bytes).
84  *
85  *	  But mpi_alloc is used in a lot of places :-)
86  */
mpi_alloc(unsigned nlimbs)87 MPI mpi_alloc(unsigned nlimbs)
88 {
89 	MPI a;
90 
91 	a = kmalloc(sizeof *a, GFP_KERNEL);
92 	if (!a)
93 		return a;
94 
95 	if (nlimbs) {
96 		a->d = mpi_alloc_limb_space(nlimbs);
97 		if (!a->d) {
98 			kfree(a);
99 			return NULL;
100 		}
101 	} else {
102 		a->d = NULL;
103 	}
104 
105 	a->alloced = nlimbs;
106 	a->nlimbs = 0;
107 	a->sign = 0;
108 	a->flags = 0;
109 	a->nbits = 0;
110 	return a;
111 }
112 EXPORT_SYMBOL_GPL(mpi_alloc);
113 
mpi_alloc_limb_space(unsigned nlimbs)114 mpi_ptr_t mpi_alloc_limb_space(unsigned nlimbs)
115 {
116 	size_t len = nlimbs * sizeof(mpi_limb_t);
117 
118 	if (!len)
119 		return NULL;
120 
121 	return kmalloc(len, GFP_KERNEL);
122 }
123 
mpi_free_limb_space(mpi_ptr_t a)124 void mpi_free_limb_space(mpi_ptr_t a)
125 {
126 	if (!a)
127 		return;
128 
129 	kfree_sensitive(a);
130 }
131 
mpi_assign_limb_space(MPI a,mpi_ptr_t ap,unsigned nlimbs)132 void mpi_assign_limb_space(MPI a, mpi_ptr_t ap, unsigned nlimbs)
133 {
134 	mpi_free_limb_space(a->d);
135 	a->d = ap;
136 	a->alloced = nlimbs;
137 }
138 
139 /****************
140  * Resize the array of A to NLIMBS. the additional space is cleared
141  * (set to 0) [done by m_realloc()]
142  */
mpi_resize(MPI a,unsigned nlimbs)143 int mpi_resize(MPI a, unsigned nlimbs)
144 {
145 	void *p;
146 
147 	if (nlimbs <= a->alloced)
148 		return 0;	/* no need to do it */
149 
150 	if (a->d) {
151 		p = kcalloc(nlimbs, sizeof(mpi_limb_t), GFP_KERNEL);
152 		if (!p)
153 			return -ENOMEM;
154 		memcpy(p, a->d, a->alloced * sizeof(mpi_limb_t));
155 		kfree_sensitive(a->d);
156 		a->d = p;
157 	} else {
158 		a->d = kcalloc(nlimbs, sizeof(mpi_limb_t), GFP_KERNEL);
159 		if (!a->d)
160 			return -ENOMEM;
161 	}
162 	a->alloced = nlimbs;
163 	return 0;
164 }
165 
mpi_clear(MPI a)166 void mpi_clear(MPI a)
167 {
168 	if (!a)
169 		return;
170 	a->nlimbs = 0;
171 	a->flags = 0;
172 }
173 EXPORT_SYMBOL_GPL(mpi_clear);
174 
mpi_free(MPI a)175 void mpi_free(MPI a)
176 {
177 	if (!a)
178 		return;
179 
180 	if (a->flags & 4)
181 		kfree_sensitive(a->d);
182 	else
183 		mpi_free_limb_space(a->d);
184 
185 	if (a->flags & ~7)
186 		pr_info("invalid flag value in mpi\n");
187 	kfree(a);
188 }
189 EXPORT_SYMBOL_GPL(mpi_free);
190 
191 /****************
192  * Note: This copy function should not interpret the MPI
193  *	 but copy it transparently.
194  */
mpi_copy(MPI a)195 MPI mpi_copy(MPI a)
196 {
197 	int i;
198 	MPI b;
199 
200 	if (a) {
201 		b = mpi_alloc(a->nlimbs);
202 		b->nlimbs = a->nlimbs;
203 		b->sign = a->sign;
204 		b->flags = a->flags;
205 		b->flags &= ~(16|32); /* Reset the immutable and constant flags. */
206 		for (i = 0; i < b->nlimbs; i++)
207 			b->d[i] = a->d[i];
208 	} else
209 		b = NULL;
210 	return b;
211 }
212 
213 /****************
214  * This function allocates an MPI which is optimized to hold
215  * a value as large as the one given in the argument and allocates it
216  * with the same flags as A.
217  */
mpi_alloc_like(MPI a)218 MPI mpi_alloc_like(MPI a)
219 {
220 	MPI b;
221 
222 	if (a) {
223 		b = mpi_alloc(a->nlimbs);
224 		b->nlimbs = 0;
225 		b->sign = 0;
226 		b->flags = a->flags;
227 	} else
228 		b = NULL;
229 
230 	return b;
231 }
232 
233 
234 /* Set U into W and release U.  If W is NULL only U will be released. */
mpi_snatch(MPI w,MPI u)235 void mpi_snatch(MPI w, MPI u)
236 {
237 	if (w) {
238 		mpi_assign_limb_space(w, u->d, u->alloced);
239 		w->nlimbs = u->nlimbs;
240 		w->sign   = u->sign;
241 		w->flags  = u->flags;
242 		u->alloced = 0;
243 		u->nlimbs = 0;
244 		u->d = NULL;
245 	}
246 	mpi_free(u);
247 }
248 
249 
mpi_set(MPI w,MPI u)250 MPI mpi_set(MPI w, MPI u)
251 {
252 	mpi_ptr_t wp, up;
253 	mpi_size_t usize = u->nlimbs;
254 	int usign = u->sign;
255 
256 	if (!w)
257 		w = mpi_alloc(mpi_get_nlimbs(u));
258 	RESIZE_IF_NEEDED(w, usize);
259 	wp = w->d;
260 	up = u->d;
261 	MPN_COPY(wp, up, usize);
262 	w->nlimbs = usize;
263 	w->flags = u->flags;
264 	w->flags &= ~(16|32); /* Reset the immutable and constant flags.  */
265 	w->sign = usign;
266 	return w;
267 }
268 EXPORT_SYMBOL_GPL(mpi_set);
269 
mpi_set_ui(MPI w,unsigned long u)270 MPI mpi_set_ui(MPI w, unsigned long u)
271 {
272 	if (!w)
273 		w = mpi_alloc(1);
274 	/* FIXME: If U is 0 we have no need to resize and thus possible
275 	 * allocating the limbs.
276 	 */
277 	RESIZE_IF_NEEDED(w, 1);
278 	w->d[0] = u;
279 	w->nlimbs = u ? 1 : 0;
280 	w->sign = 0;
281 	w->flags = 0;
282 	return w;
283 }
284 EXPORT_SYMBOL_GPL(mpi_set_ui);
285 
mpi_alloc_set_ui(unsigned long u)286 MPI mpi_alloc_set_ui(unsigned long u)
287 {
288 	MPI w = mpi_alloc(1);
289 	w->d[0] = u;
290 	w->nlimbs = u ? 1 : 0;
291 	w->sign = 0;
292 	return w;
293 }
294 
295 /****************
296  * Swap the value of A and B, when SWAP is 1.
297  * Leave the value when SWAP is 0.
298  * This implementation should be constant-time regardless of SWAP.
299  */
mpi_swap_cond(MPI a,MPI b,unsigned long swap)300 void mpi_swap_cond(MPI a, MPI b, unsigned long swap)
301 {
302 	mpi_size_t i;
303 	mpi_size_t nlimbs;
304 	mpi_limb_t mask = ((mpi_limb_t)0) - swap;
305 	mpi_limb_t x;
306 
307 	if (a->alloced > b->alloced)
308 		nlimbs = b->alloced;
309 	else
310 		nlimbs = a->alloced;
311 	if (a->nlimbs > nlimbs || b->nlimbs > nlimbs)
312 		return;
313 
314 	for (i = 0; i < nlimbs; i++) {
315 		x = mask & (a->d[i] ^ b->d[i]);
316 		a->d[i] = a->d[i] ^ x;
317 		b->d[i] = b->d[i] ^ x;
318 	}
319 
320 	x = mask & (a->nlimbs ^ b->nlimbs);
321 	a->nlimbs = a->nlimbs ^ x;
322 	b->nlimbs = b->nlimbs ^ x;
323 
324 	x = mask & (a->sign ^ b->sign);
325 	a->sign = a->sign ^ x;
326 	b->sign = b->sign ^ x;
327 }
328 
329 MODULE_DESCRIPTION("Multiprecision maths library");
330 MODULE_LICENSE("GPL");
331