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 short use_mempool = X->use_mempool; 781 782 mbedtls_mpi_free( X ); 783 mpi_init( X, use_mempool ); 784 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, limbs ) ); 785 } 786 787 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) ); 788 789 for( i = buflen, j = 0; i > 0; i--, j++ ) 790 X->p[j / ciL] |= ((mbedtls_mpi_uint) buf[i - 1]) << ((j % ciL) << 3); 791 792 cleanup: 793 794 return( ret ); 795 } 796 797 /* 798 * Export X into unsigned binary data, big endian 799 */ 800 int mbedtls_mpi_write_binary( const mbedtls_mpi *X, 801 unsigned char *buf, size_t buflen ) 802 { 803 size_t stored_bytes; 804 size_t bytes_to_copy; 805 unsigned char *p; 806 size_t i; 807 808 MPI_VALIDATE_RET( X != NULL ); 809 MPI_VALIDATE_RET( buflen == 0 || buf != NULL ); 810 811 stored_bytes = X->n * ciL; 812 813 if( stored_bytes < buflen ) 814 { 815 /* There is enough space in the output buffer. Write initial 816 * null bytes and record the position at which to start 817 * writing the significant bytes. In this case, the execution 818 * trace of this function does not depend on the value of the 819 * number. */ 820 bytes_to_copy = stored_bytes; 821 p = buf + buflen - stored_bytes; 822 memset( buf, 0, buflen - stored_bytes ); 823 } 824 else 825 { 826 /* The output buffer is smaller than the allocated size of X. 827 * However X may fit if its leading bytes are zero. */ 828 bytes_to_copy = buflen; 829 p = buf; 830 for( i = bytes_to_copy; i < stored_bytes; i++ ) 831 { 832 if( GET_BYTE( X, i ) != 0 ) 833 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL ); 834 } 835 } 836 837 for( i = 0; i < bytes_to_copy; i++ ) 838 p[bytes_to_copy - i - 1] = GET_BYTE( X, i ); 839 840 return( 0 ); 841 } 842 843 /* 844 * Left-shift: X <<= count 845 */ 846 int mbedtls_mpi_shift_l( mbedtls_mpi *X, size_t count ) 847 { 848 int ret; 849 size_t i, v0, t1; 850 mbedtls_mpi_uint r0 = 0, r1; 851 MPI_VALIDATE_RET( X != NULL ); 852 853 v0 = count / (biL ); 854 t1 = count & (biL - 1); 855 856 i = mbedtls_mpi_bitlen( X ) + count; 857 858 if( X->n * biL < i ) 859 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, BITS_TO_LIMBS( i ) ) ); 860 861 ret = 0; 862 863 /* 864 * shift by count / limb_size 865 */ 866 if( v0 > 0 ) 867 { 868 for( i = X->n; i > v0; i-- ) 869 X->p[i - 1] = X->p[i - v0 - 1]; 870 871 for( ; i > 0; i-- ) 872 X->p[i - 1] = 0; 873 } 874 875 /* 876 * shift by count % limb_size 877 */ 878 if( t1 > 0 ) 879 { 880 for( i = v0; i < X->n; i++ ) 881 { 882 r1 = X->p[i] >> (biL - t1); 883 X->p[i] <<= t1; 884 X->p[i] |= r0; 885 r0 = r1; 886 } 887 } 888 889 cleanup: 890 891 return( ret ); 892 } 893 894 /* 895 * Right-shift: X >>= count 896 */ 897 int mbedtls_mpi_shift_r( mbedtls_mpi *X, size_t count ) 898 { 899 size_t i, v0, v1; 900 mbedtls_mpi_uint r0 = 0, r1; 901 MPI_VALIDATE_RET( X != NULL ); 902 903 v0 = count / biL; 904 v1 = count & (biL - 1); 905 906 if( v0 > X->n || ( v0 == X->n && v1 > 0 ) ) 907 return mbedtls_mpi_lset( X, 0 ); 908 909 /* 910 * shift by count / limb_size 911 */ 912 if( v0 > 0 ) 913 { 914 for( i = 0; i < X->n - v0; i++ ) 915 X->p[i] = X->p[i + v0]; 916 917 for( ; i < X->n; i++ ) 918 X->p[i] = 0; 919 } 920 921 /* 922 * shift by count % limb_size 923 */ 924 if( v1 > 0 ) 925 { 926 for( i = X->n; i > 0; i-- ) 927 { 928 r1 = X->p[i - 1] << (biL - v1); 929 X->p[i - 1] >>= v1; 930 X->p[i - 1] |= r0; 931 r0 = r1; 932 } 933 } 934 935 return( 0 ); 936 } 937 938 /* 939 * Compare unsigned values 940 */ 941 int mbedtls_mpi_cmp_abs( const mbedtls_mpi *X, const mbedtls_mpi *Y ) 942 { 943 size_t i, j; 944 MPI_VALIDATE_RET( X != NULL ); 945 MPI_VALIDATE_RET( Y != NULL ); 946 947 for( i = X->n; i > 0; i-- ) 948 if( X->p[i - 1] != 0 ) 949 break; 950 951 for( j = Y->n; j > 0; j-- ) 952 if( Y->p[j - 1] != 0 ) 953 break; 954 955 if( i == 0 && j == 0 ) 956 return( 0 ); 957 958 if( i > j ) return( 1 ); 959 if( j > i ) return( -1 ); 960 961 for( ; i > 0; i-- ) 962 { 963 if( X->p[i - 1] > Y->p[i - 1] ) return( 1 ); 964 if( X->p[i - 1] < Y->p[i - 1] ) return( -1 ); 965 } 966 967 return( 0 ); 968 } 969 970 /* 971 * Compare signed values 972 */ 973 int mbedtls_mpi_cmp_mpi( const mbedtls_mpi *X, const mbedtls_mpi *Y ) 974 { 975 size_t i, j; 976 MPI_VALIDATE_RET( X != NULL ); 977 MPI_VALIDATE_RET( Y != NULL ); 978 979 for( i = X->n; i > 0; i-- ) 980 if( X->p[i - 1] != 0 ) 981 break; 982 983 for( j = Y->n; j > 0; j-- ) 984 if( Y->p[j - 1] != 0 ) 985 break; 986 987 if( i == 0 && j == 0 ) 988 return( 0 ); 989 990 if( i > j ) return( X->s ); 991 if( j > i ) return( -Y->s ); 992 993 if( X->s > 0 && Y->s < 0 ) return( 1 ); 994 if( Y->s > 0 && X->s < 0 ) return( -1 ); 995 996 for( ; i > 0; i-- ) 997 { 998 if( X->p[i - 1] > Y->p[i - 1] ) return( X->s ); 999 if( X->p[i - 1] < Y->p[i - 1] ) return( -X->s ); 1000 } 1001 1002 return( 0 ); 1003 } 1004 1005 /* 1006 * Compare signed values 1007 */ 1008 int mbedtls_mpi_cmp_int( const mbedtls_mpi *X, mbedtls_mpi_sint z ) 1009 { 1010 mbedtls_mpi Y; 1011 mbedtls_mpi_uint p[1]; 1012 MPI_VALIDATE_RET( X != NULL ); 1013 1014 *p = ( z < 0 ) ? -z : z; 1015 Y.s = ( z < 0 ) ? -1 : 1; 1016 Y.n = 1; 1017 Y.p = p; 1018 1019 return( mbedtls_mpi_cmp_mpi( X, &Y ) ); 1020 } 1021 1022 /* 1023 * Unsigned addition: X = |A| + |B| (HAC 14.7) 1024 */ 1025 int mbedtls_mpi_add_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B ) 1026 { 1027 int ret; 1028 size_t i, j; 1029 mbedtls_mpi_uint *o, *p, c, tmp; 1030 MPI_VALIDATE_RET( X != NULL ); 1031 MPI_VALIDATE_RET( A != NULL ); 1032 MPI_VALIDATE_RET( B != NULL ); 1033 1034 if( X == B ) 1035 { 1036 const mbedtls_mpi *T = A; A = X; B = T; 1037 } 1038 1039 if( X != A ) 1040 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) ); 1041 1042 /* 1043 * X should always be positive as a result of unsigned additions. 1044 */ 1045 X->s = 1; 1046 1047 for( j = B->n; j > 0; j-- ) 1048 if( B->p[j - 1] != 0 ) 1049 break; 1050 1051 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) ); 1052 1053 o = B->p; p = X->p; c = 0; 1054 1055 /* 1056 * tmp is used because it might happen that p == o 1057 */ 1058 for( i = 0; i < j; i++, o++, p++ ) 1059 { 1060 tmp= *o; 1061 *p += c; c = ( *p < c ); 1062 *p += tmp; c += ( *p < tmp ); 1063 } 1064 1065 while( c != 0 ) 1066 { 1067 if( i >= X->n ) 1068 { 1069 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + 1 ) ); 1070 p = X->p + i; 1071 } 1072 1073 *p += c; c = ( *p < c ); i++; p++; 1074 } 1075 1076 cleanup: 1077 1078 return( ret ); 1079 } 1080 1081 /* 1082 * Helper for mbedtls_mpi subtraction 1083 */ 1084 static void mpi_sub_hlp( size_t n, mbedtls_mpi_uint *s, mbedtls_mpi_uint *d ) 1085 { 1086 size_t i; 1087 mbedtls_mpi_uint c, z; 1088 1089 for( i = c = 0; i < n; i++, s++, d++ ) 1090 { 1091 z = ( *d < c ); *d -= c; 1092 c = ( *d < *s ) + z; *d -= *s; 1093 } 1094 1095 while( c != 0 ) 1096 { 1097 z = ( *d < c ); *d -= c; 1098 c = z; d++; 1099 } 1100 } 1101 1102 /* 1103 * Unsigned subtraction: X = |A| - |B| (HAC 14.9) 1104 */ 1105 int mbedtls_mpi_sub_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B ) 1106 { 1107 mbedtls_mpi TB; 1108 int ret; 1109 size_t n; 1110 MPI_VALIDATE_RET( X != NULL ); 1111 MPI_VALIDATE_RET( A != NULL ); 1112 MPI_VALIDATE_RET( B != NULL ); 1113 1114 if( mbedtls_mpi_cmp_abs( A, B ) < 0 ) 1115 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE ); 1116 1117 mbedtls_mpi_init_mempool( &TB ); 1118 1119 if( X == B ) 1120 { 1121 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) ); 1122 B = &TB; 1123 } 1124 1125 if( X != A ) 1126 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) ); 1127 1128 /* 1129 * X should always be positive as a result of unsigned subtractions. 1130 */ 1131 X->s = 1; 1132 1133 ret = 0; 1134 1135 for( n = B->n; n > 0; n-- ) 1136 if( B->p[n - 1] != 0 ) 1137 break; 1138 1139 mpi_sub_hlp( n, B->p, X->p ); 1140 1141 cleanup: 1142 1143 mbedtls_mpi_free( &TB ); 1144 1145 return( ret ); 1146 } 1147 1148 /* 1149 * Signed addition: X = A + B 1150 */ 1151 int mbedtls_mpi_add_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B ) 1152 { 1153 int ret, s; 1154 MPI_VALIDATE_RET( X != NULL ); 1155 MPI_VALIDATE_RET( A != NULL ); 1156 MPI_VALIDATE_RET( B != NULL ); 1157 1158 s = A->s; 1159 if( A->s * B->s < 0 ) 1160 { 1161 if( mbedtls_mpi_cmp_abs( A, B ) >= 0 ) 1162 { 1163 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) ); 1164 X->s = s; 1165 } 1166 else 1167 { 1168 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) ); 1169 X->s = -s; 1170 } 1171 } 1172 else 1173 { 1174 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) ); 1175 X->s = s; 1176 } 1177 1178 cleanup: 1179 1180 return( ret ); 1181 } 1182 1183 /* 1184 * Signed subtraction: X = A - B 1185 */ 1186 int mbedtls_mpi_sub_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B ) 1187 { 1188 int ret, s; 1189 MPI_VALIDATE_RET( X != NULL ); 1190 MPI_VALIDATE_RET( A != NULL ); 1191 MPI_VALIDATE_RET( B != NULL ); 1192 1193 s = A->s; 1194 if( A->s * B->s > 0 ) 1195 { 1196 if( mbedtls_mpi_cmp_abs( A, B ) >= 0 ) 1197 { 1198 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) ); 1199 X->s = s; 1200 } 1201 else 1202 { 1203 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) ); 1204 X->s = -s; 1205 } 1206 } 1207 else 1208 { 1209 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) ); 1210 X->s = s; 1211 } 1212 1213 cleanup: 1214 1215 return( ret ); 1216 } 1217 1218 /* 1219 * Signed addition: X = A + b 1220 */ 1221 int mbedtls_mpi_add_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b ) 1222 { 1223 mbedtls_mpi _B; 1224 mbedtls_mpi_uint p[1]; 1225 MPI_VALIDATE_RET( X != NULL ); 1226 MPI_VALIDATE_RET( A != NULL ); 1227 1228 p[0] = ( b < 0 ) ? -b : b; 1229 _B.s = ( b < 0 ) ? -1 : 1; 1230 _B.n = 1; 1231 _B.p = p; 1232 1233 return( mbedtls_mpi_add_mpi( X, A, &_B ) ); 1234 } 1235 1236 /* 1237 * Signed subtraction: X = A - b 1238 */ 1239 int mbedtls_mpi_sub_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b ) 1240 { 1241 mbedtls_mpi _B; 1242 mbedtls_mpi_uint p[1]; 1243 MPI_VALIDATE_RET( X != NULL ); 1244 MPI_VALIDATE_RET( A != NULL ); 1245 1246 p[0] = ( b < 0 ) ? -b : b; 1247 _B.s = ( b < 0 ) ? -1 : 1; 1248 _B.n = 1; 1249 _B.p = p; 1250 1251 return( mbedtls_mpi_sub_mpi( X, A, &_B ) ); 1252 } 1253 1254 /* 1255 * Helper for mbedtls_mpi multiplication 1256 */ 1257 static 1258 #if defined(__APPLE__) && defined(__arm__) 1259 /* 1260 * Apple LLVM version 4.2 (clang-425.0.24) (based on LLVM 3.2svn) 1261 * appears to need this to prevent bad ARM code generation at -O3. 1262 */ 1263 __attribute__ ((noinline)) 1264 #endif 1265 void mpi_mul_hlp( size_t i, mbedtls_mpi_uint *s, mbedtls_mpi_uint *d, mbedtls_mpi_uint b ) 1266 { 1267 mbedtls_mpi_uint c = 0, t = 0; 1268 1269 #if defined(MULADDC_HUIT) 1270 for( ; i >= 8; i -= 8 ) 1271 { 1272 MULADDC_INIT 1273 MULADDC_HUIT 1274 MULADDC_STOP 1275 } 1276 1277 for( ; i > 0; i-- ) 1278 { 1279 MULADDC_INIT 1280 MULADDC_CORE 1281 MULADDC_STOP 1282 } 1283 #else /* MULADDC_HUIT */ 1284 for( ; i >= 16; i -= 16 ) 1285 { 1286 MULADDC_INIT 1287 MULADDC_CORE MULADDC_CORE 1288 MULADDC_CORE MULADDC_CORE 1289 MULADDC_CORE MULADDC_CORE 1290 MULADDC_CORE MULADDC_CORE 1291 1292 MULADDC_CORE MULADDC_CORE 1293 MULADDC_CORE MULADDC_CORE 1294 MULADDC_CORE MULADDC_CORE 1295 MULADDC_CORE MULADDC_CORE 1296 MULADDC_STOP 1297 } 1298 1299 for( ; i >= 8; i -= 8 ) 1300 { 1301 MULADDC_INIT 1302 MULADDC_CORE MULADDC_CORE 1303 MULADDC_CORE MULADDC_CORE 1304 1305 MULADDC_CORE MULADDC_CORE 1306 MULADDC_CORE MULADDC_CORE 1307 MULADDC_STOP 1308 } 1309 1310 for( ; i > 0; i-- ) 1311 { 1312 MULADDC_INIT 1313 MULADDC_CORE 1314 MULADDC_STOP 1315 } 1316 #endif /* MULADDC_HUIT */ 1317 1318 t++; 1319 1320 do { 1321 *d += c; c = ( *d < c ); d++; 1322 } 1323 while( c != 0 ); 1324 } 1325 1326 /* 1327 * Baseline multiplication: X = A * B (HAC 14.12) 1328 */ 1329 int mbedtls_mpi_mul_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B ) 1330 { 1331 int ret; 1332 size_t i, j; 1333 mbedtls_mpi TA, TB; 1334 MPI_VALIDATE_RET( X != NULL ); 1335 MPI_VALIDATE_RET( A != NULL ); 1336 MPI_VALIDATE_RET( B != NULL ); 1337 1338 mbedtls_mpi_init_mempool( &TA ); mbedtls_mpi_init_mempool( &TB ); 1339 1340 if( X == A ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) ); A = &TA; } 1341 if( X == B ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) ); B = &TB; } 1342 1343 for( i = A->n; i > 0; i-- ) 1344 if( A->p[i - 1] != 0 ) 1345 break; 1346 1347 for( j = B->n; j > 0; j-- ) 1348 if( B->p[j - 1] != 0 ) 1349 break; 1350 1351 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + j ) ); 1352 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) ); 1353 1354 for( ; j > 0; j-- ) 1355 mpi_mul_hlp( i, A->p, X->p + j - 1, B->p[j - 1] ); 1356 1357 X->s = A->s * B->s; 1358 1359 cleanup: 1360 1361 mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TA ); 1362 1363 return( ret ); 1364 } 1365 1366 /* 1367 * Baseline multiplication: X = A * b 1368 */ 1369 int mbedtls_mpi_mul_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b ) 1370 { 1371 mbedtls_mpi _B; 1372 mbedtls_mpi_uint p[1]; 1373 MPI_VALIDATE_RET( X != NULL ); 1374 MPI_VALIDATE_RET( A != NULL ); 1375 1376 _B.s = 1; 1377 _B.n = 1; 1378 _B.p = p; 1379 p[0] = b; 1380 1381 return( mbedtls_mpi_mul_mpi( X, A, &_B ) ); 1382 } 1383 1384 /* 1385 * Unsigned integer divide - double mbedtls_mpi_uint dividend, u1/u0, and 1386 * mbedtls_mpi_uint divisor, d 1387 */ 1388 static mbedtls_mpi_uint mbedtls_int_div_int( mbedtls_mpi_uint u1, 1389 mbedtls_mpi_uint u0, mbedtls_mpi_uint d, mbedtls_mpi_uint *r ) 1390 { 1391 #if defined(MBEDTLS_HAVE_UDBL) 1392 mbedtls_t_udbl dividend, quotient; 1393 #else 1394 const mbedtls_mpi_uint radix = (mbedtls_mpi_uint) 1 << biH; 1395 const mbedtls_mpi_uint uint_halfword_mask = ( (mbedtls_mpi_uint) 1 << biH ) - 1; 1396 mbedtls_mpi_uint d0, d1, q0, q1, rAX, r0, quotient; 1397 mbedtls_mpi_uint u0_msw, u0_lsw; 1398 size_t s; 1399 #endif 1400 1401 /* 1402 * Check for overflow 1403 */ 1404 if( 0 == d || u1 >= d ) 1405 { 1406 if (r != NULL) *r = ~0; 1407 1408 return ( ~0 ); 1409 } 1410 1411 #if defined(MBEDTLS_HAVE_UDBL) 1412 dividend = (mbedtls_t_udbl) u1 << biL; 1413 dividend |= (mbedtls_t_udbl) u0; 1414 quotient = dividend / d; 1415 if( quotient > ( (mbedtls_t_udbl) 1 << biL ) - 1 ) 1416 quotient = ( (mbedtls_t_udbl) 1 << biL ) - 1; 1417 1418 if( r != NULL ) 1419 *r = (mbedtls_mpi_uint)( dividend - (quotient * d ) ); 1420 1421 return (mbedtls_mpi_uint) quotient; 1422 #else 1423 1424 /* 1425 * Algorithm D, Section 4.3.1 - The Art of Computer Programming 1426 * Vol. 2 - Seminumerical Algorithms, Knuth 1427 */ 1428 1429 /* 1430 * Normalize the divisor, d, and dividend, u0, u1 1431 */ 1432 s = mbedtls_clz( d ); 1433 d = d << s; 1434 1435 u1 = u1 << s; 1436 u1 |= ( u0 >> ( biL - s ) ) & ( -(mbedtls_mpi_sint)s >> ( biL - 1 ) ); 1437 u0 = u0 << s; 1438 1439 d1 = d >> biH; 1440 d0 = d & uint_halfword_mask; 1441 1442 u0_msw = u0 >> biH; 1443 u0_lsw = u0 & uint_halfword_mask; 1444 1445 /* 1446 * Find the first quotient and remainder 1447 */ 1448 q1 = u1 / d1; 1449 r0 = u1 - d1 * q1; 1450 1451 while( q1 >= radix || ( q1 * d0 > radix * r0 + u0_msw ) ) 1452 { 1453 q1 -= 1; 1454 r0 += d1; 1455 1456 if ( r0 >= radix ) break; 1457 } 1458 1459 rAX = ( u1 * radix ) + ( u0_msw - q1 * d ); 1460 q0 = rAX / d1; 1461 r0 = rAX - q0 * d1; 1462 1463 while( q0 >= radix || ( q0 * d0 > radix * r0 + u0_lsw ) ) 1464 { 1465 q0 -= 1; 1466 r0 += d1; 1467 1468 if ( r0 >= radix ) break; 1469 } 1470 1471 if (r != NULL) 1472 *r = ( rAX * radix + u0_lsw - q0 * d ) >> s; 1473 1474 quotient = q1 * radix + q0; 1475 1476 return quotient; 1477 #endif 1478 } 1479 1480 /* 1481 * Division by mbedtls_mpi: A = Q * B + R (HAC 14.20) 1482 */ 1483 int mbedtls_mpi_div_mpi( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A, 1484 const mbedtls_mpi *B ) 1485 { 1486 int ret; 1487 size_t i, n, t, k; 1488 mbedtls_mpi X, Y, Z, T1, T2; 1489 MPI_VALIDATE_RET( A != NULL ); 1490 MPI_VALIDATE_RET( B != NULL ); 1491 1492 if( mbedtls_mpi_cmp_int( B, 0 ) == 0 ) 1493 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO ); 1494 1495 mbedtls_mpi_init_mempool( &X ); mbedtls_mpi_init_mempool( &Y ); 1496 mbedtls_mpi_init_mempool( &Z ); mbedtls_mpi_init_mempool( &T1 ); 1497 mbedtls_mpi_init_mempool( &T2 ); 1498 1499 if( mbedtls_mpi_cmp_abs( A, B ) < 0 ) 1500 { 1501 if( Q != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_lset( Q, 0 ) ); 1502 if( R != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, A ) ); 1503 return( 0 ); 1504 } 1505 1506 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &X, A ) ); 1507 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, B ) ); 1508 X.s = Y.s = 1; 1509 1510 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &Z, A->n + 2 ) ); 1511 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Z, 0 ) ); 1512 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T1, 2 ) ); 1513 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T2, 3 ) ); 1514 1515 k = mbedtls_mpi_bitlen( &Y ) % biL; 1516 if( k < biL - 1 ) 1517 { 1518 k = biL - 1 - k; 1519 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &X, k ) ); 1520 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, k ) ); 1521 } 1522 else k = 0; 1523 1524 n = X.n - 1; 1525 t = Y.n - 1; 1526 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, biL * ( n - t ) ) ); 1527 1528 while( mbedtls_mpi_cmp_mpi( &X, &Y ) >= 0 ) 1529 { 1530 Z.p[n - t]++; 1531 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &Y ) ); 1532 } 1533 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, biL * ( n - t ) ) ); 1534 1535 for( i = n; i > t ; i-- ) 1536 { 1537 if( X.p[i] >= Y.p[t] ) 1538 Z.p[i - t - 1] = ~0; 1539 else 1540 { 1541 Z.p[i - t - 1] = mbedtls_int_div_int( X.p[i], X.p[i - 1], 1542 Y.p[t], NULL); 1543 } 1544 1545 Z.p[i - t - 1]++; 1546 do 1547 { 1548 Z.p[i - t - 1]--; 1549 1550 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &T1, 0 ) ); 1551 T1.p[0] = ( t < 1 ) ? 0 : Y.p[t - 1]; 1552 T1.p[1] = Y.p[t]; 1553 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &T1, Z.p[i - t - 1] ) ); 1554 1555 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &T2, 0 ) ); 1556 T2.p[0] = ( i < 2 ) ? 0 : X.p[i - 2]; 1557 T2.p[1] = ( i < 1 ) ? 0 : X.p[i - 1]; 1558 T2.p[2] = X.p[i]; 1559 } 1560 while( mbedtls_mpi_cmp_mpi( &T1, &T2 ) > 0 ); 1561 1562 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &Y, Z.p[i - t - 1] ) ); 1563 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) ); 1564 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T1 ) ); 1565 1566 if( mbedtls_mpi_cmp_int( &X, 0 ) < 0 ) 1567 { 1568 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T1, &Y ) ); 1569 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) ); 1570 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &X, &X, &T1 ) ); 1571 Z.p[i - t - 1]--; 1572 } 1573 } 1574 1575 if( Q != NULL ) 1576 { 1577 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( Q, &Z ) ); 1578 Q->s = A->s * B->s; 1579 } 1580 1581 if( R != NULL ) 1582 { 1583 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &X, k ) ); 1584 X.s = A->s; 1585 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, &X ) ); 1586 1587 if( mbedtls_mpi_cmp_int( R, 0 ) == 0 ) 1588 R->s = 1; 1589 } 1590 1591 cleanup: 1592 1593 mbedtls_mpi_free( &X ); mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &Z ); 1594 mbedtls_mpi_free( &T1 ); mbedtls_mpi_free( &T2 ); 1595 1596 return( ret ); 1597 } 1598 1599 /* 1600 * Division by int: A = Q * b + R 1601 */ 1602 int mbedtls_mpi_div_int( mbedtls_mpi *Q, mbedtls_mpi *R, 1603 const mbedtls_mpi *A, 1604 mbedtls_mpi_sint b ) 1605 { 1606 mbedtls_mpi _B; 1607 mbedtls_mpi_uint p[1]; 1608 MPI_VALIDATE_RET( A != NULL ); 1609 1610 p[0] = ( b < 0 ) ? -b : b; 1611 _B.s = ( b < 0 ) ? -1 : 1; 1612 _B.n = 1; 1613 _B.p = p; 1614 1615 return( mbedtls_mpi_div_mpi( Q, R, A, &_B ) ); 1616 } 1617 1618 /* 1619 * Modulo: R = A mod B 1620 */ 1621 int mbedtls_mpi_mod_mpi( mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B ) 1622 { 1623 int ret; 1624 MPI_VALIDATE_RET( R != NULL ); 1625 MPI_VALIDATE_RET( A != NULL ); 1626 MPI_VALIDATE_RET( B != NULL ); 1627 1628 if( mbedtls_mpi_cmp_int( B, 0 ) < 0 ) 1629 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE ); 1630 1631 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( NULL, R, A, B ) ); 1632 1633 while( mbedtls_mpi_cmp_int( R, 0 ) < 0 ) 1634 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( R, R, B ) ); 1635 1636 while( mbedtls_mpi_cmp_mpi( R, B ) >= 0 ) 1637 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( R, R, B ) ); 1638 1639 cleanup: 1640 1641 return( ret ); 1642 } 1643 1644 /* 1645 * Modulo: r = A mod b 1646 */ 1647 int mbedtls_mpi_mod_int( mbedtls_mpi_uint *r, const mbedtls_mpi *A, mbedtls_mpi_sint b ) 1648 { 1649 size_t i; 1650 mbedtls_mpi_uint x, y, z; 1651 MPI_VALIDATE_RET( r != NULL ); 1652 MPI_VALIDATE_RET( A != NULL ); 1653 1654 if( b == 0 ) 1655 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO ); 1656 1657 if( b < 0 ) 1658 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE ); 1659 1660 /* 1661 * handle trivial cases 1662 */ 1663 if( b == 1 ) 1664 { 1665 *r = 0; 1666 return( 0 ); 1667 } 1668 1669 if( b == 2 ) 1670 { 1671 *r = A->p[0] & 1; 1672 return( 0 ); 1673 } 1674 1675 /* 1676 * general case 1677 */ 1678 for( i = A->n, y = 0; i > 0; i-- ) 1679 { 1680 x = A->p[i - 1]; 1681 y = ( y << biH ) | ( x >> biH ); 1682 z = y / b; 1683 y -= z * b; 1684 1685 x <<= biH; 1686 y = ( y << biH ) | ( x >> biH ); 1687 z = y / b; 1688 y -= z * b; 1689 } 1690 1691 /* 1692 * If A is negative, then the current y represents a negative value. 1693 * Flipping it to the positive side. 1694 */ 1695 if( A->s < 0 && y != 0 ) 1696 y = b - y; 1697 1698 *r = y; 1699 1700 return( 0 ); 1701 } 1702 1703 /* 1704 * Fast Montgomery initialization (thanks to Tom St Denis) 1705 */ 1706 void mbedtls_mpi_montg_init( mbedtls_mpi_uint *mm, const mbedtls_mpi *N ) 1707 { 1708 mbedtls_mpi_uint x, m0 = N->p[0]; 1709 unsigned int i; 1710 1711 x = m0; 1712 x += ( ( m0 + 2 ) & 4 ) << 1; 1713 1714 for( i = biL; i >= 8; i /= 2 ) 1715 x *= ( 2 - ( m0 * x ) ); 1716 1717 *mm = ~x + 1; 1718 } 1719 1720 /* 1721 * Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36) 1722 */ 1723 int mbedtls_mpi_montmul( mbedtls_mpi *A, const mbedtls_mpi *B, 1724 const mbedtls_mpi *N, mbedtls_mpi_uint mm, 1725 const mbedtls_mpi *T ) 1726 { 1727 size_t i, n, m; 1728 mbedtls_mpi_uint u0, u1, *d; 1729 1730 if( T->n < N->n + 1 || T->p == NULL ) 1731 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); 1732 1733 memset( T->p, 0, T->n * ciL ); 1734 1735 d = T->p; 1736 n = N->n; 1737 m = ( B->n < n ) ? B->n : n; 1738 1739 for( i = 0; i < n; i++ ) 1740 { 1741 /* 1742 * T = (T + u0*B + u1*N) / 2^biL 1743 */ 1744 u0 = A->p[i]; 1745 u1 = ( d[0] + u0 * B->p[0] ) * mm; 1746 1747 mpi_mul_hlp( m, B->p, d, u0 ); 1748 mpi_mul_hlp( n, N->p, d, u1 ); 1749 1750 *d++ = u0; d[n + 1] = 0; 1751 } 1752 1753 memcpy( A->p, d, ( n + 1 ) * ciL ); 1754 1755 if( mbedtls_mpi_cmp_abs( A, N ) >= 0 ) 1756 mpi_sub_hlp( n, N->p, A->p ); 1757 else 1758 /* prevent timing attacks */ 1759 mpi_sub_hlp( n, A->p, T->p ); 1760 1761 return( 0 ); 1762 } 1763 1764 /* 1765 * Montgomery reduction: A = A * R^-1 mod N 1766 */ 1767 int mbedtls_mpi_montred( mbedtls_mpi *A, const mbedtls_mpi *N, 1768 mbedtls_mpi_uint mm, const mbedtls_mpi *T ) 1769 { 1770 mbedtls_mpi_uint z = 1; 1771 mbedtls_mpi U; 1772 1773 U.n = U.s = (int) z; 1774 U.p = &z; 1775 1776 return( mbedtls_mpi_montmul( A, &U, N, mm, T ) ); 1777 } 1778 1779 /* 1780 * Sliding-window exponentiation: X = A^E mod N (HAC 14.85) 1781 */ 1782 int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A, 1783 const mbedtls_mpi *E, const mbedtls_mpi *N, 1784 mbedtls_mpi *_RR ) 1785 { 1786 int ret; 1787 size_t wbits, wsize, one = 1; 1788 size_t i, j, nblimbs; 1789 size_t bufsize, nbits; 1790 mbedtls_mpi_uint ei, mm, state; 1791 mbedtls_mpi RR, T, Apos; 1792 mbedtls_mpi *W = NULL; 1793 const size_t array_size_W = 2 << MBEDTLS_MPI_WINDOW_SIZE; 1794 int neg; 1795 1796 MPI_VALIDATE_RET( X != NULL ); 1797 MPI_VALIDATE_RET( A != NULL ); 1798 MPI_VALIDATE_RET( E != NULL ); 1799 MPI_VALIDATE_RET( N != NULL ); 1800 1801 if( mbedtls_mpi_cmp_int( N, 0 ) <= 0 || ( N->p[0] & 1 ) == 0 ) 1802 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); 1803 1804 if( mbedtls_mpi_cmp_int( E, 0 ) < 0 ) 1805 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); 1806 1807 /* 1808 * Init temps and window size 1809 */ 1810 mbedtls_mpi_montg_init( &mm, N ); 1811 mbedtls_mpi_init_mempool( &RR ); mbedtls_mpi_init_mempool( &T ); 1812 mbedtls_mpi_init_mempool( &Apos ); 1813 1814 i = mbedtls_mpi_bitlen( E ); 1815 1816 wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 : 1817 ( i > 79 ) ? 4 : ( i > 23 ) ? 3 : 1; 1818 1819 if( wsize > MBEDTLS_MPI_WINDOW_SIZE ) 1820 wsize = MBEDTLS_MPI_WINDOW_SIZE; 1821 1822 j = N->n + 1; 1823 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) ); 1824 1825 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T, j * 2 ) ); 1826 1827 /* 1828 * Compensate for negative A (and correct at the end) 1829 */ 1830 neg = ( A->s == -1 ); 1831 if( neg ) 1832 { 1833 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Apos, A ) ); 1834 Apos.s = 1; 1835 A = &Apos; 1836 } 1837 1838 /* 1839 * If 1st call, pre-compute R^2 mod N 1840 */ 1841 if( _RR == NULL || _RR->p == NULL ) 1842 { 1843 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &RR, 1 ) ); 1844 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &RR, N->n * 2 * biL ) ); 1845 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &RR, &RR, N ) ); 1846 1847 if( _RR != NULL ) 1848 memcpy( _RR, &RR, sizeof( mbedtls_mpi ) ); 1849 } 1850 else 1851 memcpy( &RR, _RR, sizeof( mbedtls_mpi ) ); 1852 1853 W = mempool_alloc( mbedtls_mpi_mempool, 1854 sizeof( mbedtls_mpi ) * array_size_W ); 1855 if( W == NULL ) { 1856 ret = MBEDTLS_ERR_MPI_ALLOC_FAILED; 1857 goto cleanup; 1858 } 1859 for( i = 0; i < array_size_W; i++ ) 1860 mbedtls_mpi_init_mempool( W + i ); 1861 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[1], j ) ); 1862 1863 /* 1864 * W[1] = A * R^2 * R^-1 mod N = A * R mod N 1865 */ 1866 if( mbedtls_mpi_cmp_mpi( A, N ) >= 0 ) 1867 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &W[1], A, N ) ); 1868 else 1869 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[1], A ) ); 1870 1871 MBEDTLS_MPI_CHK( mbedtls_mpi_montmul( &W[1], &RR, N, mm, &T ) ); 1872 1873 /* 1874 * X = R^2 * R^-1 mod N = R mod N 1875 */ 1876 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &RR ) ); 1877 MBEDTLS_MPI_CHK( mbedtls_mpi_montred( X, N, mm, &T ) ); 1878 1879 if( wsize > 1 ) 1880 { 1881 /* 1882 * W[1 << (wsize - 1)] = W[1] ^ (wsize - 1) 1883 */ 1884 j = one << ( wsize - 1 ); 1885 1886 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[j], N->n + 1 ) ); 1887 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[j], &W[1] ) ); 1888 1889 for( i = 0; i < wsize - 1; i++ ) 1890 MBEDTLS_MPI_CHK( mbedtls_mpi_montmul( &W[j], &W[j], N, mm, &T ) ); 1891 1892 /* 1893 * W[i] = W[i - 1] * W[1] 1894 */ 1895 for( i = j + 1; i < ( one << wsize ); i++ ) 1896 { 1897 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[i], N->n + 1 ) ); 1898 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[i], &W[i - 1] ) ); 1899 1900 MBEDTLS_MPI_CHK( mbedtls_mpi_montmul( &W[i], &W[1], N, mm, &T ) ); 1901 } 1902 } 1903 1904 nblimbs = E->n; 1905 bufsize = 0; 1906 nbits = 0; 1907 wbits = 0; 1908 state = 0; 1909 1910 while( 1 ) 1911 { 1912 if( bufsize == 0 ) 1913 { 1914 if( nblimbs == 0 ) 1915 break; 1916 1917 nblimbs--; 1918 1919 bufsize = sizeof( mbedtls_mpi_uint ) << 3; 1920 } 1921 1922 bufsize--; 1923 1924 ei = (E->p[nblimbs] >> bufsize) & 1; 1925 1926 /* 1927 * skip leading 0s 1928 */ 1929 if( ei == 0 && state == 0 ) 1930 continue; 1931 1932 if( ei == 0 && state == 1 ) 1933 { 1934 /* 1935 * out of window, square X 1936 */ 1937 MBEDTLS_MPI_CHK( mbedtls_mpi_montmul( X, X, N, mm, &T ) ); 1938 continue; 1939 } 1940 1941 /* 1942 * add ei to current window 1943 */ 1944 state = 2; 1945 1946 nbits++; 1947 wbits |= ( ei << ( wsize - nbits ) ); 1948 1949 if( nbits == wsize ) 1950 { 1951 /* 1952 * X = X^wsize R^-1 mod N 1953 */ 1954 for( i = 0; i < wsize; i++ ) 1955 MBEDTLS_MPI_CHK( mbedtls_mpi_montmul( X, X, N, mm, &T ) ); 1956 1957 /* 1958 * X = X * W[wbits] R^-1 mod N 1959 */ 1960 MBEDTLS_MPI_CHK( mbedtls_mpi_montmul( X, &W[wbits], N, mm, &T ) ); 1961 1962 state--; 1963 nbits = 0; 1964 wbits = 0; 1965 } 1966 } 1967 1968 /* 1969 * process the remaining bits 1970 */ 1971 for( i = 0; i < nbits; i++ ) 1972 { 1973 MBEDTLS_MPI_CHK( mbedtls_mpi_montmul( X, X, N, mm, &T ) ); 1974 1975 wbits <<= 1; 1976 1977 if( ( wbits & ( one << wsize ) ) != 0 ) 1978 MBEDTLS_MPI_CHK( mbedtls_mpi_montmul( X, &W[1], N, mm, &T ) ); 1979 } 1980 1981 /* 1982 * X = A^E * R * R^-1 mod N = A^E mod N 1983 */ 1984 MBEDTLS_MPI_CHK( mbedtls_mpi_montred( X, N, mm, &T ) ); 1985 1986 if( neg && E->n != 0 && ( E->p[0] & 1 ) != 0 ) 1987 { 1988 X->s = -1; 1989 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( X, N, X ) ); 1990 } 1991 1992 cleanup: 1993 1994 if( W ) 1995 for( i = 0; i < array_size_W; i++ ) 1996 mbedtls_mpi_free( W + i ); 1997 mempool_free( mbedtls_mpi_mempool , W ); 1998 1999 mbedtls_mpi_free( &T ); mbedtls_mpi_free( &Apos ); 2000 2001 if( _RR == NULL || _RR->p == NULL ) 2002 mbedtls_mpi_free( &RR ); 2003 2004 return( ret ); 2005 } 2006 2007 /* 2008 * Greatest common divisor: G = gcd(A, B) (HAC 14.54) 2009 */ 2010 int mbedtls_mpi_gcd( mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B ) 2011 { 2012 int ret; 2013 size_t lz, lzt; 2014 mbedtls_mpi TG, TA, TB; 2015 2016 MPI_VALIDATE_RET( G != NULL ); 2017 MPI_VALIDATE_RET( A != NULL ); 2018 MPI_VALIDATE_RET( B != NULL ); 2019 2020 mbedtls_mpi_init_mempool( &TG ); mbedtls_mpi_init_mempool( &TA ); 2021 mbedtls_mpi_init_mempool( &TB ); 2022 2023 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) ); 2024 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) ); 2025 2026 lz = mbedtls_mpi_lsb( &TA ); 2027 lzt = mbedtls_mpi_lsb( &TB ); 2028 2029 if( lzt < lz ) 2030 lz = lzt; 2031 2032 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, lz ) ); 2033 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, lz ) ); 2034 2035 TA.s = TB.s = 1; 2036 2037 while( mbedtls_mpi_cmp_int( &TA, 0 ) != 0 ) 2038 { 2039 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, mbedtls_mpi_lsb( &TA ) ) ); 2040 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, mbedtls_mpi_lsb( &TB ) ) ); 2041 2042 if( mbedtls_mpi_cmp_mpi( &TA, &TB ) >= 0 ) 2043 { 2044 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TA, &TA, &TB ) ); 2045 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, 1 ) ); 2046 } 2047 else 2048 { 2049 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TB, &TB, &TA ) ); 2050 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, 1 ) ); 2051 } 2052 } 2053 2054 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &TB, lz ) ); 2055 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( G, &TB ) ); 2056 2057 cleanup: 2058 2059 mbedtls_mpi_free( &TG ); mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TB ); 2060 2061 return( ret ); 2062 } 2063 2064 /* 2065 * Fill X with size bytes of random. 2066 * 2067 * Use a temporary bytes representation to make sure the result is the same 2068 * regardless of the platform endianness (useful when f_rng is actually 2069 * deterministic, eg for tests). 2070 */ 2071 int mbedtls_mpi_fill_random( mbedtls_mpi *X, size_t size, 2072 int (*f_rng)(void *, unsigned char *, size_t), 2073 void *p_rng ) 2074 { 2075 int ret; 2076 unsigned char buf[MBEDTLS_MPI_MAX_SIZE]; 2077 MPI_VALIDATE_RET( X != NULL ); 2078 MPI_VALIDATE_RET( f_rng != NULL ); 2079 2080 if( size > MBEDTLS_MPI_MAX_SIZE ) 2081 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); 2082 2083 MBEDTLS_MPI_CHK( f_rng( p_rng, buf, size ) ); 2084 MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( X, buf, size ) ); 2085 2086 cleanup: 2087 mbedtls_platform_zeroize( buf, sizeof( buf ) ); 2088 return( ret ); 2089 } 2090 2091 /* 2092 * Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64) 2093 */ 2094 int mbedtls_mpi_inv_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N ) 2095 { 2096 int ret; 2097 mbedtls_mpi G, TA, TU, U1, U2, TB, TV, V1, V2; 2098 MPI_VALIDATE_RET( X != NULL ); 2099 MPI_VALIDATE_RET( A != NULL ); 2100 MPI_VALIDATE_RET( N != NULL ); 2101 2102 if( mbedtls_mpi_cmp_int( N, 1 ) <= 0 ) 2103 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); 2104 2105 mbedtls_mpi_init_mempool( &TA ); mbedtls_mpi_init_mempool( &TU ); 2106 mbedtls_mpi_init_mempool( &U1 ); mbedtls_mpi_init_mempool( &U2 ); 2107 mbedtls_mpi_init_mempool( &G ); mbedtls_mpi_init_mempool( &TB ); 2108 mbedtls_mpi_init_mempool( &TV ); mbedtls_mpi_init_mempool( &V1 ); 2109 mbedtls_mpi_init_mempool( &V2 ); 2110 2111 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &G, A, N ) ); 2112 2113 if( mbedtls_mpi_cmp_int( &G, 1 ) != 0 ) 2114 { 2115 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; 2116 goto cleanup; 2117 } 2118 2119 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &TA, A, N ) ); 2120 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TU, &TA ) ); 2121 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, N ) ); 2122 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TV, N ) ); 2123 2124 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U1, 1 ) ); 2125 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U2, 0 ) ); 2126 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V1, 0 ) ); 2127 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V2, 1 ) ); 2128 2129 do 2130 { 2131 while( ( TU.p[0] & 1 ) == 0 ) 2132 { 2133 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TU, 1 ) ); 2134 2135 if( ( U1.p[0] & 1 ) != 0 || ( U2.p[0] & 1 ) != 0 ) 2136 { 2137 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &U1, &U1, &TB ) ); 2138 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &TA ) ); 2139 } 2140 2141 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U1, 1 ) ); 2142 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U2, 1 ) ); 2143 } 2144 2145 while( ( TV.p[0] & 1 ) == 0 ) 2146 { 2147 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TV, 1 ) ); 2148 2149 if( ( V1.p[0] & 1 ) != 0 || ( V2.p[0] & 1 ) != 0 ) 2150 { 2151 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, &TB ) ); 2152 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &TA ) ); 2153 } 2154 2155 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V1, 1 ) ); 2156 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V2, 1 ) ); 2157 } 2158 2159 if( mbedtls_mpi_cmp_mpi( &TU, &TV ) >= 0 ) 2160 { 2161 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TU, &TU, &TV ) ); 2162 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U1, &U1, &V1 ) ); 2163 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &V2 ) ); 2164 } 2165 else 2166 { 2167 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TV, &TV, &TU ) ); 2168 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, &U1 ) ); 2169 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &U2 ) ); 2170 } 2171 } 2172 while( mbedtls_mpi_cmp_int( &TU, 0 ) != 0 ); 2173 2174 while( mbedtls_mpi_cmp_int( &V1, 0 ) < 0 ) 2175 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, N ) ); 2176 2177 while( mbedtls_mpi_cmp_mpi( &V1, N ) >= 0 ) 2178 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, N ) ); 2179 2180 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &V1 ) ); 2181 2182 cleanup: 2183 2184 mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TU ); mbedtls_mpi_free( &U1 ); mbedtls_mpi_free( &U2 ); 2185 mbedtls_mpi_free( &G ); mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TV ); 2186 mbedtls_mpi_free( &V1 ); mbedtls_mpi_free( &V2 ); 2187 2188 return( ret ); 2189 } 2190 2191 #if defined(MBEDTLS_GENPRIME) 2192 2193 static const int small_prime[] = 2194 { 2195 3, 5, 7, 11, 13, 17, 19, 23, 2196 29, 31, 37, 41, 43, 47, 53, 59, 2197 61, 67, 71, 73, 79, 83, 89, 97, 2198 101, 103, 107, 109, 113, 127, 131, 137, 2199 139, 149, 151, 157, 163, 167, 173, 179, 2200 181, 191, 193, 197, 199, 211, 223, 227, 2201 229, 233, 239, 241, 251, 257, 263, 269, 2202 271, 277, 281, 283, 293, 307, 311, 313, 2203 317, 331, 337, 347, 349, 353, 359, 367, 2204 373, 379, 383, 389, 397, 401, 409, 419, 2205 421, 431, 433, 439, 443, 449, 457, 461, 2206 463, 467, 479, 487, 491, 499, 503, 509, 2207 521, 523, 541, 547, 557, 563, 569, 571, 2208 577, 587, 593, 599, 601, 607, 613, 617, 2209 619, 631, 641, 643, 647, 653, 659, 661, 2210 673, 677, 683, 691, 701, 709, 719, 727, 2211 733, 739, 743, 751, 757, 761, 769, 773, 2212 787, 797, 809, 811, 821, 823, 827, 829, 2213 839, 853, 857, 859, 863, 877, 881, 883, 2214 887, 907, 911, 919, 929, 937, 941, 947, 2215 953, 967, 971, 977, 983, 991, 997, -103 2216 }; 2217 2218 /* 2219 * Small divisors test (X must be positive) 2220 * 2221 * Return values: 2222 * 0: no small factor (possible prime, more tests needed) 2223 * 1: certain prime 2224 * MBEDTLS_ERR_MPI_NOT_ACCEPTABLE: certain non-prime 2225 * other negative: error 2226 */ 2227 static int mpi_check_small_factors( const mbedtls_mpi *X ) 2228 { 2229 int ret = 0; 2230 size_t i; 2231 mbedtls_mpi_uint r; 2232 2233 if( ( X->p[0] & 1 ) == 0 ) 2234 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE ); 2235 2236 for( i = 0; small_prime[i] > 0; i++ ) 2237 { 2238 if( mbedtls_mpi_cmp_int( X, small_prime[i] ) <= 0 ) 2239 return( 1 ); 2240 2241 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, small_prime[i] ) ); 2242 2243 if( r == 0 ) 2244 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE ); 2245 } 2246 2247 cleanup: 2248 return( ret ); 2249 } 2250 2251 /* 2252 * Miller-Rabin pseudo-primality test (HAC 4.24) 2253 */ 2254 static int mpi_miller_rabin( const mbedtls_mpi *X, size_t rounds, 2255 int (*f_rng)(void *, unsigned char *, size_t), 2256 void *p_rng ) 2257 { 2258 int ret, count; 2259 size_t i, j, k, s; 2260 mbedtls_mpi W, R, T, A, RR; 2261 2262 MPI_VALIDATE_RET( X != NULL ); 2263 MPI_VALIDATE_RET( f_rng != NULL ); 2264 2265 mbedtls_mpi_init_mempool( &W ); mbedtls_mpi_init_mempool( &R ); 2266 mbedtls_mpi_init_mempool( &T ); mbedtls_mpi_init_mempool( &A ); 2267 mbedtls_mpi_init_mempool( &RR ); 2268 2269 /* 2270 * W = |X| - 1 2271 * R = W >> lsb( W ) 2272 */ 2273 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &W, X, 1 ) ); 2274 s = mbedtls_mpi_lsb( &W ); 2275 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R, &W ) ); 2276 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &R, s ) ); 2277 2278 i = mbedtls_mpi_bitlen( X ); 2279 2280 for( i = 0; i < rounds; i++ ) 2281 { 2282 /* 2283 * pick a random A, 1 < A < |X| - 1 2284 */ 2285 count = 0; 2286 do { 2287 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &A, X->n * ciL, f_rng, p_rng ) ); 2288 2289 j = mbedtls_mpi_bitlen( &A ); 2290 k = mbedtls_mpi_bitlen( &W ); 2291 if (j > k) { 2292 A.p[A.n - 1] &= ( (mbedtls_mpi_uint) 1 << ( k - ( A.n - 1 ) * biL - 1 ) ) - 1; 2293 } 2294 2295 if (count++ > 300) { 2296 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; 2297 goto cleanup; 2298 } 2299 2300 } while ( mbedtls_mpi_cmp_mpi( &A, &W ) >= 0 || 2301 mbedtls_mpi_cmp_int( &A, 1 ) <= 0 ); 2302 2303 /* 2304 * A = A^R mod |X| 2305 */ 2306 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &A, &A, &R, X, &RR ) ); 2307 2308 if( mbedtls_mpi_cmp_mpi( &A, &W ) == 0 || 2309 mbedtls_mpi_cmp_int( &A, 1 ) == 0 ) 2310 continue; 2311 2312 j = 1; 2313 while( j < s && mbedtls_mpi_cmp_mpi( &A, &W ) != 0 ) 2314 { 2315 /* 2316 * A = A * A mod |X| 2317 */ 2318 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &A, &A ) ); 2319 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &A, &T, X ) ); 2320 2321 if( mbedtls_mpi_cmp_int( &A, 1 ) == 0 ) 2322 break; 2323 2324 j++; 2325 } 2326 2327 /* 2328 * not prime if A != |X| - 1 or A == 1 2329 */ 2330 if( mbedtls_mpi_cmp_mpi( &A, &W ) != 0 || 2331 mbedtls_mpi_cmp_int( &A, 1 ) == 0 ) 2332 { 2333 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; 2334 break; 2335 } 2336 } 2337 2338 cleanup: 2339 mbedtls_mpi_free( &W ); mbedtls_mpi_free( &R ); 2340 mbedtls_mpi_free( &T ); mbedtls_mpi_free( &A ); 2341 mbedtls_mpi_free( &RR ); 2342 2343 return( ret ); 2344 } 2345 2346 /* 2347 * Pseudo-primality test: small factors, then Miller-Rabin 2348 */ 2349 int mbedtls_mpi_is_prime_ext( const mbedtls_mpi *X, int rounds, 2350 int (*f_rng)(void *, unsigned char *, size_t), 2351 void *p_rng ) 2352 { 2353 int ret; 2354 mbedtls_mpi XX; 2355 MPI_VALIDATE_RET( X != NULL ); 2356 MPI_VALIDATE_RET( f_rng != NULL ); 2357 2358 XX.s = 1; 2359 XX.n = X->n; 2360 XX.p = X->p; 2361 2362 if( mbedtls_mpi_cmp_int( &XX, 0 ) == 0 || 2363 mbedtls_mpi_cmp_int( &XX, 1 ) == 0 ) 2364 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE ); 2365 2366 if( mbedtls_mpi_cmp_int( &XX, 2 ) == 0 ) 2367 return( 0 ); 2368 2369 if( ( ret = mpi_check_small_factors( &XX ) ) != 0 ) 2370 { 2371 if( ret == 1 ) 2372 return( 0 ); 2373 2374 return( ret ); 2375 } 2376 2377 return( mpi_miller_rabin( &XX, rounds, f_rng, p_rng ) ); 2378 } 2379 2380 #if !defined(MBEDTLS_DEPRECATED_REMOVED) 2381 /* 2382 * Pseudo-primality test, error probability 2^-80 2383 */ 2384 int mbedtls_mpi_is_prime( const mbedtls_mpi *X, 2385 int (*f_rng)(void *, unsigned char *, size_t), 2386 void *p_rng ) 2387 { 2388 MPI_VALIDATE_RET( X != NULL ); 2389 MPI_VALIDATE_RET( f_rng != NULL ); 2390 2391 /* 2392 * In the past our key generation aimed for an error rate of at most 2393 * 2^-80. Since this function is deprecated, aim for the same certainty 2394 * here as well. 2395 */ 2396 return( mbedtls_mpi_is_prime_ext( X, 40, f_rng, p_rng ) ); 2397 } 2398 #endif 2399 2400 /* 2401 * Prime number generation 2402 * 2403 * To generate an RSA key in a way recommended by FIPS 186-4, both primes must 2404 * be either 1024 bits or 1536 bits long, and flags must contain 2405 * MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR. 2406 */ 2407 int mbedtls_mpi_gen_prime( mbedtls_mpi *X, size_t nbits, int flags, 2408 int (*f_rng)(void *, unsigned char *, size_t), 2409 void *p_rng ) 2410 { 2411 #ifdef MBEDTLS_HAVE_INT64 2412 // ceil(2^63.5) 2413 #define CEIL_MAXUINT_DIV_SQRT2 0xb504f333f9de6485ULL 2414 #else 2415 // ceil(2^31.5) 2416 #define CEIL_MAXUINT_DIV_SQRT2 0xb504f334U 2417 #endif 2418 int ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; 2419 size_t k, n; 2420 int rounds; 2421 mbedtls_mpi_uint r; 2422 mbedtls_mpi Y; 2423 2424 MPI_VALIDATE_RET( X != NULL ); 2425 MPI_VALIDATE_RET( f_rng != NULL ); 2426 2427 if( nbits < 3 || nbits > MBEDTLS_MPI_MAX_BITS ) 2428 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA ); 2429 2430 mbedtls_mpi_init_mempool( &Y ); 2431 2432 n = BITS_TO_LIMBS( nbits ); 2433 2434 if( ( flags & MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR ) == 0 ) 2435 { 2436 /* 2437 * 2^-80 error probability, number of rounds chosen per HAC, table 4.4 2438 */ 2439 rounds = ( ( nbits >= 1300 ) ? 2 : ( nbits >= 850 ) ? 3 : 2440 ( nbits >= 650 ) ? 4 : ( nbits >= 350 ) ? 8 : 2441 ( nbits >= 250 ) ? 12 : ( nbits >= 150 ) ? 18 : 27 ); 2442 } 2443 else 2444 { 2445 /* 2446 * 2^-100 error probability, number of rounds computed based on HAC, 2447 * fact 4.48 2448 */ 2449 rounds = ( ( nbits >= 1450 ) ? 4 : ( nbits >= 1150 ) ? 5 : 2450 ( nbits >= 1000 ) ? 6 : ( nbits >= 850 ) ? 7 : 2451 ( nbits >= 750 ) ? 8 : ( nbits >= 500 ) ? 13 : 2452 ( nbits >= 250 ) ? 28 : ( nbits >= 150 ) ? 40 : 51 ); 2453 } 2454 2455 while( 1 ) 2456 { 2457 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( X, n * ciL, f_rng, p_rng ) ); 2458 /* make sure generated number is at least (nbits-1)+0.5 bits (FIPS 186-4 §B.3.3 steps 4.4, 5.5) */ 2459 if( X->p[n-1] < CEIL_MAXUINT_DIV_SQRT2 ) continue; 2460 2461 k = n * biL; 2462 if( k > nbits ) MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( X, k - nbits ) ); 2463 X->p[0] |= 1; 2464 2465 if( ( flags & MBEDTLS_MPI_GEN_PRIME_FLAG_DH ) == 0 ) 2466 { 2467 ret = mbedtls_mpi_is_prime_ext( X, rounds, f_rng, p_rng ); 2468 2469 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE ) 2470 goto cleanup; 2471 } 2472 else 2473 { 2474 /* 2475 * An necessary condition for Y and X = 2Y + 1 to be prime 2476 * is X = 2 mod 3 (which is equivalent to Y = 2 mod 3). 2477 * Make sure it is satisfied, while keeping X = 3 mod 4 2478 */ 2479 2480 X->p[0] |= 2; 2481 2482 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, 3 ) ); 2483 if( r == 0 ) 2484 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 8 ) ); 2485 else if( r == 1 ) 2486 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 4 ) ); 2487 2488 /* Set Y = (X-1) / 2, which is X / 2 because X is odd */ 2489 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, X ) ); 2490 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, 1 ) ); 2491 2492 while( 1 ) 2493 { 2494 /* 2495 * First, check small factors for X and Y 2496 * before doing Miller-Rabin on any of them 2497 */ 2498 if( ( ret = mpi_check_small_factors( X ) ) == 0 && 2499 ( ret = mpi_check_small_factors( &Y ) ) == 0 && 2500 ( ret = mpi_miller_rabin( X, rounds, f_rng, p_rng ) ) 2501 == 0 && 2502 ( ret = mpi_miller_rabin( &Y, rounds, f_rng, p_rng ) ) 2503 == 0 ) 2504 goto cleanup; 2505 2506 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE ) 2507 goto cleanup; 2508 2509 /* 2510 * Next candidates. We want to preserve Y = (X-1) / 2 and 2511 * Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3) 2512 * so up Y by 6 and X by 12. 2513 */ 2514 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 12 ) ); 2515 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( &Y, &Y, 6 ) ); 2516 } 2517 } 2518 } 2519 2520 cleanup: 2521 2522 mbedtls_mpi_free( &Y ); 2523 2524 return( ret ); 2525 } 2526 2527 #endif /* MBEDTLS_GENPRIME */ 2528 2529 #if defined(MBEDTLS_SELF_TEST) 2530 2531 #define GCD_PAIR_COUNT 3 2532 2533 static const int gcd_pairs[GCD_PAIR_COUNT][3] = 2534 { 2535 { 693, 609, 21 }, 2536 { 1764, 868, 28 }, 2537 { 768454923, 542167814, 1 } 2538 }; 2539 2540 /* 2541 * Checkup routine 2542 */ 2543 int mbedtls_mpi_self_test( int verbose ) 2544 { 2545 int ret, i; 2546 mbedtls_mpi A, E, N, X, Y, U, V; 2547 2548 mbedtls_mpi_init_mempool( &A ); mbedtls_mpi_init_mempool( &E ); 2549 mbedtls_mpi_init_mempool( &N ); mbedtls_mpi_init_mempool( &X ); 2550 mbedtls_mpi_init_mempool( &Y ); mbedtls_mpi_init_mempool( &U ); 2551 mbedtls_mpi_init_mempool( &V ); 2552 2553 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &A, 16, 2554 "EFE021C2645FD1DC586E69184AF4A31E" \ 2555 "D5F53E93B5F123FA41680867BA110131" \ 2556 "944FE7952E2517337780CB0DB80E61AA" \ 2557 "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) ); 2558 2559 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &E, 16, 2560 "B2E7EFD37075B9F03FF989C7C5051C20" \ 2561 "34D2A323810251127E7BF8625A4F49A5" \ 2562 "F3E27F4DA8BD59C47D6DAABA4C8127BD" \ 2563 "5B5C25763222FEFCCFC38B832366C29E" ) ); 2564 2565 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &N, 16, 2566 "0066A198186C18C10B2F5ED9B522752A" \ 2567 "9830B69916E535C8F047518A889A43A5" \ 2568 "94B6BED27A168D31D4A52F88925AA8F5" ) ); 2569 2570 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &X, &A, &N ) ); 2571 2572 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16, 2573 "602AB7ECA597A3D6B56FF9829A5E8B85" \ 2574 "9E857EA95A03512E2BAE7391688D264A" \ 2575 "A5663B0341DB9CCFD2C4C5F421FEC814" \ 2576 "8001B72E848A38CAE1C65F78E56ABDEF" \ 2577 "E12D3C039B8A02D6BE593F0BBBDA56F1" \ 2578 "ECF677152EF804370C1A305CAF3B5BF1" \ 2579 "30879B56C61DE584A0F53A2447A51E" ) ); 2580 2581 if( verbose != 0 ) 2582 mbedtls_printf( " MPI test #1 (mul_mpi): " ); 2583 2584 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 ) 2585 { 2586 if( verbose != 0 ) 2587 mbedtls_printf( "failed\n" ); 2588 2589 ret = 1; 2590 goto cleanup; 2591 } 2592 2593 if( verbose != 0 ) 2594 mbedtls_printf( "passed\n" ); 2595 2596 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( &X, &Y, &A, &N ) ); 2597 2598 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16, 2599 "256567336059E52CAE22925474705F39A94" ) ); 2600 2601 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &V, 16, 2602 "6613F26162223DF488E9CD48CC132C7A" \ 2603 "0AC93C701B001B092E4E5B9F73BCD27B" \ 2604 "9EE50D0657C77F374E903CDFA4C642" ) ); 2605 2606 if( verbose != 0 ) 2607 mbedtls_printf( " MPI test #2 (div_mpi): " ); 2608 2609 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 || 2610 mbedtls_mpi_cmp_mpi( &Y, &V ) != 0 ) 2611 { 2612 if( verbose != 0 ) 2613 mbedtls_printf( "failed\n" ); 2614 2615 ret = 1; 2616 goto cleanup; 2617 } 2618 2619 if( verbose != 0 ) 2620 mbedtls_printf( "passed\n" ); 2621 2622 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &X, &A, &E, &N, NULL ) ); 2623 2624 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16, 2625 "36E139AEA55215609D2816998ED020BB" \ 2626 "BD96C37890F65171D948E9BC7CBAA4D9" \ 2627 "325D24D6A3C12710F10A09FA08AB87" ) ); 2628 2629 if( verbose != 0 ) 2630 mbedtls_printf( " MPI test #3 (exp_mod): " ); 2631 2632 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 ) 2633 { 2634 if( verbose != 0 ) 2635 mbedtls_printf( "failed\n" ); 2636 2637 ret = 1; 2638 goto cleanup; 2639 } 2640 2641 if( verbose != 0 ) 2642 mbedtls_printf( "passed\n" ); 2643 2644 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &X, &A, &N ) ); 2645 2646 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16, 2647 "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \ 2648 "C3DBA76456363A10869622EAC2DD84EC" \ 2649 "C5B8A74DAC4D09E03B5E0BE779F2DF61" ) ); 2650 2651 if( verbose != 0 ) 2652 mbedtls_printf( " MPI test #4 (inv_mod): " ); 2653 2654 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 ) 2655 { 2656 if( verbose != 0 ) 2657 mbedtls_printf( "failed\n" ); 2658 2659 ret = 1; 2660 goto cleanup; 2661 } 2662 2663 if( verbose != 0 ) 2664 mbedtls_printf( "passed\n" ); 2665 2666 if( verbose != 0 ) 2667 mbedtls_printf( " MPI test #5 (simple gcd): " ); 2668 2669 for( i = 0; i < GCD_PAIR_COUNT; i++ ) 2670 { 2671 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &X, gcd_pairs[i][0] ) ); 2672 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Y, gcd_pairs[i][1] ) ); 2673 2674 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &A, &X, &Y ) ); 2675 2676 if( mbedtls_mpi_cmp_int( &A, gcd_pairs[i][2] ) != 0 ) 2677 { 2678 if( verbose != 0 ) 2679 mbedtls_printf( "failed at %d\n", i ); 2680 2681 ret = 1; 2682 goto cleanup; 2683 } 2684 } 2685 2686 if( verbose != 0 ) 2687 mbedtls_printf( "passed\n" ); 2688 2689 cleanup: 2690 2691 if( ret != 0 && verbose != 0 ) 2692 mbedtls_printf( "Unexpected error, return code = %08X\n", ret ); 2693 2694 mbedtls_mpi_free( &A ); mbedtls_mpi_free( &E ); mbedtls_mpi_free( &N ); mbedtls_mpi_free( &X ); 2695 mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &U ); mbedtls_mpi_free( &V ); 2696 2697 if( verbose != 0 ) 2698 mbedtls_printf( "\n" ); 2699 2700 return( ret ); 2701 } 2702 2703 #endif /* MBEDTLS_SELF_TEST */ 2704 2705 #endif /* MBEDTLS_BIGNUM_C */ 2706