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