1/** 2 * Core bignum functions 3 * 4 * This interface should only be used by the legacy bignum module (bignum.h) 5 * and the modular bignum modules (bignum_mod.c, bignum_mod_raw.c). All other 6 * modules should use the high-level modular bignum interface (bignum_mod.h) 7 * or the legacy bignum interface (bignum.h). 8 * 9 * This module is about processing non-negative integers with a fixed upper 10 * bound that's of the form 2^n-1 where n is a multiple of #biL. 11 * These can be thought of integers written in base 2^#biL with a fixed 12 * number of digits. Digits in this base are called *limbs*. 13 * Many operations treat these numbers as the principal representation of 14 * a number modulo 2^n or a smaller bound. 15 * 16 * The functions in this module obey the following conventions unless 17 * explicitly indicated otherwise: 18 * 19 * - **Overflow**: some functions indicate overflow from the range 20 * [0, 2^n-1] by returning carry parameters, while others operate 21 * modulo and so cannot overflow. This should be clear from the function 22 * documentation. 23 * - **Bignum parameters**: Bignums are passed as pointers to an array of 24 * limbs. A limb has the type #mbedtls_mpi_uint. Unless otherwise specified: 25 * - Bignum parameters called \p A, \p B, ... are inputs, and are 26 * not modified by the function. 27 * - For operations modulo some number, the modulus is called \p N 28 * and is input-only. 29 * - Bignum parameters called \p X, \p Y are outputs or input-output. 30 * The initial content of output-only parameters is ignored. 31 * - Some functions use different names that reflect traditional 32 * naming of operands of certain operations (e.g. 33 * divisor/dividend/quotient/remainder). 34 * - \p T is a temporary storage area. The initial content of such 35 * parameter is ignored and the final content is unspecified. 36 * - **Bignum sizes**: bignum sizes are always expressed in limbs. 37 * Most functions work on bignums of a given size and take a single 38 * \p limbs parameter that applies to all parameters that are limb arrays. 39 * All bignum sizes must be at least 1 and must be significantly less than 40 * #SIZE_MAX. The behavior if a size is 0 is undefined. The behavior if the 41 * total size of all parameters overflows #SIZE_MAX is undefined. 42 * - **Parameter ordering**: for bignum parameters, outputs come before inputs. 43 * Temporaries come last. 44 * - **Aliasing**: in general, output bignums may be aliased to one or more 45 * inputs. As an exception, parameters that are documented as a modulus value 46 * may not be aliased to an output. Outputs may not be aliased to one another. 47 * Temporaries may not be aliased to any other parameter. 48 * - **Overlap**: apart from aliasing of limb array pointers (where two 49 * arguments are equal pointers), overlap is not supported and may result 50 * in undefined behavior. 51 * - **Error handling**: This is a low-level module. Functions generally do not 52 * try to protect against invalid arguments such as nonsensical sizes or 53 * null pointers. Note that some functions that operate on bignums of 54 * different sizes have constraints about their size, and violating those 55 * constraints may lead to buffer overflows. 56 * - **Modular representatives**: functions that operate modulo \p N expect 57 * all modular inputs to be in the range [0, \p N - 1] and guarantee outputs 58 * in the range [0, \p N - 1]. If an input is out of range, outputs are 59 * fully unspecified, though bignum values out of range should not cause 60 * buffer overflows (beware that this is not extensively tested). 61 */ 62 63/* 64 * Copyright The Mbed TLS Contributors 65 * SPDX-License-Identifier: Apache-2.0 OR GPL-2.0-or-later 66 */ 67 68#ifndef MBEDTLS_BIGNUM_CORE_H 69#define MBEDTLS_BIGNUM_CORE_H 70 71#include "common.h" 72 73#if defined(MBEDTLS_BIGNUM_C) 74#include "mbedtls/bignum.h" 75#endif 76 77#include "constant_time_internal.h" 78 79#define ciL (sizeof(mbedtls_mpi_uint)) /** chars in limb */ 80#define biL (ciL << 3) /** bits in limb */ 81#define biH (ciL << 2) /** half limb size */ 82 83/* 84 * Convert between bits/chars and number of limbs 85 * Divide first in order to avoid potential overflows 86 */ 87#define BITS_TO_LIMBS(i) ((i) / biL + ((i) % biL != 0)) 88#define CHARS_TO_LIMBS(i) ((i) / ciL + ((i) % ciL != 0)) 89/* Get a specific byte, without range checks. */ 90#define GET_BYTE(X, i) \ 91 (((X)[(i) / ciL] >> (((i) % ciL) * 8)) & 0xff) 92 93/** Count leading zero bits in a given integer. 94 * 95 * \warning The result is undefined if \p a == 0 96 * 97 * \param a Integer to count leading zero bits. 98 * 99 * \return The number of leading zero bits in \p a, if \p a != 0. 100 * If \p a == 0, the result is undefined. 101 */ 102size_t mbedtls_mpi_core_clz(mbedtls_mpi_uint a); 103 104/** Return the minimum number of bits required to represent the value held 105 * in the MPI. 106 * 107 * \note This function returns 0 if all the limbs of \p A are 0. 108 * 109 * \param[in] A The address of the MPI. 110 * \param A_limbs The number of limbs of \p A. 111 * 112 * \return The number of bits in \p A. 113 */ 114size_t mbedtls_mpi_core_bitlen(const mbedtls_mpi_uint *A, size_t A_limbs); 115 116/** Convert a big-endian byte array aligned to the size of mbedtls_mpi_uint 117 * into the storage form used by mbedtls_mpi. 118 * 119 * \param[in,out] A The address of the MPI. 120 * \param A_limbs The number of limbs of \p A. 121 */ 122void mbedtls_mpi_core_bigendian_to_host(mbedtls_mpi_uint *A, 123 size_t A_limbs); 124 125/** \brief Compare a machine integer with an MPI. 126 * 127 * This function operates in constant time with respect 128 * to the values of \p min and \p A. 129 * 130 * \param min A machine integer. 131 * \param[in] A An MPI. 132 * \param A_limbs The number of limbs of \p A. 133 * This must be at least 1. 134 * 135 * \return MBEDTLS_CT_TRUE if \p min is less than or equal to \p A, otherwise MBEDTLS_CT_FALSE. 136 */ 137mbedtls_ct_condition_t mbedtls_mpi_core_uint_le_mpi(mbedtls_mpi_uint min, 138 const mbedtls_mpi_uint *A, 139 size_t A_limbs); 140 141/** 142 * \brief Check if one unsigned MPI is less than another in constant 143 * time. 144 * 145 * \param A The left-hand MPI. This must point to an array of limbs 146 * with the same allocated length as \p B. 147 * \param B The right-hand MPI. This must point to an array of limbs 148 * with the same allocated length as \p A. 149 * \param limbs The number of limbs in \p A and \p B. 150 * This must not be 0. 151 * 152 * \return MBEDTLS_CT_TRUE if \p A is less than \p B. 153 * MBEDTLS_CT_FALSE if \p A is greater than or equal to \p B. 154 */ 155mbedtls_ct_condition_t mbedtls_mpi_core_lt_ct(const mbedtls_mpi_uint *A, 156 const mbedtls_mpi_uint *B, 157 size_t limbs); 158 159/** 160 * \brief Perform a safe conditional copy of an MPI which doesn't reveal 161 * whether assignment was done or not. 162 * 163 * \param[out] X The address of the destination MPI. 164 * This must be initialized. Must have enough limbs to 165 * store the full value of \p A. 166 * \param[in] A The address of the source MPI. This must be initialized. 167 * \param limbs The number of limbs of \p A. 168 * \param assign The condition deciding whether to perform the 169 * assignment or not. Callers will need to use 170 * the constant time interface (e.g. `mbedtls_ct_bool()`) 171 * to construct this argument. 172 * 173 * \note This function avoids leaking any information about whether 174 * the assignment was done or not. 175 */ 176void mbedtls_mpi_core_cond_assign(mbedtls_mpi_uint *X, 177 const mbedtls_mpi_uint *A, 178 size_t limbs, 179 mbedtls_ct_condition_t assign); 180 181/** 182 * \brief Perform a safe conditional swap of two MPIs which doesn't reveal 183 * whether the swap was done or not. 184 * 185 * \param[in,out] X The address of the first MPI. 186 * This must be initialized. 187 * \param[in,out] Y The address of the second MPI. 188 * This must be initialized. 189 * \param limbs The number of limbs of \p X and \p Y. 190 * \param swap The condition deciding whether to perform 191 * the swap or not. 192 * 193 * \note This function avoids leaking any information about whether 194 * the swap was done or not. 195 */ 196void mbedtls_mpi_core_cond_swap(mbedtls_mpi_uint *X, 197 mbedtls_mpi_uint *Y, 198 size_t limbs, 199 mbedtls_ct_condition_t swap); 200 201/** Import X from unsigned binary data, little-endian. 202 * 203 * The MPI needs to have enough limbs to store the full value (including any 204 * most significant zero bytes in the input). 205 * 206 * \param[out] X The address of the MPI. 207 * \param X_limbs The number of limbs of \p X. 208 * \param[in] input The input buffer to import from. 209 * \param input_length The length bytes of \p input. 210 * 211 * \return \c 0 if successful. 212 * \return #MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if \p X isn't 213 * large enough to hold the value in \p input. 214 */ 215int mbedtls_mpi_core_read_le(mbedtls_mpi_uint *X, 216 size_t X_limbs, 217 const unsigned char *input, 218 size_t input_length); 219 220/** Import X from unsigned binary data, big-endian. 221 * 222 * The MPI needs to have enough limbs to store the full value (including any 223 * most significant zero bytes in the input). 224 * 225 * \param[out] X The address of the MPI. 226 * May only be #NULL if \p X_limbs is 0 and \p input_length 227 * is 0. 228 * \param X_limbs The number of limbs of \p X. 229 * \param[in] input The input buffer to import from. 230 * May only be #NULL if \p input_length is 0. 231 * \param input_length The length in bytes of \p input. 232 * 233 * \return \c 0 if successful. 234 * \return #MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if \p X isn't 235 * large enough to hold the value in \p input. 236 */ 237int mbedtls_mpi_core_read_be(mbedtls_mpi_uint *X, 238 size_t X_limbs, 239 const unsigned char *input, 240 size_t input_length); 241 242/** Export A into unsigned binary data, little-endian. 243 * 244 * \note If \p output is shorter than \p A the export is still successful if the 245 * value held in \p A fits in the buffer (that is, if enough of the most 246 * significant bytes of \p A are 0). 247 * 248 * \param[in] A The address of the MPI. 249 * \param A_limbs The number of limbs of \p A. 250 * \param[out] output The output buffer to export to. 251 * \param output_length The length in bytes of \p output. 252 * 253 * \return \c 0 if successful. 254 * \return #MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if \p output isn't 255 * large enough to hold the value of \p A. 256 */ 257int mbedtls_mpi_core_write_le(const mbedtls_mpi_uint *A, 258 size_t A_limbs, 259 unsigned char *output, 260 size_t output_length); 261 262/** Export A into unsigned binary data, big-endian. 263 * 264 * \note If \p output is shorter than \p A the export is still successful if the 265 * value held in \p A fits in the buffer (that is, if enough of the most 266 * significant bytes of \p A are 0). 267 * 268 * \param[in] A The address of the MPI. 269 * \param A_limbs The number of limbs of \p A. 270 * \param[out] output The output buffer to export to. 271 * \param output_length The length in bytes of \p output. 272 * 273 * \return \c 0 if successful. 274 * \return #MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if \p output isn't 275 * large enough to hold the value of \p A. 276 */ 277int mbedtls_mpi_core_write_be(const mbedtls_mpi_uint *A, 278 size_t A_limbs, 279 unsigned char *output, 280 size_t output_length); 281 282/** \brief Shift an MPI in-place right by a number of bits. 283 * 284 * Shifting by more bits than there are bit positions 285 * in \p X is valid and results in setting \p X to 0. 286 * 287 * This function's execution time depends on the value 288 * of \p count (and of course \p limbs). 289 * 290 * \param[in,out] X The number to shift. 291 * \param limbs The number of limbs of \p X. This must be at least 1. 292 * \param count The number of bits to shift by. 293 */ 294void mbedtls_mpi_core_shift_r(mbedtls_mpi_uint *X, size_t limbs, 295 size_t count); 296 297/** 298 * \brief Shift an MPI in-place left by a number of bits. 299 * 300 * Shifting by more bits than there are bit positions 301 * in \p X will produce an unspecified result. 302 * 303 * This function's execution time depends on the value 304 * of \p count (and of course \p limbs). 305 * \param[in,out] X The number to shift. 306 * \param limbs The number of limbs of \p X. This must be at least 1. 307 * \param count The number of bits to shift by. 308 */ 309void mbedtls_mpi_core_shift_l(mbedtls_mpi_uint *X, size_t limbs, 310 size_t count); 311 312/** 313 * \brief Add two fixed-size large unsigned integers, returning the carry. 314 * 315 * Calculates `A + B` where `A` and `B` have the same size. 316 * 317 * This function operates modulo `2^(biL*limbs)` and returns the carry 318 * (1 if there was a wraparound, and 0 otherwise). 319 * 320 * \p X may be aliased to \p A or \p B. 321 * 322 * \param[out] X The result of the addition. 323 * \param[in] A Little-endian presentation of the left operand. 324 * \param[in] B Little-endian presentation of the right operand. 325 * \param limbs Number of limbs of \p X, \p A and \p B. 326 * 327 * \return 1 if `A + B >= 2^(biL*limbs)`, 0 otherwise. 328 */ 329mbedtls_mpi_uint mbedtls_mpi_core_add(mbedtls_mpi_uint *X, 330 const mbedtls_mpi_uint *A, 331 const mbedtls_mpi_uint *B, 332 size_t limbs); 333 334/** 335 * \brief Conditional addition of two fixed-size large unsigned integers, 336 * returning the carry. 337 * 338 * Functionally equivalent to 339 * 340 * ``` 341 * if( cond ) 342 * X += A; 343 * return carry; 344 * ``` 345 * 346 * This function operates modulo `2^(biL*limbs)`. 347 * 348 * \param[in,out] X The pointer to the (little-endian) array 349 * representing the bignum to accumulate onto. 350 * \param[in] A The pointer to the (little-endian) array 351 * representing the bignum to conditionally add 352 * to \p X. This may be aliased to \p X but may not 353 * overlap otherwise. 354 * \param limbs Number of limbs of \p X and \p A. 355 * \param cond Condition bit dictating whether addition should 356 * happen or not. This must be \c 0 or \c 1. 357 * 358 * \warning If \p cond is neither 0 nor 1, the result of this function 359 * is unspecified, and the resulting value in \p X might be 360 * neither its original value nor \p X + \p A. 361 * 362 * \return 1 if `X + cond * A >= 2^(biL*limbs)`, 0 otherwise. 363 */ 364mbedtls_mpi_uint mbedtls_mpi_core_add_if(mbedtls_mpi_uint *X, 365 const mbedtls_mpi_uint *A, 366 size_t limbs, 367 unsigned cond); 368 369/** 370 * \brief Subtract two fixed-size large unsigned integers, returning the borrow. 371 * 372 * Calculate `A - B` where \p A and \p B have the same size. 373 * This function operates modulo `2^(biL*limbs)` and returns the carry 374 * (1 if there was a wraparound, i.e. if `A < B`, and 0 otherwise). 375 * 376 * \p X may be aliased to \p A or \p B, or even both, but may not overlap 377 * either otherwise. 378 * 379 * \param[out] X The result of the subtraction. 380 * \param[in] A Little-endian presentation of left operand. 381 * \param[in] B Little-endian presentation of right operand. 382 * \param limbs Number of limbs of \p X, \p A and \p B. 383 * 384 * \return 1 if `A < B`. 385 * 0 if `A >= B`. 386 */ 387mbedtls_mpi_uint mbedtls_mpi_core_sub(mbedtls_mpi_uint *X, 388 const mbedtls_mpi_uint *A, 389 const mbedtls_mpi_uint *B, 390 size_t limbs); 391 392/** 393 * \brief Perform a fixed-size multiply accumulate operation: X += b * A 394 * 395 * \p X may be aliased to \p A (when \p X_limbs == \p A_limbs), but may not 396 * otherwise overlap. 397 * 398 * This function operates modulo `2^(biL*X_limbs)`. 399 * 400 * \param[in,out] X The pointer to the (little-endian) array 401 * representing the bignum to accumulate onto. 402 * \param X_limbs The number of limbs of \p X. This must be 403 * at least \p A_limbs. 404 * \param[in] A The pointer to the (little-endian) array 405 * representing the bignum to multiply with. 406 * This may be aliased to \p X but may not overlap 407 * otherwise. 408 * \param A_limbs The number of limbs of \p A. 409 * \param b X scalar to multiply with. 410 * 411 * \return The carry at the end of the operation. 412 */ 413mbedtls_mpi_uint mbedtls_mpi_core_mla(mbedtls_mpi_uint *X, size_t X_limbs, 414 const mbedtls_mpi_uint *A, size_t A_limbs, 415 mbedtls_mpi_uint b); 416 417/** 418 * \brief Perform a known-size multiplication 419 * 420 * \p X may not be aliased to any of the inputs for this function. 421 * \p A may be aliased to \p B. 422 * 423 * \param[out] X The pointer to the (little-endian) array to receive 424 * the product of \p A_limbs and \p B_limbs. 425 * This must be of length \p A_limbs + \p B_limbs. 426 * \param[in] A The pointer to the (little-endian) array 427 * representing the first factor. 428 * \param A_limbs The number of limbs in \p A. 429 * \param[in] B The pointer to the (little-endian) array 430 * representing the second factor. 431 * \param B_limbs The number of limbs in \p B. 432 */ 433void mbedtls_mpi_core_mul(mbedtls_mpi_uint *X, 434 const mbedtls_mpi_uint *A, size_t A_limbs, 435 const mbedtls_mpi_uint *B, size_t B_limbs); 436 437/** 438 * \brief Calculate initialisation value for fast Montgomery modular 439 * multiplication 440 * 441 * \param[in] N Little-endian presentation of the modulus. This must have 442 * at least one limb. 443 * 444 * \return The initialisation value for fast Montgomery modular multiplication 445 */ 446mbedtls_mpi_uint mbedtls_mpi_core_montmul_init(const mbedtls_mpi_uint *N); 447 448/** 449 * \brief Montgomery multiplication: X = A * B * R^-1 mod N (HAC 14.36) 450 * 451 * \p A and \p B must be in canonical form. That is, < \p N. 452 * 453 * \p X may be aliased to \p A or \p N, or even \p B (if \p AN_limbs == 454 * \p B_limbs) but may not overlap any parameters otherwise. 455 * 456 * \p A and \p B may alias each other, if \p AN_limbs == \p B_limbs. They may 457 * not alias \p N (since they must be in canonical form, they cannot == \p N). 458 * 459 * \param[out] X The destination MPI, as a little-endian array of 460 * length \p AN_limbs. 461 * On successful completion, X contains the result of 462 * the multiplication `A * B * R^-1` mod N where 463 * `R = 2^(biL*AN_limbs)`. 464 * \param[in] A Little-endian presentation of first operand. 465 * Must have the same number of limbs as \p N. 466 * \param[in] B Little-endian presentation of second operand. 467 * \param[in] B_limbs The number of limbs in \p B. 468 * Must be <= \p AN_limbs. 469 * \param[in] N Little-endian presentation of the modulus. 470 * This must be odd, and have exactly the same number 471 * of limbs as \p A. 472 * It may alias \p X, but must not alias or otherwise 473 * overlap any of the other parameters. 474 * \param[in] AN_limbs The number of limbs in \p X, \p A and \p N. 475 * \param mm The Montgomery constant for \p N: -N^-1 mod 2^biL. 476 * This can be calculated by `mbedtls_mpi_core_montmul_init()`. 477 * \param[in,out] T Temporary storage of size at least 2*AN_limbs+1 limbs. 478 * Its initial content is unused and 479 * its final content is indeterminate. 480 * It must not alias or otherwise overlap any of the 481 * other parameters. 482 */ 483void mbedtls_mpi_core_montmul(mbedtls_mpi_uint *X, 484 const mbedtls_mpi_uint *A, 485 const mbedtls_mpi_uint *B, size_t B_limbs, 486 const mbedtls_mpi_uint *N, size_t AN_limbs, 487 mbedtls_mpi_uint mm, mbedtls_mpi_uint *T); 488 489/** 490 * \brief Calculate the square of the Montgomery constant. (Needed 491 * for conversion and operations in Montgomery form.) 492 * 493 * \param[out] X A pointer to the result of the calculation of 494 * the square of the Montgomery constant: 495 * 2^{2*n*biL} mod N. 496 * \param[in] N Little-endian presentation of the modulus, which must be odd. 497 * 498 * \return 0 if successful. 499 * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED if there is not enough space 500 * to store the value of Montgomery constant squared. 501 * \return #MBEDTLS_ERR_MPI_DIVISION_BY_ZERO if \p N modulus is zero. 502 * \return #MBEDTLS_ERR_MPI_NEGATIVE_VALUE if \p N modulus is negative. 503 */ 504int mbedtls_mpi_core_get_mont_r2_unsafe(mbedtls_mpi *X, 505 const mbedtls_mpi *N); 506 507#if defined(MBEDTLS_TEST_HOOKS) 508/** 509 * Copy an MPI from a table without leaking the index. 510 * 511 * \param dest The destination buffer. This must point to a writable 512 * buffer of at least \p limbs limbs. 513 * \param table The address of the table. This must point to a readable 514 * array of \p count elements of \p limbs limbs each. 515 * \param limbs The number of limbs in each table entry. 516 * \param count The number of entries in \p table. 517 * \param index The (secret) table index to look up. This must be in the 518 * range `0 .. count-1`. 519 */ 520void mbedtls_mpi_core_ct_uint_table_lookup(mbedtls_mpi_uint *dest, 521 const mbedtls_mpi_uint *table, 522 size_t limbs, 523 size_t count, 524 size_t index); 525#endif /* MBEDTLS_TEST_HOOKS */ 526 527/** 528 * \brief Fill an integer with a number of random bytes. 529 * 530 * \param X The destination MPI. 531 * \param X_limbs The number of limbs of \p X. 532 * \param bytes The number of random bytes to generate. 533 * \param f_rng The RNG function to use. This must not be \c NULL. 534 * \param p_rng The RNG parameter to be passed to \p f_rng. This may be 535 * \c NULL if \p f_rng doesn't need a context argument. 536 * 537 * \return \c 0 if successful. 538 * \return #MBEDTLS_ERR_MPI_BAD_INPUT_DATA if \p X does not have 539 * enough room for \p bytes bytes. 540 * \return A negative error code on RNG failure. 541 * 542 * \note The bytes obtained from the RNG are interpreted 543 * as a big-endian representation of an MPI; this can 544 * be relevant in applications like deterministic ECDSA. 545 */ 546int mbedtls_mpi_core_fill_random(mbedtls_mpi_uint *X, size_t X_limbs, 547 size_t bytes, 548 int (*f_rng)(void *, unsigned char *, size_t), 549 void *p_rng); 550 551/** Generate a random number uniformly in a range. 552 * 553 * This function generates a random number between \p min inclusive and 554 * \p N exclusive. 555 * 556 * The procedure complies with RFC 6979 §3.3 (deterministic ECDSA) 557 * when the RNG is a suitably parametrized instance of HMAC_DRBG 558 * and \p min is \c 1. 559 * 560 * \note There are `N - min` possible outputs. The lower bound 561 * \p min can be reached, but the upper bound \p N cannot. 562 * 563 * \param X The destination MPI, with \p limbs limbs. 564 * It must not be aliased with \p N or otherwise overlap it. 565 * \param min The minimum value to return. 566 * \param N The upper bound of the range, exclusive, with \p limbs limbs. 567 * In other words, this is one plus the maximum value to return. 568 * \p N must be strictly larger than \p min. 569 * \param limbs The number of limbs of \p N and \p X. 570 * This must not be 0. 571 * \param f_rng The RNG function to use. This must not be \c NULL. 572 * \param p_rng The RNG parameter to be passed to \p f_rng. 573 * 574 * \return \c 0 if successful. 575 * \return #MBEDTLS_ERR_MPI_NOT_ACCEPTABLE if the implementation was 576 * unable to find a suitable value within a limited number 577 * of attempts. This has a negligible probability if \p N 578 * is significantly larger than \p min, which is the case 579 * for all usual cryptographic applications. 580 */ 581int mbedtls_mpi_core_random(mbedtls_mpi_uint *X, 582 mbedtls_mpi_uint min, 583 const mbedtls_mpi_uint *N, 584 size_t limbs, 585 int (*f_rng)(void *, unsigned char *, size_t), 586 void *p_rng); 587 588/** 589 * \brief Returns the number of limbs of working memory required for 590 * a call to `mbedtls_mpi_core_exp_mod()`. 591 * 592 * \note This will always be at least 593 * `mbedtls_mpi_core_montmul_working_limbs(AN_limbs)`, 594 * i.e. sufficient for a call to `mbedtls_mpi_core_montmul()`. 595 * 596 * \param AN_limbs The number of limbs in the input `A` and the modulus `N` 597 * (they must be the same size) that will be given to 598 * `mbedtls_mpi_core_exp_mod()`. 599 * \param E_limbs The number of limbs in the exponent `E` that will be given 600 * to `mbedtls_mpi_core_exp_mod()`. 601 * 602 * \return The number of limbs of working memory required by 603 * `mbedtls_mpi_core_exp_mod()`. 604 */ 605size_t mbedtls_mpi_core_exp_mod_working_limbs(size_t AN_limbs, size_t E_limbs); 606 607/** 608 * \brief Perform a modular exponentiation with secret exponent: 609 * X = A^E mod N, where \p A is already in Montgomery form. 610 * 611 * \p X may be aliased to \p A, but not to \p RR or \p E, even if \p E_limbs == 612 * \p AN_limbs. 613 * 614 * \param[out] X The destination MPI, as a little endian array of length 615 * \p AN_limbs. 616 * \param[in] A The base MPI, as a little endian array of length \p AN_limbs. 617 * Must be in Montgomery form. 618 * \param[in] N The modulus, as a little endian array of length \p AN_limbs. 619 * \param AN_limbs The number of limbs in \p X, \p A, \p N, \p RR. 620 * \param[in] E The exponent, as a little endian array of length \p E_limbs. 621 * \param E_limbs The number of limbs in \p E. 622 * \param[in] RR The precomputed residue of 2^{2*biL} modulo N, as a little 623 * endian array of length \p AN_limbs. 624 * \param[in,out] T Temporary storage of at least the number of limbs returned 625 * by `mbedtls_mpi_core_exp_mod_working_limbs()`. 626 * Its initial content is unused and its final content is 627 * indeterminate. 628 * It must not alias or otherwise overlap any of the other 629 * parameters. 630 * It is up to the caller to zeroize \p T when it is no 631 * longer needed, and before freeing it if it was dynamically 632 * allocated. 633 */ 634void mbedtls_mpi_core_exp_mod(mbedtls_mpi_uint *X, 635 const mbedtls_mpi_uint *A, 636 const mbedtls_mpi_uint *N, size_t AN_limbs, 637 const mbedtls_mpi_uint *E, size_t E_limbs, 638 const mbedtls_mpi_uint *RR, 639 mbedtls_mpi_uint *T); 640 641/** 642 * \brief Subtract unsigned integer from known-size large unsigned integers. 643 * Return the borrow. 644 * 645 * \param[out] X The result of the subtraction. 646 * \param[in] A The left operand. 647 * \param b The unsigned scalar to subtract. 648 * \param limbs Number of limbs of \p X and \p A. 649 * 650 * \return 1 if `A < b`. 651 * 0 if `A >= b`. 652 */ 653mbedtls_mpi_uint mbedtls_mpi_core_sub_int(mbedtls_mpi_uint *X, 654 const mbedtls_mpi_uint *A, 655 mbedtls_mpi_uint b, 656 size_t limbs); 657 658/** 659 * \brief Determine if a given MPI has the value \c 0 in constant time with 660 * respect to the value (but not with respect to the number of limbs). 661 * 662 * \param[in] A The MPI to test. 663 * \param limbs Number of limbs in \p A. 664 * 665 * \return MBEDTLS_CT_FALSE if `A == 0` 666 * MBEDTLS_CT_TRUE if `A != 0`. 667 */ 668mbedtls_ct_condition_t mbedtls_mpi_core_check_zero_ct(const mbedtls_mpi_uint *A, 669 size_t limbs); 670 671/** 672 * \brief Returns the number of limbs of working memory required for 673 * a call to `mbedtls_mpi_core_montmul()`. 674 * 675 * \param AN_limbs The number of limbs in the input `A` and the modulus `N` 676 * (they must be the same size) that will be given to 677 * `mbedtls_mpi_core_montmul()` or one of the other functions 678 * that specifies this as the amount of working memory needed. 679 * 680 * \return The number of limbs of working memory required by 681 * `mbedtls_mpi_core_montmul()` (or other similar function). 682 */ 683static inline size_t mbedtls_mpi_core_montmul_working_limbs(size_t AN_limbs) 684{ 685 return 2 * AN_limbs + 1; 686} 687 688/** Convert an MPI into Montgomery form. 689 * 690 * \p X may be aliased to \p A, but may not otherwise overlap it. 691 * 692 * \p X may not alias \p N (it is in canonical form, so must be strictly less 693 * than \p N). Nor may it alias or overlap \p rr (this is unlikely to be 694 * required in practice.) 695 * 696 * This function is a thin wrapper around `mbedtls_mpi_core_montmul()` that is 697 * an alternative to calling `mbedtls_mpi_mod_raw_to_mont_rep()` when we 698 * don't want to allocate memory. 699 * 700 * \param[out] X The result of the conversion. 701 * Must have the same number of limbs as \p A. 702 * \param[in] A The MPI to convert into Montgomery form. 703 * Must have the same number of limbs as the modulus. 704 * \param[in] N The address of the modulus, which gives the size of 705 * the base `R` = 2^(biL*N->limbs). 706 * \param[in] AN_limbs The number of limbs in \p X, \p A, \p N and \p rr. 707 * \param mm The Montgomery constant for \p N: -N^-1 mod 2^biL. 708 * This can be determined by calling 709 * `mbedtls_mpi_core_montmul_init()`. 710 * \param[in] rr The residue for `2^{2*n*biL} mod N`. 711 * \param[in,out] T Temporary storage of size at least 712 * `mbedtls_mpi_core_montmul_working_limbs(AN_limbs)` 713 * limbs. 714 * Its initial content is unused and 715 * its final content is indeterminate. 716 * It must not alias or otherwise overlap any of the 717 * other parameters. 718 */ 719void mbedtls_mpi_core_to_mont_rep(mbedtls_mpi_uint *X, 720 const mbedtls_mpi_uint *A, 721 const mbedtls_mpi_uint *N, 722 size_t AN_limbs, 723 mbedtls_mpi_uint mm, 724 const mbedtls_mpi_uint *rr, 725 mbedtls_mpi_uint *T); 726 727/** Convert an MPI from Montgomery form. 728 * 729 * \p X may be aliased to \p A, but may not otherwise overlap it. 730 * 731 * \p X may not alias \p N (it is in canonical form, so must be strictly less 732 * than \p N). 733 * 734 * This function is a thin wrapper around `mbedtls_mpi_core_montmul()` that is 735 * an alternative to calling `mbedtls_mpi_mod_raw_from_mont_rep()` when we 736 * don't want to allocate memory. 737 * 738 * \param[out] X The result of the conversion. 739 * Must have the same number of limbs as \p A. 740 * \param[in] A The MPI to convert from Montgomery form. 741 * Must have the same number of limbs as the modulus. 742 * \param[in] N The address of the modulus, which gives the size of 743 * the base `R` = 2^(biL*N->limbs). 744 * \param[in] AN_limbs The number of limbs in \p X, \p A and \p N. 745 * \param mm The Montgomery constant for \p N: -N^-1 mod 2^biL. 746 * This can be determined by calling 747 * `mbedtls_mpi_core_montmul_init()`. 748 * \param[in,out] T Temporary storage of size at least 749 * `mbedtls_mpi_core_montmul_working_limbs(AN_limbs)` 750 * limbs. 751 * Its initial content is unused and 752 * its final content is indeterminate. 753 * It must not alias or otherwise overlap any of the 754 * other parameters. 755 */ 756void mbedtls_mpi_core_from_mont_rep(mbedtls_mpi_uint *X, 757 const mbedtls_mpi_uint *A, 758 const mbedtls_mpi_uint *N, 759 size_t AN_limbs, 760 mbedtls_mpi_uint mm, 761 mbedtls_mpi_uint *T); 762 763#endif /* MBEDTLS_BIGNUM_CORE_H */ 764