1 /** 2 * \file bignum.h 3 * 4 * \brief Multi-precision integer library 5 */ 6 /* 7 * Copyright (C) 2006-2015, ARM Limited, All Rights Reserved 8 * SPDX-License-Identifier: Apache-2.0 9 * 10 * Licensed under the Apache License, Version 2.0 (the "License"); you may 11 * not use this file except in compliance with the License. 12 * You may obtain a copy of the License at 13 * 14 * http://www.apache.org/licenses/LICENSE-2.0 15 * 16 * Unless required by applicable law or agreed to in writing, software 17 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT 18 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 19 * See the License for the specific language governing permissions and 20 * limitations under the License. 21 * 22 * This file is part of mbed TLS (https://tls.mbed.org) 23 */ 24 #ifndef MBEDTLS_BIGNUM_H 25 #define MBEDTLS_BIGNUM_H 26 27 #if !defined(MBEDTLS_CONFIG_FILE) 28 #include "config.h" 29 #else 30 #include MBEDTLS_CONFIG_FILE 31 #endif 32 33 #include <stddef.h> 34 #include <stdint.h> 35 36 #if defined(MBEDTLS_FS_IO) 37 #include <stdio.h> 38 #endif 39 40 #define MBEDTLS_ERR_MPI_FILE_IO_ERROR -0x0002 /**< An error occurred while reading from or writing to a file. */ 41 #define MBEDTLS_ERR_MPI_BAD_INPUT_DATA -0x0004 /**< Bad input parameters to function. */ 42 #define MBEDTLS_ERR_MPI_INVALID_CHARACTER -0x0006 /**< There is an invalid character in the digit string. */ 43 #define MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL -0x0008 /**< The buffer is too small to write to. */ 44 #define MBEDTLS_ERR_MPI_NEGATIVE_VALUE -0x000A /**< The input arguments are negative or result in illegal output. */ 45 #define MBEDTLS_ERR_MPI_DIVISION_BY_ZERO -0x000C /**< The input argument for division is zero, which is not allowed. */ 46 #define MBEDTLS_ERR_MPI_NOT_ACCEPTABLE -0x000E /**< The input arguments are not acceptable. */ 47 #define MBEDTLS_ERR_MPI_ALLOC_FAILED -0x0010 /**< Memory allocation failed. */ 48 49 #define MBEDTLS_MPI_CHK(f) do { if( ( ret = f ) != 0 ) goto cleanup; } while( 0 ) 50 51 /* 52 * Maximum size MPIs are allowed to grow to in number of limbs. 53 */ 54 #define MBEDTLS_MPI_MAX_LIMBS 10000 55 56 #if !defined(MBEDTLS_MPI_WINDOW_SIZE) 57 /* 58 * Maximum window size used for modular exponentiation. Default: 6 59 * Minimum value: 1. Maximum value: 6. 60 * 61 * Result is an array of ( 2 << MBEDTLS_MPI_WINDOW_SIZE ) MPIs used 62 * for the sliding window calculation. (So 64 by default) 63 * 64 * Reduction in size, reduces speed. 65 */ 66 #define MBEDTLS_MPI_WINDOW_SIZE 6 /**< Maximum windows size used. */ 67 #endif /* !MBEDTLS_MPI_WINDOW_SIZE */ 68 69 #if !defined(MBEDTLS_MPI_MAX_SIZE) 70 /* 71 * Maximum size of MPIs allowed in bits and bytes for user-MPIs. 72 * ( Default: 512 bytes => 4096 bits, Maximum tested: 2048 bytes => 16384 bits ) 73 * 74 * Note: Calculations can temporarily result in larger MPIs. So the number 75 * of limbs required (MBEDTLS_MPI_MAX_LIMBS) is higher. 76 */ 77 #define MBEDTLS_MPI_MAX_SIZE 1024 /**< Maximum number of bytes for usable MPIs. */ 78 #endif /* !MBEDTLS_MPI_MAX_SIZE */ 79 80 #define MBEDTLS_MPI_MAX_BITS ( 8 * MBEDTLS_MPI_MAX_SIZE ) /**< Maximum number of bits for usable MPIs. */ 81 82 /* 83 * When reading from files with mbedtls_mpi_read_file() and writing to files with 84 * mbedtls_mpi_write_file() the buffer should have space 85 * for a (short) label, the MPI (in the provided radix), the newline 86 * characters and the '\0'. 87 * 88 * By default we assume at least a 10 char label, a minimum radix of 10 89 * (decimal) and a maximum of 4096 bit numbers (1234 decimal chars). 90 * Autosized at compile time for at least a 10 char label, a minimum radix 91 * of 10 (decimal) for a number of MBEDTLS_MPI_MAX_BITS size. 92 * 93 * This used to be statically sized to 1250 for a maximum of 4096 bit 94 * numbers (1234 decimal chars). 95 * 96 * Calculate using the formula: 97 * MBEDTLS_MPI_RW_BUFFER_SIZE = ceil(MBEDTLS_MPI_MAX_BITS / ln(10) * ln(2)) + 98 * LabelSize + 6 99 */ 100 #define MBEDTLS_MPI_MAX_BITS_SCALE100 ( 100 * MBEDTLS_MPI_MAX_BITS ) 101 #define MBEDTLS_LN_2_DIV_LN_10_SCALE100 332 102 #define MBEDTLS_MPI_RW_BUFFER_SIZE ( ((MBEDTLS_MPI_MAX_BITS_SCALE100 + MBEDTLS_LN_2_DIV_LN_10_SCALE100 - 1) / MBEDTLS_LN_2_DIV_LN_10_SCALE100) + 10 + 6 ) 103 104 /* 105 * Define the base integer type, architecture-wise. 106 * 107 * 32 or 64-bit integer types can be forced regardless of the underlying 108 * architecture by defining MBEDTLS_HAVE_INT32 or MBEDTLS_HAVE_INT64 109 * respectively and undefining MBEDTLS_HAVE_ASM. 110 * 111 * Double-width integers (e.g. 128-bit in 64-bit architectures) can be 112 * disabled by defining MBEDTLS_NO_UDBL_DIVISION. 113 */ 114 #if !defined(MBEDTLS_HAVE_INT32) 115 #if defined(_MSC_VER) && defined(_M_AMD64) 116 /* Always choose 64-bit when using MSC */ 117 #if !defined(MBEDTLS_HAVE_INT64) 118 #define MBEDTLS_HAVE_INT64 119 #endif /* !MBEDTLS_HAVE_INT64 */ 120 typedef int64_t mbedtls_mpi_sint; 121 typedef uint64_t mbedtls_mpi_uint; 122 #elif defined(__GNUC__) && ( \ 123 defined(__amd64__) || defined(__x86_64__) || \ 124 defined(__ppc64__) || defined(__powerpc64__) || \ 125 defined(__ia64__) || defined(__alpha__) || \ 126 ( defined(__sparc__) && defined(__arch64__) ) || \ 127 defined(__s390x__) || defined(__mips64) ) 128 #if !defined(MBEDTLS_HAVE_INT64) 129 #define MBEDTLS_HAVE_INT64 130 #endif /* MBEDTLS_HAVE_INT64 */ 131 typedef int64_t mbedtls_mpi_sint; 132 typedef uint64_t mbedtls_mpi_uint; 133 #if !defined(MBEDTLS_NO_UDBL_DIVISION) 134 /* mbedtls_t_udbl defined as 128-bit unsigned int */ 135 typedef unsigned int mbedtls_t_udbl __attribute__((mode(TI))); 136 #define MBEDTLS_HAVE_UDBL 137 #endif /* !MBEDTLS_NO_UDBL_DIVISION */ 138 #elif defined(__ARMCC_VERSION) && defined(__aarch64__) 139 /* 140 * __ARMCC_VERSION is defined for both armcc and armclang and 141 * __aarch64__ is only defined by armclang when compiling 64-bit code 142 */ 143 #if !defined(MBEDTLS_HAVE_INT64) 144 #define MBEDTLS_HAVE_INT64 145 #endif /* !MBEDTLS_HAVE_INT64 */ 146 typedef int64_t mbedtls_mpi_sint; 147 typedef uint64_t mbedtls_mpi_uint; 148 #if !defined(MBEDTLS_NO_UDBL_DIVISION) 149 /* mbedtls_t_udbl defined as 128-bit unsigned int */ 150 typedef __uint128_t mbedtls_t_udbl; 151 #define MBEDTLS_HAVE_UDBL 152 #endif /* !MBEDTLS_NO_UDBL_DIVISION */ 153 #elif defined(MBEDTLS_HAVE_INT64) 154 /* Force 64-bit integers with unknown compiler */ 155 typedef int64_t mbedtls_mpi_sint; 156 typedef uint64_t mbedtls_mpi_uint; 157 #endif 158 #endif /* !MBEDTLS_HAVE_INT32 */ 159 160 #if !defined(MBEDTLS_HAVE_INT64) 161 /* Default to 32-bit compilation */ 162 #if !defined(MBEDTLS_HAVE_INT32) 163 #define MBEDTLS_HAVE_INT32 164 #endif /* !MBEDTLS_HAVE_INT32 */ 165 typedef int32_t mbedtls_mpi_sint; 166 typedef uint32_t mbedtls_mpi_uint; 167 #if !defined(MBEDTLS_NO_UDBL_DIVISION) 168 typedef uint64_t mbedtls_t_udbl; 169 #define MBEDTLS_HAVE_UDBL 170 #endif /* !MBEDTLS_NO_UDBL_DIVISION */ 171 #endif /* !MBEDTLS_HAVE_INT64 */ 172 173 #ifdef __cplusplus 174 extern "C" { 175 #endif 176 177 /** 178 * \brief MPI structure 179 */ 180 typedef struct mbedtls_mpi 181 { 182 int s; /*!< integer sign */ 183 size_t n; /*!< total # of limbs */ 184 mbedtls_mpi_uint *p; /*!< pointer to limbs */ 185 } 186 mbedtls_mpi; 187 188 /** 189 * \brief Initialize one MPI (make internal references valid) 190 * This just makes it ready to be set or freed, 191 * but does not define a value for the MPI. 192 * 193 * \param X One MPI to initialize. 194 */ 195 void mbedtls_mpi_init( mbedtls_mpi *X ); 196 197 /** 198 * \brief Unallocate one MPI 199 * 200 * \param X One MPI to unallocate. 201 */ 202 void mbedtls_mpi_free( mbedtls_mpi *X ); 203 204 /** 205 * \brief Enlarge to the specified number of limbs 206 * 207 * This function does nothing if the MPI is already large enough. 208 * 209 * \param X MPI to grow 210 * \param nblimbs The target number of limbs 211 * 212 * \return 0 if successful, 213 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed 214 */ 215 int mbedtls_mpi_grow( mbedtls_mpi *X, size_t nblimbs ); 216 217 /** 218 * \brief Resize down, keeping at least the specified number of limbs 219 * 220 * If \c X is smaller than \c nblimbs, it is resized up 221 * instead. 222 * 223 * \param X MPI to shrink 224 * \param nblimbs The minimum number of limbs to keep 225 * 226 * \return 0 if successful, 227 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed 228 * (this can only happen when resizing up). 229 */ 230 int mbedtls_mpi_shrink( mbedtls_mpi *X, size_t nblimbs ); 231 232 /** 233 * \brief Copy the contents of Y into X 234 * 235 * \param X Destination MPI. It is enlarged if necessary. 236 * \param Y Source MPI. 237 * 238 * \return 0 if successful, 239 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed 240 */ 241 int mbedtls_mpi_copy( mbedtls_mpi *X, const mbedtls_mpi *Y ); 242 243 /** 244 * \brief Swap the contents of X and Y 245 * 246 * \param X First MPI value 247 * \param Y Second MPI value 248 */ 249 void mbedtls_mpi_swap( mbedtls_mpi *X, mbedtls_mpi *Y ); 250 251 /** 252 * \brief Safe conditional assignement X = Y if assign is 1 253 * 254 * \param X MPI to conditionally assign to 255 * \param Y Value to be assigned 256 * \param assign 1: perform the assignment, 0: keep X's original value 257 * 258 * \return 0 if successful, 259 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed, 260 * 261 * \note This function is equivalent to 262 * if( assign ) mbedtls_mpi_copy( X, Y ); 263 * except that it avoids leaking any information about whether 264 * the assignment was done or not (the above code may leak 265 * information through branch prediction and/or memory access 266 * patterns analysis). 267 */ 268 int mbedtls_mpi_safe_cond_assign( mbedtls_mpi *X, const mbedtls_mpi *Y, unsigned char assign ); 269 270 /** 271 * \brief Safe conditional swap X <-> Y if swap is 1 272 * 273 * \param X First mbedtls_mpi value 274 * \param Y Second mbedtls_mpi value 275 * \param assign 1: perform the swap, 0: keep X and Y's original values 276 * 277 * \return 0 if successful, 278 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed, 279 * 280 * \note This function is equivalent to 281 * if( assign ) mbedtls_mpi_swap( X, Y ); 282 * except that it avoids leaking any information about whether 283 * the assignment was done or not (the above code may leak 284 * information through branch prediction and/or memory access 285 * patterns analysis). 286 */ 287 int mbedtls_mpi_safe_cond_swap( mbedtls_mpi *X, mbedtls_mpi *Y, unsigned char assign ); 288 289 /** 290 * \brief Set value from integer 291 * 292 * \param X MPI to set 293 * \param z Value to use 294 * 295 * \return 0 if successful, 296 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed 297 */ 298 int mbedtls_mpi_lset( mbedtls_mpi *X, mbedtls_mpi_sint z ); 299 300 /** 301 * \brief Get a specific bit from X 302 * 303 * \param X MPI to use 304 * \param pos Zero-based index of the bit in X 305 * 306 * \return Either a 0 or a 1 307 */ 308 int mbedtls_mpi_get_bit( const mbedtls_mpi *X, size_t pos ); 309 310 /** 311 * \brief Set a bit of X to a specific value of 0 or 1 312 * 313 * \note Will grow X if necessary to set a bit to 1 in a not yet 314 * existing limb. Will not grow if bit should be set to 0 315 * 316 * \param X MPI to use 317 * \param pos Zero-based index of the bit in X 318 * \param val The value to set the bit to (0 or 1) 319 * 320 * \return 0 if successful, 321 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed, 322 * MBEDTLS_ERR_MPI_BAD_INPUT_DATA if val is not 0 or 1 323 */ 324 int mbedtls_mpi_set_bit( mbedtls_mpi *X, size_t pos, unsigned char val ); 325 326 /** 327 * \brief Return the number of zero-bits before the least significant 328 * '1' bit 329 * 330 * Note: Thus also the zero-based index of the least significant '1' bit 331 * 332 * \param X MPI to use 333 */ 334 size_t mbedtls_mpi_lsb( const mbedtls_mpi *X ); 335 336 /** 337 * \brief Return the number of bits up to and including the most 338 * significant '1' bit' 339 * 340 * Note: Thus also the one-based index of the most significant '1' bit 341 * 342 * \param X MPI to use 343 */ 344 size_t mbedtls_mpi_bitlen( const mbedtls_mpi *X ); 345 346 /** 347 * \brief Return the total size in bytes 348 * 349 * \param X MPI to use 350 */ 351 size_t mbedtls_mpi_size( const mbedtls_mpi *X ); 352 353 /** 354 * \brief Import from an ASCII string 355 * 356 * \param X Destination MPI 357 * \param radix Input numeric base 358 * \param s Null-terminated string buffer 359 * 360 * \return 0 if successful, or a MBEDTLS_ERR_MPI_XXX error code 361 */ 362 int mbedtls_mpi_read_string( mbedtls_mpi *X, int radix, const char *s ); 363 364 /** 365 * \brief Export into an ASCII string 366 * 367 * \param X Source MPI 368 * \param radix Output numeric base 369 * \param buf Buffer to write the string to 370 * \param buflen Length of buf 371 * \param olen Length of the string written, including final NUL byte 372 * 373 * \return 0 if successful, or a MBEDTLS_ERR_MPI_XXX error code. 374 * *olen is always updated to reflect the amount 375 * of data that has (or would have) been written. 376 * 377 * \note Call this function with buflen = 0 to obtain the 378 * minimum required buffer size in *olen. 379 */ 380 int mbedtls_mpi_write_string( const mbedtls_mpi *X, int radix, 381 char *buf, size_t buflen, size_t *olen ); 382 383 #if defined(MBEDTLS_FS_IO) 384 /** 385 * \brief Read MPI from a line in an opened file 386 * 387 * \param X Destination MPI 388 * \param radix Input numeric base 389 * \param fin Input file handle 390 * 391 * \return 0 if successful, MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if 392 * the file read buffer is too small or a 393 * MBEDTLS_ERR_MPI_XXX error code 394 * 395 * \note On success, this function advances the file stream 396 * to the end of the current line or to EOF. 397 * 398 * The function returns 0 on an empty line. 399 * 400 * Leading whitespaces are ignored, as is a 401 * '0x' prefix for radix 16. 402 * 403 */ 404 int mbedtls_mpi_read_file( mbedtls_mpi *X, int radix, FILE *fin ); 405 406 /** 407 * \brief Write X into an opened file, or stdout if fout is NULL 408 * 409 * \param p Prefix, can be NULL 410 * \param X Source MPI 411 * \param radix Output numeric base 412 * \param fout Output file handle (can be NULL) 413 * 414 * \return 0 if successful, or a MBEDTLS_ERR_MPI_XXX error code 415 * 416 * \note Set fout == NULL to print X on the console. 417 */ 418 int mbedtls_mpi_write_file( const char *p, const mbedtls_mpi *X, int radix, FILE *fout ); 419 #endif /* MBEDTLS_FS_IO */ 420 421 /** 422 * \brief Import X from unsigned binary data, big endian 423 * 424 * \param X Destination MPI 425 * \param buf Input buffer 426 * \param buflen Input buffer size 427 * 428 * \return 0 if successful, 429 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed 430 */ 431 int mbedtls_mpi_read_binary( mbedtls_mpi *X, const unsigned char *buf, size_t buflen ); 432 433 /** 434 * \brief Export X into unsigned binary data, big endian. 435 * Always fills the whole buffer, which will start with zeros 436 * if the number is smaller. 437 * 438 * \param X Source MPI 439 * \param buf Output buffer 440 * \param buflen Output buffer size 441 * 442 * \return 0 if successful, 443 * MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if buf isn't large enough 444 */ 445 int mbedtls_mpi_write_binary( const mbedtls_mpi *X, unsigned char *buf, size_t buflen ); 446 447 /** 448 * \brief Left-shift: X <<= count 449 * 450 * \param X MPI to shift 451 * \param count Amount to shift 452 * 453 * \return 0 if successful, 454 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed 455 */ 456 int mbedtls_mpi_shift_l( mbedtls_mpi *X, size_t count ); 457 458 /** 459 * \brief Right-shift: X >>= count 460 * 461 * \param X MPI to shift 462 * \param count Amount to shift 463 * 464 * \return 0 if successful, 465 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed 466 */ 467 int mbedtls_mpi_shift_r( mbedtls_mpi *X, size_t count ); 468 469 /** 470 * \brief Compare unsigned values 471 * 472 * \param X Left-hand MPI 473 * \param Y Right-hand MPI 474 * 475 * \return 1 if |X| is greater than |Y|, 476 * -1 if |X| is lesser than |Y| or 477 * 0 if |X| is equal to |Y| 478 */ 479 int mbedtls_mpi_cmp_abs( const mbedtls_mpi *X, const mbedtls_mpi *Y ); 480 481 /** 482 * \brief Compare signed values 483 * 484 * \param X Left-hand MPI 485 * \param Y Right-hand MPI 486 * 487 * \return 1 if X is greater than Y, 488 * -1 if X is lesser than Y or 489 * 0 if X is equal to Y 490 */ 491 int mbedtls_mpi_cmp_mpi( const mbedtls_mpi *X, const mbedtls_mpi *Y ); 492 493 /** 494 * \brief Compare signed values 495 * 496 * \param X Left-hand MPI 497 * \param z The integer value to compare to 498 * 499 * \return 1 if X is greater than z, 500 * -1 if X is lesser than z or 501 * 0 if X is equal to z 502 */ 503 int mbedtls_mpi_cmp_int( const mbedtls_mpi *X, mbedtls_mpi_sint z ); 504 505 /** 506 * \brief Unsigned addition: X = |A| + |B| 507 * 508 * \param X Destination MPI 509 * \param A Left-hand MPI 510 * \param B Right-hand MPI 511 * 512 * \return 0 if successful, 513 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed 514 */ 515 int mbedtls_mpi_add_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B ); 516 517 /** 518 * \brief Unsigned subtraction: X = |A| - |B| 519 * 520 * \param X Destination MPI 521 * \param A Left-hand MPI 522 * \param B Right-hand MPI 523 * 524 * \return 0 if successful, 525 * MBEDTLS_ERR_MPI_NEGATIVE_VALUE if B is greater than A 526 */ 527 int mbedtls_mpi_sub_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B ); 528 529 /** 530 * \brief Signed addition: X = A + B 531 * 532 * \param X Destination MPI 533 * \param A Left-hand MPI 534 * \param B Right-hand MPI 535 * 536 * \return 0 if successful, 537 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed 538 */ 539 int mbedtls_mpi_add_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B ); 540 541 /** 542 * \brief Signed subtraction: X = A - B 543 * 544 * \param X Destination MPI 545 * \param A Left-hand MPI 546 * \param B Right-hand MPI 547 * 548 * \return 0 if successful, 549 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed 550 */ 551 int mbedtls_mpi_sub_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B ); 552 553 /** 554 * \brief Signed addition: X = A + b 555 * 556 * \param X Destination MPI 557 * \param A Left-hand MPI 558 * \param b The integer value to add 559 * 560 * \return 0 if successful, 561 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed 562 */ 563 int mbedtls_mpi_add_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b ); 564 565 /** 566 * \brief Signed subtraction: X = A - b 567 * 568 * \param X Destination MPI 569 * \param A Left-hand MPI 570 * \param b The integer value to subtract 571 * 572 * \return 0 if successful, 573 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed 574 */ 575 int mbedtls_mpi_sub_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b ); 576 577 /** 578 * \brief Baseline multiplication: X = A * B 579 * 580 * \param X Destination MPI 581 * \param A Left-hand MPI 582 * \param B Right-hand MPI 583 * 584 * \return 0 if successful, 585 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed 586 */ 587 int mbedtls_mpi_mul_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B ); 588 589 /** 590 * \brief Baseline multiplication: X = A * b 591 * 592 * \param X Destination MPI 593 * \param A Left-hand MPI 594 * \param b The unsigned integer value to multiply with 595 * 596 * \note b is unsigned 597 * 598 * \return 0 if successful, 599 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed 600 */ 601 int mbedtls_mpi_mul_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b ); 602 603 /** 604 * \brief Division by mbedtls_mpi: A = Q * B + R 605 * 606 * \param Q Destination MPI for the quotient 607 * \param R Destination MPI for the rest value 608 * \param A Left-hand MPI 609 * \param B Right-hand MPI 610 * 611 * \return 0 if successful, 612 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed, 613 * MBEDTLS_ERR_MPI_DIVISION_BY_ZERO if B == 0 614 * 615 * \note Either Q or R can be NULL. 616 */ 617 int mbedtls_mpi_div_mpi( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B ); 618 619 /** 620 * \brief Division by int: A = Q * b + R 621 * 622 * \param Q Destination MPI for the quotient 623 * \param R Destination MPI for the rest value 624 * \param A Left-hand MPI 625 * \param b Integer to divide by 626 * 627 * \return 0 if successful, 628 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed, 629 * MBEDTLS_ERR_MPI_DIVISION_BY_ZERO if b == 0 630 * 631 * \note Either Q or R can be NULL. 632 */ 633 int mbedtls_mpi_div_int( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A, mbedtls_mpi_sint b ); 634 635 /** 636 * \brief Modulo: R = A mod B 637 * 638 * \param R Destination MPI for the rest value 639 * \param A Left-hand MPI 640 * \param B Right-hand MPI 641 * 642 * \return 0 if successful, 643 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed, 644 * MBEDTLS_ERR_MPI_DIVISION_BY_ZERO if B == 0, 645 * MBEDTLS_ERR_MPI_NEGATIVE_VALUE if B < 0 646 */ 647 int mbedtls_mpi_mod_mpi( mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B ); 648 649 /** 650 * \brief Modulo: r = A mod b 651 * 652 * \param r Destination mbedtls_mpi_uint 653 * \param A Left-hand MPI 654 * \param b Integer to divide by 655 * 656 * \return 0 if successful, 657 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed, 658 * MBEDTLS_ERR_MPI_DIVISION_BY_ZERO if b == 0, 659 * MBEDTLS_ERR_MPI_NEGATIVE_VALUE if b < 0 660 */ 661 int mbedtls_mpi_mod_int( mbedtls_mpi_uint *r, const mbedtls_mpi *A, mbedtls_mpi_sint b ); 662 663 /** 664 * \brief Sliding-window exponentiation: X = A^E mod N 665 * 666 * \param X Destination MPI 667 * \param A Left-hand MPI 668 * \param E Exponent MPI 669 * \param N Modular MPI 670 * \param _RR Speed-up MPI used for recalculations 671 * 672 * \return 0 if successful, 673 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed, 674 * MBEDTLS_ERR_MPI_BAD_INPUT_DATA if N is negative or even or 675 * if E is negative 676 * 677 * \note _RR is used to avoid re-computing R*R mod N across 678 * multiple calls, which speeds up things a bit. It can 679 * be set to NULL if the extra performance is unneeded. 680 */ 681 int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *E, const mbedtls_mpi *N, mbedtls_mpi *_RR ); 682 683 /** 684 * \brief Fill an MPI X with size bytes of random 685 * 686 * \param X Destination MPI 687 * \param size Size in bytes 688 * \param f_rng RNG function 689 * \param p_rng RNG parameter 690 * 691 * \return 0 if successful, 692 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed 693 * 694 * \note The bytes obtained from the PRNG are interpreted 695 * as a big-endian representation of an MPI; this can 696 * be relevant in applications like deterministic ECDSA. 697 */ 698 int mbedtls_mpi_fill_random( mbedtls_mpi *X, size_t size, 699 int (*f_rng)(void *, unsigned char *, size_t), 700 void *p_rng ); 701 702 /** 703 * \brief Greatest common divisor: G = gcd(A, B) 704 * 705 * \param G Destination MPI 706 * \param A Left-hand MPI 707 * \param B Right-hand MPI 708 * 709 * \return 0 if successful, 710 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed 711 */ 712 int mbedtls_mpi_gcd( mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B ); 713 714 /** 715 * \brief Modular inverse: X = A^-1 mod N 716 * 717 * \param X Destination MPI 718 * \param A Left-hand MPI 719 * \param N Right-hand MPI 720 * 721 * \return 0 if successful, 722 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed, 723 * MBEDTLS_ERR_MPI_BAD_INPUT_DATA if N is <= 1, 724 MBEDTLS_ERR_MPI_NOT_ACCEPTABLE if A has no inverse mod N. 725 */ 726 int mbedtls_mpi_inv_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N ); 727 728 #if !defined(MBEDTLS_DEPRECATED_REMOVED) 729 #if defined(MBEDTLS_DEPRECATED_WARNING) 730 #define MBEDTLS_DEPRECATED __attribute__((deprecated)) 731 #else 732 #define MBEDTLS_DEPRECATED 733 #endif 734 /** 735 * \brief Miller-Rabin primality test with error probability of 736 * 2<sup>-80</sup> 737 * 738 * \deprecated Superseded by mbedtls_mpi_is_prime_ext() which allows 739 * specifying the number of Miller-Rabin rounds. 740 * 741 * \param X MPI to check 742 * \param f_rng RNG function 743 * \param p_rng RNG parameter 744 * 745 * \return 0 if successful (probably prime), 746 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed, 747 * MBEDTLS_ERR_MPI_NOT_ACCEPTABLE if X is not prime 748 */ 749 MBEDTLS_DEPRECATED int mbedtls_mpi_is_prime( const mbedtls_mpi *X, 750 int (*f_rng)(void *, unsigned char *, size_t), 751 void *p_rng ); 752 #undef MBEDTLS_DEPRECATED 753 #endif /* !MBEDTLS_DEPRECATED_REMOVED */ 754 755 /** 756 * \brief Miller-Rabin primality test. 757 * 758 * \warning If \p X is potentially generated by an adversary, for example 759 * when validating cryptographic parameters that you didn't 760 * generate yourself and that are supposed to be prime, then 761 * \p rounds should be at least the half of the security 762 * strength of the cryptographic algorithm. On the other hand, 763 * if \p X is chosen uniformly or non-adversially (as is the 764 * case when mbedtls_mpi_gen_prime calls this function), then 765 * \p rounds can be much lower. 766 * 767 * \param X MPI to check 768 * \param rounds Number of bases to perform Miller-Rabin primality test for. 769 * The probability of returning 0 on a composite is at most 770 * 2<sup>-2*\p rounds</sup>. 771 * \param f_rng RNG function 772 * \param p_rng RNG parameter 773 * 774 * \return 0 if successful (probably prime), 775 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed, 776 * MBEDTLS_ERR_MPI_NOT_ACCEPTABLE if X is not prime 777 */ 778 int mbedtls_mpi_is_prime_ext( const mbedtls_mpi *X, int rounds, 779 int (*f_rng)(void *, unsigned char *, size_t), 780 void *p_rng ); 781 /** 782 * \brief Flags for mbedtls_mpi_gen_prime() 783 * 784 * Each of these flags is a constraint on the result X returned by 785 * mbedtls_mpi_gen_prime(). 786 */ 787 typedef enum { 788 MBEDTLS_MPI_GEN_PRIME_FLAG_DH = 0x0001, /**< (X-1)/2 is prime too */ 789 MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR = 0x0002, /**< lower error rate from 2<sup>-80</sup> to 2<sup>-128</sup> */ 790 } mbedtls_mpi_gen_prime_flag_t; 791 792 /** 793 * \brief Prime number generation 794 * 795 * \param X Destination MPI 796 * \param nbits Required size of X in bits 797 * ( 3 <= nbits <= MBEDTLS_MPI_MAX_BITS ) 798 * \param flags Mask of flags of type #mbedtls_mpi_gen_prime_flag_t 799 * \param f_rng RNG function 800 * \param p_rng RNG parameter 801 * 802 * \return 0 if successful (probably prime), 803 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed, 804 * MBEDTLS_ERR_MPI_BAD_INPUT_DATA if nbits is < 3 805 */ 806 int mbedtls_mpi_gen_prime( mbedtls_mpi *X, size_t nbits, int flags, 807 int (*f_rng)(void *, unsigned char *, size_t), 808 void *p_rng ); 809 810 /** 811 * \brief Checkup routine 812 * 813 * \return 0 if successful, or 1 if the test failed 814 */ 815 int mbedtls_mpi_self_test( int verbose ); 816 817 #ifdef __cplusplus 818 } 819 #endif 820 821 #endif /* bignum.h */ 822
