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