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