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