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-bit integers can be forced on 64-bit arches (eg. for testing purposes) 107 * by defining MBEDTLS_HAVE_INT32 and undefining MBEDTLS_HAVE_ASM 108 */ 109 #if ( ! defined(MBEDTLS_HAVE_INT32) && \ 110 defined(_MSC_VER) && defined(_M_AMD64) ) 111 #define MBEDTLS_HAVE_INT64 112 typedef int64_t mbedtls_mpi_sint; 113 typedef uint64_t mbedtls_mpi_uint; 114 #else 115 #if ( ! defined(MBEDTLS_HAVE_INT32) && \ 116 defined(__GNUC__) && ( \ 117 defined(__amd64__) || defined(__x86_64__) || \ 118 defined(__ppc64__) || defined(__powerpc64__) || \ 119 defined(__ia64__) || defined(__alpha__) || \ 120 (defined(__sparc__) && defined(__arch64__)) || \ 121 defined(__s390x__) || defined(__mips64) ) ) 122 #define MBEDTLS_HAVE_INT64 123 typedef int64_t mbedtls_mpi_sint; 124 typedef uint64_t mbedtls_mpi_uint; 125 /* mbedtls_t_udbl defined as 128-bit unsigned int */ 126 typedef unsigned int mbedtls_t_udbl __attribute__((mode(TI))); 127 #define MBEDTLS_HAVE_UDBL 128 #else 129 #define MBEDTLS_HAVE_INT32 130 typedef int32_t mbedtls_mpi_sint; 131 typedef uint32_t mbedtls_mpi_uint; 132 typedef uint64_t mbedtls_t_udbl; 133 #define MBEDTLS_HAVE_UDBL 134 #endif /* !MBEDTLS_HAVE_INT32 && __GNUC__ && 64-bit platform */ 135 #endif /* !MBEDTLS_HAVE_INT32 && _MSC_VER && _M_AMD64 */ 136 137 #ifdef __cplusplus 138 extern "C" { 139 #endif 140 141 /** 142 * \brief MPI structure 143 */ 144 typedef struct 145 { 146 int s; /*!< integer sign */ 147 size_t n; /*!< total # of limbs */ 148 mbedtls_mpi_uint *p; /*!< pointer to limbs */ 149 } 150 mbedtls_mpi; 151 152 /** 153 * \brief Initialize one MPI (make internal references valid) 154 * This just makes it ready to be set or freed, 155 * but does not define a value for the MPI. 156 * 157 * \param X One MPI to initialize. 158 */ 159 void mbedtls_mpi_init( mbedtls_mpi *X ); 160 161 /** 162 * \brief Unallocate one MPI 163 * 164 * \param X One MPI to unallocate. 165 */ 166 void mbedtls_mpi_free( mbedtls_mpi *X ); 167 168 /** 169 * \brief Enlarge to the specified number of limbs 170 * 171 * \param X MPI to grow 172 * \param nblimbs The target number of limbs 173 * 174 * \return 0 if successful, 175 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed 176 */ 177 int mbedtls_mpi_grow( mbedtls_mpi *X, size_t nblimbs ); 178 179 /** 180 * \brief Resize down, keeping at least the specified number of limbs 181 * 182 * \param X MPI to shrink 183 * \param nblimbs The minimum number of limbs to keep 184 * 185 * \return 0 if successful, 186 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed 187 */ 188 int mbedtls_mpi_shrink( mbedtls_mpi *X, size_t nblimbs ); 189 190 /** 191 * \brief Copy the contents of Y into X 192 * 193 * \param X Destination MPI 194 * \param Y Source MPI 195 * 196 * \return 0 if successful, 197 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed 198 */ 199 int mbedtls_mpi_copy( mbedtls_mpi *X, const mbedtls_mpi *Y ); 200 201 /** 202 * \brief Swap the contents of X and Y 203 * 204 * \param X First MPI value 205 * \param Y Second MPI value 206 */ 207 void mbedtls_mpi_swap( mbedtls_mpi *X, mbedtls_mpi *Y ); 208 209 /** 210 * \brief Safe conditional assignement X = Y if assign is 1 211 * 212 * \param X MPI to conditionally assign to 213 * \param Y Value to be assigned 214 * \param assign 1: perform the assignment, 0: keep X's original value 215 * 216 * \return 0 if successful, 217 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed, 218 * 219 * \note This function is equivalent to 220 * if( assign ) mbedtls_mpi_copy( X, Y ); 221 * except that it avoids leaking any information about whether 222 * the assignment was done or not (the above code may leak 223 * information through branch prediction and/or memory access 224 * patterns analysis). 225 */ 226 int mbedtls_mpi_safe_cond_assign( mbedtls_mpi *X, const mbedtls_mpi *Y, unsigned char assign ); 227 228 /** 229 * \brief Safe conditional swap X <-> Y if swap is 1 230 * 231 * \param X First mbedtls_mpi value 232 * \param Y Second mbedtls_mpi value 233 * \param assign 1: perform the swap, 0: keep X and Y's original values 234 * 235 * \return 0 if successful, 236 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed, 237 * 238 * \note This function is equivalent to 239 * if( assign ) mbedtls_mpi_swap( X, Y ); 240 * except that it avoids leaking any information about whether 241 * the assignment was done or not (the above code may leak 242 * information through branch prediction and/or memory access 243 * patterns analysis). 244 */ 245 int mbedtls_mpi_safe_cond_swap( mbedtls_mpi *X, mbedtls_mpi *Y, unsigned char assign ); 246 247 /** 248 * \brief Set value from integer 249 * 250 * \param X MPI to set 251 * \param z Value to use 252 * 253 * \return 0 if successful, 254 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed 255 */ 256 int mbedtls_mpi_lset( mbedtls_mpi *X, mbedtls_mpi_sint z ); 257 258 /** 259 * \brief Get a specific bit from X 260 * 261 * \param X MPI to use 262 * \param pos Zero-based index of the bit in X 263 * 264 * \return Either a 0 or a 1 265 */ 266 int mbedtls_mpi_get_bit( const mbedtls_mpi *X, size_t pos ); 267 268 /** 269 * \brief Set a bit of X to a specific value of 0 or 1 270 * 271 * \note Will grow X if necessary to set a bit to 1 in a not yet 272 * existing limb. Will not grow if bit should be set to 0 273 * 274 * \param X MPI to use 275 * \param pos Zero-based index of the bit in X 276 * \param val The value to set the bit to (0 or 1) 277 * 278 * \return 0 if successful, 279 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed, 280 * MBEDTLS_ERR_MPI_BAD_INPUT_DATA if val is not 0 or 1 281 */ 282 int mbedtls_mpi_set_bit( mbedtls_mpi *X, size_t pos, unsigned char val ); 283 284 /** 285 * \brief Return the number of zero-bits before the least significant 286 * '1' bit 287 * 288 * Note: Thus also the zero-based index of the least significant '1' bit 289 * 290 * \param X MPI to use 291 */ 292 size_t mbedtls_mpi_lsb( const mbedtls_mpi *X ); 293 294 /** 295 * \brief Return the number of bits up to and including the most 296 * significant '1' bit' 297 * 298 * Note: Thus also the one-based index of the most significant '1' bit 299 * 300 * \param X MPI to use 301 */ 302 size_t mbedtls_mpi_bitlen( const mbedtls_mpi *X ); 303 304 /** 305 * \brief Return the total size in bytes 306 * 307 * \param X MPI to use 308 */ 309 size_t mbedtls_mpi_size( const mbedtls_mpi *X ); 310 311 /** 312 * \brief Import from an ASCII string 313 * 314 * \param X Destination MPI 315 * \param radix Input numeric base 316 * \param s Null-terminated string buffer 317 * 318 * \return 0 if successful, or a MBEDTLS_ERR_MPI_XXX error code 319 */ 320 int mbedtls_mpi_read_string( mbedtls_mpi *X, int radix, const char *s ); 321 322 /** 323 * \brief Export into an ASCII string 324 * 325 * \param X Source MPI 326 * \param radix Output numeric base 327 * \param buf Buffer to write the string to 328 * \param buflen Length of buf 329 * \param olen Length of the string written, including final NUL byte 330 * 331 * \return 0 if successful, or a MBEDTLS_ERR_MPI_XXX error code. 332 * *olen is always updated to reflect the amount 333 * of data that has (or would have) been written. 334 * 335 * \note Call this function with buflen = 0 to obtain the 336 * minimum required buffer size in *olen. 337 */ 338 int mbedtls_mpi_write_string( const mbedtls_mpi *X, int radix, 339 char *buf, size_t buflen, size_t *olen ); 340 341 #if defined(MBEDTLS_FS_IO) 342 /** 343 * \brief Read X from an opened file 344 * 345 * \param X Destination MPI 346 * \param radix Input numeric base 347 * \param fin Input file handle 348 * 349 * \return 0 if successful, MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if 350 * the file read buffer is too small or a 351 * MBEDTLS_ERR_MPI_XXX error code 352 */ 353 int mbedtls_mpi_read_file( mbedtls_mpi *X, int radix, FILE *fin ); 354 355 /** 356 * \brief Write X into an opened file, or stdout if fout is NULL 357 * 358 * \param p Prefix, can be NULL 359 * \param X Source MPI 360 * \param radix Output numeric base 361 * \param fout Output file handle (can be NULL) 362 * 363 * \return 0 if successful, or a MBEDTLS_ERR_MPI_XXX error code 364 * 365 * \note Set fout == NULL to print X on the console. 366 */ 367 int mbedtls_mpi_write_file( const char *p, const mbedtls_mpi *X, int radix, FILE *fout ); 368 #endif /* MBEDTLS_FS_IO */ 369 370 /** 371 * \brief Import X from unsigned binary data, big endian 372 * 373 * \param X Destination MPI 374 * \param buf Input buffer 375 * \param buflen Input buffer size 376 * 377 * \return 0 if successful, 378 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed 379 */ 380 int mbedtls_mpi_read_binary( mbedtls_mpi *X, const unsigned char *buf, size_t buflen ); 381 382 /** 383 * \brief Export X into unsigned binary data, big endian. 384 * Always fills the whole buffer, which will start with zeros 385 * if the number is smaller. 386 * 387 * \param X Source MPI 388 * \param buf Output buffer 389 * \param buflen Output buffer size 390 * 391 * \return 0 if successful, 392 * MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if buf isn't large enough 393 */ 394 int mbedtls_mpi_write_binary( const mbedtls_mpi *X, unsigned char *buf, size_t buflen ); 395 396 /** 397 * \brief Left-shift: X <<= count 398 * 399 * \param X MPI to shift 400 * \param count Amount to shift 401 * 402 * \return 0 if successful, 403 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed 404 */ 405 int mbedtls_mpi_shift_l( mbedtls_mpi *X, size_t count ); 406 407 /** 408 * \brief Right-shift: X >>= count 409 * 410 * \param X MPI to shift 411 * \param count Amount to shift 412 * 413 * \return 0 if successful, 414 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed 415 */ 416 int mbedtls_mpi_shift_r( mbedtls_mpi *X, size_t count ); 417 418 /** 419 * \brief Compare unsigned values 420 * 421 * \param X Left-hand MPI 422 * \param Y Right-hand MPI 423 * 424 * \return 1 if |X| is greater than |Y|, 425 * -1 if |X| is lesser than |Y| or 426 * 0 if |X| is equal to |Y| 427 */ 428 int mbedtls_mpi_cmp_abs( const mbedtls_mpi *X, const mbedtls_mpi *Y ); 429 430 /** 431 * \brief Compare signed values 432 * 433 * \param X Left-hand MPI 434 * \param Y Right-hand MPI 435 * 436 * \return 1 if X is greater than Y, 437 * -1 if X is lesser than Y or 438 * 0 if X is equal to Y 439 */ 440 int mbedtls_mpi_cmp_mpi( const mbedtls_mpi *X, const mbedtls_mpi *Y ); 441 442 /** 443 * \brief Compare signed values 444 * 445 * \param X Left-hand MPI 446 * \param z The integer value to compare to 447 * 448 * \return 1 if X is greater than z, 449 * -1 if X is lesser than z or 450 * 0 if X is equal to z 451 */ 452 int mbedtls_mpi_cmp_int( const mbedtls_mpi *X, mbedtls_mpi_sint z ); 453 454 /** 455 * \brief Unsigned addition: X = |A| + |B| 456 * 457 * \param X Destination MPI 458 * \param A Left-hand MPI 459 * \param B Right-hand MPI 460 * 461 * \return 0 if successful, 462 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed 463 */ 464 int mbedtls_mpi_add_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B ); 465 466 /** 467 * \brief Unsigned subtraction: X = |A| - |B| 468 * 469 * \param X Destination MPI 470 * \param A Left-hand MPI 471 * \param B Right-hand MPI 472 * 473 * \return 0 if successful, 474 * MBEDTLS_ERR_MPI_NEGATIVE_VALUE if B is greater than A 475 */ 476 int mbedtls_mpi_sub_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B ); 477 478 /** 479 * \brief Signed addition: X = A + B 480 * 481 * \param X Destination MPI 482 * \param A Left-hand MPI 483 * \param B Right-hand MPI 484 * 485 * \return 0 if successful, 486 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed 487 */ 488 int mbedtls_mpi_add_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B ); 489 490 /** 491 * \brief Signed subtraction: X = A - B 492 * 493 * \param X Destination MPI 494 * \param A Left-hand MPI 495 * \param B Right-hand MPI 496 * 497 * \return 0 if successful, 498 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed 499 */ 500 int mbedtls_mpi_sub_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B ); 501 502 /** 503 * \brief Signed addition: X = A + b 504 * 505 * \param X Destination MPI 506 * \param A Left-hand MPI 507 * \param b The integer value to add 508 * 509 * \return 0 if successful, 510 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed 511 */ 512 int mbedtls_mpi_add_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b ); 513 514 /** 515 * \brief Signed subtraction: X = A - b 516 * 517 * \param X Destination MPI 518 * \param A Left-hand MPI 519 * \param b The integer value to subtract 520 * 521 * \return 0 if successful, 522 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed 523 */ 524 int mbedtls_mpi_sub_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b ); 525 526 /** 527 * \brief Baseline multiplication: X = A * B 528 * 529 * \param X Destination MPI 530 * \param A Left-hand MPI 531 * \param B Right-hand MPI 532 * 533 * \return 0 if successful, 534 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed 535 */ 536 int mbedtls_mpi_mul_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B ); 537 538 /** 539 * \brief Baseline multiplication: X = A * b 540 * 541 * \param X Destination MPI 542 * \param A Left-hand MPI 543 * \param b The unsigned integer value to multiply with 544 * 545 * \note b is unsigned 546 * 547 * \return 0 if successful, 548 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed 549 */ 550 int mbedtls_mpi_mul_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b ); 551 552 /** 553 * \brief Division by mbedtls_mpi: A = Q * B + R 554 * 555 * \param Q Destination MPI for the quotient 556 * \param R Destination MPI for the rest value 557 * \param A Left-hand MPI 558 * \param B Right-hand MPI 559 * 560 * \return 0 if successful, 561 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed, 562 * MBEDTLS_ERR_MPI_DIVISION_BY_ZERO if B == 0 563 * 564 * \note Either Q or R can be NULL. 565 */ 566 int mbedtls_mpi_div_mpi( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B ); 567 568 /** 569 * \brief Division by int: A = Q * b + R 570 * 571 * \param Q Destination MPI for the quotient 572 * \param R Destination MPI for the rest value 573 * \param A Left-hand MPI 574 * \param b Integer to divide by 575 * 576 * \return 0 if successful, 577 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed, 578 * MBEDTLS_ERR_MPI_DIVISION_BY_ZERO if b == 0 579 * 580 * \note Either Q or R can be NULL. 581 */ 582 int mbedtls_mpi_div_int( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A, mbedtls_mpi_sint b ); 583 584 /** 585 * \brief Modulo: R = A mod B 586 * 587 * \param R Destination MPI for the rest value 588 * \param A Left-hand MPI 589 * \param B Right-hand MPI 590 * 591 * \return 0 if successful, 592 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed, 593 * MBEDTLS_ERR_MPI_DIVISION_BY_ZERO if B == 0, 594 * MBEDTLS_ERR_MPI_NEGATIVE_VALUE if B < 0 595 */ 596 int mbedtls_mpi_mod_mpi( mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B ); 597 598 /** 599 * \brief Modulo: r = A mod b 600 * 601 * \param r Destination mbedtls_mpi_uint 602 * \param A Left-hand MPI 603 * \param b Integer to divide by 604 * 605 * \return 0 if successful, 606 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed, 607 * MBEDTLS_ERR_MPI_DIVISION_BY_ZERO if b == 0, 608 * MBEDTLS_ERR_MPI_NEGATIVE_VALUE if b < 0 609 */ 610 int mbedtls_mpi_mod_int( mbedtls_mpi_uint *r, const mbedtls_mpi *A, mbedtls_mpi_sint b ); 611 612 /** 613 * \brief Sliding-window exponentiation: X = A^E mod N 614 * 615 * \param X Destination MPI 616 * \param A Left-hand MPI 617 * \param E Exponent MPI 618 * \param N Modular MPI 619 * \param _RR Speed-up MPI used for recalculations 620 * 621 * \return 0 if successful, 622 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed, 623 * MBEDTLS_ERR_MPI_BAD_INPUT_DATA if N is negative or even or 624 * if E is negative 625 * 626 * \note _RR is used to avoid re-computing R*R mod N across 627 * multiple calls, which speeds up things a bit. It can 628 * be set to NULL if the extra performance is unneeded. 629 */ 630 int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *E, const mbedtls_mpi *N, mbedtls_mpi *_RR ); 631 632 /** 633 * \brief Fill an MPI X with size bytes of random 634 * 635 * \param X Destination MPI 636 * \param size Size in bytes 637 * \param f_rng RNG function 638 * \param p_rng RNG parameter 639 * 640 * \return 0 if successful, 641 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed 642 */ 643 int mbedtls_mpi_fill_random( mbedtls_mpi *X, size_t size, 644 int (*f_rng)(void *, unsigned char *, size_t), 645 void *p_rng ); 646 647 /** 648 * \brief Greatest common divisor: G = gcd(A, B) 649 * 650 * \param G Destination MPI 651 * \param A Left-hand MPI 652 * \param B Right-hand MPI 653 * 654 * \return 0 if successful, 655 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed 656 */ 657 int mbedtls_mpi_gcd( mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B ); 658 659 /** 660 * \brief Modular inverse: X = A^-1 mod N 661 * 662 * \param X Destination MPI 663 * \param A Left-hand MPI 664 * \param N Right-hand MPI 665 * 666 * \return 0 if successful, 667 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed, 668 * MBEDTLS_ERR_MPI_BAD_INPUT_DATA if N is negative or nil 669 MBEDTLS_ERR_MPI_NOT_ACCEPTABLE if A has no inverse mod N 670 */ 671 int mbedtls_mpi_inv_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N ); 672 673 /** 674 * \brief Miller-Rabin primality test 675 * 676 * \param X MPI to check 677 * \param f_rng RNG function 678 * \param p_rng RNG parameter 679 * 680 * \return 0 if successful (probably prime), 681 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed, 682 * MBEDTLS_ERR_MPI_NOT_ACCEPTABLE if X is not prime 683 */ 684 int mbedtls_mpi_is_prime( const mbedtls_mpi *X, 685 int (*f_rng)(void *, unsigned char *, size_t), 686 void *p_rng ); 687 688 /** 689 * \brief Prime number generation 690 * 691 * \param X Destination MPI 692 * \param nbits Required size of X in bits 693 * ( 3 <= nbits <= MBEDTLS_MPI_MAX_BITS ) 694 * \param dh_flag If 1, then (X-1)/2 will be prime too 695 * \param f_rng RNG function 696 * \param p_rng RNG parameter 697 * 698 * \return 0 if successful (probably prime), 699 * MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed, 700 * MBEDTLS_ERR_MPI_BAD_INPUT_DATA if nbits is < 3 701 */ 702 int mbedtls_mpi_gen_prime( mbedtls_mpi *X, size_t nbits, int dh_flag, 703 int (*f_rng)(void *, unsigned char *, size_t), 704 void *p_rng ); 705 706 /** 707 * \brief Checkup routine 708 * 709 * \return 0 if successful, or 1 if the test failed 710 */ 711 int mbedtls_mpi_self_test( int verbose ); 712 713 #ifdef __cplusplus 714 } 715 #endif 716 717 #endif /* bignum.h */ 718
