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