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