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