1 /** 2 * \file bignum.h 3 * 4 * \brief Multi-precision integer library 5 */ 6 /* 7 * Copyright The Mbed TLS Contributors 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 #ifndef MBEDTLS_BIGNUM_H 23 #define MBEDTLS_BIGNUM_H 24 #include "mbedtls/private_access.h" 25 26 #include "mbedtls/build_info.h" 27 28 #include <stddef.h> 29 #include <stdint.h> 30 31 #if defined(MBEDTLS_FS_IO) 32 #include <stdio.h> 33 #endif 34 35 /** An error occurred while reading from or writing to a file. */ 36 #define MBEDTLS_ERR_MPI_FILE_IO_ERROR -0x0002 37 /** Bad input parameters to function. */ 38 #define MBEDTLS_ERR_MPI_BAD_INPUT_DATA -0x0004 39 /** There is an invalid character in the digit string. */ 40 #define MBEDTLS_ERR_MPI_INVALID_CHARACTER -0x0006 41 /** The buffer is too small to write to. */ 42 #define MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL -0x0008 43 /** The input arguments are negative or result in illegal output. */ 44 #define MBEDTLS_ERR_MPI_NEGATIVE_VALUE -0x000A 45 /** The input argument for division is zero, which is not allowed. */ 46 #define MBEDTLS_ERR_MPI_DIVISION_BY_ZERO -0x000C 47 /** The input arguments are not acceptable. */ 48 #define MBEDTLS_ERR_MPI_NOT_ACCEPTABLE -0x000E 49 /** Memory allocation failed. */ 50 #define MBEDTLS_ERR_MPI_ALLOC_FAILED -0x0010 51 52 #define MBEDTLS_MPI_CHK(f) \ 53 do \ 54 { \ 55 if( ( ret = (f) ) != 0 ) \ 56 goto cleanup; \ 57 } while( 0 ) 58 59 /* 60 * Maximum size MPIs are allowed to grow to in number of limbs. 61 */ 62 #define MBEDTLS_MPI_MAX_LIMBS 10000 63 64 #if !defined(MBEDTLS_MPI_WINDOW_SIZE) 65 /* 66 * Maximum window size used for modular exponentiation. Default: 6 67 * Minimum value: 1. Maximum value: 6. 68 * 69 * Result is an array of ( 2 ** MBEDTLS_MPI_WINDOW_SIZE ) MPIs used 70 * for the sliding window calculation. (So 64 by default) 71 * 72 * Reduction in size, reduces speed. 73 */ 74 #define MBEDTLS_MPI_WINDOW_SIZE 6 /**< Maximum window size used. */ 75 #endif /* !MBEDTLS_MPI_WINDOW_SIZE */ 76 77 #if !defined(MBEDTLS_MPI_MAX_SIZE) 78 /* 79 * Maximum size of MPIs allowed in bits and bytes for user-MPIs. 80 * ( Default: 512 bytes => 4096 bits, Maximum tested: 2048 bytes => 16384 bits ) 81 * 82 * Note: Calculations can temporarily result in larger MPIs. So the number 83 * of limbs required (MBEDTLS_MPI_MAX_LIMBS) is higher. 84 */ 85 #define MBEDTLS_MPI_MAX_SIZE 1024 /**< Maximum number of bytes for usable MPIs. */ 86 #endif /* !MBEDTLS_MPI_MAX_SIZE */ 87 88 #define MBEDTLS_MPI_MAX_BITS ( 8 * MBEDTLS_MPI_MAX_SIZE ) /**< Maximum number of bits for usable MPIs. */ 89 90 /* 91 * When reading from files with mbedtls_mpi_read_file() and writing to files with 92 * mbedtls_mpi_write_file() the buffer should have space 93 * for a (short) label, the MPI (in the provided radix), the newline 94 * characters and the '\0'. 95 * 96 * By default we assume at least a 10 char label, a minimum radix of 10 97 * (decimal) and a maximum of 4096 bit numbers (1234 decimal chars). 98 * Autosized at compile time for at least a 10 char label, a minimum radix 99 * of 10 (decimal) for a number of MBEDTLS_MPI_MAX_BITS size. 100 * 101 * This used to be statically sized to 1250 for a maximum of 4096 bit 102 * numbers (1234 decimal chars). 103 * 104 * Calculate using the formula: 105 * MBEDTLS_MPI_RW_BUFFER_SIZE = ceil(MBEDTLS_MPI_MAX_BITS / ln(10) * ln(2)) + 106 * LabelSize + 6 107 */ 108 #define MBEDTLS_MPI_MAX_BITS_SCALE100 ( 100 * MBEDTLS_MPI_MAX_BITS ) 109 #define MBEDTLS_LN_2_DIV_LN_10_SCALE100 332 110 #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 ) 111 112 /* 113 * Define the base integer type, architecture-wise. 114 * 115 * 32 or 64-bit integer types can be forced regardless of the underlying 116 * architecture by defining MBEDTLS_HAVE_INT32 or MBEDTLS_HAVE_INT64 117 * respectively and undefining MBEDTLS_HAVE_ASM. 118 * 119 * Double-width integers (e.g. 128-bit in 64-bit architectures) can be 120 * disabled by defining MBEDTLS_NO_UDBL_DIVISION. 121 */ 122 #if !defined(MBEDTLS_HAVE_INT32) 123 #if defined(_MSC_VER) && defined(_M_AMD64) 124 /* Always choose 64-bit when using MSC */ 125 #if !defined(MBEDTLS_HAVE_INT64) 126 #define MBEDTLS_HAVE_INT64 127 #endif /* !MBEDTLS_HAVE_INT64 */ 128 typedef int64_t mbedtls_mpi_sint; 129 typedef uint64_t mbedtls_mpi_uint; 130 #elif defined(__GNUC__) && ( \ 131 defined(__amd64__) || defined(__x86_64__) || \ 132 defined(__ppc64__) || defined(__powerpc64__) || \ 133 defined(__ia64__) || defined(__alpha__) || \ 134 ( defined(__sparc__) && defined(__arch64__) ) || \ 135 defined(__s390x__) || defined(__mips64) || \ 136 defined(__aarch64__) ) 137 #if !defined(MBEDTLS_HAVE_INT64) 138 #define MBEDTLS_HAVE_INT64 139 #endif /* MBEDTLS_HAVE_INT64 */ 140 typedef int64_t mbedtls_mpi_sint; 141 typedef uint64_t mbedtls_mpi_uint; 142 #if !defined(MBEDTLS_NO_UDBL_DIVISION) 143 /* mbedtls_t_udbl defined as 128-bit unsigned int */ 144 typedef unsigned int mbedtls_t_udbl __attribute__((mode(TI))); 145 #define MBEDTLS_HAVE_UDBL 146 #endif /* !MBEDTLS_NO_UDBL_DIVISION */ 147 #elif defined(__ARMCC_VERSION) && defined(__aarch64__) 148 /* 149 * __ARMCC_VERSION is defined for both armcc and armclang and 150 * __aarch64__ is only defined by armclang when compiling 64-bit code 151 */ 152 #if !defined(MBEDTLS_HAVE_INT64) 153 #define MBEDTLS_HAVE_INT64 154 #endif /* !MBEDTLS_HAVE_INT64 */ 155 typedef int64_t mbedtls_mpi_sint; 156 typedef uint64_t mbedtls_mpi_uint; 157 #if !defined(MBEDTLS_NO_UDBL_DIVISION) 158 /* mbedtls_t_udbl defined as 128-bit unsigned int */ 159 typedef __uint128_t mbedtls_t_udbl; 160 #define MBEDTLS_HAVE_UDBL 161 #endif /* !MBEDTLS_NO_UDBL_DIVISION */ 162 #elif defined(MBEDTLS_HAVE_INT64) 163 /* Force 64-bit integers with unknown compiler */ 164 typedef int64_t mbedtls_mpi_sint; 165 typedef uint64_t mbedtls_mpi_uint; 166 #endif 167 #endif /* !MBEDTLS_HAVE_INT32 */ 168 169 #if !defined(MBEDTLS_HAVE_INT64) 170 /* Default to 32-bit compilation */ 171 #if !defined(MBEDTLS_HAVE_INT32) 172 #define MBEDTLS_HAVE_INT32 173 #endif /* !MBEDTLS_HAVE_INT32 */ 174 typedef int32_t mbedtls_mpi_sint; 175 typedef uint32_t mbedtls_mpi_uint; 176 #if !defined(MBEDTLS_NO_UDBL_DIVISION) 177 typedef uint64_t mbedtls_t_udbl; 178 #define MBEDTLS_HAVE_UDBL 179 #endif /* !MBEDTLS_NO_UDBL_DIVISION */ 180 #endif /* !MBEDTLS_HAVE_INT64 */ 181 182 #ifdef __cplusplus 183 extern "C" { 184 #endif 185 186 /** 187 * \brief MPI structure 188 */ 189 typedef struct mbedtls_mpi 190 { 191 int MBEDTLS_PRIVATE(s); /*!< Sign: -1 if the mpi is negative, 1 otherwise */ 192 size_t MBEDTLS_PRIVATE(n); /*!< total # of limbs */ 193 mbedtls_mpi_uint *MBEDTLS_PRIVATE(p); /*!< pointer to limbs */ 194 } 195 mbedtls_mpi; 196 197 /** 198 * \brief Initialize an MPI context. 199 * 200 * This makes the MPI ready to be set or freed, 201 * but does not define a value for the MPI. 202 * 203 * \param X The MPI context to initialize. This must not be \c NULL. 204 */ 205 void mbedtls_mpi_init( mbedtls_mpi *X ); 206 207 /** 208 * \brief This function frees the components of an MPI context. 209 * 210 * \param X The MPI context to be cleared. This may be \c NULL, 211 * in which case this function is a no-op. If it is 212 * not \c NULL, it must point to an initialized MPI. 213 */ 214 void mbedtls_mpi_free( mbedtls_mpi *X ); 215 216 /** 217 * \brief Enlarge an MPI to the specified number of limbs. 218 * 219 * \note This function does nothing if the MPI is 220 * already large enough. 221 * 222 * \param X The MPI to grow. It must be initialized. 223 * \param nblimbs The target number of limbs. 224 * 225 * \return \c 0 if successful. 226 * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed. 227 * \return Another negative error code on other kinds of failure. 228 */ 229 int mbedtls_mpi_grow( mbedtls_mpi *X, size_t nblimbs ); 230 231 /** 232 * \brief This function resizes an MPI downwards, keeping at least the 233 * specified number of limbs. 234 * 235 * If \c X is smaller than \c nblimbs, it is resized up 236 * instead. 237 * 238 * \param X The MPI to shrink. This must point to an initialized MPI. 239 * \param nblimbs The minimum number of limbs to keep. 240 * 241 * \return \c 0 if successful. 242 * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed 243 * (this can only happen when resizing up). 244 * \return Another negative error code on other kinds of failure. 245 */ 246 int mbedtls_mpi_shrink( mbedtls_mpi *X, size_t nblimbs ); 247 248 /** 249 * \brief Make a copy of an MPI. 250 * 251 * \param X The destination MPI. This must point to an initialized MPI. 252 * \param Y The source MPI. This must point to an initialized MPI. 253 * 254 * \note The limb-buffer in the destination MPI is enlarged 255 * if necessary to hold the value in the source MPI. 256 * 257 * \return \c 0 if successful. 258 * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed. 259 * \return Another negative error code on other kinds of failure. 260 */ 261 int mbedtls_mpi_copy( mbedtls_mpi *X, const mbedtls_mpi *Y ); 262 263 /** 264 * \brief Swap the contents of two MPIs. 265 * 266 * \param X The first MPI. It must be initialized. 267 * \param Y The second MPI. It must be initialized. 268 */ 269 void mbedtls_mpi_swap( mbedtls_mpi *X, mbedtls_mpi *Y ); 270 271 /** 272 * \brief Perform a safe conditional copy of MPI which doesn't 273 * reveal whether the condition was true or not. 274 * 275 * \param X The MPI to conditionally assign to. This must point 276 * to an initialized MPI. 277 * \param Y The MPI to be assigned from. This must point to an 278 * initialized MPI. 279 * \param assign The condition deciding whether to perform the 280 * assignment or not. Possible values: 281 * * \c 1: Perform the assignment `X = Y`. 282 * * \c 0: Keep the original value of \p X. 283 * 284 * \note This function is equivalent to 285 * `if( assign ) mbedtls_mpi_copy( X, Y );` 286 * except that it avoids leaking any information about whether 287 * the assignment was done or not (the above code may leak 288 * information through branch prediction and/or memory access 289 * patterns analysis). 290 * 291 * \return \c 0 if successful. 292 * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed. 293 * \return Another negative error code on other kinds of failure. 294 */ 295 int mbedtls_mpi_safe_cond_assign( mbedtls_mpi *X, const mbedtls_mpi *Y, unsigned char assign ); 296 297 /** 298 * \brief Perform a safe conditional swap which doesn't 299 * reveal whether the condition was true or not. 300 * 301 * \param X The first MPI. This must be initialized. 302 * \param Y The second MPI. This must be initialized. 303 * \param assign The condition deciding whether to perform 304 * the swap or not. Possible values: 305 * * \c 1: Swap the values of \p X and \p Y. 306 * * \c 0: Keep the original values of \p X and \p Y. 307 * 308 * \note This function is equivalent to 309 * if( assign ) mbedtls_mpi_swap( X, Y ); 310 * except that it avoids leaking any information about whether 311 * the assignment was done or not (the above code may leak 312 * information through branch prediction and/or memory access 313 * patterns analysis). 314 * 315 * \return \c 0 if successful. 316 * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed. 317 * \return Another negative error code on other kinds of failure. 318 * 319 */ 320 int mbedtls_mpi_safe_cond_swap( mbedtls_mpi *X, mbedtls_mpi *Y, unsigned char assign ); 321 322 /** 323 * \brief Store integer value in MPI. 324 * 325 * \param X The MPI to set. This must be initialized. 326 * \param z The value to use. 327 * 328 * \return \c 0 if successful. 329 * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed. 330 * \return Another negative error code on other kinds of failure. 331 */ 332 int mbedtls_mpi_lset( mbedtls_mpi *X, mbedtls_mpi_sint z ); 333 334 /** 335 * \brief Get a specific bit from an MPI. 336 * 337 * \param X The MPI to query. This must be initialized. 338 * \param pos Zero-based index of the bit to query. 339 * 340 * \return \c 0 or \c 1 on success, depending on whether bit \c pos 341 * of \c X is unset or set. 342 * \return A negative error code on failure. 343 */ 344 int mbedtls_mpi_get_bit( const mbedtls_mpi *X, size_t pos ); 345 346 /** 347 * \brief Modify a specific bit in an MPI. 348 * 349 * \note This function will grow the target MPI if necessary to set a 350 * bit to \c 1 in a not yet existing limb. It will not grow if 351 * the bit should be set to \c 0. 352 * 353 * \param X The MPI to modify. This must be initialized. 354 * \param pos Zero-based index of the bit to modify. 355 * \param val The desired value of bit \c pos: \c 0 or \c 1. 356 * 357 * \return \c 0 if successful. 358 * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed. 359 * \return Another negative error code on other kinds of failure. 360 */ 361 int mbedtls_mpi_set_bit( mbedtls_mpi *X, size_t pos, unsigned char val ); 362 363 /** 364 * \brief Return the number of bits of value \c 0 before the 365 * least significant bit of value \c 1. 366 * 367 * \note This is the same as the zero-based index of 368 * the least significant bit of value \c 1. 369 * 370 * \param X The MPI to query. 371 * 372 * \return The number of bits of value \c 0 before the least significant 373 * bit of value \c 1 in \p X. 374 */ 375 size_t mbedtls_mpi_lsb( const mbedtls_mpi *X ); 376 377 /** 378 * \brief Return the number of bits up to and including the most 379 * significant bit of value \c 1. 380 * 381 * * \note This is same as the one-based index of the most 382 * significant bit of value \c 1. 383 * 384 * \param X The MPI to query. This must point to an initialized MPI. 385 * 386 * \return The number of bits up to and including the most 387 * significant bit of value \c 1. 388 */ 389 size_t mbedtls_mpi_bitlen( const mbedtls_mpi *X ); 390 391 /** 392 * \brief Return the total size of an MPI value in bytes. 393 * 394 * \param X The MPI to use. This must point to an initialized MPI. 395 * 396 * \note The value returned by this function may be less than 397 * the number of bytes used to store \p X internally. 398 * This happens if and only if there are trailing bytes 399 * of value zero. 400 * 401 * \return The least number of bytes capable of storing 402 * the absolute value of \p X. 403 */ 404 size_t mbedtls_mpi_size( const mbedtls_mpi *X ); 405 406 /** 407 * \brief Import an MPI from an ASCII string. 408 * 409 * \param X The destination MPI. This must point to an initialized MPI. 410 * \param radix The numeric base of the input string. 411 * \param s Null-terminated string buffer. 412 * 413 * \return \c 0 if successful. 414 * \return A negative error code on failure. 415 */ 416 int mbedtls_mpi_read_string( mbedtls_mpi *X, int radix, const char *s ); 417 418 /** 419 * \brief Export an MPI to an ASCII string. 420 * 421 * \param X The source MPI. This must point to an initialized MPI. 422 * \param radix The numeric base of the output string. 423 * \param buf The buffer to write the string to. This must be writable 424 * buffer of length \p buflen Bytes. 425 * \param buflen The available size in Bytes of \p buf. 426 * \param olen The address at which to store the length of the string 427 * written, including the final \c NULL byte. This must 428 * not be \c NULL. 429 * 430 * \note You can call this function with `buflen == 0` to obtain the 431 * minimum required buffer size in `*olen`. 432 * 433 * \return \c 0 if successful. 434 * \return #MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if the target buffer \p buf 435 * is too small to hold the value of \p X in the desired base. 436 * In this case, `*olen` is nonetheless updated to contain the 437 * size of \p buf required for a successful call. 438 * \return Another negative error code on different kinds of failure. 439 */ 440 int mbedtls_mpi_write_string( const mbedtls_mpi *X, int radix, 441 char *buf, size_t buflen, size_t *olen ); 442 443 #if defined(MBEDTLS_FS_IO) 444 /** 445 * \brief Read an MPI from a line in an opened file. 446 * 447 * \param X The destination MPI. This must point to an initialized MPI. 448 * \param radix The numeric base of the string representation used 449 * in the source line. 450 * \param fin The input file handle to use. This must not be \c NULL. 451 * 452 * \note On success, this function advances the file stream 453 * to the end of the current line or to EOF. 454 * 455 * The function returns \c 0 on an empty line. 456 * 457 * Leading whitespaces are ignored, as is a 458 * '0x' prefix for radix \c 16. 459 * 460 * \return \c 0 if successful. 461 * \return #MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if the file read buffer 462 * is too small. 463 * \return Another negative error code on failure. 464 */ 465 int mbedtls_mpi_read_file( mbedtls_mpi *X, int radix, FILE *fin ); 466 467 /** 468 * \brief Export an MPI into an opened file. 469 * 470 * \param p A string prefix to emit prior to the MPI data. 471 * For example, this might be a label, or "0x" when 472 * printing in base \c 16. This may be \c NULL if no prefix 473 * is needed. 474 * \param X The source MPI. This must point to an initialized MPI. 475 * \param radix The numeric base to be used in the emitted string. 476 * \param fout The output file handle. This may be \c NULL, in which case 477 * the output is written to \c stdout. 478 * 479 * \return \c 0 if successful. 480 * \return A negative error code on failure. 481 */ 482 int mbedtls_mpi_write_file( const char *p, const mbedtls_mpi *X, 483 int radix, FILE *fout ); 484 #endif /* MBEDTLS_FS_IO */ 485 486 /** 487 * \brief Import an MPI from unsigned big endian binary data. 488 * 489 * \param X The destination MPI. This must point to an initialized MPI. 490 * \param buf The input buffer. This must be a readable buffer of length 491 * \p buflen Bytes. 492 * \param buflen The length of the input buffer \p p in Bytes. 493 * 494 * \return \c 0 if successful. 495 * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed. 496 * \return Another negative error code on different kinds of failure. 497 */ 498 int mbedtls_mpi_read_binary( mbedtls_mpi *X, const unsigned char *buf, 499 size_t buflen ); 500 501 /** 502 * \brief Import X from unsigned binary data, little endian 503 * 504 * \param X The destination MPI. This must point to an initialized MPI. 505 * \param buf The input buffer. This must be a readable buffer of length 506 * \p buflen Bytes. 507 * \param buflen The length of the input buffer \p p in Bytes. 508 * 509 * \return \c 0 if successful. 510 * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed. 511 * \return Another negative error code on different kinds of failure. 512 */ 513 int mbedtls_mpi_read_binary_le( mbedtls_mpi *X, 514 const unsigned char *buf, size_t buflen ); 515 516 /** 517 * \brief Export X into unsigned binary data, big endian. 518 * Always fills the whole buffer, which will start with zeros 519 * if the number is smaller. 520 * 521 * \param X The source MPI. This must point to an initialized MPI. 522 * \param buf The output buffer. This must be a writable buffer of length 523 * \p buflen Bytes. 524 * \param buflen The size of the output buffer \p buf in Bytes. 525 * 526 * \return \c 0 if successful. 527 * \return #MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if \p buf isn't 528 * large enough to hold the value of \p X. 529 * \return Another negative error code on different kinds of failure. 530 */ 531 int mbedtls_mpi_write_binary( const mbedtls_mpi *X, unsigned char *buf, 532 size_t buflen ); 533 534 /** 535 * \brief Export X into unsigned binary data, little endian. 536 * Always fills the whole buffer, which will end with zeros 537 * if the number is smaller. 538 * 539 * \param X The source MPI. This must point to an initialized MPI. 540 * \param buf The output buffer. This must be a writable buffer of length 541 * \p buflen Bytes. 542 * \param buflen The size of the output buffer \p buf in Bytes. 543 * 544 * \return \c 0 if successful. 545 * \return #MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if \p buf isn't 546 * large enough to hold the value of \p X. 547 * \return Another negative error code on different kinds of failure. 548 */ 549 int mbedtls_mpi_write_binary_le( const mbedtls_mpi *X, 550 unsigned char *buf, size_t buflen ); 551 552 /** 553 * \brief Perform a left-shift on an MPI: X <<= count 554 * 555 * \param X The MPI to shift. This must point to an initialized MPI. 556 * \param count The number of bits to shift by. 557 * 558 * \return \c 0 if successful. 559 * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED if a memory allocation failed. 560 * \return Another negative error code on different kinds of failure. 561 */ 562 int mbedtls_mpi_shift_l( mbedtls_mpi *X, size_t count ); 563 564 /** 565 * \brief Perform a right-shift on an MPI: X >>= count 566 * 567 * \param X The MPI to shift. This must point to an initialized MPI. 568 * \param count The number of bits to shift by. 569 * 570 * \return \c 0 if successful. 571 * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED if a memory allocation failed. 572 * \return Another negative error code on different kinds of failure. 573 */ 574 int mbedtls_mpi_shift_r( mbedtls_mpi *X, size_t count ); 575 576 /** 577 * \brief Compare the absolute values of two MPIs. 578 * 579 * \param X The left-hand MPI. This must point to an initialized MPI. 580 * \param Y The right-hand MPI. This must point to an initialized MPI. 581 * 582 * \return \c 1 if `|X|` is greater than `|Y|`. 583 * \return \c -1 if `|X|` is lesser than `|Y|`. 584 * \return \c 0 if `|X|` is equal to `|Y|`. 585 */ 586 int mbedtls_mpi_cmp_abs( const mbedtls_mpi *X, const mbedtls_mpi *Y ); 587 588 /** 589 * \brief Compare two MPIs. 590 * 591 * \param X The left-hand MPI. This must point to an initialized MPI. 592 * \param Y The right-hand MPI. This must point to an initialized MPI. 593 * 594 * \return \c 1 if \p X is greater than \p Y. 595 * \return \c -1 if \p X is lesser than \p Y. 596 * \return \c 0 if \p X is equal to \p Y. 597 */ 598 int mbedtls_mpi_cmp_mpi( const mbedtls_mpi *X, const mbedtls_mpi *Y ); 599 600 /** 601 * \brief Check if an MPI is less than the other in constant time. 602 * 603 * \param X The left-hand MPI. This must point to an initialized MPI 604 * with the same allocated length as Y. 605 * \param Y The right-hand MPI. This must point to an initialized MPI 606 * with the same allocated length as X. 607 * \param ret The result of the comparison: 608 * \c 1 if \p X is less than \p Y. 609 * \c 0 if \p X is greater than or equal to \p Y. 610 * 611 * \return 0 on success. 612 * \return MBEDTLS_ERR_MPI_BAD_INPUT_DATA if the allocated length of 613 * the two input MPIs is not the same. 614 */ 615 int mbedtls_mpi_lt_mpi_ct( const mbedtls_mpi *X, const mbedtls_mpi *Y, 616 unsigned *ret ); 617 618 /** 619 * \brief Compare an MPI with an integer. 620 * 621 * \param X The left-hand MPI. This must point to an initialized MPI. 622 * \param z The integer value to compare \p X to. 623 * 624 * \return \c 1 if \p X is greater than \p z. 625 * \return \c -1 if \p X is lesser than \p z. 626 * \return \c 0 if \p X is equal to \p z. 627 */ 628 int mbedtls_mpi_cmp_int( const mbedtls_mpi *X, mbedtls_mpi_sint z ); 629 630 /** 631 * \brief Perform an unsigned addition of MPIs: X = |A| + |B| 632 * 633 * \param X The destination MPI. This must point to an initialized MPI. 634 * \param A The first summand. This must point to an initialized MPI. 635 * \param B The second summand. This must point to an initialized MPI. 636 * 637 * \return \c 0 if successful. 638 * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED if a memory allocation failed. 639 * \return Another negative error code on different kinds of failure. 640 */ 641 int mbedtls_mpi_add_abs( mbedtls_mpi *X, const mbedtls_mpi *A, 642 const mbedtls_mpi *B ); 643 644 /** 645 * \brief Perform an unsigned subtraction of MPIs: X = |A| - |B| 646 * 647 * \param X The destination MPI. This must point to an initialized MPI. 648 * \param A The minuend. This must point to an initialized MPI. 649 * \param B The subtrahend. This must point to an initialized MPI. 650 * 651 * \return \c 0 if successful. 652 * \return #MBEDTLS_ERR_MPI_NEGATIVE_VALUE if \p B is greater than \p A. 653 * \return Another negative error code on different kinds of failure. 654 * 655 */ 656 int mbedtls_mpi_sub_abs( mbedtls_mpi *X, const mbedtls_mpi *A, 657 const mbedtls_mpi *B ); 658 659 /** 660 * \brief Perform a signed addition of MPIs: X = A + B 661 * 662 * \param X The destination MPI. This must point to an initialized MPI. 663 * \param A The first summand. This must point to an initialized MPI. 664 * \param B The second summand. This must point to an initialized MPI. 665 * 666 * \return \c 0 if successful. 667 * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED if a memory allocation failed. 668 * \return Another negative error code on different kinds of failure. 669 */ 670 int mbedtls_mpi_add_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, 671 const mbedtls_mpi *B ); 672 673 /** 674 * \brief Perform a signed subtraction of MPIs: X = A - B 675 * 676 * \param X The destination MPI. This must point to an initialized MPI. 677 * \param A The minuend. This must point to an initialized MPI. 678 * \param B The subtrahend. This must point to an initialized MPI. 679 * 680 * \return \c 0 if successful. 681 * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED if a memory allocation failed. 682 * \return Another negative error code on different kinds of failure. 683 */ 684 int mbedtls_mpi_sub_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, 685 const mbedtls_mpi *B ); 686 687 /** 688 * \brief Perform a signed addition of an MPI and an integer: X = A + b 689 * 690 * \param X The destination MPI. This must point to an initialized MPI. 691 * \param A The first summand. This must point to an initialized MPI. 692 * \param b The second summand. 693 * 694 * \return \c 0 if successful. 695 * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED if a memory allocation failed. 696 * \return Another negative error code on different kinds of failure. 697 */ 698 int mbedtls_mpi_add_int( mbedtls_mpi *X, const mbedtls_mpi *A, 699 mbedtls_mpi_sint b ); 700 701 /** 702 * \brief Perform a signed subtraction of an MPI and an integer: 703 * X = A - b 704 * 705 * \param X The destination MPI. This must point to an initialized MPI. 706 * \param A The minuend. This must point to an initialized MPI. 707 * \param b The subtrahend. 708 * 709 * \return \c 0 if successful. 710 * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED if a memory allocation failed. 711 * \return Another negative error code on different kinds of failure. 712 */ 713 int mbedtls_mpi_sub_int( mbedtls_mpi *X, const mbedtls_mpi *A, 714 mbedtls_mpi_sint b ); 715 716 /** 717 * \brief Perform a multiplication of two MPIs: X = A * B 718 * 719 * \param X The destination MPI. This must point to an initialized MPI. 720 * \param A The first factor. This must point to an initialized MPI. 721 * \param B The second factor. This must point to an initialized MPI. 722 * 723 * \return \c 0 if successful. 724 * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED if a memory allocation failed. 725 * \return Another negative error code on different kinds of failure. 726 * 727 */ 728 int mbedtls_mpi_mul_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, 729 const mbedtls_mpi *B ); 730 731 /** 732 * \brief Perform a multiplication of an MPI with an unsigned integer: 733 * X = A * b 734 * 735 * \param X The destination MPI. This must point to an initialized MPI. 736 * \param A The first factor. This must point to an initialized MPI. 737 * \param b The second factor. 738 * 739 * \return \c 0 if successful. 740 * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED if a memory allocation failed. 741 * \return Another negative error code on different kinds of failure. 742 * 743 */ 744 int mbedtls_mpi_mul_int( mbedtls_mpi *X, const mbedtls_mpi *A, 745 mbedtls_mpi_uint b ); 746 747 /** 748 * \brief Perform a division with remainder of two MPIs: 749 * A = Q * B + R 750 * 751 * \param Q The destination MPI for the quotient. 752 * This may be \c NULL if the value of the 753 * quotient is not needed. 754 * \param R The destination MPI for the remainder value. 755 * This may be \c NULL if the value of the 756 * remainder is not needed. 757 * \param A The dividend. This must point to an initialized MPi. 758 * \param B The divisor. This must point to an initialized MPI. 759 * 760 * \return \c 0 if successful. 761 * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed. 762 * \return #MBEDTLS_ERR_MPI_DIVISION_BY_ZERO if \p B equals zero. 763 * \return Another negative error code on different kinds of failure. 764 */ 765 int mbedtls_mpi_div_mpi( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A, 766 const mbedtls_mpi *B ); 767 768 /** 769 * \brief Perform a division with remainder of an MPI by an integer: 770 * A = Q * b + R 771 * 772 * \param Q The destination MPI for the quotient. 773 * This may be \c NULL if the value of the 774 * quotient is not needed. 775 * \param R The destination MPI for the remainder value. 776 * This may be \c NULL if the value of the 777 * remainder is not needed. 778 * \param A The dividend. This must point to an initialized MPi. 779 * \param b The divisor. 780 * 781 * \return \c 0 if successful. 782 * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED if memory allocation failed. 783 * \return #MBEDTLS_ERR_MPI_DIVISION_BY_ZERO if \p b equals zero. 784 * \return Another negative error code on different kinds of failure. 785 */ 786 int mbedtls_mpi_div_int( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A, 787 mbedtls_mpi_sint b ); 788 789 /** 790 * \brief Perform a modular reduction. R = A mod B 791 * 792 * \param R The destination MPI for the residue value. 793 * This must point to an initialized MPI. 794 * \param A The MPI to compute the residue of. 795 * This must point to an initialized MPI. 796 * \param B The base of the modular reduction. 797 * This must point to an initialized MPI. 798 * 799 * \return \c 0 if successful. 800 * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED if a memory allocation failed. 801 * \return #MBEDTLS_ERR_MPI_DIVISION_BY_ZERO if \p B equals zero. 802 * \return #MBEDTLS_ERR_MPI_NEGATIVE_VALUE if \p B is negative. 803 * \return Another negative error code on different kinds of failure. 804 * 805 */ 806 int mbedtls_mpi_mod_mpi( mbedtls_mpi *R, const mbedtls_mpi *A, 807 const mbedtls_mpi *B ); 808 809 /** 810 * \brief Perform a modular reduction with respect to an integer. 811 * r = A mod b 812 * 813 * \param r The address at which to store the residue. 814 * This must not be \c NULL. 815 * \param A The MPI to compute the residue of. 816 * This must point to an initialized MPi. 817 * \param b The integer base of the modular reduction. 818 * 819 * \return \c 0 if successful. 820 * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED if a memory allocation failed. 821 * \return #MBEDTLS_ERR_MPI_DIVISION_BY_ZERO if \p b equals zero. 822 * \return #MBEDTLS_ERR_MPI_NEGATIVE_VALUE if \p b is negative. 823 * \return Another negative error code on different kinds of failure. 824 */ 825 int mbedtls_mpi_mod_int( mbedtls_mpi_uint *r, const mbedtls_mpi *A, 826 mbedtls_mpi_sint b ); 827 828 /** 829 * \brief Perform a sliding-window exponentiation: X = A^E mod N 830 * 831 * \param X The destination MPI. This must point to an initialized MPI. 832 * \param A The base of the exponentiation. 833 * This must point to an initialized MPI. 834 * \param E The exponent MPI. This must point to an initialized MPI. 835 * \param N The base for the modular reduction. This must point to an 836 * initialized MPI. 837 * \param prec_RR A helper MPI depending solely on \p N which can be used to 838 * speed-up multiple modular exponentiations for the same value 839 * of \p N. This may be \c NULL. If it is not \c NULL, it must 840 * point to an initialized MPI. If it hasn't been used after 841 * the call to mbedtls_mpi_init(), this function will compute 842 * the helper value and store it in \p prec_RR for reuse on 843 * subsequent calls to this function. Otherwise, the function 844 * will assume that \p prec_RR holds the helper value set by a 845 * previous call to mbedtls_mpi_exp_mod(), and reuse it. 846 * 847 * \return \c 0 if successful. 848 * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED if a memory allocation failed. 849 * \return #MBEDTLS_ERR_MPI_BAD_INPUT_DATA if \c N is negative or 850 * even, or if \c E is negative. 851 * \return Another negative error code on different kinds of failures. 852 * 853 */ 854 int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A, 855 const mbedtls_mpi *E, const mbedtls_mpi *N, 856 mbedtls_mpi *prec_RR ); 857 858 /** 859 * \brief Fill an MPI with a number of random bytes. 860 * 861 * \param X The destination MPI. This must point to an initialized MPI. 862 * \param size The number of random bytes to generate. 863 * \param f_rng The RNG function to use. This must not be \c NULL. 864 * \param p_rng The RNG parameter to be passed to \p f_rng. This may be 865 * \c NULL if \p f_rng doesn't need a context argument. 866 * 867 * \return \c 0 if successful. 868 * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED if a memory allocation failed. 869 * \return Another negative error code on failure. 870 * 871 * \note The bytes obtained from the RNG are interpreted 872 * as a big-endian representation of an MPI; this can 873 * be relevant in applications like deterministic ECDSA. 874 */ 875 int mbedtls_mpi_fill_random( mbedtls_mpi *X, size_t size, 876 int (*f_rng)(void *, unsigned char *, size_t), 877 void *p_rng ); 878 879 /** Generate a random number uniformly in a range. 880 * 881 * This function generates a random number between \p min inclusive and 882 * \p N exclusive. 883 * 884 * The procedure complies with RFC 6979 §3.3 (deterministic ECDSA) 885 * when the RNG is a suitably parametrized instance of HMAC_DRBG 886 * and \p min is \c 1. 887 * 888 * \note There are `N - min` possible outputs. The lower bound 889 * \p min can be reached, but the upper bound \p N cannot. 890 * 891 * \param X The destination MPI. This must point to an initialized MPI. 892 * \param min The minimum value to return. 893 * It must be nonnegative. 894 * \param N The upper bound of the range, exclusive. 895 * In other words, this is one plus the maximum value to return. 896 * \p N must be strictly larger than \p min. 897 * \param f_rng The RNG function to use. This must not be \c NULL. 898 * \param p_rng The RNG parameter to be passed to \p f_rng. 899 * 900 * \return \c 0 if successful. 901 * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED if a memory allocation failed. 902 * \return #MBEDTLS_ERR_MPI_BAD_INPUT_DATA if \p min or \p N is invalid 903 * or if they are incompatible. 904 * \return #MBEDTLS_ERR_MPI_NOT_ACCEPTABLE if the implementation was 905 * unable to find a suitable value within a limited number 906 * of attempts. This has a negligible probability if \p N 907 * is significantly larger than \p min, which is the case 908 * for all usual cryptographic applications. 909 * \return Another negative error code on failure. 910 */ 911 int mbedtls_mpi_random( mbedtls_mpi *X, 912 mbedtls_mpi_sint min, 913 const mbedtls_mpi *N, 914 int (*f_rng)(void *, unsigned char *, size_t), 915 void *p_rng ); 916 917 /** 918 * \brief Compute the greatest common divisor: G = gcd(A, B) 919 * 920 * \param G The destination MPI. This must point to an initialized MPI. 921 * \param A The first operand. This must point to an initialized MPI. 922 * \param B The second operand. This must point to an initialized MPI. 923 * 924 * \return \c 0 if successful. 925 * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED if a memory allocation failed. 926 * \return Another negative error code on different kinds of failure. 927 */ 928 int mbedtls_mpi_gcd( mbedtls_mpi *G, const mbedtls_mpi *A, 929 const mbedtls_mpi *B ); 930 931 /** 932 * \brief Compute the modular inverse: X = A^-1 mod N 933 * 934 * \param X The destination MPI. This must point to an initialized MPI. 935 * \param A The MPI to calculate the modular inverse of. This must point 936 * to an initialized MPI. 937 * \param N The base of the modular inversion. This must point to an 938 * initialized MPI. 939 * 940 * \return \c 0 if successful. 941 * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED if a memory allocation failed. 942 * \return #MBEDTLS_ERR_MPI_BAD_INPUT_DATA if \p N is less than 943 * or equal to one. 944 * \return #MBEDTLS_ERR_MPI_NOT_ACCEPTABLE if \p has no modular inverse 945 * with respect to \p N. 946 */ 947 int mbedtls_mpi_inv_mod( mbedtls_mpi *X, const mbedtls_mpi *A, 948 const mbedtls_mpi *N ); 949 950 /** 951 * \brief Miller-Rabin primality test. 952 * 953 * \warning If \p X is potentially generated by an adversary, for example 954 * when validating cryptographic parameters that you didn't 955 * generate yourself and that are supposed to be prime, then 956 * \p rounds should be at least the half of the security 957 * strength of the cryptographic algorithm. On the other hand, 958 * if \p X is chosen uniformly or non-adversially (as is the 959 * case when mbedtls_mpi_gen_prime calls this function), then 960 * \p rounds can be much lower. 961 * 962 * \param X The MPI to check for primality. 963 * This must point to an initialized MPI. 964 * \param rounds The number of bases to perform the Miller-Rabin primality 965 * test for. The probability of returning 0 on a composite is 966 * at most 2<sup>-2*\p rounds</sup>. 967 * \param f_rng The RNG function to use. This must not be \c NULL. 968 * \param p_rng The RNG parameter to be passed to \p f_rng. 969 * This may be \c NULL if \p f_rng doesn't use 970 * a context parameter. 971 * 972 * \return \c 0 if successful, i.e. \p X is probably prime. 973 * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED if a memory allocation failed. 974 * \return #MBEDTLS_ERR_MPI_NOT_ACCEPTABLE if \p X is not prime. 975 * \return Another negative error code on other kinds of failure. 976 */ 977 int mbedtls_mpi_is_prime_ext( const mbedtls_mpi *X, int rounds, 978 int (*f_rng)(void *, unsigned char *, size_t), 979 void *p_rng ); 980 /** 981 * \brief Flags for mbedtls_mpi_gen_prime() 982 * 983 * Each of these flags is a constraint on the result X returned by 984 * mbedtls_mpi_gen_prime(). 985 */ 986 typedef enum { 987 MBEDTLS_MPI_GEN_PRIME_FLAG_DH = 0x0001, /**< (X-1)/2 is prime too */ 988 MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR = 0x0002, /**< lower error rate from 2<sup>-80</sup> to 2<sup>-128</sup> */ 989 } mbedtls_mpi_gen_prime_flag_t; 990 991 /** 992 * \brief Generate a prime number. 993 * 994 * \param X The destination MPI to store the generated prime in. 995 * This must point to an initialized MPi. 996 * \param nbits The required size of the destination MPI in bits. 997 * This must be between \c 3 and #MBEDTLS_MPI_MAX_BITS. 998 * \param flags A mask of flags of type #mbedtls_mpi_gen_prime_flag_t. 999 * \param f_rng The RNG function to use. This must not be \c NULL. 1000 * \param p_rng The RNG parameter to be passed to \p f_rng. 1001 * This may be \c NULL if \p f_rng doesn't use 1002 * a context parameter. 1003 * 1004 * \return \c 0 if successful, in which case \p X holds a 1005 * probably prime number. 1006 * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED if a memory allocation failed. 1007 * \return #MBEDTLS_ERR_MPI_BAD_INPUT_DATA if `nbits` is not between 1008 * \c 3 and #MBEDTLS_MPI_MAX_BITS. 1009 */ 1010 int mbedtls_mpi_gen_prime( mbedtls_mpi *X, size_t nbits, int flags, 1011 int (*f_rng)(void *, unsigned char *, size_t), 1012 void *p_rng ); 1013 1014 #if defined(MBEDTLS_SELF_TEST) 1015 1016 /** 1017 * \brief Checkup routine 1018 * 1019 * \return 0 if successful, or 1 if the test failed 1020 */ 1021 int mbedtls_mpi_self_test( int verbose ); 1022 1023 #endif /* MBEDTLS_SELF_TEST */ 1024 1025 #ifdef __cplusplus 1026 } 1027 #endif 1028 1029 #endif /* bignum.h */ 1030