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 = (mbedtls_mpi_uint *) mbedtls_calloc(T_limbs, sizeof(mbedtls_mpi_uint)); 1760 if (T == NULL) { 1761 return MBEDTLS_ERR_MPI_ALLOC_FAILED; 1762 } 1763 1764 mbedtls_mpi RR; 1765 mbedtls_mpi_init_mempool(&RR); 1766 1767 /* 1768 * If 1st call, pre-compute R^2 mod N 1769 */ 1770 if (prec_RR == NULL || prec_RR->p == NULL) { 1771 MBEDTLS_MPI_CHK(mbedtls_mpi_core_get_mont_r2_unsafe(&RR, N)); 1772 1773 if (prec_RR != NULL) { 1774 *prec_RR = RR; 1775 } 1776 } else { 1777 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(prec_RR, N->n)); 1778 RR = *prec_RR; 1779 } 1780 1781 /* 1782 * To preserve constness we need to make a copy of A. Using X for this to 1783 * save memory. 1784 */ 1785 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, A)); 1786 1787 /* 1788 * Compensate for negative A (and correct at the end). 1789 */ 1790 X->s = 1; 1791 1792 /* 1793 * Make sure that X is in a form that is safe for consumption by 1794 * the core functions. 1795 * 1796 * - The core functions will not touch the limbs of X above N->n. The 1797 * result will be correct if those limbs are 0, which the mod call 1798 * ensures. 1799 * - Also, X must have at least as many limbs as N for the calls to the 1800 * core functions. 1801 */ 1802 if (mbedtls_mpi_cmp_mpi(X, N) >= 0) { 1803 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(X, X, N)); 1804 } 1805 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, N->n)); 1806 1807 /* 1808 * Convert to and from Montgomery around mbedtls_mpi_core_exp_mod(). 1809 */ 1810 { 1811 mbedtls_mpi_uint mm = mbedtls_mpi_core_montmul_init(N->p); 1812 mbedtls_mpi_core_to_mont_rep(X->p, X->p, N->p, N->n, mm, RR.p, T); 1813 if (E_public == MBEDTLS_MPI_IS_PUBLIC) { 1814 mbedtls_mpi_core_exp_mod_unsafe(X->p, X->p, N->p, N->n, E->p, E->n, RR.p, T); 1815 } else { 1816 mbedtls_mpi_core_exp_mod(X->p, X->p, N->p, N->n, E->p, E->n, RR.p, T); 1817 } 1818 mbedtls_mpi_core_from_mont_rep(X->p, X->p, N->p, N->n, mm, T); 1819 } 1820 1821 /* 1822 * Correct for negative A. 1823 */ 1824 if (A->s == -1 && (E->p[0] & 1) != 0) { 1825 mbedtls_ct_condition_t is_x_non_zero = mbedtls_mpi_core_check_zero_ct(X->p, X->n); 1826 X->s = mbedtls_ct_mpi_sign_if(is_x_non_zero, -1, 1); 1827 1828 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(X, N, X)); 1829 } 1830 1831 cleanup: 1832 1833 mbedtls_mpi_zeroize_and_free(T, T_limbs); 1834 1835 if (prec_RR == NULL || prec_RR->p == NULL) { 1836 mbedtls_mpi_free(&RR); 1837 } 1838 1839 return ret; 1840 } 1841 1842 int mbedtls_mpi_exp_mod(mbedtls_mpi *X, const mbedtls_mpi *A, 1843 const mbedtls_mpi *E, const mbedtls_mpi *N, 1844 mbedtls_mpi *prec_RR) 1845 { 1846 #if (defined(__KERNEL__) && defined(CFG_CORE_UNSAFE_MODEXP)) || \ 1847 (!defined(__KERNEL__) && defined(CFG_TA_MEBDTLS_UNSAFE_MODEXP)) 1848 return mbedtls_mpi_exp_mod_unsafe(X, A, E, N, prec_RR); 1849 #else 1850 return mbedtls_mpi_exp_mod_optionally_safe(X, A, E, MBEDTLS_MPI_IS_SECRET, N, prec_RR); 1851 #endif 1852 } 1853 1854 1855 /* 1856 * Sliding-window exponentiation: X = A^E mod N (HAC 14.85) 1857 */ 1858 int mbedtls_mpi_exp_mod_unsafe(mbedtls_mpi *X, const mbedtls_mpi *A, 1859 const mbedtls_mpi *E, const mbedtls_mpi *N, 1860 mbedtls_mpi *prec_RR) 1861 { 1862 return mbedtls_mpi_exp_mod_optionally_safe(X, A, E, MBEDTLS_MPI_IS_PUBLIC, N, prec_RR); 1863 } 1864 1865 /* 1866 * Greatest common divisor: G = gcd(A, B) (HAC 14.54) 1867 */ 1868 int mbedtls_mpi_gcd(mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B) 1869 { 1870 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1871 size_t lz, lzt; 1872 mbedtls_mpi TA, TB; 1873 1874 mbedtls_mpi_init_mempool(&TA); mbedtls_mpi_init_mempool(&TB); 1875 1876 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TA, A)); 1877 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TB, B)); 1878 1879 lz = mbedtls_mpi_lsb(&TA); 1880 lzt = mbedtls_mpi_lsb(&TB); 1881 1882 /* The loop below gives the correct result when A==0 but not when B==0. 1883 * So have a special case for B==0. Leverage the fact that we just 1884 * calculated the lsb and lsb(B)==0 iff B is odd or 0 to make the test 1885 * slightly more efficient than cmp_int(). */ 1886 if (lzt == 0 && mbedtls_mpi_get_bit(&TB, 0) == 0) { 1887 ret = mbedtls_mpi_copy(G, A); 1888 goto cleanup; 1889 } 1890 1891 if (lzt < lz) { 1892 lz = lzt; 1893 } 1894 1895 TA.s = TB.s = 1; 1896 1897 /* We mostly follow the procedure described in HAC 14.54, but with some 1898 * minor differences: 1899 * - Sequences of multiplications or divisions by 2 are grouped into a 1900 * single shift operation. 1901 * - The procedure in HAC assumes that 0 < TB <= TA. 1902 * - The condition TB <= TA is not actually necessary for correctness. 1903 * TA and TB have symmetric roles except for the loop termination 1904 * condition, and the shifts at the beginning of the loop body 1905 * remove any significance from the ordering of TA vs TB before 1906 * the shifts. 1907 * - If TA = 0, the loop goes through 0 iterations and the result is 1908 * correctly TB. 1909 * - The case TB = 0 was short-circuited above. 1910 * 1911 * For the correctness proof below, decompose the original values of 1912 * A and B as 1913 * A = sa * 2^a * A' with A'=0 or A' odd, and sa = +-1 1914 * B = sb * 2^b * B' with B'=0 or B' odd, and sb = +-1 1915 * Then gcd(A, B) = 2^{min(a,b)} * gcd(A',B'), 1916 * and gcd(A',B') is odd or 0. 1917 * 1918 * At the beginning, we have TA = |A| and TB = |B| so gcd(A,B) = gcd(TA,TB). 1919 * The code maintains the following invariant: 1920 * gcd(A,B) = 2^k * gcd(TA,TB) for some k (I) 1921 */ 1922 1923 /* Proof that the loop terminates: 1924 * At each iteration, either the right-shift by 1 is made on a nonzero 1925 * value and the nonnegative integer bitlen(TA) + bitlen(TB) decreases 1926 * by at least 1, or the right-shift by 1 is made on zero and then 1927 * TA becomes 0 which ends the loop (TB cannot be 0 if it is right-shifted 1928 * since in that case TB is calculated from TB-TA with the condition TB>TA). 1929 */ 1930 while (mbedtls_mpi_cmp_int(&TA, 0) != 0) { 1931 /* Divisions by 2 preserve the invariant (I). */ 1932 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TA, mbedtls_mpi_lsb(&TA))); 1933 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TB, mbedtls_mpi_lsb(&TB))); 1934 1935 /* Set either TA or TB to |TA-TB|/2. Since TA and TB are both odd, 1936 * TA-TB is even so the division by 2 has an integer result. 1937 * Invariant (I) is preserved since any odd divisor of both TA and TB 1938 * also divides |TA-TB|/2, and any odd divisor of both TA and |TA-TB|/2 1939 * also divides TB, and any odd divisor of both TB and |TA-TB|/2 also 1940 * divides TA. 1941 */ 1942 if (mbedtls_mpi_cmp_mpi(&TA, &TB) >= 0) { 1943 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(&TA, &TA, &TB)); 1944 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TA, 1)); 1945 } else { 1946 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(&TB, &TB, &TA)); 1947 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TB, 1)); 1948 } 1949 /* Note that one of TA or TB is still odd. */ 1950 } 1951 1952 /* By invariant (I), gcd(A,B) = 2^k * gcd(TA,TB) for some k. 1953 * At the loop exit, TA = 0, so gcd(TA,TB) = TB. 1954 * - If there was at least one loop iteration, then one of TA or TB is odd, 1955 * and TA = 0, so TB is odd and gcd(TA,TB) = gcd(A',B'). In this case, 1956 * lz = min(a,b) so gcd(A,B) = 2^lz * TB. 1957 * - If there was no loop iteration, then A was 0, and gcd(A,B) = B. 1958 * In this case, lz = 0 and B = TB so gcd(A,B) = B = 2^lz * TB as well. 1959 */ 1960 1961 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&TB, lz)); 1962 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(G, &TB)); 1963 1964 cleanup: 1965 1966 mbedtls_mpi_free(&TA); mbedtls_mpi_free(&TB); 1967 1968 return ret; 1969 } 1970 1971 /* 1972 * Fill X with size bytes of random. 1973 * The bytes returned from the RNG are used in a specific order which 1974 * is suitable for deterministic ECDSA (see the specification of 1975 * mbedtls_mpi_random() and the implementation in mbedtls_mpi_fill_random()). 1976 */ 1977 int mbedtls_mpi_fill_random(mbedtls_mpi *X, size_t size, 1978 int (*f_rng)(void *, unsigned char *, size_t), 1979 void *p_rng) 1980 { 1981 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1982 const size_t limbs = CHARS_TO_LIMBS(size); 1983 1984 /* Ensure that target MPI has exactly the necessary number of limbs */ 1985 MBEDTLS_MPI_CHK(mbedtls_mpi_resize_clear(X, limbs)); 1986 if (size == 0) { 1987 return 0; 1988 } 1989 1990 ret = mbedtls_mpi_core_fill_random(X->p, X->n, size, f_rng, p_rng); 1991 1992 cleanup: 1993 return ret; 1994 } 1995 1996 int mbedtls_mpi_random(mbedtls_mpi *X, 1997 mbedtls_mpi_sint min, 1998 const mbedtls_mpi *N, 1999 int (*f_rng)(void *, unsigned char *, size_t), 2000 void *p_rng) 2001 { 2002 if (min < 0) { 2003 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; 2004 } 2005 if (mbedtls_mpi_cmp_int(N, min) <= 0) { 2006 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; 2007 } 2008 2009 /* Ensure that target MPI has exactly the same number of limbs 2010 * as the upper bound, even if the upper bound has leading zeros. 2011 * This is necessary for mbedtls_mpi_core_random. */ 2012 int ret = mbedtls_mpi_resize_clear(X, N->n); 2013 if (ret != 0) { 2014 return ret; 2015 } 2016 2017 return mbedtls_mpi_core_random(X->p, min, N->p, X->n, f_rng, p_rng); 2018 } 2019 2020 /* 2021 * Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64) 2022 */ 2023 int mbedtls_mpi_inv_mod(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N) 2024 { 2025 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2026 mbedtls_mpi G, TA, TU, U1, U2, TB, TV, V1, V2; 2027 2028 if (mbedtls_mpi_cmp_int(N, 1) <= 0) { 2029 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; 2030 } 2031 2032 mbedtls_mpi_init_mempool(&TA); mbedtls_mpi_init_mempool(&TU); 2033 mbedtls_mpi_init_mempool(&U1); mbedtls_mpi_init_mempool(&U2); 2034 mbedtls_mpi_init_mempool(&G); mbedtls_mpi_init_mempool(&TB); 2035 mbedtls_mpi_init_mempool(&TV); mbedtls_mpi_init_mempool(&V1); 2036 mbedtls_mpi_init_mempool(&V2); 2037 2038 MBEDTLS_MPI_CHK(mbedtls_mpi_gcd(&G, A, N)); 2039 2040 if (mbedtls_mpi_cmp_int(&G, 1) != 0) { 2041 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; 2042 goto cleanup; 2043 } 2044 2045 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(&TA, A, N)); 2046 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TU, &TA)); 2047 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TB, N)); 2048 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TV, N)); 2049 2050 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&U1, 1)); 2051 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&U2, 0)); 2052 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&V1, 0)); 2053 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&V2, 1)); 2054 2055 do { 2056 while ((TU.p[0] & 1) == 0) { 2057 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TU, 1)); 2058 2059 if ((U1.p[0] & 1) != 0 || (U2.p[0] & 1) != 0) { 2060 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&U1, &U1, &TB)); 2061 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&U2, &U2, &TA)); 2062 } 2063 2064 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&U1, 1)); 2065 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&U2, 1)); 2066 } 2067 2068 while ((TV.p[0] & 1) == 0) { 2069 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TV, 1)); 2070 2071 if ((V1.p[0] & 1) != 0 || (V2.p[0] & 1) != 0) { 2072 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&V1, &V1, &TB)); 2073 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&V2, &V2, &TA)); 2074 } 2075 2076 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&V1, 1)); 2077 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&V2, 1)); 2078 } 2079 2080 if (mbedtls_mpi_cmp_mpi(&TU, &TV) >= 0) { 2081 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&TU, &TU, &TV)); 2082 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&U1, &U1, &V1)); 2083 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&U2, &U2, &V2)); 2084 } else { 2085 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&TV, &TV, &TU)); 2086 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&V1, &V1, &U1)); 2087 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&V2, &V2, &U2)); 2088 } 2089 } while (mbedtls_mpi_cmp_int(&TU, 0) != 0); 2090 2091 while (mbedtls_mpi_cmp_int(&V1, 0) < 0) { 2092 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&V1, &V1, N)); 2093 } 2094 2095 while (mbedtls_mpi_cmp_mpi(&V1, N) >= 0) { 2096 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&V1, &V1, N)); 2097 } 2098 2099 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, &V1)); 2100 2101 cleanup: 2102 2103 mbedtls_mpi_free(&TA); mbedtls_mpi_free(&TU); mbedtls_mpi_free(&U1); mbedtls_mpi_free(&U2); 2104 mbedtls_mpi_free(&G); mbedtls_mpi_free(&TB); mbedtls_mpi_free(&TV); 2105 mbedtls_mpi_free(&V1); mbedtls_mpi_free(&V2); 2106 2107 return ret; 2108 } 2109 2110 #if defined(MBEDTLS_GENPRIME) 2111 2112 /* Gaps between primes, starting at 3. https://oeis.org/A001223 */ 2113 static const unsigned char small_prime_gaps[] = { 2114 2, 2, 4, 2, 4, 2, 4, 6, 2115 2, 6, 4, 2, 4, 6, 6, 2, 2116 6, 4, 2, 6, 4, 6, 8, 4, 2117 2, 4, 2, 4, 14, 4, 6, 2, 2118 10, 2, 6, 6, 4, 6, 6, 2, 2119 10, 2, 4, 2, 12, 12, 4, 2, 2120 4, 6, 2, 10, 6, 6, 6, 2, 2121 6, 4, 2, 10, 14, 4, 2, 4, 2122 14, 6, 10, 2, 4, 6, 8, 6, 2123 6, 4, 6, 8, 4, 8, 10, 2, 2124 10, 2, 6, 4, 6, 8, 4, 2, 2125 4, 12, 8, 4, 8, 4, 6, 12, 2126 2, 18, 6, 10, 6, 6, 2, 6, 2127 10, 6, 6, 2, 6, 6, 4, 2, 2128 12, 10, 2, 4, 6, 6, 2, 12, 2129 4, 6, 8, 10, 8, 10, 8, 6, 2130 6, 4, 8, 6, 4, 8, 4, 14, 2131 10, 12, 2, 10, 2, 4, 2, 10, 2132 14, 4, 2, 4, 14, 4, 2, 4, 2133 20, 4, 8, 10, 8, 4, 6, 6, 2134 14, 4, 6, 6, 8, 6, /*reaches 997*/ 2135 0 /* the last entry is effectively unused */ 2136 }; 2137 2138 /* 2139 * Small divisors test (X must be positive) 2140 * 2141 * Return values: 2142 * 0: no small factor (possible prime, more tests needed) 2143 * 1: certain prime 2144 * MBEDTLS_ERR_MPI_NOT_ACCEPTABLE: certain non-prime 2145 * other negative: error 2146 */ 2147 static int mpi_check_small_factors(const mbedtls_mpi *X) 2148 { 2149 int ret = 0; 2150 size_t i; 2151 mbedtls_mpi_uint r; 2152 unsigned p = 3; /* The first odd prime */ 2153 2154 if ((X->p[0] & 1) == 0) { 2155 return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; 2156 } 2157 2158 for (i = 0; i < sizeof(small_prime_gaps); p += small_prime_gaps[i], i++) { 2159 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_int(&r, X, p)); 2160 if (r == 0) { 2161 if (mbedtls_mpi_cmp_int(X, p) == 0) { 2162 return 1; 2163 } else { 2164 return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; 2165 } 2166 } 2167 } 2168 2169 cleanup: 2170 return ret; 2171 } 2172 2173 /* 2174 * Miller-Rabin pseudo-primality test (HAC 4.24) 2175 */ 2176 static int mpi_miller_rabin(const mbedtls_mpi *X, size_t rounds, 2177 int (*f_rng)(void *, unsigned char *, size_t), 2178 void *p_rng) 2179 { 2180 int ret, count; 2181 size_t i, j, k, s; 2182 mbedtls_mpi W, R, T, A, RR; 2183 2184 mbedtls_mpi_init_mempool(&W); mbedtls_mpi_init_mempool(&R); 2185 mbedtls_mpi_init_mempool(&T); mbedtls_mpi_init_mempool(&A); 2186 mbedtls_mpi_init_mempool(&RR); 2187 2188 /* 2189 * W = |X| - 1 2190 * R = W >> lsb( W ) 2191 */ 2192 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_int(&W, X, 1)); 2193 s = mbedtls_mpi_lsb(&W); 2194 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&R, &W)); 2195 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&R, s)); 2196 2197 for (i = 0; i < rounds; i++) { 2198 /* 2199 * pick a random A, 1 < A < |X| - 1 2200 */ 2201 count = 0; 2202 do { 2203 MBEDTLS_MPI_CHK(mbedtls_mpi_fill_random(&A, X->n * ciL, f_rng, p_rng)); 2204 2205 j = mbedtls_mpi_bitlen(&A); 2206 k = mbedtls_mpi_bitlen(&W); 2207 if (j > k) { 2208 A.p[A.n - 1] &= ((mbedtls_mpi_uint) 1 << (k - (A.n - 1) * biL - 1)) - 1; 2209 } 2210 2211 if (count++ > 300) { 2212 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; 2213 goto cleanup; 2214 } 2215 2216 } while (mbedtls_mpi_cmp_mpi(&A, &W) >= 0 || 2217 mbedtls_mpi_cmp_int(&A, 1) <= 0); 2218 2219 /* 2220 * A = A^R mod |X| 2221 */ 2222 MBEDTLS_MPI_CHK(mbedtls_mpi_exp_mod(&A, &A, &R, X, &RR)); 2223 2224 if (mbedtls_mpi_cmp_mpi(&A, &W) == 0 || 2225 mbedtls_mpi_cmp_int(&A, 1) == 0) { 2226 continue; 2227 } 2228 2229 j = 1; 2230 while (j < s && mbedtls_mpi_cmp_mpi(&A, &W) != 0) { 2231 /* 2232 * A = A * A mod |X| 2233 */ 2234 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(&T, &A, &A)); 2235 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(&A, &T, X)); 2236 2237 if (mbedtls_mpi_cmp_int(&A, 1) == 0) { 2238 break; 2239 } 2240 2241 j++; 2242 } 2243 2244 /* 2245 * not prime if A != |X| - 1 or A == 1 2246 */ 2247 if (mbedtls_mpi_cmp_mpi(&A, &W) != 0 || 2248 mbedtls_mpi_cmp_int(&A, 1) == 0) { 2249 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; 2250 break; 2251 } 2252 } 2253 2254 cleanup: 2255 mbedtls_mpi_free(&W); mbedtls_mpi_free(&R); 2256 mbedtls_mpi_free(&T); mbedtls_mpi_free(&A); 2257 mbedtls_mpi_free(&RR); 2258 2259 return ret; 2260 } 2261 2262 /* 2263 * Pseudo-primality test: small factors, then Miller-Rabin 2264 */ 2265 int mbedtls_mpi_is_prime_ext(const mbedtls_mpi *X, int rounds, 2266 int (*f_rng)(void *, unsigned char *, size_t), 2267 void *p_rng) 2268 { 2269 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2270 mbedtls_mpi XX; 2271 2272 XX.s = 1; 2273 XX.n = X->n; 2274 XX.p = X->p; 2275 2276 if (mbedtls_mpi_cmp_int(&XX, 0) == 0 || 2277 mbedtls_mpi_cmp_int(&XX, 1) == 0) { 2278 return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; 2279 } 2280 2281 if (mbedtls_mpi_cmp_int(&XX, 2) == 0) { 2282 return 0; 2283 } 2284 2285 if ((ret = mpi_check_small_factors(&XX)) != 0) { 2286 if (ret == 1) { 2287 return 0; 2288 } 2289 2290 return ret; 2291 } 2292 2293 return mpi_miller_rabin(&XX, rounds, f_rng, p_rng); 2294 } 2295 2296 /* 2297 * Prime number generation 2298 * 2299 * To generate an RSA key in a way recommended by FIPS 186-4, both primes must 2300 * be either 1024 bits or 1536 bits long, and flags must contain 2301 * MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR. 2302 */ 2303 int mbedtls_mpi_gen_prime(mbedtls_mpi *X, size_t nbits, int flags, 2304 int (*f_rng)(void *, unsigned char *, size_t), 2305 void *p_rng) 2306 { 2307 #ifdef MBEDTLS_HAVE_INT64 2308 // ceil(2^63.5) 2309 #define CEIL_MAXUINT_DIV_SQRT2 0xb504f333f9de6485ULL 2310 #else 2311 // ceil(2^31.5) 2312 #define CEIL_MAXUINT_DIV_SQRT2 0xb504f334U 2313 #endif 2314 int ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; 2315 size_t k, n; 2316 int rounds; 2317 mbedtls_mpi_uint r; 2318 mbedtls_mpi Y; 2319 2320 if (nbits < 3 || nbits > MBEDTLS_MPI_MAX_BITS) { 2321 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; 2322 } 2323 2324 mbedtls_mpi_init_mempool(&Y); 2325 2326 n = BITS_TO_LIMBS(nbits); 2327 2328 if ((flags & MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR) == 0) { 2329 /* 2330 * 2^-80 error probability, number of rounds chosen per HAC, table 4.4 2331 */ 2332 rounds = ((nbits >= 1300) ? 2 : (nbits >= 850) ? 3 : 2333 (nbits >= 650) ? 4 : (nbits >= 350) ? 8 : 2334 (nbits >= 250) ? 12 : (nbits >= 150) ? 18 : 27); 2335 } else { 2336 /* 2337 * 2^-100 error probability, number of rounds computed based on HAC, 2338 * fact 4.48 2339 */ 2340 rounds = ((nbits >= 1450) ? 4 : (nbits >= 1150) ? 5 : 2341 (nbits >= 1000) ? 6 : (nbits >= 850) ? 7 : 2342 (nbits >= 750) ? 8 : (nbits >= 500) ? 13 : 2343 (nbits >= 250) ? 28 : (nbits >= 150) ? 40 : 51); 2344 } 2345 2346 while (1) { 2347 MBEDTLS_MPI_CHK(mbedtls_mpi_fill_random(X, n * ciL, f_rng, p_rng)); 2348 /* make sure generated number is at least (nbits-1)+0.5 bits (FIPS 186-4 §B.3.3 steps 4.4, 5.5) */ 2349 if (X->p[n-1] < CEIL_MAXUINT_DIV_SQRT2) { 2350 continue; 2351 } 2352 2353 k = n * biL; 2354 if (k > nbits) { 2355 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(X, k - nbits)); 2356 } 2357 X->p[0] |= 1; 2358 2359 if ((flags & MBEDTLS_MPI_GEN_PRIME_FLAG_DH) == 0) { 2360 ret = mbedtls_mpi_is_prime_ext(X, rounds, f_rng, p_rng); 2361 2362 if (ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE) { 2363 goto cleanup; 2364 } 2365 } else { 2366 /* 2367 * A necessary condition for Y and X = 2Y + 1 to be prime 2368 * is X = 2 mod 3 (which is equivalent to Y = 2 mod 3). 2369 * Make sure it is satisfied, while keeping X = 3 mod 4 2370 */ 2371 2372 X->p[0] |= 2; 2373 2374 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_int(&r, X, 3)); 2375 if (r == 0) { 2376 MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, X, 8)); 2377 } else if (r == 1) { 2378 MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, X, 4)); 2379 } 2380 2381 /* Set Y = (X-1) / 2, which is X / 2 because X is odd */ 2382 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&Y, X)); 2383 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&Y, 1)); 2384 2385 while (1) { 2386 /* 2387 * First, check small factors for X and Y 2388 * before doing Miller-Rabin on any of them 2389 */ 2390 if ((ret = mpi_check_small_factors(X)) == 0 && 2391 (ret = mpi_check_small_factors(&Y)) == 0 && 2392 (ret = mpi_miller_rabin(X, rounds, f_rng, p_rng)) 2393 == 0 && 2394 (ret = mpi_miller_rabin(&Y, rounds, f_rng, p_rng)) 2395 == 0) { 2396 goto cleanup; 2397 } 2398 2399 if (ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE) { 2400 goto cleanup; 2401 } 2402 2403 /* 2404 * Next candidates. We want to preserve Y = (X-1) / 2 and 2405 * Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3) 2406 * so up Y by 6 and X by 12. 2407 */ 2408 MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, X, 12)); 2409 MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(&Y, &Y, 6)); 2410 } 2411 } 2412 } 2413 2414 cleanup: 2415 2416 mbedtls_mpi_free(&Y); 2417 2418 return ret; 2419 } 2420 2421 #endif /* MBEDTLS_GENPRIME */ 2422 2423 #if defined(MBEDTLS_SELF_TEST) 2424 2425 #define GCD_PAIR_COUNT 3 2426 2427 static const int gcd_pairs[GCD_PAIR_COUNT][3] = 2428 { 2429 { 693, 609, 21 }, 2430 { 1764, 868, 28 }, 2431 { 768454923, 542167814, 1 } 2432 }; 2433 2434 /* 2435 * Checkup routine 2436 */ 2437 int mbedtls_mpi_self_test(int verbose) 2438 { 2439 int ret, i; 2440 mbedtls_mpi A, E, N, X, Y, U, V; 2441 2442 mbedtls_mpi_init_mempool(&A); mbedtls_mpi_init_mempool(&E); 2443 mbedtls_mpi_init_mempool(&N); mbedtls_mpi_init_mempool(&X); 2444 mbedtls_mpi_init_mempool(&Y); mbedtls_mpi_init_mempool(&U); 2445 mbedtls_mpi_init_mempool(&V); 2446 2447 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&A, 16, 2448 "EFE021C2645FD1DC586E69184AF4A31E" \ 2449 "D5F53E93B5F123FA41680867BA110131" \ 2450 "944FE7952E2517337780CB0DB80E61AA" \ 2451 "E7C8DDC6C5C6AADEB34EB38A2F40D5E6")); 2452 2453 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&E, 16, 2454 "B2E7EFD37075B9F03FF989C7C5051C20" \ 2455 "34D2A323810251127E7BF8625A4F49A5" \ 2456 "F3E27F4DA8BD59C47D6DAABA4C8127BD" \ 2457 "5B5C25763222FEFCCFC38B832366C29E")); 2458 2459 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&N, 16, 2460 "0066A198186C18C10B2F5ED9B522752A" \ 2461 "9830B69916E535C8F047518A889A43A5" \ 2462 "94B6BED27A168D31D4A52F88925AA8F5")); 2463 2464 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(&X, &A, &N)); 2465 2466 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&U, 16, 2467 "602AB7ECA597A3D6B56FF9829A5E8B85" \ 2468 "9E857EA95A03512E2BAE7391688D264A" \ 2469 "A5663B0341DB9CCFD2C4C5F421FEC814" \ 2470 "8001B72E848A38CAE1C65F78E56ABDEF" \ 2471 "E12D3C039B8A02D6BE593F0BBBDA56F1" \ 2472 "ECF677152EF804370C1A305CAF3B5BF1" \ 2473 "30879B56C61DE584A0F53A2447A51E")); 2474 2475 if (verbose != 0) { 2476 mbedtls_printf(" MPI test #1 (mul_mpi): "); 2477 } 2478 2479 if (mbedtls_mpi_cmp_mpi(&X, &U) != 0) { 2480 if (verbose != 0) { 2481 mbedtls_printf("failed\n"); 2482 } 2483 2484 ret = 1; 2485 goto cleanup; 2486 } 2487 2488 if (verbose != 0) { 2489 mbedtls_printf("passed\n"); 2490 } 2491 2492 MBEDTLS_MPI_CHK(mbedtls_mpi_div_mpi(&X, &Y, &A, &N)); 2493 2494 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&U, 16, 2495 "256567336059E52CAE22925474705F39A94")); 2496 2497 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&V, 16, 2498 "6613F26162223DF488E9CD48CC132C7A" \ 2499 "0AC93C701B001B092E4E5B9F73BCD27B" \ 2500 "9EE50D0657C77F374E903CDFA4C642")); 2501 2502 if (verbose != 0) { 2503 mbedtls_printf(" MPI test #2 (div_mpi): "); 2504 } 2505 2506 if (mbedtls_mpi_cmp_mpi(&X, &U) != 0 || 2507 mbedtls_mpi_cmp_mpi(&Y, &V) != 0) { 2508 if (verbose != 0) { 2509 mbedtls_printf("failed\n"); 2510 } 2511 2512 ret = 1; 2513 goto cleanup; 2514 } 2515 2516 if (verbose != 0) { 2517 mbedtls_printf("passed\n"); 2518 } 2519 2520 MBEDTLS_MPI_CHK(mbedtls_mpi_exp_mod(&X, &A, &E, &N, NULL)); 2521 2522 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&U, 16, 2523 "36E139AEA55215609D2816998ED020BB" \ 2524 "BD96C37890F65171D948E9BC7CBAA4D9" \ 2525 "325D24D6A3C12710F10A09FA08AB87")); 2526 2527 if (verbose != 0) { 2528 mbedtls_printf(" MPI test #3 (exp_mod): "); 2529 } 2530 2531 if (mbedtls_mpi_cmp_mpi(&X, &U) != 0) { 2532 if (verbose != 0) { 2533 mbedtls_printf("failed\n"); 2534 } 2535 2536 ret = 1; 2537 goto cleanup; 2538 } 2539 2540 if (verbose != 0) { 2541 mbedtls_printf("passed\n"); 2542 } 2543 2544 MBEDTLS_MPI_CHK(mbedtls_mpi_inv_mod(&X, &A, &N)); 2545 2546 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&U, 16, 2547 "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \ 2548 "C3DBA76456363A10869622EAC2DD84EC" \ 2549 "C5B8A74DAC4D09E03B5E0BE779F2DF61")); 2550 2551 if (verbose != 0) { 2552 mbedtls_printf(" MPI test #4 (inv_mod): "); 2553 } 2554 2555 if (mbedtls_mpi_cmp_mpi(&X, &U) != 0) { 2556 if (verbose != 0) { 2557 mbedtls_printf("failed\n"); 2558 } 2559 2560 ret = 1; 2561 goto cleanup; 2562 } 2563 2564 if (verbose != 0) { 2565 mbedtls_printf("passed\n"); 2566 } 2567 2568 if (verbose != 0) { 2569 mbedtls_printf(" MPI test #5 (simple gcd): "); 2570 } 2571 2572 for (i = 0; i < GCD_PAIR_COUNT; i++) { 2573 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&X, gcd_pairs[i][0])); 2574 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&Y, gcd_pairs[i][1])); 2575 2576 MBEDTLS_MPI_CHK(mbedtls_mpi_gcd(&A, &X, &Y)); 2577 2578 if (mbedtls_mpi_cmp_int(&A, gcd_pairs[i][2]) != 0) { 2579 if (verbose != 0) { 2580 mbedtls_printf("failed at %d\n", i); 2581 } 2582 2583 ret = 1; 2584 goto cleanup; 2585 } 2586 } 2587 2588 if (verbose != 0) { 2589 mbedtls_printf("passed\n"); 2590 } 2591 2592 cleanup: 2593 2594 if (ret != 0 && verbose != 0) { 2595 mbedtls_printf("Unexpected error, return code = %08X\n", (unsigned int) ret); 2596 } 2597 2598 mbedtls_mpi_free(&A); mbedtls_mpi_free(&E); mbedtls_mpi_free(&N); mbedtls_mpi_free(&X); 2599 mbedtls_mpi_free(&Y); mbedtls_mpi_free(&U); mbedtls_mpi_free(&V); 2600 2601 if (verbose != 0) { 2602 mbedtls_printf("\n"); 2603 } 2604 2605 return ret; 2606 } 2607 2608 #endif /* MBEDTLS_SELF_TEST */ 2609 2610 #endif /* MBEDTLS_BIGNUM_C */ 2611