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