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 p = (mbedtls_mpi_uint *)mbedtls_calloc(i, ciL); 311 if (p == NULL) 312 return MBEDTLS_ERR_MPI_ALLOC_FAILED; 313 } 314 315 if (X->p != NULL) { 316 memcpy(p, X->p, i * ciL); 317 318 if (X->use_mempool) { 319 mbedtls_mpi_zeroize(X->p, X->n); 320 mempool_free(mbedtls_mpi_mempool, X->p); 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 #if defined(__has_builtin) 485 #if (MBEDTLS_MPI_UINT_MAX == UINT_MAX) && __has_builtin(__builtin_ctz) 486 #define mbedtls_mpi_uint_ctz __builtin_ctz 487 #elif (MBEDTLS_MPI_UINT_MAX == ULONG_MAX) && __has_builtin(__builtin_ctzl) 488 #define mbedtls_mpi_uint_ctz __builtin_ctzl 489 #elif (MBEDTLS_MPI_UINT_MAX == ULLONG_MAX) && __has_builtin(__builtin_ctzll) 490 #define mbedtls_mpi_uint_ctz __builtin_ctzll 491 #endif 492 #endif 493 494 #if !defined(mbedtls_mpi_uint_ctz) 495 static size_t mbedtls_mpi_uint_ctz(mbedtls_mpi_uint x) 496 { 497 size_t count = 0; 498 mbedtls_ct_condition_t done = MBEDTLS_CT_FALSE; 499 500 for (size_t i = 0; i < biL; i++) { 501 mbedtls_ct_condition_t non_zero = mbedtls_ct_bool((x >> i) & 1); 502 done = mbedtls_ct_bool_or(done, non_zero); 503 count = mbedtls_ct_size_if(done, count, i + 1); 504 } 505 506 return count; 507 } 508 #endif 509 510 /* 511 * Return the number of less significant zero-bits 512 */ 513 size_t mbedtls_mpi_lsb(const mbedtls_mpi *X) 514 { 515 size_t i; 516 517 for (i = 0; i < X->n; i++) { 518 if (X->p[i] != 0) { 519 return i * biL + mbedtls_mpi_uint_ctz(X->p[i]); 520 } 521 } 522 523 return 0; 524 } 525 526 /* 527 * Return the number of bits 528 */ 529 size_t mbedtls_mpi_bitlen(const mbedtls_mpi *X) 530 { 531 return mbedtls_mpi_core_bitlen(X->p, X->n); 532 } 533 534 /* 535 * Return the total size in bytes 536 */ 537 size_t mbedtls_mpi_size(const mbedtls_mpi *X) 538 { 539 return (mbedtls_mpi_bitlen(X) + 7) >> 3; 540 } 541 542 /* 543 * Convert an ASCII character to digit value 544 */ 545 static int mpi_get_digit(mbedtls_mpi_uint *d, int radix, char c) 546 { 547 *d = 255; 548 549 if (c >= 0x30 && c <= 0x39) { 550 *d = c - 0x30; 551 } 552 if (c >= 0x41 && c <= 0x46) { 553 *d = c - 0x37; 554 } 555 if (c >= 0x61 && c <= 0x66) { 556 *d = c - 0x57; 557 } 558 559 if (*d >= (mbedtls_mpi_uint) radix) { 560 return MBEDTLS_ERR_MPI_INVALID_CHARACTER; 561 } 562 563 return 0; 564 } 565 566 /* 567 * Import from an ASCII string 568 */ 569 int mbedtls_mpi_read_string(mbedtls_mpi *X, int radix, const char *s) 570 { 571 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 572 size_t i, j, slen, n; 573 int sign = 1; 574 mbedtls_mpi_uint d; 575 mbedtls_mpi T; 576 577 if (radix < 2 || radix > 16) { 578 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; 579 } 580 581 mbedtls_mpi_init_mempool(&T); 582 583 if (s[0] == 0) { 584 mbedtls_mpi_free(X); 585 return 0; 586 } 587 588 if (s[0] == '-') { 589 ++s; 590 sign = -1; 591 } 592 593 slen = strlen(s); 594 595 if (radix == 16) { 596 if (slen > SIZE_MAX >> 2) { 597 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; 598 } 599 600 n = BITS_TO_LIMBS(slen << 2); 601 602 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, n)); 603 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 0)); 604 605 for (i = slen, j = 0; i > 0; i--, j++) { 606 MBEDTLS_MPI_CHK(mpi_get_digit(&d, radix, s[i - 1])); 607 X->p[j / (2 * ciL)] |= d << ((j % (2 * ciL)) << 2); 608 } 609 } else { 610 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 0)); 611 612 for (i = 0; i < slen; i++) { 613 MBEDTLS_MPI_CHK(mpi_get_digit(&d, radix, s[i])); 614 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int(&T, X, radix)); 615 MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, &T, d)); 616 } 617 } 618 619 if (sign < 0 && mbedtls_mpi_bitlen(X) != 0) { 620 X->s = -1; 621 } 622 623 cleanup: 624 625 mbedtls_mpi_free(&T); 626 627 return ret; 628 } 629 630 /* 631 * Helper to write the digits high-order first. 632 */ 633 static int mpi_write_hlp(mbedtls_mpi *X, int radix, 634 char **p, const size_t buflen) 635 { 636 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 637 mbedtls_mpi_uint r; 638 size_t length = 0; 639 char *p_end = *p + buflen; 640 641 do { 642 if (length >= buflen) { 643 return MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL; 644 } 645 646 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_int(&r, X, radix)); 647 MBEDTLS_MPI_CHK(mbedtls_mpi_div_int(X, NULL, X, radix)); 648 /* 649 * Write the residue in the current position, as an ASCII character. 650 */ 651 if (r < 0xA) { 652 *(--p_end) = (char) ('0' + r); 653 } else { 654 *(--p_end) = (char) ('A' + (r - 0xA)); 655 } 656 657 length++; 658 } while (mbedtls_mpi_cmp_int(X, 0) != 0); 659 660 memmove(*p, p_end, length); 661 *p += length; 662 663 cleanup: 664 665 return ret; 666 } 667 668 /* 669 * Export into an ASCII string 670 */ 671 int mbedtls_mpi_write_string(const mbedtls_mpi *X, int radix, 672 char *buf, size_t buflen, size_t *olen) 673 { 674 int ret = 0; 675 size_t n; 676 char *p; 677 mbedtls_mpi T; 678 679 if (radix < 2 || radix > 16) { 680 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; 681 } 682 683 n = mbedtls_mpi_bitlen(X); /* Number of bits necessary to present `n`. */ 684 if (radix >= 4) { 685 n >>= 1; /* Number of 4-adic digits necessary to present 686 * `n`. If radix > 4, this might be a strict 687 * overapproximation of the number of 688 * radix-adic digits needed to present `n`. */ 689 } 690 if (radix >= 16) { 691 n >>= 1; /* Number of hexadecimal digits necessary to 692 * present `n`. */ 693 694 } 695 n += 1; /* Terminating null byte */ 696 n += 1; /* Compensate for the divisions above, which round down `n` 697 * in case it's not even. */ 698 n += 1; /* Potential '-'-sign. */ 699 n += (n & 1); /* Make n even to have enough space for hexadecimal writing, 700 * which always uses an even number of hex-digits. */ 701 702 if (buflen < n) { 703 *olen = n; 704 return MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL; 705 } 706 707 p = buf; 708 mbedtls_mpi_init_mempool(&T); 709 710 if (X->s == -1) { 711 *p++ = '-'; 712 buflen--; 713 } 714 715 if (radix == 16) { 716 int c; 717 size_t i, j, k; 718 719 for (i = X->n, k = 0; i > 0; i--) { 720 for (j = ciL; j > 0; j--) { 721 c = (X->p[i - 1] >> ((j - 1) << 3)) & 0xFF; 722 723 if (c == 0 && k == 0 && (i + j) != 2) { 724 continue; 725 } 726 727 *(p++) = "0123456789ABCDEF" [c / 16]; 728 *(p++) = "0123456789ABCDEF" [c % 16]; 729 k = 1; 730 } 731 } 732 } else { 733 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&T, X)); 734 735 if (T.s == -1) { 736 T.s = 1; 737 } 738 739 MBEDTLS_MPI_CHK(mpi_write_hlp(&T, radix, &p, buflen)); 740 } 741 742 *p++ = '\0'; 743 *olen = (size_t) (p - buf); 744 745 cleanup: 746 747 mbedtls_mpi_free(&T); 748 749 return ret; 750 } 751 752 #if defined(MBEDTLS_FS_IO) 753 /* 754 * Read X from an opened file 755 */ 756 int mbedtls_mpi_read_file(mbedtls_mpi *X, int radix, FILE *fin) 757 { 758 mbedtls_mpi_uint d; 759 size_t slen; 760 char *p; 761 /* 762 * Buffer should have space for (short) label and decimal formatted MPI, 763 * newline characters and '\0' 764 */ 765 char s[MBEDTLS_MPI_RW_BUFFER_SIZE]; 766 767 if (radix < 2 || radix > 16) { 768 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; 769 } 770 771 memset(s, 0, sizeof(s)); 772 if (fgets(s, sizeof(s) - 1, fin) == NULL) { 773 return MBEDTLS_ERR_MPI_FILE_IO_ERROR; 774 } 775 776 slen = strlen(s); 777 if (slen == sizeof(s) - 2) { 778 return MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL; 779 } 780 781 if (slen > 0 && s[slen - 1] == '\n') { 782 slen--; s[slen] = '\0'; 783 } 784 if (slen > 0 && s[slen - 1] == '\r') { 785 slen--; s[slen] = '\0'; 786 } 787 788 p = s + slen; 789 while (p-- > s) { 790 if (mpi_get_digit(&d, radix, *p) != 0) { 791 break; 792 } 793 } 794 795 return mbedtls_mpi_read_string(X, radix, p + 1); 796 } 797 798 /* 799 * Write X into an opened file (or stdout if fout == NULL) 800 */ 801 int mbedtls_mpi_write_file(const char *p, const mbedtls_mpi *X, int radix, FILE *fout) 802 { 803 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 804 size_t n, slen, plen; 805 /* 806 * Buffer should have space for (short) label and decimal formatted MPI, 807 * newline characters and '\0' 808 */ 809 char s[MBEDTLS_MPI_RW_BUFFER_SIZE]; 810 811 if (radix < 2 || radix > 16) { 812 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; 813 } 814 815 memset(s, 0, sizeof(s)); 816 817 MBEDTLS_MPI_CHK(mbedtls_mpi_write_string(X, radix, s, sizeof(s) - 2, &n)); 818 819 if (p == NULL) { 820 p = ""; 821 } 822 823 plen = strlen(p); 824 slen = strlen(s); 825 s[slen++] = '\r'; 826 s[slen++] = '\n'; 827 828 if (fout != NULL) { 829 if (fwrite(p, 1, plen, fout) != plen || 830 fwrite(s, 1, slen, fout) != slen) { 831 return MBEDTLS_ERR_MPI_FILE_IO_ERROR; 832 } 833 } else { 834 mbedtls_printf("%s%s", p, s); 835 } 836 837 cleanup: 838 839 return ret; 840 } 841 #endif /* MBEDTLS_FS_IO */ 842 843 /* 844 * Import X from unsigned binary data, little endian 845 * 846 * This function is guaranteed to return an MPI with exactly the necessary 847 * number of limbs (in particular, it does not skip 0s in the input). 848 */ 849 int mbedtls_mpi_read_binary_le(mbedtls_mpi *X, 850 const unsigned char *buf, size_t buflen) 851 { 852 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 853 const size_t limbs = CHARS_TO_LIMBS(buflen); 854 855 /* Ensure that target MPI has exactly the necessary number of limbs */ 856 MBEDTLS_MPI_CHK(mbedtls_mpi_resize_clear(X, limbs)); 857 858 MBEDTLS_MPI_CHK(mbedtls_mpi_core_read_le(X->p, X->n, buf, buflen)); 859 860 cleanup: 861 862 /* 863 * This function is also used to import keys. However, wiping the buffers 864 * upon failure is not necessary because failure only can happen before any 865 * input is copied. 866 */ 867 return ret; 868 } 869 870 /* 871 * Import X from unsigned binary data, big endian 872 * 873 * This function is guaranteed to return an MPI with exactly the necessary 874 * number of limbs (in particular, it does not skip 0s in the input). 875 */ 876 int mbedtls_mpi_read_binary(mbedtls_mpi *X, const unsigned char *buf, size_t buflen) 877 { 878 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 879 const size_t limbs = CHARS_TO_LIMBS(buflen); 880 881 /* Ensure that target MPI has exactly the necessary number of limbs */ 882 MBEDTLS_MPI_CHK(mbedtls_mpi_resize_clear(X, limbs)); 883 884 MBEDTLS_MPI_CHK(mbedtls_mpi_core_read_be(X->p, X->n, buf, buflen)); 885 886 cleanup: 887 888 /* 889 * This function is also used to import keys. However, wiping the buffers 890 * upon failure is not necessary because failure only can happen before any 891 * input is copied. 892 */ 893 return ret; 894 } 895 896 /* 897 * Export X into unsigned binary data, little endian 898 */ 899 int mbedtls_mpi_write_binary_le(const mbedtls_mpi *X, 900 unsigned char *buf, size_t buflen) 901 { 902 return mbedtls_mpi_core_write_le(X->p, X->n, buf, buflen); 903 } 904 905 /* 906 * Export X into unsigned binary data, big endian 907 */ 908 int mbedtls_mpi_write_binary(const mbedtls_mpi *X, 909 unsigned char *buf, size_t buflen) 910 { 911 return mbedtls_mpi_core_write_be(X->p, X->n, buf, buflen); 912 } 913 914 /* 915 * Left-shift: X <<= count 916 */ 917 int mbedtls_mpi_shift_l(mbedtls_mpi *X, size_t count) 918 { 919 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 920 size_t i; 921 922 i = mbedtls_mpi_bitlen(X) + count; 923 924 if (X->n * biL < i) { 925 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, BITS_TO_LIMBS(i))); 926 } 927 928 ret = 0; 929 930 mbedtls_mpi_core_shift_l(X->p, X->n, count); 931 cleanup: 932 933 return ret; 934 } 935 936 /* 937 * Right-shift: X >>= count 938 */ 939 int mbedtls_mpi_shift_r(mbedtls_mpi *X, size_t count) 940 { 941 if (X->n != 0) { 942 mbedtls_mpi_core_shift_r(X->p, X->n, count); 943 } 944 return 0; 945 } 946 947 /* 948 * Compare unsigned values 949 */ 950 int mbedtls_mpi_cmp_abs(const mbedtls_mpi *X, const mbedtls_mpi *Y) 951 { 952 size_t i, j; 953 954 for (i = X->n; i > 0; i--) { 955 if (X->p[i - 1] != 0) { 956 break; 957 } 958 } 959 960 for (j = Y->n; j > 0; j--) { 961 if (Y->p[j - 1] != 0) { 962 break; 963 } 964 } 965 966 /* If i == j == 0, i.e. abs(X) == abs(Y), 967 * we end up returning 0 at the end of the function. */ 968 969 if (i > j) { 970 return 1; 971 } 972 if (j > i) { 973 return -1; 974 } 975 976 for (; i > 0; i--) { 977 if (X->p[i - 1] > Y->p[i - 1]) { 978 return 1; 979 } 980 if (X->p[i - 1] < Y->p[i - 1]) { 981 return -1; 982 } 983 } 984 985 return 0; 986 } 987 988 /* 989 * Compare signed values 990 */ 991 int mbedtls_mpi_cmp_mpi(const mbedtls_mpi *X, const mbedtls_mpi *Y) 992 { 993 size_t i, j; 994 995 for (i = X->n; i > 0; i--) { 996 if (X->p[i - 1] != 0) { 997 break; 998 } 999 } 1000 1001 for (j = Y->n; j > 0; j--) { 1002 if (Y->p[j - 1] != 0) { 1003 break; 1004 } 1005 } 1006 1007 if (i == 0 && j == 0) { 1008 return 0; 1009 } 1010 1011 if (i > j) { 1012 return X->s; 1013 } 1014 if (j > i) { 1015 return -Y->s; 1016 } 1017 1018 if (X->s > 0 && Y->s < 0) { 1019 return 1; 1020 } 1021 if (Y->s > 0 && X->s < 0) { 1022 return -1; 1023 } 1024 1025 for (; i > 0; i--) { 1026 if (X->p[i - 1] > Y->p[i - 1]) { 1027 return X->s; 1028 } 1029 if (X->p[i - 1] < Y->p[i - 1]) { 1030 return -X->s; 1031 } 1032 } 1033 1034 return 0; 1035 } 1036 1037 /* 1038 * Compare signed values 1039 */ 1040 int mbedtls_mpi_cmp_int(const mbedtls_mpi *X, mbedtls_mpi_sint z) 1041 { 1042 mbedtls_mpi Y; 1043 mbedtls_mpi_uint p[1]; 1044 1045 *p = mpi_sint_abs(z); 1046 Y.s = TO_SIGN(z); 1047 Y.n = 1; 1048 Y.p = p; 1049 1050 return mbedtls_mpi_cmp_mpi(X, &Y); 1051 } 1052 1053 /* 1054 * Unsigned addition: X = |A| + |B| (HAC 14.7) 1055 */ 1056 int mbedtls_mpi_add_abs(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B) 1057 { 1058 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1059 size_t j; 1060 mbedtls_mpi_uint *p; 1061 mbedtls_mpi_uint c; 1062 1063 if (X == B) { 1064 const mbedtls_mpi *T = A; A = X; B = T; 1065 } 1066 1067 if (X != A) { 1068 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, A)); 1069 } 1070 1071 /* 1072 * X must always be positive as a result of unsigned additions. 1073 */ 1074 X->s = 1; 1075 1076 for (j = B->n; j > 0; j--) { 1077 if (B->p[j - 1] != 0) { 1078 break; 1079 } 1080 } 1081 1082 /* Exit early to avoid undefined behavior on NULL+0 when X->n == 0 1083 * and B is 0 (of any size). */ 1084 if (j == 0) { 1085 return 0; 1086 } 1087 1088 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, j)); 1089 1090 /* j is the number of non-zero limbs of B. Add those to X. */ 1091 1092 p = X->p; 1093 1094 c = mbedtls_mpi_core_add(p, p, B->p, j); 1095 1096 p += j; 1097 1098 /* Now propagate any carry */ 1099 1100 while (c != 0) { 1101 if (j >= X->n) { 1102 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, j + 1)); 1103 p = X->p + j; 1104 } 1105 1106 *p += c; c = (*p < c); j++; p++; 1107 } 1108 1109 cleanup: 1110 1111 return ret; 1112 } 1113 1114 /* 1115 * Unsigned subtraction: X = |A| - |B| (HAC 14.9, 14.10) 1116 */ 1117 int mbedtls_mpi_sub_abs(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B) 1118 { 1119 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1120 size_t n; 1121 mbedtls_mpi_uint carry; 1122 1123 for (n = B->n; n > 0; n--) { 1124 if (B->p[n - 1] != 0) { 1125 break; 1126 } 1127 } 1128 if (n > A->n) { 1129 /* B >= (2^ciL)^n > A */ 1130 ret = MBEDTLS_ERR_MPI_NEGATIVE_VALUE; 1131 goto cleanup; 1132 } 1133 1134 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, A->n)); 1135 1136 /* Set the high limbs of X to match A. Don't touch the lower limbs 1137 * because X might be aliased to B, and we must not overwrite the 1138 * significant digits of B. */ 1139 if (A->n > n && A != X) { 1140 memcpy(X->p + n, A->p + n, (A->n - n) * ciL); 1141 } 1142 if (X->n > A->n) { 1143 memset(X->p + A->n, 0, (X->n - A->n) * ciL); 1144 } 1145 1146 carry = mbedtls_mpi_core_sub(X->p, A->p, B->p, n); 1147 if (carry != 0) { 1148 /* Propagate the carry through the rest of X. */ 1149 carry = mbedtls_mpi_core_sub_int(X->p + n, X->p + n, carry, X->n - n); 1150 1151 /* If we have further carry/borrow, the result is negative. */ 1152 if (carry != 0) { 1153 ret = MBEDTLS_ERR_MPI_NEGATIVE_VALUE; 1154 goto cleanup; 1155 } 1156 } 1157 1158 /* X should always be positive as a result of unsigned subtractions. */ 1159 X->s = 1; 1160 1161 cleanup: 1162 return ret; 1163 } 1164 1165 /* Common function for signed addition and subtraction. 1166 * Calculate A + B * flip_B where flip_B is 1 or -1. 1167 */ 1168 static int add_sub_mpi(mbedtls_mpi *X, 1169 const mbedtls_mpi *A, const mbedtls_mpi *B, 1170 int flip_B) 1171 { 1172 int ret, s; 1173 1174 s = A->s; 1175 if (A->s * B->s * flip_B < 0) { 1176 int cmp = mbedtls_mpi_cmp_abs(A, B); 1177 if (cmp >= 0) { 1178 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(X, A, B)); 1179 /* If |A| = |B|, the result is 0 and we must set the sign bit 1180 * to +1 regardless of which of A or B was negative. Otherwise, 1181 * since |A| > |B|, the sign is the sign of A. */ 1182 X->s = cmp == 0 ? 1 : s; 1183 } else { 1184 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(X, B, A)); 1185 /* Since |A| < |B|, the sign is the opposite of A. */ 1186 X->s = -s; 1187 } 1188 } else { 1189 MBEDTLS_MPI_CHK(mbedtls_mpi_add_abs(X, A, B)); 1190 X->s = s; 1191 } 1192 1193 cleanup: 1194 1195 return ret; 1196 } 1197 1198 /* 1199 * Signed addition: X = A + B 1200 */ 1201 int mbedtls_mpi_add_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B) 1202 { 1203 return add_sub_mpi(X, A, B, 1); 1204 } 1205 1206 /* 1207 * Signed subtraction: X = A - B 1208 */ 1209 int mbedtls_mpi_sub_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B) 1210 { 1211 return add_sub_mpi(X, A, B, -1); 1212 } 1213 1214 /* 1215 * Signed addition: X = A + b 1216 */ 1217 int mbedtls_mpi_add_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b) 1218 { 1219 mbedtls_mpi B; 1220 mbedtls_mpi_uint p[1]; 1221 1222 p[0] = mpi_sint_abs(b); 1223 B.s = TO_SIGN(b); 1224 B.n = 1; 1225 B.p = p; 1226 1227 return mbedtls_mpi_add_mpi(X, A, &B); 1228 } 1229 1230 /* 1231 * Signed subtraction: X = A - b 1232 */ 1233 int mbedtls_mpi_sub_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b) 1234 { 1235 mbedtls_mpi B; 1236 mbedtls_mpi_uint p[1]; 1237 1238 p[0] = mpi_sint_abs(b); 1239 B.s = TO_SIGN(b); 1240 B.n = 1; 1241 B.p = p; 1242 1243 return mbedtls_mpi_sub_mpi(X, A, &B); 1244 } 1245 1246 /* 1247 * Baseline multiplication: X = A * B (HAC 14.12) 1248 */ 1249 int mbedtls_mpi_mul_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B) 1250 { 1251 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1252 size_t i, j; 1253 mbedtls_mpi TA, TB; 1254 int result_is_zero = 0; 1255 1256 mbedtls_mpi_init_mempool(&TA); 1257 mbedtls_mpi_init_mempool(&TB); 1258 1259 if (X == A) { 1260 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TA, A)); A = &TA; 1261 } 1262 if (X == B) { 1263 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TB, B)); B = &TB; 1264 } 1265 1266 for (i = A->n; i > 0; i--) { 1267 if (A->p[i - 1] != 0) { 1268 break; 1269 } 1270 } 1271 if (i == 0) { 1272 result_is_zero = 1; 1273 } 1274 1275 for (j = B->n; j > 0; j--) { 1276 if (B->p[j - 1] != 0) { 1277 break; 1278 } 1279 } 1280 if (j == 0) { 1281 result_is_zero = 1; 1282 } 1283 1284 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, i + j)); 1285 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 0)); 1286 1287 mbedtls_mpi_core_mul(X->p, A->p, i, B->p, j); 1288 1289 /* If the result is 0, we don't shortcut the operation, which reduces 1290 * but does not eliminate side channels leaking the zero-ness. We do 1291 * need to take care to set the sign bit properly since the library does 1292 * not fully support an MPI object with a value of 0 and s == -1. */ 1293 if (result_is_zero) { 1294 X->s = 1; 1295 } else { 1296 X->s = A->s * B->s; 1297 } 1298 1299 cleanup: 1300 1301 mbedtls_mpi_free(&TB); mbedtls_mpi_free(&TA); 1302 1303 return ret; 1304 } 1305 1306 /* 1307 * Baseline multiplication: X = A * b 1308 */ 1309 int mbedtls_mpi_mul_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b) 1310 { 1311 size_t n = A->n; 1312 while (n > 0 && A->p[n - 1] == 0) { 1313 --n; 1314 } 1315 1316 /* The general method below doesn't work if b==0. */ 1317 if (b == 0 || n == 0) { 1318 return mbedtls_mpi_lset(X, 0); 1319 } 1320 1321 /* Calculate A*b as A + A*(b-1) to take advantage of mbedtls_mpi_core_mla */ 1322 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1323 /* In general, A * b requires 1 limb more than b. If 1324 * A->p[n - 1] * b / b == A->p[n - 1], then A * b fits in the same 1325 * number of limbs as A and the call to grow() is not required since 1326 * copy() will take care of the growth if needed. However, experimentally, 1327 * making the call to grow() unconditional causes slightly fewer 1328 * calls to calloc() in ECP code, presumably because it reuses the 1329 * same mpi for a while and this way the mpi is more likely to directly 1330 * grow to its final size. 1331 * 1332 * Note that calculating A*b as 0 + A*b doesn't work as-is because 1333 * A,X can be the same. */ 1334 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, n + 1)); 1335 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, A)); 1336 mbedtls_mpi_core_mla(X->p, X->n, A->p, n, b - 1); 1337 1338 cleanup: 1339 return ret; 1340 } 1341 1342 /* 1343 * Unsigned integer divide - double mbedtls_mpi_uint dividend, u1/u0, and 1344 * mbedtls_mpi_uint divisor, d 1345 */ 1346 static mbedtls_mpi_uint mbedtls_int_div_int(mbedtls_mpi_uint u1, 1347 mbedtls_mpi_uint u0, 1348 mbedtls_mpi_uint d, 1349 mbedtls_mpi_uint *r) 1350 { 1351 #if defined(MBEDTLS_HAVE_UDBL) 1352 mbedtls_t_udbl dividend, quotient; 1353 #else 1354 const mbedtls_mpi_uint radix = (mbedtls_mpi_uint) 1 << biH; 1355 const mbedtls_mpi_uint uint_halfword_mask = ((mbedtls_mpi_uint) 1 << biH) - 1; 1356 mbedtls_mpi_uint d0, d1, q0, q1, rAX, r0, quotient; 1357 mbedtls_mpi_uint u0_msw, u0_lsw; 1358 size_t s; 1359 #endif 1360 1361 /* 1362 * Check for overflow 1363 */ 1364 if (0 == d || u1 >= d) { 1365 if (r != NULL) { 1366 *r = ~(mbedtls_mpi_uint) 0u; 1367 } 1368 1369 return ~(mbedtls_mpi_uint) 0u; 1370 } 1371 1372 #if defined(MBEDTLS_HAVE_UDBL) 1373 dividend = (mbedtls_t_udbl) u1 << biL; 1374 dividend |= (mbedtls_t_udbl) u0; 1375 quotient = dividend / d; 1376 if (quotient > ((mbedtls_t_udbl) 1 << biL) - 1) { 1377 quotient = ((mbedtls_t_udbl) 1 << biL) - 1; 1378 } 1379 1380 if (r != NULL) { 1381 *r = (mbedtls_mpi_uint) (dividend - (quotient * d)); 1382 } 1383 1384 return (mbedtls_mpi_uint) quotient; 1385 #else 1386 1387 /* 1388 * Algorithm D, Section 4.3.1 - The Art of Computer Programming 1389 * Vol. 2 - Seminumerical Algorithms, Knuth 1390 */ 1391 1392 /* 1393 * Normalize the divisor, d, and dividend, u0, u1 1394 */ 1395 s = mbedtls_mpi_core_clz(d); 1396 d = d << s; 1397 1398 u1 = u1 << s; 1399 u1 |= (u0 >> (biL - s)) & (-(mbedtls_mpi_sint) s >> (biL - 1)); 1400 u0 = u0 << s; 1401 1402 d1 = d >> biH; 1403 d0 = d & uint_halfword_mask; 1404 1405 u0_msw = u0 >> biH; 1406 u0_lsw = u0 & uint_halfword_mask; 1407 1408 /* 1409 * Find the first quotient and remainder 1410 */ 1411 q1 = u1 / d1; 1412 r0 = u1 - d1 * q1; 1413 1414 while (q1 >= radix || (q1 * d0 > radix * r0 + u0_msw)) { 1415 q1 -= 1; 1416 r0 += d1; 1417 1418 if (r0 >= radix) { 1419 break; 1420 } 1421 } 1422 1423 rAX = (u1 * radix) + (u0_msw - q1 * d); 1424 q0 = rAX / d1; 1425 r0 = rAX - q0 * d1; 1426 1427 while (q0 >= radix || (q0 * d0 > radix * r0 + u0_lsw)) { 1428 q0 -= 1; 1429 r0 += d1; 1430 1431 if (r0 >= radix) { 1432 break; 1433 } 1434 } 1435 1436 if (r != NULL) { 1437 *r = (rAX * radix + u0_lsw - q0 * d) >> s; 1438 } 1439 1440 quotient = q1 * radix + q0; 1441 1442 return quotient; 1443 #endif 1444 } 1445 1446 /* 1447 * Division by mbedtls_mpi: A = Q * B + R (HAC 14.20) 1448 */ 1449 int mbedtls_mpi_div_mpi(mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A, 1450 const mbedtls_mpi *B) 1451 { 1452 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1453 size_t i, n, t, k; 1454 mbedtls_mpi X, Y, Z, T1, T2; 1455 mbedtls_mpi_uint TP2[3]; 1456 1457 if (mbedtls_mpi_cmp_int(B, 0) == 0) { 1458 return MBEDTLS_ERR_MPI_DIVISION_BY_ZERO; 1459 } 1460 1461 mbedtls_mpi_init_mempool(&X); mbedtls_mpi_init_mempool(&Y); 1462 mbedtls_mpi_init_mempool(&Z); mbedtls_mpi_init_mempool(&T1); 1463 /* 1464 * Avoid dynamic memory allocations for constant-size T2. 1465 * 1466 * T2 is used for comparison only and the 3 limbs are assigned explicitly, 1467 * so nobody increase the size of the MPI and we're safe to use an on-stack 1468 * buffer. 1469 */ 1470 T2.s = 1; 1471 T2.n = sizeof(TP2) / sizeof(*TP2); 1472 T2.p = TP2; 1473 1474 if (mbedtls_mpi_cmp_abs(A, B) < 0) { 1475 if (Q != NULL) { 1476 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(Q, 0)); 1477 } 1478 if (R != NULL) { 1479 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(R, A)); 1480 } 1481 return 0; 1482 } 1483 1484 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&X, A)); 1485 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&Y, B)); 1486 X.s = Y.s = 1; 1487 1488 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&Z, A->n + 2)); 1489 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&Z, 0)); 1490 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&T1, A->n + 2)); 1491 1492 k = mbedtls_mpi_bitlen(&Y) % biL; 1493 if (k < biL - 1) { 1494 k = biL - 1 - k; 1495 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&X, k)); 1496 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&Y, k)); 1497 } else { 1498 k = 0; 1499 } 1500 1501 n = X.n - 1; 1502 t = Y.n - 1; 1503 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&Y, biL * (n - t))); 1504 1505 while (mbedtls_mpi_cmp_mpi(&X, &Y) >= 0) { 1506 Z.p[n - t]++; 1507 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&X, &X, &Y)); 1508 } 1509 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&Y, biL * (n - t))); 1510 1511 for (i = n; i > t; i--) { 1512 if (X.p[i] >= Y.p[t]) { 1513 Z.p[i - t - 1] = ~(mbedtls_mpi_uint) 0u; 1514 } else { 1515 Z.p[i - t - 1] = mbedtls_int_div_int(X.p[i], X.p[i - 1], 1516 Y.p[t], NULL); 1517 } 1518 1519 T2.p[0] = (i < 2) ? 0 : X.p[i - 2]; 1520 T2.p[1] = (i < 1) ? 0 : X.p[i - 1]; 1521 T2.p[2] = X.p[i]; 1522 1523 Z.p[i - t - 1]++; 1524 do { 1525 Z.p[i - t - 1]--; 1526 1527 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&T1, 0)); 1528 T1.p[0] = (t < 1) ? 0 : Y.p[t - 1]; 1529 T1.p[1] = Y.p[t]; 1530 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int(&T1, &T1, Z.p[i - t - 1])); 1531 } while (mbedtls_mpi_cmp_mpi(&T1, &T2) > 0); 1532 1533 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int(&T1, &Y, Z.p[i - t - 1])); 1534 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&T1, biL * (i - t - 1))); 1535 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&X, &X, &T1)); 1536 1537 if (mbedtls_mpi_cmp_int(&X, 0) < 0) { 1538 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&T1, &Y)); 1539 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&T1, biL * (i - t - 1))); 1540 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&X, &X, &T1)); 1541 Z.p[i - t - 1]--; 1542 } 1543 } 1544 1545 if (Q != NULL) { 1546 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(Q, &Z)); 1547 Q->s = A->s * B->s; 1548 } 1549 1550 if (R != NULL) { 1551 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&X, k)); 1552 X.s = A->s; 1553 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(R, &X)); 1554 1555 if (mbedtls_mpi_cmp_int(R, 0) == 0) { 1556 R->s = 1; 1557 } 1558 } 1559 1560 cleanup: 1561 1562 mbedtls_mpi_free(&X); mbedtls_mpi_free(&Y); mbedtls_mpi_free(&Z); 1563 mbedtls_mpi_free(&T1); 1564 mbedtls_platform_zeroize(TP2, sizeof(TP2)); 1565 1566 return ret; 1567 } 1568 1569 /* 1570 * Division by int: A = Q * b + R 1571 */ 1572 int mbedtls_mpi_div_int(mbedtls_mpi *Q, mbedtls_mpi *R, 1573 const mbedtls_mpi *A, 1574 mbedtls_mpi_sint b) 1575 { 1576 mbedtls_mpi B; 1577 mbedtls_mpi_uint p[1]; 1578 1579 p[0] = mpi_sint_abs(b); 1580 B.s = TO_SIGN(b); 1581 B.n = 1; 1582 B.p = p; 1583 1584 return mbedtls_mpi_div_mpi(Q, R, A, &B); 1585 } 1586 1587 /* 1588 * Modulo: R = A mod B 1589 */ 1590 int mbedtls_mpi_mod_mpi(mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B) 1591 { 1592 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1593 1594 if (mbedtls_mpi_cmp_int(B, 0) < 0) { 1595 return MBEDTLS_ERR_MPI_NEGATIVE_VALUE; 1596 } 1597 1598 MBEDTLS_MPI_CHK(mbedtls_mpi_div_mpi(NULL, R, A, B)); 1599 1600 while (mbedtls_mpi_cmp_int(R, 0) < 0) { 1601 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(R, R, B)); 1602 } 1603 1604 while (mbedtls_mpi_cmp_mpi(R, B) >= 0) { 1605 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(R, R, B)); 1606 } 1607 1608 cleanup: 1609 1610 return ret; 1611 } 1612 1613 /* 1614 * Modulo: r = A mod b 1615 */ 1616 int mbedtls_mpi_mod_int(mbedtls_mpi_uint *r, const mbedtls_mpi *A, mbedtls_mpi_sint b) 1617 { 1618 size_t i; 1619 mbedtls_mpi_uint x, y, z; 1620 1621 if (b == 0) { 1622 return MBEDTLS_ERR_MPI_DIVISION_BY_ZERO; 1623 } 1624 1625 if (b < 0) { 1626 return MBEDTLS_ERR_MPI_NEGATIVE_VALUE; 1627 } 1628 1629 /* 1630 * handle trivial cases 1631 */ 1632 if (b == 1 || A->n == 0) { 1633 *r = 0; 1634 return 0; 1635 } 1636 1637 if (b == 2) { 1638 *r = A->p[0] & 1; 1639 return 0; 1640 } 1641 1642 /* 1643 * general case 1644 */ 1645 for (i = A->n, y = 0; i > 0; i--) { 1646 x = A->p[i - 1]; 1647 y = (y << biH) | (x >> biH); 1648 z = y / b; 1649 y -= z * b; 1650 1651 x <<= biH; 1652 y = (y << biH) | (x >> biH); 1653 z = y / b; 1654 y -= z * b; 1655 } 1656 1657 /* 1658 * If A is negative, then the current y represents a negative value. 1659 * Flipping it to the positive side. 1660 */ 1661 if (A->s < 0 && y != 0) { 1662 y = b - y; 1663 } 1664 1665 *r = y; 1666 1667 return 0; 1668 } 1669 1670 /** 1671 * \remark Replaced by our own because the original has been removed since 1672 * mbedtls v3.6.0. 1673 */ 1674 void mbedtls_mpi_montg_init(mbedtls_mpi_uint *mm, const mbedtls_mpi *N) 1675 { 1676 *mm = mbedtls_mpi_core_montmul_init(N->p); 1677 } 1678 1679 /** Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36) 1680 * 1681 * \param[in,out] A One of the numbers to multiply. 1682 * It must have at least as many limbs as N 1683 * (A->n >= N->n), and any limbs beyond n are ignored. 1684 * On successful completion, A contains the result of 1685 * the multiplication A * B * R^-1 mod N where 1686 * R = (2^ciL)^n. 1687 * \param[in] B One of the numbers to multiply. 1688 * It must be nonzero and must not have more limbs than N 1689 * (B->n <= N->n). 1690 * \param[in] N The modulus. \p N must be odd. 1691 * \param mm The value calculated by `mpi_montg_init(&mm, N)`. 1692 * This is -N^-1 mod 2^ciL. 1693 * \param[in,out] T A bignum for temporary storage. 1694 * It must be at least twice the limb size of N plus 1 1695 * (T->n >= 2 * N->n + 1). 1696 * Its initial content is unused and 1697 * its final content is indeterminate. 1698 * It does not get reallocated. 1699 * \remark Replaced by our own because the original has been removed since 1700 * mbedtls v3.6.0. 1701 */ 1702 void mbedtls_mpi_montmul(mbedtls_mpi *A, const mbedtls_mpi *B, 1703 const mbedtls_mpi *N, mbedtls_mpi_uint mm, 1704 mbedtls_mpi *T) 1705 { 1706 mbedtls_mpi_core_montmul(A->p, A->p, B->p, B->n, N->p, N->n, mm, T->p); 1707 } 1708 1709 /** 1710 * Montgomery reduction: A = A * R^-1 mod N 1711 * 1712 * See mbedtls_mpi_montmul() regarding constraints and guarantees on the 1713 * parameters. 1714 * 1715 * \remark Replaced by our own because the original has been removed since 1716 * mbedtls v3.6.0. 1717 */ 1718 void mbedtls_mpi_montred(mbedtls_mpi *A, const mbedtls_mpi *N, 1719 mbedtls_mpi_uint mm, mbedtls_mpi *T) 1720 { 1721 mbedtls_mpi_uint z = 1; 1722 mbedtls_mpi U; 1723 1724 U.n = U.s = (int)z; 1725 U.p = &z; 1726 1727 mbedtls_mpi_montmul(A, &U, N, mm, T); 1728 } 1729 1730 /* 1731 * Warning! If the parameter E_public has MBEDTLS_MPI_IS_PUBLIC as its value, 1732 * this function is not constant time with respect to the exponent (parameter E). 1733 */ 1734 static int mbedtls_mpi_exp_mod_optionally_safe(mbedtls_mpi *X, const mbedtls_mpi *A, 1735 const mbedtls_mpi *E, int E_public, 1736 const mbedtls_mpi *N, mbedtls_mpi *prec_RR) 1737 { 1738 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1739 1740 if (mbedtls_mpi_cmp_int(N, 0) <= 0 || (N->p[0] & 1) == 0) { 1741 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; 1742 } 1743 1744 if (mbedtls_mpi_cmp_int(E, 0) < 0) { 1745 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; 1746 } 1747 1748 if (mbedtls_mpi_bitlen(E) > MBEDTLS_MPI_MAX_BITS || 1749 mbedtls_mpi_bitlen(N) > MBEDTLS_MPI_MAX_BITS) { 1750 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; 1751 } 1752 1753 /* 1754 * Ensure that the exponent that we are passing to the core is not NULL. 1755 */ 1756 if (E->n == 0) { 1757 ret = mbedtls_mpi_lset(X, 1); 1758 return ret; 1759 } 1760 1761 /* 1762 * Allocate working memory for mbedtls_mpi_core_exp_mod() 1763 */ 1764 size_t T_limbs = mbedtls_mpi_core_exp_mod_working_limbs(N->n, E->n); 1765 mbedtls_mpi_uint *T = mempool_calloc(mbedtls_mpi_mempool, T_limbs, 1766 sizeof(mbedtls_mpi_uint)); 1767 if (T == NULL) { 1768 return MBEDTLS_ERR_MPI_ALLOC_FAILED; 1769 } 1770 1771 mbedtls_mpi RR; 1772 mbedtls_mpi_init_mempool(&RR); 1773 1774 /* 1775 * If 1st call, pre-compute R^2 mod N 1776 */ 1777 if (prec_RR == NULL || prec_RR->p == NULL) { 1778 MBEDTLS_MPI_CHK(mbedtls_mpi_core_get_mont_r2_unsafe(&RR, N)); 1779 1780 if (prec_RR != NULL) { 1781 *prec_RR = RR; 1782 } 1783 } else { 1784 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(prec_RR, N->n)); 1785 RR = *prec_RR; 1786 } 1787 1788 /* 1789 * To preserve constness we need to make a copy of A. Using X for this to 1790 * save memory. 1791 */ 1792 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, A)); 1793 1794 /* 1795 * Compensate for negative A (and correct at the end). 1796 */ 1797 X->s = 1; 1798 1799 /* 1800 * Make sure that X is in a form that is safe for consumption by 1801 * the core functions. 1802 * 1803 * - The core functions will not touch the limbs of X above N->n. The 1804 * result will be correct if those limbs are 0, which the mod call 1805 * ensures. 1806 * - Also, X must have at least as many limbs as N for the calls to the 1807 * core functions. 1808 */ 1809 if (mbedtls_mpi_cmp_mpi(X, N) >= 0) { 1810 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(X, X, N)); 1811 } 1812 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, N->n)); 1813 1814 /* 1815 * Convert to and from Montgomery around mbedtls_mpi_core_exp_mod(). 1816 */ 1817 { 1818 mbedtls_mpi_uint mm = mbedtls_mpi_core_montmul_init(N->p); 1819 mbedtls_mpi_core_to_mont_rep(X->p, X->p, N->p, N->n, mm, RR.p, T); 1820 if (E_public == MBEDTLS_MPI_IS_PUBLIC) { 1821 mbedtls_mpi_core_exp_mod_unsafe(X->p, X->p, N->p, N->n, E->p, E->n, RR.p, T); 1822 } else { 1823 mbedtls_mpi_core_exp_mod(X->p, X->p, N->p, N->n, E->p, E->n, RR.p, T); 1824 } 1825 mbedtls_mpi_core_from_mont_rep(X->p, X->p, N->p, N->n, mm, T); 1826 } 1827 1828 /* 1829 * Correct for negative A. 1830 */ 1831 if (A->s == -1 && (E->p[0] & 1) != 0) { 1832 mbedtls_ct_condition_t is_x_non_zero = mbedtls_mpi_core_check_zero_ct(X->p, X->n); 1833 X->s = mbedtls_ct_mpi_sign_if(is_x_non_zero, -1, 1); 1834 1835 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(X, N, X)); 1836 } 1837 1838 cleanup: 1839 1840 mbedtls_mpi_zeroize(T, T_limbs); 1841 mempool_free(mbedtls_mpi_mempool, T); 1842 1843 if (prec_RR == NULL || prec_RR->p == NULL) { 1844 mbedtls_mpi_free(&RR); 1845 } 1846 1847 return ret; 1848 } 1849 1850 int mbedtls_mpi_exp_mod(mbedtls_mpi *X, const mbedtls_mpi *A, 1851 const mbedtls_mpi *E, const mbedtls_mpi *N, 1852 mbedtls_mpi *prec_RR) 1853 { 1854 #if (defined(__KERNEL__) && defined(CFG_CORE_UNSAFE_MODEXP)) || \ 1855 (!defined(__KERNEL__) && defined(CFG_TA_MBEDTLS_UNSAFE_MODEXP)) 1856 return mbedtls_mpi_exp_mod_unsafe(X, A, E, N, prec_RR); 1857 #else 1858 return mbedtls_mpi_exp_mod_optionally_safe(X, A, E, MBEDTLS_MPI_IS_SECRET, N, prec_RR); 1859 #endif 1860 } 1861 1862 /* 1863 * Sliding-window exponentiation: X = A^E mod N (HAC 14.85) 1864 */ 1865 int mbedtls_mpi_exp_mod_unsafe(mbedtls_mpi *X, const mbedtls_mpi *A, 1866 const mbedtls_mpi *E, const mbedtls_mpi *N, 1867 mbedtls_mpi *prec_RR) 1868 { 1869 return mbedtls_mpi_exp_mod_optionally_safe(X, A, E, MBEDTLS_MPI_IS_PUBLIC, N, prec_RR); 1870 } 1871 1872 /* Constant-time GCD and/or modinv with odd modulus and A <= N */ 1873 int mbedtls_mpi_gcd_modinv_odd(mbedtls_mpi *G, 1874 mbedtls_mpi *I, 1875 const mbedtls_mpi *A, 1876 const mbedtls_mpi *N) 1877 { 1878 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1879 mbedtls_mpi local_g; 1880 mbedtls_mpi_uint *T = NULL; 1881 const size_t T_factor = I != NULL ? 5 : 4; 1882 const mbedtls_mpi_uint zero = 0; 1883 1884 /* Check requirements on A and N */ 1885 if (mbedtls_mpi_cmp_int(A, 0) < 0 || 1886 mbedtls_mpi_cmp_mpi(A, N) > 0 || 1887 mbedtls_mpi_get_bit(N, 0) != 1 || 1888 (I != NULL && mbedtls_mpi_cmp_int(N, 1) == 0)) { 1889 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; 1890 } 1891 1892 /* Check aliasing requirements */ 1893 if (A == N || (I != NULL && (I == N || G == N))) { 1894 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; 1895 } 1896 1897 mbedtls_mpi_init_mempool(&local_g); 1898 1899 if (G == NULL) { 1900 G = &local_g; 1901 } 1902 1903 /* We can't modify the values of G or I before use in the main function, 1904 * as they could be aliased to A or N. */ 1905 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(G, N->n)); 1906 if (I != NULL) { 1907 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(I, N->n)); 1908 } 1909 1910 T = mbedtls_calloc(sizeof(mbedtls_mpi_uint) * N->n, T_factor); 1911 if (T == NULL) { 1912 ret = MBEDTLS_ERR_MPI_ALLOC_FAILED; 1913 goto cleanup; 1914 } 1915 1916 mbedtls_mpi_uint *Ip = I != NULL ? I->p : NULL; 1917 /* If A is 0 (null), then A->p would be null, and A->n would be 0, 1918 * which would be an issue if A->p and A->n were passed to 1919 * mbedtls_mpi_core_gcd_modinv_odd below. */ 1920 const mbedtls_mpi_uint *Ap = A->p != NULL ? A->p : &zero; 1921 size_t An = A->n >= N->n ? N->n : A->p != NULL ? A->n : 1; 1922 mbedtls_mpi_core_gcd_modinv_odd(G->p, Ip, Ap, An, N->p, N->n, T); 1923 1924 G->s = 1; 1925 if (I != NULL) { 1926 I->s = 1; 1927 } 1928 1929 if (G->n > N->n) { 1930 memset(G->p + N->n, 0, ciL * (G->n - N->n)); 1931 } 1932 if (I != NULL && I->n > N->n) { 1933 memset(I->p + N->n, 0, ciL * (I->n - N->n)); 1934 } 1935 1936 cleanup: 1937 mbedtls_mpi_free(&local_g); 1938 mbedtls_free(T); 1939 return ret; 1940 } 1941 1942 /* 1943 * Greatest common divisor: G = gcd(A, B) 1944 * Wrapper around mbedtls_mpi_gcd_modinv() that removes its restrictions. 1945 */ 1946 int mbedtls_mpi_gcd(mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B) 1947 { 1948 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1949 mbedtls_mpi TA, TB; 1950 1951 mbedtls_mpi_init_mempool(&TA); mbedtls_mpi_init_mempool(&TB); 1952 1953 /* Make copies and take absolute values */ 1954 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TA, A)); 1955 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TB, B)); 1956 TA.s = TB.s = 1; 1957 1958 /* Make the two values the same (non-zero) number of limbs. 1959 * This is needed to use mbedtls_mpi_core functions below. */ 1960 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&TA, TB.n != 0 ? TB.n : 1)); 1961 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&TB, TA.n)); // non-zero from above 1962 1963 /* Handle special cases (that don't happen in crypto usage) */ 1964 if (mbedtls_mpi_core_check_zero_ct(TA.p, TA.n) == MBEDTLS_CT_FALSE) { 1965 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(G, &TB)); // GCD(0, B) = abs(B) 1966 goto cleanup; 1967 } 1968 if (mbedtls_mpi_core_check_zero_ct(TB.p, TB.n) == MBEDTLS_CT_FALSE) { 1969 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(G, &TA)); // GCD(A, 0) = abs(A) 1970 goto cleanup; 1971 } 1972 1973 /* Make boths inputs odd by putting powers of 2 on the side */ 1974 const size_t za = mbedtls_mpi_lsb(&TA); 1975 const size_t zb = mbedtls_mpi_lsb(&TB); 1976 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TA, za)); 1977 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TB, zb)); 1978 1979 /* Ensure A <= B: if B < A, swap them */ 1980 mbedtls_ct_condition_t swap = mbedtls_mpi_core_lt_ct(TB.p, TA.p, TA.n); 1981 mbedtls_mpi_core_cond_swap(TA.p, TB.p, TA.n, swap); 1982 1983 MBEDTLS_MPI_CHK(mbedtls_mpi_gcd_modinv_odd(G, NULL, &TA, &TB)); 1984 1985 /* Re-inject the power of 2 we had previously put aside */ 1986 size_t zg = za > zb ? zb : za; // zg = min(za, zb) 1987 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(G, zg)); 1988 1989 cleanup: 1990 1991 mbedtls_mpi_free(&TA); mbedtls_mpi_free(&TB); 1992 1993 return ret; 1994 } 1995 1996 /* 1997 * Fill X with size bytes of random. 1998 * The bytes returned from the RNG are used in a specific order which 1999 * is suitable for deterministic ECDSA (see the specification of 2000 * mbedtls_mpi_random() and the implementation in mbedtls_mpi_fill_random()). 2001 */ 2002 int mbedtls_mpi_fill_random(mbedtls_mpi *X, size_t size, 2003 int (*f_rng)(void *, unsigned char *, size_t), 2004 void *p_rng) 2005 { 2006 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2007 const size_t limbs = CHARS_TO_LIMBS(size); 2008 2009 /* Ensure that target MPI has exactly the necessary number of limbs */ 2010 MBEDTLS_MPI_CHK(mbedtls_mpi_resize_clear(X, limbs)); 2011 if (size == 0) { 2012 return 0; 2013 } 2014 2015 ret = mbedtls_mpi_core_fill_random(X->p, X->n, size, f_rng, p_rng); 2016 2017 cleanup: 2018 return ret; 2019 } 2020 2021 int mbedtls_mpi_random(mbedtls_mpi *X, 2022 mbedtls_mpi_sint min, 2023 const mbedtls_mpi *N, 2024 int (*f_rng)(void *, unsigned char *, size_t), 2025 void *p_rng) 2026 { 2027 if (min < 0) { 2028 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; 2029 } 2030 if (mbedtls_mpi_cmp_int(N, min) <= 0) { 2031 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; 2032 } 2033 2034 /* Ensure that target MPI has exactly the same number of limbs 2035 * as the upper bound, even if the upper bound has leading zeros. 2036 * This is necessary for mbedtls_mpi_core_random. */ 2037 int ret = mbedtls_mpi_resize_clear(X, N->n); 2038 if (ret != 0) { 2039 return ret; 2040 } 2041 2042 return mbedtls_mpi_core_random(X->p, min, N->p, X->n, f_rng, p_rng); 2043 } 2044 2045 /* 2046 * Modular inverse: X = A^-1 mod N with N odd (and A any range) 2047 */ 2048 int mbedtls_mpi_inv_mod_odd(mbedtls_mpi *X, 2049 const mbedtls_mpi *A, 2050 const mbedtls_mpi *N) 2051 { 2052 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2053 mbedtls_mpi T, G; 2054 2055 mbedtls_mpi_init_mempool(&T); 2056 mbedtls_mpi_init_mempool(&G); 2057 2058 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(&T, A, N)); 2059 MBEDTLS_MPI_CHK(mbedtls_mpi_gcd_modinv_odd(&G, &T, &T, N)); 2060 if (mbedtls_mpi_cmp_int(&G, 1) != 0) { 2061 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; 2062 goto cleanup; 2063 } 2064 2065 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, &T)); 2066 2067 cleanup: 2068 mbedtls_mpi_free(&T); 2069 mbedtls_mpi_free(&G); 2070 2071 return ret; 2072 } 2073 2074 /* 2075 * Compute X = A^-1 mod N with N even, A odd and 1 < A < N. 2076 * 2077 * This is not obvious because our constant-time modinv function only works with 2078 * an odd modulus, and here the modulus is even. The idea is that computing a 2079 * a^-1 mod b is really just computing the u coefficient in the Bézout relation 2080 * a*u + b*v = 1 (assuming gcd(a,b) = 1, i.e. the inverse exists). But if we know 2081 * one of u, v in this relation then the other is easy to find. So we can 2082 * actually start by computing N^-1 mod A with gives us "the wrong half" of the 2083 * Bézout relation, from which we'll deduce the interesting half A^-1 mod N. 2084 * 2085 * Return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE if the inverse doesn't exist. 2086 */ 2087 int mbedtls_mpi_inv_mod_even_in_range(mbedtls_mpi *X, 2088 mbedtls_mpi const *A, 2089 mbedtls_mpi const *N) 2090 { 2091 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2092 mbedtls_mpi I, G; 2093 2094 mbedtls_mpi_init_mempool(&I); 2095 mbedtls_mpi_init_mempool(&G); 2096 2097 /* Set I = N^-1 mod A */ 2098 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(&I, N, A)); 2099 MBEDTLS_MPI_CHK(mbedtls_mpi_gcd_modinv_odd(&G, &I, &I, A)); 2100 if (mbedtls_mpi_cmp_int(&G, 1) != 0) { 2101 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; 2102 goto cleanup; 2103 } 2104 2105 /* We know N * I = 1 + k * A for some k, which we can easily compute 2106 * as k = (N*I - 1) / A (we know there will be no remainder). */ 2107 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(&I, &I, N)); 2108 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_int(&I, &I, 1)); 2109 MBEDTLS_MPI_CHK(mbedtls_mpi_div_mpi(&G, NULL, &I, A)); 2110 2111 /* Now we have a Bézout relation N * (previous value of I) - G * A = 1, 2112 * so A^-1 mod N is -G mod N, which is N - G. 2113 * Note that 0 < k < N since 0 < I < A, so G (k) is already in range. */ 2114 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(X, N, &G)); 2115 2116 cleanup: 2117 mbedtls_mpi_free(&I); 2118 mbedtls_mpi_free(&G); 2119 return ret; 2120 } 2121 2122 /* 2123 * Compute X = A^-1 mod N with N even and A odd (but in any range). 2124 * 2125 * Return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE if the inverse doesn't exist. 2126 */ 2127 static int mbedtls_mpi_inv_mod_even(mbedtls_mpi *X, 2128 mbedtls_mpi const *A, 2129 mbedtls_mpi const *N) 2130 { 2131 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2132 mbedtls_mpi AA; 2133 2134 mbedtls_mpi_init_mempool(&AA); 2135 2136 /* Bring A in the range [0, N). */ 2137 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(&AA, A, N)); 2138 2139 /* We know A >= 0 but the next function wants A > 1 */ 2140 int cmp = mbedtls_mpi_cmp_int(&AA, 1); 2141 if (cmp < 0) { // AA == 0 2142 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; 2143 goto cleanup; 2144 } 2145 if (cmp == 0) { // AA = 1 2146 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 1)); 2147 goto cleanup; 2148 } 2149 2150 /* Now we know 1 < A < N, N is even and AA is still odd */ 2151 MBEDTLS_MPI_CHK(mbedtls_mpi_inv_mod_even_in_range(X, &AA, N)); 2152 2153 cleanup: 2154 mbedtls_mpi_free(&AA); 2155 return ret; 2156 } 2157 2158 /* 2159 * Modular inverse: X = A^-1 mod N 2160 * 2161 * Wrapper around mbedtls_mpi_gcd_modinv_odd() that lifts its limitations. 2162 */ 2163 int mbedtls_mpi_inv_mod(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N) 2164 { 2165 if (mbedtls_mpi_cmp_int(N, 1) <= 0) { 2166 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; 2167 } 2168 2169 if (mbedtls_mpi_get_bit(N, 0) == 1) { 2170 return mbedtls_mpi_inv_mod_odd(X, A, N); 2171 } 2172 2173 if (mbedtls_mpi_get_bit(A, 0) == 1) { 2174 return mbedtls_mpi_inv_mod_even(X, A, N); 2175 } 2176 2177 /* If A and N are both even, 2 divides their GCD, so no inverse. */ 2178 return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; 2179 } 2180 2181 #if defined(MBEDTLS_GENPRIME) 2182 2183 /* Gaps between primes, starting at 3. https://oeis.org/A001223 */ 2184 static const unsigned char small_prime_gaps[] = { 2185 2, 2, 4, 2, 4, 2, 4, 6, 2186 2, 6, 4, 2, 4, 6, 6, 2, 2187 6, 4, 2, 6, 4, 6, 8, 4, 2188 2, 4, 2, 4, 14, 4, 6, 2, 2189 10, 2, 6, 6, 4, 6, 6, 2, 2190 10, 2, 4, 2, 12, 12, 4, 2, 2191 4, 6, 2, 10, 6, 6, 6, 2, 2192 6, 4, 2, 10, 14, 4, 2, 4, 2193 14, 6, 10, 2, 4, 6, 8, 6, 2194 6, 4, 6, 8, 4, 8, 10, 2, 2195 10, 2, 6, 4, 6, 8, 4, 2, 2196 4, 12, 8, 4, 8, 4, 6, 12, 2197 2, 18, 6, 10, 6, 6, 2, 6, 2198 10, 6, 6, 2, 6, 6, 4, 2, 2199 12, 10, 2, 4, 6, 6, 2, 12, 2200 4, 6, 8, 10, 8, 10, 8, 6, 2201 6, 4, 8, 6, 4, 8, 4, 14, 2202 10, 12, 2, 10, 2, 4, 2, 10, 2203 14, 4, 2, 4, 14, 4, 2, 4, 2204 20, 4, 8, 10, 8, 4, 6, 6, 2205 14, 4, 6, 6, 8, 6, /*reaches 997*/ 2206 0 /* the last entry is effectively unused */ 2207 }; 2208 2209 /* 2210 * Small divisors test (X must be positive) 2211 * 2212 * Return values: 2213 * 0: no small factor (possible prime, more tests needed) 2214 * 1: certain prime 2215 * MBEDTLS_ERR_MPI_NOT_ACCEPTABLE: certain non-prime 2216 * other negative: error 2217 */ 2218 static int mpi_check_small_factors(const mbedtls_mpi *X) 2219 { 2220 int ret = 0; 2221 size_t i; 2222 mbedtls_mpi_uint r; 2223 unsigned p = 3; /* The first odd prime */ 2224 2225 if ((X->p[0] & 1) == 0) { 2226 return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; 2227 } 2228 2229 for (i = 0; i < sizeof(small_prime_gaps); p += small_prime_gaps[i], i++) { 2230 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_int(&r, X, p)); 2231 if (r == 0) { 2232 if (mbedtls_mpi_cmp_int(X, p) == 0) { 2233 return 1; 2234 } else { 2235 return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; 2236 } 2237 } 2238 } 2239 2240 cleanup: 2241 return ret; 2242 } 2243 2244 /* 2245 * Miller-Rabin pseudo-primality test (HAC 4.24) 2246 */ 2247 static int mpi_miller_rabin(const mbedtls_mpi *X, size_t rounds, 2248 int (*f_rng)(void *, unsigned char *, size_t), 2249 void *p_rng) 2250 { 2251 int ret, count; 2252 size_t i, j, k, s; 2253 mbedtls_mpi W, R, T, A, RR; 2254 2255 mbedtls_mpi_init_mempool(&W); mbedtls_mpi_init_mempool(&R); 2256 mbedtls_mpi_init_mempool(&T); mbedtls_mpi_init_mempool(&A); 2257 mbedtls_mpi_init_mempool(&RR); 2258 2259 /* 2260 * W = |X| - 1 2261 * R = W >> lsb( W ) 2262 */ 2263 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_int(&W, X, 1)); 2264 s = mbedtls_mpi_lsb(&W); 2265 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&R, &W)); 2266 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&R, s)); 2267 2268 for (i = 0; i < rounds; i++) { 2269 /* 2270 * pick a random A, 1 < A < |X| - 1 2271 */ 2272 count = 0; 2273 do { 2274 MBEDTLS_MPI_CHK(mbedtls_mpi_fill_random(&A, X->n * ciL, f_rng, p_rng)); 2275 2276 j = mbedtls_mpi_bitlen(&A); 2277 k = mbedtls_mpi_bitlen(&W); 2278 if (j > k) { 2279 A.p[A.n - 1] &= ((mbedtls_mpi_uint) 1 << (k - (A.n - 1) * biL - 1)) - 1; 2280 } 2281 2282 if (count++ > 300) { 2283 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; 2284 goto cleanup; 2285 } 2286 2287 } while (mbedtls_mpi_cmp_mpi(&A, &W) >= 0 || 2288 mbedtls_mpi_cmp_int(&A, 1) <= 0); 2289 2290 /* 2291 * A = A^R mod |X| 2292 */ 2293 MBEDTLS_MPI_CHK(mbedtls_mpi_exp_mod(&A, &A, &R, X, &RR)); 2294 2295 if (mbedtls_mpi_cmp_mpi(&A, &W) == 0 || 2296 mbedtls_mpi_cmp_int(&A, 1) == 0) { 2297 continue; 2298 } 2299 2300 j = 1; 2301 while (j < s && mbedtls_mpi_cmp_mpi(&A, &W) != 0) { 2302 /* 2303 * A = A * A mod |X| 2304 */ 2305 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(&T, &A, &A)); 2306 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(&A, &T, X)); 2307 2308 if (mbedtls_mpi_cmp_int(&A, 1) == 0) { 2309 break; 2310 } 2311 2312 j++; 2313 } 2314 2315 /* 2316 * not prime if A != |X| - 1 or A == 1 2317 */ 2318 if (mbedtls_mpi_cmp_mpi(&A, &W) != 0 || 2319 mbedtls_mpi_cmp_int(&A, 1) == 0) { 2320 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; 2321 break; 2322 } 2323 } 2324 2325 cleanup: 2326 mbedtls_mpi_free(&W); mbedtls_mpi_free(&R); 2327 mbedtls_mpi_free(&T); mbedtls_mpi_free(&A); 2328 mbedtls_mpi_free(&RR); 2329 2330 return ret; 2331 } 2332 2333 /* 2334 * Pseudo-primality test: small factors, then Miller-Rabin 2335 */ 2336 int mbedtls_mpi_is_prime_ext(const mbedtls_mpi *X, int rounds, 2337 int (*f_rng)(void *, unsigned char *, size_t), 2338 void *p_rng) 2339 { 2340 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2341 mbedtls_mpi XX; 2342 2343 XX.s = 1; 2344 XX.n = X->n; 2345 XX.p = X->p; 2346 2347 if (mbedtls_mpi_cmp_int(&XX, 0) == 0 || 2348 mbedtls_mpi_cmp_int(&XX, 1) == 0) { 2349 return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; 2350 } 2351 2352 if (mbedtls_mpi_cmp_int(&XX, 2) == 0) { 2353 return 0; 2354 } 2355 2356 if ((ret = mpi_check_small_factors(&XX)) != 0) { 2357 if (ret == 1) { 2358 return 0; 2359 } 2360 2361 return ret; 2362 } 2363 2364 return mpi_miller_rabin(&XX, rounds, f_rng, p_rng); 2365 } 2366 2367 /* 2368 * Prime number generation 2369 * 2370 * To generate an RSA key in a way recommended by FIPS 186-4, both primes must 2371 * be either 1024 bits or 1536 bits long, and flags must contain 2372 * MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR. 2373 */ 2374 int mbedtls_mpi_gen_prime(mbedtls_mpi *X, size_t nbits, int flags, 2375 int (*f_rng)(void *, unsigned char *, size_t), 2376 void *p_rng) 2377 { 2378 #ifdef MBEDTLS_HAVE_INT64 2379 // ceil(2^63.5) 2380 #define CEIL_MAXUINT_DIV_SQRT2 0xb504f333f9de6485ULL 2381 #else 2382 // ceil(2^31.5) 2383 #define CEIL_MAXUINT_DIV_SQRT2 0xb504f334U 2384 #endif 2385 int ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; 2386 size_t k, n; 2387 int rounds; 2388 mbedtls_mpi_uint r; 2389 mbedtls_mpi Y; 2390 2391 if (nbits < 3 || nbits > MBEDTLS_MPI_MAX_BITS) { 2392 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; 2393 } 2394 2395 mbedtls_mpi_init_mempool(&Y); 2396 2397 n = BITS_TO_LIMBS(nbits); 2398 2399 if ((flags & MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR) == 0) { 2400 /* 2401 * 2^-80 error probability, number of rounds chosen per HAC, table 4.4 2402 */ 2403 rounds = ((nbits >= 1300) ? 2 : (nbits >= 850) ? 3 : 2404 (nbits >= 650) ? 4 : (nbits >= 350) ? 8 : 2405 (nbits >= 250) ? 12 : (nbits >= 150) ? 18 : 27); 2406 } else { 2407 /* 2408 * 2^-100 error probability, number of rounds computed based on HAC, 2409 * fact 4.48 2410 */ 2411 rounds = ((nbits >= 1450) ? 4 : (nbits >= 1150) ? 5 : 2412 (nbits >= 1000) ? 6 : (nbits >= 850) ? 7 : 2413 (nbits >= 750) ? 8 : (nbits >= 500) ? 13 : 2414 (nbits >= 250) ? 28 : (nbits >= 150) ? 40 : 51); 2415 } 2416 2417 while (1) { 2418 MBEDTLS_MPI_CHK(mbedtls_mpi_fill_random(X, n * ciL, f_rng, p_rng)); 2419 /* make sure generated number is at least (nbits-1)+0.5 bits (FIPS 186-4 §B.3.3 steps 4.4, 5.5) */ 2420 if (X->p[n-1] < CEIL_MAXUINT_DIV_SQRT2) { 2421 continue; 2422 } 2423 2424 k = n * biL; 2425 if (k > nbits) { 2426 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(X, k - nbits)); 2427 } 2428 X->p[0] |= 1; 2429 2430 if ((flags & MBEDTLS_MPI_GEN_PRIME_FLAG_DH) == 0) { 2431 ret = mbedtls_mpi_is_prime_ext(X, rounds, f_rng, p_rng); 2432 2433 if (ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE) { 2434 goto cleanup; 2435 } 2436 } else { 2437 /* 2438 * A necessary condition for Y and X = 2Y + 1 to be prime 2439 * is X = 2 mod 3 (which is equivalent to Y = 2 mod 3). 2440 * Make sure it is satisfied, while keeping X = 3 mod 4 2441 */ 2442 2443 X->p[0] |= 2; 2444 2445 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_int(&r, X, 3)); 2446 if (r == 0) { 2447 MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, X, 8)); 2448 } else if (r == 1) { 2449 MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, X, 4)); 2450 } 2451 2452 /* Set Y = (X-1) / 2, which is X / 2 because X is odd */ 2453 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&Y, X)); 2454 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&Y, 1)); 2455 2456 while (1) { 2457 /* 2458 * First, check small factors for X and Y 2459 * before doing Miller-Rabin on any of them 2460 */ 2461 if ((ret = mpi_check_small_factors(X)) == 0 && 2462 (ret = mpi_check_small_factors(&Y)) == 0 && 2463 (ret = mpi_miller_rabin(X, rounds, f_rng, p_rng)) 2464 == 0 && 2465 (ret = mpi_miller_rabin(&Y, rounds, f_rng, p_rng)) 2466 == 0) { 2467 goto cleanup; 2468 } 2469 2470 if (ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE) { 2471 goto cleanup; 2472 } 2473 2474 /* 2475 * Next candidates. We want to preserve Y = (X-1) / 2 and 2476 * Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3) 2477 * so up Y by 6 and X by 12. 2478 */ 2479 MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, X, 12)); 2480 MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(&Y, &Y, 6)); 2481 } 2482 } 2483 } 2484 2485 cleanup: 2486 2487 mbedtls_mpi_free(&Y); 2488 2489 return ret; 2490 } 2491 2492 #endif /* MBEDTLS_GENPRIME */ 2493 2494 #if defined(MBEDTLS_SELF_TEST) 2495 2496 #define GCD_PAIR_COUNT 3 2497 2498 static const int gcd_pairs[GCD_PAIR_COUNT][3] = 2499 { 2500 { 693, 609, 21 }, 2501 { 1764, 868, 28 }, 2502 { 768454923, 542167814, 1 } 2503 }; 2504 2505 /* 2506 * Checkup routine 2507 */ 2508 int mbedtls_mpi_self_test(int verbose) 2509 { 2510 int ret, i; 2511 mbedtls_mpi A, E, N, X, Y, U, V; 2512 2513 mbedtls_mpi_init_mempool(&A); mbedtls_mpi_init_mempool(&E); 2514 mbedtls_mpi_init_mempool(&N); mbedtls_mpi_init_mempool(&X); 2515 mbedtls_mpi_init_mempool(&Y); mbedtls_mpi_init_mempool(&U); 2516 mbedtls_mpi_init_mempool(&V); 2517 2518 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&A, 16, 2519 "EFE021C2645FD1DC586E69184AF4A31E" \ 2520 "D5F53E93B5F123FA41680867BA110131" \ 2521 "944FE7952E2517337780CB0DB80E61AA" \ 2522 "E7C8DDC6C5C6AADEB34EB38A2F40D5E6")); 2523 2524 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&E, 16, 2525 "B2E7EFD37075B9F03FF989C7C5051C20" \ 2526 "34D2A323810251127E7BF8625A4F49A5" \ 2527 "F3E27F4DA8BD59C47D6DAABA4C8127BD" \ 2528 "5B5C25763222FEFCCFC38B832366C29E")); 2529 2530 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&N, 16, 2531 "0066A198186C18C10B2F5ED9B522752A" \ 2532 "9830B69916E535C8F047518A889A43A5" \ 2533 "94B6BED27A168D31D4A52F88925AA8F5")); 2534 2535 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(&X, &A, &N)); 2536 2537 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&U, 16, 2538 "602AB7ECA597A3D6B56FF9829A5E8B85" \ 2539 "9E857EA95A03512E2BAE7391688D264A" \ 2540 "A5663B0341DB9CCFD2C4C5F421FEC814" \ 2541 "8001B72E848A38CAE1C65F78E56ABDEF" \ 2542 "E12D3C039B8A02D6BE593F0BBBDA56F1" \ 2543 "ECF677152EF804370C1A305CAF3B5BF1" \ 2544 "30879B56C61DE584A0F53A2447A51E")); 2545 2546 if (verbose != 0) { 2547 mbedtls_printf(" MPI test #1 (mul_mpi): "); 2548 } 2549 2550 if (mbedtls_mpi_cmp_mpi(&X, &U) != 0) { 2551 if (verbose != 0) { 2552 mbedtls_printf("failed\n"); 2553 } 2554 2555 ret = 1; 2556 goto cleanup; 2557 } 2558 2559 if (verbose != 0) { 2560 mbedtls_printf("passed\n"); 2561 } 2562 2563 MBEDTLS_MPI_CHK(mbedtls_mpi_div_mpi(&X, &Y, &A, &N)); 2564 2565 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&U, 16, 2566 "256567336059E52CAE22925474705F39A94")); 2567 2568 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&V, 16, 2569 "6613F26162223DF488E9CD48CC132C7A" \ 2570 "0AC93C701B001B092E4E5B9F73BCD27B" \ 2571 "9EE50D0657C77F374E903CDFA4C642")); 2572 2573 if (verbose != 0) { 2574 mbedtls_printf(" MPI test #2 (div_mpi): "); 2575 } 2576 2577 if (mbedtls_mpi_cmp_mpi(&X, &U) != 0 || 2578 mbedtls_mpi_cmp_mpi(&Y, &V) != 0) { 2579 if (verbose != 0) { 2580 mbedtls_printf("failed\n"); 2581 } 2582 2583 ret = 1; 2584 goto cleanup; 2585 } 2586 2587 if (verbose != 0) { 2588 mbedtls_printf("passed\n"); 2589 } 2590 2591 MBEDTLS_MPI_CHK(mbedtls_mpi_exp_mod(&X, &A, &E, &N, NULL)); 2592 2593 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&U, 16, 2594 "36E139AEA55215609D2816998ED020BB" \ 2595 "BD96C37890F65171D948E9BC7CBAA4D9" \ 2596 "325D24D6A3C12710F10A09FA08AB87")); 2597 2598 if (verbose != 0) { 2599 mbedtls_printf(" MPI test #3 (exp_mod): "); 2600 } 2601 2602 if (mbedtls_mpi_cmp_mpi(&X, &U) != 0) { 2603 if (verbose != 0) { 2604 mbedtls_printf("failed\n"); 2605 } 2606 2607 ret = 1; 2608 goto cleanup; 2609 } 2610 2611 if (verbose != 0) { 2612 mbedtls_printf("passed\n"); 2613 } 2614 2615 MBEDTLS_MPI_CHK(mbedtls_mpi_inv_mod(&X, &A, &N)); 2616 2617 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&U, 16, 2618 "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \ 2619 "C3DBA76456363A10869622EAC2DD84EC" \ 2620 "C5B8A74DAC4D09E03B5E0BE779F2DF61")); 2621 2622 if (verbose != 0) { 2623 mbedtls_printf(" MPI test #4 (inv_mod): "); 2624 } 2625 2626 if (mbedtls_mpi_cmp_mpi(&X, &U) != 0) { 2627 if (verbose != 0) { 2628 mbedtls_printf("failed\n"); 2629 } 2630 2631 ret = 1; 2632 goto cleanup; 2633 } 2634 2635 if (verbose != 0) { 2636 mbedtls_printf("passed\n"); 2637 } 2638 2639 if (verbose != 0) { 2640 mbedtls_printf(" MPI test #5 (simple gcd): "); 2641 } 2642 2643 for (i = 0; i < GCD_PAIR_COUNT; i++) { 2644 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&X, gcd_pairs[i][0])); 2645 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&Y, gcd_pairs[i][1])); 2646 2647 MBEDTLS_MPI_CHK(mbedtls_mpi_gcd(&A, &X, &Y)); 2648 2649 if (mbedtls_mpi_cmp_int(&A, gcd_pairs[i][2]) != 0) { 2650 if (verbose != 0) { 2651 mbedtls_printf("failed at %d\n", i); 2652 } 2653 2654 ret = 1; 2655 goto cleanup; 2656 } 2657 } 2658 2659 if (verbose != 0) { 2660 mbedtls_printf("passed\n"); 2661 } 2662 2663 cleanup: 2664 2665 if (ret != 0 && verbose != 0) { 2666 mbedtls_printf("Unexpected error, return code = %08X\n", (unsigned int) ret); 2667 } 2668 2669 mbedtls_mpi_free(&A); mbedtls_mpi_free(&E); mbedtls_mpi_free(&N); mbedtls_mpi_free(&X); 2670 mbedtls_mpi_free(&Y); mbedtls_mpi_free(&U); mbedtls_mpi_free(&V); 2671 2672 if (verbose != 0) { 2673 mbedtls_printf("\n"); 2674 } 2675 2676 return ret; 2677 } 2678 2679 #endif /* MBEDTLS_SELF_TEST */ 2680 2681 #endif /* MBEDTLS_BIGNUM_C */ 2682