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 4923341 : static inline signed short mbedtls_ct_mpi_sign_if(mbedtls_ct_condition_t cond,
49 : signed short sign1, signed short sign2)
50 : {
51 4923341 : 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 : mbedtls_ct_condition_t different_sign, X_is_negative, Y_is_negative, result;
62 :
63 0 : if (X->n != Y->n) {
64 0 : 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 4923341 : int mbedtls_mpi_safe_cond_assign(mbedtls_mpi *X,
119 : const mbedtls_mpi *Y,
120 : unsigned char assign)
121 : {
122 4923341 : int ret = 0;
123 :
124 4923341 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, Y->n));
125 :
126 : {
127 4923341 : mbedtls_ct_condition_t do_assign = mbedtls_ct_bool(assign);
128 :
129 4923341 : X->s = mbedtls_ct_mpi_sign_if(do_assign, Y->s, X->s);
130 :
131 4923341 : mbedtls_mpi_core_cond_assign(X->p, Y->p, Y->n, do_assign);
132 :
133 4923341 : mbedtls_ct_condition_t do_not_assign = mbedtls_ct_bool_not(do_assign);
134 4940296 : for (size_t i = Y->n; i < X->n; i++) {
135 16955 : X->p[i] = mbedtls_ct_mpi_uint_if_else_0(do_not_assign, X->p[i]);
136 : }
137 : }
138 :
139 4923341 : cleanup:
140 4923341 : 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 : int s;
155 :
156 0 : if (X == Y) {
157 0 : 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 0 : cleanup:
172 0 : 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 13542782 : void mbedtls_mpi_init(mbedtls_mpi *X)
182 : {
183 13542782 : X->s = 1;
184 13542782 : X->n = 0;
185 13542782 : X->p = NULL;
186 13542782 : }
187 :
188 : /*
189 : * Unallocate one MPI
190 : */
191 13500417 : void mbedtls_mpi_free(mbedtls_mpi *X)
192 : {
193 13500417 : if (X == NULL) {
194 0 : return;
195 : }
196 :
197 13500417 : if (X->p != NULL) {
198 2283870 : mbedtls_mpi_zeroize_and_free(X->p, X->n);
199 : }
200 :
201 13500417 : X->s = 1;
202 13500417 : X->n = 0;
203 13500417 : X->p = NULL;
204 : }
205 :
206 : /*
207 : * Enlarge to the specified number of limbs
208 : */
209 41695373 : int mbedtls_mpi_grow(mbedtls_mpi *X, size_t nblimbs)
210 : {
211 : mbedtls_mpi_uint *p;
212 :
213 41695373 : if (nblimbs > MBEDTLS_MPI_MAX_LIMBS) {
214 0 : return MBEDTLS_ERR_MPI_ALLOC_FAILED;
215 : }
216 :
217 41695373 : if (X->n < nblimbs) {
218 2477091 : if ((p = (mbedtls_mpi_uint *) mbedtls_calloc(nblimbs, ciL)) == NULL) {
219 0 : return MBEDTLS_ERR_MPI_ALLOC_FAILED;
220 : }
221 :
222 2477091 : if (X->p != NULL) {
223 192461 : memcpy(p, X->p, X->n * ciL);
224 192461 : 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 2477091 : X->n = (unsigned short) nblimbs;
230 2477091 : X->p = p;
231 : }
232 :
233 41695373 : return 0;
234 : }
235 :
236 : /*
237 : * Resize down as much as possible,
238 : * while keeping at least the specified number of limbs
239 : */
240 31952 : int mbedtls_mpi_shrink(mbedtls_mpi *X, size_t nblimbs)
241 : {
242 : mbedtls_mpi_uint *p;
243 : size_t i;
244 :
245 31952 : if (nblimbs > MBEDTLS_MPI_MAX_LIMBS) {
246 0 : return MBEDTLS_ERR_MPI_ALLOC_FAILED;
247 : }
248 :
249 : /* Actually resize up if there are currently fewer than nblimbs limbs. */
250 31952 : 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 212010 : for (i = X->n - 1; i > 0; i--) {
256 212010 : if (X->p[i] != 0) {
257 31952 : break;
258 : }
259 : }
260 31952 : i++;
261 :
262 31952 : if (i < nblimbs) {
263 281 : i = nblimbs;
264 : }
265 :
266 31952 : if ((p = (mbedtls_mpi_uint *) mbedtls_calloc(i, ciL)) == NULL) {
267 0 : return MBEDTLS_ERR_MPI_ALLOC_FAILED;
268 : }
269 :
270 31952 : if (X->p != NULL) {
271 31952 : memcpy(p, X->p, i * ciL);
272 31952 : 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 31952 : X->n = (unsigned short) i;
278 31952 : X->p = p;
279 :
280 31952 : return 0;
281 : }
282 :
283 : /* Resize X to have exactly n limbs and set it to 0. */
284 34749 : static int mbedtls_mpi_resize_clear(mbedtls_mpi *X, size_t limbs)
285 : {
286 34749 : if (limbs == 0) {
287 0 : mbedtls_mpi_free(X);
288 0 : return 0;
289 34749 : } else if (X->n == limbs) {
290 110 : memset(X->p, 0, limbs * ciL);
291 110 : X->s = 1;
292 110 : return 0;
293 : } else {
294 34639 : mbedtls_mpi_free(X);
295 34639 : 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 4702031 : int mbedtls_mpi_copy(mbedtls_mpi *X, const mbedtls_mpi *Y)
308 : {
309 4702031 : int ret = 0;
310 : size_t i;
311 :
312 4702031 : if (X == Y) {
313 67388 : return 0;
314 : }
315 :
316 4634643 : if (Y->n == 0) {
317 2247 : if (X->n != 0) {
318 0 : X->s = 1;
319 0 : memset(X->p, 0, X->n * ciL);
320 : }
321 2247 : return 0;
322 : }
323 :
324 27236970 : for (i = Y->n - 1; i > 0; i--) {
325 27219704 : if (Y->p[i] != 0) {
326 4615130 : break;
327 : }
328 : }
329 4632396 : i++;
330 :
331 4632396 : X->s = Y->s;
332 :
333 4632396 : if (X->n < i) {
334 1900654 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, i));
335 : } else {
336 2731742 : memset(X->p + i, 0, (X->n - i) * ciL);
337 : }
338 :
339 4632396 : memcpy(X->p, Y->p, i * ciL);
340 :
341 4632396 : cleanup:
342 :
343 4632396 : 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 : 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 15046979 : static inline mbedtls_mpi_uint mpi_sint_abs(mbedtls_mpi_sint z)
359 : {
360 15046979 : if (z >= 0) {
361 15043979 : 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 3000 : 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 6742495 : int mbedtls_mpi_lset(mbedtls_mpi *X, mbedtls_mpi_sint z)
378 : {
379 6742495 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
380 :
381 6742495 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, 1));
382 6742495 : memset(X->p, 0, X->n * ciL);
383 :
384 6742495 : X->p[0] = mpi_sint_abs(z);
385 6742495 : X->s = TO_SIGN(z);
386 :
387 6742495 : cleanup:
388 :
389 6742495 : return ret;
390 : }
391 :
392 : /*
393 : * Get a specific bit
394 : */
395 896840 : int mbedtls_mpi_get_bit(const mbedtls_mpi *X, size_t pos)
396 : {
397 896840 : if (X->n * biL <= pos) {
398 7264 : return 0;
399 : }
400 :
401 889576 : 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 0 : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
415 : }
416 :
417 0 : if (X->n * biL <= pos) {
418 0 : if (val == 0) {
419 0 : 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 0 : cleanup:
429 :
430 0 : 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 2 : size_t mbedtls_mpi_lsb(const mbedtls_mpi *X)
463 : {
464 : size_t i;
465 :
466 2 : for (i = 0; i < X->n; i++) {
467 2 : if (X->p[i] != 0) {
468 2 : return i * biL + mbedtls_mpi_uint_ctz(X->p[i]);
469 : }
470 : }
471 :
472 0 : return 0;
473 : }
474 :
475 : /*
476 : * Return the number of bits
477 : */
478 8740358 : size_t mbedtls_mpi_bitlen(const mbedtls_mpi *X)
479 : {
480 8740358 : return mbedtls_mpi_core_bitlen(X->p, X->n);
481 : }
482 :
483 : /*
484 : * Return the total size in bytes
485 : */
486 18215 : size_t mbedtls_mpi_size(const mbedtls_mpi *X)
487 : {
488 18215 : 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 0 : 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 : size_t i, j, slen, n;
522 0 : int sign = 1;
523 : mbedtls_mpi_uint d;
524 : mbedtls_mpi T;
525 :
526 0 : if (radix < 2 || radix > 16) {
527 0 : 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 0 : 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 : mbedtls_mpi_uint r;
587 0 : size_t length = 0;
588 0 : char *p_end = *p + buflen;
589 :
590 : do {
591 0 : if (length >= buflen) {
592 0 : 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 0 : cleanup:
613 :
614 0 : 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 : size_t n;
625 : char *p;
626 : mbedtls_mpi T;
627 :
628 0 : if (radix < 2 || radix > 16) {
629 0 : 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 : int c;
666 : 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 33926 : int mbedtls_mpi_read_binary(mbedtls_mpi *X, const unsigned char *buf, size_t buflen)
826 : {
827 33926 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
828 33926 : const size_t limbs = CHARS_TO_LIMBS(buflen);
829 :
830 : /* Ensure that target MPI has exactly the necessary number of limbs */
831 33926 : MBEDTLS_MPI_CHK(mbedtls_mpi_resize_clear(X, limbs));
832 :
833 33926 : MBEDTLS_MPI_CHK(mbedtls_mpi_core_read_be(X->p, X->n, buf, buflen));
834 :
835 33926 : 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 33926 : 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 1118 : int mbedtls_mpi_write_binary(const mbedtls_mpi *X,
858 : unsigned char *buf, size_t buflen)
859 : {
860 1118 : return mbedtls_mpi_core_write_be(X->p, X->n, buf, buflen);
861 : }
862 :
863 : /*
864 : * Left-shift: X <<= count
865 : */
866 2248440 : int mbedtls_mpi_shift_l(mbedtls_mpi *X, size_t count)
867 : {
868 2248440 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
869 : size_t i;
870 :
871 2248440 : i = mbedtls_mpi_bitlen(X) + count;
872 :
873 2248440 : if (X->n * biL < i) {
874 11276 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, BITS_TO_LIMBS(i)));
875 : }
876 :
877 2248440 : ret = 0;
878 :
879 2248440 : mbedtls_mpi_core_shift_l(X->p, X->n, count);
880 2248440 : cleanup:
881 :
882 2248440 : return ret;
883 : }
884 :
885 : /*
886 : * Right-shift: X >>= count
887 : */
888 7557 : int mbedtls_mpi_shift_r(mbedtls_mpi *X, size_t count)
889 : {
890 7557 : if (X->n != 0) {
891 7557 : mbedtls_mpi_core_shift_r(X->p, X->n, count);
892 : }
893 7557 : return 0;
894 : }
895 :
896 : /*
897 : * Compare unsigned values
898 : */
899 11085845 : int mbedtls_mpi_cmp_abs(const mbedtls_mpi *X, const mbedtls_mpi *Y)
900 : {
901 : size_t i, j;
902 :
903 62916378 : for (i = X->n; i > 0; i--) {
904 62916378 : if (X->p[i - 1] != 0) {
905 11085845 : break;
906 : }
907 : }
908 :
909 30458889 : for (j = Y->n; j > 0; j--) {
910 30458887 : if (Y->p[j - 1] != 0) {
911 11085843 : 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 11085845 : if (i > j) {
919 1529272 : return 1;
920 : }
921 9556573 : if (j > i) {
922 0 : return -1;
923 : }
924 :
925 9587113 : for (; i > 0; i--) {
926 9587111 : if (X->p[i - 1] > Y->p[i - 1]) {
927 2096535 : return 1;
928 : }
929 7490576 : if (X->p[i - 1] < Y->p[i - 1]) {
930 7460036 : return -1;
931 : }
932 : }
933 :
934 2 : return 0;
935 : }
936 :
937 : /*
938 : * Compare signed values
939 : */
940 21067062 : int mbedtls_mpi_cmp_mpi(const mbedtls_mpi *X, const mbedtls_mpi *Y)
941 : {
942 : size_t i, j;
943 :
944 120664407 : for (i = X->n; i > 0; i--) {
945 120655928 : if (X->p[i - 1] != 0) {
946 21058583 : break;
947 : }
948 : }
949 :
950 29192293 : for (j = Y->n; j > 0; j--) {
951 21151168 : if (Y->p[j - 1] != 0) {
952 13025937 : break;
953 : }
954 : }
955 :
956 21067062 : if (i == 0 && j == 0) {
957 8472 : return 0;
958 : }
959 :
960 21058590 : if (i > j) {
961 11037160 : return X->s;
962 : }
963 10021430 : if (j > i) {
964 18467 : return -Y->s;
965 : }
966 :
967 10002963 : if (X->s > 0 && Y->s < 0) {
968 0 : return 1;
969 : }
970 10002963 : if (Y->s > 0 && X->s < 0) {
971 0 : return -1;
972 : }
973 :
974 10364390 : for (; i > 0; i--) {
975 10119141 : if (X->p[i - 1] > Y->p[i - 1]) {
976 29019 : return X->s;
977 : }
978 10090122 : if (X->p[i - 1] < Y->p[i - 1]) {
979 9728695 : return -X->s;
980 : }
981 : }
982 :
983 245249 : return 0;
984 : }
985 :
986 : /*
987 : * Compare signed values
988 : */
989 8288246 : int mbedtls_mpi_cmp_int(const mbedtls_mpi *X, mbedtls_mpi_sint z)
990 : {
991 : mbedtls_mpi Y;
992 : mbedtls_mpi_uint p[1];
993 :
994 8288246 : *p = mpi_sint_abs(z);
995 8288246 : Y.s = TO_SIGN(z);
996 8288246 : Y.n = 1;
997 8288246 : Y.p = p;
998 :
999 8288246 : return mbedtls_mpi_cmp_mpi(X, &Y);
1000 : }
1001 :
1002 : /*
1003 : * Unsigned addition: X = |A| + |B| (HAC 14.7)
1004 : */
1005 514083 : int mbedtls_mpi_add_abs(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
1006 : {
1007 514083 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1008 : size_t j;
1009 : mbedtls_mpi_uint *p;
1010 : mbedtls_mpi_uint c;
1011 :
1012 514083 : if (X == B) {
1013 0 : const mbedtls_mpi *T = A; A = X; B = T;
1014 : }
1015 :
1016 514083 : if (X != A) {
1017 497670 : 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 514083 : X->s = 1;
1024 :
1025 3016007 : for (j = B->n; j > 0; j--) {
1026 3016007 : if (B->p[j - 1] != 0) {
1027 514083 : 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 514083 : if (j == 0) {
1034 0 : return 0;
1035 : }
1036 :
1037 514083 : 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 514083 : p = X->p;
1042 :
1043 514083 : c = mbedtls_mpi_core_add(p, p, B->p, j);
1044 :
1045 514083 : p += j;
1046 :
1047 : /* Now propagate any carry */
1048 :
1049 762222 : while (c != 0) {
1050 248139 : if (j >= X->n) {
1051 193 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, j + 1));
1052 193 : p = X->p + j;
1053 : }
1054 :
1055 248139 : *p += c; c = (*p < c); j++; p++;
1056 : }
1057 :
1058 514083 : cleanup:
1059 :
1060 514083 : return ret;
1061 : }
1062 :
1063 : /*
1064 : * Unsigned subtraction: X = |A| - |B| (HAC 14.9, 14.10)
1065 : */
1066 14061706 : int mbedtls_mpi_sub_abs(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
1067 : {
1068 14061706 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1069 : size_t n;
1070 : mbedtls_mpi_uint carry;
1071 :
1072 60572133 : for (n = B->n; n > 0; n--) {
1073 60572131 : if (B->p[n - 1] != 0) {
1074 14061704 : break;
1075 : }
1076 : }
1077 14061706 : 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 14061706 : 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 14061706 : if (A->n > n && A != X) {
1089 2080458 : memcpy(X->p + n, A->p + n, (A->n - n) * ciL);
1090 : }
1091 14061706 : if (X->n > A->n) {
1092 5728301 : memset(X->p + A->n, 0, (X->n - A->n) * ciL);
1093 : }
1094 :
1095 14061706 : carry = mbedtls_mpi_core_sub(X->p, A->p, B->p, n);
1096 14061706 : if (carry != 0) {
1097 : /* Propagate the carry through the rest of X. */
1098 4485961 : 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 4485961 : 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 14061706 : X->s = 1;
1109 :
1110 14061706 : cleanup:
1111 14061706 : 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 11594477 : static int add_sub_mpi(mbedtls_mpi *X,
1118 : const mbedtls_mpi *A, const mbedtls_mpi *B,
1119 : int flip_B)
1120 : {
1121 : int ret, s;
1122 :
1123 11594477 : s = A->s;
1124 11594477 : if (A->s * B->s * flip_B < 0) {
1125 11080433 : int cmp = mbedtls_mpi_cmp_abs(A, B);
1126 11080433 : if (cmp >= 0) {
1127 3622050 : 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 3622050 : X->s = cmp == 0 ? 1 : s;
1132 : } else {
1133 7458383 : MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(X, B, A));
1134 : /* Since |A| < |B|, the sign is the opposite of A. */
1135 7458383 : X->s = -s;
1136 : }
1137 : } else {
1138 514044 : MBEDTLS_MPI_CHK(mbedtls_mpi_add_abs(X, A, B));
1139 514044 : X->s = s;
1140 : }
1141 :
1142 11594477 : cleanup:
1143 :
1144 11594477 : return ret;
1145 : }
1146 :
1147 : /*
1148 : * Signed addition: X = A + B
1149 : */
1150 7599217 : int mbedtls_mpi_add_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
1151 : {
1152 7599217 : return add_sub_mpi(X, A, B, 1);
1153 : }
1154 :
1155 : /*
1156 : * Signed subtraction: X = A - B
1157 : */
1158 3995260 : int mbedtls_mpi_sub_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
1159 : {
1160 3995260 : return add_sub_mpi(X, A, B, -1);
1161 : }
1162 :
1163 : /*
1164 : * Signed addition: X = A + b
1165 : */
1166 2 : int mbedtls_mpi_add_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b)
1167 : {
1168 : mbedtls_mpi B;
1169 : mbedtls_mpi_uint p[1];
1170 :
1171 2 : p[0] = mpi_sint_abs(b);
1172 2 : B.s = TO_SIGN(b);
1173 2 : B.n = 1;
1174 2 : B.p = p;
1175 :
1176 2 : return mbedtls_mpi_add_mpi(X, A, &B);
1177 : }
1178 :
1179 : /*
1180 : * Signed subtraction: X = A - b
1181 : */
1182 16236 : int mbedtls_mpi_sub_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b)
1183 : {
1184 : mbedtls_mpi B;
1185 : mbedtls_mpi_uint p[1];
1186 :
1187 16236 : p[0] = mpi_sint_abs(b);
1188 16236 : B.s = TO_SIGN(b);
1189 16236 : B.n = 1;
1190 16236 : B.p = p;
1191 :
1192 16236 : return mbedtls_mpi_sub_mpi(X, A, &B);
1193 : }
1194 :
1195 : /*
1196 : * Baseline multiplication: X = A * B (HAC 14.12)
1197 : */
1198 6440638 : int mbedtls_mpi_mul_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
1199 : {
1200 6440638 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1201 : size_t i, j;
1202 : mbedtls_mpi TA, TB;
1203 6440638 : int result_is_zero = 0;
1204 :
1205 6440638 : mbedtls_mpi_init(&TA);
1206 6440638 : mbedtls_mpi_init(&TB);
1207 :
1208 6440638 : if (X == A) {
1209 1832504 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TA, A)); A = &TA;
1210 : }
1211 6440638 : if (X == B) {
1212 21032 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TB, B)); B = &TB;
1213 : }
1214 :
1215 21901612 : for (i = A->n; i > 0; i--) {
1216 21901612 : if (A->p[i - 1] != 0) {
1217 6440638 : break;
1218 : }
1219 : }
1220 6440638 : if (i == 0) {
1221 0 : result_is_zero = 1;
1222 : }
1223 :
1224 28945132 : for (j = B->n; j > 0; j--) {
1225 28945132 : if (B->p[j - 1] != 0) {
1226 6440638 : break;
1227 : }
1228 : }
1229 6440638 : if (j == 0) {
1230 0 : result_is_zero = 1;
1231 : }
1232 :
1233 6440638 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, i + j));
1234 6440638 : MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 0));
1235 :
1236 6440638 : 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 6440638 : if (result_is_zero) {
1243 0 : X->s = 1;
1244 : } else {
1245 6440638 : X->s = A->s * B->s;
1246 : }
1247 :
1248 6440638 : cleanup:
1249 :
1250 6440638 : mbedtls_mpi_free(&TB); mbedtls_mpi_free(&TA);
1251 :
1252 6440638 : return ret;
1253 : }
1254 :
1255 : /*
1256 : * Baseline multiplication: X = A * b
1257 : */
1258 601559 : int mbedtls_mpi_mul_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b)
1259 : {
1260 601559 : size_t n = A->n;
1261 9215552 : while (n > 0 && A->p[n - 1] == 0) {
1262 8613993 : --n;
1263 : }
1264 :
1265 : /* The general method below doesn't work if b==0. */
1266 601559 : if (b == 0 || n == 0) {
1267 4 : 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 601555 : 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 601555 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, n + 1));
1284 601555 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, A));
1285 601555 : mbedtls_mpi_core_mla(X->p, X->n, A->p, n, b - 1);
1286 :
1287 601555 : cleanup:
1288 601555 : 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 38426 : 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 : 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 38426 : 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 38426 : dividend = (mbedtls_t_udbl) u1 << biL;
1323 38426 : dividend |= (mbedtls_t_udbl) u0;
1324 38426 : quotient = dividend / d;
1325 38426 : if (quotient > ((mbedtls_t_udbl) 1 << biL) - 1) {
1326 0 : quotient = ((mbedtls_t_udbl) 1 << biL) - 1;
1327 : }
1328 :
1329 38426 : if (r != NULL) {
1330 0 : *r = (mbedtls_mpi_uint) (dividend - (quotient * d));
1331 : }
1332 :
1333 38426 : 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 5412 : int mbedtls_mpi_div_mpi(mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A,
1399 : const mbedtls_mpi *B)
1400 : {
1401 5412 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1402 : size_t i, n, t, k;
1403 : mbedtls_mpi X, Y, Z, T1, T2;
1404 : mbedtls_mpi_uint TP2[3];
1405 :
1406 5412 : if (mbedtls_mpi_cmp_int(B, 0) == 0) {
1407 0 : return MBEDTLS_ERR_MPI_DIVISION_BY_ZERO;
1408 : }
1409 :
1410 5412 : mbedtls_mpi_init(&X); mbedtls_mpi_init(&Y); mbedtls_mpi_init(&Z);
1411 5412 : 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 5412 : T2.s = 1;
1420 5412 : T2.n = sizeof(TP2) / sizeof(*TP2);
1421 5412 : T2.p = TP2;
1422 :
1423 5412 : if (mbedtls_mpi_cmp_abs(A, B) < 0) {
1424 1653 : if (Q != NULL) {
1425 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_lset(Q, 0));
1426 : }
1427 1653 : if (R != NULL) {
1428 1653 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(R, A));
1429 : }
1430 1653 : return 0;
1431 : }
1432 :
1433 3759 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&X, A));
1434 3759 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&Y, B));
1435 3759 : X.s = Y.s = 1;
1436 :
1437 3759 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&Z, A->n + 2));
1438 3759 : MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&Z, 0));
1439 3759 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&T1, A->n + 2));
1440 :
1441 3759 : k = mbedtls_mpi_bitlen(&Y) % biL;
1442 3759 : if (k < biL - 1) {
1443 3759 : k = biL - 1 - k;
1444 3759 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&X, k));
1445 3759 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&Y, k));
1446 : } else {
1447 0 : k = 0;
1448 : }
1449 :
1450 3759 : n = X.n - 1;
1451 3759 : t = Y.n - 1;
1452 3759 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&Y, biL * (n - t)));
1453 :
1454 4212 : while (mbedtls_mpi_cmp_mpi(&X, &Y) >= 0) {
1455 453 : Z.p[n - t]++;
1456 453 : MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&X, &X, &Y));
1457 : }
1458 3759 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&Y, biL * (n - t)));
1459 :
1460 42185 : for (i = n; i > t; i--) {
1461 38426 : if (X.p[i] >= Y.p[t]) {
1462 0 : Z.p[i - t - 1] = ~(mbedtls_mpi_uint) 0u;
1463 : } else {
1464 38426 : Z.p[i - t - 1] = mbedtls_int_div_int(X.p[i], X.p[i - 1],
1465 38426 : Y.p[t], NULL);
1466 : }
1467 :
1468 38426 : T2.p[0] = (i < 2) ? 0 : X.p[i - 2];
1469 38426 : T2.p[1] = (i < 1) ? 0 : X.p[i - 1];
1470 38426 : T2.p[2] = X.p[i];
1471 :
1472 38426 : Z.p[i - t - 1]++;
1473 : do {
1474 65501 : Z.p[i - t - 1]--;
1475 :
1476 65501 : MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&T1, 0));
1477 65501 : T1.p[0] = (t < 1) ? 0 : Y.p[t - 1];
1478 65501 : T1.p[1] = Y.p[t];
1479 65501 : MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int(&T1, &T1, Z.p[i - t - 1]));
1480 65501 : } while (mbedtls_mpi_cmp_mpi(&T1, &T2) > 0);
1481 :
1482 38426 : MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int(&T1, &Y, Z.p[i - t - 1]));
1483 38426 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&T1, biL * (i - t - 1)));
1484 38426 : MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&X, &X, &T1));
1485 :
1486 38426 : 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 3759 : if (Q != NULL) {
1495 2 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(Q, &Z));
1496 2 : Q->s = A->s * B->s;
1497 : }
1498 :
1499 3759 : if (R != NULL) {
1500 3757 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&X, k));
1501 3757 : X.s = A->s;
1502 3757 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(R, &X));
1503 :
1504 3757 : if (mbedtls_mpi_cmp_int(R, 0) == 0) {
1505 0 : R->s = 1;
1506 : }
1507 : }
1508 :
1509 3759 : cleanup:
1510 :
1511 3759 : mbedtls_mpi_free(&X); mbedtls_mpi_free(&Y); mbedtls_mpi_free(&Z);
1512 3759 : mbedtls_mpi_free(&T1);
1513 3759 : mbedtls_platform_zeroize(TP2, sizeof(TP2));
1514 :
1515 3759 : 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 : mbedtls_mpi B;
1526 : 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 5410 : int mbedtls_mpi_mod_mpi(mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B)
1540 : {
1541 5410 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1542 :
1543 5410 : if (mbedtls_mpi_cmp_int(B, 0) < 0) {
1544 0 : return MBEDTLS_ERR_MPI_NEGATIVE_VALUE;
1545 : }
1546 :
1547 5410 : MBEDTLS_MPI_CHK(mbedtls_mpi_div_mpi(NULL, R, A, B));
1548 :
1549 5428 : while (mbedtls_mpi_cmp_int(R, 0) < 0) {
1550 18 : MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(R, R, B));
1551 : }
1552 :
1553 5410 : while (mbedtls_mpi_cmp_mpi(R, B) >= 0) {
1554 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(R, R, B));
1555 : }
1556 :
1557 5410 : cleanup:
1558 :
1559 5410 : 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 : size_t i;
1568 : mbedtls_mpi_uint x, y, z;
1569 :
1570 0 : if (b == 0) {
1571 0 : return MBEDTLS_ERR_MPI_DIVISION_BY_ZERO;
1572 : }
1573 :
1574 0 : if (b < 0) {
1575 0 : 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 503 : 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 503 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1628 :
1629 503 : if (mbedtls_mpi_cmp_int(N, 0) <= 0 || (N->p[0] & 1) == 0) {
1630 0 : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
1631 : }
1632 :
1633 503 : if (mbedtls_mpi_cmp_int(E, 0) < 0) {
1634 0 : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
1635 : }
1636 :
1637 1006 : if (mbedtls_mpi_bitlen(E) > MBEDTLS_MPI_MAX_BITS ||
1638 503 : 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 503 : 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 503 : size_t T_limbs = mbedtls_mpi_core_exp_mod_working_limbs(N->n, E->n);
1654 503 : mbedtls_mpi_uint *T = (mbedtls_mpi_uint *) mbedtls_calloc(T_limbs, sizeof(mbedtls_mpi_uint));
1655 503 : if (T == NULL) {
1656 0 : return MBEDTLS_ERR_MPI_ALLOC_FAILED;
1657 : }
1658 :
1659 : mbedtls_mpi RR;
1660 503 : mbedtls_mpi_init(&RR);
1661 :
1662 : /*
1663 : * If 1st call, pre-compute R^2 mod N
1664 : */
1665 503 : if (prec_RR == NULL || prec_RR->p == NULL) {
1666 414 : MBEDTLS_MPI_CHK(mbedtls_mpi_core_get_mont_r2_unsafe(&RR, N));
1667 :
1668 414 : if (prec_RR != NULL) {
1669 414 : *prec_RR = RR;
1670 : }
1671 : } else {
1672 89 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(prec_RR, N->n));
1673 89 : 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 503 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, A));
1681 :
1682 : /*
1683 : * Compensate for negative A (and correct at the end).
1684 : */
1685 503 : 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 503 : if (mbedtls_mpi_cmp_mpi(X, N) >= 0) {
1698 76 : MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(X, X, N));
1699 : }
1700 503 : 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 503 : mbedtls_mpi_uint mm = mbedtls_mpi_core_montmul_init(N->p);
1707 503 : mbedtls_mpi_core_to_mont_rep(X->p, X->p, N->p, N->n, mm, RR.p, T);
1708 503 : if (E_public == MBEDTLS_MPI_IS_PUBLIC) {
1709 345 : mbedtls_mpi_core_exp_mod_unsafe(X->p, X->p, N->p, N->n, E->p, E->n, RR.p, T);
1710 : } else {
1711 158 : mbedtls_mpi_core_exp_mod(X->p, X->p, N->p, N->n, E->p, E->n, RR.p, T);
1712 : }
1713 503 : 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 503 : 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 503 : cleanup:
1727 :
1728 503 : mbedtls_mpi_zeroize_and_free(T, T_limbs);
1729 :
1730 503 : if (prec_RR == NULL || prec_RR->p == NULL) {
1731 0 : mbedtls_mpi_free(&RR);
1732 : }
1733 :
1734 503 : return ret;
1735 : }
1736 :
1737 158 : 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 158 : return mbedtls_mpi_exp_mod_optionally_safe(X, A, E, MBEDTLS_MPI_IS_SECRET, N, prec_RR);
1742 : }
1743 :
1744 345 : 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 345 : 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 9733 : 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 9733 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1758 : mbedtls_mpi local_g;
1759 9733 : mbedtls_mpi_uint *T = NULL;
1760 9733 : const size_t T_factor = I != NULL ? 5 : 4;
1761 9733 : const mbedtls_mpi_uint zero = 0;
1762 :
1763 : /* Check requirements on A and N */
1764 19466 : if (mbedtls_mpi_cmp_int(A, 0) < 0 ||
1765 19466 : mbedtls_mpi_cmp_mpi(A, N) > 0 ||
1766 19466 : mbedtls_mpi_get_bit(N, 0) != 1 ||
1767 9729 : (I != NULL && mbedtls_mpi_cmp_int(N, 1) == 0)) {
1768 0 : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
1769 : }
1770 :
1771 : /* Check aliasing requirements */
1772 9733 : if (A == N || (I != NULL && (I == N || G == N))) {
1773 0 : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
1774 : }
1775 :
1776 9733 : mbedtls_mpi_init(&local_g);
1777 :
1778 9733 : if (G == NULL) {
1779 9689 : 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 9733 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(G, N->n));
1785 9733 : if (I != NULL) {
1786 9729 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(I, N->n));
1787 : }
1788 :
1789 9733 : T = mbedtls_calloc(sizeof(mbedtls_mpi_uint) * N->n, T_factor);
1790 9733 : if (T == NULL) {
1791 0 : ret = MBEDTLS_ERR_MPI_ALLOC_FAILED;
1792 0 : goto cleanup;
1793 : }
1794 :
1795 9733 : 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 9733 : const mbedtls_mpi_uint *Ap = A->p != NULL ? A->p : &zero;
1800 9733 : size_t An = A->n >= N->n ? N->n : A->p != NULL ? A->n : 1;
1801 9733 : mbedtls_mpi_core_gcd_modinv_odd(G->p, Ip, Ap, An, N->p, N->n, T);
1802 :
1803 9733 : G->s = 1;
1804 9733 : if (I != NULL) {
1805 9729 : I->s = 1;
1806 : }
1807 :
1808 9733 : if (G->n > N->n) {
1809 0 : memset(G->p + N->n, 0, ciL * (G->n - N->n));
1810 : }
1811 9733 : if (I != NULL && I->n > N->n) {
1812 3298 : memset(I->p + N->n, 0, ciL * (I->n - N->n));
1813 : }
1814 :
1815 6435 : cleanup:
1816 9733 : mbedtls_mpi_free(&local_g);
1817 9733 : mbedtls_free(T);
1818 9733 : 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 : 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 76 : 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 76 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1886 76 : const size_t limbs = CHARS_TO_LIMBS(size);
1887 :
1888 : /* Ensure that target MPI has exactly the necessary number of limbs */
1889 76 : MBEDTLS_MPI_CHK(mbedtls_mpi_resize_clear(X, limbs));
1890 76 : if (size == 0) {
1891 0 : return 0;
1892 : }
1893 :
1894 76 : ret = mbedtls_mpi_core_fill_random(X->p, X->n, size, f_rng, p_rng);
1895 :
1896 76 : cleanup:
1897 76 : return ret;
1898 : }
1899 :
1900 747 : 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 747 : if (min < 0) {
1907 0 : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
1908 : }
1909 747 : if (mbedtls_mpi_cmp_int(N, min) <= 0) {
1910 0 : 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 747 : int ret = mbedtls_mpi_resize_clear(X, N->n);
1917 747 : if (ret != 0) {
1918 0 : return ret;
1919 : }
1920 :
1921 747 : 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 2 : int mbedtls_mpi_inv_mod_odd(mbedtls_mpi *X,
1928 : const mbedtls_mpi *A,
1929 : const mbedtls_mpi *N)
1930 : {
1931 2 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1932 : mbedtls_mpi T, G;
1933 :
1934 2 : mbedtls_mpi_init(&T);
1935 2 : mbedtls_mpi_init(&G);
1936 :
1937 2 : MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(&T, A, N));
1938 2 : MBEDTLS_MPI_CHK(mbedtls_mpi_gcd_modinv_odd(&G, &T, &T, N));
1939 2 : if (mbedtls_mpi_cmp_int(&G, 1) != 0) {
1940 0 : ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
1941 0 : goto cleanup;
1942 : }
1943 :
1944 2 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, &T));
1945 :
1946 2 : cleanup:
1947 2 : mbedtls_mpi_free(&T);
1948 2 : mbedtls_mpi_free(&G);
1949 :
1950 2 : 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 : 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 : 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 0 : 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 0 : 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 0 : static int mpi_check_small_factors(const mbedtls_mpi *X)
2098 : {
2099 0 : int ret = 0;
2100 : size_t i;
2101 : mbedtls_mpi_uint r;
2102 0 : unsigned p = 3; /* The first odd prime */
2103 :
2104 0 : if ((X->p[0] & 1) == 0) {
2105 0 : return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2106 : }
2107 :
2108 0 : for (i = 0; i < sizeof(small_prime_gaps); p += small_prime_gaps[i], i++) {
2109 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_mod_int(&r, X, p));
2110 0 : if (r == 0) {
2111 0 : if (mbedtls_mpi_cmp_int(X, p) == 0) {
2112 0 : return 1;
2113 : } else {
2114 0 : return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2115 : }
2116 : }
2117 : }
2118 :
2119 0 : cleanup:
2120 0 : return ret;
2121 : }
2122 :
2123 : /*
2124 : * Miller-Rabin pseudo-primality test (HAC 4.24)
2125 : */
2126 0 : 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 0 : mbedtls_mpi_init(&W); mbedtls_mpi_init(&R);
2135 0 : mbedtls_mpi_init(&T); mbedtls_mpi_init(&A);
2136 0 : mbedtls_mpi_init(&RR);
2137 :
2138 : /*
2139 : * W = |X| - 1
2140 : * R = W >> lsb( W )
2141 : */
2142 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_sub_int(&W, X, 1));
2143 0 : s = mbedtls_mpi_lsb(&W);
2144 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&R, &W));
2145 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&R, s));
2146 :
2147 0 : for (i = 0; i < rounds; i++) {
2148 : /*
2149 : * pick a random A, 1 < A < |X| - 1
2150 : */
2151 0 : count = 0;
2152 : do {
2153 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_fill_random(&A, X->n * ciL, f_rng, p_rng));
2154 :
2155 0 : j = mbedtls_mpi_bitlen(&A);
2156 0 : k = mbedtls_mpi_bitlen(&W);
2157 0 : if (j > k) {
2158 0 : A.p[A.n - 1] &= ((mbedtls_mpi_uint) 1 << (k - (A.n - 1) * biL - 1)) - 1;
2159 : }
2160 :
2161 0 : if (count++ > 30) {
2162 0 : ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2163 0 : goto cleanup;
2164 : }
2165 :
2166 0 : } while (mbedtls_mpi_cmp_mpi(&A, &W) >= 0 ||
2167 0 : mbedtls_mpi_cmp_int(&A, 1) <= 0);
2168 :
2169 : /*
2170 : * A = A^R mod |X|
2171 : */
2172 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_exp_mod(&A, &A, &R, X, &RR));
2173 :
2174 0 : if (mbedtls_mpi_cmp_mpi(&A, &W) == 0 ||
2175 0 : mbedtls_mpi_cmp_int(&A, 1) == 0) {
2176 0 : continue;
2177 : }
2178 :
2179 0 : j = 1;
2180 0 : while (j < s && mbedtls_mpi_cmp_mpi(&A, &W) != 0) {
2181 : /*
2182 : * A = A * A mod |X|
2183 : */
2184 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(&T, &A, &A));
2185 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(&A, &T, X));
2186 :
2187 0 : if (mbedtls_mpi_cmp_int(&A, 1) == 0) {
2188 0 : break;
2189 : }
2190 :
2191 0 : j++;
2192 : }
2193 :
2194 : /*
2195 : * not prime if A != |X| - 1 or A == 1
2196 : */
2197 0 : if (mbedtls_mpi_cmp_mpi(&A, &W) != 0 ||
2198 0 : mbedtls_mpi_cmp_int(&A, 1) == 0) {
2199 0 : ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2200 0 : break;
2201 : }
2202 : }
2203 :
2204 0 : cleanup:
2205 0 : mbedtls_mpi_free(&W); mbedtls_mpi_free(&R);
2206 0 : mbedtls_mpi_free(&T); mbedtls_mpi_free(&A);
2207 0 : mbedtls_mpi_free(&RR);
2208 :
2209 0 : return ret;
2210 : }
2211 :
2212 : /*
2213 : * Pseudo-primality test: small factors, then Miller-Rabin
2214 : */
2215 0 : 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 0 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2220 : mbedtls_mpi XX;
2221 :
2222 0 : XX.s = 1;
2223 0 : XX.n = X->n;
2224 0 : XX.p = X->p;
2225 :
2226 0 : if (mbedtls_mpi_cmp_int(&XX, 0) == 0 ||
2227 0 : mbedtls_mpi_cmp_int(&XX, 1) == 0) {
2228 0 : return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2229 : }
2230 :
2231 0 : if (mbedtls_mpi_cmp_int(&XX, 2) == 0) {
2232 0 : return 0;
2233 : }
2234 :
2235 0 : if ((ret = mpi_check_small_factors(&XX)) != 0) {
2236 0 : if (ret == 1) {
2237 0 : return 0;
2238 : }
2239 :
2240 0 : return ret;
2241 : }
2242 :
2243 0 : 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 0 : 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 0 : 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 0 : if (nbits < 3 || nbits > MBEDTLS_MPI_MAX_BITS) {
2271 0 : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
2272 : }
2273 :
2274 0 : mbedtls_mpi_init(&Y);
2275 :
2276 0 : n = BITS_TO_LIMBS(nbits);
2277 :
2278 0 : 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 0 : rounds = ((nbits >= 1300) ? 2 : (nbits >= 850) ? 3 :
2283 0 : (nbits >= 650) ? 4 : (nbits >= 350) ? 8 :
2284 0 : (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 0 : rounds = ((nbits >= 1450) ? 4 : (nbits >= 1150) ? 5 :
2291 0 : (nbits >= 1000) ? 6 : (nbits >= 850) ? 7 :
2292 0 : (nbits >= 750) ? 8 : (nbits >= 500) ? 13 :
2293 0 : (nbits >= 250) ? 28 : (nbits >= 150) ? 40 : 51);
2294 : }
2295 :
2296 : while (1) {
2297 0 : 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 0 : if (X->p[n-1] < CEIL_MAXUINT_DIV_SQRT2) {
2300 0 : continue;
2301 : }
2302 :
2303 0 : k = n * biL;
2304 0 : if (k > nbits) {
2305 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(X, k - nbits));
2306 : }
2307 0 : X->p[0] |= 1;
2308 :
2309 0 : if ((flags & MBEDTLS_MPI_GEN_PRIME_FLAG_DH) == 0) {
2310 0 : ret = mbedtls_mpi_is_prime_ext(X, rounds, f_rng, p_rng);
2311 :
2312 0 : if (ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE) {
2313 0 : 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 0 : X->p[0] |= 2;
2323 :
2324 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_mod_int(&r, X, 3));
2325 0 : if (r == 0) {
2326 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, X, 8));
2327 0 : } else if (r == 1) {
2328 0 : 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 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&Y, X));
2333 0 : 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 0 : if ((ret = mpi_check_small_factors(X)) == 0 &&
2341 0 : (ret = mpi_check_small_factors(&Y)) == 0 &&
2342 0 : (ret = mpi_miller_rabin(X, rounds, f_rng, p_rng))
2343 0 : == 0 &&
2344 0 : (ret = mpi_miller_rabin(&Y, rounds, f_rng, p_rng))
2345 : == 0) {
2346 0 : goto cleanup;
2347 : }
2348 :
2349 0 : if (ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE) {
2350 0 : 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 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, X, 12));
2359 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(&Y, &Y, 6));
2360 : }
2361 : }
2362 : }
2363 :
2364 0 : cleanup:
2365 :
2366 0 : mbedtls_mpi_free(&Y);
2367 :
2368 0 : 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 0 : int mbedtls_mpi_self_test(int verbose)
2388 : {
2389 : int ret, i;
2390 : mbedtls_mpi A, E, N, X, Y, U, V;
2391 :
2392 0 : mbedtls_mpi_init(&A); mbedtls_mpi_init(&E); mbedtls_mpi_init(&N); mbedtls_mpi_init(&X);
2393 0 : mbedtls_mpi_init(&Y); mbedtls_mpi_init(&U); mbedtls_mpi_init(&V);
2394 :
2395 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&A, 16,
2396 : "EFE021C2645FD1DC586E69184AF4A31E" \
2397 : "D5F53E93B5F123FA41680867BA110131" \
2398 : "944FE7952E2517337780CB0DB80E61AA" \
2399 : "E7C8DDC6C5C6AADEB34EB38A2F40D5E6"));
2400 :
2401 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&E, 16,
2402 : "B2E7EFD37075B9F03FF989C7C5051C20" \
2403 : "34D2A323810251127E7BF8625A4F49A5" \
2404 : "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
2405 : "5B5C25763222FEFCCFC38B832366C29E"));
2406 :
2407 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&N, 16,
2408 : "0066A198186C18C10B2F5ED9B522752A" \
2409 : "9830B69916E535C8F047518A889A43A5" \
2410 : "94B6BED27A168D31D4A52F88925AA8F5"));
2411 :
2412 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(&X, &A, &N));
2413 :
2414 0 : 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 0 : if (verbose != 0) {
2424 0 : mbedtls_printf(" MPI test #1 (mul_mpi): ");
2425 : }
2426 :
2427 0 : if (mbedtls_mpi_cmp_mpi(&X, &U) != 0) {
2428 0 : if (verbose != 0) {
2429 0 : mbedtls_printf("failed\n");
2430 : }
2431 :
2432 0 : ret = 1;
2433 0 : goto cleanup;
2434 : }
2435 :
2436 0 : if (verbose != 0) {
2437 0 : mbedtls_printf("passed\n");
2438 : }
2439 :
2440 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_div_mpi(&X, &Y, &A, &N));
2441 :
2442 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&U, 16,
2443 : "256567336059E52CAE22925474705F39A94"));
2444 :
2445 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&V, 16,
2446 : "6613F26162223DF488E9CD48CC132C7A" \
2447 : "0AC93C701B001B092E4E5B9F73BCD27B" \
2448 : "9EE50D0657C77F374E903CDFA4C642"));
2449 :
2450 0 : if (verbose != 0) {
2451 0 : mbedtls_printf(" MPI test #2 (div_mpi): ");
2452 : }
2453 :
2454 0 : if (mbedtls_mpi_cmp_mpi(&X, &U) != 0 ||
2455 0 : mbedtls_mpi_cmp_mpi(&Y, &V) != 0) {
2456 0 : if (verbose != 0) {
2457 0 : mbedtls_printf("failed\n");
2458 : }
2459 :
2460 0 : ret = 1;
2461 0 : goto cleanup;
2462 : }
2463 :
2464 0 : if (verbose != 0) {
2465 0 : mbedtls_printf("passed\n");
2466 : }
2467 :
2468 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_exp_mod(&X, &A, &E, &N, NULL));
2469 :
2470 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&U, 16,
2471 : "36E139AEA55215609D2816998ED020BB" \
2472 : "BD96C37890F65171D948E9BC7CBAA4D9" \
2473 : "325D24D6A3C12710F10A09FA08AB87"));
2474 :
2475 0 : if (verbose != 0) {
2476 0 : mbedtls_printf(" MPI test #3 (exp_mod): ");
2477 : }
2478 :
2479 0 : if (mbedtls_mpi_cmp_mpi(&X, &U) != 0) {
2480 0 : if (verbose != 0) {
2481 0 : mbedtls_printf("failed\n");
2482 : }
2483 :
2484 0 : ret = 1;
2485 0 : goto cleanup;
2486 : }
2487 :
2488 0 : if (verbose != 0) {
2489 0 : mbedtls_printf("passed\n");
2490 : }
2491 :
2492 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_inv_mod(&X, &A, &N));
2493 :
2494 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&U, 16,
2495 : "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
2496 : "C3DBA76456363A10869622EAC2DD84EC" \
2497 : "C5B8A74DAC4D09E03B5E0BE779F2DF61"));
2498 :
2499 0 : if (verbose != 0) {
2500 0 : mbedtls_printf(" MPI test #4 (inv_mod): ");
2501 : }
2502 :
2503 0 : if (mbedtls_mpi_cmp_mpi(&X, &U) != 0) {
2504 0 : if (verbose != 0) {
2505 0 : mbedtls_printf("failed\n");
2506 : }
2507 :
2508 0 : ret = 1;
2509 0 : goto cleanup;
2510 : }
2511 :
2512 0 : if (verbose != 0) {
2513 0 : mbedtls_printf("passed\n");
2514 : }
2515 :
2516 0 : if (verbose != 0) {
2517 0 : mbedtls_printf(" MPI test #5 (simple gcd): ");
2518 : }
2519 :
2520 0 : for (i = 0; i < GCD_PAIR_COUNT; i++) {
2521 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&X, gcd_pairs[i][0]));
2522 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&Y, gcd_pairs[i][1]));
2523 :
2524 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_gcd(&A, &X, &Y));
2525 :
2526 0 : if (mbedtls_mpi_cmp_int(&A, gcd_pairs[i][2]) != 0) {
2527 0 : if (verbose != 0) {
2528 0 : mbedtls_printf("failed at %d\n", i);
2529 : }
2530 :
2531 0 : ret = 1;
2532 0 : goto cleanup;
2533 : }
2534 : }
2535 :
2536 0 : if (verbose != 0) {
2537 0 : mbedtls_printf("passed\n");
2538 : }
2539 :
2540 0 : cleanup:
2541 :
2542 0 : if (ret != 0 && verbose != 0) {
2543 0 : mbedtls_printf("Unexpected error, return code = %08X\n", (unsigned int) ret);
2544 : }
2545 :
2546 0 : mbedtls_mpi_free(&A); mbedtls_mpi_free(&E); mbedtls_mpi_free(&N); mbedtls_mpi_free(&X);
2547 0 : mbedtls_mpi_free(&Y); mbedtls_mpi_free(&U); mbedtls_mpi_free(&V);
2548 :
2549 0 : if (verbose != 0) {
2550 0 : mbedtls_printf("\n");
2551 : }
2552 :
2553 0 : return ret;
2554 : }
2555 :
2556 : #endif /* MBEDTLS_SELF_TEST */
2557 :
2558 : #endif /* MBEDTLS_BIGNUM_C */
|
