1 /** 2 * Low-level modular bignum functions 3 * 4 * This interface should only be used by the higher-level modular bignum 5 * module (bignum_mod.c) and the ECP module (ecp.c, ecp_curves.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 is a low-level interface to operations on integers modulo which 10 * has no protection against passing invalid arguments such as arrays of 11 * the wrong size. The functions in bignum_mod.h provide a higher-level 12 * interface that includes protections against accidental misuse, at the 13 * expense of code size and sometimes more cumbersome memory management. 14 * 15 * The functions in this module obey the following conventions unless 16 * explicitly indicated otherwise: 17 * - **Modulus parameters**: the modulus is passed as a pointer to a structure 18 * of type #mbedtls_mpi_mod_modulus. The structure must be set up with an 19 * array of limbs storing the bignum value of the modulus. The modulus must 20 * be odd and is assumed to have no leading zeroes. The modulus is usually 21 * named \c N and is usually input-only. 22 * - **Bignum parameters**: Bignums are passed as pointers to an array of 23 * limbs. A limb has the type #mbedtls_mpi_uint. Unless otherwise specified: 24 * - Bignum parameters called \c A, \c B, ... are inputs, and are not 25 * modified by the function. 26 * - Bignum parameters called \c X, \c Y are outputs or input-output. 27 * The initial content of output-only parameters is ignored. 28 * - \c T is a temporary storage area. The initial content of such a 29 * parameter is ignored and the final content is unspecified. 30 * - **Bignum sizes**: bignum sizes are usually expressed by the \c limbs 31 * member of the modulus argument. All bignum parameters must have the same 32 * number of limbs as the modulus. All bignum sizes must be at least 1 and 33 * must be significantly less than #SIZE_MAX. The behavior if a size is 0 is 34 * undefined. 35 * - **Bignum representation**: the representation of inputs and outputs is 36 * specified by the \c int_rep field of the modulus for arithmetic 37 * functions. Utility functions may allow for different representation. 38 * - **Parameter ordering**: for bignum parameters, outputs come before inputs. 39 * The modulus is passed after other bignum input parameters. Temporaries 40 * come last. 41 * - **Aliasing**: in general, output bignums may be aliased to one or more 42 * inputs. Modulus values may not be aliased to any other parameter. Outputs 43 * may not be aliased to one another. Temporaries may not be aliased to any 44 * other parameter. 45 * - **Overlap**: apart from aliasing of limb array pointers (where two 46 * arguments are equal pointers), overlap is not supported and may result 47 * in undefined behavior. 48 * - **Error handling**: This is a low-level module. Functions generally do not 49 * try to protect against invalid arguments such as nonsensical sizes or 50 * null pointers. Note that passing bignums with a different size than the 51 * modulus may lead to buffer overflows. Some functions which allocate 52 * memory or handle reading/writing of bignums will return an error if 53 * memory allocation fails or if buffer sizes are invalid. 54 * - **Modular representatives**: all functions expect inputs to be in the 55 * range [0, \c N - 1] and guarantee outputs in the range [0, \c N - 1]. If 56 * an input is out of range, outputs are fully unspecified, though bignum 57 * values out of range should not cause buffer overflows (beware that this is 58 * not extensively tested). 59 */ 60 61 /* 62 * Copyright The Mbed TLS Contributors 63 * SPDX-License-Identifier: Apache-2.0 64 * 65 * Licensed under the Apache License, Version 2.0 (the "License"); you may 66 * not use this file except in compliance with the License. 67 * You may obtain a copy of the License at 68 * 69 * http://www.apache.org/licenses/LICENSE-2.0 70 * 71 * Unless required by applicable law or agreed to in writing, software 72 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT 73 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 74 * See the License for the specific language governing permissions and 75 * limitations under the License. 76 */ 77 78 #ifndef MBEDTLS_BIGNUM_MOD_RAW_H 79 #define MBEDTLS_BIGNUM_MOD_RAW_H 80 81 #include "common.h" 82 83 #if defined(MBEDTLS_BIGNUM_C) 84 #include "mbedtls/bignum.h" 85 #endif 86 87 #include "bignum_mod.h" 88 89 /** 90 * \brief Perform a safe conditional copy of an MPI which doesn't reveal 91 * whether the assignment was done or not. 92 * 93 * The size to copy is determined by \p N. 94 * 95 * \param[out] X The address of the destination MPI. 96 * This must be initialized. Must have enough limbs to 97 * store the full value of \p A. 98 * \param[in] A The address of the source MPI. This must be initialized. 99 * \param[in] N The address of the modulus related to \p X and \p A. 100 * \param assign The condition deciding whether to perform the 101 * assignment or not. Must be either 0 or 1: 102 * * \c 1: Perform the assignment `X = A`. 103 * * \c 0: Keep the original value of \p X. 104 * 105 * \note This function avoids leaking any information about whether 106 * the assignment was done or not. 107 * 108 * \warning If \p assign is neither 0 nor 1, the result of this function 109 * is indeterminate, and the resulting value in \p X might be 110 * neither its original value nor the value in \p A. 111 */ 112 void mbedtls_mpi_mod_raw_cond_assign(mbedtls_mpi_uint *X, 113 const mbedtls_mpi_uint *A, 114 const mbedtls_mpi_mod_modulus *N, 115 unsigned char assign); 116 117 /** 118 * \brief Perform a safe conditional swap of two MPIs which doesn't reveal 119 * whether the swap was done or not. 120 * 121 * The size to swap is determined by \p N. 122 * 123 * \param[in,out] X The address of the first MPI. This must be initialized. 124 * \param[in,out] Y The address of the second MPI. This must be initialized. 125 * \param[in] N The address of the modulus related to \p X and \p Y. 126 * \param swap The condition deciding whether to perform 127 * the swap or not. Must be either 0 or 1: 128 * * \c 1: Swap the values of \p X and \p Y. 129 * * \c 0: Keep the original values of \p X and \p Y. 130 * 131 * \note This function avoids leaking any information about whether 132 * the swap was done or not. 133 * 134 * \warning If \p swap is neither 0 nor 1, the result of this function 135 * is indeterminate, and both \p X and \p Y might end up with 136 * values different to either of the original ones. 137 */ 138 void mbedtls_mpi_mod_raw_cond_swap(mbedtls_mpi_uint *X, 139 mbedtls_mpi_uint *Y, 140 const mbedtls_mpi_mod_modulus *N, 141 unsigned char swap); 142 143 /** Import X from unsigned binary data. 144 * 145 * The MPI needs to have enough limbs to store the full value (including any 146 * most significant zero bytes in the input). 147 * 148 * \param[out] X The address of the MPI. The size is determined by \p N. 149 * (In particular, it must have at least as many limbs as 150 * the modulus \p N.) 151 * \param[in] N The address of the modulus related to \p X. 152 * \param[in] input The input buffer to import from. 153 * \param input_length The length in bytes of \p input. 154 * \param ext_rep The endianness of the number in the input buffer. 155 * 156 * \return \c 0 if successful. 157 * \return #MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if \p X isn't 158 * large enough to hold the value in \p input. 159 * \return #MBEDTLS_ERR_MPI_BAD_INPUT_DATA if the external representation 160 * of \p N is invalid or \p X is not less than \p N. 161 */ 162 int mbedtls_mpi_mod_raw_read(mbedtls_mpi_uint *X, 163 const mbedtls_mpi_mod_modulus *N, 164 const unsigned char *input, 165 size_t input_length, 166 mbedtls_mpi_mod_ext_rep ext_rep); 167 168 /** Export A into unsigned binary data. 169 * 170 * \param[in] A The address of the MPI. The size is determined by \p N. 171 * (In particular, it must have at least as many limbs as 172 * the modulus \p N.) 173 * \param[in] N The address of the modulus related to \p A. 174 * \param[out] output The output buffer to export to. 175 * \param output_length The length in bytes of \p output. 176 * \param ext_rep The endianness in which the number should be written into the output buffer. 177 * 178 * \return \c 0 if successful. 179 * \return #MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if \p output isn't 180 * large enough to hold the value of \p A. 181 * \return #MBEDTLS_ERR_MPI_BAD_INPUT_DATA if the external representation 182 * of \p N is invalid. 183 */ 184 int mbedtls_mpi_mod_raw_write(const mbedtls_mpi_uint *A, 185 const mbedtls_mpi_mod_modulus *N, 186 unsigned char *output, 187 size_t output_length, 188 mbedtls_mpi_mod_ext_rep ext_rep); 189 190 /* BEGIN MERGE SLOT 1 */ 191 192 /* END MERGE SLOT 1 */ 193 194 /* BEGIN MERGE SLOT 2 */ 195 196 /** \brief Subtract two MPIs, returning the residue modulo the specified 197 * modulus. 198 * 199 * The size of the operation is determined by \p N. \p A and \p B must have 200 * the same number of limbs as \p N. 201 * 202 * \p X may be aliased to \p A or \p B, or even both, but may not overlap 203 * either otherwise. 204 * 205 * \param[out] X The address of the result MPI. 206 * This must be initialized. Must have enough limbs to 207 * store the full value of the result. 208 * \param[in] A The address of the first MPI. This must be initialized. 209 * \param[in] B The address of the second MPI. This must be initialized. 210 * \param[in] N The address of the modulus. Used to perform a modulo 211 * operation on the result of the subtraction. 212 */ 213 void mbedtls_mpi_mod_raw_sub(mbedtls_mpi_uint *X, 214 const mbedtls_mpi_uint *A, 215 const mbedtls_mpi_uint *B, 216 const mbedtls_mpi_mod_modulus *N); 217 218 /** \brief Multiply two MPIs, returning the residue modulo the specified 219 * modulus. 220 * 221 * \note Currently handles the case when `N->int_rep` is 222 * MBEDTLS_MPI_MOD_REP_MONTGOMERY. 223 * 224 * The size of the operation is determined by \p N. \p A, \p B and \p X must 225 * all be associated with the modulus \p N and must all have the same number 226 * of limbs as \p N. 227 * 228 * \p X may be aliased to \p A or \p B, or even both, but may not overlap 229 * either otherwise. They may not alias \p N (since they must be in canonical 230 * form, they cannot == \p N). 231 * 232 * \param[out] X The address of the result MPI. Must have the same 233 * number of limbs as \p N. 234 * On successful completion, \p X contains the result of 235 * the multiplication `A * B * R^-1` mod N where 236 * `R = 2^(biL * N->limbs)`. 237 * \param[in] A The address of the first MPI. 238 * \param[in] B The address of the second MPI. 239 * \param[in] N The address of the modulus. Used to perform a modulo 240 * operation on the result of the multiplication. 241 * \param[in,out] T Temporary storage of size at least 2 * N->limbs + 1 242 * limbs. Its initial content is unused and 243 * its final content is indeterminate. 244 * It must not alias or otherwise overlap any of the 245 * other parameters. 246 */ 247 void mbedtls_mpi_mod_raw_mul(mbedtls_mpi_uint *X, 248 const mbedtls_mpi_uint *A, 249 const mbedtls_mpi_uint *B, 250 const mbedtls_mpi_mod_modulus *N, 251 mbedtls_mpi_uint *T); 252 253 /* END MERGE SLOT 2 */ 254 255 /* BEGIN MERGE SLOT 3 */ 256 257 /** 258 * \brief Returns the number of limbs of working memory required for 259 * a call to `mbedtls_mpi_mod_raw_inv_prime()`. 260 * 261 * \note This will always be at least 262 * `mbedtls_mpi_core_montmul_working_limbs(AN_limbs)`, 263 * i.e. sufficient for a call to `mbedtls_mpi_core_montmul()`. 264 * 265 * \param AN_limbs The number of limbs in the input `A` and the modulus `N` 266 * (they must be the same size) that will be given to 267 * `mbedtls_mpi_mod_raw_inv_prime()`. 268 * 269 * \return The number of limbs of working memory required by 270 * `mbedtls_mpi_mod_raw_inv_prime()`. 271 */ 272 size_t mbedtls_mpi_mod_raw_inv_prime_working_limbs(size_t AN_limbs); 273 274 /** 275 * \brief Perform fixed-width modular inversion of a Montgomery-form MPI with 276 * respect to a modulus \p N that must be prime. 277 * 278 * \p X may be aliased to \p A, but not to \p N or \p RR. 279 * 280 * \param[out] X The modular inverse of \p A with respect to \p N. 281 * Will be in Montgomery form. 282 * \param[in] A The number to calculate the modular inverse of. 283 * Must be in Montgomery form. Must not be 0. 284 * \param[in] N The modulus, as a little-endian array of length \p AN_limbs. 285 * Must be prime. 286 * \param AN_limbs The number of limbs in \p A, \p N and \p RR. 287 * \param[in] RR The precomputed residue of 2^{2*biL} modulo N, as a little- 288 * endian array of length \p AN_limbs. 289 * \param[in,out] T Temporary storage of at least the number of limbs returned 290 * by `mbedtls_mpi_mod_raw_inv_prime_working_limbs()`. 291 * Its initial content is unused and its final content is 292 * indeterminate. 293 * It must not alias or otherwise overlap any of the other 294 * parameters. 295 * It is up to the caller to zeroize \p T when it is no 296 * longer needed, and before freeing it if it was dynamically 297 * allocated. 298 */ 299 void mbedtls_mpi_mod_raw_inv_prime(mbedtls_mpi_uint *X, 300 const mbedtls_mpi_uint *A, 301 const mbedtls_mpi_uint *N, 302 size_t AN_limbs, 303 const mbedtls_mpi_uint *RR, 304 mbedtls_mpi_uint *T); 305 306 /* END MERGE SLOT 3 */ 307 308 /* BEGIN MERGE SLOT 4 */ 309 310 /* END MERGE SLOT 4 */ 311 312 /* BEGIN MERGE SLOT 5 */ 313 /** 314 * \brief Perform a known-size modular addition. 315 * 316 * Calculate `A + B modulo N`. 317 * 318 * The number of limbs in each operand, and the result, is given by the 319 * modulus \p N. 320 * 321 * \p X may be aliased to \p A or \p B, or even both, but may not overlap 322 * either otherwise. 323 * 324 * \param[out] X The result of the modular addition. 325 * \param[in] A Little-endian presentation of the left operand. This 326 * must be smaller than \p N. 327 * \param[in] B Little-endian presentation of the right operand. This 328 * must be smaller than \p N. 329 * \param[in] N The address of the modulus. 330 */ 331 void mbedtls_mpi_mod_raw_add(mbedtls_mpi_uint *X, 332 const mbedtls_mpi_uint *A, 333 const mbedtls_mpi_uint *B, 334 const mbedtls_mpi_mod_modulus *N); 335 /* END MERGE SLOT 5 */ 336 337 /* BEGIN MERGE SLOT 6 */ 338 339 /** Convert an MPI from canonical representation (little-endian limb array) 340 * to the representation associated with the modulus. 341 * 342 * \param[in,out] X The limb array to convert. 343 * It must have as many limbs as \p N. 344 * It is converted in place. 345 * If this function returns an error, the content of \p X 346 * is unspecified. 347 * \param[in] N The modulus structure. 348 * 349 * \return \c 0 if successful. 350 * Otherwise an \c MBEDTLS_ERR_MPI_xxx error code. 351 */ 352 int mbedtls_mpi_mod_raw_canonical_to_modulus_rep( 353 mbedtls_mpi_uint *X, 354 const mbedtls_mpi_mod_modulus *N); 355 356 /** Convert an MPI from the representation associated with the modulus 357 * to canonical representation (little-endian limb array). 358 * 359 * \param[in,out] X The limb array to convert. 360 * It must have as many limbs as \p N. 361 * It is converted in place. 362 * If this function returns an error, the content of \p X 363 * is unspecified. 364 * \param[in] N The modulus structure. 365 * 366 * \return \c 0 if successful. 367 * Otherwise an \c MBEDTLS_ERR_MPI_xxx error code. 368 */ 369 int mbedtls_mpi_mod_raw_modulus_to_canonical_rep( 370 mbedtls_mpi_uint *X, 371 const mbedtls_mpi_mod_modulus *N); 372 373 /** Generate a random number uniformly in a range. 374 * 375 * This function generates a random number between \p min inclusive and 376 * \p N exclusive. 377 * 378 * The procedure complies with RFC 6979 §3.3 (deterministic ECDSA) 379 * when the RNG is a suitably parametrized instance of HMAC_DRBG 380 * and \p min is \c 1. 381 * 382 * \note There are `N - min` possible outputs. The lower bound 383 * \p min can be reached, but the upper bound \p N cannot. 384 * 385 * \param X The destination MPI, in canonical representation modulo \p N. 386 * It must not be aliased with \p N or otherwise overlap it. 387 * \param min The minimum value to return. It must be strictly smaller 388 * than \b N. 389 * \param N The modulus. 390 * This is the upper bound of the output range, exclusive. 391 * \param f_rng The RNG function to use. This must not be \c NULL. 392 * \param p_rng The RNG parameter to be passed to \p f_rng. 393 * 394 * \return \c 0 if successful. 395 * \return #MBEDTLS_ERR_MPI_NOT_ACCEPTABLE if the implementation was 396 * unable to find a suitable value within a limited number 397 * of attempts. This has a negligible probability if \p N 398 * is significantly larger than \p min, which is the case 399 * for all usual cryptographic applications. 400 */ 401 int mbedtls_mpi_mod_raw_random(mbedtls_mpi_uint *X, 402 mbedtls_mpi_uint min, 403 const mbedtls_mpi_mod_modulus *N, 404 int (*f_rng)(void *, unsigned char *, size_t), 405 void *p_rng); 406 407 /* END MERGE SLOT 6 */ 408 409 /* BEGIN MERGE SLOT 7 */ 410 /** Convert an MPI into Montgomery form. 411 * 412 * \param X The address of the MPI. 413 * Must have the same number of limbs as \p N. 414 * \param N The address of the modulus, which gives the size of 415 * the base `R` = 2^(biL*N->limbs). 416 * 417 * \return \c 0 if successful. 418 */ 419 int mbedtls_mpi_mod_raw_to_mont_rep(mbedtls_mpi_uint *X, 420 const mbedtls_mpi_mod_modulus *N); 421 422 /** Convert an MPI back from Montgomery representation. 423 * 424 * \param X The address of the MPI. 425 * Must have the same number of limbs as \p N. 426 * \param N The address of the modulus, which gives the size of 427 * the base `R`= 2^(biL*N->limbs). 428 * 429 * \return \c 0 if successful. 430 */ 431 int mbedtls_mpi_mod_raw_from_mont_rep(mbedtls_mpi_uint *X, 432 const mbedtls_mpi_mod_modulus *N); 433 434 /** \brief Perform fixed width modular negation. 435 * 436 * The size of the operation is determined by \p N. \p A must have 437 * the same number of limbs as \p N. 438 * 439 * \p X may be aliased to \p A. 440 * 441 * \param[out] X The result of the modular negation. 442 * This must be initialized. 443 * \param[in] A Little-endian presentation of the input operand. This 444 * must be less than or equal to \p N. 445 * \param[in] N The modulus to use. 446 */ 447 void mbedtls_mpi_mod_raw_neg(mbedtls_mpi_uint *X, 448 const mbedtls_mpi_uint *A, 449 const mbedtls_mpi_mod_modulus *N); 450 /* END MERGE SLOT 7 */ 451 452 /* BEGIN MERGE SLOT 8 */ 453 454 /* END MERGE SLOT 8 */ 455 456 /* BEGIN MERGE SLOT 9 */ 457 458 /* END MERGE SLOT 9 */ 459 460 /* BEGIN MERGE SLOT 10 */ 461 462 /* END MERGE SLOT 10 */ 463 464 #endif /* MBEDTLS_BIGNUM_MOD_RAW_H */ 465
