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