1 /* wolfmath.c
2 *
3 * Copyright (C) 2006-2021 wolfSSL Inc.
4 *
5 * This file is part of wolfSSL.
6 *
7 * wolfSSL is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
11 *
12 * wolfSSL is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335, USA
20 */
21
22
23 /* common functions for either math library */
24
25 #ifdef HAVE_CONFIG_H
26 #include <config.h>
27 #endif
28
29 /* in case user set USE_FAST_MATH there */
30 #include <wolfssl/wolfcrypt/settings.h>
31
32 #include <wolfssl/wolfcrypt/integer.h>
33
34 #include <wolfssl/wolfcrypt/error-crypt.h>
35 #include <wolfssl/wolfcrypt/logging.h>
36
37 #if defined(USE_FAST_MATH) || !defined(NO_BIG_INT)
38
39 #ifdef WOLFSSL_ASYNC_CRYPT
40 #include <wolfssl/wolfcrypt/async.h>
41 #endif
42
43 #ifdef NO_INLINE
44 #include <wolfssl/wolfcrypt/misc.h>
45 #else
46 #define WOLFSSL_MISC_INCLUDED
47 #include <wolfcrypt/src/misc.c>
48 #endif
49
50
51 #if !defined(WC_NO_CACHE_RESISTANT) && \
52 ((defined(HAVE_ECC) && defined(ECC_TIMING_RESISTANT)) || \
53 (defined(USE_FAST_MATH) && defined(TFM_TIMING_RESISTANT)))
54
55 /* all off / all on pointer addresses for constant calculations */
56 /* ecc.c uses same table */
57 const wc_ptr_t wc_off_on_addr[2] =
58 {
59 #if defined(WC_64BIT_CPU)
60 W64LIT(0x0000000000000000),
61 W64LIT(0xffffffffffffffff)
62 #elif defined(WC_16BIT_CPU)
63 0x0000U,
64 0xffffU
65 #else
66 /* 32 bit */
67 0x00000000U,
68 0xffffffffU
69 #endif
70 };
71 #endif
72
73
get_digit_count(const mp_int * a)74 int get_digit_count(const mp_int* a)
75 {
76 if (a == NULL)
77 return 0;
78
79 return a->used;
80 }
81
get_digit(const mp_int * a,int n)82 mp_digit get_digit(const mp_int* a, int n)
83 {
84 if (a == NULL)
85 return 0;
86
87 return (n >= a->used || n < 0) ? 0 : a->dp[n];
88 }
89
90 #if defined(HAVE_ECC) || defined(WOLFSSL_MP_COND_COPY)
91 /* Conditionally copy a into b. Performed in constant time.
92 *
93 * a MP integer to copy.
94 * copy On 1, copy a into b. on 0 leave b unchanged.
95 * b MP integer to copy into.
96 * returns BAD_FUNC_ARG when a or b is NULL, MEMORY_E when growing b fails and
97 * MP_OKAY otherwise.
98 */
mp_cond_copy(mp_int * a,int copy,mp_int * b)99 int mp_cond_copy(mp_int* a, int copy, mp_int* b)
100 {
101 int err = MP_OKAY;
102 int i;
103 #if defined(SP_WORD_SIZE) && SP_WORD_SIZE == 8
104 unsigned int mask = (unsigned int)0 - copy;
105 #else
106 mp_digit mask = (mp_digit)0 - copy;
107 #endif
108
109 if (a == NULL || b == NULL)
110 err = BAD_FUNC_ARG;
111
112 /* Ensure b has enough space to copy a into */
113 if (err == MP_OKAY)
114 err = mp_grow(b, a->used + 1);
115 if (err == MP_OKAY) {
116 /* When mask 0, b is unchanged2
117 * When mask all set, b ^ b ^ a = a
118 */
119 /* Conditionaly copy all digits and then number of used diigits.
120 * get_digit() returns 0 when index greater than available digit.
121 */
122 for (i = 0; i < a->used; i++) {
123 b->dp[i] ^= (get_digit(a, i) ^ get_digit(b, i)) & mask;
124 }
125 for (; i < b->used; i++) {
126 b->dp[i] ^= (get_digit(a, i) ^ get_digit(b, i)) & mask;
127 }
128 b->used ^= (a->used ^ b->used) & (int)mask;
129 #if (!defined(WOLFSSL_SP_MATH) && !defined(WOLFSSL_SP_MATH_ALL)) || \
130 defined(WOLFSSL_SP_INT_NEGATIVE)
131 b->sign ^= (a->sign ^ b->sign) & (int)mask;
132 #endif
133 }
134
135 return err;
136 }
137 #endif
138
139 #ifndef WC_NO_RNG
get_rand_digit(WC_RNG * rng,mp_digit * d)140 int get_rand_digit(WC_RNG* rng, mp_digit* d)
141 {
142 return wc_RNG_GenerateBlock(rng, (byte*)d, sizeof(mp_digit));
143 }
144
145 #if defined(WC_RSA_BLINDING) || defined(WOLFCRYPT_HAVE_SAKKE)
mp_rand(mp_int * a,int digits,WC_RNG * rng)146 int mp_rand(mp_int* a, int digits, WC_RNG* rng)
147 {
148 int ret = 0;
149 int cnt = digits * sizeof(mp_digit);
150 #if !defined(USE_FAST_MATH) && !defined(WOLFSSL_SP_MATH)
151 int i;
152 #endif
153
154 if (rng == NULL) {
155 ret = MISSING_RNG_E;
156 }
157 else if (a == NULL || digits == 0) {
158 ret = BAD_FUNC_ARG;
159 }
160
161 #if !defined(USE_FAST_MATH) && !defined(WOLFSSL_SP_MATH)
162 /* allocate space for digits */
163 if (ret == MP_OKAY) {
164 ret = mp_set_bit(a, digits * DIGIT_BIT - 1);
165 }
166 #else
167 #if defined(WOLFSSL_SP_MATH) || defined(WOLFSSL_SP_MATH_ALL)
168 if ((ret == MP_OKAY) && (digits > SP_INT_DIGITS))
169 #else
170 if ((ret == MP_OKAY) && (digits > FP_SIZE))
171 #endif
172 {
173 ret = BAD_FUNC_ARG;
174 }
175 if (ret == MP_OKAY) {
176 a->used = digits;
177 }
178 #endif
179 /* fill the data with random bytes */
180 if (ret == MP_OKAY) {
181 ret = wc_RNG_GenerateBlock(rng, (byte*)a->dp, cnt);
182 }
183 if (ret == MP_OKAY) {
184 #if !defined(USE_FAST_MATH) && !defined(WOLFSSL_SP_MATH)
185 /* Mask down each digit to only bits used */
186 for (i = 0; i < a->used; i++) {
187 a->dp[i] &= MP_MASK;
188 }
189 #endif
190 /* ensure top digit is not zero */
191 while ((ret == MP_OKAY) && (a->dp[a->used - 1] == 0)) {
192 ret = get_rand_digit(rng, &a->dp[a->used - 1]);
193 #if !defined(USE_FAST_MATH) && !defined(WOLFSSL_SP_MATH)
194 a->dp[a->used - 1] &= MP_MASK;
195 #endif
196 }
197 }
198
199 return ret;
200 }
201 #endif /* WC_RSA_BLINDING || WOLFCRYPT_HAVE_SAKKE */
202 #endif
203
204 #if defined(HAVE_ECC) || defined(WOLFSSL_EXPORT_INT)
205 /* export an mp_int as unsigned char or hex string
206 * encType is WC_TYPE_UNSIGNED_BIN or WC_TYPE_HEX_STR
207 * return MP_OKAY on success */
wc_export_int(mp_int * mp,byte * buf,word32 * len,word32 keySz,int encType)208 int wc_export_int(mp_int* mp, byte* buf, word32* len, word32 keySz,
209 int encType)
210 {
211 int err;
212
213 if (mp == NULL || buf == NULL || len == NULL)
214 return BAD_FUNC_ARG;
215
216 if (encType == WC_TYPE_HEX_STR) {
217 /* for WC_TYPE_HEX_STR the keySz is not used.
218 * The size is computed via mp_radix_size and checked with len input */
219 #ifdef WC_MP_TO_RADIX
220 int size = 0;
221 err = mp_radix_size(mp, MP_RADIX_HEX, &size);
222 if (err == MP_OKAY) {
223 /* make sure we can fit result */
224 if (*len < (word32)size) {
225 *len = (word32)size;
226 return BUFFER_E;
227 }
228 *len = (word32)size;
229 err = mp_tohex(mp, (char*)buf);
230 }
231 #else
232 err = NOT_COMPILED_IN;
233 #endif
234 }
235 else {
236 /* for WC_TYPE_UNSIGNED_BIN keySz is used to zero pad.
237 * The key size is always returned as the size */
238 if (*len < keySz) {
239 *len = keySz;
240 return BUFFER_E;
241 }
242 *len = keySz;
243 XMEMSET(buf, 0, *len);
244 err = mp_to_unsigned_bin(mp, buf + (keySz - mp_unsigned_bin_size(mp)));
245 }
246
247 return err;
248 }
249 #endif
250
251
252 #ifdef HAVE_WOLF_BIGINT
wc_bigint_init(WC_BIGINT * a)253 void wc_bigint_init(WC_BIGINT* a)
254 {
255 if (a != NULL) {
256 a->buf = NULL;
257 a->len = 0;
258 a->heap = NULL;
259 }
260 }
261
wc_bigint_alloc(WC_BIGINT * a,word32 sz)262 int wc_bigint_alloc(WC_BIGINT* a, word32 sz)
263 {
264 int err = MP_OKAY;
265
266 if (a == NULL)
267 return BAD_FUNC_ARG;
268
269 if (sz > 0) {
270 if (a->buf && sz > a->len) {
271 wc_bigint_free(a);
272 }
273 if (a->buf == NULL) {
274 a->buf = (byte*)XMALLOC(sz, a->heap, DYNAMIC_TYPE_WOLF_BIGINT);
275 if (a->buf == NULL) {
276 err = MP_MEM;
277 }
278 }
279 else {
280 XMEMSET(a->buf, 0, sz);
281 }
282 }
283 a->len = sz;
284
285 return err;
286 }
287
288 /* assumes input is big endian format */
wc_bigint_from_unsigned_bin(WC_BIGINT * a,const byte * in,word32 inlen)289 int wc_bigint_from_unsigned_bin(WC_BIGINT* a, const byte* in, word32 inlen)
290 {
291 int err;
292
293 if (a == NULL || in == NULL || inlen == 0)
294 return BAD_FUNC_ARG;
295
296 err = wc_bigint_alloc(a, inlen);
297 if (err == 0) {
298 XMEMCPY(a->buf, in, inlen);
299 }
300
301 return err;
302 }
303
wc_bigint_to_unsigned_bin(WC_BIGINT * a,byte * out,word32 * outlen)304 int wc_bigint_to_unsigned_bin(WC_BIGINT* a, byte* out, word32* outlen)
305 {
306 word32 sz;
307
308 if (a == NULL || out == NULL || outlen == NULL || *outlen == 0)
309 return BAD_FUNC_ARG;
310
311 /* trim to fit into output buffer */
312 sz = a->len;
313 if (a->len > *outlen) {
314 WOLFSSL_MSG("wc_bigint_export: Truncating output");
315 sz = *outlen;
316 }
317
318 if (a->buf) {
319 XMEMCPY(out, a->buf, sz);
320 }
321
322 *outlen = sz;
323
324 return MP_OKAY;
325 }
326
wc_bigint_zero(WC_BIGINT * a)327 void wc_bigint_zero(WC_BIGINT* a)
328 {
329 if (a && a->buf) {
330 ForceZero(a->buf, a->len);
331 }
332 }
333
wc_bigint_free(WC_BIGINT * a)334 void wc_bigint_free(WC_BIGINT* a)
335 {
336 if (a) {
337 if (a->buf) {
338 XFREE(a->buf, a->heap, DYNAMIC_TYPE_WOLF_BIGINT);
339 }
340 a->buf = NULL;
341 a->len = 0;
342 }
343 }
344
345 /* sz: make sure the buffer is at least that size and zero padded.
346 * A `sz == 0` will use the size of `src`.
347 * The calulcates sz is stored into dst->len in `wc_bigint_alloc`.
348 */
wc_mp_to_bigint_sz(mp_int * src,WC_BIGINT * dst,word32 sz)349 int wc_mp_to_bigint_sz(mp_int* src, WC_BIGINT* dst, word32 sz)
350 {
351 int err;
352 word32 x, y;
353
354 if (src == NULL || dst == NULL)
355 return BAD_FUNC_ARG;
356
357 /* get size of source */
358 x = mp_unsigned_bin_size(src);
359 if (sz < x)
360 sz = x;
361
362 /* make sure destination is allocated and large enough */
363 err = wc_bigint_alloc(dst, sz);
364 if (err == MP_OKAY) {
365
366 /* leading zero pad */
367 y = sz - x;
368 XMEMSET(dst->buf, 0, y);
369
370 /* export src as unsigned bin to destination buf */
371 err = mp_to_unsigned_bin(src, dst->buf + y);
372 }
373
374 return err;
375 }
376
wc_mp_to_bigint(mp_int * src,WC_BIGINT * dst)377 int wc_mp_to_bigint(mp_int* src, WC_BIGINT* dst)
378 {
379 if (src == NULL || dst == NULL)
380 return BAD_FUNC_ARG;
381
382 return wc_mp_to_bigint_sz(src, dst, 0);
383 }
384
wc_bigint_to_mp(WC_BIGINT * src,mp_int * dst)385 int wc_bigint_to_mp(WC_BIGINT* src, mp_int* dst)
386 {
387 int err;
388
389 if (src == NULL || dst == NULL)
390 return BAD_FUNC_ARG;
391
392 if (src->buf == NULL)
393 return BAD_FUNC_ARG;
394
395 err = mp_read_unsigned_bin(dst, src->buf, src->len);
396 wc_bigint_free(src);
397
398 return err;
399 }
400 #endif /* HAVE_WOLF_BIGINT */
401
402 #endif /* USE_FAST_MATH || !NO_BIG_INT */
403