Branch data Line data Source code
1 : : /*
2 : : * Multi-precision integer library
3 : : *
4 : : * Copyright The Mbed TLS Contributors
5 : : * SPDX-License-Identifier: Apache-2.0 OR GPL-2.0-or-later
6 : : */
7 : :
8 : : /*
9 : : * The following sources were referenced in the design of this Multi-precision
10 : : * Integer library:
11 : : *
12 : : * [1] Handbook of Applied Cryptography - 1997
13 : : * Menezes, van Oorschot and Vanstone
14 : : *
15 : : * [2] Multi-Precision Math
16 : : * Tom St Denis
17 : : * https://github.com/libtom/libtommath/blob/develop/tommath.pdf
18 : : *
19 : : * [3] GNU Multi-Precision Arithmetic Library
20 : : * https://gmplib.org/manual/index.html
21 : : *
22 : : */
23 : :
24 : : #include "common.h"
25 : :
26 : : #if defined(MBEDTLS_BIGNUM_C)
27 : :
28 : : #include "mbedtls/bignum.h"
29 : : #include "bignum_core.h"
30 : : #include "bignum_internal.h"
31 : : #include "bn_mul.h"
32 : : #include "mbedtls/platform_util.h"
33 : : #include "mbedtls/error.h"
34 : : #include "constant_time_internal.h"
35 : :
36 : : #include <limits.h>
37 : : #include <string.h>
38 : :
39 : : #include "mbedtls/platform.h"
40 : :
41 : :
42 : :
43 : : /*
44 : : * Conditionally select an MPI sign in constant time.
45 : : * (MPI sign is the field s in mbedtls_mpi. It is unsigned short and only 1 and -1 are valid
46 : : * values.)
47 : : */
48 : 28580 : static inline signed short mbedtls_ct_mpi_sign_if(mbedtls_ct_condition_t cond,
49 : : signed short sign1, signed short sign2)
50 : : {
51 : 28580 : return (signed short) mbedtls_ct_uint_if(cond, sign1 + 1, sign2 + 1) - 1;
52 : : }
53 : :
54 : : /*
55 : : * Compare signed values in constant time
56 : : */
57 : 0 : int mbedtls_mpi_lt_mpi_ct(const mbedtls_mpi *X,
58 : : const mbedtls_mpi *Y,
59 : : unsigned *ret)
60 : : {
61 : 0 : mbedtls_ct_condition_t different_sign, X_is_negative, Y_is_negative, result;
62 : :
63 [ # # ]: 0 : if (X->n != Y->n) {
64 : : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
65 : : }
66 : :
67 : : /*
68 : : * Set N_is_negative to MBEDTLS_CT_FALSE if N >= 0, MBEDTLS_CT_TRUE if N < 0.
69 : : * We know that N->s == 1 if N >= 0 and N->s == -1 if N < 0.
70 : : */
71 : 0 : X_is_negative = mbedtls_ct_bool((X->s & 2) >> 1);
72 : 0 : Y_is_negative = mbedtls_ct_bool((Y->s & 2) >> 1);
73 : :
74 : : /*
75 : : * If the signs are different, then the positive operand is the bigger.
76 : : * That is if X is negative (X_is_negative == 1), then X < Y is true and it
77 : : * is false if X is positive (X_is_negative == 0).
78 : : */
79 : 0 : different_sign = mbedtls_ct_bool_ne(X_is_negative, Y_is_negative); // true if different sign
80 : 0 : result = mbedtls_ct_bool_and(different_sign, X_is_negative);
81 : :
82 : : /*
83 : : * Assuming signs are the same, compare X and Y. We switch the comparison
84 : : * order if they are negative so that we get the right result, regardles of
85 : : * sign.
86 : : */
87 : :
88 : : /* This array is used to conditionally swap the pointers in const time */
89 : 0 : void * const p[2] = { X->p, Y->p };
90 : 0 : size_t i = mbedtls_ct_size_if_else_0(X_is_negative, 1);
91 : 0 : mbedtls_ct_condition_t lt = mbedtls_mpi_core_lt_ct(p[i], p[i ^ 1], X->n);
92 : :
93 : : /*
94 : : * Store in result iff the signs are the same (i.e., iff different_sign == false). If
95 : : * the signs differ, result has already been set, so we don't change it.
96 : : */
97 : 0 : result = mbedtls_ct_bool_or(result,
98 : : mbedtls_ct_bool_and(mbedtls_ct_bool_not(different_sign), lt));
99 : :
100 : 0 : *ret = mbedtls_ct_uint_if_else_0(result, 1);
101 : :
102 : 0 : return 0;
103 : : }
104 : :
105 : : /*
106 : : * Conditionally assign X = Y, without leaking information
107 : : * about whether the assignment was made or not.
108 : : * (Leaking information about the respective sizes of X and Y is ok however.)
109 : : */
110 : : #if defined(_MSC_VER) && defined(MBEDTLS_PLATFORM_IS_WINDOWS_ON_ARM64) && \
111 : : (_MSC_FULL_VER < 193131103)
112 : : /*
113 : : * MSVC miscompiles this function if it's inlined prior to Visual Studio 2022 version 17.1. See:
114 : : * https://developercommunity.visualstudio.com/t/c-compiler-miscompiles-part-of-mbedtls-library-on/1646989
115 : : */
116 : : __declspec(noinline)
117 : : #endif
118 : 28580 : int mbedtls_mpi_safe_cond_assign(mbedtls_mpi *X,
119 : : const mbedtls_mpi *Y,
120 : : unsigned char assign)
121 : : {
122 : 28580 : int ret = 0;
123 : :
124 [ - + ]: 28580 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, Y->n));
125 : :
126 : : {
127 : 28580 : mbedtls_ct_condition_t do_assign = mbedtls_ct_bool(assign);
128 : :
129 : 28580 : X->s = mbedtls_ct_mpi_sign_if(do_assign, Y->s, X->s);
130 : :
131 : 28580 : mbedtls_mpi_core_cond_assign(X->p, Y->p, Y->n, do_assign);
132 : :
133 : 28580 : mbedtls_ct_condition_t do_not_assign = mbedtls_ct_bool_not(do_assign);
134 [ + + ]: 28740 : for (size_t i = Y->n; i < X->n; i++) {
135 : 160 : X->p[i] = mbedtls_ct_mpi_uint_if_else_0(do_not_assign, X->p[i]);
136 : : }
137 : : }
138 : :
139 : 28580 : cleanup:
140 : 28580 : return ret;
141 : : }
142 : :
143 : : /*
144 : : * Conditionally swap X and Y, without leaking information
145 : : * about whether the swap was made or not.
146 : : * Here it is not ok to simply swap the pointers, which would lead to
147 : : * different memory access patterns when X and Y are used afterwards.
148 : : */
149 : 0 : int mbedtls_mpi_safe_cond_swap(mbedtls_mpi *X,
150 : : mbedtls_mpi *Y,
151 : : unsigned char swap)
152 : : {
153 : 0 : int ret = 0;
154 : 0 : int s;
155 : :
156 [ # # ]: 0 : if (X == Y) {
157 : : return 0;
158 : : }
159 : :
160 : 0 : mbedtls_ct_condition_t do_swap = mbedtls_ct_bool(swap);
161 : :
162 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, Y->n));
163 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(Y, X->n));
164 : :
165 : 0 : s = X->s;
166 : 0 : X->s = mbedtls_ct_mpi_sign_if(do_swap, Y->s, X->s);
167 : 0 : Y->s = mbedtls_ct_mpi_sign_if(do_swap, s, Y->s);
168 : :
169 : 0 : mbedtls_mpi_core_cond_swap(X->p, Y->p, X->n, do_swap);
170 : :
171 : : cleanup:
172 : : return ret;
173 : : }
174 : :
175 : : /* Implementation that should never be optimized out by the compiler */
176 : : #define mbedtls_mpi_zeroize_and_free(v, n) mbedtls_zeroize_and_free(v, ciL * (n))
177 : :
178 : : /*
179 : : * Initialize one MPI
180 : : */
181 : 237930 : void mbedtls_mpi_init(mbedtls_mpi *X)
182 : : {
183 : 237930 : X->s = 1;
184 : 237930 : X->n = 0;
185 : 237930 : X->p = NULL;
186 : 237930 : }
187 : :
188 : : /*
189 : : * Unallocate one MPI
190 : : */
191 : 236740 : void mbedtls_mpi_free(mbedtls_mpi *X)
192 : : {
193 [ + - ]: 236740 : if (X == NULL) {
194 : : return;
195 : : }
196 : :
197 [ + + ]: 236740 : if (X->p != NULL) {
198 : 169020 : mbedtls_mpi_zeroize_and_free(X->p, X->n);
199 : : }
200 : :
201 : 236740 : X->s = 1;
202 : 236740 : X->n = 0;
203 : 236740 : X->p = NULL;
204 : : }
205 : :
206 : : /*
207 : : * Enlarge to the specified number of limbs
208 : : */
209 : 2023357 : int mbedtls_mpi_grow(mbedtls_mpi *X, size_t nblimbs)
210 : : {
211 : 2023357 : mbedtls_mpi_uint *p;
212 : :
213 [ - + ]: 2023357 : if (nblimbs > MBEDTLS_MPI_MAX_LIMBS) {
214 : : return MBEDTLS_ERR_MPI_ALLOC_FAILED;
215 : : }
216 : :
217 [ + + ]: 2023357 : if (X->n < nblimbs) {
218 [ - + ]: 286223 : if ((p = (mbedtls_mpi_uint *) mbedtls_calloc(nblimbs, ciL)) == NULL) {
219 : : return MBEDTLS_ERR_MPI_ALLOC_FAILED;
220 : : }
221 : :
222 [ + + ]: 286223 : if (X->p != NULL) {
223 : 117203 : memcpy(p, X->p, X->n * ciL);
224 : 117203 : mbedtls_mpi_zeroize_and_free(X->p, X->n);
225 : : }
226 : :
227 : : /* nblimbs fits in n because we ensure that MBEDTLS_MPI_MAX_LIMBS
228 : : * fits, and we've checked that nblimbs <= MBEDTLS_MPI_MAX_LIMBS. */
229 : 286223 : X->n = (unsigned short) nblimbs;
230 : 286223 : X->p = p;
231 : : }
232 : :
233 : : return 0;
234 : : }
235 : :
236 : : /*
237 : : * Resize down as much as possible,
238 : : * while keeping at least the specified number of limbs
239 : : */
240 : 200 : int mbedtls_mpi_shrink(mbedtls_mpi *X, size_t nblimbs)
241 : : {
242 : 200 : mbedtls_mpi_uint *p;
243 : 200 : size_t i;
244 : :
245 [ - + ]: 200 : if (nblimbs > MBEDTLS_MPI_MAX_LIMBS) {
246 : : return MBEDTLS_ERR_MPI_ALLOC_FAILED;
247 : : }
248 : :
249 : : /* Actually resize up if there are currently fewer than nblimbs limbs. */
250 [ - + ]: 200 : if (X->n <= nblimbs) {
251 : 0 : return mbedtls_mpi_grow(X, nblimbs);
252 : : }
253 : : /* After this point, then X->n > nblimbs and in particular X->n > 0. */
254 : :
255 [ + - ]: 1800 : for (i = X->n - 1; i > 0; i--) {
256 [ + + ]: 1800 : if (X->p[i] != 0) {
257 : : break;
258 : : }
259 : : }
260 : 200 : i++;
261 : :
262 : 200 : if (i < nblimbs) {
263 : : i = nblimbs;
264 : : }
265 : :
266 [ - + ]: 200 : if ((p = (mbedtls_mpi_uint *) mbedtls_calloc(i, ciL)) == NULL) {
267 : : return MBEDTLS_ERR_MPI_ALLOC_FAILED;
268 : : }
269 : :
270 [ + - ]: 200 : if (X->p != NULL) {
271 : 200 : memcpy(p, X->p, i * ciL);
272 : 200 : mbedtls_mpi_zeroize_and_free(X->p, X->n);
273 : : }
274 : :
275 : : /* i fits in n because we ensure that MBEDTLS_MPI_MAX_LIMBS
276 : : * fits, and we've checked that i <= nblimbs <= MBEDTLS_MPI_MAX_LIMBS. */
277 : 200 : X->n = (unsigned short) i;
278 : 200 : X->p = p;
279 : :
280 : 200 : return 0;
281 : : }
282 : :
283 : : /* Resize X to have exactly n limbs and set it to 0. */
284 : 90 : static int mbedtls_mpi_resize_clear(mbedtls_mpi *X, size_t limbs)
285 : : {
286 [ - + ]: 90 : if (limbs == 0) {
287 : 0 : mbedtls_mpi_free(X);
288 : 0 : return 0;
289 [ - + ]: 90 : } else if (X->n == limbs) {
290 : 0 : memset(X->p, 0, limbs * ciL);
291 : 0 : X->s = 1;
292 : 0 : return 0;
293 : : } else {
294 : 90 : mbedtls_mpi_free(X);
295 : 90 : return mbedtls_mpi_grow(X, limbs);
296 : : }
297 : : }
298 : :
299 : : /*
300 : : * Copy the contents of Y into X.
301 : : *
302 : : * This function is not constant-time. Leading zeros in Y may be removed.
303 : : *
304 : : * Ensure that X does not shrink. This is not guaranteed by the public API,
305 : : * but some code in the bignum module might still rely on this property.
306 : : */
307 : 914554 : int mbedtls_mpi_copy(mbedtls_mpi *X, const mbedtls_mpi *Y)
308 : : {
309 : 914554 : int ret = 0;
310 : 914554 : size_t i;
311 : :
312 [ + + ]: 914554 : if (X == Y) {
313 : : return 0;
314 : : }
315 : :
316 [ + + ]: 456190 : if (Y->n == 0) {
317 [ - + ]: 12 : if (X->n != 0) {
318 : 0 : X->s = 1;
319 : 0 : memset(X->p, 0, X->n * ciL);
320 : : }
321 : 12 : return 0;
322 : : }
323 : :
324 [ + + ]: 3504426 : for (i = Y->n - 1; i > 0; i--) {
325 [ + + ]: 3504322 : if (Y->p[i] != 0) {
326 : : break;
327 : : }
328 : : }
329 : 456178 : i++;
330 : :
331 : 456178 : X->s = Y->s;
332 : :
333 [ + + ]: 456178 : if (X->n < i) {
334 [ - + ]: 89226 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, i));
335 : : } else {
336 : 366952 : memset(X->p + i, 0, (X->n - i) * ciL);
337 : : }
338 : :
339 : 456178 : memcpy(X->p, Y->p, i * ciL);
340 : :
341 : : cleanup:
342 : :
343 : : return ret;
344 : : }
345 : :
346 : : /*
347 : : * Swap the contents of X and Y
348 : : */
349 : 0 : void mbedtls_mpi_swap(mbedtls_mpi *X, mbedtls_mpi *Y)
350 : : {
351 : 0 : mbedtls_mpi T;
352 : :
353 : 0 : memcpy(&T, X, sizeof(mbedtls_mpi));
354 : 0 : memcpy(X, Y, sizeof(mbedtls_mpi));
355 : 0 : memcpy(Y, &T, sizeof(mbedtls_mpi));
356 : 0 : }
357 : :
358 : 1023350 : static inline mbedtls_mpi_uint mpi_sint_abs(mbedtls_mpi_sint z)
359 : : {
360 [ + + ]: 1023350 : if (z >= 0) {
361 : 1023338 : return z;
362 : : }
363 : : /* Take care to handle the most negative value (-2^(biL-1)) correctly.
364 : : * A naive -z would have undefined behavior.
365 : : * Write this in a way that makes popular compilers happy (GCC, Clang,
366 : : * MSVC). */
367 : 12 : return (mbedtls_mpi_uint) 0 - (mbedtls_mpi_uint) z;
368 : : }
369 : :
370 : : /* Convert x to a sign, i.e. to 1, if x is positive, or -1, if x is negative.
371 : : * This looks awkward but generates smaller code than (x < 0 ? -1 : 1) */
372 : : #define TO_SIGN(x) ((mbedtls_mpi_sint) (((mbedtls_mpi_uint) x) >> (biL - 1)) * -2 + 1)
373 : :
374 : : /*
375 : : * Set value from integer
376 : : */
377 : 537536 : int mbedtls_mpi_lset(mbedtls_mpi *X, mbedtls_mpi_sint z)
378 : : {
379 : 537536 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
380 : :
381 [ - + ]: 537536 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, 1));
382 : 537536 : memset(X->p, 0, X->n * ciL);
383 : :
384 : 537536 : X->p[0] = mpi_sint_abs(z);
385 : 537536 : X->s = TO_SIGN(z);
386 : :
387 : 537536 : cleanup:
388 : :
389 : 537536 : return ret;
390 : : }
391 : :
392 : : /*
393 : : * Get a specific bit
394 : : */
395 : 5256 : int mbedtls_mpi_get_bit(const mbedtls_mpi *X, size_t pos)
396 : : {
397 [ + + ]: 5256 : if (X->n * biL <= pos) {
398 : : return 0;
399 : : }
400 : :
401 : 5216 : return (X->p[pos / biL] >> (pos % biL)) & 0x01;
402 : : }
403 : :
404 : : /*
405 : : * Set a bit to a specific value of 0 or 1
406 : : */
407 : 0 : int mbedtls_mpi_set_bit(mbedtls_mpi *X, size_t pos, unsigned char val)
408 : : {
409 : 0 : int ret = 0;
410 : 0 : size_t off = pos / biL;
411 : 0 : size_t idx = pos % biL;
412 : :
413 [ # # ]: 0 : if (val != 0 && val != 1) {
414 : : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
415 : : }
416 : :
417 [ # # ]: 0 : if (X->n * biL <= pos) {
418 [ # # ]: 0 : if (val == 0) {
419 : : return 0;
420 : : }
421 : :
422 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, off + 1));
423 : : }
424 : :
425 : 0 : X->p[off] &= ~((mbedtls_mpi_uint) 0x01 << idx);
426 : 0 : X->p[off] |= (mbedtls_mpi_uint) val << idx;
427 : :
428 : : cleanup:
429 : :
430 : : return ret;
431 : : }
432 : :
433 : : #if defined(__has_builtin)
434 : : #if (MBEDTLS_MPI_UINT_MAX == UINT_MAX) && __has_builtin(__builtin_ctz)
435 : : #define mbedtls_mpi_uint_ctz __builtin_ctz
436 : : #elif (MBEDTLS_MPI_UINT_MAX == ULONG_MAX) && __has_builtin(__builtin_ctzl)
437 : : #define mbedtls_mpi_uint_ctz __builtin_ctzl
438 : : #elif (MBEDTLS_MPI_UINT_MAX == ULLONG_MAX) && __has_builtin(__builtin_ctzll)
439 : : #define mbedtls_mpi_uint_ctz __builtin_ctzll
440 : : #endif
441 : : #endif
442 : :
443 : : #if !defined(mbedtls_mpi_uint_ctz)
444 : : static size_t mbedtls_mpi_uint_ctz(mbedtls_mpi_uint x)
445 : : {
446 : : size_t count = 0;
447 : : mbedtls_ct_condition_t done = MBEDTLS_CT_FALSE;
448 : :
449 : : for (size_t i = 0; i < biL; i++) {
450 : : mbedtls_ct_condition_t non_zero = mbedtls_ct_bool((x >> i) & 1);
451 : : done = mbedtls_ct_bool_or(done, non_zero);
452 : : count = mbedtls_ct_size_if(done, count, i + 1);
453 : : }
454 : :
455 : : return count;
456 : : }
457 : : #endif
458 : :
459 : : /*
460 : : * Return the number of less significant zero-bits
461 : : */
462 : 0 : size_t mbedtls_mpi_lsb(const mbedtls_mpi *X)
463 : : {
464 : 0 : size_t i;
465 : :
466 [ # # ]: 0 : for (i = 0; i < X->n; i++) {
467 [ # # ]: 0 : if (X->p[i] != 0) {
468 : 0 : return i * biL + mbedtls_mpi_uint_ctz(X->p[i]);
469 : : }
470 : : }
471 : :
472 : : return 0;
473 : : }
474 : :
475 : : /*
476 : : * Return the number of bits
477 : : */
478 : 480818 : size_t mbedtls_mpi_bitlen(const mbedtls_mpi *X)
479 : : {
480 : 480818 : return mbedtls_mpi_core_bitlen(X->p, X->n);
481 : : }
482 : :
483 : : /*
484 : : * Return the total size in bytes
485 : : */
486 : 30 : size_t mbedtls_mpi_size(const mbedtls_mpi *X)
487 : : {
488 : 30 : return (mbedtls_mpi_bitlen(X) + 7) >> 3;
489 : : }
490 : :
491 : : /*
492 : : * Convert an ASCII character to digit value
493 : : */
494 : 0 : static int mpi_get_digit(mbedtls_mpi_uint *d, int radix, char c)
495 : : {
496 : 0 : *d = 255;
497 : :
498 [ # # ]: 0 : if (c >= 0x30 && c <= 0x39) {
499 : 0 : *d = c - 0x30;
500 : : }
501 [ # # ]: 0 : if (c >= 0x41 && c <= 0x46) {
502 : 0 : *d = c - 0x37;
503 : : }
504 [ # # ]: 0 : if (c >= 0x61 && c <= 0x66) {
505 : 0 : *d = c - 0x57;
506 : : }
507 : :
508 [ # # ]: 0 : if (*d >= (mbedtls_mpi_uint) radix) {
509 : 0 : return MBEDTLS_ERR_MPI_INVALID_CHARACTER;
510 : : }
511 : :
512 : : return 0;
513 : : }
514 : :
515 : : /*
516 : : * Import from an ASCII string
517 : : */
518 : 0 : int mbedtls_mpi_read_string(mbedtls_mpi *X, int radix, const char *s)
519 : : {
520 : 0 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
521 : 0 : size_t i, j, slen, n;
522 : 0 : int sign = 1;
523 : 0 : mbedtls_mpi_uint d;
524 : 0 : mbedtls_mpi T;
525 : :
526 [ # # ]: 0 : if (radix < 2 || radix > 16) {
527 : : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
528 : : }
529 : :
530 : 0 : mbedtls_mpi_init(&T);
531 : :
532 [ # # ]: 0 : if (s[0] == 0) {
533 : 0 : mbedtls_mpi_free(X);
534 : 0 : return 0;
535 : : }
536 : :
537 [ # # ]: 0 : if (s[0] == '-') {
538 : 0 : ++s;
539 : 0 : sign = -1;
540 : : }
541 : :
542 : 0 : slen = strlen(s);
543 : :
544 [ # # ]: 0 : if (radix == 16) {
545 [ # # ]: 0 : if (slen > SIZE_MAX >> 2) {
546 : : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
547 : : }
548 : :
549 : 0 : n = BITS_TO_LIMBS(slen << 2);
550 : :
551 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, n));
552 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 0));
553 : :
554 [ # # ]: 0 : for (i = slen, j = 0; i > 0; i--, j++) {
555 [ # # ]: 0 : MBEDTLS_MPI_CHK(mpi_get_digit(&d, radix, s[i - 1]));
556 : 0 : X->p[j / (2 * ciL)] |= d << ((j % (2 * ciL)) << 2);
557 : : }
558 : : } else {
559 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 0));
560 : :
561 [ # # ]: 0 : for (i = 0; i < slen; i++) {
562 [ # # ]: 0 : MBEDTLS_MPI_CHK(mpi_get_digit(&d, radix, s[i]));
563 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int(&T, X, radix));
564 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, &T, d));
565 : : }
566 : : }
567 : :
568 [ # # # # ]: 0 : if (sign < 0 && mbedtls_mpi_bitlen(X) != 0) {
569 : 0 : X->s = -1;
570 : : }
571 : :
572 : 0 : cleanup:
573 : :
574 : 0 : mbedtls_mpi_free(&T);
575 : :
576 : 0 : return ret;
577 : : }
578 : :
579 : : /*
580 : : * Helper to write the digits high-order first.
581 : : */
582 : 0 : static int mpi_write_hlp(mbedtls_mpi *X, int radix,
583 : : char **p, const size_t buflen)
584 : : {
585 : 0 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
586 : 0 : mbedtls_mpi_uint r;
587 : 0 : size_t length = 0;
588 : 0 : char *p_end = *p + buflen;
589 : :
590 : 0 : do {
591 [ # # ]: 0 : if (length >= buflen) {
592 : : return MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL;
593 : : }
594 : :
595 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_mod_int(&r, X, radix));
596 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_div_int(X, NULL, X, radix));
597 : : /*
598 : : * Write the residue in the current position, as an ASCII character.
599 : : */
600 [ # # ]: 0 : if (r < 0xA) {
601 : 0 : *(--p_end) = (char) ('0' + r);
602 : : } else {
603 : 0 : *(--p_end) = (char) ('A' + (r - 0xA));
604 : : }
605 : :
606 : 0 : length++;
607 [ # # ]: 0 : } while (mbedtls_mpi_cmp_int(X, 0) != 0);
608 : :
609 : 0 : memmove(*p, p_end, length);
610 : 0 : *p += length;
611 : :
612 : : cleanup:
613 : :
614 : : return ret;
615 : : }
616 : :
617 : : /*
618 : : * Export into an ASCII string
619 : : */
620 : 0 : int mbedtls_mpi_write_string(const mbedtls_mpi *X, int radix,
621 : : char *buf, size_t buflen, size_t *olen)
622 : : {
623 : 0 : int ret = 0;
624 : 0 : size_t n;
625 : 0 : char *p;
626 : 0 : mbedtls_mpi T;
627 : :
628 [ # # ]: 0 : if (radix < 2 || radix > 16) {
629 : : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
630 : : }
631 : :
632 : 0 : n = mbedtls_mpi_bitlen(X); /* Number of bits necessary to present `n`. */
633 [ # # ]: 0 : if (radix >= 4) {
634 : 0 : n >>= 1; /* Number of 4-adic digits necessary to present
635 : : * `n`. If radix > 4, this might be a strict
636 : : * overapproximation of the number of
637 : : * radix-adic digits needed to present `n`. */
638 : : }
639 [ # # ]: 0 : if (radix >= 16) {
640 : 0 : n >>= 1; /* Number of hexadecimal digits necessary to
641 : : * present `n`. */
642 : :
643 : : }
644 : 0 : n += 1; /* Terminating null byte */
645 : 0 : n += 1; /* Compensate for the divisions above, which round down `n`
646 : : * in case it's not even. */
647 : 0 : n += 1; /* Potential '-'-sign. */
648 : 0 : n += (n & 1); /* Make n even to have enough space for hexadecimal writing,
649 : : * which always uses an even number of hex-digits. */
650 : :
651 [ # # ]: 0 : if (buflen < n) {
652 : 0 : *olen = n;
653 : 0 : return MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL;
654 : : }
655 : :
656 : 0 : p = buf;
657 : 0 : mbedtls_mpi_init(&T);
658 : :
659 [ # # ]: 0 : if (X->s == -1) {
660 : 0 : *p++ = '-';
661 : 0 : buflen--;
662 : : }
663 : :
664 [ # # ]: 0 : if (radix == 16) {
665 : 0 : int c;
666 : 0 : size_t i, j, k;
667 : :
668 [ # # ]: 0 : for (i = X->n, k = 0; i > 0; i--) {
669 [ # # ]: 0 : for (j = ciL; j > 0; j--) {
670 : 0 : c = (X->p[i - 1] >> ((j - 1) << 3)) & 0xFF;
671 : :
672 [ # # # # ]: 0 : if (c == 0 && k == 0 && (i + j) != 2) {
673 : 0 : continue;
674 : : }
675 : :
676 : 0 : *(p++) = "0123456789ABCDEF" [c / 16];
677 : 0 : *(p++) = "0123456789ABCDEF" [c % 16];
678 : 0 : k = 1;
679 : : }
680 : : }
681 : : } else {
682 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&T, X));
683 : :
684 [ # # ]: 0 : if (T.s == -1) {
685 : 0 : T.s = 1;
686 : : }
687 : :
688 [ # # ]: 0 : MBEDTLS_MPI_CHK(mpi_write_hlp(&T, radix, &p, buflen));
689 : : }
690 : :
691 : 0 : *p++ = '\0';
692 : 0 : *olen = (size_t) (p - buf);
693 : :
694 : 0 : cleanup:
695 : :
696 : 0 : mbedtls_mpi_free(&T);
697 : :
698 : 0 : return ret;
699 : : }
700 : :
701 : : #if defined(MBEDTLS_FS_IO)
702 : : /*
703 : : * Read X from an opened file
704 : : */
705 : : int mbedtls_mpi_read_file(mbedtls_mpi *X, int radix, FILE *fin)
706 : : {
707 : : mbedtls_mpi_uint d;
708 : : size_t slen;
709 : : char *p;
710 : : /*
711 : : * Buffer should have space for (short) label and decimal formatted MPI,
712 : : * newline characters and '\0'
713 : : */
714 : : char s[MBEDTLS_MPI_RW_BUFFER_SIZE];
715 : :
716 : : if (radix < 2 || radix > 16) {
717 : : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
718 : : }
719 : :
720 : : memset(s, 0, sizeof(s));
721 : : if (fgets(s, sizeof(s) - 1, fin) == NULL) {
722 : : return MBEDTLS_ERR_MPI_FILE_IO_ERROR;
723 : : }
724 : :
725 : : slen = strlen(s);
726 : : if (slen == sizeof(s) - 2) {
727 : : return MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL;
728 : : }
729 : :
730 : : if (slen > 0 && s[slen - 1] == '\n') {
731 : : slen--; s[slen] = '\0';
732 : : }
733 : : if (slen > 0 && s[slen - 1] == '\r') {
734 : : slen--; s[slen] = '\0';
735 : : }
736 : :
737 : : p = s + slen;
738 : : while (p-- > s) {
739 : : if (mpi_get_digit(&d, radix, *p) != 0) {
740 : : break;
741 : : }
742 : : }
743 : :
744 : : return mbedtls_mpi_read_string(X, radix, p + 1);
745 : : }
746 : :
747 : : /*
748 : : * Write X into an opened file (or stdout if fout == NULL)
749 : : */
750 : : int mbedtls_mpi_write_file(const char *p, const mbedtls_mpi *X, int radix, FILE *fout)
751 : : {
752 : : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
753 : : size_t n, slen, plen;
754 : : /*
755 : : * Buffer should have space for (short) label and decimal formatted MPI,
756 : : * newline characters and '\0'
757 : : */
758 : : char s[MBEDTLS_MPI_RW_BUFFER_SIZE];
759 : :
760 : : if (radix < 2 || radix > 16) {
761 : : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
762 : : }
763 : :
764 : : memset(s, 0, sizeof(s));
765 : :
766 : : MBEDTLS_MPI_CHK(mbedtls_mpi_write_string(X, radix, s, sizeof(s) - 2, &n));
767 : :
768 : : if (p == NULL) {
769 : : p = "";
770 : : }
771 : :
772 : : plen = strlen(p);
773 : : slen = strlen(s);
774 : : s[slen++] = '\r';
775 : : s[slen++] = '\n';
776 : :
777 : : if (fout != NULL) {
778 : : if (fwrite(p, 1, plen, fout) != plen ||
779 : : fwrite(s, 1, slen, fout) != slen) {
780 : : return MBEDTLS_ERR_MPI_FILE_IO_ERROR;
781 : : }
782 : : } else {
783 : : mbedtls_printf("%s%s", p, s);
784 : : }
785 : :
786 : : cleanup:
787 : :
788 : : return ret;
789 : : }
790 : : #endif /* MBEDTLS_FS_IO */
791 : :
792 : : /*
793 : : * Import X from unsigned binary data, little endian
794 : : *
795 : : * This function is guaranteed to return an MPI with exactly the necessary
796 : : * number of limbs (in particular, it does not skip 0s in the input).
797 : : */
798 : 0 : int mbedtls_mpi_read_binary_le(mbedtls_mpi *X,
799 : : const unsigned char *buf, size_t buflen)
800 : : {
801 : 0 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
802 : 0 : const size_t limbs = CHARS_TO_LIMBS(buflen);
803 : :
804 : : /* Ensure that target MPI has exactly the necessary number of limbs */
805 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_resize_clear(X, limbs));
806 : :
807 : 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_core_read_le(X->p, X->n, buf, buflen));
808 : :
809 : 0 : cleanup:
810 : :
811 : : /*
812 : : * This function is also used to import keys. However, wiping the buffers
813 : : * upon failure is not necessary because failure only can happen before any
814 : : * input is copied.
815 : : */
816 : 0 : return ret;
817 : : }
818 : :
819 : : /*
820 : : * Import X from unsigned binary data, big endian
821 : : *
822 : : * This function is guaranteed to return an MPI with exactly the necessary
823 : : * number of limbs (in particular, it does not skip 0s in the input).
824 : : */
825 : 78 : int mbedtls_mpi_read_binary(mbedtls_mpi *X, const unsigned char *buf, size_t buflen)
826 : : {
827 : 78 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
828 : 78 : const size_t limbs = CHARS_TO_LIMBS(buflen);
829 : :
830 : : /* Ensure that target MPI has exactly the necessary number of limbs */
831 [ - + ]: 78 : MBEDTLS_MPI_CHK(mbedtls_mpi_resize_clear(X, limbs));
832 : :
833 : 78 : MBEDTLS_MPI_CHK(mbedtls_mpi_core_read_be(X->p, X->n, buf, buflen));
834 : :
835 : 78 : cleanup:
836 : :
837 : : /*
838 : : * This function is also used to import keys. However, wiping the buffers
839 : : * upon failure is not necessary because failure only can happen before any
840 : : * input is copied.
841 : : */
842 : 78 : return ret;
843 : : }
844 : :
845 : : /*
846 : : * Export X into unsigned binary data, little endian
847 : : */
848 : 0 : int mbedtls_mpi_write_binary_le(const mbedtls_mpi *X,
849 : : unsigned char *buf, size_t buflen)
850 : : {
851 : 0 : return mbedtls_mpi_core_write_le(X->p, X->n, buf, buflen);
852 : : }
853 : :
854 : : /*
855 : : * Export X into unsigned binary data, big endian
856 : : */
857 : 32 : int mbedtls_mpi_write_binary(const mbedtls_mpi *X,
858 : : unsigned char *buf, size_t buflen)
859 : : {
860 : 32 : return mbedtls_mpi_core_write_be(X->p, X->n, buf, buflen);
861 : : }
862 : :
863 : : /*
864 : : * Left-shift: X <<= count
865 : : */
866 : 441752 : int mbedtls_mpi_shift_l(mbedtls_mpi *X, size_t count)
867 : : {
868 : 441752 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
869 : 441752 : size_t i;
870 : :
871 : 441752 : i = mbedtls_mpi_bitlen(X) + count;
872 : :
873 [ + + ]: 441752 : if (X->n * biL < i) {
874 [ - + ]: 116772 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, BITS_TO_LIMBS(i)));
875 : : }
876 : :
877 : 441752 : ret = 0;
878 : :
879 : 441752 : mbedtls_mpi_core_shift_l(X->p, X->n, count);
880 : 441752 : cleanup:
881 : :
882 : 441752 : return ret;
883 : : }
884 : :
885 : : /*
886 : : * Right-shift: X >>= count
887 : : */
888 : 77848 : int mbedtls_mpi_shift_r(mbedtls_mpi *X, size_t count)
889 : : {
890 [ + - ]: 77848 : if (X->n != 0) {
891 : 77848 : mbedtls_mpi_core_shift_r(X->p, X->n, count);
892 : : }
893 : 77848 : return 0;
894 : : }
895 : :
896 : : /*
897 : : * Compare unsigned values
898 : : */
899 : 386056 : int mbedtls_mpi_cmp_abs(const mbedtls_mpi *X, const mbedtls_mpi *Y)
900 : : {
901 : 386056 : size_t i, j;
902 : :
903 [ + - ]: 1736254 : for (i = X->n; i > 0; i--) {
904 [ + + ]: 1736254 : if (X->p[i - 1] != 0) {
905 : : break;
906 : : }
907 : : }
908 : :
909 [ + - ]: 1969595 : for (j = Y->n; j > 0; j--) {
910 [ + + ]: 1969595 : if (Y->p[j - 1] != 0) {
911 : : break;
912 : : }
913 : : }
914 : :
915 : : /* If i == j == 0, i.e. abs(X) == abs(Y),
916 : : * we end up returning 0 at the end of the function. */
917 : :
918 [ + + ]: 386056 : if (i > j) {
919 : : return 1;
920 : : }
921 [ + + ]: 347069 : if (j > i) {
922 : : return -1;
923 : : }
924 : :
925 [ + - ]: 576205 : for (; i > 0; i--) {
926 [ + + ]: 576205 : if (X->p[i - 1] > Y->p[i - 1]) {
927 : : return 1;
928 : : }
929 [ + + ]: 252158 : if (X->p[i - 1] < Y->p[i - 1]) {
930 : : return -1;
931 : : }
932 : : }
933 : :
934 : : return 0;
935 : : }
936 : :
937 : : /*
938 : : * Compare signed values
939 : : */
940 : 1053403 : int mbedtls_mpi_cmp_mpi(const mbedtls_mpi *X, const mbedtls_mpi *Y)
941 : : {
942 : 1053403 : size_t i, j;
943 : :
944 [ + - ]: 10588998 : for (i = X->n; i > 0; i--) {
945 [ + + ]: 10588998 : if (X->p[i - 1] != 0) {
946 : : break;
947 : : }
948 : : }
949 : :
950 [ + + ]: 1538077 : for (j = Y->n; j > 0; j--) {
951 [ + + ]: 1053723 : if (Y->p[j - 1] != 0) {
952 : : break;
953 : : }
954 : : }
955 : :
956 [ + - ]: 1053403 : if (i == 0 && j == 0) {
957 : : return 0;
958 : : }
959 : :
960 [ + + ]: 1053403 : if (i > j) {
961 : 495881 : return X->s;
962 : : }
963 [ + + ]: 557522 : if (j > i) {
964 : 95 : return -Y->s;
965 : : }
966 : :
967 [ + - + - ]: 557427 : if (X->s > 0 && Y->s < 0) {
968 : : return 1;
969 : : }
970 [ + - + - ]: 557427 : if (Y->s > 0 && X->s < 0) {
971 : : return -1;
972 : : }
973 : :
974 [ + + ]: 899730 : for (; i > 0; i--) {
975 [ + + ]: 898388 : if (X->p[i - 1] > Y->p[i - 1]) {
976 : 146710 : return X->s;
977 : : }
978 [ + + ]: 751678 : if (X->p[i - 1] < Y->p[i - 1]) {
979 : 409375 : return -X->s;
980 : : }
981 : : }
982 : :
983 : : return 0;
984 : : }
985 : :
986 : : /*
987 : : * Compare signed values
988 : : */
989 : 485774 : int mbedtls_mpi_cmp_int(const mbedtls_mpi *X, mbedtls_mpi_sint z)
990 : : {
991 : 485774 : mbedtls_mpi Y;
992 : 485774 : mbedtls_mpi_uint p[1];
993 : :
994 : 485774 : *p = mpi_sint_abs(z);
995 : 485774 : Y.s = TO_SIGN(z);
996 : 485774 : Y.n = 1;
997 : 485774 : Y.p = p;
998 : :
999 : 485774 : return mbedtls_mpi_cmp_mpi(X, &Y);
1000 : : }
1001 : :
1002 : : /*
1003 : : * Unsigned addition: X = |A| + |B| (HAC 14.7)
1004 : : */
1005 : 3124 : int mbedtls_mpi_add_abs(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
1006 : : {
1007 : 3124 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1008 : 3124 : size_t j;
1009 : 3124 : mbedtls_mpi_uint *p;
1010 : 3124 : mbedtls_mpi_uint c;
1011 : :
1012 [ - + ]: 3124 : if (X == B) {
1013 : 0 : const mbedtls_mpi *T = A; A = X; B = T;
1014 : : }
1015 : :
1016 [ + + ]: 3124 : if (X != A) {
1017 [ - + ]: 3080 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, A));
1018 : : }
1019 : :
1020 : : /*
1021 : : * X must always be positive as a result of unsigned additions.
1022 : : */
1023 : 3124 : X->s = 1;
1024 : :
1025 [ + - ]: 27610 : for (j = B->n; j > 0; j--) {
1026 [ + + ]: 27610 : if (B->p[j - 1] != 0) {
1027 : : break;
1028 : : }
1029 : : }
1030 : :
1031 : : /* Exit early to avoid undefined behavior on NULL+0 when X->n == 0
1032 : : * and B is 0 (of any size). */
1033 [ + - ]: 3124 : if (j == 0) {
1034 : : return 0;
1035 : : }
1036 : :
1037 [ - + ]: 3124 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, j));
1038 : :
1039 : : /* j is the number of non-zero limbs of B. Add those to X. */
1040 : :
1041 : 3124 : p = X->p;
1042 : :
1043 : 3124 : c = mbedtls_mpi_core_add(p, p, B->p, j);
1044 : :
1045 : 3124 : p += j;
1046 : :
1047 : : /* Now propagate any carry */
1048 : :
1049 [ + + ]: 4665 : while (c != 0) {
1050 [ + + ]: 1541 : if (j >= X->n) {
1051 [ - + ]: 6 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, j + 1));
1052 : 6 : p = X->p + j;
1053 : : }
1054 : :
1055 : 1541 : *p += c; c = (*p < c); j++; p++;
1056 : : }
1057 : :
1058 : 3124 : cleanup:
1059 : :
1060 : : return ret;
1061 : : }
1062 : :
1063 : : /*
1064 : : * Unsigned subtraction: X = |A| - |B| (HAC 14.9, 14.10)
1065 : : */
1066 : 358273 : int mbedtls_mpi_sub_abs(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
1067 : : {
1068 : 358273 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1069 : 358273 : size_t n;
1070 : 358273 : mbedtls_mpi_uint carry;
1071 : :
1072 [ + - ]: 2025581 : for (n = B->n; n > 0; n--) {
1073 [ + + ]: 2025581 : if (B->p[n - 1] != 0) {
1074 : : break;
1075 : : }
1076 : : }
1077 [ - + ]: 358273 : if (n > A->n) {
1078 : : /* B >= (2^ciL)^n > A */
1079 : 0 : ret = MBEDTLS_ERR_MPI_NEGATIVE_VALUE;
1080 : 0 : goto cleanup;
1081 : : }
1082 : :
1083 [ - + ]: 358273 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, A->n));
1084 : :
1085 : : /* Set the high limbs of X to match A. Don't touch the lower limbs
1086 : : * because X might be aliased to B, and we must not overwrite the
1087 : : * significant digits of B. */
1088 [ + + + + ]: 358273 : if (A->n > n && A != X) {
1089 : 12551 : memcpy(X->p + n, A->p + n, (A->n - n) * ciL);
1090 : : }
1091 [ + + ]: 358273 : if (X->n > A->n) {
1092 : 12395 : memset(X->p + A->n, 0, (X->n - A->n) * ciL);
1093 : : }
1094 : :
1095 : 358273 : carry = mbedtls_mpi_core_sub(X->p, A->p, B->p, n);
1096 [ + + ]: 358273 : if (carry != 0) {
1097 : : /* Propagate the carry through the rest of X. */
1098 : 11384 : carry = mbedtls_mpi_core_sub_int(X->p + n, X->p + n, carry, X->n - n);
1099 : :
1100 : : /* If we have further carry/borrow, the result is negative. */
1101 [ - + ]: 11384 : if (carry != 0) {
1102 : 0 : ret = MBEDTLS_ERR_MPI_NEGATIVE_VALUE;
1103 : 0 : goto cleanup;
1104 : : }
1105 : : }
1106 : :
1107 : : /* X should always be positive as a result of unsigned subtractions. */
1108 : 358273 : X->s = 1;
1109 : :
1110 : 358273 : cleanup:
1111 : 358273 : return ret;
1112 : : }
1113 : :
1114 : : /* Common function for signed addition and subtraction.
1115 : : * Calculate A + B * flip_B where flip_B is 1 or -1.
1116 : : */
1117 : 350014 : static int add_sub_mpi(mbedtls_mpi *X,
1118 : : const mbedtls_mpi *A, const mbedtls_mpi *B,
1119 : : int flip_B)
1120 : : {
1121 : 350014 : int ret, s;
1122 : :
1123 : 350014 : s = A->s;
1124 [ + + ]: 350014 : if (A->s * B->s * flip_B < 0) {
1125 : 346890 : int cmp = mbedtls_mpi_cmp_abs(A, B);
1126 [ + + ]: 346890 : if (cmp >= 0) {
1127 [ - + ]: 324110 : MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(X, A, B));
1128 : : /* If |A| = |B|, the result is 0 and we must set the sign bit
1129 : : * to +1 regardless of which of A or B was negative. Otherwise,
1130 : : * since |A| > |B|, the sign is the sign of A. */
1131 [ - + ]: 324110 : X->s = cmp == 0 ? 1 : s;
1132 : : } else {
1133 [ - + ]: 22780 : MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(X, B, A));
1134 : : /* Since |A| < |B|, the sign is the opposite of A. */
1135 : 22780 : X->s = -s;
1136 : : }
1137 : : } else {
1138 [ - + ]: 3124 : MBEDTLS_MPI_CHK(mbedtls_mpi_add_abs(X, A, B));
1139 : 3124 : X->s = s;
1140 : : }
1141 : :
1142 : 350014 : cleanup:
1143 : :
1144 : 350014 : return ret;
1145 : : }
1146 : :
1147 : : /*
1148 : : * Signed addition: X = A + B
1149 : : */
1150 : 14514 : int mbedtls_mpi_add_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
1151 : : {
1152 : 14514 : return add_sub_mpi(X, A, B, 1);
1153 : : }
1154 : :
1155 : : /*
1156 : : * Signed subtraction: X = A - B
1157 : : */
1158 : 335500 : int mbedtls_mpi_sub_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
1159 : : {
1160 : 335500 : return add_sub_mpi(X, A, B, -1);
1161 : : }
1162 : :
1163 : : /*
1164 : : * Signed addition: X = A + b
1165 : : */
1166 : 0 : int mbedtls_mpi_add_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b)
1167 : : {
1168 : 0 : mbedtls_mpi B;
1169 : 0 : mbedtls_mpi_uint p[1];
1170 : :
1171 : 0 : p[0] = mpi_sint_abs(b);
1172 : 0 : B.s = TO_SIGN(b);
1173 : 0 : B.n = 1;
1174 : 0 : B.p = p;
1175 : :
1176 : 0 : return mbedtls_mpi_add_mpi(X, A, &B);
1177 : : }
1178 : :
1179 : : /*
1180 : : * Signed subtraction: X = A - b
1181 : : */
1182 : 40 : int mbedtls_mpi_sub_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b)
1183 : : {
1184 : 40 : mbedtls_mpi B;
1185 : 40 : mbedtls_mpi_uint p[1];
1186 : :
1187 : 40 : p[0] = mpi_sint_abs(b);
1188 : 40 : B.s = TO_SIGN(b);
1189 : 40 : B.n = 1;
1190 : 40 : B.p = p;
1191 : :
1192 : 40 : return mbedtls_mpi_sub_mpi(X, A, &B);
1193 : : }
1194 : :
1195 : : /*
1196 : : * Baseline multiplication: X = A * B (HAC 14.12)
1197 : : */
1198 : 39160 : int mbedtls_mpi_mul_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
1199 : : {
1200 : 39160 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1201 : 39160 : size_t i, j;
1202 : 39160 : mbedtls_mpi TA, TB;
1203 : 39160 : int result_is_zero = 0;
1204 : :
1205 : 39160 : mbedtls_mpi_init(&TA);
1206 : 39160 : mbedtls_mpi_init(&TB);
1207 : :
1208 [ + + ]: 39160 : if (X == A) {
1209 [ - + ]: 11008 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TA, A)); A = &TA;
1210 : : }
1211 [ + + ]: 39160 : if (X == B) {
1212 [ - + ]: 134 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TB, B)); B = &TB;
1213 : : }
1214 : :
1215 [ + - ]: 186779 : for (i = A->n; i > 0; i--) {
1216 [ + + ]: 186779 : if (A->p[i - 1] != 0) {
1217 : : break;
1218 : : }
1219 : : }
1220 [ - + ]: 39160 : if (i == 0) {
1221 : 0 : result_is_zero = 1;
1222 : : }
1223 : :
1224 [ + - ]: 253570 : for (j = B->n; j > 0; j--) {
1225 [ + + ]: 253570 : if (B->p[j - 1] != 0) {
1226 : : break;
1227 : : }
1228 : : }
1229 [ - + ]: 39160 : if (j == 0) {
1230 : 0 : result_is_zero = 1;
1231 : : }
1232 : :
1233 [ - + ]: 39160 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, i + j));
1234 [ - + ]: 39160 : MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 0));
1235 : :
1236 : 39160 : mbedtls_mpi_core_mul(X->p, A->p, i, B->p, j);
1237 : :
1238 : : /* If the result is 0, we don't shortcut the operation, which reduces
1239 : : * but does not eliminate side channels leaking the zero-ness. We do
1240 : : * need to take care to set the sign bit properly since the library does
1241 : : * not fully support an MPI object with a value of 0 and s == -1. */
1242 [ - + ]: 39160 : if (result_is_zero) {
1243 : 0 : X->s = 1;
1244 : : } else {
1245 : 39160 : X->s = A->s * B->s;
1246 : : }
1247 : :
1248 : 39160 : cleanup:
1249 : :
1250 : 39160 : mbedtls_mpi_free(&TB); mbedtls_mpi_free(&TA);
1251 : :
1252 : 39160 : return ret;
1253 : : }
1254 : :
1255 : : /*
1256 : : * Baseline multiplication: X = A * b
1257 : : */
1258 : 772630 : int mbedtls_mpi_mul_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b)
1259 : : {
1260 : 772630 : size_t n = A->n;
1261 [ + - + + ]: 10619902 : while (n > 0 && A->p[n - 1] == 0) {
1262 : 9847272 : --n;
1263 : : }
1264 : :
1265 : : /* The general method below doesn't work if b==0. */
1266 [ - + ]: 772630 : if (b == 0 || n == 0) {
1267 : 0 : return mbedtls_mpi_lset(X, 0);
1268 : : }
1269 : :
1270 : : /* Calculate A*b as A + A*(b-1) to take advantage of mbedtls_mpi_core_mla */
1271 : 772630 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1272 : : /* In general, A * b requires 1 limb more than b. If
1273 : : * A->p[n - 1] * b / b == A->p[n - 1], then A * b fits in the same
1274 : : * number of limbs as A and the call to grow() is not required since
1275 : : * copy() will take care of the growth if needed. However, experimentally,
1276 : : * making the call to grow() unconditional causes slightly fewer
1277 : : * calls to calloc() in ECP code, presumably because it reuses the
1278 : : * same mpi for a while and this way the mpi is more likely to directly
1279 : : * grow to its final size.
1280 : : *
1281 : : * Note that calculating A*b as 0 + A*b doesn't work as-is because
1282 : : * A,X can be the same. */
1283 [ - + ]: 772630 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, n + 1));
1284 [ - + ]: 772630 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, A));
1285 : 772630 : mbedtls_mpi_core_mla(X->p, X->n, A->p, n, b - 1);
1286 : :
1287 : : cleanup:
1288 : : return ret;
1289 : : }
1290 : :
1291 : : /*
1292 : : * Unsigned integer divide - double mbedtls_mpi_uint dividend, u1/u0, and
1293 : : * mbedtls_mpi_uint divisor, d
1294 : : */
1295 : 311424 : static mbedtls_mpi_uint mbedtls_int_div_int(mbedtls_mpi_uint u1,
1296 : : mbedtls_mpi_uint u0,
1297 : : mbedtls_mpi_uint d,
1298 : : mbedtls_mpi_uint *r)
1299 : : {
1300 : : #if defined(MBEDTLS_HAVE_UDBL)
1301 : 311424 : mbedtls_t_udbl dividend, quotient;
1302 : : #else
1303 : : const mbedtls_mpi_uint radix = (mbedtls_mpi_uint) 1 << biH;
1304 : : const mbedtls_mpi_uint uint_halfword_mask = ((mbedtls_mpi_uint) 1 << biH) - 1;
1305 : : mbedtls_mpi_uint d0, d1, q0, q1, rAX, r0, quotient;
1306 : : mbedtls_mpi_uint u0_msw, u0_lsw;
1307 : : size_t s;
1308 : : #endif
1309 : :
1310 : : /*
1311 : : * Check for overflow
1312 : : */
1313 [ - + ]: 311424 : if (0 == d || u1 >= d) {
1314 [ # # ]: 0 : if (r != NULL) {
1315 : 0 : *r = ~(mbedtls_mpi_uint) 0u;
1316 : : }
1317 : :
1318 : 0 : return ~(mbedtls_mpi_uint) 0u;
1319 : : }
1320 : :
1321 : : #if defined(MBEDTLS_HAVE_UDBL)
1322 : 311424 : dividend = (mbedtls_t_udbl) u1 << biL;
1323 : 311424 : dividend |= (mbedtls_t_udbl) u0;
1324 : 311424 : quotient = dividend / d;
1325 : 311424 : if (quotient > ((mbedtls_t_udbl) 1 << biL) - 1) {
1326 : : quotient = ((mbedtls_t_udbl) 1 << biL) - 1;
1327 : : }
1328 : :
1329 [ - + ]: 311424 : if (r != NULL) {
1330 : 0 : *r = (mbedtls_mpi_uint) (dividend - (quotient * d));
1331 : : }
1332 : :
1333 : 311424 : return (mbedtls_mpi_uint) quotient;
1334 : : #else
1335 : :
1336 : : /*
1337 : : * Algorithm D, Section 4.3.1 - The Art of Computer Programming
1338 : : * Vol. 2 - Seminumerical Algorithms, Knuth
1339 : : */
1340 : :
1341 : : /*
1342 : : * Normalize the divisor, d, and dividend, u0, u1
1343 : : */
1344 : : s = mbedtls_mpi_core_clz(d);
1345 : : d = d << s;
1346 : :
1347 : : u1 = u1 << s;
1348 : : u1 |= (u0 >> (biL - s)) & (-(mbedtls_mpi_sint) s >> (biL - 1));
1349 : : u0 = u0 << s;
1350 : :
1351 : : d1 = d >> biH;
1352 : : d0 = d & uint_halfword_mask;
1353 : :
1354 : : u0_msw = u0 >> biH;
1355 : : u0_lsw = u0 & uint_halfword_mask;
1356 : :
1357 : : /*
1358 : : * Find the first quotient and remainder
1359 : : */
1360 : : q1 = u1 / d1;
1361 : : r0 = u1 - d1 * q1;
1362 : :
1363 : : while (q1 >= radix || (q1 * d0 > radix * r0 + u0_msw)) {
1364 : : q1 -= 1;
1365 : : r0 += d1;
1366 : :
1367 : : if (r0 >= radix) {
1368 : : break;
1369 : : }
1370 : : }
1371 : :
1372 : : rAX = (u1 * radix) + (u0_msw - q1 * d);
1373 : : q0 = rAX / d1;
1374 : : r0 = rAX - q0 * d1;
1375 : :
1376 : : while (q0 >= radix || (q0 * d0 > radix * r0 + u0_lsw)) {
1377 : : q0 -= 1;
1378 : : r0 += d1;
1379 : :
1380 : : if (r0 >= radix) {
1381 : : break;
1382 : : }
1383 : : }
1384 : :
1385 : : if (r != NULL) {
1386 : : *r = (rAX * radix + u0_lsw - q0 * d) >> s;
1387 : : }
1388 : :
1389 : : quotient = q1 * radix + q0;
1390 : :
1391 : : return quotient;
1392 : : #endif
1393 : : }
1394 : :
1395 : : /*
1396 : : * Division by mbedtls_mpi: A = Q * B + R (HAC 14.20)
1397 : : */
1398 : 39166 : int mbedtls_mpi_div_mpi(mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A,
1399 : : const mbedtls_mpi *B)
1400 : : {
1401 : 39166 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1402 : 39166 : size_t i, n, t, k;
1403 : 39166 : mbedtls_mpi X, Y, Z, T1, T2;
1404 : 39166 : mbedtls_mpi_uint TP2[3];
1405 : :
1406 [ + - ]: 39166 : if (mbedtls_mpi_cmp_int(B, 0) == 0) {
1407 : : return MBEDTLS_ERR_MPI_DIVISION_BY_ZERO;
1408 : : }
1409 : :
1410 : 39166 : mbedtls_mpi_init(&X); mbedtls_mpi_init(&Y); mbedtls_mpi_init(&Z);
1411 : 39166 : mbedtls_mpi_init(&T1);
1412 : : /*
1413 : : * Avoid dynamic memory allocations for constant-size T2.
1414 : : *
1415 : : * T2 is used for comparison only and the 3 limbs are assigned explicitly,
1416 : : * so nobody increase the size of the MPI and we're safe to use an on-stack
1417 : : * buffer.
1418 : : */
1419 : 39166 : T2.s = 1;
1420 : 39166 : T2.n = sizeof(TP2) / sizeof(*TP2);
1421 : 39166 : T2.p = TP2;
1422 : :
1423 [ + + ]: 39166 : if (mbedtls_mpi_cmp_abs(A, B) < 0) {
1424 [ - + ]: 242 : if (Q != NULL) {
1425 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_lset(Q, 0));
1426 : : }
1427 [ + - ]: 242 : if (R != NULL) {
1428 [ - + ]: 242 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(R, A));
1429 : : }
1430 : 242 : return 0;
1431 : : }
1432 : :
1433 [ - + ]: 38924 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&X, A));
1434 [ - + ]: 38924 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&Y, B));
1435 : 38924 : X.s = Y.s = 1;
1436 : :
1437 [ - + ]: 38924 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&Z, A->n + 2));
1438 [ - + ]: 38924 : MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&Z, 0));
1439 [ - + ]: 38924 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&T1, A->n + 2));
1440 : :
1441 : 38924 : k = mbedtls_mpi_bitlen(&Y) % biL;
1442 [ + - ]: 38924 : if (k < biL - 1) {
1443 : 38924 : k = biL - 1 - k;
1444 [ - + ]: 38924 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&X, k));
1445 [ - + ]: 38924 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&Y, k));
1446 : : } else {
1447 : : k = 0;
1448 : : }
1449 : :
1450 : 38924 : n = X.n - 1;
1451 : 38924 : t = Y.n - 1;
1452 [ - + ]: 38924 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&Y, biL * (n - t)));
1453 : :
1454 : 38924 : while (mbedtls_mpi_cmp_mpi(&X, &Y) >= 0) {
1455 : 0 : Z.p[n - t]++;
1456 [ - - - + ]: 38924 : MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&X, &X, &Y));
1457 : : }
1458 [ - + ]: 38924 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&Y, biL * (n - t)));
1459 : :
1460 [ + + ]: 350348 : for (i = n; i > t; i--) {
1461 [ - + ]: 311424 : if (X.p[i] >= Y.p[t]) {
1462 : 0 : Z.p[i - t - 1] = ~(mbedtls_mpi_uint) 0u;
1463 : : } else {
1464 : 311424 : Z.p[i - t - 1] = mbedtls_int_div_int(X.p[i], X.p[i - 1],
1465 : : Y.p[t], NULL);
1466 : : }
1467 : :
1468 [ + - ]: 311424 : T2.p[0] = (i < 2) ? 0 : X.p[i - 2];
1469 : 311424 : T2.p[1] = (i < 1) ? 0 : X.p[i - 1];
1470 : 311424 : T2.p[2] = X.p[i];
1471 : :
1472 : 311424 : Z.p[i - t - 1]++;
1473 : 458126 : do {
1474 : 458126 : Z.p[i - t - 1]--;
1475 : :
1476 [ - + ]: 458126 : MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&T1, 0));
1477 [ + - ]: 458126 : T1.p[0] = (t < 1) ? 0 : Y.p[t - 1];
1478 : 458126 : T1.p[1] = Y.p[t];
1479 [ - + ]: 458126 : MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int(&T1, &T1, Z.p[i - t - 1]));
1480 [ + + ]: 458126 : } while (mbedtls_mpi_cmp_mpi(&T1, &T2) > 0);
1481 : :
1482 [ - + ]: 311424 : MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int(&T1, &Y, Z.p[i - t - 1]));
1483 [ - + ]: 311424 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&T1, biL * (i - t - 1)));
1484 [ - + ]: 311424 : MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&X, &X, &T1));
1485 : :
1486 [ - + ]: 311424 : if (mbedtls_mpi_cmp_int(&X, 0) < 0) {
1487 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&T1, &Y));
1488 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&T1, biL * (i - t - 1)));
1489 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&X, &X, &T1));
1490 : 0 : Z.p[i - t - 1]--;
1491 : : }
1492 : : }
1493 : :
1494 [ - + ]: 38924 : if (Q != NULL) {
1495 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(Q, &Z));
1496 : 0 : Q->s = A->s * B->s;
1497 : : }
1498 : :
1499 [ - + ]: 38924 : if (R != NULL) {
1500 [ - + ]: 38924 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&X, k));
1501 : 38924 : X.s = A->s;
1502 [ - + ]: 38924 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(R, &X));
1503 : :
1504 [ + - ]: 38924 : if (mbedtls_mpi_cmp_int(R, 0) == 0) {
1505 : 0 : R->s = 1;
1506 : : }
1507 : : }
1508 : :
1509 : 38924 : cleanup:
1510 : :
1511 : 38924 : mbedtls_mpi_free(&X); mbedtls_mpi_free(&Y); mbedtls_mpi_free(&Z);
1512 : 38924 : mbedtls_mpi_free(&T1);
1513 : 38924 : mbedtls_platform_zeroize(TP2, sizeof(TP2));
1514 : :
1515 : 38924 : return ret;
1516 : : }
1517 : :
1518 : : /*
1519 : : * Division by int: A = Q * b + R
1520 : : */
1521 : 0 : int mbedtls_mpi_div_int(mbedtls_mpi *Q, mbedtls_mpi *R,
1522 : : const mbedtls_mpi *A,
1523 : : mbedtls_mpi_sint b)
1524 : : {
1525 : 0 : mbedtls_mpi B;
1526 : 0 : mbedtls_mpi_uint p[1];
1527 : :
1528 : 0 : p[0] = mpi_sint_abs(b);
1529 : 0 : B.s = TO_SIGN(b);
1530 : 0 : B.n = 1;
1531 : 0 : B.p = p;
1532 : :
1533 : 0 : return mbedtls_mpi_div_mpi(Q, R, A, &B);
1534 : : }
1535 : :
1536 : : /*
1537 : : * Modulo: R = A mod B
1538 : : */
1539 : 39166 : int mbedtls_mpi_mod_mpi(mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B)
1540 : : {
1541 : 39166 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1542 : :
1543 [ + - ]: 39166 : if (mbedtls_mpi_cmp_int(B, 0) < 0) {
1544 : : return MBEDTLS_ERR_MPI_NEGATIVE_VALUE;
1545 : : }
1546 : :
1547 [ - + ]: 39166 : MBEDTLS_MPI_CHK(mbedtls_mpi_div_mpi(NULL, R, A, B));
1548 : :
1549 : 39166 : while (mbedtls_mpi_cmp_int(R, 0) < 0) {
1550 [ - - - + ]: 39166 : MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(R, R, B));
1551 : : }
1552 : :
1553 : 39166 : while (mbedtls_mpi_cmp_mpi(R, B) >= 0) {
1554 [ - - - + ]: 39166 : MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(R, R, B));
1555 : : }
1556 : :
1557 : 39166 : cleanup:
1558 : :
1559 : : return ret;
1560 : : }
1561 : :
1562 : : /*
1563 : : * Modulo: r = A mod b
1564 : : */
1565 : 0 : int mbedtls_mpi_mod_int(mbedtls_mpi_uint *r, const mbedtls_mpi *A, mbedtls_mpi_sint b)
1566 : : {
1567 : 0 : size_t i;
1568 : 0 : mbedtls_mpi_uint x, y, z;
1569 : :
1570 [ # # ]: 0 : if (b == 0) {
1571 : : return MBEDTLS_ERR_MPI_DIVISION_BY_ZERO;
1572 : : }
1573 : :
1574 [ # # ]: 0 : if (b < 0) {
1575 : : return MBEDTLS_ERR_MPI_NEGATIVE_VALUE;
1576 : : }
1577 : :
1578 : : /*
1579 : : * handle trivial cases
1580 : : */
1581 [ # # # # ]: 0 : if (b == 1 || A->n == 0) {
1582 : 0 : *r = 0;
1583 : 0 : return 0;
1584 : : }
1585 : :
1586 [ # # ]: 0 : if (b == 2) {
1587 : 0 : *r = A->p[0] & 1;
1588 : 0 : return 0;
1589 : : }
1590 : :
1591 : : /*
1592 : : * general case
1593 : : */
1594 [ # # ]: 0 : for (i = A->n, y = 0; i > 0; i--) {
1595 : 0 : x = A->p[i - 1];
1596 : 0 : y = (y << biH) | (x >> biH);
1597 : 0 : z = y / b;
1598 : 0 : y -= z * b;
1599 : :
1600 : 0 : x <<= biH;
1601 : 0 : y = (y << biH) | (x >> biH);
1602 : 0 : z = y / b;
1603 : 0 : y -= z * b;
1604 : : }
1605 : :
1606 : : /*
1607 : : * If A is negative, then the current y represents a negative value.
1608 : : * Flipping it to the positive side.
1609 : : */
1610 [ # # # # ]: 0 : if (A->s < 0 && y != 0) {
1611 : 0 : y = b - y;
1612 : : }
1613 : :
1614 : 0 : *r = y;
1615 : :
1616 : 0 : return 0;
1617 : : }
1618 : :
1619 : : /*
1620 : : * Warning! If the parameter E_public has MBEDTLS_MPI_IS_PUBLIC as its value,
1621 : : * this function is not constant time with respect to the exponent (parameter E).
1622 : : */
1623 : 0 : static int mbedtls_mpi_exp_mod_optionally_safe(mbedtls_mpi *X, const mbedtls_mpi *A,
1624 : : const mbedtls_mpi *E, int E_public,
1625 : : const mbedtls_mpi *N, mbedtls_mpi *prec_RR)
1626 : : {
1627 : 0 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1628 : :
1629 [ # # # # ]: 0 : if (mbedtls_mpi_cmp_int(N, 0) <= 0 || (N->p[0] & 1) == 0) {
1630 : : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
1631 : : }
1632 : :
1633 [ # # ]: 0 : if (mbedtls_mpi_cmp_int(E, 0) < 0) {
1634 : : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
1635 : : }
1636 : :
1637 [ # # # # ]: 0 : if (mbedtls_mpi_bitlen(E) > MBEDTLS_MPI_MAX_BITS ||
1638 : 0 : mbedtls_mpi_bitlen(N) > MBEDTLS_MPI_MAX_BITS) {
1639 : 0 : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
1640 : : }
1641 : :
1642 : : /*
1643 : : * Ensure that the exponent that we are passing to the core is not NULL.
1644 : : */
1645 [ # # ]: 0 : if (E->n == 0) {
1646 : 0 : ret = mbedtls_mpi_lset(X, 1);
1647 : 0 : return ret;
1648 : : }
1649 : :
1650 : : /*
1651 : : * Allocate working memory for mbedtls_mpi_core_exp_mod()
1652 : : */
1653 : 0 : size_t T_limbs = mbedtls_mpi_core_exp_mod_working_limbs(N->n, E->n);
1654 : 0 : mbedtls_mpi_uint *T = (mbedtls_mpi_uint *) mbedtls_calloc(T_limbs, sizeof(mbedtls_mpi_uint));
1655 [ # # ]: 0 : if (T == NULL) {
1656 : : return MBEDTLS_ERR_MPI_ALLOC_FAILED;
1657 : : }
1658 : :
1659 : 0 : mbedtls_mpi RR;
1660 : 0 : mbedtls_mpi_init(&RR);
1661 : :
1662 : : /*
1663 : : * If 1st call, pre-compute R^2 mod N
1664 : : */
1665 [ # # # # ]: 0 : if (prec_RR == NULL || prec_RR->p == NULL) {
1666 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_core_get_mont_r2_unsafe(&RR, N));
1667 : :
1668 [ # # ]: 0 : if (prec_RR != NULL) {
1669 : 0 : *prec_RR = RR;
1670 : : }
1671 : : } else {
1672 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(prec_RR, N->n));
1673 : 0 : RR = *prec_RR;
1674 : : }
1675 : :
1676 : : /*
1677 : : * To preserve constness we need to make a copy of A. Using X for this to
1678 : : * save memory.
1679 : : */
1680 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, A));
1681 : :
1682 : : /*
1683 : : * Compensate for negative A (and correct at the end).
1684 : : */
1685 : 0 : X->s = 1;
1686 : :
1687 : : /*
1688 : : * Make sure that X is in a form that is safe for consumption by
1689 : : * the core functions.
1690 : : *
1691 : : * - The core functions will not touch the limbs of X above N->n. The
1692 : : * result will be correct if those limbs are 0, which the mod call
1693 : : * ensures.
1694 : : * - Also, X must have at least as many limbs as N for the calls to the
1695 : : * core functions.
1696 : : */
1697 [ # # ]: 0 : if (mbedtls_mpi_cmp_mpi(X, N) >= 0) {
1698 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(X, X, N));
1699 : : }
1700 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, N->n));
1701 : :
1702 : : /*
1703 : : * Convert to and from Montgomery around mbedtls_mpi_core_exp_mod().
1704 : : */
1705 : : {
1706 : 0 : mbedtls_mpi_uint mm = mbedtls_mpi_core_montmul_init(N->p);
1707 : 0 : mbedtls_mpi_core_to_mont_rep(X->p, X->p, N->p, N->n, mm, RR.p, T);
1708 [ # # ]: 0 : if (E_public == MBEDTLS_MPI_IS_PUBLIC) {
1709 : 0 : mbedtls_mpi_core_exp_mod_unsafe(X->p, X->p, N->p, N->n, E->p, E->n, RR.p, T);
1710 : : } else {
1711 : 0 : mbedtls_mpi_core_exp_mod(X->p, X->p, N->p, N->n, E->p, E->n, RR.p, T);
1712 : : }
1713 : 0 : mbedtls_mpi_core_from_mont_rep(X->p, X->p, N->p, N->n, mm, T);
1714 : : }
1715 : :
1716 : : /*
1717 : : * Correct for negative A.
1718 : : */
1719 [ # # # # ]: 0 : if (A->s == -1 && (E->p[0] & 1) != 0) {
1720 : 0 : mbedtls_ct_condition_t is_x_non_zero = mbedtls_mpi_core_check_zero_ct(X->p, X->n);
1721 : 0 : X->s = mbedtls_ct_mpi_sign_if(is_x_non_zero, -1, 1);
1722 : :
1723 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(X, N, X));
1724 : : }
1725 : :
1726 : 0 : cleanup:
1727 : :
1728 : 0 : mbedtls_mpi_zeroize_and_free(T, T_limbs);
1729 : :
1730 [ # # # # ]: 0 : if (prec_RR == NULL || prec_RR->p == NULL) {
1731 : 0 : mbedtls_mpi_free(&RR);
1732 : : }
1733 : :
1734 : : return ret;
1735 : : }
1736 : :
1737 : 0 : int mbedtls_mpi_exp_mod(mbedtls_mpi *X, const mbedtls_mpi *A,
1738 : : const mbedtls_mpi *E, const mbedtls_mpi *N,
1739 : : mbedtls_mpi *prec_RR)
1740 : : {
1741 : 0 : return mbedtls_mpi_exp_mod_optionally_safe(X, A, E, MBEDTLS_MPI_IS_SECRET, N, prec_RR);
1742 : : }
1743 : :
1744 : 0 : int mbedtls_mpi_exp_mod_unsafe(mbedtls_mpi *X, const mbedtls_mpi *A,
1745 : : const mbedtls_mpi *E, const mbedtls_mpi *N,
1746 : : mbedtls_mpi *prec_RR)
1747 : : {
1748 : 0 : return mbedtls_mpi_exp_mod_optionally_safe(X, A, E, MBEDTLS_MPI_IS_PUBLIC, N, prec_RR);
1749 : : }
1750 : :
1751 : : /* Constant-time GCD and/or modinv with odd modulus and A <= N */
1752 : 56 : int mbedtls_mpi_gcd_modinv_odd(mbedtls_mpi *G,
1753 : : mbedtls_mpi *I,
1754 : : const mbedtls_mpi *A,
1755 : : const mbedtls_mpi *N)
1756 : : {
1757 : 56 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1758 : 56 : mbedtls_mpi local_g;
1759 : 56 : mbedtls_mpi_uint *T = NULL;
1760 [ - + ]: 56 : const size_t T_factor = I != NULL ? 5 : 4;
1761 : 56 : const mbedtls_mpi_uint zero = 0;
1762 : :
1763 : : /* Check requirements on A and N */
1764 [ + - ]: 56 : if (mbedtls_mpi_cmp_int(A, 0) < 0 ||
1765 [ + - ]: 56 : mbedtls_mpi_cmp_mpi(A, N) > 0 ||
1766 [ + - + - ]: 56 : mbedtls_mpi_get_bit(N, 0) != 1 ||
1767 [ + - ]: 56 : (I != NULL && mbedtls_mpi_cmp_int(N, 1) == 0)) {
1768 : : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
1769 : : }
1770 : :
1771 : : /* Check aliasing requirements */
1772 [ + - + - : 56 : if (A == N || (I != NULL && (I == N || G == N))) {
+ - ]
1773 : : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
1774 : : }
1775 : :
1776 : 56 : mbedtls_mpi_init(&local_g);
1777 : :
1778 [ + - ]: 56 : if (G == NULL) {
1779 : 56 : G = &local_g;
1780 : : }
1781 : :
1782 : : /* We can't modify the values of G or I before use in the main function,
1783 : : * as they could be aliased to A or N. */
1784 [ - + ]: 56 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(G, N->n));
1785 [ + - ]: 56 : if (I != NULL) {
1786 [ - + ]: 56 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(I, N->n));
1787 : : }
1788 : :
1789 : 56 : T = mbedtls_calloc(sizeof(mbedtls_mpi_uint) * N->n, T_factor);
1790 [ - + ]: 56 : if (T == NULL) {
1791 : 0 : ret = MBEDTLS_ERR_MPI_ALLOC_FAILED;
1792 : 0 : goto cleanup;
1793 : : }
1794 : :
1795 [ + - ]: 56 : mbedtls_mpi_uint *Ip = I != NULL ? I->p : NULL;
1796 : : /* If A is 0 (null), then A->p would be null, and A->n would be 0,
1797 : : * which would be an issue if A->p and A->n were passed to
1798 : : * mbedtls_mpi_core_gcd_modinv_odd below. */
1799 [ + - ]: 56 : const mbedtls_mpi_uint *Ap = A->p != NULL ? A->p : &zero;
1800 [ - + - - ]: 56 : size_t An = A->n >= N->n ? N->n : A->p != NULL ? A->n : 1;
1801 : 56 : mbedtls_mpi_core_gcd_modinv_odd(G->p, Ip, Ap, An, N->p, N->n, T);
1802 : :
1803 : 56 : G->s = 1;
1804 [ + - ]: 56 : if (I != NULL) {
1805 : 56 : I->s = 1;
1806 : : }
1807 : :
1808 [ - + ]: 56 : if (G->n > N->n) {
1809 : 0 : memset(G->p + N->n, 0, ciL * (G->n - N->n));
1810 : : }
1811 [ - + + + ]: 56 : if (I != NULL && I->n > N->n) {
1812 : 24 : memset(I->p + N->n, 0, ciL * (I->n - N->n));
1813 : : }
1814 : :
1815 : 32 : cleanup:
1816 : 56 : mbedtls_mpi_free(&local_g);
1817 : 56 : mbedtls_free(T);
1818 : 56 : return ret;
1819 : : }
1820 : :
1821 : : /*
1822 : : * Greatest common divisor: G = gcd(A, B)
1823 : : * Wrapper around mbedtls_mpi_gcd_modinv() that removes its restrictions.
1824 : : */
1825 : 0 : int mbedtls_mpi_gcd(mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B)
1826 : : {
1827 : 0 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1828 : 0 : mbedtls_mpi TA, TB;
1829 : :
1830 : 0 : mbedtls_mpi_init(&TA); mbedtls_mpi_init(&TB);
1831 : :
1832 : : /* Make copies and take absolute values */
1833 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TA, A));
1834 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TB, B));
1835 : 0 : TA.s = TB.s = 1;
1836 : :
1837 : : /* Make the two values the same (non-zero) number of limbs.
1838 : : * This is needed to use mbedtls_mpi_core functions below. */
1839 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&TA, TB.n != 0 ? TB.n : 1));
1840 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&TB, TA.n)); // non-zero from above
1841 : :
1842 : : /* Handle special cases (that don't happen in crypto usage) */
1843 [ # # ]: 0 : if (mbedtls_mpi_core_check_zero_ct(TA.p, TA.n) == MBEDTLS_CT_FALSE) {
1844 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(G, &TB)); // GCD(0, B) = abs(B)
1845 : 0 : goto cleanup;
1846 : : }
1847 [ # # ]: 0 : if (mbedtls_mpi_core_check_zero_ct(TB.p, TB.n) == MBEDTLS_CT_FALSE) {
1848 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(G, &TA)); // GCD(A, 0) = abs(A)
1849 : 0 : goto cleanup;
1850 : : }
1851 : :
1852 : : /* Make boths inputs odd by putting powers of 2 on the side */
1853 : 0 : const size_t za = mbedtls_mpi_lsb(&TA);
1854 : 0 : const size_t zb = mbedtls_mpi_lsb(&TB);
1855 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TA, za));
1856 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TB, zb));
1857 : :
1858 : : /* Ensure A <= B: if B < A, swap them */
1859 : 0 : mbedtls_ct_condition_t swap = mbedtls_mpi_core_lt_ct(TB.p, TA.p, TA.n);
1860 : 0 : mbedtls_mpi_core_cond_swap(TA.p, TB.p, TA.n, swap);
1861 : :
1862 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_gcd_modinv_odd(G, NULL, &TA, &TB));
1863 : :
1864 : : /* Re-inject the power of 2 we had previously put aside */
1865 : 0 : size_t zg = za > zb ? zb : za; // zg = min(za, zb)
1866 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(G, zg));
1867 : :
1868 : 0 : cleanup:
1869 : :
1870 : 0 : mbedtls_mpi_free(&TA); mbedtls_mpi_free(&TB);
1871 : :
1872 : 0 : return ret;
1873 : : }
1874 : :
1875 : : /*
1876 : : * Fill X with size bytes of random.
1877 : : * The bytes returned from the RNG are used in a specific order which
1878 : : * is suitable for deterministic ECDSA (see the specification of
1879 : : * mbedtls_mpi_random() and the implementation in mbedtls_mpi_fill_random()).
1880 : : */
1881 : 0 : int mbedtls_mpi_fill_random(mbedtls_mpi *X, size_t size,
1882 : : int (*f_rng)(void *, unsigned char *, size_t),
1883 : : void *p_rng)
1884 : : {
1885 : 0 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1886 : 0 : const size_t limbs = CHARS_TO_LIMBS(size);
1887 : :
1888 : : /* Ensure that target MPI has exactly the necessary number of limbs */
1889 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_resize_clear(X, limbs));
1890 [ # # ]: 0 : if (size == 0) {
1891 : : return 0;
1892 : : }
1893 : :
1894 : 0 : ret = mbedtls_mpi_core_fill_random(X->p, X->n, size, f_rng, p_rng);
1895 : :
1896 : : cleanup:
1897 : : return ret;
1898 : : }
1899 : :
1900 : 12 : int mbedtls_mpi_random(mbedtls_mpi *X,
1901 : : mbedtls_mpi_sint min,
1902 : : const mbedtls_mpi *N,
1903 : : int (*f_rng)(void *, unsigned char *, size_t),
1904 : : void *p_rng)
1905 : : {
1906 [ + - ]: 12 : if (min < 0) {
1907 : : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
1908 : : }
1909 [ + - ]: 12 : if (mbedtls_mpi_cmp_int(N, min) <= 0) {
1910 : : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
1911 : : }
1912 : :
1913 : : /* Ensure that target MPI has exactly the same number of limbs
1914 : : * as the upper bound, even if the upper bound has leading zeros.
1915 : : * This is necessary for mbedtls_mpi_core_random. */
1916 : 12 : int ret = mbedtls_mpi_resize_clear(X, N->n);
1917 [ + - ]: 12 : if (ret != 0) {
1918 : : return ret;
1919 : : }
1920 : :
1921 : 12 : return mbedtls_mpi_core_random(X->p, min, N->p, X->n, f_rng, p_rng);
1922 : : }
1923 : :
1924 : : /*
1925 : : * Modular inverse: X = A^-1 mod N with N odd (and A any range)
1926 : : */
1927 : 0 : int mbedtls_mpi_inv_mod_odd(mbedtls_mpi *X,
1928 : : const mbedtls_mpi *A,
1929 : : const mbedtls_mpi *N)
1930 : : {
1931 : 0 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1932 : 0 : mbedtls_mpi T, G;
1933 : :
1934 : 0 : mbedtls_mpi_init(&T);
1935 : 0 : mbedtls_mpi_init(&G);
1936 : :
1937 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(&T, A, N));
1938 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_gcd_modinv_odd(&G, &T, &T, N));
1939 [ # # ]: 0 : if (mbedtls_mpi_cmp_int(&G, 1) != 0) {
1940 : 0 : ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
1941 : 0 : goto cleanup;
1942 : : }
1943 : :
1944 : 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, &T));
1945 : :
1946 : 0 : cleanup:
1947 : 0 : mbedtls_mpi_free(&T);
1948 : 0 : mbedtls_mpi_free(&G);
1949 : :
1950 : 0 : return ret;
1951 : : }
1952 : :
1953 : : /*
1954 : : * Compute X = A^-1 mod N with N even, A odd and 1 < A < N.
1955 : : *
1956 : : * This is not obvious because our constant-time modinv function only works with
1957 : : * an odd modulus, and here the modulus is even. The idea is that computing a
1958 : : * a^-1 mod b is really just computing the u coefficient in the Bézout relation
1959 : : * a*u + b*v = 1 (assuming gcd(a,b) = 1, i.e. the inverse exists). But if we know
1960 : : * one of u, v in this relation then the other is easy to find. So we can
1961 : : * actually start by computing N^-1 mod A with gives us "the wrong half" of the
1962 : : * Bézout relation, from which we'll deduce the interesting half A^-1 mod N.
1963 : : *
1964 : : * Return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE if the inverse doesn't exist.
1965 : : */
1966 : 0 : int mbedtls_mpi_inv_mod_even_in_range(mbedtls_mpi *X,
1967 : : mbedtls_mpi const *A,
1968 : : mbedtls_mpi const *N)
1969 : : {
1970 : 0 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1971 : 0 : mbedtls_mpi I, G;
1972 : :
1973 : 0 : mbedtls_mpi_init(&I);
1974 : 0 : mbedtls_mpi_init(&G);
1975 : :
1976 : : /* Set I = N^-1 mod A */
1977 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(&I, N, A));
1978 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_gcd_modinv_odd(&G, &I, &I, A));
1979 [ # # ]: 0 : if (mbedtls_mpi_cmp_int(&G, 1) != 0) {
1980 : 0 : ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
1981 : 0 : goto cleanup;
1982 : : }
1983 : :
1984 : : /* We know N * I = 1 + k * A for some k, which we can easily compute
1985 : : * as k = (N*I - 1) / A (we know there will be no remainder). */
1986 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(&I, &I, N));
1987 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_sub_int(&I, &I, 1));
1988 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_div_mpi(&G, NULL, &I, A));
1989 : :
1990 : : /* Now we have a Bézout relation N * (previous value of I) - G * A = 1,
1991 : : * so A^-1 mod N is -G mod N, which is N - G.
1992 : : * Note that 0 < k < N since 0 < I < A, so G (k) is already in range. */
1993 : 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(X, N, &G));
1994 : :
1995 : 0 : cleanup:
1996 : 0 : mbedtls_mpi_free(&I);
1997 : 0 : mbedtls_mpi_free(&G);
1998 : 0 : return ret;
1999 : : }
2000 : :
2001 : : /*
2002 : : * Compute X = A^-1 mod N with N even and A odd (but in any range).
2003 : : *
2004 : : * Return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE if the inverse doesn't exist.
2005 : : */
2006 : 0 : static int mbedtls_mpi_inv_mod_even(mbedtls_mpi *X,
2007 : : mbedtls_mpi const *A,
2008 : : mbedtls_mpi const *N)
2009 : : {
2010 : 0 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2011 : 0 : mbedtls_mpi AA;
2012 : :
2013 : 0 : mbedtls_mpi_init(&AA);
2014 : :
2015 : : /* Bring A in the range [0, N). */
2016 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(&AA, A, N));
2017 : :
2018 : : /* We know A >= 0 but the next function wants A > 1 */
2019 : 0 : int cmp = mbedtls_mpi_cmp_int(&AA, 1);
2020 [ # # ]: 0 : if (cmp < 0) { // AA == 0
2021 : 0 : ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2022 : 0 : goto cleanup;
2023 : : }
2024 [ # # ]: 0 : if (cmp == 0) { // AA = 1
2025 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 1));
2026 : 0 : goto cleanup;
2027 : : }
2028 : :
2029 : : /* Now we know 1 < A < N, N is even and AA is still odd */
2030 [ # # ]: 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_inv_mod_even_in_range(X, &AA, N));
2031 : :
2032 : 0 : cleanup:
2033 : 0 : mbedtls_mpi_free(&AA);
2034 : 0 : return ret;
2035 : : }
2036 : :
2037 : : /*
2038 : : * Modular inverse: X = A^-1 mod N
2039 : : *
2040 : : * Wrapper around mbedtls_mpi_gcd_modinv_odd() that lifts its limitations.
2041 : : */
2042 : 0 : int mbedtls_mpi_inv_mod(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N)
2043 : : {
2044 [ # # ]: 0 : if (mbedtls_mpi_cmp_int(N, 1) <= 0) {
2045 : : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
2046 : : }
2047 : :
2048 [ # # ]: 0 : if (mbedtls_mpi_get_bit(N, 0) == 1) {
2049 : 0 : return mbedtls_mpi_inv_mod_odd(X, A, N);
2050 : : }
2051 : :
2052 [ # # ]: 0 : if (mbedtls_mpi_get_bit(A, 0) == 1) {
2053 : 0 : return mbedtls_mpi_inv_mod_even(X, A, N);
2054 : : }
2055 : :
2056 : : /* If A and N are both even, 2 divides their GCD, so no inverse. */
2057 : : return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2058 : : }
2059 : :
2060 : : #if defined(MBEDTLS_GENPRIME)
2061 : :
2062 : : /* Gaps between primes, starting at 3. https://oeis.org/A001223 */
2063 : : static const unsigned char small_prime_gaps[] = {
2064 : : 2, 2, 4, 2, 4, 2, 4, 6,
2065 : : 2, 6, 4, 2, 4, 6, 6, 2,
2066 : : 6, 4, 2, 6, 4, 6, 8, 4,
2067 : : 2, 4, 2, 4, 14, 4, 6, 2,
2068 : : 10, 2, 6, 6, 4, 6, 6, 2,
2069 : : 10, 2, 4, 2, 12, 12, 4, 2,
2070 : : 4, 6, 2, 10, 6, 6, 6, 2,
2071 : : 6, 4, 2, 10, 14, 4, 2, 4,
2072 : : 14, 6, 10, 2, 4, 6, 8, 6,
2073 : : 6, 4, 6, 8, 4, 8, 10, 2,
2074 : : 10, 2, 6, 4, 6, 8, 4, 2,
2075 : : 4, 12, 8, 4, 8, 4, 6, 12,
2076 : : 2, 18, 6, 10, 6, 6, 2, 6,
2077 : : 10, 6, 6, 2, 6, 6, 4, 2,
2078 : : 12, 10, 2, 4, 6, 6, 2, 12,
2079 : : 4, 6, 8, 10, 8, 10, 8, 6,
2080 : : 6, 4, 8, 6, 4, 8, 4, 14,
2081 : : 10, 12, 2, 10, 2, 4, 2, 10,
2082 : : 14, 4, 2, 4, 14, 4, 2, 4,
2083 : : 20, 4, 8, 10, 8, 4, 6, 6,
2084 : : 14, 4, 6, 6, 8, 6, /*reaches 997*/
2085 : : 0 /* the last entry is effectively unused */
2086 : : };
2087 : :
2088 : : /*
2089 : : * Small divisors test (X must be positive)
2090 : : *
2091 : : * Return values:
2092 : : * 0: no small factor (possible prime, more tests needed)
2093 : : * 1: certain prime
2094 : : * MBEDTLS_ERR_MPI_NOT_ACCEPTABLE: certain non-prime
2095 : : * other negative: error
2096 : : */
2097 : : static int mpi_check_small_factors(const mbedtls_mpi *X)
2098 : : {
2099 : : int ret = 0;
2100 : : size_t i;
2101 : : mbedtls_mpi_uint r;
2102 : : unsigned p = 3; /* The first odd prime */
2103 : :
2104 : : if ((X->p[0] & 1) == 0) {
2105 : : return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2106 : : }
2107 : :
2108 : : for (i = 0; i < sizeof(small_prime_gaps); p += small_prime_gaps[i], i++) {
2109 : : MBEDTLS_MPI_CHK(mbedtls_mpi_mod_int(&r, X, p));
2110 : : if (r == 0) {
2111 : : if (mbedtls_mpi_cmp_int(X, p) == 0) {
2112 : : return 1;
2113 : : } else {
2114 : : return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2115 : : }
2116 : : }
2117 : : }
2118 : :
2119 : : cleanup:
2120 : : return ret;
2121 : : }
2122 : :
2123 : : /*
2124 : : * Miller-Rabin pseudo-primality test (HAC 4.24)
2125 : : */
2126 : : static int mpi_miller_rabin(const mbedtls_mpi *X, size_t rounds,
2127 : : int (*f_rng)(void *, unsigned char *, size_t),
2128 : : void *p_rng)
2129 : : {
2130 : : int ret, count;
2131 : : size_t i, j, k, s;
2132 : : mbedtls_mpi W, R, T, A, RR;
2133 : :
2134 : : mbedtls_mpi_init(&W); mbedtls_mpi_init(&R);
2135 : : mbedtls_mpi_init(&T); mbedtls_mpi_init(&A);
2136 : : mbedtls_mpi_init(&RR);
2137 : :
2138 : : /*
2139 : : * W = |X| - 1
2140 : : * R = W >> lsb( W )
2141 : : */
2142 : : MBEDTLS_MPI_CHK(mbedtls_mpi_sub_int(&W, X, 1));
2143 : : s = mbedtls_mpi_lsb(&W);
2144 : : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&R, &W));
2145 : : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&R, s));
2146 : :
2147 : : for (i = 0; i < rounds; i++) {
2148 : : /*
2149 : : * pick a random A, 1 < A < |X| - 1
2150 : : */
2151 : : count = 0;
2152 : : do {
2153 : : MBEDTLS_MPI_CHK(mbedtls_mpi_fill_random(&A, X->n * ciL, f_rng, p_rng));
2154 : :
2155 : : j = mbedtls_mpi_bitlen(&A);
2156 : : k = mbedtls_mpi_bitlen(&W);
2157 : : if (j > k) {
2158 : : A.p[A.n - 1] &= ((mbedtls_mpi_uint) 1 << (k - (A.n - 1) * biL - 1)) - 1;
2159 : : }
2160 : :
2161 : : if (count++ > 30) {
2162 : : ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2163 : : goto cleanup;
2164 : : }
2165 : :
2166 : : } while (mbedtls_mpi_cmp_mpi(&A, &W) >= 0 ||
2167 : : mbedtls_mpi_cmp_int(&A, 1) <= 0);
2168 : :
2169 : : /*
2170 : : * A = A^R mod |X|
2171 : : */
2172 : : MBEDTLS_MPI_CHK(mbedtls_mpi_exp_mod(&A, &A, &R, X, &RR));
2173 : :
2174 : : if (mbedtls_mpi_cmp_mpi(&A, &W) == 0 ||
2175 : : mbedtls_mpi_cmp_int(&A, 1) == 0) {
2176 : : continue;
2177 : : }
2178 : :
2179 : : j = 1;
2180 : : while (j < s && mbedtls_mpi_cmp_mpi(&A, &W) != 0) {
2181 : : /*
2182 : : * A = A * A mod |X|
2183 : : */
2184 : : MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(&T, &A, &A));
2185 : : MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(&A, &T, X));
2186 : :
2187 : : if (mbedtls_mpi_cmp_int(&A, 1) == 0) {
2188 : : break;
2189 : : }
2190 : :
2191 : : j++;
2192 : : }
2193 : :
2194 : : /*
2195 : : * not prime if A != |X| - 1 or A == 1
2196 : : */
2197 : : if (mbedtls_mpi_cmp_mpi(&A, &W) != 0 ||
2198 : : mbedtls_mpi_cmp_int(&A, 1) == 0) {
2199 : : ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2200 : : break;
2201 : : }
2202 : : }
2203 : :
2204 : : cleanup:
2205 : : mbedtls_mpi_free(&W); mbedtls_mpi_free(&R);
2206 : : mbedtls_mpi_free(&T); mbedtls_mpi_free(&A);
2207 : : mbedtls_mpi_free(&RR);
2208 : :
2209 : : return ret;
2210 : : }
2211 : :
2212 : : /*
2213 : : * Pseudo-primality test: small factors, then Miller-Rabin
2214 : : */
2215 : : int mbedtls_mpi_is_prime_ext(const mbedtls_mpi *X, int rounds,
2216 : : int (*f_rng)(void *, unsigned char *, size_t),
2217 : : void *p_rng)
2218 : : {
2219 : : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2220 : : mbedtls_mpi XX;
2221 : :
2222 : : XX.s = 1;
2223 : : XX.n = X->n;
2224 : : XX.p = X->p;
2225 : :
2226 : : if (mbedtls_mpi_cmp_int(&XX, 0) == 0 ||
2227 : : mbedtls_mpi_cmp_int(&XX, 1) == 0) {
2228 : : return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2229 : : }
2230 : :
2231 : : if (mbedtls_mpi_cmp_int(&XX, 2) == 0) {
2232 : : return 0;
2233 : : }
2234 : :
2235 : : if ((ret = mpi_check_small_factors(&XX)) != 0) {
2236 : : if (ret == 1) {
2237 : : return 0;
2238 : : }
2239 : :
2240 : : return ret;
2241 : : }
2242 : :
2243 : : return mpi_miller_rabin(&XX, rounds, f_rng, p_rng);
2244 : : }
2245 : :
2246 : : /*
2247 : : * Prime number generation
2248 : : *
2249 : : * To generate an RSA key in a way recommended by FIPS 186-4, both primes must
2250 : : * be either 1024 bits or 1536 bits long, and flags must contain
2251 : : * MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR.
2252 : : */
2253 : : int mbedtls_mpi_gen_prime(mbedtls_mpi *X, size_t nbits, int flags,
2254 : : int (*f_rng)(void *, unsigned char *, size_t),
2255 : : void *p_rng)
2256 : : {
2257 : : #ifdef MBEDTLS_HAVE_INT64
2258 : : // ceil(2^63.5)
2259 : : #define CEIL_MAXUINT_DIV_SQRT2 0xb504f333f9de6485ULL
2260 : : #else
2261 : : // ceil(2^31.5)
2262 : : #define CEIL_MAXUINT_DIV_SQRT2 0xb504f334U
2263 : : #endif
2264 : : int ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2265 : : size_t k, n;
2266 : : int rounds;
2267 : : mbedtls_mpi_uint r;
2268 : : mbedtls_mpi Y;
2269 : :
2270 : : if (nbits < 3 || nbits > MBEDTLS_MPI_MAX_BITS) {
2271 : : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
2272 : : }
2273 : :
2274 : : mbedtls_mpi_init(&Y);
2275 : :
2276 : : n = BITS_TO_LIMBS(nbits);
2277 : :
2278 : : if ((flags & MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR) == 0) {
2279 : : /*
2280 : : * 2^-80 error probability, number of rounds chosen per HAC, table 4.4
2281 : : */
2282 : : rounds = ((nbits >= 1300) ? 2 : (nbits >= 850) ? 3 :
2283 : : (nbits >= 650) ? 4 : (nbits >= 350) ? 8 :
2284 : : (nbits >= 250) ? 12 : (nbits >= 150) ? 18 : 27);
2285 : : } else {
2286 : : /*
2287 : : * 2^-100 error probability, number of rounds computed based on HAC,
2288 : : * fact 4.48
2289 : : */
2290 : : rounds = ((nbits >= 1450) ? 4 : (nbits >= 1150) ? 5 :
2291 : : (nbits >= 1000) ? 6 : (nbits >= 850) ? 7 :
2292 : : (nbits >= 750) ? 8 : (nbits >= 500) ? 13 :
2293 : : (nbits >= 250) ? 28 : (nbits >= 150) ? 40 : 51);
2294 : : }
2295 : :
2296 : : while (1) {
2297 : : MBEDTLS_MPI_CHK(mbedtls_mpi_fill_random(X, n * ciL, f_rng, p_rng));
2298 : : /* make sure generated number is at least (nbits-1)+0.5 bits (FIPS 186-4 §B.3.3 steps 4.4, 5.5) */
2299 : : if (X->p[n-1] < CEIL_MAXUINT_DIV_SQRT2) {
2300 : : continue;
2301 : : }
2302 : :
2303 : : k = n * biL;
2304 : : if (k > nbits) {
2305 : : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(X, k - nbits));
2306 : : }
2307 : : X->p[0] |= 1;
2308 : :
2309 : : if ((flags & MBEDTLS_MPI_GEN_PRIME_FLAG_DH) == 0) {
2310 : : ret = mbedtls_mpi_is_prime_ext(X, rounds, f_rng, p_rng);
2311 : :
2312 : : if (ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE) {
2313 : : goto cleanup;
2314 : : }
2315 : : } else {
2316 : : /*
2317 : : * A necessary condition for Y and X = 2Y + 1 to be prime
2318 : : * is X = 2 mod 3 (which is equivalent to Y = 2 mod 3).
2319 : : * Make sure it is satisfied, while keeping X = 3 mod 4
2320 : : */
2321 : :
2322 : : X->p[0] |= 2;
2323 : :
2324 : : MBEDTLS_MPI_CHK(mbedtls_mpi_mod_int(&r, X, 3));
2325 : : if (r == 0) {
2326 : : MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, X, 8));
2327 : : } else if (r == 1) {
2328 : : MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, X, 4));
2329 : : }
2330 : :
2331 : : /* Set Y = (X-1) / 2, which is X / 2 because X is odd */
2332 : : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&Y, X));
2333 : : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&Y, 1));
2334 : :
2335 : : while (1) {
2336 : : /*
2337 : : * First, check small factors for X and Y
2338 : : * before doing Miller-Rabin on any of them
2339 : : */
2340 : : if ((ret = mpi_check_small_factors(X)) == 0 &&
2341 : : (ret = mpi_check_small_factors(&Y)) == 0 &&
2342 : : (ret = mpi_miller_rabin(X, rounds, f_rng, p_rng))
2343 : : == 0 &&
2344 : : (ret = mpi_miller_rabin(&Y, rounds, f_rng, p_rng))
2345 : : == 0) {
2346 : : goto cleanup;
2347 : : }
2348 : :
2349 : : if (ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE) {
2350 : : goto cleanup;
2351 : : }
2352 : :
2353 : : /*
2354 : : * Next candidates. We want to preserve Y = (X-1) / 2 and
2355 : : * Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3)
2356 : : * so up Y by 6 and X by 12.
2357 : : */
2358 : : MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, X, 12));
2359 : : MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(&Y, &Y, 6));
2360 : : }
2361 : : }
2362 : : }
2363 : :
2364 : : cleanup:
2365 : :
2366 : : mbedtls_mpi_free(&Y);
2367 : :
2368 : : return ret;
2369 : : }
2370 : :
2371 : : #endif /* MBEDTLS_GENPRIME */
2372 : :
2373 : : #if defined(MBEDTLS_SELF_TEST)
2374 : :
2375 : : #define GCD_PAIR_COUNT 3
2376 : :
2377 : : static const int gcd_pairs[GCD_PAIR_COUNT][3] =
2378 : : {
2379 : : { 693, 609, 21 },
2380 : : { 1764, 868, 28 },
2381 : : { 768454923, 542167814, 1 }
2382 : : };
2383 : :
2384 : : /*
2385 : : * Checkup routine
2386 : : */
2387 : : int mbedtls_mpi_self_test(int verbose)
2388 : : {
2389 : : int ret, i;
2390 : : mbedtls_mpi A, E, N, X, Y, U, V;
2391 : :
2392 : : mbedtls_mpi_init(&A); mbedtls_mpi_init(&E); mbedtls_mpi_init(&N); mbedtls_mpi_init(&X);
2393 : : mbedtls_mpi_init(&Y); mbedtls_mpi_init(&U); mbedtls_mpi_init(&V);
2394 : :
2395 : : MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&A, 16,
2396 : : "EFE021C2645FD1DC586E69184AF4A31E" \
2397 : : "D5F53E93B5F123FA41680867BA110131" \
2398 : : "944FE7952E2517337780CB0DB80E61AA" \
2399 : : "E7C8DDC6C5C6AADEB34EB38A2F40D5E6"));
2400 : :
2401 : : MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&E, 16,
2402 : : "B2E7EFD37075B9F03FF989C7C5051C20" \
2403 : : "34D2A323810251127E7BF8625A4F49A5" \
2404 : : "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
2405 : : "5B5C25763222FEFCCFC38B832366C29E"));
2406 : :
2407 : : MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&N, 16,
2408 : : "0066A198186C18C10B2F5ED9B522752A" \
2409 : : "9830B69916E535C8F047518A889A43A5" \
2410 : : "94B6BED27A168D31D4A52F88925AA8F5"));
2411 : :
2412 : : MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(&X, &A, &N));
2413 : :
2414 : : MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&U, 16,
2415 : : "602AB7ECA597A3D6B56FF9829A5E8B85" \
2416 : : "9E857EA95A03512E2BAE7391688D264A" \
2417 : : "A5663B0341DB9CCFD2C4C5F421FEC814" \
2418 : : "8001B72E848A38CAE1C65F78E56ABDEF" \
2419 : : "E12D3C039B8A02D6BE593F0BBBDA56F1" \
2420 : : "ECF677152EF804370C1A305CAF3B5BF1" \
2421 : : "30879B56C61DE584A0F53A2447A51E"));
2422 : :
2423 : : if (verbose != 0) {
2424 : : mbedtls_printf(" MPI test #1 (mul_mpi): ");
2425 : : }
2426 : :
2427 : : if (mbedtls_mpi_cmp_mpi(&X, &U) != 0) {
2428 : : if (verbose != 0) {
2429 : : mbedtls_printf("failed\n");
2430 : : }
2431 : :
2432 : : ret = 1;
2433 : : goto cleanup;
2434 : : }
2435 : :
2436 : : if (verbose != 0) {
2437 : : mbedtls_printf("passed\n");
2438 : : }
2439 : :
2440 : : MBEDTLS_MPI_CHK(mbedtls_mpi_div_mpi(&X, &Y, &A, &N));
2441 : :
2442 : : MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&U, 16,
2443 : : "256567336059E52CAE22925474705F39A94"));
2444 : :
2445 : : MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&V, 16,
2446 : : "6613F26162223DF488E9CD48CC132C7A" \
2447 : : "0AC93C701B001B092E4E5B9F73BCD27B" \
2448 : : "9EE50D0657C77F374E903CDFA4C642"));
2449 : :
2450 : : if (verbose != 0) {
2451 : : mbedtls_printf(" MPI test #2 (div_mpi): ");
2452 : : }
2453 : :
2454 : : if (mbedtls_mpi_cmp_mpi(&X, &U) != 0 ||
2455 : : mbedtls_mpi_cmp_mpi(&Y, &V) != 0) {
2456 : : if (verbose != 0) {
2457 : : mbedtls_printf("failed\n");
2458 : : }
2459 : :
2460 : : ret = 1;
2461 : : goto cleanup;
2462 : : }
2463 : :
2464 : : if (verbose != 0) {
2465 : : mbedtls_printf("passed\n");
2466 : : }
2467 : :
2468 : : MBEDTLS_MPI_CHK(mbedtls_mpi_exp_mod(&X, &A, &E, &N, NULL));
2469 : :
2470 : : MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&U, 16,
2471 : : "36E139AEA55215609D2816998ED020BB" \
2472 : : "BD96C37890F65171D948E9BC7CBAA4D9" \
2473 : : "325D24D6A3C12710F10A09FA08AB87"));
2474 : :
2475 : : if (verbose != 0) {
2476 : : mbedtls_printf(" MPI test #3 (exp_mod): ");
2477 : : }
2478 : :
2479 : : if (mbedtls_mpi_cmp_mpi(&X, &U) != 0) {
2480 : : if (verbose != 0) {
2481 : : mbedtls_printf("failed\n");
2482 : : }
2483 : :
2484 : : ret = 1;
2485 : : goto cleanup;
2486 : : }
2487 : :
2488 : : if (verbose != 0) {
2489 : : mbedtls_printf("passed\n");
2490 : : }
2491 : :
2492 : : MBEDTLS_MPI_CHK(mbedtls_mpi_inv_mod(&X, &A, &N));
2493 : :
2494 : : MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&U, 16,
2495 : : "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
2496 : : "C3DBA76456363A10869622EAC2DD84EC" \
2497 : : "C5B8A74DAC4D09E03B5E0BE779F2DF61"));
2498 : :
2499 : : if (verbose != 0) {
2500 : : mbedtls_printf(" MPI test #4 (inv_mod): ");
2501 : : }
2502 : :
2503 : : if (mbedtls_mpi_cmp_mpi(&X, &U) != 0) {
2504 : : if (verbose != 0) {
2505 : : mbedtls_printf("failed\n");
2506 : : }
2507 : :
2508 : : ret = 1;
2509 : : goto cleanup;
2510 : : }
2511 : :
2512 : : if (verbose != 0) {
2513 : : mbedtls_printf("passed\n");
2514 : : }
2515 : :
2516 : : if (verbose != 0) {
2517 : : mbedtls_printf(" MPI test #5 (simple gcd): ");
2518 : : }
2519 : :
2520 : : for (i = 0; i < GCD_PAIR_COUNT; i++) {
2521 : : MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&X, gcd_pairs[i][0]));
2522 : : MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&Y, gcd_pairs[i][1]));
2523 : :
2524 : : MBEDTLS_MPI_CHK(mbedtls_mpi_gcd(&A, &X, &Y));
2525 : :
2526 : : if (mbedtls_mpi_cmp_int(&A, gcd_pairs[i][2]) != 0) {
2527 : : if (verbose != 0) {
2528 : : mbedtls_printf("failed at %d\n", i);
2529 : : }
2530 : :
2531 : : ret = 1;
2532 : : goto cleanup;
2533 : : }
2534 : : }
2535 : :
2536 : : if (verbose != 0) {
2537 : : mbedtls_printf("passed\n");
2538 : : }
2539 : :
2540 : : cleanup:
2541 : :
2542 : : if (ret != 0 && verbose != 0) {
2543 : : mbedtls_printf("Unexpected error, return code = %08X\n", (unsigned int) ret);
2544 : : }
2545 : :
2546 : : mbedtls_mpi_free(&A); mbedtls_mpi_free(&E); mbedtls_mpi_free(&N); mbedtls_mpi_free(&X);
2547 : : mbedtls_mpi_free(&Y); mbedtls_mpi_free(&U); mbedtls_mpi_free(&V);
2548 : :
2549 : : if (verbose != 0) {
2550 : : mbedtls_printf("\n");
2551 : : }
2552 : :
2553 : : return ret;
2554 : : }
2555 : :
2556 : : #endif /* MBEDTLS_SELF_TEST */
2557 : :
2558 : : #endif /* MBEDTLS_BIGNUM_C */
|
