1 /* 2 * Multi-precision integer library 3 * 4 * Copyright The Mbed TLS Contributors 5 * SPDX-License-Identifier: Apache-2.0 6 * 7 * Licensed under the Apache License, Version 2.0 (the "License"); you may 8 * not use this file except in compliance with the License. 9 * You may obtain a copy of the License at 10 * 11 * http://www.apache.org/licenses/LICENSE-2.0 12 * 13 * Unless required by applicable law or agreed to in writing, software 14 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT 15 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 16 * See the License for the specific language governing permissions and 17 * limitations under the License. 18 */ 19 20 /* 21 * The following sources were referenced in the design of this Multi-precision 22 * Integer library: 23 * 24 * [1] Handbook of Applied Cryptography - 1997 25 * Menezes, van Oorschot and Vanstone 26 * 27 * [2] Multi-Precision Math 28 * Tom St Denis 29 * https://github.com/libtom/libtommath/blob/develop/tommath.pdf 30 * 31 * [3] GNU Multi-Precision Arithmetic Library 32 * https://gmplib.org/manual/index.html 33 * 34 */ 35 36 #include "common.h" 37 38 #if defined(MBEDTLS_BIGNUM_C) 39 40 #include "mbedtls/bignum.h" 41 #include "mbedtls/bn_mul.h" 42 #include "mbedtls/platform_util.h" 43 #include "mbedtls/error.h" 44 #include "constant_time_internal.h" 45 46 #include <limits.h> 47 #include <string.h> 48 49 #if defined(MBEDTLS_PLATFORM_C) 50 #include "mbedtls/platform.h" 51 #else 52 #include <stdio.h> 53 #include <stdlib.h> 54 #define mbedtls_printf printf 55 #define mbedtls_calloc calloc 56 #define mbedtls_free free 57 #endif 58 59 #include <mempool.h> 60 #include <util.h> 61 62 #define MPI_VALIDATE_RET( cond ) \ 63 MBEDTLS_INTERNAL_VALIDATE_RET( cond, MBEDTLS_ERR_MPI_BAD_INPUT_DATA ) 64 #define MPI_VALIDATE( cond ) \ 65 MBEDTLS_INTERNAL_VALIDATE( cond ) 66 67 #define ciL (sizeof(mbedtls_mpi_uint)) /* chars in limb */ 68 #define biL (ciL << 3) /* bits in limb */ 69 #define biH (ciL << 2) /* half limb size */ 70 71 #define MPI_SIZE_T_MAX ( (size_t) -1 ) /* SIZE_T_MAX is not standard */ 72 73 /* 74 * Convert between bits/chars and number of limbs 75 * Divide first in order to avoid potential overflows 76 */ 77 #define BITS_TO_LIMBS(i) ( (i) / biL + ( (i) % biL != 0 ) ) 78 #define CHARS_TO_LIMBS(i) ( (i) / ciL + ( (i) % ciL != 0 ) ) 79 80 void *mbedtls_mpi_mempool; 81 82 /* Implementation that should never be optimized out by the compiler */ 83 static void mbedtls_mpi_zeroize( mbedtls_mpi_uint *v, size_t n ) 84 { 85 mbedtls_platform_zeroize( v, ciL * n ); 86 } 87 88 /* 89 * Initialize one MPI 90 */ 91 static void mpi_init( mbedtls_mpi *X, short use_mempool ) 92 { 93 MPI_VALIDATE( X != NULL ); 94 95 X->s = 1; 96 X->use_mempool = use_mempool; 97 X->n = 0; 98 X->p = NULL; 99 } 100 101 void mbedtls_mpi_init( mbedtls_mpi *X ) 102 { 103 mpi_init( X, 0 /*use_mempool*/ ); 104 } 105 106 void mbedtls_mpi_init_mempool( mbedtls_mpi *X ) 107 { 108 mpi_init( X, !!mbedtls_mpi_mempool /*use_mempool*/ ); 109 } 110 111 /* 112 * Unallocate one MPI 113 */ 114 void mbedtls_mpi_free( mbedtls_mpi *X ) 115 { 116 if( X == NULL ) 117 return; 118 119 if( X->p != NULL ) 120 { 121 mbedtls_mpi_zeroize( X->p, X->n ); 122 if( X->use_mempool ) 123 mempool_free( mbedtls_mpi_mempool, X->p ); 124 else 125 mbedtls_free( X->p ); 126 } 127 128 X->s = 1; 129 X->n = 0; 130 X->p = NULL; 131 } 132 133 /* 134 * Enlarge to the specified number of limbs 135 */ 136 int mbedtls_mpi_grow( mbedtls_mpi *X, size_t nblimbs ) 137 { 138 mbedtls_mpi_uint *p; 139 MPI_VALIDATE_RET( X != NULL ); 140 141 if( nblimbs > MBEDTLS_MPI_MAX_LIMBS ) 142 return( MBEDTLS_ERR_MPI_ALLOC_FAILED ); 143 144 if( X->n < nblimbs ) 145 { 146 if( X->use_mempool ) 147 { 148 p = mempool_alloc( mbedtls_mpi_mempool, nblimbs * ciL ); 149 if( p == NULL ) 150 return( MBEDTLS_ERR_MPI_ALLOC_FAILED ); 151 memset( p, 0, nblimbs * ciL ); 152 } 153 else 154 { 155 p = (mbedtls_mpi_uint*)mbedtls_calloc( nblimbs, ciL ); 156 if( p == NULL ) 157 return( MBEDTLS_ERR_MPI_ALLOC_FAILED ); 158 } 159 160 if( X->p != NULL ) 161 { 162 memcpy( p, X->p, X->n * ciL ); 163 mbedtls_mpi_zeroize( X->p, X->n ); 164 if( X->use_mempool ) 165 mempool_free( mbedtls_mpi_mempool, X->p); 166 else 167 mbedtls_free( X->p ); 168 } 169 170 X->n = nblimbs; 171 X->p = p; 172 } 173 174 return( 0 ); 175 } 176 177 /* 178 * Resize down as much as possible, 179 * while keeping at least the specified number of limbs 180 */ 181 int mbedtls_mpi_shrink( mbedtls_mpi *X, size_t nblimbs ) 182 { 183 mbedtls_mpi_uint *p; 184 size_t i; 185 MPI_VALIDATE_RET( X != NULL ); 186 187 if( nblimbs > MBEDTLS_MPI_MAX_LIMBS ) 188 return( MBEDTLS_ERR_MPI_ALLOC_FAILED ); 189 190 /* Actually resize up if there are currently fewer than nblimbs limbs. */ 191 if( X->n <= nblimbs ) 192 return( mbedtls_mpi_grow( X, nblimbs ) ); 193 /* After this point, then X->n > nblimbs and in particular X->n > 0. */ 194 195 for( i = X->n - 1; i > 0; i-- ) 196 if( X->p[i] != 0 ) 197 break; 198 i++; 199 200 if( i < nblimbs ) 201 i = nblimbs; 202 203 if( X->use_mempool ) 204 { 205 p = mempool_alloc( mbedtls_mpi_mempool, i * ciL ); 206 if( p == NULL ) 207 return( MBEDTLS_ERR_MPI_ALLOC_FAILED ); 208 memset( p, 0, i * ciL ); 209 } 210 else 211 { 212 p = (mbedtls_mpi_uint*)mbedtls_calloc( i, ciL ); 213 if( p == NULL ) 214 return( MBEDTLS_ERR_MPI_ALLOC_FAILED ); 215 } 216 217 if( X->p != NULL ) 218 { 219 memcpy( p, X->p, i * ciL ); 220 mbedtls_mpi_zeroize( X->p, X->n ); 221 if( X->use_mempool ) 222 mempool_free( mbedtls_mpi_mempool, X->p ); 223 else 224 mbedtls_free( X->p ); 225 } 226 227 X->n = i; 228 X->p = p; 229 230 return( 0 ); 231 } 232 233 /* Resize X to have exactly n limbs and set it to 0. */ 234 static int mbedtls_mpi_resize_clear( mbedtls_mpi *X, size_t limbs ) 235 { 236 if( limbs == 0 ) 237 { 238 mbedtls_mpi_free( X ); 239 return( 0 ); 240 } 241 else if( X->n == limbs ) 242 { 243 memset( X->p, 0, limbs * ciL ); 244 X->s = 1; 245 return( 0 ); 246 } 247 else 248 { 249 mbedtls_mpi_free( X ); 250 return( mbedtls_mpi_grow( X, limbs ) ); 251 } 252 } 253 254 /* 255 * Copy the contents of Y into X. 256 * 257 * This function is not constant-time. Leading zeros in Y may be removed. 258 * 259 * Ensure that X does not shrink. This is not guaranteed by the public API, 260 * but some code in the bignum module relies on this property, for example 261 * in mbedtls_mpi_exp_mod(). 262 */ 263 int mbedtls_mpi_copy( mbedtls_mpi *X, const mbedtls_mpi *Y ) 264 { 265 int ret = 0; 266 size_t i; 267 MPI_VALIDATE_RET( X != NULL ); 268 MPI_VALIDATE_RET( Y != NULL ); 269 270 if( X == Y ) 271 return( 0 ); 272 273 if( Y->n == 0 ) 274 { 275 if( X->n != 0 ) 276 { 277 X->s = 1; 278 memset( X->p, 0, X->n * ciL ); 279 } 280 return( 0 ); 281 } 282 283 for( i = Y->n - 1; i > 0; i-- ) 284 if( Y->p[i] != 0 ) 285 break; 286 i++; 287 288 X->s = Y->s; 289 290 if( X->n < i ) 291 { 292 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i ) ); 293 } 294 else 295 { 296 memset( X->p + i, 0, ( X->n - i ) * ciL ); 297 } 298 299 memcpy( X->p, Y->p, i * ciL ); 300 301 cleanup: 302 303 return( ret ); 304 } 305 306 /* 307 * Swap the contents of X and Y 308 */ 309 void mbedtls_mpi_swap( mbedtls_mpi *X, mbedtls_mpi *Y ) 310 { 311 mbedtls_mpi T; 312 MPI_VALIDATE( X != NULL ); 313 MPI_VALIDATE( Y != NULL ); 314 315 memcpy( &T, X, sizeof( mbedtls_mpi ) ); 316 memcpy( X, Y, sizeof( mbedtls_mpi ) ); 317 memcpy( Y, &T, sizeof( mbedtls_mpi ) ); 318 } 319 320 /* 321 * Set value from integer 322 */ 323 int mbedtls_mpi_lset( mbedtls_mpi *X, mbedtls_mpi_sint z ) 324 { 325 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 326 MPI_VALIDATE_RET( X != NULL ); 327 328 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, 1 ) ); 329 memset( X->p, 0, X->n * ciL ); 330 331 X->p[0] = ( z < 0 ) ? -z : z; 332 X->s = ( z < 0 ) ? -1 : 1; 333 334 cleanup: 335 336 return( ret ); 337 } 338 339 /* 340 * Get a specific bit 341 */ 342 int mbedtls_mpi_get_bit( const mbedtls_mpi *X, size_t pos ) 343 { 344 MPI_VALIDATE_RET( X != NULL ); 345 346 if( X->n * biL <= pos ) 347 return( 0 ); 348 349 return( ( X->p[pos / biL] >> ( pos % biL ) ) & 0x01 ); 350 } 351 352 /* Get a specific byte, without range checks. */ 353 #define GET_BYTE( X, i ) \ 354 ( ( ( X )->p[( i ) / ciL] >> ( ( ( i ) % ciL ) * 8 ) ) & 0xff ) 355 356 /* 357 * Set a bit to a specific value of 0 or 1 358 */ 359 int mbedtls_mpi_set_bit( mbedtls_mpi *X, size_t pos, unsigned char val ) 360 { 361 int ret = 0; 362 size_t off = pos / biL; 363 size_t idx = pos % biL; 364 MPI_VALIDATE_RET( X != NULL ); 365 366 if( val != 0 && val != 1 ) 367 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); 368 369 if( X->n * biL <= pos ) 370 { 371 if( val == 0 ) 372 return( 0 ); 373 374 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, off + 1 ) ); 375 } 376 377 X->p[off] &= ~( (mbedtls_mpi_uint) 0x01 << idx ); 378 X->p[off] |= (mbedtls_mpi_uint) val << idx; 379 380 cleanup: 381 382 return( ret ); 383 } 384 385 /* 386 * Return the number of less significant zero-bits 387 */ 388 size_t mbedtls_mpi_lsb( const mbedtls_mpi *X ) 389 { 390 size_t i, j, count = 0; 391 MBEDTLS_INTERNAL_VALIDATE_RET( X != NULL, 0 ); 392 393 for( i = 0; i < X->n; i++ ) 394 for( j = 0; j < biL; j++, count++ ) 395 if( ( ( X->p[i] >> j ) & 1 ) != 0 ) 396 return( count ); 397 398 return( 0 ); 399 } 400 401 /* 402 * Count leading zero bits in a given integer 403 */ 404 static size_t mbedtls_clz( const mbedtls_mpi_uint x ) 405 { 406 size_t j; 407 mbedtls_mpi_uint mask = (mbedtls_mpi_uint) 1 << (biL - 1); 408 409 for( j = 0; j < biL; j++ ) 410 { 411 if( x & mask ) break; 412 413 mask >>= 1; 414 } 415 416 return j; 417 } 418 419 /* 420 * Return the number of bits 421 */ 422 size_t mbedtls_mpi_bitlen( const mbedtls_mpi *X ) 423 { 424 size_t i, j; 425 426 if( X->n == 0 ) 427 return( 0 ); 428 429 for( i = X->n - 1; i > 0; i-- ) 430 if( X->p[i] != 0 ) 431 break; 432 433 j = biL - mbedtls_clz( X->p[i] ); 434 435 return( ( i * biL ) + j ); 436 } 437 438 /* 439 * Return the total size in bytes 440 */ 441 size_t mbedtls_mpi_size( const mbedtls_mpi *X ) 442 { 443 return( ( mbedtls_mpi_bitlen( X ) + 7 ) >> 3 ); 444 } 445 446 /* 447 * Convert an ASCII character to digit value 448 */ 449 static int mpi_get_digit( mbedtls_mpi_uint *d, int radix, char c ) 450 { 451 *d = 255; 452 453 if( c >= 0x30 && c <= 0x39 ) *d = c - 0x30; 454 if( c >= 0x41 && c <= 0x46 ) *d = c - 0x37; 455 if( c >= 0x61 && c <= 0x66 ) *d = c - 0x57; 456 457 if( *d >= (mbedtls_mpi_uint) radix ) 458 return( MBEDTLS_ERR_MPI_INVALID_CHARACTER ); 459 460 return( 0 ); 461 } 462 463 /* 464 * Import from an ASCII string 465 */ 466 int mbedtls_mpi_read_string( mbedtls_mpi *X, int radix, const char *s ) 467 { 468 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 469 size_t i, j, slen, n; 470 int sign = 1; 471 mbedtls_mpi_uint d; 472 mbedtls_mpi T; 473 MPI_VALIDATE_RET( X != NULL ); 474 MPI_VALIDATE_RET( s != NULL ); 475 476 if( radix < 2 || radix > 16 ) 477 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); 478 479 mbedtls_mpi_init_mempool( &T ); 480 481 if( s[0] == 0 ) 482 { 483 mbedtls_mpi_free( X ); 484 return( 0 ); 485 } 486 487 if( s[0] == '-' ) 488 { 489 ++s; 490 sign = -1; 491 } 492 493 slen = strlen( s ); 494 495 if( radix == 16 ) 496 { 497 if( slen > MPI_SIZE_T_MAX >> 2 ) 498 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); 499 500 n = BITS_TO_LIMBS( slen << 2 ); 501 502 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, n ) ); 503 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) ); 504 505 for( i = slen, j = 0; i > 0; i--, j++ ) 506 { 507 MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i - 1] ) ); 508 X->p[j / ( 2 * ciL )] |= d << ( ( j % ( 2 * ciL ) ) << 2 ); 509 } 510 } 511 else 512 { 513 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) ); 514 515 for( i = 0; i < slen; i++ ) 516 { 517 MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i] ) ); 518 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T, X, radix ) ); 519 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, &T, d ) ); 520 } 521 } 522 523 if( sign < 0 && mbedtls_mpi_bitlen( X ) != 0 ) 524 X->s = -1; 525 526 cleanup: 527 528 mbedtls_mpi_free( &T ); 529 530 return( ret ); 531 } 532 533 /* 534 * Helper to write the digits high-order first. 535 */ 536 static int mpi_write_hlp( mbedtls_mpi *X, int radix, 537 char **p, const size_t buflen ) 538 { 539 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 540 mbedtls_mpi_uint r; 541 size_t length = 0; 542 char *p_end = *p + buflen; 543 544 do 545 { 546 if( length >= buflen ) 547 { 548 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL ); 549 } 550 551 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, radix ) ); 552 MBEDTLS_MPI_CHK( mbedtls_mpi_div_int( X, NULL, X, radix ) ); 553 /* 554 * Write the residue in the current position, as an ASCII character. 555 */ 556 if( r < 0xA ) 557 *(--p_end) = (char)( '0' + r ); 558 else 559 *(--p_end) = (char)( 'A' + ( r - 0xA ) ); 560 561 length++; 562 } while( mbedtls_mpi_cmp_int( X, 0 ) != 0 ); 563 564 memmove( *p, p_end, length ); 565 *p += length; 566 567 cleanup: 568 569 return( ret ); 570 } 571 572 /* 573 * Export into an ASCII string 574 */ 575 int mbedtls_mpi_write_string( const mbedtls_mpi *X, int radix, 576 char *buf, size_t buflen, size_t *olen ) 577 { 578 int ret = 0; 579 size_t n; 580 char *p; 581 mbedtls_mpi T; 582 MPI_VALIDATE_RET( X != NULL ); 583 MPI_VALIDATE_RET( olen != NULL ); 584 MPI_VALIDATE_RET( buflen == 0 || buf != NULL ); 585 586 if( radix < 2 || radix > 16 ) 587 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); 588 589 n = mbedtls_mpi_bitlen( X ); /* Number of bits necessary to present `n`. */ 590 if( radix >= 4 ) n >>= 1; /* Number of 4-adic digits necessary to present 591 * `n`. If radix > 4, this might be a strict 592 * overapproximation of the number of 593 * radix-adic digits needed to present `n`. */ 594 if( radix >= 16 ) n >>= 1; /* Number of hexadecimal digits necessary to 595 * present `n`. */ 596 597 n += 1; /* Terminating null byte */ 598 n += 1; /* Compensate for the divisions above, which round down `n` 599 * in case it's not even. */ 600 n += 1; /* Potential '-'-sign. */ 601 n += ( n & 1 ); /* Make n even to have enough space for hexadecimal writing, 602 * which always uses an even number of hex-digits. */ 603 604 if( buflen < n ) 605 { 606 *olen = n; 607 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL ); 608 } 609 610 p = buf; 611 mbedtls_mpi_init_mempool( &T ); 612 613 if( X->s == -1 ) 614 { 615 *p++ = '-'; 616 buflen--; 617 } 618 619 if( radix == 16 ) 620 { 621 int c; 622 size_t i, j, k; 623 624 for( i = X->n, k = 0; i > 0; i-- ) 625 { 626 for( j = ciL; j > 0; j-- ) 627 { 628 c = ( X->p[i - 1] >> ( ( j - 1 ) << 3) ) & 0xFF; 629 630 if( c == 0 && k == 0 && ( i + j ) != 2 ) 631 continue; 632 633 *(p++) = "0123456789ABCDEF" [c / 16]; 634 *(p++) = "0123456789ABCDEF" [c % 16]; 635 k = 1; 636 } 637 } 638 } 639 else 640 { 641 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T, X ) ); 642 643 if( T.s == -1 ) 644 T.s = 1; 645 646 MBEDTLS_MPI_CHK( mpi_write_hlp( &T, radix, &p, buflen ) ); 647 } 648 649 *p++ = '\0'; 650 *olen = p - buf; 651 652 cleanup: 653 654 mbedtls_mpi_free( &T ); 655 656 return( ret ); 657 } 658 659 #if defined(MBEDTLS_FS_IO) 660 /* 661 * Read X from an opened file 662 */ 663 int mbedtls_mpi_read_file( mbedtls_mpi *X, int radix, FILE *fin ) 664 { 665 mbedtls_mpi_uint d; 666 size_t slen; 667 char *p; 668 /* 669 * Buffer should have space for (short) label and decimal formatted MPI, 670 * newline characters and '\0' 671 */ 672 char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ]; 673 674 MPI_VALIDATE_RET( X != NULL ); 675 MPI_VALIDATE_RET( fin != NULL ); 676 677 if( radix < 2 || radix > 16 ) 678 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); 679 680 memset( s, 0, sizeof( s ) ); 681 if( fgets( s, sizeof( s ) - 1, fin ) == NULL ) 682 return( MBEDTLS_ERR_MPI_FILE_IO_ERROR ); 683 684 slen = strlen( s ); 685 if( slen == sizeof( s ) - 2 ) 686 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL ); 687 688 if( slen > 0 && s[slen - 1] == '\n' ) { slen--; s[slen] = '\0'; } 689 if( slen > 0 && s[slen - 1] == '\r' ) { slen--; s[slen] = '\0'; } 690 691 p = s + slen; 692 while( p-- > s ) 693 if( mpi_get_digit( &d, radix, *p ) != 0 ) 694 break; 695 696 return( mbedtls_mpi_read_string( X, radix, p + 1 ) ); 697 } 698 699 /* 700 * Write X into an opened file (or stdout if fout == NULL) 701 */ 702 int mbedtls_mpi_write_file( const char *p, const mbedtls_mpi *X, int radix, FILE *fout ) 703 { 704 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 705 size_t n, slen, plen; 706 /* 707 * Buffer should have space for (short) label and decimal formatted MPI, 708 * newline characters and '\0' 709 */ 710 char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ]; 711 MPI_VALIDATE_RET( X != NULL ); 712 713 if( radix < 2 || radix > 16 ) 714 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); 715 716 memset( s, 0, sizeof( s ) ); 717 718 MBEDTLS_MPI_CHK( mbedtls_mpi_write_string( X, radix, s, sizeof( s ) - 2, &n ) ); 719 720 if( p == NULL ) p = ""; 721 722 plen = strlen( p ); 723 slen = strlen( s ); 724 s[slen++] = '\r'; 725 s[slen++] = '\n'; 726 727 if( fout != NULL ) 728 { 729 if( fwrite( p, 1, plen, fout ) != plen || 730 fwrite( s, 1, slen, fout ) != slen ) 731 return( MBEDTLS_ERR_MPI_FILE_IO_ERROR ); 732 } 733 else 734 mbedtls_printf( "%s%s", p, s ); 735 736 cleanup: 737 738 return( ret ); 739 } 740 #endif /* MBEDTLS_FS_IO */ 741 742 743 /* Convert a big-endian byte array aligned to the size of mbedtls_mpi_uint 744 * into the storage form used by mbedtls_mpi. */ 745 746 static mbedtls_mpi_uint mpi_uint_bigendian_to_host_c( mbedtls_mpi_uint x ) 747 { 748 uint8_t i; 749 unsigned char *x_ptr; 750 mbedtls_mpi_uint tmp = 0; 751 752 for( i = 0, x_ptr = (unsigned char*) &x; i < ciL; i++, x_ptr++ ) 753 { 754 tmp <<= CHAR_BIT; 755 tmp |= (mbedtls_mpi_uint) *x_ptr; 756 } 757 758 return( tmp ); 759 } 760 761 static mbedtls_mpi_uint mpi_uint_bigendian_to_host( mbedtls_mpi_uint x ) 762 { 763 #if defined(__BYTE_ORDER__) 764 765 /* Nothing to do on bigendian systems. */ 766 #if ( __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ ) 767 return( x ); 768 #endif /* __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ */ 769 770 #if ( __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ ) 771 772 /* For GCC and Clang, have builtins for byte swapping. */ 773 #if defined(__GNUC__) && defined(__GNUC_PREREQ) 774 #if __GNUC_PREREQ(4,3) 775 #define have_bswap 776 #endif 777 #endif 778 779 #if defined(__clang__) && defined(__has_builtin) 780 #if __has_builtin(__builtin_bswap32) && \ 781 __has_builtin(__builtin_bswap64) 782 #define have_bswap 783 #endif 784 #endif 785 786 #if defined(have_bswap) 787 /* The compiler is hopefully able to statically evaluate this! */ 788 switch( sizeof(mbedtls_mpi_uint) ) 789 { 790 case 4: 791 return( __builtin_bswap32(x) ); 792 case 8: 793 return( __builtin_bswap64(x) ); 794 } 795 #endif 796 #endif /* __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ */ 797 #endif /* __BYTE_ORDER__ */ 798 799 /* Fall back to C-based reordering if we don't know the byte order 800 * or we couldn't use a compiler-specific builtin. */ 801 return( mpi_uint_bigendian_to_host_c( x ) ); 802 } 803 804 static void mpi_bigendian_to_host( mbedtls_mpi_uint * const p, size_t limbs ) 805 { 806 mbedtls_mpi_uint *cur_limb_left; 807 mbedtls_mpi_uint *cur_limb_right; 808 if( limbs == 0 ) 809 return; 810 811 /* 812 * Traverse limbs and 813 * - adapt byte-order in each limb 814 * - swap the limbs themselves. 815 * For that, simultaneously traverse the limbs from left to right 816 * and from right to left, as long as the left index is not bigger 817 * than the right index (it's not a problem if limbs is odd and the 818 * indices coincide in the last iteration). 819 */ 820 for( cur_limb_left = p, cur_limb_right = p + ( limbs - 1 ); 821 cur_limb_left <= cur_limb_right; 822 cur_limb_left++, cur_limb_right-- ) 823 { 824 mbedtls_mpi_uint tmp; 825 /* Note that if cur_limb_left == cur_limb_right, 826 * this code effectively swaps the bytes only once. */ 827 tmp = mpi_uint_bigendian_to_host( *cur_limb_left ); 828 *cur_limb_left = mpi_uint_bigendian_to_host( *cur_limb_right ); 829 *cur_limb_right = tmp; 830 } 831 } 832 833 /* 834 * Import X from unsigned binary data, little endian 835 */ 836 int mbedtls_mpi_read_binary_le( mbedtls_mpi *X, 837 const unsigned char *buf, size_t buflen ) 838 { 839 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 840 size_t i; 841 size_t const limbs = CHARS_TO_LIMBS( buflen ); 842 843 /* Ensure that target MPI has exactly the necessary number of limbs */ 844 MBEDTLS_MPI_CHK( mbedtls_mpi_resize_clear( X, limbs ) ); 845 846 for( i = 0; i < buflen; i++ ) 847 X->p[i / ciL] |= ((mbedtls_mpi_uint) buf[i]) << ((i % ciL) << 3); 848 849 cleanup: 850 851 /* 852 * This function is also used to import keys. However, wiping the buffers 853 * upon failure is not necessary because failure only can happen before any 854 * input is copied. 855 */ 856 return( ret ); 857 } 858 859 /* 860 * Import X from unsigned binary data, big endian 861 */ 862 int mbedtls_mpi_read_binary( mbedtls_mpi *X, const unsigned char *buf, size_t buflen ) 863 { 864 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 865 size_t const limbs = CHARS_TO_LIMBS( buflen ); 866 size_t const overhead = ( limbs * ciL ) - buflen; 867 unsigned char *Xp; 868 869 MPI_VALIDATE_RET( X != NULL ); 870 MPI_VALIDATE_RET( buflen == 0 || buf != NULL ); 871 872 /* Ensure that target MPI has exactly the necessary number of limbs */ 873 MBEDTLS_MPI_CHK( mbedtls_mpi_resize_clear( X, limbs ) ); 874 875 /* Avoid calling `memcpy` with NULL source or destination argument, 876 * even if buflen is 0. */ 877 if( buflen != 0 ) 878 { 879 Xp = (unsigned char*) X->p; 880 memcpy( Xp + overhead, buf, buflen ); 881 882 mpi_bigendian_to_host( X->p, limbs ); 883 } 884 885 cleanup: 886 887 /* 888 * This function is also used to import keys. However, wiping the buffers 889 * upon failure is not necessary because failure only can happen before any 890 * input is copied. 891 */ 892 return( ret ); 893 } 894 895 /* 896 * Export X into unsigned binary data, little endian 897 */ 898 int mbedtls_mpi_write_binary_le( const mbedtls_mpi *X, 899 unsigned char *buf, size_t buflen ) 900 { 901 size_t stored_bytes = X->n * ciL; 902 size_t bytes_to_copy; 903 size_t i; 904 905 if( stored_bytes < buflen ) 906 { 907 bytes_to_copy = stored_bytes; 908 } 909 else 910 { 911 bytes_to_copy = buflen; 912 913 /* The output buffer is smaller than the allocated size of X. 914 * However X may fit if its leading bytes are zero. */ 915 for( i = bytes_to_copy; i < stored_bytes; i++ ) 916 { 917 if( GET_BYTE( X, i ) != 0 ) 918 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL ); 919 } 920 } 921 922 for( i = 0; i < bytes_to_copy; i++ ) 923 buf[i] = GET_BYTE( X, i ); 924 925 if( stored_bytes < buflen ) 926 { 927 /* Write trailing 0 bytes */ 928 memset( buf + stored_bytes, 0, buflen - stored_bytes ); 929 } 930 931 return( 0 ); 932 } 933 934 /* 935 * Export X into unsigned binary data, big endian 936 */ 937 int mbedtls_mpi_write_binary( const mbedtls_mpi *X, 938 unsigned char *buf, size_t buflen ) 939 { 940 size_t stored_bytes; 941 size_t bytes_to_copy; 942 unsigned char *p; 943 size_t i; 944 945 MPI_VALIDATE_RET( X != NULL ); 946 MPI_VALIDATE_RET( buflen == 0 || buf != NULL ); 947 948 stored_bytes = X->n * ciL; 949 950 if( stored_bytes < buflen ) 951 { 952 /* There is enough space in the output buffer. Write initial 953 * null bytes and record the position at which to start 954 * writing the significant bytes. In this case, the execution 955 * trace of this function does not depend on the value of the 956 * number. */ 957 bytes_to_copy = stored_bytes; 958 p = buf + buflen - stored_bytes; 959 memset( buf, 0, buflen - stored_bytes ); 960 } 961 else 962 { 963 /* The output buffer is smaller than the allocated size of X. 964 * However X may fit if its leading bytes are zero. */ 965 bytes_to_copy = buflen; 966 p = buf; 967 for( i = bytes_to_copy; i < stored_bytes; i++ ) 968 { 969 if( GET_BYTE( X, i ) != 0 ) 970 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL ); 971 } 972 } 973 974 for( i = 0; i < bytes_to_copy; i++ ) 975 p[bytes_to_copy - i - 1] = GET_BYTE( X, i ); 976 977 return( 0 ); 978 } 979 980 /* 981 * Left-shift: X <<= count 982 */ 983 int mbedtls_mpi_shift_l( mbedtls_mpi *X, size_t count ) 984 { 985 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 986 size_t i, v0, t1; 987 mbedtls_mpi_uint r0 = 0, r1; 988 MPI_VALIDATE_RET( X != NULL ); 989 990 v0 = count / (biL ); 991 t1 = count & (biL - 1); 992 993 i = mbedtls_mpi_bitlen( X ) + count; 994 995 if( X->n * biL < i ) 996 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, BITS_TO_LIMBS( i ) ) ); 997 998 ret = 0; 999 1000 /* 1001 * shift by count / limb_size 1002 */ 1003 if( v0 > 0 ) 1004 { 1005 for( i = X->n; i > v0; i-- ) 1006 X->p[i - 1] = X->p[i - v0 - 1]; 1007 1008 for( ; i > 0; i-- ) 1009 X->p[i - 1] = 0; 1010 } 1011 1012 /* 1013 * shift by count % limb_size 1014 */ 1015 if( t1 > 0 ) 1016 { 1017 for( i = v0; i < X->n; i++ ) 1018 { 1019 r1 = X->p[i] >> (biL - t1); 1020 X->p[i] <<= t1; 1021 X->p[i] |= r0; 1022 r0 = r1; 1023 } 1024 } 1025 1026 cleanup: 1027 1028 return( ret ); 1029 } 1030 1031 /* 1032 * Right-shift: X >>= count 1033 */ 1034 int mbedtls_mpi_shift_r( mbedtls_mpi *X, size_t count ) 1035 { 1036 size_t i, v0, v1; 1037 mbedtls_mpi_uint r0 = 0, r1; 1038 MPI_VALIDATE_RET( X != NULL ); 1039 1040 v0 = count / biL; 1041 v1 = count & (biL - 1); 1042 1043 if( v0 > X->n || ( v0 == X->n && v1 > 0 ) ) 1044 return mbedtls_mpi_lset( X, 0 ); 1045 1046 /* 1047 * shift by count / limb_size 1048 */ 1049 if( v0 > 0 ) 1050 { 1051 for( i = 0; i < X->n - v0; i++ ) 1052 X->p[i] = X->p[i + v0]; 1053 1054 for( ; i < X->n; i++ ) 1055 X->p[i] = 0; 1056 } 1057 1058 /* 1059 * shift by count % limb_size 1060 */ 1061 if( v1 > 0 ) 1062 { 1063 for( i = X->n; i > 0; i-- ) 1064 { 1065 r1 = X->p[i - 1] << (biL - v1); 1066 X->p[i - 1] >>= v1; 1067 X->p[i - 1] |= r0; 1068 r0 = r1; 1069 } 1070 } 1071 1072 return( 0 ); 1073 } 1074 1075 /* 1076 * Compare unsigned values 1077 */ 1078 int mbedtls_mpi_cmp_abs( const mbedtls_mpi *X, const mbedtls_mpi *Y ) 1079 { 1080 size_t i, j; 1081 MPI_VALIDATE_RET( X != NULL ); 1082 MPI_VALIDATE_RET( Y != NULL ); 1083 1084 for( i = X->n; i > 0; i-- ) 1085 if( X->p[i - 1] != 0 ) 1086 break; 1087 1088 for( j = Y->n; j > 0; j-- ) 1089 if( Y->p[j - 1] != 0 ) 1090 break; 1091 1092 if( i == 0 && j == 0 ) 1093 return( 0 ); 1094 1095 if( i > j ) return( 1 ); 1096 if( j > i ) return( -1 ); 1097 1098 for( ; i > 0; i-- ) 1099 { 1100 if( X->p[i - 1] > Y->p[i - 1] ) return( 1 ); 1101 if( X->p[i - 1] < Y->p[i - 1] ) return( -1 ); 1102 } 1103 1104 return( 0 ); 1105 } 1106 1107 /* 1108 * Compare signed values 1109 */ 1110 int mbedtls_mpi_cmp_mpi( const mbedtls_mpi *X, const mbedtls_mpi *Y ) 1111 { 1112 size_t i, j; 1113 MPI_VALIDATE_RET( X != NULL ); 1114 MPI_VALIDATE_RET( Y != NULL ); 1115 1116 for( i = X->n; i > 0; i-- ) 1117 if( X->p[i - 1] != 0 ) 1118 break; 1119 1120 for( j = Y->n; j > 0; j-- ) 1121 if( Y->p[j - 1] != 0 ) 1122 break; 1123 1124 if( i == 0 && j == 0 ) 1125 return( 0 ); 1126 1127 if( i > j ) return( X->s ); 1128 if( j > i ) return( -Y->s ); 1129 1130 if( X->s > 0 && Y->s < 0 ) return( 1 ); 1131 if( Y->s > 0 && X->s < 0 ) return( -1 ); 1132 1133 for( ; i > 0; i-- ) 1134 { 1135 if( X->p[i - 1] > Y->p[i - 1] ) return( X->s ); 1136 if( X->p[i - 1] < Y->p[i - 1] ) return( -X->s ); 1137 } 1138 1139 return( 0 ); 1140 } 1141 1142 /* 1143 * Compare signed values 1144 */ 1145 int mbedtls_mpi_cmp_int( const mbedtls_mpi *X, mbedtls_mpi_sint z ) 1146 { 1147 mbedtls_mpi Y; 1148 mbedtls_mpi_uint p[1]; 1149 MPI_VALIDATE_RET( X != NULL ); 1150 1151 *p = ( z < 0 ) ? -z : z; 1152 Y.s = ( z < 0 ) ? -1 : 1; 1153 Y.n = 1; 1154 Y.p = p; 1155 1156 return( mbedtls_mpi_cmp_mpi( X, &Y ) ); 1157 } 1158 1159 /* 1160 * Unsigned addition: X = |A| + |B| (HAC 14.7) 1161 */ 1162 int mbedtls_mpi_add_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B ) 1163 { 1164 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1165 size_t i, j; 1166 mbedtls_mpi_uint *o, *p, c, tmp; 1167 MPI_VALIDATE_RET( X != NULL ); 1168 MPI_VALIDATE_RET( A != NULL ); 1169 MPI_VALIDATE_RET( B != NULL ); 1170 1171 if( X == B ) 1172 { 1173 const mbedtls_mpi *T = A; A = X; B = T; 1174 } 1175 1176 if( X != A ) 1177 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) ); 1178 1179 /* 1180 * X should always be positive as a result of unsigned additions. 1181 */ 1182 X->s = 1; 1183 1184 for( j = B->n; j > 0; j-- ) 1185 if( B->p[j - 1] != 0 ) 1186 break; 1187 1188 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) ); 1189 1190 o = B->p; p = X->p; c = 0; 1191 1192 /* 1193 * tmp is used because it might happen that p == o 1194 */ 1195 for( i = 0; i < j; i++, o++, p++ ) 1196 { 1197 tmp= *o; 1198 *p += c; c = ( *p < c ); 1199 *p += tmp; c += ( *p < tmp ); 1200 } 1201 1202 while( c != 0 ) 1203 { 1204 if( i >= X->n ) 1205 { 1206 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + 1 ) ); 1207 p = X->p + i; 1208 } 1209 1210 *p += c; c = ( *p < c ); i++; p++; 1211 } 1212 1213 cleanup: 1214 1215 return( ret ); 1216 } 1217 1218 /** 1219 * Helper for mbedtls_mpi subtraction. 1220 * 1221 * Calculate l - r where l and r have the same size. 1222 * This function operates modulo (2^ciL)^n and returns the carry 1223 * (1 if there was a wraparound, i.e. if `l < r`, and 0 otherwise). 1224 * 1225 * d may be aliased to l or r. 1226 * 1227 * \param n Number of limbs of \p d, \p l and \p r. 1228 * \param[out] d The result of the subtraction. 1229 * \param[in] l The left operand. 1230 * \param[in] r The right operand. 1231 * 1232 * \return 1 if `l < r`. 1233 * 0 if `l >= r`. 1234 */ 1235 static mbedtls_mpi_uint mpi_sub_hlp( size_t n, 1236 mbedtls_mpi_uint *d, 1237 const mbedtls_mpi_uint *l, 1238 const mbedtls_mpi_uint *r ) 1239 { 1240 size_t i; 1241 mbedtls_mpi_uint c = 0, t, z; 1242 1243 for( i = 0; i < n; i++ ) 1244 { 1245 z = ( l[i] < c ); t = l[i] - c; 1246 c = ( t < r[i] ) + z; d[i] = t - r[i]; 1247 } 1248 1249 return( c ); 1250 } 1251 1252 /* 1253 * Unsigned subtraction: X = |A| - |B| (HAC 14.9, 14.10) 1254 */ 1255 int mbedtls_mpi_sub_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B ) 1256 { 1257 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1258 size_t n; 1259 mbedtls_mpi_uint carry; 1260 MPI_VALIDATE_RET( X != NULL ); 1261 MPI_VALIDATE_RET( A != NULL ); 1262 MPI_VALIDATE_RET( B != NULL ); 1263 1264 for( n = B->n; n > 0; n-- ) 1265 if( B->p[n - 1] != 0 ) 1266 break; 1267 if( n > A->n ) 1268 { 1269 /* B >= (2^ciL)^n > A */ 1270 ret = MBEDTLS_ERR_MPI_NEGATIVE_VALUE; 1271 goto cleanup; 1272 } 1273 1274 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, A->n ) ); 1275 1276 /* Set the high limbs of X to match A. Don't touch the lower limbs 1277 * because X might be aliased to B, and we must not overwrite the 1278 * significant digits of B. */ 1279 if( A->n > n ) 1280 memcpy( X->p + n, A->p + n, ( A->n - n ) * ciL ); 1281 if( X->n > A->n ) 1282 memset( X->p + A->n, 0, ( X->n - A->n ) * ciL ); 1283 1284 carry = mpi_sub_hlp( n, X->p, A->p, B->p ); 1285 if( carry != 0 ) 1286 { 1287 /* Propagate the carry to the first nonzero limb of X. */ 1288 for( ; n < X->n && X->p[n] == 0; n++ ) 1289 --X->p[n]; 1290 /* If we ran out of space for the carry, it means that the result 1291 * is negative. */ 1292 if( n == X->n ) 1293 { 1294 ret = MBEDTLS_ERR_MPI_NEGATIVE_VALUE; 1295 goto cleanup; 1296 } 1297 --X->p[n]; 1298 } 1299 1300 /* X should always be positive as a result of unsigned subtractions. */ 1301 X->s = 1; 1302 1303 cleanup: 1304 return( ret ); 1305 } 1306 1307 /* 1308 * Signed addition: X = A + B 1309 */ 1310 int mbedtls_mpi_add_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B ) 1311 { 1312 int ret, s; 1313 MPI_VALIDATE_RET( X != NULL ); 1314 MPI_VALIDATE_RET( A != NULL ); 1315 MPI_VALIDATE_RET( B != NULL ); 1316 1317 s = A->s; 1318 if( A->s * B->s < 0 ) 1319 { 1320 if( mbedtls_mpi_cmp_abs( A, B ) >= 0 ) 1321 { 1322 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) ); 1323 X->s = s; 1324 } 1325 else 1326 { 1327 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) ); 1328 X->s = -s; 1329 } 1330 } 1331 else 1332 { 1333 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) ); 1334 X->s = s; 1335 } 1336 1337 cleanup: 1338 1339 return( ret ); 1340 } 1341 1342 /* 1343 * Signed subtraction: X = A - B 1344 */ 1345 int mbedtls_mpi_sub_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B ) 1346 { 1347 int ret, s; 1348 MPI_VALIDATE_RET( X != NULL ); 1349 MPI_VALIDATE_RET( A != NULL ); 1350 MPI_VALIDATE_RET( B != NULL ); 1351 1352 s = A->s; 1353 if( A->s * B->s > 0 ) 1354 { 1355 if( mbedtls_mpi_cmp_abs( A, B ) >= 0 ) 1356 { 1357 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) ); 1358 X->s = s; 1359 } 1360 else 1361 { 1362 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) ); 1363 X->s = -s; 1364 } 1365 } 1366 else 1367 { 1368 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) ); 1369 X->s = s; 1370 } 1371 1372 cleanup: 1373 1374 return( ret ); 1375 } 1376 1377 /* 1378 * Signed addition: X = A + b 1379 */ 1380 int mbedtls_mpi_add_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b ) 1381 { 1382 mbedtls_mpi B; 1383 mbedtls_mpi_uint p[1]; 1384 MPI_VALIDATE_RET( X != NULL ); 1385 MPI_VALIDATE_RET( A != NULL ); 1386 1387 p[0] = ( b < 0 ) ? -b : b; 1388 B.s = ( b < 0 ) ? -1 : 1; 1389 B.n = 1; 1390 B.p = p; 1391 1392 return( mbedtls_mpi_add_mpi( X, A, &B ) ); 1393 } 1394 1395 /* 1396 * Signed subtraction: X = A - b 1397 */ 1398 int mbedtls_mpi_sub_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b ) 1399 { 1400 mbedtls_mpi B; 1401 mbedtls_mpi_uint p[1]; 1402 MPI_VALIDATE_RET( X != NULL ); 1403 MPI_VALIDATE_RET( A != NULL ); 1404 1405 p[0] = ( b < 0 ) ? -b : b; 1406 B.s = ( b < 0 ) ? -1 : 1; 1407 B.n = 1; 1408 B.p = p; 1409 1410 return( mbedtls_mpi_sub_mpi( X, A, &B ) ); 1411 } 1412 1413 /** Helper for mbedtls_mpi multiplication. 1414 * 1415 * Add \p b * \p s to \p d. 1416 * 1417 * \param i The number of limbs of \p s. 1418 * \param[in] s A bignum to multiply, of size \p i. 1419 * It may overlap with \p d, but only if 1420 * \p d <= \p s. 1421 * Its leading limb must not be \c 0. 1422 * \param[in,out] d The bignum to add to. 1423 * It must be sufficiently large to store the 1424 * result of the multiplication. This means 1425 * \p i + 1 limbs if \p d[\p i - 1] started as 0 and \p b 1426 * is not known a priori. 1427 * \param b A scalar to multiply. 1428 */ 1429 static 1430 #if defined(__APPLE__) && defined(__arm__) 1431 /* 1432 * Apple LLVM version 4.2 (clang-425.0.24) (based on LLVM 3.2svn) 1433 * appears to need this to prevent bad ARM code generation at -O3. 1434 */ 1435 __attribute__ ((noinline)) 1436 #endif 1437 void mpi_mul_hlp( size_t i, 1438 const mbedtls_mpi_uint *s, 1439 mbedtls_mpi_uint *d, 1440 mbedtls_mpi_uint b ) 1441 { 1442 mbedtls_mpi_uint c = 0, t = 0; 1443 1444 #if defined(MULADDC_HUIT) 1445 for( ; i >= 8; i -= 8 ) 1446 { 1447 MULADDC_INIT 1448 MULADDC_HUIT 1449 MULADDC_STOP 1450 } 1451 1452 for( ; i > 0; i-- ) 1453 { 1454 MULADDC_INIT 1455 MULADDC_CORE 1456 MULADDC_STOP 1457 } 1458 #else /* MULADDC_HUIT */ 1459 for( ; i >= 16; i -= 16 ) 1460 { 1461 MULADDC_INIT 1462 MULADDC_CORE MULADDC_CORE 1463 MULADDC_CORE MULADDC_CORE 1464 MULADDC_CORE MULADDC_CORE 1465 MULADDC_CORE MULADDC_CORE 1466 1467 MULADDC_CORE MULADDC_CORE 1468 MULADDC_CORE MULADDC_CORE 1469 MULADDC_CORE MULADDC_CORE 1470 MULADDC_CORE MULADDC_CORE 1471 MULADDC_STOP 1472 } 1473 1474 for( ; i >= 8; i -= 8 ) 1475 { 1476 MULADDC_INIT 1477 MULADDC_CORE MULADDC_CORE 1478 MULADDC_CORE MULADDC_CORE 1479 1480 MULADDC_CORE MULADDC_CORE 1481 MULADDC_CORE MULADDC_CORE 1482 MULADDC_STOP 1483 } 1484 1485 for( ; i > 0; i-- ) 1486 { 1487 MULADDC_INIT 1488 MULADDC_CORE 1489 MULADDC_STOP 1490 } 1491 #endif /* MULADDC_HUIT */ 1492 1493 t++; 1494 1495 while( c != 0 ) 1496 { 1497 *d += c; c = ( *d < c ); d++; 1498 } 1499 } 1500 1501 /* 1502 * Baseline multiplication: X = A * B (HAC 14.12) 1503 */ 1504 int mbedtls_mpi_mul_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B ) 1505 { 1506 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1507 size_t i, j; 1508 mbedtls_mpi TA, TB; 1509 int result_is_zero = 0; 1510 MPI_VALIDATE_RET( X != NULL ); 1511 MPI_VALIDATE_RET( A != NULL ); 1512 MPI_VALIDATE_RET( B != NULL ); 1513 1514 mbedtls_mpi_init_mempool( &TA ); mbedtls_mpi_init_mempool( &TB ); 1515 1516 if( X == A ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) ); A = &TA; } 1517 if( X == B ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) ); B = &TB; } 1518 1519 for( i = A->n; i > 0; i-- ) 1520 if( A->p[i - 1] != 0 ) 1521 break; 1522 if( i == 0 ) 1523 result_is_zero = 1; 1524 1525 for( j = B->n; j > 0; j-- ) 1526 if( B->p[j - 1] != 0 ) 1527 break; 1528 if( j == 0 ) 1529 result_is_zero = 1; 1530 1531 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + j ) ); 1532 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) ); 1533 1534 for( ; j > 0; j-- ) 1535 mpi_mul_hlp( i, A->p, X->p + j - 1, B->p[j - 1] ); 1536 1537 /* If the result is 0, we don't shortcut the operation, which reduces 1538 * but does not eliminate side channels leaking the zero-ness. We do 1539 * need to take care to set the sign bit properly since the library does 1540 * not fully support an MPI object with a value of 0 and s == -1. */ 1541 if( result_is_zero ) 1542 X->s = 1; 1543 else 1544 X->s = A->s * B->s; 1545 1546 cleanup: 1547 1548 mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TA ); 1549 1550 return( ret ); 1551 } 1552 1553 /* 1554 * Baseline multiplication: X = A * b 1555 */ 1556 int mbedtls_mpi_mul_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b ) 1557 { 1558 MPI_VALIDATE_RET( X != NULL ); 1559 MPI_VALIDATE_RET( A != NULL ); 1560 1561 /* mpi_mul_hlp can't deal with a leading 0. */ 1562 size_t n = A->n; 1563 while( n > 0 && A->p[n - 1] == 0 ) 1564 --n; 1565 1566 /* The general method below doesn't work if n==0 or b==0. By chance 1567 * calculating the result is trivial in those cases. */ 1568 if( b == 0 || n == 0 ) 1569 { 1570 return( mbedtls_mpi_lset( X, 0 ) ); 1571 } 1572 1573 /* Calculate A*b as A + A*(b-1) to take advantage of mpi_mul_hlp */ 1574 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1575 /* In general, A * b requires 1 limb more than b. If 1576 * A->p[n - 1] * b / b == A->p[n - 1], then A * b fits in the same 1577 * number of limbs as A and the call to grow() is not required since 1578 * copy() will take care of the growth if needed. However, experimentally, 1579 * making the call to grow() unconditional causes slightly fewer 1580 * calls to calloc() in ECP code, presumably because it reuses the 1581 * same mpi for a while and this way the mpi is more likely to directly 1582 * grow to its final size. */ 1583 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, n + 1 ) ); 1584 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) ); 1585 mpi_mul_hlp( n, A->p, X->p, b - 1 ); 1586 1587 cleanup: 1588 return( ret ); 1589 } 1590 1591 /* 1592 * Unsigned integer divide - double mbedtls_mpi_uint dividend, u1/u0, and 1593 * mbedtls_mpi_uint divisor, d 1594 */ 1595 static mbedtls_mpi_uint mbedtls_int_div_int( mbedtls_mpi_uint u1, 1596 mbedtls_mpi_uint u0, mbedtls_mpi_uint d, mbedtls_mpi_uint *r ) 1597 { 1598 #if defined(MBEDTLS_HAVE_UDBL) 1599 mbedtls_t_udbl dividend, quotient; 1600 #else 1601 const mbedtls_mpi_uint radix = (mbedtls_mpi_uint) 1 << biH; 1602 const mbedtls_mpi_uint uint_halfword_mask = ( (mbedtls_mpi_uint) 1 << biH ) - 1; 1603 mbedtls_mpi_uint d0, d1, q0, q1, rAX, r0, quotient; 1604 mbedtls_mpi_uint u0_msw, u0_lsw; 1605 size_t s; 1606 #endif 1607 1608 /* 1609 * Check for overflow 1610 */ 1611 if( 0 == d || u1 >= d ) 1612 { 1613 if (r != NULL) *r = ~0; 1614 1615 return ( ~0 ); 1616 } 1617 1618 #if defined(MBEDTLS_HAVE_UDBL) 1619 dividend = (mbedtls_t_udbl) u1 << biL; 1620 dividend |= (mbedtls_t_udbl) u0; 1621 quotient = dividend / d; 1622 if( quotient > ( (mbedtls_t_udbl) 1 << biL ) - 1 ) 1623 quotient = ( (mbedtls_t_udbl) 1 << biL ) - 1; 1624 1625 if( r != NULL ) 1626 *r = (mbedtls_mpi_uint)( dividend - (quotient * d ) ); 1627 1628 return (mbedtls_mpi_uint) quotient; 1629 #else 1630 1631 /* 1632 * Algorithm D, Section 4.3.1 - The Art of Computer Programming 1633 * Vol. 2 - Seminumerical Algorithms, Knuth 1634 */ 1635 1636 /* 1637 * Normalize the divisor, d, and dividend, u0, u1 1638 */ 1639 s = mbedtls_clz( d ); 1640 d = d << s; 1641 1642 u1 = u1 << s; 1643 u1 |= ( u0 >> ( biL - s ) ) & ( -(mbedtls_mpi_sint)s >> ( biL - 1 ) ); 1644 u0 = u0 << s; 1645 1646 d1 = d >> biH; 1647 d0 = d & uint_halfword_mask; 1648 1649 u0_msw = u0 >> biH; 1650 u0_lsw = u0 & uint_halfword_mask; 1651 1652 /* 1653 * Find the first quotient and remainder 1654 */ 1655 q1 = u1 / d1; 1656 r0 = u1 - d1 * q1; 1657 1658 while( q1 >= radix || ( q1 * d0 > radix * r0 + u0_msw ) ) 1659 { 1660 q1 -= 1; 1661 r0 += d1; 1662 1663 if ( r0 >= radix ) break; 1664 } 1665 1666 rAX = ( u1 * radix ) + ( u0_msw - q1 * d ); 1667 q0 = rAX / d1; 1668 r0 = rAX - q0 * d1; 1669 1670 while( q0 >= radix || ( q0 * d0 > radix * r0 + u0_lsw ) ) 1671 { 1672 q0 -= 1; 1673 r0 += d1; 1674 1675 if ( r0 >= radix ) break; 1676 } 1677 1678 if (r != NULL) 1679 *r = ( rAX * radix + u0_lsw - q0 * d ) >> s; 1680 1681 quotient = q1 * radix + q0; 1682 1683 return quotient; 1684 #endif 1685 } 1686 1687 /* 1688 * Division by mbedtls_mpi: A = Q * B + R (HAC 14.20) 1689 */ 1690 int mbedtls_mpi_div_mpi( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A, 1691 const mbedtls_mpi *B ) 1692 { 1693 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1694 size_t i, n, t, k; 1695 mbedtls_mpi X, Y, Z, T1, T2; 1696 mbedtls_mpi_uint TP2[3]; 1697 MPI_VALIDATE_RET( A != NULL ); 1698 MPI_VALIDATE_RET( B != NULL ); 1699 1700 if( mbedtls_mpi_cmp_int( B, 0 ) == 0 ) 1701 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO ); 1702 1703 mbedtls_mpi_init_mempool( &X ); mbedtls_mpi_init_mempool( &Y ); 1704 mbedtls_mpi_init_mempool( &Z ); mbedtls_mpi_init_mempool( &T1 ); 1705 /* 1706 * Avoid dynamic memory allocations for constant-size T2. 1707 * 1708 * T2 is used for comparison only and the 3 limbs are assigned explicitly, 1709 * so nobody increase the size of the MPI and we're safe to use an on-stack 1710 * buffer. 1711 */ 1712 T2.s = 1; 1713 T2.n = sizeof( TP2 ) / sizeof( *TP2 ); 1714 T2.p = TP2; 1715 1716 if( mbedtls_mpi_cmp_abs( A, B ) < 0 ) 1717 { 1718 if( Q != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_lset( Q, 0 ) ); 1719 if( R != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, A ) ); 1720 return( 0 ); 1721 } 1722 1723 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &X, A ) ); 1724 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, B ) ); 1725 X.s = Y.s = 1; 1726 1727 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &Z, A->n + 2 ) ); 1728 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Z, 0 ) ); 1729 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T1, A->n + 2 ) ); 1730 1731 k = mbedtls_mpi_bitlen( &Y ) % biL; 1732 if( k < biL - 1 ) 1733 { 1734 k = biL - 1 - k; 1735 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &X, k ) ); 1736 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, k ) ); 1737 } 1738 else k = 0; 1739 1740 n = X.n - 1; 1741 t = Y.n - 1; 1742 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, biL * ( n - t ) ) ); 1743 1744 while( mbedtls_mpi_cmp_mpi( &X, &Y ) >= 0 ) 1745 { 1746 Z.p[n - t]++; 1747 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &Y ) ); 1748 } 1749 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, biL * ( n - t ) ) ); 1750 1751 for( i = n; i > t ; i-- ) 1752 { 1753 if( X.p[i] >= Y.p[t] ) 1754 Z.p[i - t - 1] = ~0; 1755 else 1756 { 1757 Z.p[i - t - 1] = mbedtls_int_div_int( X.p[i], X.p[i - 1], 1758 Y.p[t], NULL); 1759 } 1760 1761 T2.p[0] = ( i < 2 ) ? 0 : X.p[i - 2]; 1762 T2.p[1] = ( i < 1 ) ? 0 : X.p[i - 1]; 1763 T2.p[2] = X.p[i]; 1764 1765 Z.p[i - t - 1]++; 1766 do 1767 { 1768 Z.p[i - t - 1]--; 1769 1770 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &T1, 0 ) ); 1771 T1.p[0] = ( t < 1 ) ? 0 : Y.p[t - 1]; 1772 T1.p[1] = Y.p[t]; 1773 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &T1, Z.p[i - t - 1] ) ); 1774 } 1775 while( mbedtls_mpi_cmp_mpi( &T1, &T2 ) > 0 ); 1776 1777 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &Y, Z.p[i - t - 1] ) ); 1778 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) ); 1779 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T1 ) ); 1780 1781 if( mbedtls_mpi_cmp_int( &X, 0 ) < 0 ) 1782 { 1783 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T1, &Y ) ); 1784 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) ); 1785 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &X, &X, &T1 ) ); 1786 Z.p[i - t - 1]--; 1787 } 1788 } 1789 1790 if( Q != NULL ) 1791 { 1792 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( Q, &Z ) ); 1793 Q->s = A->s * B->s; 1794 } 1795 1796 if( R != NULL ) 1797 { 1798 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &X, k ) ); 1799 X.s = A->s; 1800 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, &X ) ); 1801 1802 if( mbedtls_mpi_cmp_int( R, 0 ) == 0 ) 1803 R->s = 1; 1804 } 1805 1806 cleanup: 1807 1808 mbedtls_mpi_free( &X ); mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &Z ); 1809 mbedtls_mpi_free( &T1 ); 1810 mbedtls_platform_zeroize( TP2, sizeof( TP2 ) ); 1811 1812 return( ret ); 1813 } 1814 1815 /* 1816 * Division by int: A = Q * b + R 1817 */ 1818 int mbedtls_mpi_div_int( mbedtls_mpi *Q, mbedtls_mpi *R, 1819 const mbedtls_mpi *A, 1820 mbedtls_mpi_sint b ) 1821 { 1822 mbedtls_mpi B; 1823 mbedtls_mpi_uint p[1]; 1824 MPI_VALIDATE_RET( A != NULL ); 1825 1826 p[0] = ( b < 0 ) ? -b : b; 1827 B.s = ( b < 0 ) ? -1 : 1; 1828 B.n = 1; 1829 B.p = p; 1830 1831 return( mbedtls_mpi_div_mpi( Q, R, A, &B ) ); 1832 } 1833 1834 /* 1835 * Modulo: R = A mod B 1836 */ 1837 int mbedtls_mpi_mod_mpi( mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B ) 1838 { 1839 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1840 MPI_VALIDATE_RET( R != NULL ); 1841 MPI_VALIDATE_RET( A != NULL ); 1842 MPI_VALIDATE_RET( B != NULL ); 1843 1844 if( mbedtls_mpi_cmp_int( B, 0 ) < 0 ) 1845 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE ); 1846 1847 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( NULL, R, A, B ) ); 1848 1849 while( mbedtls_mpi_cmp_int( R, 0 ) < 0 ) 1850 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( R, R, B ) ); 1851 1852 while( mbedtls_mpi_cmp_mpi( R, B ) >= 0 ) 1853 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( R, R, B ) ); 1854 1855 cleanup: 1856 1857 return( ret ); 1858 } 1859 1860 /* 1861 * Modulo: r = A mod b 1862 */ 1863 int mbedtls_mpi_mod_int( mbedtls_mpi_uint *r, const mbedtls_mpi *A, mbedtls_mpi_sint b ) 1864 { 1865 size_t i; 1866 mbedtls_mpi_uint x, y, z; 1867 MPI_VALIDATE_RET( r != NULL ); 1868 MPI_VALIDATE_RET( A != NULL ); 1869 1870 if( b == 0 ) 1871 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO ); 1872 1873 if( b < 0 ) 1874 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE ); 1875 1876 /* 1877 * handle trivial cases 1878 */ 1879 if( b == 1 || A->n == 0 ) 1880 { 1881 *r = 0; 1882 return( 0 ); 1883 } 1884 1885 if( b == 2 ) 1886 { 1887 *r = A->p[0] & 1; 1888 return( 0 ); 1889 } 1890 1891 /* 1892 * general case 1893 */ 1894 for( i = A->n, y = 0; i > 0; i-- ) 1895 { 1896 x = A->p[i - 1]; 1897 y = ( y << biH ) | ( x >> biH ); 1898 z = y / b; 1899 y -= z * b; 1900 1901 x <<= biH; 1902 y = ( y << biH ) | ( x >> biH ); 1903 z = y / b; 1904 y -= z * b; 1905 } 1906 1907 /* 1908 * If A is negative, then the current y represents a negative value. 1909 * Flipping it to the positive side. 1910 */ 1911 if( A->s < 0 && y != 0 ) 1912 y = b - y; 1913 1914 *r = y; 1915 1916 return( 0 ); 1917 } 1918 1919 /* 1920 * Fast Montgomery initialization (thanks to Tom St Denis) 1921 */ 1922 static void mpi_montg_init( mbedtls_mpi_uint *mm, const mbedtls_mpi *N ) 1923 { 1924 mbedtls_mpi_uint x, m0 = N->p[0]; 1925 unsigned int i; 1926 1927 x = m0; 1928 x += ( ( m0 + 2 ) & 4 ) << 1; 1929 1930 for( i = biL; i >= 8; i /= 2 ) 1931 x *= ( 2 - ( m0 * x ) ); 1932 1933 *mm = ~x + 1; 1934 } 1935 1936 void mbedtls_mpi_montg_init( mbedtls_mpi_uint *mm, const mbedtls_mpi *N ) 1937 { 1938 mpi_montg_init( mm, N ); 1939 } 1940 1941 /** Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36) 1942 * 1943 * \param[in,out] A One of the numbers to multiply. 1944 * It must have at least as many limbs as N 1945 * (A->n >= N->n), and any limbs beyond n are ignored. 1946 * On successful completion, A contains the result of 1947 * the multiplication A * B * R^-1 mod N where 1948 * R = (2^ciL)^n. 1949 * \param[in] B One of the numbers to multiply. 1950 * It must be nonzero and must not have more limbs than N 1951 * (B->n <= N->n). 1952 * \param[in] N The modulo. N must be odd. 1953 * \param mm The value calculated by `mpi_montg_init(&mm, N)`. 1954 * This is -N^-1 mod 2^ciL. 1955 * \param[in,out] T A bignum for temporary storage. 1956 * It must be at least twice the limb size of N plus 2 1957 * (T->n >= 2 * (N->n + 1)). 1958 * Its initial content is unused and 1959 * its final content is indeterminate. 1960 * Note that unlike the usual convention in the library 1961 * for `const mbedtls_mpi*`, the content of T can change. 1962 */ 1963 static void mpi_montmul( mbedtls_mpi *A, const mbedtls_mpi *B, const mbedtls_mpi *N, mbedtls_mpi_uint mm, 1964 const mbedtls_mpi *T ) 1965 { 1966 size_t i, n, m; 1967 mbedtls_mpi_uint u0, u1, *d; 1968 1969 memset( T->p, 0, T->n * ciL ); 1970 1971 d = T->p; 1972 n = N->n; 1973 m = ( B->n < n ) ? B->n : n; 1974 1975 for( i = 0; i < n; i++ ) 1976 { 1977 /* 1978 * T = (T + u0*B + u1*N) / 2^biL 1979 */ 1980 u0 = A->p[i]; 1981 u1 = ( d[0] + u0 * B->p[0] ) * mm; 1982 1983 mpi_mul_hlp( m, B->p, d, u0 ); 1984 mpi_mul_hlp( n, N->p, d, u1 ); 1985 1986 *d++ = u0; d[n + 1] = 0; 1987 } 1988 1989 /* At this point, d is either the desired result or the desired result 1990 * plus N. We now potentially subtract N, avoiding leaking whether the 1991 * subtraction is performed through side channels. */ 1992 1993 /* Copy the n least significant limbs of d to A, so that 1994 * A = d if d < N (recall that N has n limbs). */ 1995 memcpy( A->p, d, n * ciL ); 1996 /* If d >= N then we want to set A to d - N. To prevent timing attacks, 1997 * do the calculation without using conditional tests. */ 1998 /* Set d to d0 + (2^biL)^n - N where d0 is the current value of d. */ 1999 d[n] += 1; 2000 d[n] -= mpi_sub_hlp( n, d, d, N->p ); 2001 /* If d0 < N then d < (2^biL)^n 2002 * so d[n] == 0 and we want to keep A as it is. 2003 * If d0 >= N then d >= (2^biL)^n, and d <= (2^biL)^n + N < 2 * (2^biL)^n 2004 * so d[n] == 1 and we want to set A to the result of the subtraction 2005 * which is d - (2^biL)^n, i.e. the n least significant limbs of d. 2006 * This exactly corresponds to a conditional assignment. */ 2007 mbedtls_ct_mpi_uint_cond_assign( n, A->p, d, (unsigned char) d[n] ); 2008 } 2009 2010 void mbedtls_mpi_montmul( mbedtls_mpi *A, const mbedtls_mpi *B, const mbedtls_mpi *N, mbedtls_mpi_uint mm, 2011 const mbedtls_mpi *T ) 2012 { 2013 mpi_montmul( A, B, N, mm, T); 2014 } 2015 2016 /* 2017 * Montgomery reduction: A = A * R^-1 mod N 2018 * 2019 * See mpi_montmul() regarding constraints and guarantees on the parameters. 2020 */ 2021 static void mpi_montred( mbedtls_mpi *A, const mbedtls_mpi *N, 2022 mbedtls_mpi_uint mm, const mbedtls_mpi *T ) 2023 { 2024 mbedtls_mpi_uint z = 1; 2025 mbedtls_mpi U; 2026 2027 U.n = U.s = (int) z; 2028 U.p = &z; 2029 2030 mpi_montmul( A, &U, N, mm, T ); 2031 } 2032 2033 void mbedtls_mpi_montred( mbedtls_mpi *A, const mbedtls_mpi *N, 2034 mbedtls_mpi_uint mm, const mbedtls_mpi *T ) 2035 { 2036 mpi_montred( A, N, mm, T ); 2037 } 2038 2039 /** 2040 * Select an MPI from a table without leaking the index. 2041 * 2042 * This is functionally equivalent to mbedtls_mpi_copy(R, T[idx]) except it 2043 * reads the entire table in order to avoid leaking the value of idx to an 2044 * attacker able to observe memory access patterns. 2045 * 2046 * \param[out] R Where to write the selected MPI. 2047 * \param[in] T The table to read from. 2048 * \param[in] T_size The number of elements in the table. 2049 * \param[in] idx The index of the element to select; 2050 * this must satisfy 0 <= idx < T_size. 2051 * 2052 * \return \c 0 on success, or a negative error code. 2053 */ 2054 static int mpi_select( mbedtls_mpi *R, const mbedtls_mpi *T, size_t T_size, size_t idx ) 2055 { 2056 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2057 2058 for( size_t i = 0; i < T_size; i++ ) 2059 { 2060 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( R, &T[i], 2061 (unsigned char) mbedtls_ct_size_bool_eq( i, idx ) ) ); 2062 } 2063 2064 cleanup: 2065 return( ret ); 2066 } 2067 2068 /* 2069 * Sliding-window exponentiation: X = A^E mod N (HAC 14.85) 2070 */ 2071 int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A, 2072 const mbedtls_mpi *E, const mbedtls_mpi *N, 2073 mbedtls_mpi *prec_RR ) 2074 { 2075 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2076 size_t wbits, wsize, one = 1; 2077 size_t i, j, nblimbs; 2078 size_t bufsize, nbits; 2079 mbedtls_mpi_uint ei, mm, state; 2080 mbedtls_mpi RR, T, WW, Apos; 2081 mbedtls_mpi *W = NULL; 2082 const size_t array_size_W = 2 << MBEDTLS_MPI_WINDOW_SIZE; 2083 int neg; 2084 2085 MPI_VALIDATE_RET( X != NULL ); 2086 MPI_VALIDATE_RET( A != NULL ); 2087 MPI_VALIDATE_RET( E != NULL ); 2088 MPI_VALIDATE_RET( N != NULL ); 2089 2090 if( mbedtls_mpi_cmp_int( N, 0 ) <= 0 || ( N->p[0] & 1 ) == 0 ) 2091 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); 2092 2093 if( mbedtls_mpi_cmp_int( E, 0 ) < 0 ) 2094 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); 2095 2096 if( mbedtls_mpi_bitlen( E ) > MBEDTLS_MPI_MAX_BITS || 2097 mbedtls_mpi_bitlen( N ) > MBEDTLS_MPI_MAX_BITS ) 2098 return ( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); 2099 2100 /* 2101 * Init temps and window size 2102 */ 2103 mpi_montg_init( &mm, N ); 2104 mbedtls_mpi_init_mempool( &RR ); mbedtls_mpi_init( &T ); 2105 mbedtls_mpi_init_mempool( &Apos ); 2106 mbedtls_mpi_init_mempool( &WW ); 2107 2108 i = mbedtls_mpi_bitlen( E ); 2109 2110 wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 : 2111 ( i > 79 ) ? 4 : ( i > 23 ) ? 3 : 1; 2112 2113 #if( MBEDTLS_MPI_WINDOW_SIZE < 6 ) 2114 if( wsize > MBEDTLS_MPI_WINDOW_SIZE ) 2115 wsize = MBEDTLS_MPI_WINDOW_SIZE; 2116 #endif 2117 2118 j = N->n + 1; 2119 /* All W[i] and X must have at least N->n limbs for the mpi_montmul() 2120 * and mpi_montred() calls later. Here we ensure that W[1] and X are 2121 * large enough, and later we'll grow other W[i] to the same length. 2122 * They must not be shrunk midway through this function! 2123 */ 2124 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) ); 2125 2126 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T, j * 2 ) ); 2127 2128 /* 2129 * Compensate for negative A (and correct at the end) 2130 */ 2131 neg = ( A->s == -1 ); 2132 if( neg ) 2133 { 2134 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Apos, A ) ); 2135 Apos.s = 1; 2136 A = &Apos; 2137 } 2138 2139 /* 2140 * If 1st call, pre-compute R^2 mod N 2141 */ 2142 if( prec_RR == NULL || prec_RR->p == NULL ) 2143 { 2144 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &RR, 1 ) ); 2145 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &RR, N->n * 2 * biL ) ); 2146 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &RR, &RR, N ) ); 2147 2148 if( prec_RR != NULL ) 2149 memcpy( prec_RR, &RR, sizeof( mbedtls_mpi ) ); 2150 } 2151 else 2152 memcpy( &RR, prec_RR, sizeof( mbedtls_mpi ) ); 2153 2154 W = mempool_alloc( mbedtls_mpi_mempool, 2155 sizeof( mbedtls_mpi ) * array_size_W ); 2156 if( W == NULL ) { 2157 ret = MBEDTLS_ERR_MPI_ALLOC_FAILED; 2158 goto cleanup; 2159 } 2160 for( i = 0; i < array_size_W; i++ ) 2161 mbedtls_mpi_init_mempool( W + i ); 2162 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[1], j ) ); 2163 2164 /* 2165 * W[1] = A * R^2 * R^-1 mod N = A * R mod N 2166 */ 2167 if( mbedtls_mpi_cmp_mpi( A, N ) >= 0 ) 2168 { 2169 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &W[1], A, N ) ); 2170 /* This should be a no-op because W[1] is already that large before 2171 * mbedtls_mpi_mod_mpi(), but it's necessary to avoid an overflow 2172 * in mpi_montmul() below, so let's make sure. */ 2173 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[1], N->n + 1 ) ); 2174 } 2175 else 2176 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[1], A ) ); 2177 2178 /* Note that this is safe because W[1] always has at least N->n limbs 2179 * (it grew above and was preserved by mbedtls_mpi_copy()). */ 2180 mpi_montmul( &W[1], &RR, N, mm, &T ); 2181 2182 /* 2183 * X = R^2 * R^-1 mod N = R mod N 2184 */ 2185 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &RR ) ); 2186 mpi_montred( X, N, mm, &T ); 2187 2188 if( wsize > 1 ) 2189 { 2190 /* 2191 * W[1 << (wsize - 1)] = W[1] ^ (wsize - 1) 2192 */ 2193 j = one << ( wsize - 1 ); 2194 2195 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[j], N->n + 1 ) ); 2196 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[j], &W[1] ) ); 2197 2198 for( i = 0; i < wsize - 1; i++ ) 2199 mpi_montmul( &W[j], &W[j], N, mm, &T ); 2200 2201 /* 2202 * W[i] = W[i - 1] * W[1] 2203 */ 2204 for( i = j + 1; i < ( one << wsize ); i++ ) 2205 { 2206 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[i], N->n + 1 ) ); 2207 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[i], &W[i - 1] ) ); 2208 2209 mpi_montmul( &W[i], &W[1], N, mm, &T ); 2210 } 2211 } 2212 2213 nblimbs = E->n; 2214 bufsize = 0; 2215 nbits = 0; 2216 wbits = 0; 2217 state = 0; 2218 2219 while( 1 ) 2220 { 2221 if( bufsize == 0 ) 2222 { 2223 if( nblimbs == 0 ) 2224 break; 2225 2226 nblimbs--; 2227 2228 bufsize = sizeof( mbedtls_mpi_uint ) << 3; 2229 } 2230 2231 bufsize--; 2232 2233 ei = (E->p[nblimbs] >> bufsize) & 1; 2234 2235 /* 2236 * skip leading 0s 2237 */ 2238 if( ei == 0 && state == 0 ) 2239 continue; 2240 2241 if( ei == 0 && state == 1 ) 2242 { 2243 /* 2244 * out of window, square X 2245 */ 2246 mpi_montmul( X, X, N, mm, &T ); 2247 continue; 2248 } 2249 2250 /* 2251 * add ei to current window 2252 */ 2253 state = 2; 2254 2255 nbits++; 2256 wbits |= ( ei << ( wsize - nbits ) ); 2257 2258 if( nbits == wsize ) 2259 { 2260 /* 2261 * X = X^wsize R^-1 mod N 2262 */ 2263 for( i = 0; i < wsize; i++ ) 2264 mpi_montmul( X, X, N, mm, &T ); 2265 2266 /* 2267 * X = X * W[wbits] R^-1 mod N 2268 */ 2269 MBEDTLS_MPI_CHK( mpi_select( &WW, W, (size_t) 1 << wsize, wbits ) ); 2270 mpi_montmul( X, &WW, N, mm, &T ); 2271 2272 state--; 2273 nbits = 0; 2274 wbits = 0; 2275 } 2276 } 2277 2278 /* 2279 * process the remaining bits 2280 */ 2281 for( i = 0; i < nbits; i++ ) 2282 { 2283 mpi_montmul( X, X, N, mm, &T ); 2284 2285 wbits <<= 1; 2286 2287 if( ( wbits & ( one << wsize ) ) != 0 ) 2288 mpi_montmul( X, &W[1], N, mm, &T ); 2289 } 2290 2291 /* 2292 * X = A^E * R * R^-1 mod N = A^E mod N 2293 */ 2294 mpi_montred( X, N, mm, &T ); 2295 2296 if( neg && E->n != 0 && ( E->p[0] & 1 ) != 0 ) 2297 { 2298 X->s = -1; 2299 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( X, N, X ) ); 2300 } 2301 2302 cleanup: 2303 2304 if( W ) 2305 for( i = 0; i < array_size_W; i++ ) 2306 mbedtls_mpi_free( W + i ); 2307 mempool_free( mbedtls_mpi_mempool , W ); 2308 2309 mbedtls_mpi_free( &T ); mbedtls_mpi_free( &Apos ); 2310 mbedtls_mpi_free( &WW ); 2311 2312 if( prec_RR == NULL || prec_RR->p == NULL ) 2313 mbedtls_mpi_free( &RR ); 2314 2315 return( ret ); 2316 } 2317 2318 /* 2319 * Greatest common divisor: G = gcd(A, B) (HAC 14.54) 2320 */ 2321 int mbedtls_mpi_gcd( mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B ) 2322 { 2323 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2324 size_t lz, lzt; 2325 mbedtls_mpi TA, TB; 2326 2327 MPI_VALIDATE_RET( G != NULL ); 2328 MPI_VALIDATE_RET( A != NULL ); 2329 MPI_VALIDATE_RET( B != NULL ); 2330 2331 mbedtls_mpi_init_mempool( &TA ); mbedtls_mpi_init_mempool( &TB ); 2332 2333 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) ); 2334 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) ); 2335 2336 lz = mbedtls_mpi_lsb( &TA ); 2337 lzt = mbedtls_mpi_lsb( &TB ); 2338 2339 /* The loop below gives the correct result when A==0 but not when B==0. 2340 * So have a special case for B==0. Leverage the fact that we just 2341 * calculated the lsb and lsb(B)==0 iff B is odd or 0 to make the test 2342 * slightly more efficient than cmp_int(). */ 2343 if( lzt == 0 && mbedtls_mpi_get_bit( &TB, 0 ) == 0 ) 2344 { 2345 ret = mbedtls_mpi_copy( G, A ); 2346 goto cleanup; 2347 } 2348 2349 if( lzt < lz ) 2350 lz = lzt; 2351 2352 TA.s = TB.s = 1; 2353 2354 /* We mostly follow the procedure described in HAC 14.54, but with some 2355 * minor differences: 2356 * - Sequences of multiplications or divisions by 2 are grouped into a 2357 * single shift operation. 2358 * - The procedure in HAC assumes that 0 < TB <= TA. 2359 * - The condition TB <= TA is not actually necessary for correctness. 2360 * TA and TB have symmetric roles except for the loop termination 2361 * condition, and the shifts at the beginning of the loop body 2362 * remove any significance from the ordering of TA vs TB before 2363 * the shifts. 2364 * - If TA = 0, the loop goes through 0 iterations and the result is 2365 * correctly TB. 2366 * - The case TB = 0 was short-circuited above. 2367 * 2368 * For the correctness proof below, decompose the original values of 2369 * A and B as 2370 * A = sa * 2^a * A' with A'=0 or A' odd, and sa = +-1 2371 * B = sb * 2^b * B' with B'=0 or B' odd, and sb = +-1 2372 * Then gcd(A, B) = 2^{min(a,b)} * gcd(A',B'), 2373 * and gcd(A',B') is odd or 0. 2374 * 2375 * At the beginning, we have TA = |A| and TB = |B| so gcd(A,B) = gcd(TA,TB). 2376 * The code maintains the following invariant: 2377 * gcd(A,B) = 2^k * gcd(TA,TB) for some k (I) 2378 */ 2379 2380 /* Proof that the loop terminates: 2381 * At each iteration, either the right-shift by 1 is made on a nonzero 2382 * value and the nonnegative integer bitlen(TA) + bitlen(TB) decreases 2383 * by at least 1, or the right-shift by 1 is made on zero and then 2384 * TA becomes 0 which ends the loop (TB cannot be 0 if it is right-shifted 2385 * since in that case TB is calculated from TB-TA with the condition TB>TA). 2386 */ 2387 while( mbedtls_mpi_cmp_int( &TA, 0 ) != 0 ) 2388 { 2389 /* Divisions by 2 preserve the invariant (I). */ 2390 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, mbedtls_mpi_lsb( &TA ) ) ); 2391 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, mbedtls_mpi_lsb( &TB ) ) ); 2392 2393 /* Set either TA or TB to |TA-TB|/2. Since TA and TB are both odd, 2394 * TA-TB is even so the division by 2 has an integer result. 2395 * Invariant (I) is preserved since any odd divisor of both TA and TB 2396 * also divides |TA-TB|/2, and any odd divisor of both TA and |TA-TB|/2 2397 * also divides TB, and any odd divisor of both TB and |TA-TB|/2 also 2398 * divides TA. 2399 */ 2400 if( mbedtls_mpi_cmp_mpi( &TA, &TB ) >= 0 ) 2401 { 2402 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TA, &TA, &TB ) ); 2403 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, 1 ) ); 2404 } 2405 else 2406 { 2407 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TB, &TB, &TA ) ); 2408 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, 1 ) ); 2409 } 2410 /* Note that one of TA or TB is still odd. */ 2411 } 2412 2413 /* By invariant (I), gcd(A,B) = 2^k * gcd(TA,TB) for some k. 2414 * At the loop exit, TA = 0, so gcd(TA,TB) = TB. 2415 * - If there was at least one loop iteration, then one of TA or TB is odd, 2416 * and TA = 0, so TB is odd and gcd(TA,TB) = gcd(A',B'). In this case, 2417 * lz = min(a,b) so gcd(A,B) = 2^lz * TB. 2418 * - If there was no loop iteration, then A was 0, and gcd(A,B) = B. 2419 * In this case, lz = 0 and B = TB so gcd(A,B) = B = 2^lz * TB as well. 2420 */ 2421 2422 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &TB, lz ) ); 2423 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( G, &TB ) ); 2424 2425 cleanup: 2426 2427 mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TB ); 2428 2429 return( ret ); 2430 } 2431 2432 /* Fill X with n_bytes random bytes. 2433 * X must already have room for those bytes. 2434 * The ordering of the bytes returned from the RNG is suitable for 2435 * deterministic ECDSA (see RFC 6979 §3.3 and mbedtls_mpi_random()). 2436 * The size and sign of X are unchanged. 2437 * n_bytes must not be 0. 2438 */ 2439 static int mpi_fill_random_internal( 2440 mbedtls_mpi *X, size_t n_bytes, 2441 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng ) 2442 { 2443 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2444 const size_t limbs = CHARS_TO_LIMBS( n_bytes ); 2445 const size_t overhead = ( limbs * ciL ) - n_bytes; 2446 2447 if( X->n < limbs ) 2448 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); 2449 2450 memset( X->p, 0, overhead ); 2451 memset( (unsigned char *) X->p + limbs * ciL, 0, ( X->n - limbs ) * ciL ); 2452 MBEDTLS_MPI_CHK( f_rng( p_rng, (unsigned char *) X->p + overhead, n_bytes ) ); 2453 mpi_bigendian_to_host( X->p, limbs ); 2454 2455 cleanup: 2456 return( ret ); 2457 } 2458 2459 /* 2460 * Fill X with size bytes of random. 2461 * 2462 * Use a temporary bytes representation to make sure the result is the same 2463 * regardless of the platform endianness (useful when f_rng is actually 2464 * deterministic, eg for tests). 2465 */ 2466 int mbedtls_mpi_fill_random( mbedtls_mpi *X, size_t size, 2467 int (*f_rng)(void *, unsigned char *, size_t), 2468 void *p_rng ) 2469 { 2470 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2471 size_t const limbs = CHARS_TO_LIMBS( size ); 2472 2473 MPI_VALIDATE_RET( X != NULL ); 2474 MPI_VALIDATE_RET( f_rng != NULL ); 2475 2476 /* Ensure that target MPI has exactly the necessary number of limbs */ 2477 MBEDTLS_MPI_CHK( mbedtls_mpi_resize_clear( X, limbs ) ); 2478 if( size == 0 ) 2479 return( 0 ); 2480 2481 ret = mpi_fill_random_internal( X, size, f_rng, p_rng ); 2482 2483 cleanup: 2484 return( ret ); 2485 } 2486 2487 int mbedtls_mpi_random( mbedtls_mpi *X, 2488 mbedtls_mpi_sint min, 2489 const mbedtls_mpi *N, 2490 int (*f_rng)(void *, unsigned char *, size_t), 2491 void *p_rng ) 2492 { 2493 int ret = MBEDTLS_ERR_MPI_BAD_INPUT_DATA; 2494 int count; 2495 unsigned lt_lower = 1, lt_upper = 0; 2496 size_t n_bits = mbedtls_mpi_bitlen( N ); 2497 size_t n_bytes = ( n_bits + 7 ) / 8; 2498 mbedtls_mpi lower_bound; 2499 2500 if( min < 0 ) 2501 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); 2502 if( mbedtls_mpi_cmp_int( N, min ) <= 0 ) 2503 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); 2504 2505 /* 2506 * When min == 0, each try has at worst a probability 1/2 of failing 2507 * (the msb has a probability 1/2 of being 0, and then the result will 2508 * be < N), so after 30 tries failure probability is a most 2**(-30). 2509 * 2510 * When N is just below a power of 2, as is the case when generating 2511 * a random scalar on most elliptic curves, 1 try is enough with 2512 * overwhelming probability. When N is just above a power of 2, 2513 * as when generating a random scalar on secp224k1, each try has 2514 * a probability of failing that is almost 1/2. 2515 * 2516 * The probabilities are almost the same if min is nonzero but negligible 2517 * compared to N. This is always the case when N is crypto-sized, but 2518 * it's convenient to support small N for testing purposes. When N 2519 * is small, use a higher repeat count, otherwise the probability of 2520 * failure is macroscopic. 2521 */ 2522 count = ( n_bytes > 4 ? 30 : 250 ); 2523 2524 mbedtls_mpi_init( &lower_bound ); 2525 2526 /* Ensure that target MPI has exactly the same number of limbs 2527 * as the upper bound, even if the upper bound has leading zeros. 2528 * This is necessary for the mbedtls_mpi_lt_mpi_ct() check. */ 2529 MBEDTLS_MPI_CHK( mbedtls_mpi_resize_clear( X, N->n ) ); 2530 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &lower_bound, N->n ) ); 2531 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &lower_bound, min ) ); 2532 2533 /* 2534 * Match the procedure given in RFC 6979 §3.3 (deterministic ECDSA) 2535 * when f_rng is a suitably parametrized instance of HMAC_DRBG: 2536 * - use the same byte ordering; 2537 * - keep the leftmost n_bits bits of the generated octet string; 2538 * - try until result is in the desired range. 2539 * This also avoids any bias, which is especially important for ECDSA. 2540 */ 2541 do 2542 { 2543 MBEDTLS_MPI_CHK( mpi_fill_random_internal( X, n_bytes, f_rng, p_rng ) ); 2544 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( X, 8 * n_bytes - n_bits ) ); 2545 2546 if( --count == 0 ) 2547 { 2548 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; 2549 goto cleanup; 2550 } 2551 2552 MBEDTLS_MPI_CHK( mbedtls_mpi_lt_mpi_ct( X, &lower_bound, <_lower ) ); 2553 MBEDTLS_MPI_CHK( mbedtls_mpi_lt_mpi_ct( X, N, <_upper ) ); 2554 } 2555 while( lt_lower != 0 || lt_upper == 0 ); 2556 2557 cleanup: 2558 mbedtls_mpi_free( &lower_bound ); 2559 return( ret ); 2560 } 2561 2562 /* 2563 * Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64) 2564 */ 2565 int mbedtls_mpi_inv_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N ) 2566 { 2567 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2568 mbedtls_mpi G, TA, TU, U1, U2, TB, TV, V1, V2; 2569 MPI_VALIDATE_RET( X != NULL ); 2570 MPI_VALIDATE_RET( A != NULL ); 2571 MPI_VALIDATE_RET( N != NULL ); 2572 2573 if( mbedtls_mpi_cmp_int( N, 1 ) <= 0 ) 2574 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); 2575 2576 mbedtls_mpi_init_mempool( &TA ); mbedtls_mpi_init_mempool( &TU ); 2577 mbedtls_mpi_init_mempool( &U1 ); mbedtls_mpi_init_mempool( &U2 ); 2578 mbedtls_mpi_init_mempool( &G ); mbedtls_mpi_init_mempool( &TB ); 2579 mbedtls_mpi_init_mempool( &TV ); mbedtls_mpi_init_mempool( &V1 ); 2580 mbedtls_mpi_init_mempool( &V2 ); 2581 2582 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &G, A, N ) ); 2583 2584 if( mbedtls_mpi_cmp_int( &G, 1 ) != 0 ) 2585 { 2586 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; 2587 goto cleanup; 2588 } 2589 2590 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &TA, A, N ) ); 2591 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TU, &TA ) ); 2592 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, N ) ); 2593 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TV, N ) ); 2594 2595 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U1, 1 ) ); 2596 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U2, 0 ) ); 2597 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V1, 0 ) ); 2598 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V2, 1 ) ); 2599 2600 do 2601 { 2602 while( ( TU.p[0] & 1 ) == 0 ) 2603 { 2604 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TU, 1 ) ); 2605 2606 if( ( U1.p[0] & 1 ) != 0 || ( U2.p[0] & 1 ) != 0 ) 2607 { 2608 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &U1, &U1, &TB ) ); 2609 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &TA ) ); 2610 } 2611 2612 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U1, 1 ) ); 2613 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U2, 1 ) ); 2614 } 2615 2616 while( ( TV.p[0] & 1 ) == 0 ) 2617 { 2618 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TV, 1 ) ); 2619 2620 if( ( V1.p[0] & 1 ) != 0 || ( V2.p[0] & 1 ) != 0 ) 2621 { 2622 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, &TB ) ); 2623 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &TA ) ); 2624 } 2625 2626 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V1, 1 ) ); 2627 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V2, 1 ) ); 2628 } 2629 2630 if( mbedtls_mpi_cmp_mpi( &TU, &TV ) >= 0 ) 2631 { 2632 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TU, &TU, &TV ) ); 2633 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U1, &U1, &V1 ) ); 2634 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &V2 ) ); 2635 } 2636 else 2637 { 2638 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TV, &TV, &TU ) ); 2639 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, &U1 ) ); 2640 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &U2 ) ); 2641 } 2642 } 2643 while( mbedtls_mpi_cmp_int( &TU, 0 ) != 0 ); 2644 2645 while( mbedtls_mpi_cmp_int( &V1, 0 ) < 0 ) 2646 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, N ) ); 2647 2648 while( mbedtls_mpi_cmp_mpi( &V1, N ) >= 0 ) 2649 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, N ) ); 2650 2651 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &V1 ) ); 2652 2653 cleanup: 2654 2655 mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TU ); mbedtls_mpi_free( &U1 ); mbedtls_mpi_free( &U2 ); 2656 mbedtls_mpi_free( &G ); mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TV ); 2657 mbedtls_mpi_free( &V1 ); mbedtls_mpi_free( &V2 ); 2658 2659 return( ret ); 2660 } 2661 2662 #if defined(MBEDTLS_GENPRIME) 2663 2664 static const int small_prime[] = 2665 { 2666 3, 5, 7, 11, 13, 17, 19, 23, 2667 29, 31, 37, 41, 43, 47, 53, 59, 2668 61, 67, 71, 73, 79, 83, 89, 97, 2669 101, 103, 107, 109, 113, 127, 131, 137, 2670 139, 149, 151, 157, 163, 167, 173, 179, 2671 181, 191, 193, 197, 199, 211, 223, 227, 2672 229, 233, 239, 241, 251, 257, 263, 269, 2673 271, 277, 281, 283, 293, 307, 311, 313, 2674 317, 331, 337, 347, 349, 353, 359, 367, 2675 373, 379, 383, 389, 397, 401, 409, 419, 2676 421, 431, 433, 439, 443, 449, 457, 461, 2677 463, 467, 479, 487, 491, 499, 503, 509, 2678 521, 523, 541, 547, 557, 563, 569, 571, 2679 577, 587, 593, 599, 601, 607, 613, 617, 2680 619, 631, 641, 643, 647, 653, 659, 661, 2681 673, 677, 683, 691, 701, 709, 719, 727, 2682 733, 739, 743, 751, 757, 761, 769, 773, 2683 787, 797, 809, 811, 821, 823, 827, 829, 2684 839, 853, 857, 859, 863, 877, 881, 883, 2685 887, 907, 911, 919, 929, 937, 941, 947, 2686 953, 967, 971, 977, 983, 991, 997, -103 2687 }; 2688 2689 /* 2690 * Small divisors test (X must be positive) 2691 * 2692 * Return values: 2693 * 0: no small factor (possible prime, more tests needed) 2694 * 1: certain prime 2695 * MBEDTLS_ERR_MPI_NOT_ACCEPTABLE: certain non-prime 2696 * other negative: error 2697 */ 2698 static int mpi_check_small_factors( const mbedtls_mpi *X ) 2699 { 2700 int ret = 0; 2701 size_t i; 2702 mbedtls_mpi_uint r; 2703 2704 if( ( X->p[0] & 1 ) == 0 ) 2705 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE ); 2706 2707 for( i = 0; small_prime[i] > 0; i++ ) 2708 { 2709 if( mbedtls_mpi_cmp_int( X, small_prime[i] ) <= 0 ) 2710 return( 1 ); 2711 2712 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, small_prime[i] ) ); 2713 2714 if( r == 0 ) 2715 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE ); 2716 } 2717 2718 cleanup: 2719 return( ret ); 2720 } 2721 2722 /* 2723 * Miller-Rabin pseudo-primality test (HAC 4.24) 2724 */ 2725 static int mpi_miller_rabin( const mbedtls_mpi *X, size_t rounds, 2726 int (*f_rng)(void *, unsigned char *, size_t), 2727 void *p_rng ) 2728 { 2729 int ret, count; 2730 size_t i, j, k, s; 2731 mbedtls_mpi W, R, T, A, RR; 2732 2733 MPI_VALIDATE_RET( X != NULL ); 2734 MPI_VALIDATE_RET( f_rng != NULL ); 2735 2736 mbedtls_mpi_init_mempool( &W ); mbedtls_mpi_init_mempool( &R ); 2737 mbedtls_mpi_init_mempool( &T ); mbedtls_mpi_init_mempool( &A ); 2738 mbedtls_mpi_init_mempool( &RR ); 2739 2740 /* 2741 * W = |X| - 1 2742 * R = W >> lsb( W ) 2743 */ 2744 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &W, X, 1 ) ); 2745 s = mbedtls_mpi_lsb( &W ); 2746 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R, &W ) ); 2747 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &R, s ) ); 2748 2749 for( i = 0; i < rounds; i++ ) 2750 { 2751 /* 2752 * pick a random A, 1 < A < |X| - 1 2753 */ 2754 count = 0; 2755 do { 2756 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &A, X->n * ciL, f_rng, p_rng ) ); 2757 2758 j = mbedtls_mpi_bitlen( &A ); 2759 k = mbedtls_mpi_bitlen( &W ); 2760 if (j > k) { 2761 A.p[A.n - 1] &= ( (mbedtls_mpi_uint) 1 << ( k - ( A.n - 1 ) * biL - 1 ) ) - 1; 2762 } 2763 2764 if (count++ > 300) { 2765 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; 2766 goto cleanup; 2767 } 2768 2769 } while ( mbedtls_mpi_cmp_mpi( &A, &W ) >= 0 || 2770 mbedtls_mpi_cmp_int( &A, 1 ) <= 0 ); 2771 2772 /* 2773 * A = A^R mod |X| 2774 */ 2775 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &A, &A, &R, X, &RR ) ); 2776 2777 if( mbedtls_mpi_cmp_mpi( &A, &W ) == 0 || 2778 mbedtls_mpi_cmp_int( &A, 1 ) == 0 ) 2779 continue; 2780 2781 j = 1; 2782 while( j < s && mbedtls_mpi_cmp_mpi( &A, &W ) != 0 ) 2783 { 2784 /* 2785 * A = A * A mod |X| 2786 */ 2787 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &A, &A ) ); 2788 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &A, &T, X ) ); 2789 2790 if( mbedtls_mpi_cmp_int( &A, 1 ) == 0 ) 2791 break; 2792 2793 j++; 2794 } 2795 2796 /* 2797 * not prime if A != |X| - 1 or A == 1 2798 */ 2799 if( mbedtls_mpi_cmp_mpi( &A, &W ) != 0 || 2800 mbedtls_mpi_cmp_int( &A, 1 ) == 0 ) 2801 { 2802 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; 2803 break; 2804 } 2805 } 2806 2807 cleanup: 2808 mbedtls_mpi_free( &W ); mbedtls_mpi_free( &R ); 2809 mbedtls_mpi_free( &T ); mbedtls_mpi_free( &A ); 2810 mbedtls_mpi_free( &RR ); 2811 2812 return( ret ); 2813 } 2814 2815 /* 2816 * Pseudo-primality test: small factors, then Miller-Rabin 2817 */ 2818 int mbedtls_mpi_is_prime_ext( const mbedtls_mpi *X, int rounds, 2819 int (*f_rng)(void *, unsigned char *, size_t), 2820 void *p_rng ) 2821 { 2822 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2823 mbedtls_mpi XX; 2824 MPI_VALIDATE_RET( X != NULL ); 2825 MPI_VALIDATE_RET( f_rng != NULL ); 2826 2827 XX.s = 1; 2828 XX.n = X->n; 2829 XX.p = X->p; 2830 2831 if( mbedtls_mpi_cmp_int( &XX, 0 ) == 0 || 2832 mbedtls_mpi_cmp_int( &XX, 1 ) == 0 ) 2833 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE ); 2834 2835 if( mbedtls_mpi_cmp_int( &XX, 2 ) == 0 ) 2836 return( 0 ); 2837 2838 if( ( ret = mpi_check_small_factors( &XX ) ) != 0 ) 2839 { 2840 if( ret == 1 ) 2841 return( 0 ); 2842 2843 return( ret ); 2844 } 2845 2846 return( mpi_miller_rabin( &XX, rounds, f_rng, p_rng ) ); 2847 } 2848 2849 #if !defined(MBEDTLS_DEPRECATED_REMOVED) 2850 /* 2851 * Pseudo-primality test, error probability 2^-80 2852 */ 2853 int mbedtls_mpi_is_prime( const mbedtls_mpi *X, 2854 int (*f_rng)(void *, unsigned char *, size_t), 2855 void *p_rng ) 2856 { 2857 MPI_VALIDATE_RET( X != NULL ); 2858 MPI_VALIDATE_RET( f_rng != NULL ); 2859 2860 /* 2861 * In the past our key generation aimed for an error rate of at most 2862 * 2^-80. Since this function is deprecated, aim for the same certainty 2863 * here as well. 2864 */ 2865 return( mbedtls_mpi_is_prime_ext( X, 40, f_rng, p_rng ) ); 2866 } 2867 #endif 2868 2869 /* 2870 * Prime number generation 2871 * 2872 * To generate an RSA key in a way recommended by FIPS 186-4, both primes must 2873 * be either 1024 bits or 1536 bits long, and flags must contain 2874 * MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR. 2875 */ 2876 int mbedtls_mpi_gen_prime( mbedtls_mpi *X, size_t nbits, int flags, 2877 int (*f_rng)(void *, unsigned char *, size_t), 2878 void *p_rng ) 2879 { 2880 #ifdef MBEDTLS_HAVE_INT64 2881 // ceil(2^63.5) 2882 #define CEIL_MAXUINT_DIV_SQRT2 0xb504f333f9de6485ULL 2883 #else 2884 // ceil(2^31.5) 2885 #define CEIL_MAXUINT_DIV_SQRT2 0xb504f334U 2886 #endif 2887 int ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; 2888 size_t k, n; 2889 int rounds; 2890 mbedtls_mpi_uint r; 2891 mbedtls_mpi Y; 2892 2893 MPI_VALIDATE_RET( X != NULL ); 2894 MPI_VALIDATE_RET( f_rng != NULL ); 2895 2896 if( nbits < 3 || nbits > MBEDTLS_MPI_MAX_BITS ) 2897 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); 2898 2899 mbedtls_mpi_init_mempool( &Y ); 2900 2901 n = BITS_TO_LIMBS( nbits ); 2902 2903 if( ( flags & MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR ) == 0 ) 2904 { 2905 /* 2906 * 2^-80 error probability, number of rounds chosen per HAC, table 4.4 2907 */ 2908 rounds = ( ( nbits >= 1300 ) ? 2 : ( nbits >= 850 ) ? 3 : 2909 ( nbits >= 650 ) ? 4 : ( nbits >= 350 ) ? 8 : 2910 ( nbits >= 250 ) ? 12 : ( nbits >= 150 ) ? 18 : 27 ); 2911 } 2912 else 2913 { 2914 /* 2915 * 2^-100 error probability, number of rounds computed based on HAC, 2916 * fact 4.48 2917 */ 2918 rounds = ( ( nbits >= 1450 ) ? 4 : ( nbits >= 1150 ) ? 5 : 2919 ( nbits >= 1000 ) ? 6 : ( nbits >= 850 ) ? 7 : 2920 ( nbits >= 750 ) ? 8 : ( nbits >= 500 ) ? 13 : 2921 ( nbits >= 250 ) ? 28 : ( nbits >= 150 ) ? 40 : 51 ); 2922 } 2923 2924 while( 1 ) 2925 { 2926 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( X, n * ciL, f_rng, p_rng ) ); 2927 /* make sure generated number is at least (nbits-1)+0.5 bits (FIPS 186-4 §B.3.3 steps 4.4, 5.5) */ 2928 if( X->p[n-1] < CEIL_MAXUINT_DIV_SQRT2 ) continue; 2929 2930 k = n * biL; 2931 if( k > nbits ) MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( X, k - nbits ) ); 2932 X->p[0] |= 1; 2933 2934 if( ( flags & MBEDTLS_MPI_GEN_PRIME_FLAG_DH ) == 0 ) 2935 { 2936 ret = mbedtls_mpi_is_prime_ext( X, rounds, f_rng, p_rng ); 2937 2938 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE ) 2939 goto cleanup; 2940 } 2941 else 2942 { 2943 /* 2944 * An necessary condition for Y and X = 2Y + 1 to be prime 2945 * is X = 2 mod 3 (which is equivalent to Y = 2 mod 3). 2946 * Make sure it is satisfied, while keeping X = 3 mod 4 2947 */ 2948 2949 X->p[0] |= 2; 2950 2951 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, 3 ) ); 2952 if( r == 0 ) 2953 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 8 ) ); 2954 else if( r == 1 ) 2955 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 4 ) ); 2956 2957 /* Set Y = (X-1) / 2, which is X / 2 because X is odd */ 2958 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, X ) ); 2959 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, 1 ) ); 2960 2961 while( 1 ) 2962 { 2963 /* 2964 * First, check small factors for X and Y 2965 * before doing Miller-Rabin on any of them 2966 */ 2967 if( ( ret = mpi_check_small_factors( X ) ) == 0 && 2968 ( ret = mpi_check_small_factors( &Y ) ) == 0 && 2969 ( ret = mpi_miller_rabin( X, rounds, f_rng, p_rng ) ) 2970 == 0 && 2971 ( ret = mpi_miller_rabin( &Y, rounds, f_rng, p_rng ) ) 2972 == 0 ) 2973 goto cleanup; 2974 2975 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE ) 2976 goto cleanup; 2977 2978 /* 2979 * Next candidates. We want to preserve Y = (X-1) / 2 and 2980 * Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3) 2981 * so up Y by 6 and X by 12. 2982 */ 2983 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 12 ) ); 2984 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( &Y, &Y, 6 ) ); 2985 } 2986 } 2987 } 2988 2989 cleanup: 2990 2991 mbedtls_mpi_free( &Y ); 2992 2993 return( ret ); 2994 } 2995 2996 #endif /* MBEDTLS_GENPRIME */ 2997 2998 #if defined(MBEDTLS_SELF_TEST) 2999 3000 #define GCD_PAIR_COUNT 3 3001 3002 static const int gcd_pairs[GCD_PAIR_COUNT][3] = 3003 { 3004 { 693, 609, 21 }, 3005 { 1764, 868, 28 }, 3006 { 768454923, 542167814, 1 } 3007 }; 3008 3009 /* 3010 * Checkup routine 3011 */ 3012 int mbedtls_mpi_self_test( int verbose ) 3013 { 3014 int ret, i; 3015 mbedtls_mpi A, E, N, X, Y, U, V; 3016 3017 mbedtls_mpi_init_mempool( &A ); mbedtls_mpi_init_mempool( &E ); 3018 mbedtls_mpi_init_mempool( &N ); mbedtls_mpi_init_mempool( &X ); 3019 mbedtls_mpi_init_mempool( &Y ); mbedtls_mpi_init_mempool( &U ); 3020 mbedtls_mpi_init_mempool( &V ); 3021 3022 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &A, 16, 3023 "EFE021C2645FD1DC586E69184AF4A31E" \ 3024 "D5F53E93B5F123FA41680867BA110131" \ 3025 "944FE7952E2517337780CB0DB80E61AA" \ 3026 "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) ); 3027 3028 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &E, 16, 3029 "B2E7EFD37075B9F03FF989C7C5051C20" \ 3030 "34D2A323810251127E7BF8625A4F49A5" \ 3031 "F3E27F4DA8BD59C47D6DAABA4C8127BD" \ 3032 "5B5C25763222FEFCCFC38B832366C29E" ) ); 3033 3034 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &N, 16, 3035 "0066A198186C18C10B2F5ED9B522752A" \ 3036 "9830B69916E535C8F047518A889A43A5" \ 3037 "94B6BED27A168D31D4A52F88925AA8F5" ) ); 3038 3039 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &X, &A, &N ) ); 3040 3041 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16, 3042 "602AB7ECA597A3D6B56FF9829A5E8B85" \ 3043 "9E857EA95A03512E2BAE7391688D264A" \ 3044 "A5663B0341DB9CCFD2C4C5F421FEC814" \ 3045 "8001B72E848A38CAE1C65F78E56ABDEF" \ 3046 "E12D3C039B8A02D6BE593F0BBBDA56F1" \ 3047 "ECF677152EF804370C1A305CAF3B5BF1" \ 3048 "30879B56C61DE584A0F53A2447A51E" ) ); 3049 3050 if( verbose != 0 ) 3051 mbedtls_printf( " MPI test #1 (mul_mpi): " ); 3052 3053 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 ) 3054 { 3055 if( verbose != 0 ) 3056 mbedtls_printf( "failed\n" ); 3057 3058 ret = 1; 3059 goto cleanup; 3060 } 3061 3062 if( verbose != 0 ) 3063 mbedtls_printf( "passed\n" ); 3064 3065 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( &X, &Y, &A, &N ) ); 3066 3067 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16, 3068 "256567336059E52CAE22925474705F39A94" ) ); 3069 3070 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &V, 16, 3071 "6613F26162223DF488E9CD48CC132C7A" \ 3072 "0AC93C701B001B092E4E5B9F73BCD27B" \ 3073 "9EE50D0657C77F374E903CDFA4C642" ) ); 3074 3075 if( verbose != 0 ) 3076 mbedtls_printf( " MPI test #2 (div_mpi): " ); 3077 3078 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 || 3079 mbedtls_mpi_cmp_mpi( &Y, &V ) != 0 ) 3080 { 3081 if( verbose != 0 ) 3082 mbedtls_printf( "failed\n" ); 3083 3084 ret = 1; 3085 goto cleanup; 3086 } 3087 3088 if( verbose != 0 ) 3089 mbedtls_printf( "passed\n" ); 3090 3091 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &X, &A, &E, &N, NULL ) ); 3092 3093 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16, 3094 "36E139AEA55215609D2816998ED020BB" \ 3095 "BD96C37890F65171D948E9BC7CBAA4D9" \ 3096 "325D24D6A3C12710F10A09FA08AB87" ) ); 3097 3098 if( verbose != 0 ) 3099 mbedtls_printf( " MPI test #3 (exp_mod): " ); 3100 3101 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 ) 3102 { 3103 if( verbose != 0 ) 3104 mbedtls_printf( "failed\n" ); 3105 3106 ret = 1; 3107 goto cleanup; 3108 } 3109 3110 if( verbose != 0 ) 3111 mbedtls_printf( "passed\n" ); 3112 3113 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &X, &A, &N ) ); 3114 3115 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16, 3116 "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \ 3117 "C3DBA76456363A10869622EAC2DD84EC" \ 3118 "C5B8A74DAC4D09E03B5E0BE779F2DF61" ) ); 3119 3120 if( verbose != 0 ) 3121 mbedtls_printf( " MPI test #4 (inv_mod): " ); 3122 3123 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 ) 3124 { 3125 if( verbose != 0 ) 3126 mbedtls_printf( "failed\n" ); 3127 3128 ret = 1; 3129 goto cleanup; 3130 } 3131 3132 if( verbose != 0 ) 3133 mbedtls_printf( "passed\n" ); 3134 3135 if( verbose != 0 ) 3136 mbedtls_printf( " MPI test #5 (simple gcd): " ); 3137 3138 for( i = 0; i < GCD_PAIR_COUNT; i++ ) 3139 { 3140 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &X, gcd_pairs[i][0] ) ); 3141 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Y, gcd_pairs[i][1] ) ); 3142 3143 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &A, &X, &Y ) ); 3144 3145 if( mbedtls_mpi_cmp_int( &A, gcd_pairs[i][2] ) != 0 ) 3146 { 3147 if( verbose != 0 ) 3148 mbedtls_printf( "failed at %d\n", i ); 3149 3150 ret = 1; 3151 goto cleanup; 3152 } 3153 } 3154 3155 if( verbose != 0 ) 3156 mbedtls_printf( "passed\n" ); 3157 3158 cleanup: 3159 3160 if( ret != 0 && verbose != 0 ) 3161 mbedtls_printf( "Unexpected error, return code = %08X\n", (unsigned int) ret ); 3162 3163 mbedtls_mpi_free( &A ); mbedtls_mpi_free( &E ); mbedtls_mpi_free( &N ); mbedtls_mpi_free( &X ); 3164 mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &U ); mbedtls_mpi_free( &V ); 3165 3166 if( verbose != 0 ) 3167 mbedtls_printf( "\n" ); 3168 3169 return( ret ); 3170 } 3171 3172 #endif /* MBEDTLS_SELF_TEST */ 3173 3174 #endif /* MBEDTLS_BIGNUM_C */ 3175