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