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